[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Soot bugs when first Unit is a target
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);