"vranganath" == Venkatesh Prasad Ranganath <vranganath@cox.net> writes:
vranganath> The way I had implemented this was to extend
vranganath> UnitGraph and modify the constructed CFG in the
vranganath> constructor of the extended class. Any
vranganath> suggestions as to how might I accomplish this via
vranganath> the new API.
This morning I described the easiest possibility to implement:
extending one of BriefUnitGraph, TrapUnitGraph,
CompleteUnitGraph, or ExceptionalUnitGraph instead (with the
choice depending on the parameters you've been passing to
UnitGraph's constructor).
From your description of how you remove some exceptional edges
from the CFG, I suspect your likely choice is
ExceptionalUnitGraph. Then you should be able to simply remove
the same edges from the result of
ExceptionalUnitGraph(body, PedanticThrowAnalysis.v(), false)
as you were removing from the result of
UnitGraph(body, true, false)
(though you might want to call
ExceptionalUnitGraph(body, UnitThrowAnalysis.v(), true)
instead; the result would not be identical to the result of
UnitGraph(body, true, false), but it omits exceptional
edges from units that can't actually throw the type of exception
that the destination handler catches, which you might be hoping
to eliminate anyway; more detail below if you want it).
ExceptionalUnitGraph's constructor is at least supposed to be
structured to allow you to avoid adding some of the edges in the
first place, rather than removing them after the fact. Doing so,
though, does require looking at how the constructor works. If
you're not interested in it, you can ignore the rest of the
message.
Constructing an ExceptionalUnitGraph consists of three steps:
1. Add the edges representing regular control flow, by calling the
buildUnexceptionalEdges() method inherited from UnitGraph.
2. Figure out which exceptions each Unit may throw, and where
they may be caught. This is performed by
ExceptionalUnitGraph.buildExceptionDests().
3. Derive the control flow edges corresponding to the
ExceptionDests. This is perfomed by
ExceptionalUnitGraph.buildExceptionalEdges().
You can modify each of the three steps by overriding methods, and
you can also influence the second step by passing a different
ThrowAnalysis to the constructor.
In more detail:
1. I can't imagine what you might want to change in step 1, but
you can override buildUnexceptionalEdges if you need to change
something.
2. buildExceptionDests() calls throwAnalysis.mightThrow(unit) for
every unit in the method to get a list of Exceptions that the
unit throws, and then looks for traps that can catch those
exceptions. The result is a set of ExceptionDest objects. For
example, in the snippet of code:
try {
d = 0; //0
a = b - c; //1
d = c/a; //2
} catch (ArithmeticException e) {
return d; //3
}
If the constructor is passed PedanticThrowAnalysis.v() (which
says that any unit can throw any exception), then
buildExceptionDests will produce three ExceptionDests saying
that each of statements 0, 1, and 2 may throw an
ArithmeticException to line 3.
If the constructor is passed UnitThrowAnalysis.v() (which uses
the specification of the bytecodes corresponding to each Unit
to determine what exceptions it might actually throw),
buildExceptionDests will create a single ExceptionDest for
the code sample, saying that line 1 can throw
ArithmeticException to line 3.
So if you are uninterested in some exception types, or if you
have a sophisticated analysis which proves some exceptions
cannot happen (e.g., an analysis that determines that b and c
in our example above cannot be equal, so a cannot be zero, and
the ArithmeticException is never thrown), you can write your
own ThrowAnalysis class which returns the corresponding set of
exceptions for each unit, and pass that instead of
PedanticThrowAnalysis.v(). Anything that provides the method
ThrowableSet mightThrow(Unit)
qualifies as a ThrowAnalysis.
You could also override buildExceptionDests() in a subclass of
ExceptionalUnitGraph, to ignore some of the exception types
reported by the ThrowAnalysis.
3. Essentially buildExceptionalEdges adds an edge to the handler
unit from each _predecessor_ of the unit throwing the
exception. In the case of athrow instructions and
instructions which call another method (including instructions
which might cause another class to be loaded, since that
triggers the execution of static initializers), we have to add
an edge from the instruction itself as well as its
predecessors, because of the possibility that the method call
has side effects that will occur before the exception gets
thrown.
I recall that you and I discussed this business of edges from
predecessors of excepting statements last fall. I picked my
example to re-illustrate their necessity: the CFG edge should be
from instruction 1 to instruction 3, not from instruction 2 to
instruction 3, because if the exception occurs, we know that d
still has the value 0. If we change the example to
try {
d = 0; //0
a = b - c; //1
d = m(c,a); //2
} catch (ArithmeticException e) {
return d; //3
}
there is still an ExceptionDest from 2 to 3, labeled with
ArithmeticException, because my strictly intraprocedural
ThrowAnalysis has to assume that method m might throw an
ArithmeticExpression (the VM does not enforce "throws"
declarations, so we can't trust them). Now, though, we need
CFG edges to line 3 from both lines 1 and 2. An edge from
line 2 is necessary so that program analyses take into account
the possibility that the call to m has changed something
before the exception is caught. An edge from line 1 is
necessary, so that dataflow analyses will realize that they
can't assume that the assignment to d has taken place.
The distinction between CFG edges proper and the flow of
exceptions is important to us because we use the graphs for
dataflow analyses. I don't know if the distinction matters
for your purposes.
The boolean parameter to the ExceptionalUnitGraph indicates
whether or not to add CFG edges to handlers from excepting
statements which have no side effects. I.e. in the original
version of our example, where line 2 reads "d = c/a", if you
pass "true" as the third parameter, there will be no edge from
line 2 to line 3, but if you pass "false", there will be an
edge. From the perspective of dataflow analyses, at least,
there is no reason to add CFG edges from statements without
side effects; the only reason to set the
omitExceptingUnitEdges parameter to "false" instead of "true"
is to preserve compatibility with the old CompleteUnitGraph.
So you can modify the behaviour of buildExceptionalUnitEdges
slightly by passing a different value for
omitExceptingUnitEdges, or you can override it completely. If
you overrride it, though, you need to be aware of the
necessity to perform transitive closures for the case where
the first statement in one handler might throw an exception to
the first statement in another, which might throw an exception
to the first statement in another ... There's a mention of
that in the technical report, but you probably need to look at
the code to understand what is going on.
(Self-justifying aside: The desire to allow you to tweak the
constructed graph without modifying existing code, incidentally,
is what prompted me to change the implementation of UnitGraph and
BlockGraph: before, because all the work was done in the
monolithic constructor of the parent graph, when people wanted to
get a new type of graph, they had to add code to the parent
constructor and pass a flag to activate that code (see, for
example the snippets of code in the BlockGraph constructor which
are actually specific to ArrayRefBlockGraph and ZonedBlockGraph).
It seems to me that this defeats the purpose of object-oriented
programming, since you need to modify existing code to extend it.
I have attempted to break the constructors up so that the code
specific to subclasses is actually found in those subclasses,
instead of within an if-statement in the superclass.)