Insert instructions in LLVM

Question

If I am trying to create an instruction and insert at the start of a function, will this be the right way as I could not see the instruction inserted when I used opt to load the .so file and process the .ll file.

if (auto* op = dyn_cast<Instruction>(&I))
{
    if(prepend_first == false)
    {
        llvm::LLVMContext& context = I.getContext();
        Value* lhs = ConstantInt::get(Type::getInt32Ty(context), 4);
        Value* rhs = ConstantInt::get(Type::getInt32Ty(context), 6);

        IRBuilder<> builder(op);
        builder.CreateMul(lhs, rhs);
        builder.SetInsertPoint(&I);

        prepend_first = true;
    }
}

EDIT (27 Nov 2020) This is the entire pass, which is based on other articles as well.

using namespace llvm;

namespace
{
    struct customllvm : public PassInfoMixin<customllvm>
    {
        llvm:PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
        {
            for(BasicBlock &BB : F)
            {
                bool prepend_first = false;

                for(Instruction &I : BB)
                {
                    if(auto *op = dyn_cast<Instruction>(&I))
                    {
                        if(prepend_first != true)
                        {
                            llvm::LLVMContext& context = I.getContext();
                            Value* lhs = ConstantInt::get(Type::getInt32Ty(context), 4);
                            Value* rhs = ConstantInt::get(Type::getInt32Ty(context), 6);

                            IRBuilder<> builder(op);
                            builder.CreateMul(lhs, rhs);
                            builder.SetInsertPoint(&I);

                            prepend_first = true;
                        }
                    }
                }
            }
        }
    }
}

Answer 1

It is neither about bad insertion nor optimizing out unused instruction. It is all about constant folding.

It is not related to SetInsertPoint() because IRBuilder<> IRB(&I) by default inserts the new instruction before instruction I. Therefore, in this example you do not even need to set the insertion point explicitly.

I will shortly show why it is nor related to removing unused instructions but I first explain two other problems with your pass:

1. Your pass does not necessarily insert the new instruction just at the start of a function as desired, but it inserts the new instruction at the start of each basic block of a function. Here are two solutions:

   • Set prepend_first to false only once and before the for(BasicBlock &BB : F) loop starts, so that prepend_first will be false only for the first basic block when reaching the checking if statement. This approach is not interesting though because of unnecessary iterations.

   • A better approach is to avoid iterations over basic blocks and instructions by directly selecting the first instruction of the first basic block. I will be using this approach in my passes.

2. Your dyn_cast<Instruction>(&I) checking cast is not necessary. This cast basically checks whether I is of Instruction type, which is obviously always true.

Here is my first_pass which is inspired by your code but free of the two issues explained above:

#include "llvm/IR/IRBuilder.h"
...
PreservedAnalyses first_pass(Function &F) {
  Function::iterator FI = F.begin();  //iterator to the first basic block
  BasicBlock &BB = *FI;
  BasicBlock::iterator BBI = BB.begin();  //iterator to the first instruction
  Instruction &I = *BBI;

  LLVMContext& context = I.getContext();
  Value* lhs = ConstantInt::get(Type::getInt32Ty(context), 4);
  Value* rhs = ConstantInt::get(Type::getInt32Ty(context), 6);

  IRBuilder<> builder(&I);
  builder.CreateMul(lhs, rhs, "new_mul");

  return PreservedAnalyses::none();
}

Note that first_pass yet does not insert the constant operation new_mul into an input IR. Before explaining about constant folding which is the root cause, let me first prove that your problem does not stem from removing unused code by doing an interesting experiment.

Here is my test.c:

int foo(int a, int b) {
  int c = a + 1;
  int d = b - 2;
  return c / d;
}

Here are the commands I used to generate test.ll which will be the input IR:

clang -O0 -Xclang -disable-O0-optnone -emit-llvm -c test.c -o test.bc
opt -S -mem2reg test.bc -o test.ll

And here is the generated test.ll:

; Function Attrs: noinline nounwind uwtable
define dso_local i32 @foo(i32 noundef %a, i32 noundef %b) #0 {
entry:
  %add = add nsw i32 %a, 1
  %sub = sub nsw i32 %b, 2
  %div = sdiv i32 %add, %sub
  ret i32 %div
}

Here is my second_pass which is the same as my first_pass with the difference that it uses the result of new_mul in the second instruction that it creates called new_add, so new_mul will be used this time. new_add is supposed to be inserted before the second instruction of the input IR:

#include "llvm/IR/IRBuilder.h"
...
PreservedAnalyses second_pass(Function &F) {
  Function::iterator FI = F.begin();
  BasicBlock &BB = *FI;
  BasicBlock::iterator BBI = BB.begin();
  Instruction &I = *BBI;

  LLVMContext& context = I.getContext();
  Value* lhs = ConstantInt::get(Type::getInt32Ty(context), 4);
  Value* rhs = ConstantInt::get(Type::getInt32Ty(context), 6);

  IRBuilder<> IRB(&I);
  auto new_mul = IRB.CreateMul(lhs, rhs, "new_mul");

  // Specific to this pass.
  Instruction &I_Sec = *(++BBI);    
  IRBuilder<> IRB_Sec(&I_Sec);
  IRB_Sec.CreateAdd(new_mul, I_Sec.getOperand(0), "new_add");

  return PreservedAnalyses::none();
}

I ran test.ll through second_pass and got this result IR:

; Function Attrs: noinline nounwind uwtable
define dso_local i32 @foo(i32 noundef %a, i32 noundef %b) #0 {
entry:
  %add = add nsw i32 %a, 1
  %new_add = add i32 24, %b
  %sub = sub nsw i32 %b, 2
  %div = sdiv i32 %add, %sub
  ret i32 %div
}

As we can see, although this time new_mul was used but yet it is not inserted into the result IR. Even more interestingly, new_add is successfully inserted into the result IR though it is not used. So it is clear that optimizing out unused code CANNOT be why new_mul is not generated.

Back to my main point: constant folding!

Constant folding is a compiler optimization where constant operations are evaluated at compile time instead of computing them at run time. In other words, the compiler does not generate code for a constant operation and in case the result of that operation is later used the compiler simply uses its value instead.

In your example, the new instruction that you are trying to create (new_mul) is a constant operation because both of its arguments are constants (4 and 6). Therefore, in the presence of constant folding the compiler does not generate code for it and in case it is later used (as in new_add of second_pass) the compiler uses its value instead (4 * 6 = 24).

It is very important to know that IRBuilder performs constant folding unless the folding type is explicitly specified otherwise. In other words, we have to use IRBuilder<llvm::NoFolder> instead of IRBuilder<> if we want the compiler NOT to perform constant folding.

Finally, here is my third_pass which is the same as my first_pass with the difference that it uses IRBuilder<llvm::NoFolder> instead of IRBuilder<> to create the constant operation new_mul:

#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/NoFolder.h"  // Do not forget to include.
...
PreservedAnalyses third_pass(Function &F) {
  Function::iterator FI = F.begin();  //iterator to the first basic block
  BasicBlock &BB = *FI;
  BasicBlock::iterator BBI = BB.begin();  //iterator to the first instruction
  Instruction &I = *BBI;

  LLVMContext& context = I.getContext();
  Value* lhs = ConstantInt::get(Type::getInt32Ty(context), 4);
  Value* rhs = ConstantInt::get(Type::getInt32Ty(context), 6);

  IRBuilder<llvm::NoFolder> builder(&I);  // NoFolder
  builder.CreateMul(lhs, rhs, "new_mul");

  return PreservedAnalyses::none();
}

Now if I run test.ll through third_pass I get this result IR:

; Function Attrs: noinline nounwind uwtable
define dso_local i32 @foo(i32 noundef %a, i32 noundef %b) #0 {
entry:
  %new_mul = mul i32 4, 6
  %add = add nsw i32 %a, 1
  %sub = sub nsw i32 %b, 2
  %div = sdiv i32 %add, %sub
  ret i32 %div
}

As we can see, new_mul is inserted at the beginning of the function as desired.

Answer 2

You need to set the insertion point first. And only then create instruction.