llvm dev - Oct 2010 - [LLVMdev] Specify dominator for BasicBlock to avoid "Instruction does not dominate all uses!"

Hi,

I am working on a pass aimed to unify multiple exits of a loop into a unique
basic block. The approach is straight forward: 
I create a unique BasicBlock BB_unique that has as predecessors all the exit
blocks of the loop, it contains a phi instruction and a switch to redirect
the flow correctly. Additionally, for each initial exit block I create an
associated block that will jump to the original successors of the exit
block.
In short:

    B1  B2  B3                      BB4 
     |     |     |                           |
      \    |    /                            |
       ExitBB1                     ExitBB2 
         |    |                            |     | 
       /       \                          /       \
EBB1.1 EBB1.2        EBB2.1     EBB2.2


becomes:

    B1  B2  B3                    BB4 
     |     |     |                       |
      \    |    /                        |
     ExitBB1                     ExitBB2 
           |                             |
        ----------------------------------
                        |
                  BB_unique
                 /                  \
    ExitBB1_redirect        ExitBB2_redirect
         |    |                            |    | 
       /       \                          /      \
EBB1.1 EBB1.2        EBB2.1     EBB2.2

And BB_unique contains:
%PHI_uniqueExit = phi i8 [ 0, %ExitBB1 ], [ 1, %ExitBB2 ]
  switch i8 %PHI_uniqueExit, label %switch_default [
    i8 0, label %ExitBB1_redirect
    i8 1, label %ExitBB2_redirect
  ]

The problem is that all instructions defined in ExitBB1 seem to not dominate
their uses, if they are used in successors of ExitBB1_redirect (similar for
ExitBB2). I understand that this comes from the fact that the verifier
considers that block EBB1.1 can be reached from BB_unique on another path
than from ExitBB1. And this gives the error "Instruction does not dominate
all uses!" if Instruction is defined in ExitBB1 and used in EBB1.1.
However,
because of the switch instruction, this is not possible. 

I tried to set the immediate dominator of ExitBB1_redirect to be ExitBB1
instead of BB_unique, but the error is still there.
The simple solution would be to move the body of ExitBB1 entirely into
ExitBB1_redirect, but this is not possible if there are any PHI
instructions.
Is there a clean solution to this problem? Can I inform the verifier that no
other path exists to reach ExitBB1_redirect, except from ExitBB1?  


Thanks, 
Alexandra


-- 
View this message in context:
http://old.nabble.com/Specify-dominator-for-BasicBlock-to-avoid-%22Instruction-does-not-dominate-all-uses%21%22-tp29935454p29935454.html
Sent from the LLVM - Dev mailing list archive at Nabble.com.

On Oct 11, 2010, at 9:05 AM, Xinfinity wrote:
> 
> Hi,
> 
> I am working on a pass aimed to unify multiple exits of a loop into a
unique
> basic block. The approach is straight forward: 
> I create a unique BasicBlock BB_unique that has as predecessors all the
exit
> blocks of the loop, it contains a phi instruction and a switch to redirect
> the flow correctly. Additionally, for each initial exit block I create an
> associated block that will jump to the original successors of the exit
> block.
> In short:
> 
>    B1  B2  B3                      BB4 
>     |     |     |                           |
>      \    |    /                            |
>       ExitBB1                     ExitBB2 
>         |    |                            |     | 
>       /       \                          /       \
> EBB1.1 EBB1.2        EBB2.1     EBB2.2
> 
> 
> becomes:
> 
>    B1  B2  B3                    BB4 
>     |     |     |                       |
>      \    |    /                        |
>     ExitBB1                     ExitBB2 
>           |                             |
>        ----------------------------------
>                        |
>                  BB_unique
>                 /                  \
>    ExitBB1_redirect        ExitBB2_redirect
>         |    |                            |    | 
>       /       \                          /      \
> EBB1.1 EBB1.2        EBB2.1     EBB2.2
> 
> And BB_unique contains:
> %PHI_uniqueExit = phi i8 [ 0, %ExitBB1 ], [ 1, %ExitBB2 ]
>  switch i8 %PHI_uniqueExit, label %switch_default [
>    i8 0, label %ExitBB1_redirect
>    i8 1, label %ExitBB2_redirect
>  ]
> 
> The problem is that all instructions defined in ExitBB1 seem to not
dominate
> their uses, if they are used in successors of ExitBB1_redirect (similar for
> ExitBB2). I understand that this comes from the fact that the verifier
> considers that block EBB1.1 can be reached from BB_unique on another path
> than from ExitBB1.
One approach is to use insert PHI nodes in BB_unique for values defined in
ExitBB1 and use these phi nodes in ExitBB1_redirect.

-
Devang
> And this gives the error "Instruction does not dominate
> all uses!" if Instruction is defined in ExitBB1 and used in EBB1.1.
However,
> because of the switch instruction, this is not possible. 
> 
> I tried to set the immediate dominator of ExitBB1_redirect to be ExitBB1
> instead of BB_unique, but the error is still there.
> The simple solution would be to move the body of ExitBB1 entirely into
> ExitBB1_redirect, but this is not possible if there are any PHI
> instructions.
> Is there a clean solution to this problem? Can I inform the verifier that
no
> other path exists to reach ExitBB1_redirect, except from ExitBB1?  
> 
> 
> Thanks, 
> Alexandra
> 
> 
> -- 
> View this message in context:
http://old.nabble.com/Specify-dominator-for-BasicBlock-to-avoid-%22Instruction-does-not-dominate-all-uses%21%22-tp29935454p29935454.html
> Sent from the LLVM - Dev mailing list archive at Nabble.com.
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi,

You may run the "RegToMem" pass before unify multiple exits of a loop
into a unique basic block, which will demotes all registers to memory
references, so you do not need to worried if your transform break the
SSA form.

and here is the introduction of RegToMem:
//===----------------------------------------------------------------------===//
//
// This file demotes all registers to memory references.  It is intented to be
// the inverse of PromoteMemoryToRegister.  By converting to loads, the only
// values live accross basic blocks are allocas and loads before phi nodes.
// It is intended that this should make CFG hacking much easier.
// To make later hacking easier, the entry block is split into two, such that
// all introduced allocas and nothing else are in the entry block.
//
//===----------------------------------------------------------------------===//

best regards
ether

Hi, I tried adding the PHI nodes in BB_unique, and it works for the simple
case described here, but in case the nodes were declared in some
predecessors of ExitBB1 and used in ExitBB1_redirect and its successors, it
won't work, unless I create entries for all of them in BB_unique.

B1 (declares PHI_1)                        B3
 |                                                     |   
B2                                                   |
|                                                      |
ExitBB1                                        ExitBB2
 |
Succ1 (uses PHI_1)

becomes:

B1 (declares PHI_1)                        B3
 |                                                     |   
B2                                                   |
|                                                      |
ExitBB1                                        ExitBB2
  |                                                    |
 -------------------------------------------------------
                           |
                  BB_unique
                   /            \
 ExitBB1_redirect     ExitBB2_redirect
             |
Succ1 (uses PHI_1)


 


Devang Patel wrote:
> 
> 
> 
> One approach is to use insert PHI nodes in BB_unique for values defined in
> ExitBB1 and use these phi nodes in ExitBB1_redirect.
> 
> 
> 
> Devang
> 
> 
> 
I will use the pass -reg2mem, as suggested by ether, to avoid to PHI nodes
altogether.

Thanks,
Alexandra
-

-- 
View this message in context:
http://old.nabble.com/Specify-dominator-for-BasicBlock-to-avoid-%22Instruction-does-not-dominate-all-uses%21%22-tp29935454p29942642.html
Sent from the LLVM - Dev mailing list archive at Nabble.com.