Dominator error inserting instructions into BasicBlock

Hi,

I've been writing some optimization passes for LLVM and had good luck with
the simple stuff, but I am running into all kinds of trouble trying to make copies of variables within a BasicBlock as part of a LoopPass

I am trying to make copies of the variables that are in scope in the loop body like so:

  //Remove the existing terminator
  first_block->getTerminator()->eraseFromParent();

  //Get the symbol table so that we know what to store
  ValueSymbolTable* vst = first_block->getValueSymbolTable();

  IRBuilder <> builder(first_block);
  for (ValueSymbolTable::iterator vst_it = vst->begin(); vst_it !=
vst->end(); vst_it++) {
        AllocaInst* store_var = builder.CreateAlloca(type, 0,my_name.c_str());
        builder.CreateStore(symbol, store_var, true);
     }

//Put a terminator on the block
builder.CreateRetVoid();

This builds fine, but I get dominator issues when I try to test it with opt.
I'm sure that I just don't understand all of the constraints on the IR, but
I would appreciate it if anyone can point me in the right direction. The
output from opt is below.

Instruction does not dominate all uses!
        %inc = add i32 %tmp1, 1 ; <i32> [#uses=2] volatile
store i32 %inc, i32* %_my_inc
Instruction does not dominate all uses!
        %tmp1 = load i32* @i ; <i32> [#uses=2] volatile
store i32 %tmp1, i32* %_my_tmp1
Broken module found, compilation aborted!

Thanks,
Shane

Hi Shane,

Hi,

I've been writing some optimization passes for LLVM and had good luck
with
the simple stuff, but I am running into all kinds of trouble trying to
make copies of variables within a BasicBlock as part of a LoopPass

I am trying to make copies of the variables that are in scope in the
loop body like so:

Why do you want to copy variables ? What transformations are you doing
as a loop pass ?

//Remove the existing terminator
first_block->getTerminator()->eraseFromParent();

//Get the symbol table so that we know what to store
ValueSymbolTable* vst = first_block->getValueSymbolTable();

IRBuilder <> builder(first_block);
for (ValueSymbolTable::iterator vst_it = vst->begin(); vst_it !=
vst->end(); vst_it++) {
AllocaInst* store_var = builder.CreateAlloca(type,
0,my_name.c_str());
builder.CreateStore(symbol, store_var, true);
}

//Put a terminator on the block
builder.CreateRetVoid();

This builds fine, but I get dominator issues when I try to test it
with opt.
I'm sure that I just don't understand all of the constraints on the
IR, but
I would appreciate it if anyone can point me in the right direction. The
output from opt is below.

Instruction does not dominate all uses!
%inc = add i32 %tmp1, 1 ; <i32> [#uses=2] volatile
store i32 %inc, i32* %_my_inc

Here you're trying to store results of add instruction. But the error
message says the add instruction does not dominate store instruction.

Shane Clark wrote:

Hi,

I've been writing some optimization passes for LLVM and had good luck
with
the simple stuff, but I am running into all kinds of trouble trying to
make copies of variables within a BasicBlock as part of a LoopPass

I am trying to make copies of the variables that are in scope in the
loop body like so:
  

I haven't looked at your code below to see what is wrong, but I thought
I'd make a few comments on the LLVM IR that you may find useful. Please
see below.

  //Remove the existing terminator
  first_block->getTerminator()->eraseFromParent();

  //Get the symbol table so that we know what to store
  ValueSymbolTable* vst = first_block->getValueSymbolTable();

  IRBuilder <> builder(first_block);
  for (ValueSymbolTable::iterator vst_it = vst->begin(); vst_it !=
vst->end(); vst_it++) {
        AllocaInst* store_var = builder.CreateAlloca(type,
0,my_name.c_str());
        builder.CreateStore(symbol, store_var, true);
     }

//Put a terminator on the block
builder.CreateRetVoid();

This builds fine, but I get dominator issues when I try to test it
with opt.
I'm sure that I just don't understand all of the constraints on the
IR, but
  

The LLVM IR requires that all virtual registers be in SSA form. This
means that

a) Each virtual register has only 1 instruction that ever assigns a
value to it.
b) The instruction that assigns to the virtual register (or more
accurately, defines the virtual register) must dominate all uses of the
virtual register.

If you are creating something like a C local variable that can be
assigned to multiple times or that may be used in places not dominated
by its definition, then the best thing to do is to:

1) Create an alloca instruction that allocates stack memory to hold the
variable
2) Add LLVM load/store instructions to read/write the variable
3) Use the mem2reg pass (or the PromoteMemToReg() function in
llvm/Transforms/Utils/PromoteMemToReg.h) to promote the stack-allocated
memory into SSA virtual registers.

I'm not sure if this answers your question, but hopefully it will shine
some light on the constraints the LLVM IR places on virtual registers.

-- John T.