[Soot-list] PointsToSet and equals/hashcode

Tue Aug 15 22:53:21 EDT 2006

Ok, this is handled now in revision 2468. I implemented the appropriate functionality in soot.jimple.spark.sets.PointsToSetInternal for Spark and soot.jimple.paddle.PointsToSetReadOnly for Paddle. Both are superclasses of all PointsToSet implementations we provide, except soot.jimple.toolkits.pointer.MemoryEfficientRasUnion, which I hence changed, too.

After doing so paddle indeed performed much slower, due to the first stack trace we see below. I guess this is a very hot method in paddle and now equals/hashCode had become much more expensive. Hence, I exchanged the HashSet being used there for the new soot.util.IdentityHashSet. This gives us back the old performance.

Eric

> -----Original Message-----
> From: soot-list-bounces at sable.mcgill.ca [mailto:soot-list-
> bounces at sable.mcgill.ca] On Behalf Of Eric Bodden
> Sent: Tuesday, August 15, 2006 3:07 PM
> To: Ondrej Lhotak
> Cc: soot-list at sable.mcgill.ca
> Subject: RE: [Soot-list] PointsToSet and equals/hashcode
> 
> Hmmm... it just came to my mind that was not 100% appropriate since it
> did not take calls to equals(..) into account which come from the JDK.
> So I wrote another aspect monitoring whenever we put PointsToSet into a
> Map or Collection and that gave the following two traces:
> 
> class soot.jimple.paddle.DoublePointsToSet
> 
> used at:
> 	at
> soot.jimple.paddle.PropWorklist.fieldUpdate(PropWorklist.java:128)
> 	at
> soot.jimple.paddle.AbsPropagator$1.update(AbsPropagator.java:56)
> 	at
> soot.jimple.paddle.DependencyManager.update(DependencyManager.java:76)
> 	at soot.jimple.paddle.OFCGScene.solve(OFCGScene.java:168)
> 	at soot.jimple.paddle.OFCGConfig.solve(OFCGConfig.java:35)
> 	at soot.jimple.paddle.PaddleScene.solve(PaddleScene.java:1386)
> 	at
> soot.jimple.paddle.PaddleTransformer.solve(PaddleTransformer.java:99)
> 	at
> soot.jimple.paddle.PaddleTransformer.internalTransform(PaddleTransforme
> r.java:46)
> 	at soot.SceneTransformer.transform(SceneTransformer.java:39)
> 	at
> soot.jimple.paddle.PaddleHook.internalTransform(PaddleHook.java:43)
> 	at soot.SceneTransformer.transform(SceneTransformer.java:39)
> 	at soot.Transform.apply(Transform.java:89)
> 	at soot.RadioScenePack.internalApply(RadioScenePack.java:60)
> 	at
> soot.jimple.toolkits.callgraph.CallGraphPack.internalApply(CallGraphPac
> k.java:40)
> 	at soot.Pack.apply(Pack.java:110)
> 	at
> abc.tm.weaving.weaver.tmanalysis.TracematchAnalysis.buildAbstractedCall
> Graph(TracematchAnalysis.java:259)
> 	at
> abc.tm.weaving.weaver.tmanalysis.TracematchAnalysis.analyze(TracematchA
> nalysis.java:146)
> 	at
> abc.weaving.weaver.ReweavingPass$Worker.run(ReweavingPass.java:148)
> 	at java.lang.Thread.run(Thread.java:595)
> 
> class soot.jimple.paddle.DoublePointsToSet
> 
> used at:
> 	at
> soot.jimple.toolkits.pointer.MemoryEfficientRasUnion.addAll(MemoryEffic
> ientRasUnion.java:56)
> 	at
> abc.tm.weaving.weaver.tmanalysis.VariableSMEdgeFactory$SMVariableEdge.i
> mportVariableMapping(VariableSMEdgeFactory.java:139)
> 	at
> abc.tm.weaving.weaver.tmanalysis.UGStateMachine.addVariableMappings(UGS
> tateMachine.java:310)
> 	at
> abc.tm.weaving.weaver.tmanalysis.UGStateMachine.newTransition(UGStateMa
> chine.java:289)
> 	at
> abc.tm.weaving.weaver.tmanalysis.UGStateMachine.addStatesFor(UGStateMac
> hine.java:240)
> 	at
> abc.tm.weaving.weaver.tmanalysis.UGStateMachine.addStatesFor(UGStateMac
> hine.java:242)
> 	at
> abc.tm.weaving.weaver.tmanalysis.UGStateMachine.addStatesFor(UGStateMac
> hine.java:242)
> 	at
> abc.tm.weaving.weaver.tmanalysis.UGStateMachine.addStatesFor(UGStateMac
> hine.java:242)
> 	at
> abc.tm.weaving.weaver.tmanalysis.UGStateMachine.<init>(UGStateMachine.j
> ava:101)
> 	at
> abc.tm.weaving.weaver.tmanalysis.TracematchAnalysis.buildUnitGraphState
> Machine(TracematchAnalysis.java:316)
> 	at
> abc.tm.weaving.weaver.tmanalysis.TracematchAnalysis.buildUnitGraphState
> Machines(TracematchAnalysis.java:280)
> 	at
> abc.tm.weaving.weaver.tmanalysis.TracematchAnalysis.analyze(TracematchA
> nalysis.java:150)
> 	at
> abc.weaving.weaver.ReweavingPass$Worker.run(ReweavingPass.java:148)
> 	at java.lang.Thread.run(Thread.java:595)
> 
> Regarding the latter, I would have to modify this class anyway when I
> proceed. Regarding the former, Ondrej could you please give me an
> indication whether implementing equals/hashcode for the
> DoublePointsToSet at this point could have any performance negative
> implications or could otherwise break assumptions you make?
> 
> Thanks a lot,
> 
> Eric
> 
> 
> > -----Original Message-----
> > From: soot-list-bounces at sable.mcgill.ca [mailto:soot-list-
> > bounces at sable.mcgill.ca] On Behalf Of Eric Bodden
> > Sent: Tuesday, August 15, 2006 2:48 PM
> > To: soot-list at sable.mcgill.ca
> > Subject: RE: [Soot-list] PointsToSet and equals/hashcode
> >
> > Ok, since nobody answered so far, I investigated a little myself.
> Using
> > AspectJ (thanks, Laurie, for the idea) I was able to determine that
> > apparently "equals" is never called on any implementation of
> > PointsToSet within Paddle or Soot.
> >
> > Hence I conclude that it cannot hurt if I implement those methods,
> > which I will go ahead with now.
> >
> > Cheers,
> > Eric
> >
> >
> > > -----Original Message-----
> > > From: soot-list-bounces at sable.mcgill.ca [mailto:soot-list-
> > > bounces at sable.mcgill.ca] On Behalf Of Eric Bodden
> > > Sent: Sunday, August 13, 2006 8:20 PM
> > > To: soot-list at sable.mcgill.ca
> > > Subject: [Soot-list] PointsToSet and equals/hashcode
> > >
> > > Hi all.
> > >
> > > I am implementing some flow analysis that uses points-to sets as
> > > analysis information. As usual, the fixed point iteration stops
> when
> > > the analysis information does not change any more, i.e. when the
> new
> > > one is EQUAL to the old one. EQUAL here means equal based on
> whatever
> > > the equals(Object) method says.
> > >
> > > Unfortunately the available implementations for PointsToSet in Soot
> > do
> > > not implements equals nor hashcode, which causes my iteration to go
> > on
> > > forever. My question is now how to best overcome this issue.
> > >
> > > Is there any reason for why those methods are not implemented? (It
> > > seems that in fact there *can* be multiple instances of one and the
> > > same "equal" points-to set so reference-equality is actually not
> very
> > > satisfactory here in my eyes.)
> > >
> > > Should I just go ahead and implement those methods for
> > > PointsToSetInternal etc.? If so, are there any particular hidden
> > issues
> > > I should take in account?
> > >
> > > Is there any other way you could think of how to fix my analysis
> > > without implementing those methods?
> > >
> > > Thanks a lot,
> > > Eric
> > >
> > > --
> > > Eric Bodden
> > > Sable Research Group, McGill University
> > > Montréal, Québec, Canada
> > >
> > > _______________________________________________
> > > Soot-list mailing list
> > > Soot-list at sable.mcgill.ca
> > > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> > _______________________________________________
> > Soot-list mailing list
> > Soot-list at sable.mcgill.ca
> > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> 
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list