post-dominance frontier

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

post-dominance frontier

Ryan M. Lefever
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?

Regards,
Ryan


* "Efficiently Computing Static Single Assignment Form and the Control
Dependence Graph" by Cytron, Ferrante, Rosen, Wegman, and Zadeck

--
Ryan M. Lefever  [http://www.ews.uiuc.edu/~lefever]
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: post-dominance frontier

Chris Lattner
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

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: 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
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev