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

[Eric Bodden]

Fromwhat I can see the problem seems to be that your DependencyItem
class does not implement equals(..) nor hashCode(). Therefore your
flow sets can nevr be equal to each other and thus you never reach the
fixed point.

Eric

2008/7/31 Ahmad Golzar <golzara at cs.man.ac.uk>:
> 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
>
>



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