From 1824b45ef65c0e3c4181915ac49ac24391b9b698 Mon Sep 17 00:00:00 2001
From: jjenista <jjenista>
Date: Tue, 29 Jun 2010 19:05:04 +0000
Subject: [PATCH] getting close to effects for new disjoint analysis
---
.../Analysis/Disjoint/DisjointAnalysis.java | 39 ++++++-----
.../Analysis/Disjoint/EffectsAnalysis.java | 63 ++++++++++++++++-
.../src/Analysis/OoOJava/OoOJavaAnalysis.java | 68 +++++++++++++------
Robust/src/Main/Main.java | 2 +-
4 files changed, 130 insertions(+), 42 deletions(-)
diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java
index 25a35349..ee933a70 100644
--- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java
+++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java
@@ -420,6 +420,11 @@ public class DisjointAnalysis {
protected Hashtable< Descriptor, Set<Descriptor> >
mapDescriptorToSetDependents;
+ // if the analysis client wants to flag allocation sites
+ // programmatically, it should provide a set of FlatNew
+ // statements--this may be null if unneeded
+ protected Set<FlatNew> sitesToFlag;
+
// maps each flat new to one analysis abstraction
// allocate site object, these exist outside reach graphs
protected Hashtable<FlatNew, AllocSite>
@@ -559,10 +564,11 @@ public class DisjointAnalysis {
CallGraph cg,
Liveness l,
ArrayReferencees ar,
+ Set<FlatNew> sitesToFlag,
RBlockRelationAnalysis rra,
RBlockStatusAnalysis rsa
) {
- init( s, tu, cg, l, ar, rra, rsa );
+ init( s, tu, cg, l, ar, sitesToFlag, rra, rsa );
}
protected void init( State state,
@@ -570,19 +576,21 @@ public class DisjointAnalysis {
CallGraph callGraph,
Liveness liveness,
ArrayReferencees arrayReferencees,
+ Set<FlatNew> sitesToFlag,
RBlockRelationAnalysis rra,
RBlockStatusAnalysis rsa
) {
analysisComplete = false;
- this.state = state;
- this.typeUtil = typeUtil;
- this.callGraph = callGraph;
- this.liveness = liveness;
- this.arrayReferencees = arrayReferencees;
- this.rblockRel = rra;
- this.rblockStatus = rsa;
+ this.state = state;
+ this.typeUtil = typeUtil;
+ this.callGraph = callGraph;
+ this.liveness = liveness;
+ this.arrayReferencees = arrayReferencees;
+ this.sitesToFlag = sitesToFlag;
+ this.rblockRel = rra;
+ this.rblockStatus = rsa;
if( rblockRel != null ) {
doEffectsAnalysis = true;
@@ -934,18 +942,10 @@ public class DisjointAnalysis {
}
- //System.out.println( "At "+fn );
- //System.out.println( " inacc-in: "+rg.getInaccessibleVars() );
-
-
// modify rg with appropriate transfer function
rg = analyzeFlatNode( d, fm, fn, setReturns, rg );
- //System.out.println( " inacc-out: "+rg.getInaccessibleVars() );
- //System.out.println( "\n" );
-
-
if( takeDebugSnapshots &&
d.getSymbol().equals( descSymbolDebug )
) {
@@ -1673,11 +1673,16 @@ public class DisjointAnalysis {
// return just the allocation site associated with one FlatNew node
protected AllocSite getAllocSiteFromFlatNewPRIVATE( FlatNew fnew ) {
+ boolean flagProgrammatically = false;
+ if( sitesToFlag != null && sitesToFlag.contains( fnew ) ) {
+ flagProgrammatically = true;
+ }
+
if( !mapFlatNewToAllocSite.containsKey( fnew ) ) {
AllocSite as = AllocSite.factory( allocationDepth,
fnew,
fnew.getDisjointId(),
- false
+ flagProgrammatically
);
// the newest nodes are single objects
diff --git a/Robust/src/Analysis/Disjoint/EffectsAnalysis.java b/Robust/src/Analysis/Disjoint/EffectsAnalysis.java
index 52244a53..1ed85fa9 100644
--- a/Robust/src/Analysis/Disjoint/EffectsAnalysis.java
+++ b/Robust/src/Analysis/Disjoint/EffectsAnalysis.java
@@ -34,8 +34,17 @@ public class EffectsAnalysis {
// support interprocedural analysis
private Hashtable<Taint, Set<Effect>> taint2effects;
+ // redundant views of the effect set for
+ // efficient retrieval
+ private Hashtable<FlatSESEEnterNode, Hashtable<Taint, Set<Effect>> > sese2te;
+ private Hashtable<FlatNode, Hashtable<Taint, Set<Effect>> > stallSite2te;
+
+
public EffectsAnalysis() {
taint2effects = new Hashtable<Taint, Set<Effect>>();
+
+ sese2te = new Hashtable<FlatSESEEnterNode, Hashtable<Taint, Set<Effect>> >();
+ stallSite2te = new Hashtable<FlatNode, Hashtable<Taint, Set<Effect>> >();
}
@@ -49,7 +58,8 @@ public class EffectsAnalysis {
public Iterator iteratorTaintEffectPairs() {
return taint2effects.entrySet().iterator();
}
-
+
+ /*
public Hashtable<Taint, Set<Effect>> getSESEEffects(FlatSESEEnterNode sese){
Hashtable<Taint, Set<Effect>> taint2Effects = new Hashtable<Taint, Set<Effect>>();
@@ -77,7 +87,8 @@ public class EffectsAnalysis {
return taint2Effects;
}
-
+ */
+
public Hashtable<Taint, Set<Effect>> getStallSiteEffects(FlatNode fn, TempDescriptor td){
Hashtable<Taint, Set<Effect>> taint2Effects = new Hashtable<Taint, Set<Effect>>();
@@ -115,15 +126,63 @@ public class EffectsAnalysis {
ReachGraph.predsEmpty
);
+ // add to the global bag
Set<Effect> effectSet = taint2effects.get(tNoPreds);
if (effectSet == null) {
effectSet = new HashSet<Effect>();
}
effectSet.add(e);
taint2effects.put(tNoPreds, effectSet);
+
+ // add to the alternate retrieval bags
+ if( t.getSESE() != null ) {
+ FlatSESEEnterNode sese = t.getSESE();
+
+ Hashtable<Taint, Set<Effect>> te = sese2te.get( sese );
+ if( te == null ) {
+ te = new Hashtable<Taint, Set<Effect>>();
+ }
+
+ Set<Effect> effects = te.get(tNoPreds);
+ if (effects == null) {
+ effects = new HashSet<Effect>();
+ }
+ effects.add(e);
+ te.put(tNoPreds, effects);
+
+ sese2te.put(sese, te);
+
+ } else {
+ assert t.getStallSite() != null;
+ FlatNode stallSite = t.getStallSite();
+
+ Hashtable<Taint, Set<Effect>> te = stallSite2te.get( stallSite );
+ if( te == null ) {
+ te = new Hashtable<Taint, Set<Effect>>();
+ }
+
+ Set<Effect> effects = te.get(tNoPreds);
+ if (effects == null) {
+ effects = new HashSet<Effect>();
+ }
+ effects.add(e);
+ te.put(tNoPreds, effects);
+
+ stallSite2te.put(stallSite, te);
+ }
}
+ public Hashtable<Taint, Set<Effect>> get( FlatSESEEnterNode sese ) {
+ return sese2te.get(sese);
+ }
+
+ public Hashtable<Taint, Set<Effect>> get( FlatNode stallSite ) {
+ return stallSite2te.get(stallSite);
+ }
+
+
+
public void analyzeFlatFieldNode(ReachGraph rg, TempDescriptor rhs, FieldDescriptor fld) {
VariableNode vn = rg.td2vn.get(rhs);
diff --git a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java
index 61886d1c..0c7707d3 100644
--- a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java
+++ b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java
@@ -27,6 +27,7 @@ import IR.Flat.FlatFieldNode;
import IR.Flat.FlatMethod;
import IR.Flat.FlatNode;
import IR.Flat.FlatOpNode;
+import IR.Flat.FlatNew;
import IR.Flat.FlatSESEEnterNode;
import IR.Flat.FlatSESEExitNode;
import IR.Flat.FlatSetFieldNode;
@@ -155,8 +156,16 @@ public class OoOJavaAnalysis {
// 5th pass, use disjointness with NO FLAGGED REGIONS
// to compute taints and effects
- disjointAnalysisTaints = new DisjointAnalysis(state, typeUtil, callGraph, liveness,
- arrayReferencees, rblockRel, rblockStatus);
+ disjointAnalysisTaints =
+ new DisjointAnalysis(state,
+ typeUtil,
+ callGraph,
+ liveness,
+ arrayReferencees,
+ null, // no FlatNew set to flag
+ rblockRel,
+ rblockStatus
+ );
// 6th pass, not available analysis FOR VARIABLES!
methItr = descriptorsToAnalyze.iterator();
@@ -169,14 +178,17 @@ public class OoOJavaAnalysis {
notAvailableForward(fm);
}
- /*
- // #th pass, make conflict graph
- // conflict graph is maintained by each parent sese
+ // 7th pass, make conflict graph
+ // conflict graph is maintained by each parent sese,
+ // and while making the graph identify set of FlatNew
+ // that next disjoint reach. analysis should flag
+ Set<FlatNew> sitesToFlag = new HashSet<FlatNew>();
+
methItr = descriptorsToAnalyze.iterator();
while (methItr.hasNext()) {
Descriptor d = methItr.next();
FlatMethod fm = state.getMethodFlat(d);
- makeConflictGraph(fm);
+ makeConflictGraph(fm, sitesToFlag);
}
// debug routine
@@ -194,9 +206,25 @@ public class OoOJavaAnalysis {
}
}
- // #th pass, calculate conflicts
- calculateConflicts();
+ // 8th pass, ask disjoint analysis to compute reachability
+ // for objects that may cause heap conflicts so the most
+ // efficient method to deal with conflict can be computed
+ // later
+ disjointAnalysisReach =
+ new DisjointAnalysis(state,
+ typeUtil,
+ callGraph,
+ liveness,
+ arrayReferencees,
+ sitesToFlag,
+ null, // don't do effects analysis again!
+ null // don't do effects analysis again!
+ );
+
+ // 9th pass, calculate conflicts
+ //calculateConflicts();
+ /*
// #th pass, compiling locks
synthesizeLocks();
@@ -641,7 +669,7 @@ public class OoOJavaAnalysis {
} // end switch
}
- private void makeConflictGraph(FlatMethod fm) {
+ private void makeConflictGraph(FlatMethod fm, Set<FlatNew> sitesToFlag) {
Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
flatNodesToVisit.add(fm);
@@ -658,16 +686,12 @@ public class OoOJavaAnalysis {
if (!seseStack.isEmpty()) {
- // Add Stall Node of current program statement
- // disjointAnalysisTaints.getEffectsAnalysis().getEffects(t);
-
ConflictGraph conflictGraph = sese2conflictGraph.get(seseStack.peek());
if (conflictGraph == null) {
conflictGraph = new ConflictGraph();
}
- conflictGraph_nodeAction(fn, seseStack.peek());
-
+ conflictGraph_nodeAction(fn, seseStack.peek(), sitesToFlag);
}
// schedule forward nodes for analysis
@@ -683,7 +707,7 @@ public class OoOJavaAnalysis {
}
- private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE) {
+ private void conflictGraph_nodeAction(FlatNode fn, FlatSESEEnterNode currentSESE, Set<FlatNew> sitesToFlag) {
EffectsAnalysis effectsAnalysis = disjointAnalysisTaints.getEffectsAnalysis();
ConflictGraph conflictGraph = sese2conflictGraph.get(currentSESE.getParent());
@@ -699,7 +723,7 @@ public class OoOJavaAnalysis {
if (!fsen.getIsCallerSESEplaceholder() && currentSESE.getParent() != null) {
// collects effects set of invar set and generates invar node
- Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.getSESEEffects(currentSESE);
+ Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.get(currentSESE);
conflictGraph.addLiveIn(taint2Effects);
}
}
@@ -712,8 +736,8 @@ public class OoOJavaAnalysis {
TempDescriptor rhs = ffn.getSrc();
// add stall site
- Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.getStallSiteEffects(fn, rhs);
- conflictGraph.addStallSite(taint2Effects);
+ //Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.get(fn, rhs);
+ //conflictGraph.addStallSite(taint2Effects);
}
break;
@@ -726,11 +750,11 @@ public class OoOJavaAnalysis {
TempDescriptor rhs = fsfn.getSrc();
// collects effects of stall site and generates stall site node
- Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.getStallSiteEffects(fn, rhs);
- conflictGraph.addStallSite(taint2Effects);
+ //Hashtable<Taint, Set<Effect>> taint2Effects=effectsAnalysis.get(fn, rhs);
+ //conflictGraph.addStallSite(taint2Effects);
- taint2Effects=effectsAnalysis.getStallSiteEffects(fn, lhs);
- conflictGraph.addStallSite(taint2Effects);
+ //taint2Effects=effectsAnalysis.get(fn, lhs);
+ //conflictGraph.addStallSite(taint2Effects);
}
break;
diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java
index 73224acb..06adf610 100644
--- a/Robust/src/Main/Main.java
+++ b/Robust/src/Main/Main.java
@@ -505,7 +505,7 @@ public class Main {
CallGraph cg = new CallGraph(state);
Liveness l = new Liveness();
ArrayReferencees ar = new ArrayReferencees(state);
- DisjointAnalysis da = new DisjointAnalysis(state, tu, cg, l, ar, null, null);
+ DisjointAnalysis da = new DisjointAnalysis(state, tu, cg, l, ar, null, null, null);
}
if (state.OOOJAVA) {
--
2.34.1