ir: use value.Value for operands of instructions?

[mewmew]

This has come up in discussion and would enable APIs such as Operands() []*value.Value, which would allow not only use tracking, but also value replacement; as proposed by @pwaller. (ref: #42)

Depending on how far we wish to take this API change, there are some benefits and drawbacks. The main drawback I can see is if we change instructions (and terminators) to take value.Value instead of *ir.BasicBlock, since then users of the API cannot make use of the basic block directly, but would have to type assert to inspect the instructions of the basic block for instance. This is also true for the phi instruction, for which Incoming may be redefined as follows:

 // Incoming is an incoming value of a phi instruction.
 type Incoming struct {
 	// Incoming value.
 	X value.Value
 	// Predecessor basic block of the incoming value.
-	Pred *BasicBlock
+	Pred value.Value // *ir.BasicBlock
 }

Another instruction that would change is catchdad, which would take a value.Value instead of the concrete type *TermCatchSwitch:

 // InstCatchPad is an LLVM IR catchpad instruction.
 type InstCatchPad struct {
 	// Name of local variable associated with the result.
 	LocalIdent
 	// Exception scope.
- 	Scope *TermCatchSwitch
+ 	Scope value.Value // *ir.TermCatchSwitch
 	// Exception arguments.
 	Args []value.Value
 
 	// extra.
 
 	// (optional) Metadata.
 	Metadata []*metadata.MetadataAttachment
 }

Besides the phi and catchpad instructions, quite a few terminators would be update to make use of value.Value instead of *ir.BasicBlock.

 // TermCondBr is a conditional LLVM IR br terminator.
 type TermCondBr struct {
 	// Branching condition.
 	Cond value.Value
 	// True condition target branch.
-	TargetTrue *BasicBlock
+	TargetTrue value.Value // *ir.BasicBlock
 	// False condition target branch.
-	TargetFalse *BasicBlock
+	TargetFalse value.Value // *ir.BasicBlock
 
 	// extra.
 
 	// Successor basic blocks of the terminator.
 	Successors []*BasicBlock
 	// (optional) Metadata.
 	Metadata []*metadata.MetadataAttachment
 }

The catchret terminator would take a value.Value instead of *ir.InstCatchPad

It is also possible we'd have to update ir.Case to take a value.Value instead of a constant.Constant if we want to use this approach for also refining/updating/replacing values and not just for read-only access to operands.

 // Case is a switch case.
 type Case struct {
 	// Case comparand.
-	X constant.Constant // integer constant or integer constant expression
+	X value.Value // integer constant or integer constant expression
 	// Case target branch.
 	Target *BasicBlock
 }

I'm currently on the fence whether this change is good or not. The data types become less exact with what values they may contain, and specifically for basic blocks, users of the API would have to type assert to access the fields specific to basic blocks (such as its instructions). On the other hand, it would enable a general and quite powerful API for operand tracking and replacement.

I'll label this for the v0.4.0 release for now, as it mostly targets data analysis and the use-def chains API.

Any input is warmly welcome.

Cheers,
/u

[hosewiejacke]

I played with the official python API and everything being a value (including instructions that do not return a value) was bewildering. Don't know what's better in this case, though.

[mewmew]

Hi @hosewiejacke

I played with the official python API and everything being a value (including instructions that do not return a value) was bewildering. Don't know what's better in this case, though.

I agree, you kind of feel like a compiler construction Wizard when everything can be used as an operand to everything else.

I think we've struck a good balance atm with what instructions implement the value.Value interface. Essentially, anything you can use as an operand to another instruction is a value. The few remaining instructions, mostly fence and store which instead only implement the ir.Instruction and can thus only be appended to the list of instructions in a basic block.

Regarding this issue, we are trying to figure out if relaxing the type constraints on the concrete struct types of various instructions may allow for more powerful data flow analysis APIs in future releases of llir/llvm. There is an obvious trade-off. The more concrete of a type you have as members of the structs, the more knowledge is presented to the user, e.g. using *ir.BasicBlock for the target of a branch instruction provides more knowledge than if we use a value.Value.

However, if we relax this and use value.Value throughout, then we could have APIs that allow not only retrieval of information about value uses throughout the IR, but also makes it possible to have APIs that update the values through *value.Value pointer access.

We will continue to collect information, and see what are the various benefits and drawbacks with different approaches. I think I'm starting to lean more and more to the side of using value.Value throughout. We will see :)

Wish you a great winter holidays and happy coding!

Cheers,
Robin

[mewmew]

Hmm, I've been using the help wanted labels for indicating that we'd like to get more input and various views for the design discussions. Perhaps this label is more often interpreted to mean something along the lines of we need help to implement this rather than please join our discussion to nail the API. Should we add a new label (e.g. ongoing discussion, user input wanted, or something along those lines) instead?

cc: @pwaller.

[hosewiejacke]

Perhaps this label is more often interpreted to mean something along the lines of *we need help to implement this*

Yes, that's how I interpret it.

Should we add a new label (e.g. *ongoing discussion*, *user input wanted*, or something along those lines) instead?

SGTM.

[mewmew]

Perhaps this label is more often interpreted to mean something along the lines of we need help to implement this
Yes, that's how I interpret it.
Should we add a new label (e.g. ongoing discussion, user input wanted, or something along those lines) instead?
SGTM.

Good. I've added the proposal label now, perhaps that is enough to indicate that this is a design decision that needs to be fleshed out and that welcome anyone to contribution to the discussion.