1 package Analysis.Disjoint;
4 import java.util.Map.Entry;
7 import IR.FieldDescriptor;
8 import IR.Flat.FlatCall;
9 import IR.Flat.FlatMethod;
10 import IR.Flat.FlatNode;
11 import IR.Flat.TempDescriptor;
12 import IR.Flat.FlatSESEEnterNode;
14 /////////////////////////////////////////////
16 // Effects analysis computes read/write/strong
17 // update and other sorts of effects for the
18 // scope of a method or rblock. The effects
19 // are associated with the heap roots through
20 // which a reference to the effect target was
23 // The effects analysis piggy-backs
24 // on the disjoint reachability analysis,
25 // if requested, to support OoOJava and
26 // potentially other analysis clients.
28 /////////////////////////////////////////////
30 public class EffectsAnalysis {
32 // the effects analysis should combine taints
33 // that match except for predicates--preds just
34 // support interprocedural analysis
35 private Hashtable<Taint, Set<Effect>> taint2effects;
37 // redundant views of the effect set for
38 // efficient retrieval
39 private Hashtable<FlatSESEEnterNode, Hashtable<Taint, Set<Effect>> > sese2te;
40 private Hashtable<FlatNode, Hashtable<Taint, Set<Effect>> > stallSite2te;
43 public EffectsAnalysis() {
44 taint2effects = new Hashtable<Taint, Set<Effect>>();
46 sese2te = new Hashtable<FlatSESEEnterNode, Hashtable<Taint, Set<Effect>> >();
47 stallSite2te = new Hashtable<FlatNode, Hashtable<Taint, Set<Effect>> >();
51 public Set<Effect> getEffects(Taint t) {
52 Taint tNoPreds = Canonical.changePredsTo( t,
55 return taint2effects.get(tNoPreds);
58 public Iterator iteratorTaintEffectPairs() {
59 return taint2effects.entrySet().iterator();
63 public Hashtable<Taint, Set<Effect>> getSESEEffects(FlatSESEEnterNode sese){
65 Hashtable<Taint, Set<Effect>> taint2Effects = new Hashtable<Taint, Set<Effect>>();
66 Iterator iter=iteratorTaintEffectPairs();
67 while (iter.hasNext()) {
68 Entry entry = (Entry) iter.next();
69 Taint taint = (Taint) entry.getKey();
70 Set<Effect> effects = (Set<Effect>) entry.getValue();
71 if (taint.getSESE().equals(sese)) {
72 Iterator<Effect> eIter = effects.iterator();
73 while (eIter.hasNext()) {
74 Effect effect = eIter.next();
75 if (taint.getSESE().equals(sese)) {
76 Set<Effect> effectSet = taint2Effects.get(taint);
77 if (effectSet == null) {
78 effectSet = new HashSet<Effect>();
80 effectSet.add(effect);
81 taint2Effects.put(taint, effectSet);
92 public Hashtable<Taint, Set<Effect>> getStallSiteEffects(FlatNode fn, TempDescriptor td){
94 Hashtable<Taint, Set<Effect>> taint2Effects = new Hashtable<Taint, Set<Effect>>();
95 Iterator iter=iteratorTaintEffectPairs();
96 while(iter.hasNext()){
97 Entry entry=(Entry)iter.next();
98 Taint taint=(Taint)entry.getKey();
99 Set<Effect> effects=(Set<Effect>)entry.getValue();
100 if(taint.getStallSite().equals(fn)){
101 Iterator<Effect> eIter=effects.iterator();
102 while (eIter.hasNext()) {
103 Effect effect = eIter.next();
104 if( taint.getStallSite().equals(fn) && taint.getVar().equals(td) ){
105 Set<Effect> effectSet=taint2Effects.get(taint);
107 effectSet=new HashSet<Effect>();
109 effectSet.add(effect);
110 taint2Effects.put(taint, effectSet);
115 return taint2Effects;
119 protected void add(Taint t, Effect e) {
120 if( t.getSESE() != null &&
121 t.getSESE().getIsCallerSESEplaceholder() ) {
125 Taint tNoPreds = Canonical.changePredsTo( t,
126 ReachGraph.predsEmpty
129 // add to the global bag
130 Set<Effect> effectSet = taint2effects.get(tNoPreds);
131 if (effectSet == null) {
132 effectSet = new HashSet<Effect>();
135 taint2effects.put(tNoPreds, effectSet);
137 // add to the alternate retrieval bags
138 if( t.getSESE() != null ) {
139 FlatSESEEnterNode sese = t.getSESE();
141 Hashtable<Taint, Set<Effect>> te = sese2te.get( sese );
143 te = new Hashtable<Taint, Set<Effect>>();
146 Set<Effect> effects = te.get(tNoPreds);
147 if (effects == null) {
148 effects = new HashSet<Effect>();
151 te.put(tNoPreds, effects);
153 sese2te.put(sese, te);
156 assert t.getStallSite() != null;
157 FlatNode stallSite = t.getStallSite();
159 Hashtable<Taint, Set<Effect>> te = stallSite2te.get( stallSite );
161 te = new Hashtable<Taint, Set<Effect>>();
164 Set<Effect> effects = te.get(tNoPreds);
165 if (effects == null) {
166 effects = new HashSet<Effect>();
169 te.put(tNoPreds, effects);
171 stallSite2te.put(stallSite, te);
176 public Hashtable<Taint, Set<Effect>> get( FlatSESEEnterNode sese ) {
177 return sese2te.get(sese);
180 public Hashtable<Taint, Set<Effect>> get( FlatNode stallSite ) {
181 return stallSite2te.get(stallSite);
186 public void analyzeFlatFieldNode(ReachGraph rg, TempDescriptor rhs, FieldDescriptor fld) {
188 VariableNode vn = rg.td2vn.get(rhs);
193 for (Iterator<RefEdge> iterator = vn.iteratorToReferencees(); iterator.hasNext();) {
194 RefEdge edge = iterator.next();
195 TaintSet taintSet = edge.getTaints();
196 AllocSite affectedAlloc = edge.getDst().getAllocSite();
197 Effect effect = new Effect(affectedAlloc, Effect.read, fld);
199 for (Iterator<Taint> taintSetIter = taintSet.iterator(); taintSetIter.hasNext();) {
200 Taint taint = taintSetIter.next();
206 public void analyzeFlatSetFieldNode(ReachGraph rg, TempDescriptor lhs, FieldDescriptor fld, boolean strongUpdate) {
208 VariableNode vn = rg.td2vn.get(lhs);
213 for (Iterator<RefEdge> iterator = vn.iteratorToReferencees(); iterator.hasNext();) {
214 RefEdge edge = iterator.next();
215 TaintSet taintSet = edge.getTaints();
216 AllocSite affectedAlloc = edge.getDst().getAllocSite();
217 Effect effect = new Effect(affectedAlloc, Effect.write, fld);
218 Effect effectSU = null;
221 effectSU = new Effect(affectedAlloc, Effect.strongupdate, fld);
224 for (Iterator<Taint> taintSetIter = taintSet.iterator(); taintSetIter.hasNext();) {
225 Taint taint = taintSetIter.next();
226 add( taint, effect );
229 add( taint, effectSU );
236 public String toString() {
237 return taint2effects.toString();
240 public void writeEffects( String outfile ) {
242 BufferedWriter bw = new BufferedWriter(new FileWriter(outfile));
244 bw.write( "Effects\n---------------\n\n" );
246 Iterator meItr = taint2effects.entrySet().iterator();
247 while( meItr.hasNext() ) {
248 Map.Entry me = (Map.Entry) meItr.next();
249 Taint taint = (Taint) me.getKey();
250 Set<Effect> effects = (Set<Effect>) me.getValue();
252 Iterator<Effect> eItr = effects.iterator();
253 while( eItr.hasNext() ) {
254 Effect e = eItr.next();
256 bw.write( taint+"-->"+e+"\n" );
261 } catch( IOException e ) {}
265 * public MethodEffects getMethodEffectsByMethodContext(MethodContext mc){
266 * return mapMethodContextToMethodEffects.get(mc); }
268 * public void createNewMapping(MethodContext mcNew) { if(!methodeffects)
269 * return; if (!mapMethodContextToMethodEffects.containsKey(mcNew)) {
270 * MethodEffects meNew = new MethodEffects();
271 * mapMethodContextToMethodEffects.put(mcNew, meNew); } }
275 * public void analyzeFlatCall(OwnershipGraph calleeOG, MethodContext
276 * calleeMC, MethodContext callerMC, FlatCall fc) { if(!methodeffects) return;
277 * MethodEffects me = mapMethodContextToMethodEffects.get(callerMC);
278 * MethodEffects meFlatCall = mapMethodContextToMethodEffects .get(calleeMC);
279 * me.analyzeFlatCall(calleeOG, fc, callerMC, meFlatCall);
280 * mapMethodContextToMethodEffects.put(callerMC, me); }
284 * public void analyzeFlatFieldNode(MethodContext mc, OwnershipGraph og,
285 * TempDescriptor srcDesc, FieldDescriptor fieldDesc) { if(!methodeffects)
286 * return; MethodEffects me = mapMethodContextToMethodEffects.get(mc);
287 * me.analyzeFlatFieldNode(og, srcDesc, fieldDesc);
288 * mapMethodContextToMethodEffects.put(mc, me); }
290 * public void analyzeFlatSetFieldNode(MethodContext mc, OwnershipGraph og,
291 * TempDescriptor dstDesc, FieldDescriptor fieldDesc) { if(!methodeffects)
292 * return; MethodEffects me = mapMethodContextToMethodEffects.get(mc);
293 * me.analyzeFlatSetFieldNode(og, dstDesc, fieldDesc);
294 * mapMethodContextToMethodEffects.put(mc, me); }
296 * public void analyzeFlatSetElementNode(MethodContext mc, OwnershipGraph og,
297 * TempDescriptor dstDesc, FieldDescriptor fieldDesc) { if(!methodeffects)
298 * return; MethodEffects me = mapMethodContextToMethodEffects.get(mc);
299 * me.analyzeFlatSetElementNode(og, dstDesc, fieldDesc);
300 * mapMethodContextToMethodEffects.put(mc, me); }
302 * public void analyzeFlatElementNode(MethodContext mc, OwnershipGraph og,
303 * TempDescriptor dstDesc, FieldDescriptor fieldDesc) { if(!methodeffects)
304 * return; MethodEffects me = mapMethodContextToMethodEffects.get(mc);
305 * me.analyzeFlatElementNode(og, dstDesc, fieldDesc);
306 * mapMethodContextToMethodEffects.put(mc, me); }
309 * public void writeMethodEffectsResult() throws IOException {
311 * try { BufferedWriter bw = new BufferedWriter(new FileWriter(
312 * "MethodEffects_report.txt"));
314 * Set<MethodContext> mcSet = mapMethodContextToMethodEffects.keySet();
315 * Iterator<MethodContext> mcIter = mcSet.iterator(); while (mcIter.hasNext())
316 * { MethodContext mc = mcIter.next(); MethodDescriptor md =
317 * (MethodDescriptor) mc.getDescriptor();
319 * int startIdx = 0; if (!md.isStatic()) { startIdx = 1; }
321 * MethodEffects me = mapMethodContextToMethodEffects.get(mc); EffectsSet
322 * effectsSet = me.getEffects();
324 * bw.write("Method " + mc + " :\n"); for (int i = startIdx; i <
325 * md.numParameters() + startIdx; i++) {
327 * String paramName = md.getParamName(i - startIdx);
329 * Set<EffectsKey> effectSet = effectsSet.getReadingSet(i); String keyStr =
330 * "{"; if (effectSet != null) { Iterator<EffectsKey> effectIter =
331 * effectSet.iterator(); while (effectIter.hasNext()) { EffectsKey key =
332 * effectIter.next(); keyStr += " " + key; } } keyStr += " }";
333 * bw.write(" Paramter " + paramName + " ReadingSet=" + keyStr + "\n");
335 * effectSet = effectsSet.getWritingSet(new Integer(i)); keyStr = "{"; if
336 * (effectSet != null) { Iterator<EffectsKey> effectIter =
337 * effectSet.iterator(); while (effectIter.hasNext()) { EffectsKey key =
338 * effectIter.next(); keyStr += " " + key; } }
340 * keyStr += " }"; bw.write(" Paramter " + paramName + " WritingngSet=" +
347 * bw.close(); } catch (IOException e) { System.err.println(e); }