In this recipe, you will learn about instruction combining in LLVM. By instruction combining, we mean replacing a sequence of instructions with more efficient instructions that produce the same result in fewer machine cycles. In this recipe, we will see how we can make modifications in the LLVM code to combine certain instructions.
To test our implementation, we will write test code that we will use to verify that our implementation is working properly to combine instructions:
define i32 @test19(i32 %x, i32 %y, i32 %z) {
%xor1 = xor i32 %y, %z
%or = or i32 %x, %xor1
%xor2 = xor i32 %x, %z
%xor3 = xor i32 %xor2, %y
%res = xor i32 %or, %xor3
ret i32 %res
}- Open the
lib/Transforms/InstCombine/InstCombineAndOrXor.cppfile. - In the
InstCombiner::visitXor(BinaryOperator&I)function, go to theifcondition—if(Op0I&&Op1I)—and add this:if (match(Op0I, m_Or(m_Xor(m_Value(B), m_Value(C)), m_Value(A))) && match(Op1I, m_Xor( m_Xor(m_Specific(A), m_Specific(C)), m_Specific(B)))) { return BinaryOperator::CreateAnd(A, Builder->CreateXor(B,C)); } - Now build LLVM again so that the Opt tool can use the new functionality and run the test case in this way:
Opt –instcombine –S testcode.ll define i32 @test19(i32 %x, i32 %y, i32 %z) { %1 = xor i32 %y, %z %res = and i32 %1, %x ret i32 %res }
In this recipe, we added code to the instruction combining file, which handles transformations involving the AND, OR, and XOR operators.
We added code for matching the pattern of the (A | (B ^ C)) ^ ((A ^ C) ^ B) form, and reduced it to A & (B ^ C). The if (match(Op0I, m_Or(m_Xor(m_Value(B), m_Value(C)), m_Value(A))) && match(Op1I, m_Xor( m_Xor(m_Specific(A), m_Specific(C)), m_Specific(B)))) line looks out for the pattern similar to the one shown at the start of this paragraph.
The return BinaryOperator::CreateAnd(A, Builder->CreateXor(B,C)); line returns the reduced value after building a new instruction, replacing the previous matched code.
When we run the instcombine pass over the test code, we get the reduced result. You can see the number of operations is reduced from five to two.
- The topic of instruction combining is very wide, and there are loads and loads of possibilities. Similar to the instruction combining function is the instruction simplify function, where we simplify complicated instructions but don't necessarily reduce the number of instructions, as is the case with instruction combining. To look more deeply into this, go through the code in the
lib/Transforms/InstCombinefolder