From 09503b04db1f5c1c06b4072c98c4fa195ed83d75 Mon Sep 17 00:00:00 2001 From: yeom Date: Wed, 30 Mar 2011 23:12:40 +0000 Subject: [PATCH] bug fixes on OoOJava, now it works fine with all of benchmarks(but, Kmeans has lower speedup 10.6x than 13.8x. still working on...) -changes on the potential stall site analysis: propagating the status of callee's return node to the caller region and when current node has a status change, making following nodes updated to get a new potential stall site status. -changes on liveness analysis of OoOJava: new analysis only covers the task region, not whole region of the flat method. -changes on disjoint analysis: rather than using reachgraph's inAccessibleSet, using the result of brian's new accessible analysis. --- .../Analysis/Disjoint/DisjointAnalysis.java | 41 ++++-- .../src/Analysis/OoOJava/OoOJavaAnalysis.java | 103 ++++++++------ .../OoOJava/RBlockRelationAnalysis.java | 130 +++++++++++------- 3 files changed, 170 insertions(+), 104 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 28b1d31f..34d41521 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -3,6 +3,7 @@ package Analysis.Disjoint; import Analysis.CallGraph.*; import Analysis.Liveness; import Analysis.ArrayReferencees; +import Analysis.OoOJava.Accessible; import Analysis.OoOJava.RBlockRelationAnalysis; import IR.*; import IR.Flat.*; @@ -538,7 +539,8 @@ public class DisjointAnalysis implements HeapAnalysis { new Hashtable(); private Hashtable fc2enclosing; - + + Accessible accessible; // allocate various structures that are not local // to a single class method--should be done once @@ -677,8 +679,13 @@ public class DisjointAnalysis implements HeapAnalysis { if( rblockRel != null ) { doEffectsAnalysis = true; effectsAnalysis = new EffectsAnalysis(); + + //note: instead of reachgraph's isAccessible, using the result of accessible analysis + //since accessible gives us more accurate results + accessible=new Accessible(state, callGraph, rra, liveness); + accessible.doAnalysis(); } - + this.allocationDepth = state.DISJOINTALLOCDEPTH; this.releaseMode = state.DISJOINTRELEASEMODE; this.determinismDesired = state.DISJOINTDETERMINISM; @@ -1205,7 +1212,8 @@ public class DisjointAnalysis implements HeapAnalysis { if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { if(rblockRel.isPotentialStallSite(fn)){ // x gets status of y - if(!rg.isAccessible(rhs)){ +// if(!rg.isAccessible(rhs)){ + if(!accessible.isAccessible(fn, rhs)){ rg.makeInaccessible(lhs); } } @@ -1228,7 +1236,8 @@ public class DisjointAnalysis implements HeapAnalysis { if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { if(rblockRel.isPotentialStallSite(fn)){ // x gets status of y - if(!rg.isAccessible(rhs)){ +// if(!rg.isAccessible(rhs)){ + if(!accessible.isAccessible(fn,rhs)){ rg.makeInaccessible(lhs); } } @@ -1252,7 +1261,8 @@ public class DisjointAnalysis implements HeapAnalysis { if(rblockRel.isPotentialStallSite(fn)){ // x=y.f, stall y if not accessible // contributes read effects on stall site of y - if(!rg.isAccessible(rhs)) { +// if(!rg.isAccessible(rhs)) { + if(!accessible.isAccessible(fn,rhs)) { rg.taintStallSite(fn, rhs); } @@ -1290,11 +1300,13 @@ public class DisjointAnalysis implements HeapAnalysis { if(rblockRel.isPotentialStallSite(fn)){ // x.y=f , stall x and y if they are not accessible // also contribute write effects on stall site of x - if(!rg.isAccessible(lhs)) { +// if(!rg.isAccessible(lhs)) { + if(!accessible.isAccessible(fn,lhs)) { rg.taintStallSite(fn, lhs); } - if(!rg.isAccessible(rhs)) { +// if(!rg.isAccessible(rhs)) { + if(!accessible.isAccessible(fn,rhs)) { rg.taintStallSite(fn, rhs); } @@ -1334,7 +1346,8 @@ public class DisjointAnalysis implements HeapAnalysis { // x=y.f, stall y if not accessible // contributes read effects on stall site of y // after this, x and y are accessbile. - if(!rg.isAccessible(rhs)) { +// if(!rg.isAccessible(rhs)) { + if(!accessible.isAccessible(fn,rhs)) { rg.taintStallSite(fn, rhs); } @@ -1373,11 +1386,13 @@ public class DisjointAnalysis implements HeapAnalysis { if(rblockRel.isPotentialStallSite(fn)){ // x.y=f , stall x and y if they are not accessible // also contribute write effects on stall site of x - if(!rg.isAccessible(lhs)) { +// if(!rg.isAccessible(lhs)) { + if(!accessible.isAccessible(fn,lhs)) { rg.taintStallSite(fn, lhs); } - if(!rg.isAccessible(rhs)) { +// if(!rg.isAccessible(rhs)) { + if(!accessible.isAccessible(fn,rhs)) { rg.taintStallSite(fn, rhs); } @@ -1621,7 +1636,8 @@ public class DisjointAnalysis implements HeapAnalysis { ); if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - if( !rgPossibleCallee.isAccessible( ReachGraph.tdReturn ) ) { +// if( !rgPossibleCallee.isAccessible( ReachGraph.tdReturn ) ) { + if( !accessible.isAccessible(fn, ReachGraph.tdReturn ) ) { rgPossibleCaller.makeInaccessible( fc.getReturnTemp() ); } } @@ -1664,7 +1680,8 @@ public class DisjointAnalysis implements HeapAnalysis { // before transfer, do effects analysis support if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - if(!rg.isAccessible(rhs)){ +// if(!rg.isAccessible(rhs)){ + if(!accessible.isAccessible(fn,rhs)){ rg.makeInaccessible(ReachGraph.tdReturn); } } diff --git a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java index 5cc9a97a..f0df0c61 100644 --- a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java +++ b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java @@ -147,16 +147,14 @@ public class OoOJavaAnalysis { State.logEvent("OoOJavaAnalysis 1st pass completed"); + // 2nd pass, liveness, in-set out-set (no virtual reads yet!) - methItr = descriptorsToAnalyze.iterator(); - while (methItr.hasNext()) { - Descriptor d = methItr.next(); - FlatMethod fm = state.getMethodFlat(d); - - // note we can't use the general liveness analysis already in - // the compiler because this analysis is task-aware - livenessAnalysisBackward(fm); + Iterator seseItr = rblockRel.getLocalRootSESEs().iterator(); + while (seseItr.hasNext()) { + FlatSESEEnterNode sese = seseItr.next(); + livenessAnalysisBackward(sese,liveness); } + State.logEvent("OoOJavaAnalysis 2nd pass completed"); @@ -171,14 +169,15 @@ public class OoOJavaAnalysis { variableAnalysisForward(fm); } State.logEvent("OoOJavaAnalysis 3rd pass completed"); + // 4th pass, compute liveness contribution from // virtual reads discovered in variable pass - methItr = descriptorsToAnalyze.iterator(); - while (methItr.hasNext()) { - Descriptor d = methItr.next(); - FlatMethod fm = state.getMethodFlat(d); - livenessAnalysisBackward(fm); + seseItr = rblockRel.getLocalRootSESEs().iterator(); + while (seseItr.hasNext()) { + FlatSESEEnterNode sese = seseItr.next(); + livenessAnalysisBackward(sese,liveness); } + State.logEvent("OoOJavaAnalysis 4th pass completed"); // 5th pass, use disjointness with NO FLAGGED REGIONS @@ -251,7 +250,7 @@ public class OoOJavaAnalysis { while (methItr.hasNext()) { Descriptor d = methItr.next(); FlatMethod fm = state.getMethodFlat(d); - codePlansForward(fm); + codePlansForward(fm,liveness); } State.logEvent("OoOJavaAnalysis 12th pass completed"); @@ -334,13 +333,14 @@ public class OoOJavaAnalysis { } - private void livenessAnalysisBackward(FlatMethod fm) { + private void livenessAnalysisBackward(FlatSESEEnterNode fsen,Liveness liveness) { // flow backward across nodes to compute liveness, and // take special care with sese enter/exit nodes that // alter this from normal liveness analysis Set flatNodesToVisit = new HashSet(); - flatNodesToVisit.add( fm.getFlatExit() ); +// flatNodesToVisit.add( fm.getFlatExit() ); + flatNodesToVisit.add(fsen.getFlatExit()); while( !flatNodesToVisit.isEmpty() ) { FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next(); @@ -358,22 +358,24 @@ public class OoOJavaAnalysis { } } - Set curr = liveness_nodeActions( fn, livein ); + Set curr = liveness_nodeActions( fn, livein, liveness ); // if a new result, schedule backward nodes for analysis if( !curr.equals( prev ) ) { - livenessGlobalView.put( fn, curr ); - for( int i = 0; i < fn.numPrev(); i++ ) { - FlatNode nn = fn.getPrev( i ); - flatNodesToVisit.add( nn ); - } + if(fn!=fsen){ + livenessGlobalView.put( fn, curr ); + for( int i = 0; i < fn.numPrev(); i++ ) { + FlatNode nn = fn.getPrev( i ); + flatNodesToVisit.add( nn ); + } + } } } } private Set liveness_nodeActions( FlatNode fn, - Set liveIn + Set liveIn, Liveness liveness ) { switch( fn.kind() ) { @@ -400,7 +402,9 @@ public class OoOJavaAnalysis { // be live-out at the task's exit (and therefore should // go in the task's out-var set) FlatSESEExitNode fsexn = fsen.getFlatExit(); - Set livetemps = livenessGlobalView.get( fsexn ); + //note: liveness analysis can have corresponding decisions + Set livetemps= liveness.getLiveInTemps(fsen.getfmEnclosing(), fsexn); +// Set livetemps = livenessGlobalView.get( fsexn ); if( livetemps != null && livetemps.contains( writeTemps[i] ) ) { fsen.addOutVar( writeTemps[i] ); } @@ -762,7 +766,7 @@ public class OoOJavaAnalysis { } - private void codePlansForward(FlatMethod fm) { + private void codePlansForward(FlatMethod fm, Liveness liveness) { // start from flat method top, visit every node in // method exactly once @@ -804,7 +808,7 @@ public class OoOJavaAnalysis { } codePlans_nodeActions(fm, fn, - dotSTlive, dotSTtable, dotSTnotAvailSet, + /*dotSTlive*/liveness, dotSTtable, dotSTnotAvailSet, currentSESE); for (int i = 0; i < fn.numNext(); i++) { @@ -819,7 +823,8 @@ public class OoOJavaAnalysis { private void codePlans_nodeActions(FlatMethod fm, FlatNode fn, - Set liveSetIn, +// Set liveSetIn, + Liveness liveness, VarSrcTokTable vstTableIn, Set notAvailSetIn, FlatSESEEnterNode currentSESE) { @@ -918,9 +923,10 @@ public class OoOJavaAnalysis { default: { // a node with no live set has nothing to stall for - if (liveSetIn == null) { - break; - } + // note: no reason to check here, remove this.... +// if (liveSetIn == null) { +// break; +// } TempDescriptor[] readarray = fn.readsTemps(); for (int i = 0; i < readarray.length; i++) { @@ -961,11 +967,16 @@ public class OoOJavaAnalysis { Set copySet = new HashSet(); Iterator refVarItr = vstAlsoAvail.getRefVars().iterator(); + while (refVarItr.hasNext()) { TempDescriptor refVar = refVarItr.next(); - if (liveSetIn.contains(refVar)) { - copySet.add(refVar); - } + //note: this should just use normal liveness in...only want to copy live variables... +// if (liveSetIn.contains(refVar)) { +// copySet.add(refVar); +// } + if(liveness.getLiveInTemps(fm, fn).contains(refVar)){ + copySet.add(refVar); + } } if (!copySet.isEmpty()) { @@ -1024,7 +1035,9 @@ public class OoOJavaAnalysis { for (int i = 0; i < fn.numNext(); i++) { FlatNode nn = fn.getNext(i); VarSrcTokTable nextVstTable = variableResults.get(nn); - Set nextLiveIn = livenessGlobalView.get(nn); + // note: using the result of liveness analysis regardless of task structures + // Set nextLiveIn = livenessGlobalView.get(nn); + Set nextLiveIn=liveness.getLiveInTemps(fm, nn); // the table can be null if it is one of the few IR nodes // completely outside of the root SESE scope @@ -1055,15 +1068,18 @@ public class OoOJavaAnalysis { FlatMethod fm, TempDescriptor var ) { FlatNode fnContext; - - if( fsen.getIsCallerProxySESE() ) { - // attach the dynamic variable to track to - // the flat method, so it can be declared at entry - fnContext = fm; - } else { - // otherwise the code context is a task body - fnContext = fsen; - } + + // note: dynamic variable declarations are always located in the flat method that encloses task block + // there is no need to set fnContext to fsen +// if( fsen.getIsCallerProxySESE() ) { +// // attach the dynamic variable to track to +// // the flat method, so it can be declared at entry +// fnContext = fm; +// } else { +// // otherwise the code context is a task body +// fnContext = fsen; +// } + fnContext=fm; ContextTaskNames ctn = fn2contextTaskNames.get( fnContext ); if( ctn == null ) { @@ -1072,6 +1088,7 @@ public class OoOJavaAnalysis { ctn.addDynamicVar( var ); fn2contextTaskNames.put( fnContext, ctn ); + } private void addNeededStaticName( FlatSESEEnterNode fsen, diff --git a/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java b/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java index 3f470ce0..fc9d0b0e 100644 --- a/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java +++ b/Robust/src/Analysis/OoOJava/RBlockRelationAnalysis.java @@ -5,6 +5,7 @@ import IR.TypeUtil; import IR.MethodDescriptor; import IR.TypeDescriptor; import IR.Flat.*; +import Util.Pair; import Analysis.CallGraph.CallGraph; import java.util.*; @@ -110,6 +111,10 @@ public class RBlockRelationAnalysis { // after some child task definition such that, without looking at // the flat node itself, the parent might have to stall for child protected Hashtable fn2isPotentialStallSite; + + HashMap>> methodmap= + new HashMap>>(); + //////////////////////// @@ -459,102 +464,129 @@ public class RBlockRelationAnalysis { Set visited = new HashSet(); - while( !flatNodesToVisit.isEmpty() ) { - Map.Entry me = (Map.Entry) flatNodesToVisit.entrySet().iterator().next(); - FlatNode fn = (FlatNode) me.getKey(); + while (!flatNodesToVisit.isEmpty()) { + Map.Entry me = (Map.Entry) flatNodesToVisit.entrySet().iterator().next(); + FlatNode fn = (FlatNode) me.getKey(); FlatMethod fm = (FlatMethod) me.getValue(); - flatNodesToVisit.remove( fn ); - visited.add( fn ); + flatNodesToVisit.remove(fn); + visited.add(fn); // the "is potential stall site" strategy is to propagate // "false" from the beginning of a task until you hit a // child, then from the child's exit propagate "true" for - // the parent statements after children. When you pull a node + // the parent statements after children. When you pull a node // out of the bag for traversal and it happens to be an // enter or an exit node, fix the dumb propagation that // your IR predecessor pushed on you - Boolean isPotentialStallSite = isPotentialStallSite( fn ); + Boolean isPotentialStallSite = isPotentialStallSite(fn); - if( fn == fsen.getFlatExit() ) { - // don't enqueue any futher nodes when you find your exit, + if (fn == fsen.getFlatExit()) { + // don't enqueue any further nodes when you find your exit, // NOR mark your own flat as a statement you are currently // executing, your parent(s) will mark it continue; } - if( fn instanceof FlatSESEExitNode ) { - setIsPotentialStallSite( fn, false ); - isPotentialStallSite = true; + if (fn instanceof FlatSESEExitNode) { + setIsPotentialStallSite(fn, false); + isPotentialStallSite = true; } - + // the purpose of this traversal is to find program // points where rblock 'fsen' might be executing - addPossibleExecutingRBlock( fn, fsen ); + addPossibleExecutingRBlock(fn, fsen); - if( fn instanceof FlatSESEEnterNode ) { + if (fn instanceof FlatSESEEnterNode) { // don't visit internal nodes of child, // just enqueue the exit node FlatSESEEnterNode child = (FlatSESEEnterNode) fn; - assert fsen.getChildren().contains( child ); - assert child.getParents().contains( fsen ); - flatNodesToVisit.put( child.getFlatExit(), fm ); - setIsPotentialStallSite( fn, false ); + assert fsen.getChildren().contains(child); + assert child.getParents().contains(fsen); + flatNodesToVisit.put(child.getFlatExit(), fm); + setIsPotentialStallSite(fn, false); // explicitly do this to handle the case that you - // should mark yourself as possibly executing at + // should mark yourself as possibly executing at // your own exit, because one instance can // recursively invoke another - addPossibleExecutingRBlock( child.getFlatExit(), fsen ); + addPossibleExecutingRBlock(child.getFlatExit(), fsen); continue; } - - + // if previous flat nodes have any changes,, // propagate predecessor's status of stall site potential - - if( fn instanceof FlatCall ) { + if (fn instanceof FlatCall) { + // start visiting nodes in other contexts - FlatCall fc = (FlatCall) fn; + FlatCall fc = (FlatCall) fn; MethodDescriptor mdCallee = fc.getMethod(); Set implementations = new HashSet(); - if( mdCallee.isStatic() ) { - implementations.add( mdCallee ); + if (mdCallee.isStatic()) { + implementations.add(mdCallee); } else { TypeDescriptor typeDesc = fc.getThis().getType(); - implementations.addAll( callGraph.getMethods( mdCallee, typeDesc ) ); + implementations.addAll(callGraph.getMethods(mdCallee, typeDesc)); } - for( Iterator imps = implementations.iterator(); imps.hasNext(); ) { + for (Iterator imps = implementations.iterator(); imps.hasNext();) { MethodDescriptor mdImp = (MethodDescriptor) imps.next(); - FlatMethod fmImp = state.getMethodFlat( mdImp ); - if ((isPotentialStallSite&&!isPotentialStallSite(fmImp))|| - !visited.contains(fmImp)) { - flatNodesToVisit.put( fmImp, fmImp ); - - // propagate your IR graph predecessor's stall site potential - mergeIsPotentialStallSite( fmImp, isPotentialStallSite ); - } + FlatMethod fmImp = state.getMethodFlat(mdImp); + + // keep mapping from fc's md to + // later, when return node of callee becomes a potential stall site, + // following flat nodes of fc should be re-analyzied + if(!methodmap.containsKey(fmImp)){ + methodmap.put(mdImp, new HashSet>()); + } + methodmap.get(mdImp).add(new Pair(fc,fm.getMethod())); + + if ((isPotentialStallSite && !isPotentialStallSite(fmImp)) || !visited.contains(fmImp)) { + flatNodesToVisit.put(fmImp, fmImp); + + // propagate your IR graph predecessor's stall site potential + mergeIsPotentialStallSite(fmImp, isPotentialStallSite); + } + } // don't 'continue' out of this loop, also enqueue // flat nodes that flow in the current method context } + + if (fn instanceof FlatReturnNode) { + // if return node is potential stall site, need to inform its caller + if (isPotentialStallSite) { + Set> callset = methodmap.get(fm.getMethod()); + if (callset != null) { + for (Pair fcallpair : callset) { + FlatCall fcall = fcallpair.getFirst(); + MethodDescriptor mdcaller = fcallpair.getSecond(); + for (int i = 0; i < fcall.numNext(); i++) { + FlatNode nn = fcall.getNext(i); + if ( visited.contains(nn) && (!isPotentialStallSite(nn)) ) { + mergeIsPotentialStallSite(nn, isPotentialStallSite); + FlatMethod fmcaller = state.getMethodFlat(mdcaller); + flatNodesToVisit.put(nn, fmcaller); + } + } + } + } + } + } - - // only when current flat node has a change on the status of potential stall site, - // need to visit following flat nodes - for (int i = 0; i < fn.numNext(); i++) { - FlatNode nn = fn.getNext(i); - if ((isPotentialStallSite&&!isPotentialStallSite(nn))|| - !visited.contains(nn)) { - flatNodesToVisit.put(nn, fm); - mergeIsPotentialStallSite( nn, isPotentialStallSite ); - } - } + // note: only when current flat node has a change on the status of potential + // stall site, need to visit following flat nodes + for (int i = 0; i < fn.numNext(); i++) { + FlatNode nn = fn.getNext(i); + if ((isPotentialStallSite && !isPotentialStallSite(nn)) || !visited.contains(nn)) { + flatNodesToVisit.put(nn, fm); + mergeIsPotentialStallSite(nn, isPotentialStallSite); + } + } } } } -- 2.34.1