[LLVMdev] Specify dominator for BasicBlock to avoid "Instruction does not dominate all uses!"

Devang Patel
2010-10-11T17:59:03Z

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