[LLVMdev] post-dominance frontier
Ryan M. Lefever
lefever at crhc.uiuc.edu
Tue Dec 19 16:12:24 PST 2006
In a message that I had previously posted, contained below, I inquired
about how the post-dominance frontier of a procedure is computed in
LLVM. I was informed that LLVM does not use a CFG that is augmented
with a dummy entry and exit node, when it computes the post-dominance
frontier. Does that change the result when computing the post-dominance
frontier?
I am asking because that is what I believe is happening in an LLVM
transformation that I'm working on.
Below is a function that on which I am running the transform, with all
instructions stripped from the function, except terminator instructions:
----------
void %load_array(int %var_name) {
entry:
br bool %tmp, label %return, label %cond_next
cond_next: ; preds = %entry
br bool %bothcond, label %bb, label %cond_next8
cond_next8: ; preds = %cond_next
br bool %tmp10, label %cond_next12, label %bb21
cond_next12: ; preds = %cond_next8
br bool %tmp17, label %bb, label %bb21
bb: ; preds = %cond_next12, %cond_next
ret void
bb21: ; preds = %cond_next12, %cond_next8
br bool %tmp26, label %return, label %cond_true27
cond_true27: ; preds = %bb21
br bool %tmp.i, label %pop.exit, label %cond_true.i
cond_true.i: ; preds = %cond_true27
br label %pop.exit
pop.exit: ; preds = %cond_true.i, %cond_true27
ret void
return: ; preds = %bb21, %entry
ret void
}
----------
Using LLVM's calculations, the post-dominance-frontier for each basic
block is as follows:
Basic Block Post-Dominance-Frontier
----------- -----------------------
entry -
bb -
cond_next8 cond_next
cond_next12 cond_next
cond_next -
bb21 cond_next8, cond_next12
cond_true27 cond_next8, cond_next12
pop.exit cond_next8, cond_next12
cond_true.i cond_true27
Using my hand calculations and a CFG augmented with a dummy entry and
exit node, I computed the post-dominance-frontier as follows:
Basic Block Post-Dominance-Frontier
----------- -----------------------
DummyEntry -
entry DummyEntry
cond_next entry
cond_next8 cond_next
cond_next12 cond_next8
bb21 cond_next8, cond_next12
cond_true27 bb21
cond_true.i cond_true27
pop.exit bb21
bb cond_next, cond_next12
return entry, bb21
DummyExit -
I may have made mistakes in my hand calculations because I may
misunderstand the post-dominance frontier. If so, please let me know.
If not, can someone please explain why there is a difference in the way
LLVM computes the post-dominance frontier and the way classic literature
says describes its computation.
For reference, below is the dot input of the non-augmented CFG of the
function I gave above:
----------
digraph{
entry->cond_next;
entry->return;
cond_next->cond_next8;
cond_next->bb;
cond_next8->cond_next12;
cond_next8->bb21;
cond_next12->bb;
cond_next12->bb21;
bb21->cond_true27;
bb21->return;
cond_true27->"cond_true.i";
cond_true27->"pop.exit";
"cond_true.i"->"pop.exit";
}
----------
Here is the dot input for the augmented CFG of the function I gave above:
----------
digraph{
DummyEntry->entry;
DummyEntry->DummyExit;
entry->cond_next;
entry->return;
cond_next->cond_next8;
cond_next->bb;
cond_next8->cond_next12;
cond_next8->bb21;
cond_next12->bb;
cond_next12->bb21;
bb21->cond_true27;
bb21->return;
cond_true27->"cond_true.i";
cond_true27->"pop.exit";
"cond_true.i"->"pop.exit";
bb->DummyExit;
"pop.exit"->DummyExit;
return->DummyExit;
}
----------
Regards,
Ryan
Chris Lattner wrote:
> On Thu, 9 Nov 2006, Ryan M. Lefever wrote:
>
> Sorry I never responded to this:
>
>> In the literature (see below for a reference), when a dominance frontier
>> is computed, it is computed from a CFG that contains a dummy entry node
>> and dummy exit node. Further, those dummy nodes are potential members
>> of the (post-)dominance frontier for a given basic block. In LLVM, I
>> could not figure out a way to determine if the dummy entry node is a
>> member of the post-dominance frontier of a basic block. Is there a way
>> to get that information?
>
> LLVM doesn't use dummy entrance/exit nodes. LLVM functions always have a
> single entry node (the first BB in the function) and multiple exits are
> handled specially.
>
> -Chris
>
>> Regards,
>> Ryan
>>
>>
>> * "Efficiently Computing Static Single Assignment Form and the Control
>> Dependence Graph" by Cytron, Ferrante, Rosen, Wegman, and Zadeck
>>
>>
>
> -Chris
>
More information about the llvm-dev
mailing list