[Soot-list] Creating and Modifiying Dominator Trees? (and Various Questions)

[Ryan Rueth]

Sorry, I am quite new to most of this, so please forgive my ignorance.  I
think I did a poor job of describing my problem so let me try to restate
what I was worried about.

Assume, I have a class that has the following two methods:

Foo()
{
	...
	Bar();
	...
}

Bar()
{
	...
	If ( x < 0 )
	{	
		Y = 100;
	}	
	Else
	{
		Y = 50;
	}
	...
}

Now, assume that all I wanted to implement was a numerical numbering of each
dominator in the tree.  Now, my understanding is that the block of code that
occurs in Foo() before Bar() would dominate the entire Bar() block of code (
assuming Bar() is only ever called from Foo() ).  Thus, when I was numbering
the dominators, let's say there was only one basic block in Foo() before
calling Bar(), so we would label that #1, and then the first block in Bar()
would be labeled #2, and so forth.

Now, if I were trying to implement this numbering of dominators by making a
Transformer that extended BodyTransformer, wouldn't this cause problems if I
had methods that called other methods?  So, for example, we assume these are
the only two methods in my class.  Each method has one Body attached to it.
Now, we start running my transformation and it starts by numbering the
dominators in Foo() (as this is the first body it comes across we assume).
Now, the next body in the list would be Bar() and thus the transformation is
run and Bar() gets numbered for a second time.  

Wouldn't this either overwrite the previous tags or simply be redundant?  

Or am I completely misunderstanding how the dominator tree should be formed?


Would Bar() be called a second time (i.e. after it was seen in Foo())? 

Would the Dominator Analysis not expand the call to Bar() and simply create
a Basic Block that was just the method call to Bar()?

Thank you,
Ryan


-----Original Message-----
From: eric.bodden at googlemail.com [mailto:eric.bodden at googlemail.com] On
Behalf Of Eric Bodden
Sent: Monday, March 05, 2007 8:11 PM
To: Ryan Rueth
Cc: soot-list at sable.mcgill.ca
Subject: Re: [Soot-list] Creating and Modifiying Dominator Trees? (and
Various Questions)

On 3/5/07, Ryan Rueth <rrueth at gmail.com> wrote:
> So far, I believe I would just have to create a Transformer, but I'm not
> sure which I would extend.  I want to create a DominatorTree for the
entire
> .class file, so would I be extending SceneTransformer?

What do you mean by a dominator tree of a class file? Domination only
makes sense intraprocedurally. So you surely want to have a tree for
each method separately, don't you?

> If I made this a
> BodyTransformer, would that mean that I was only transforming each
> individual body of code (for example method1() and method2() would each be
> transformed separately and not integrated into a single DomintatorTree,
> assuming that method1 and method2 could actually be in the same Tree)?

A dominator tree holds no methods, it holds statements. What's your
notion of a dominator tree?

> So far, I have found the DominatorTree class
>
(http://www.sable.mcgill.ca/soot/doc/soot/toolkits/graph/DominatorTree.html)
> and I understand that I will need a DominatorsFinder class to pass the
> DominatorTree constructor, thus I'd probably use the
SimpleDominatorsFinder
>
(http://www.sable.mcgill.ca/soot/doc/soot/toolkits/graph/SimpleDominatorsFin
der.html).
>  In addition to that I'd need a DirectedGraph to pass that constructor, so
I
> was thinking about using something like the ExceptionalUnitGraph
>
(http://www.sable.mcgill.ca/soot/doc/soot/toolkits/graph/ExceptionalUnitGrap
h.html),
> but would this actually give me the DominatorTree for the entire .class
file
> that I passed in?  It seems like it only creates a graph for a single Body
> instance?

What you describe is the correct way of getting a dominator tree for a
*single method*... (1) create an ExceptionalUnitGraph for the method's
body (2) use SimpleDominatorsFinder to create a dominator tree.

There's no way of getting such information for an entire class and I
frankly don't see how this would make sense.

Eric

-- 
Eric Bodden
Sable Research Group
McGill University, Montréal, Canada