[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Soot bugs when first Unit is a target

I will look at the bug in ArrayBoundsCheckElimination, but cannot guarantee a time limit for now.

Ondrej LHOTAK wrote:
On Fri, Jul 16, 2004 at 09:41:37AM -0500, Archie Cobbs wrote:

Chris Pickett wrote:

Why not try and introduce (at the right time) fake heads (using NOP's?) before targets that are the first statement?

NopEliminator would probably interfere with this plan; you'd have to stop it from touching graph heads until you were done with Jimple, and then go back and get rid of all those heads. It could work, I think. 

I tried it and it didn't work, even if I added the Nop's after
the jop phase had already run. Not sure why that didn't fix it,
but it didn't..

NopEliminator is part of jb, not jop, although that's probably not relevant. Are the Nop's still there when it dies? 

Ah, yes now adding Nop's works. Before it wasn't working because
I didn't realize that when you insert a Stmt at the beginning of
a body, jumps to the old first Stmt are redirected to the new one.
So you have to do it like this:

   Unit first = (Unit)units.getFirst();
   Unit newFirst = Jimple.v().newNopStmt();
   units.insertBefore(newFirst, first);
   newFirst.redirectJumpsToThisTo(first);



A less convoluted way to do this would be to use
units.getNonPatchingChain().insertBefore()


Thanks for all the help.. at least now I can workaround the problem.
However, it still leaves the unanswered question as to what is going on.

For one thing, it's not clear to me what the definition of "head" is
in the context of a directed graph. Is a head equivalent to a node with
in-degree zero? (I don't think so, but..) If so, then BlockGraph.java is
broken, because the first statement is always marked as a head.



This has come up before. I don't think the definition is clear to
anybody. It's not defined in DirectedGraph what a "head"/"tail" is.
In a DirectedGraph, the only definition that makes sense is nodes with
in/out-degree zero, respectively. Therefore, I believe UnitGraph and
BlockGraph should not redefine head/tail to mean entry/exit point, but
instead should define new methods for entry/exit points. This wasn't
done because nobody commented on it and it would break lots of existing
code, but IMHO it's more of a fix than a break, so I suggest it be done
anyway. I'd like to hear other opinions, however. BTW UnitGraph and
BlockGraph should get a common super-interface ControlFlowGraph with
these methods (which would be a sub-interface of DirectedGraph).


Otherwise, if a head is not required to have degree zero (seems more
likely to be the case), then it must be ArrayBoundsCheckerAnalysis.java
(at least) that has the bug, because it assumes that all heads have
in-degree zero.


I agree that this assumption is a bug in ArrayBoundsCheckerAnalysis.


At this point I'm stuck because I haven't studied the theory behind the
array check analysis enough to understand how it works.



This is Feng's code, and he's quite busy at the moment. I think once we
decide what to do about the heads/tails/entry/exit points thing above,
either he will fix it, or someone else will have to learn enough about
the analysis to fix it.


FYI, below is my patch to fix related bugs found in the process of
investigating this one. Note there is a new fix not included in the
previous patch I posted. Maintainers, please review (and commit if
acceptable).



I am grateful for the patches, but they both fail on the current SVN
version of Soot. I think this is because of John's cleanup of the
control flow graph building code (revision 1385), which may have fixed
many of the bugs these patches fix. (I think the heads/tails/entry/exit
points discussion came up in the context of John's cleanup.)

I would suggest updating to revision 1385. At the moment, I wouldn't
suggest updating to anything more recent than that unless you are
willing to chase lots of frequently-changing dependencies. A new project
is currently being developed on top of Soot, and people are making
changes to the Soot trunk which require specific versions of Soot's
various dependencies. Hopefully soon we will have an up-to-date public
web page of the various dependencies needed to build the current svn
version of Soot.

Ondrej


Thanks,
-Archie

__________________________________________________________________________
Archie Cobbs      *        CTO, Awarix        *      http://www.awarix.com

diff -ur src.orig/soot/toolkits/graph/BlockGraph.java src/soot/toolkits/graph/BlockGraph.java
--- src.orig/soot/toolkits/graph/BlockGraph.java Sat Nov 22 14:16:09 2003
+++ src/soot/toolkits/graph/BlockGraph.java Thu Jul 15 16:49:19 2004
@@ -120,7 +120,9 @@
// Get the leaders that bound exception contexts.
if(type == ZONED) { List predList = new ArrayList();
- predList.add(mUnits.getPredOf(someTrap.getBeginUnit()));
+ if(mUnits.getPredOf(someTrap.getBeginUnit()) != null) {
+ predList.add(mUnits.getPredOf(someTrap.getBeginUnit()));
+ }
leaders.put(someTrap.getBeginUnit(), predList);

predList = new ArrayList();
@@ -189,7 +191,7 @@
predecessors= new LinkedList();
predecessors.add(currentUnit);
Unit targetPred = (Unit) mUnits.getPredOf(target);
- if(targetPred.fallsThrough())
+ if(targetPred != null && targetPred.fallsThrough())
predecessors.add(targetPred);
leaders.put(target, predecessors);
@@ -238,13 +240,15 @@

if ((nextUnit != null) &&(stmt.containsArrayRef()))
{
+ List predecessors;
if (!leaders.containsKey(nextUnit))
{
- List predicessors = new LinkedList();
- predicessors.add(currentUnit);
-
- leaders.put(nextUnit, predicessors);
+ predecessors = new LinkedList();
+ leaders.put(nextUnit, predecessors);
+ } else {
+ predecessors = (List)leaders.get(nextUnit);
}
+ predecessors.add(currentUnit);
}
}
@@ -264,7 +268,7 @@
predecessors= new LinkedList();
predecessors.add(currentUnit);
Unit targetPred = (Unit) mUnits.getPredOf(target);
- if(targetPred.fallsThrough())
+ if(targetPred != null && targetPred.fallsThrough())
predecessors.add(targetPred);
leaders.put(target, predecessors);