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

[Eric Bodden]

Hmmm, you should probably try to tell us what you are actually trying
to achieve. What do you want to analyze/optimize?

> 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() ).

Dominance is usually defined on a control flow graph (containing basic
blocks). Such a graph (usually) never spans multiple methods. So it's
true that everything before the *call* to Bar() dominates the *call*
to Bar(). But you cannot actually say that this code dominates Bar()
itself. You could obviously define something like interprocedural
dominance but then you would have to use the call graph of the program
to find out that Bar() is really only called once at that place plus
that the call to Bar() can only resolve to the single Bar() method and
not to another method (via polymorphism). Basically you would have to
have inlining semantics.

> 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.

That's not generally true. In fact, the call to Bar() would could be
part of the basic block that precedes this statement.

> 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?
> 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 the Dominator Analysis not expand the call to Bar() and simply create
> a Basic Block that was just the method call to Bar()?

Yes, I think you are misunderstanding the common definition of
dominance. Dominance is usually an *intra*procedural concept, i.e. it
does not make sense over across method boundaries. If you do want to
define such a thing as dominance *inter*procedurally you have to do it
more or less manually by constructing dominator trees for each method
in question and then combining them using call graph information.

However, since I am not sure what your actual goal is, I am not sure
if there might not be an easier solution to your problem.

Eric

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