[LLVMdev] post-dominance frontier

[Ryan M. Lefever]

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
>