Re: Soot bugs when first Unit is a target

[John Jorgensen <jorgnsn@lcd.uregina.ca>]

    olohtak> Then, in UnitGraph, these methods must respect the
    olohtak> specification and indeed return nodes with
    olohtak> in/out-degree zero. This means that we need to
    olohtak> somehow identify entry/exit points.

    olohtak> I've been thinking about your example, where the entry point
    olohtak> has an edge into it. I think this is very strange,
    olohtak> and is not usually the case in the example graphs
    olohtak> that people look at when they think about flow
    olohtak> analysis.

From my notes last summer, I have a simpler---albeit still
contrived---example method that Soot-2.1.0 claims has no heads.

    static int counter;
    static void lookMaNoHeads() {
       do {
            System.out.println(counter);
	    counter--;
       } while (counter > 0);
    }

The lack of heads per se produced no direct difficulties---it seemed
few analyses make much use of getHeads()---but BlockGraph did crash
because of the bug Archie noted.

Before going on, I'll cite my description of the current
behaviour of my revisions to UnitGraph, so we all know what is
currently in the repository as well as what is released in Soot
2.1.0:

  The new abstract UnitGraph class supplies a default
  buildHeadsAndTails() method which preserves the old behaviour
  where predecessor-less units are heads and successor-less units
  are tails. This method is used by all subclasses of UnitGraph
  except ExceptionalUnitGraph, which includes as a head the
  initial unit in the method, and the first unit in every handler
  that might catch an exception thrown by the initial unit in the
  method (see the discussion of transitive exceptional control flow
  at the end of section 3.3.3). ExceptionalUnitGraph defines as a
  tail all return instructions and all explicit throws whose
  exception may escape the method.

The revised BlockGraph classes just define any Block which
begins with a head Unit to be a head Block, and any block which
ends with a tail unit to be a tail Block.

    olohtak> Since the entry/exit points have to be treated
    olohtak> specially (in many analyses, they are initialized to
    olohtak> different things), allowing them to have edges into
    olohtak> them will lead to confusing analyses at best, and
    olohtak> possibly incorrect ones as well. The standard thing
    olohtak> in textbooks seems to be to have dummy entry/exit
    olohtak> nodes.  Why can't we have those in UnitGraphs, and
    olohtak> add methods to return them?

My understanding is that Ondrej would essentially like to leave
the existing definition of UnitGraph.getHeads() and getTails()
unchanged in all subclasses---for consistency with
DirectedGraph---and move what ExceptionalUnitGraph() now calls
getHeds() and getTails() up into UnitGraph, but under a new name,
say, getEntryPoints() and getExitPoints().
BlockGraph.getHeads()/getTails() and
getEntryPoints()/getExitPoints() could continue to be derived
from the underlying UnitGraph.

I haven't reminded myself thoroughly enough about last year's
discussion to have any firm opinions to contribute.  I should
raise one point, though, which might matter.

To date, it has always been the case that every node in a
UnitGraph corresponds to a Unit in the associated Body's Chain.
From the analyses I have looked at (but I have made no systematic
survey), it seems typical to iterate through the Units of the
graph performing analyses or transformations. If the new dummy
entry node and exit node were full-fledged graph nodes (i.e. they
get listed by the graph iterator, the dummy entry point appears
as a predecessor of the Units that we used to call heads, etc),
though, there would then be graph nodes which do not correspond
to any Unit in the underlying Body (I imagine it could be
problematic to add corresponding Nops to the Chain, if only
because of the difficulty of keeping the NopEliminator from
getting rid of them again before you want).  This might
necessitate adding special cases to a number of existing analyses
so that they do not try to manipulate the nodes associated with
the entry point and exit point.

The cowardly---albeit inelegant---way out would be to add
ControlFlowGraph.getEntryPoints() and
ControlFlowGraph.getExitPoints() methods which return a list of
entry Units and exit Units as before, without any corresponding
dummy nodes in the graph. That would mean that the flow analysis
classes might still need to jump through hoops to merge the
initial entry flow values into the regular flow values, and it
would retain the current ugly kludges for adding extra entry
points when the first Unit in a method might throw a caught
exception. But it would save the necessity of combing existing
code for possible problems with dummy nodesB.