Instruction simplification example

In this section, we will see how we fold instructions into simpler forms in LLVM. Here, the creation of new instructions will not take place. Instruction simplification does constant folding:

sub i32 2, 1 -> 1

That is, it simplifies the sub instruction to a constant value 1.

It can handle non-constant operands as well:

or i32 %x, 0 -> %x

It returns a value of variable %x 

and i32 %x %x -> %x

In this case, it returns an already existing value.

The implementations for the methods that simplify instructions are located in lib/Analysis/InstructionSimplify.cpp.

Some of the important methods of dealing with the simplification of instructions are:

  • SimplifyBinOp method: This is used to simplify binary operations such as addition, subtraction, and multiplication, and so on. It has the function signature as follows:
    static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, 
Value *RHS, const Query &Q, unsigned MaxRecurse)

Here, by Opcode, we mean the operator instruction that we are trying to simplify. LHS and RHS are the operands on either side of the operator. MaxRecurse is the recursion level we specify after which the routine must stop trying simplification of the instruction.

In this method, we have a switch case on the Opcode:

switch (Opcode) {

Using this Opcode, the method decides which function it needs to call for simplification. Some of the methods are as follows:

  • SimplifyAddInst: This method tries to fold the result of the Add operator when the operands are known. Some of the folding is as follows:
    X + undef -> undef
X + 0 -> X
X + (Y - X) -> Y or (Y - X) + X -> Y

The code for the last simplification in the function static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const Query &Q, unsigned MaxRecurse ) looks something like this:

if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
      match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
    return Y;

Here, the first condition matches the (Y-X) value in the expression as Operand1: m_Value(Y) denotes value of Y and m_Specific(Op0) denotes X. As soon as it is matched it folds the expression to a constant value Y and returns it. The case is similar for the second part of our condition:

  • SimplifySubInst: This method tries to fold the result of subtract operator when the operators are known. Some examples for the same are as follows:
    X - undef -> undef
X - X -> 0
X - 0 -> X
X - (X - Y) -> Y

The matching of instructions and folding is done similar to as shown in SimplifyAddInst:

  • SimplifyAndInst: Similar to the two preceding methods, it tries to fold the result for the logical operator And. Some examples of this are:
    A & ~A  =  ~A & A  =  0

The code for this, in the method looks like:

if (match(Op0, m_Not(m_Specific(Op1))) ||
      match(Op1, m_Not(m_Specific(Op0))))
    return Constant::getNullValue(Op0->getType());

Here, it tries to match A and ~A and returns a Null value, 0, when it matches the condition.

So, we have seen a bit of instruction simplification. Now, what do we do if we can replace a set of instructions with a more effective set of instructions?

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.118.152.58