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

Xinfinity

unread,

Oct 11, 2010, 12:05:14 PM10/11/10

to llv...@cs.uiuc.edu

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:

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.

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Devang Patel

unread,

Oct 11, 2010, 1:59:03 PM10/11/10

to Xinfinity, llv...@cs.uiuc.edu

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

ether zhhb

unread,

Oct 11, 2010, 10:13:02 PM10/11/10

to Xinfinity, llv...@cs.uiuc.edu

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

Xinfinity

unread,

Oct 12, 2010, 8:24:55 AM10/12/10

to llv...@cs.uiuc.edu

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.

becomes:

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

ether zhhb

unread,

Oct 12, 2010, 8:49:38 AM10/12/10

to Xinfinity, llv...@cs.uiuc.edu

hi,

you may also add something like this in the "getAnalysisUsage" of your pass:

AU.addRequiredID(DemoteRegisterToMemoryID);

After this, the reg2mem pass will always run before your pass.

best regards
ether

Reply all

Reply to author

Forward