[Soot-list] My Forward Analysis crashes when there is a loop in function

[Ahmad Golzar]

Hi Eric,
Sorry for my imprecise language. By crash I mean the framework continues
calling the flowThrough method for the set of statements of the loop
indefinitely. Just going round and round with those statements.
Here is a sample code I'm running the analysis on:
for(int i = 0; i < a; i++)
{
   sum += b;
}
So in this case I have 3 statements. An "if" statement and two assignment
statements. The framework just continues sending them to flowThrough in
turn.
Thank you for the default implementation. I didn't know such class exists.
First I will try to fix my code because I have already built other things on
top of it. I create a Data Dependency Graph from the results of the Reaching
Definitions analysis. Just don't tell me there is a default Data Dependency
Graph generator in soot :)
Thank you again,
Ahmad

public class ReachingDefinitionsAnalysis extends ForwardFlowAnalysis
{
   private FlowSet emptySet;
   
   public ReachingDefinitionsAnalysis(DirectedGraph<Unit> g) {
      super(g);                
      emptySet = new ArraySparseSet();
      doAnalysis();
   }
   
   @Override
   protected void merge(Object in1, Object in2, Object out) {
      FlowSet inSet1 = (FlowSet)in1,
            inSet2 = (FlowSet)in2,
            outSet = (FlowSet)out;
      inSet1.union(inSet2, outSet);
   }

   @Override
   protected void copy(Object source, Object dest) {
      FlowSet srcSet = (FlowSet)source,
            destSet = (FlowSet)dest;
      srcSet.copy(destSet);
   }
   
   @Override
   protected Object newInitialFlow() {
      return emptySet.clone();
   }

   @Override
   protected Object entryInitialFlow() {
      return emptySet.clone();
   }
   
   @Override
   protected void flowThrough(Object in, Object node, Object out) {
      FlowSet inSet = (FlowSet)in,
            outSet = (FlowSet)out;
      Unit u = (Unit)node;
      kill(inSet, u, outSet);
      gen(outSet, u);
   }
   
   private void kill(FlowSet inSet, Unit u, FlowSet outSet) {
      FlowSet kills = (FlowSet)emptySet.clone();
      Iterator<ValueBox> defIt = u.getDefBoxes().iterator();
      while (defIt.hasNext()) {
         ValueBox defBox = defIt.next();

         if (defBox.getValue() instanceof Local) {
            Iterator<DependencyItem> inSetIt = inSet.iterator();
            while (inSetIt.hasNext()) {
               DependencyItem e = inSetIt.next();
               Local local = e.getLocal();
               if (local.equivTo(defBox.getValue()))
                  kills.add(e);
            }
         }
      }
      inSet.difference(kills, outSet);
   }
   
   private void gen(FlowSet outSet, Unit u) {
      Iterator<ValueBox> useIt = u.getDefBoxes().iterator();
      
      while (useIt.hasNext()) {
         ValueBox useBox = useIt.next();
         if(useBox.getValue() instanceof Local)
            outSet.add(new DependencyItem(u, (Local)useBox.getValue()));
      }
   }              
}

public class DependencyItem
{
   private Local local;
   private Unit unit;
   DependencyItem(Unit u, Local l)
   {
      this.unit = u;
      this.local = l;
   }
   
   public Local getLocal(){
      return this.local;
   }
   
   public Unit getUnit()
   {
      return this.unit;
   }
}
-----Original Message-----
From: eric.bodden at googlemail.com [mailto:eric.bodden at googlemail.com] On
Behalf Of Eric Bodden
Sent: Thursday, July 31, 2008 3:18 AM
To: Ahmad Golzar
Cc: soot-list at sable.mcgill.ca
Subject: Re: [Soot-list] My Forward Analysis crashes when there is a loop in
function

Hi Ahmad,

What do you mean by "crash"? A stack trace usually helps to identify
the problem.

Also you may prefer the default implementation in Soot that is known
to work quite well:
http://www.sable.mcgill.ca/soot/doc/soot/toolkits/scalar/SmartLocalDefs.html

Eric

2008/7/30 Ahmad Golzar <golzara at cs.man.ac.uk>:
> Hi,
>
> I have implemented "Reaching Definitions" analysis using the data-flow
> analysis framework in Soot. It works fine with functions that do not have
> any loops in them, but crashes with any function that contains a loop.
Here
> is the code of the class. Have I done anything wrong?
>
>
>
>
>
>
> Thanks,
>
> Ahmad
>
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
>



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