interface BinaryInstruction

[dannypsnl]

In some optimization, like value numbering, can find out BinaryInstruction automatically will be a nice feature. For example:

switch inst.(type) {
case ir.BinaryInstruction:
    opCode := inst.OpCode()
    v1 := getValueOf(inst.Operand(1))
    v2 := getValueOf(inst.Operand(2))
    hashKey := makeHashKey(v1, opCode, v2)
    // ...
}

[dannypsnl]

From @mewmew

The Operands function returns the operands for each instruction.
The GetOpCode function returns the opcode of each instruction.
The opcode.IsBinaryInst method may be used to distinguish binary instructions.

For now, we can place Operands, GetOpCode and OpCode in irutil. It is quite likely that we will move Operands to become a method for each instruction, and include it in the ir.Instruction interface.

For now, let's keep it in irutil and we can finalize the decision whether to move Operands to the ir.Instruction interface later.

[mewmew]

Uploaded a preliminary example for issue 191.

package main

import (
	"fmt"
	"log"

	"github.com/llir/llvm/asm"
	"github.com/llir/llvm/ir"
	"github.com/llir/llvm/ir/value"
	"github.com/pkg/errors"
)

func main() {
	if err := foo("foo.ll"); err != nil {
		log.Fatalf("%+v", err)
	}
}

func foo(llPath string) error {
	m, err := asm.ParseFile(llPath)
	if err != nil {
		return errors.WithStack(err)
	}
	for _, f := range m.Funcs {
		for _, block := range f.Blocks {
			for _, inst := range block.Insts {
				opcode := GetOpCode(inst)
				if opcode.IsBinaryInst() {
					operands := Operands(inst)
					makeHashKey(operands[0], opcode, operands[1])
				}
			}
		}
	}
	return nil
}

func makeHashKey(x value.Value, opcode OpCode, y value.Value) uint64 {
	fmt.Println("x:", x)
	fmt.Println("opcode:", opcode)
	fmt.Println("y:", y)
	// TODO: compute hash key
	return 0
}

// Operands returns the operands of the given instruction.
func Operands(inst ir.Instruction) []value.Value {
	switch inst := inst.(type) {
	// Unary instructions
	case *ir.InstFNeg:
		return []value.Value{inst.X}
	// Binary instructions
	case *ir.InstAdd:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstFAdd:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstSub:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstFSub:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstMul:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstFMul:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstUDiv:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstSDiv:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstFDiv:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstURem:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstSRem:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstFRem:
		return []value.Value{inst.X, inst.Y}
	// Bitwise instructions
	case *ir.InstShl:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstLShr:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstAShr:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstAnd:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstOr:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstXor:
		return []value.Value{inst.X, inst.Y}
	// Vector instructions
	case *ir.InstExtractElement:
		return []value.Value{inst.X, inst.Index}
	case *ir.InstInsertElement:
		return []value.Value{inst.X, inst.Elem, inst.Index}
	case *ir.InstShuffleVector:
		return []value.Value{inst.X, inst.Y, inst.Mask}
	// Aggregate instructions
	case *ir.InstExtractValue:
		return []value.Value{inst.X}
	case *ir.InstInsertValue:
		return []value.Value{inst.X, inst.Elem}
	// Memory instructions
	case *ir.InstAlloca:
		return []value.Value{inst.NElems}
	case *ir.InstLoad:
		return []value.Value{inst.Src}
	case *ir.InstStore:
		return []value.Value{inst.Src, inst.Dst}
	case *ir.InstFence:
		return nil
	case *ir.InstCmpXchg:
		return []value.Value{inst.Ptr, inst.Cmp, inst.New}
	case *ir.InstAtomicRMW:
		return []value.Value{inst.Dst, inst.X}
	case *ir.InstGetElementPtr:
		return append([]value.Value{inst.Src}, inst.Indices...)
	// Conversion instructions
	case *ir.InstTrunc:
		return []value.Value{inst.From}
	case *ir.InstZExt:
		return []value.Value{inst.From}
	case *ir.InstSExt:
		return []value.Value{inst.From}
	case *ir.InstFPTrunc:
		return []value.Value{inst.From}
	case *ir.InstFPExt:
		return []value.Value{inst.From}
	case *ir.InstFPToUI:
		return []value.Value{inst.From}
	case *ir.InstFPToSI:
		return []value.Value{inst.From}
	case *ir.InstUIToFP:
		return []value.Value{inst.From}
	case *ir.InstSIToFP:
		return []value.Value{inst.From}
	case *ir.InstPtrToInt:
		return []value.Value{inst.From}
	case *ir.InstIntToPtr:
		return []value.Value{inst.From}
	case *ir.InstBitCast:
		return []value.Value{inst.From}
	case *ir.InstAddrSpaceCast:
		return []value.Value{inst.From}
	// Other instructions
	case *ir.InstICmp:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstFCmp:
		return []value.Value{inst.X, inst.Y}
	case *ir.InstPhi:
		operands := make([]value.Value, 0, 2*len(inst.Incs))
		for _, inc := range inst.Incs {
			operands = append(operands, inc.X, inc.Pred)
		}
		return operands
	case *ir.InstSelect:
		return []value.Value{inst.Cond, inst.ValueTrue, inst.ValueFalse}
	case *ir.InstFreeze:
		return []value.Value{inst.X}
	case *ir.InstCall:
		return append([]value.Value{inst.Callee}, inst.Args...)
	case *ir.InstVAArg:
		return []value.Value{inst.ArgList}
	case *ir.InstLandingPad:
		var operands []value.Value
		for _, clause := range inst.Clauses {
			operands = append(operands, clause.X)
		}
		return operands
	case *ir.InstCatchPad:
		return append([]value.Value{inst.CatchSwitch}, inst.Args...)
	case *ir.InstCleanupPad:
		return append([]value.Value{inst.ParentPad}, inst.Args...)
	}
	panic(fmt.Errorf("support for instruction %T not yet implemented", inst))
}

// GetOpCode returns the op code of the given instruction
func GetOpCode(inst ir.Instruction) OpCode {
	switch inst.(type) {
	// Unary instructions
	case *ir.InstFNeg:
		return OpCodeInstFNeg
	// Binary instructions
	case *ir.InstAdd:
		return OpCodeInstAdd
	case *ir.InstFAdd:
		return OpCodeInstFAdd
	case *ir.InstSub:
		return OpCodeInstSub
	case *ir.InstFSub:
		return OpCodeInstFSub
	case *ir.InstMul:
		return OpCodeInstMul
	case *ir.InstFMul:
		return OpCodeInstFMul
	case *ir.InstUDiv:
		return OpCodeInstUDiv
	case *ir.InstSDiv:
		return OpCodeInstSDiv
	case *ir.InstFDiv:
		return OpCodeInstFDiv
	case *ir.InstURem:
		return OpCodeInstURem
	case *ir.InstSRem:
		return OpCodeInstSRem
	case *ir.InstFRem:
		return OpCodeInstFRem
	// Bitwise instructions
	case *ir.InstShl:
		return OpCodeInstShl
	case *ir.InstLShr:
		return OpCodeInstLShr
	case *ir.InstAShr:
		return OpCodeInstAShr
	case *ir.InstAnd:
		return OpCodeInstAnd
	case *ir.InstOr:
		return OpCodeInstOr
	case *ir.InstXor:
		return OpCodeInstXor
	// Vector instructions
	case *ir.InstExtractElement:
		return OpCodeInstExtractElement
	case *ir.InstInsertElement:
		return OpCodeInstInsertElement
	case *ir.InstShuffleVector:
		return OpCodeInstShuffleVector
	// Aggregate instructions
	case *ir.InstExtractValue:
		return OpCodeInstExtractValue
	case *ir.InstInsertValue:
		return OpCodeInstInsertValue
	// Memory instructions
	case *ir.InstAlloca:
		return OpCodeInstAlloca
	case *ir.InstLoad:
		return OpCodeInstLoad
	case *ir.InstStore:
		return OpCodeInstStore
	case *ir.InstFence:
		return OpCodeInstFence
	case *ir.InstCmpXchg:
		return OpCodeInstCmpXchg
	case *ir.InstAtomicRMW:
		return OpCodeInstAtomicRMW
	case *ir.InstGetElementPtr:
		return OpCodeInstGetElementPtr
	// Conversion instructions
	case *ir.InstTrunc:
		return OpCodeInstTrunc
	case *ir.InstZExt:
		return OpCodeInstZExt
	case *ir.InstSExt:
		return OpCodeInstSExt
	case *ir.InstFPTrunc:
		return OpCodeInstFPTrunc
	case *ir.InstFPExt:
		return OpCodeInstFPExt
	case *ir.InstFPToUI:
		return OpCodeInstFPToUI
	case *ir.InstFPToSI:
		return OpCodeInstFPToSI
	case *ir.InstUIToFP:
		return OpCodeInstUIToFP
	case *ir.InstSIToFP:
		return OpCodeInstSIToFP
	case *ir.InstPtrToInt:
		return OpCodeInstPtrToInt
	case *ir.InstIntToPtr:
		return OpCodeInstIntToPtr
	case *ir.InstBitCast:
		return OpCodeInstBitCast
	case *ir.InstAddrSpaceCast:
		return OpCodeInstAddrSpaceCast
	// Other instructions
	case *ir.InstICmp:
		return OpCodeInstICmp
	case *ir.InstFCmp:
		return OpCodeInstFCmp
	case *ir.InstPhi:
		return OpCodeInstPhi
	case *ir.InstSelect:
		return OpCodeInstSelect
	case *ir.InstFreeze:
		return OpCodeInstFreeze
	case *ir.InstCall:
		return OpCodeInstCall
	case *ir.InstVAArg:
		return OpCodeInstVAArg
	case *ir.InstLandingPad:
		return OpCodeInstLandingPad
	case *ir.InstCatchPad:
		return OpCodeInstCatchPad
	case *ir.InstCleanupPad:
		return OpCodeInstCleanupPad
	}
	panic(fmt.Errorf("support for instruction %T not yet implemented", inst))
}

//go:generate stringer -type OpCode

// OpCode represents the op code of an instruction.
type OpCode int

// IsBinaryInst reports whether the given op code is a binary or bitwise
// instruction.
func (opcode OpCode) IsBinaryInst() bool {
	switch opcode {
	// Binary instructions
	case OpCodeInstAdd, OpCodeInstFAdd, OpCodeInstSub, OpCodeInstFSub, OpCodeInstMul, OpCodeInstFMul, OpCodeInstUDiv, OpCodeInstSDiv, OpCodeInstFDiv, OpCodeInstURem, OpCodeInstSRem, OpCodeInstFRem:
		return true
	// Bitwise instructions
	case OpCodeInstShl, OpCodeInstLShr, OpCodeInstAShr, OpCodeInstAnd, OpCodeInstOr, OpCodeInstXor:
		return true
	}
	return false
}

// Instruction op codes.
const (
	OpCodeNone OpCode = 0
	// Unary instructions
	OpCodeInstFNeg OpCode = iota + 1
	// Binary instructions
	OpCodeInstAdd
	OpCodeInstFAdd
	OpCodeInstSub
	OpCodeInstFSub
	OpCodeInstMul
	OpCodeInstFMul
	OpCodeInstUDiv
	OpCodeInstSDiv
	OpCodeInstFDiv
	OpCodeInstURem
	OpCodeInstSRem
	OpCodeInstFRem
	// Bitwise instructions
	OpCodeInstShl
	OpCodeInstLShr
	OpCodeInstAShr
	OpCodeInstAnd
	OpCodeInstOr
	OpCodeInstXor
	// Vector instructions
	OpCodeInstExtractElement
	OpCodeInstInsertElement
	OpCodeInstShuffleVector
	// Aggregate instructions
	OpCodeInstExtractValue
	OpCodeInstInsertValue
	// Memory instructions
	OpCodeInstAlloca
	OpCodeInstLoad
	OpCodeInstStore
	OpCodeInstFence
	OpCodeInstCmpXchg
	OpCodeInstAtomicRMW
	OpCodeInstGetElementPtr
	// Conversion instructions
	OpCodeInstTrunc
	OpCodeInstZExt
	OpCodeInstSExt
	OpCodeInstFPTrunc
	OpCodeInstFPExt
	OpCodeInstFPToUI
	OpCodeInstFPToSI
	OpCodeInstUIToFP
	OpCodeInstSIToFP
	OpCodeInstPtrToInt
	OpCodeInstIntToPtr
	OpCodeInstBitCast
	OpCodeInstAddrSpaceCast
	// Other instructions
	OpCodeInstICmp
	OpCodeInstFCmp
	OpCodeInstPhi
	OpCodeInstSelect
	OpCodeInstFreeze
	OpCodeInstCall
	OpCodeInstVAArg
	OpCodeInstLandingPad
	OpCodeInstCatchPad
	OpCodeInstCleanupPad
)

[mewmew]

Related discussions in #42.

There are two considerations we should take, both outlined by @pwaller:

1. return pointer to value.Value from Operands to allow mutation.
2. pass destination slice to Operands to avoid allocation

Regarding the first point, I think this will allow for a very powerful API. Similar to the IR traversal API (inspired by Go fix) that we have in irutil.Walk.

Regarding the second point. While preferable to keep memory allocations low, up until now, we've prioritized a simpler API for llir/llvm over potential to reduce memory allocations. In particular, for methods which allocate and return slices ((e.g. ir.Terminator.Succs). For consistency and a continued prioritization of simplified API, I think we should skip the second point and keep the API as simple as possible.

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
}

Cheers,
Robin

[mewmew]

Related to this issue, the Operands method is implemented in PR #214.

[dannypsnl]

close by #214.