llvm dev - Aug 2009 - [LLVMdev] 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,

On Tue, Aug 4, 2009 at 6:11 PM, Shane Clark<ssclark at cs.umass.edu>
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:
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.
> 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!
>

-
Devang

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.
> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>