Use tracking

[mewmew]

The issue is intended to track discussions and experimental implementation related to use tracking.

The C++ API of LLVM defines the concepts of a Use and a User. A Use is an edge between a used value and its user. Each User has a number of operands which specify the Used values. Pseudo code follows:

type Value interface {
	Uses() []Use
}

type Use interface {
	OpNum() int
	User() User
	Usee() Value
}

type User() interface {
	NOps() int
	Op(i int) Value
	SetOp(i int, v Value) error
}

Anyone is invited to join the discussion. How would users of the API which to use it? May it be implemented by a dedicated package separate from the ir package? How would the interaction work? May there co-exist several implementations of use-tracking, and is this ever useful?

[andybalholm]

The simplest thing that could possibly work would be to make Instructions and Terminators fulfill this interface:

interface ValueUser {
    ValuesUsed() []Value
}

Then users of the package could implement their own use tracking without needing a giant type switch; they could treat all ValueUsers alike.

But once you've done that, building a map from Values to ValueUsers would be simple enough that you might as well do it too:

func FindUsers(f *ir.Func) map[Value][]ValueUser

[mewmew]

Looks great.

The ValuesUsed method is essentially identical to the proposed Operands method (see #42 and #191 (comment)).

From #191 (comment):

Suggested re-definition of ir.Instruction (and potentially ir.Terminator) interface:

package ir

// Instruction is an LLVM IR instruction. All instructions (except store and
// fence) implement the value.Named interface and may thus be used directly as
// values.
//
// An Instruction has one of the following underlying types.
//
// ...
type Instruction interface {
	LLStringer
	// isInstruction ensures that only instructions can be assigned to the
	// instruction.Instruction interface.
	isInstruction()
	// Operands returns a mutable list of operands of the instruction.
	Operands() []*value.Value
}

And correspondingly for ir.Terminator.

package ir

// Terminator is an LLVM IR terminator instruction (a control flow instruction).
//
// A Terminator has one of the following underlying types.
//
// ...
type Terminator interface {
	LLStringer
	// Succs returns the successor basic blocks of the terminator.
	Succs() []*Block
	// Operands returns a mutable list of operands of the terminator.
	Operands() []*value.Value
}

Essentially, the only difference between the ValuesUsed and the Operands method is that Operands returns a mutable slice of values ([]*value.Value).

I propose we go ahead with implementing the Operands method for ir.Instruction and ir.Terminator, and have it return a mutable list of values, thus supporting both use tracking and operand modification.

The ValueUser interface would then be defined something along the lines of:

package value

// ValueUser is an instruction or terminator which uses values as operands.
type ValueUser interface {
	// Operands returns a mutable list of operands of the value user (instruction or terminator).
	Operands() []*Value
}

@andybalholm and @dannypsnl, what are your thoughts on this API?

Cheers,
Robin

[andybalholm]

Sounds good to me. I'm not sure if ValueUser is the best name for the interface if the method is named Operands, but I don't know what name to suggest.

[mewmew]

Sounds good to me. I'm not sure if ValueUser is the best name for the interface if the method is named Operands, but I don't know what name to suggest.

I think it's fine. If we figure out a better one while implementing the feature, we can change it.

How about value.User? This matches the name used in the official LLVM API (ref: https://llvm.org/doxygen/classllvm_1_1User.html).

[dannypsnl]

So we only need to merge operands branch?

[andybalholm]

Yes, I think value.User would be fine.

[mewmew]

So we only need to merge operands branch?

Almost. The operands branch still used non-mutable lists for operands. I made a new PR (#214) returning a mutable list from the Operands method. Otherwise, they should be identical.

Cheers,
Robin