From 0c4bda74ebe52a302d3d3ddc1b335b80d9fb482e Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 28 Jun 2010 18:00:35 +0000 Subject: [PATCH] changed organization and brought in a few new pieces for new disjoint+ooojava --- .../Analysis/Disjoint/DisjointAnalysis.java | 4 +- .../src/Analysis/OoOJava/OoOJavaAnalysis.java | 2 - .../src/Analysis/RBlockRelationAnalysis.java | 200 ---------------- Robust/src/Analysis/RBlockStatusAnalysis.java | 222 ------------------ Robust/src/Main/Main.java | 1 - 5 files changed, 2 insertions(+), 427 deletions(-) delete mode 100644 Robust/src/Analysis/RBlockRelationAnalysis.java delete mode 100644 Robust/src/Analysis/RBlockStatusAnalysis.java diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 86dc5366..1fc3ba7f 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -3,8 +3,8 @@ package Analysis.Disjoint; import Analysis.CallGraph.*; import Analysis.Liveness; import Analysis.ArrayReferencees; -import Analysis.RBlockRelationAnalysis; -import Analysis.RBlockStatusAnalysis; +import Analysis.OoOJava.RBlockRelationAnalysis; +import Analysis.OoOJava.RBlockStatusAnalysis; import IR.*; import IR.Flat.*; import IR.Tree.Modifiers; diff --git a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java index d052f23f..e20b95db 100644 --- a/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java +++ b/Robust/src/Analysis/OoOJava/OoOJavaAnalysis.java @@ -11,8 +11,6 @@ import java.util.Map.Entry; import Analysis.ArrayReferencees; import Analysis.Liveness; -import Analysis.RBlockRelationAnalysis; -import Analysis.RBlockStatusAnalysis; import Analysis.CallGraph.CallGraph; import Analysis.Disjoint.DisjointAnalysis; import Analysis.Disjoint.Effect; diff --git a/Robust/src/Analysis/RBlockRelationAnalysis.java b/Robust/src/Analysis/RBlockRelationAnalysis.java deleted file mode 100644 index 14e04817..00000000 --- a/Robust/src/Analysis/RBlockRelationAnalysis.java +++ /dev/null @@ -1,200 +0,0 @@ -package Analysis; - -import IR.State; -import IR.TypeUtil; -import Analysis.CallGraph.CallGraph; -import IR.MethodDescriptor; -import IR.Flat.*; -import java.util.*; - -// This analysis computes relations between rblocks -// and identifies important rblocks. - -public class RBlockRelationAnalysis { - - // compiler data - State state; - TypeUtil typeUtil; - CallGraph callGraph; - - // an implicit SESE is automatically spliced into - // the IR graph around the C main before this analysis--it - // is nothing special except that we can make assumptions - // about it, such as the whole program ends when it ends - protected FlatSESEEnterNode mainSESE; - - // SESEs that are the root of an SESE tree belong to this - // set--the main SESE is always a root, statically SESEs - // inside methods are a root because we don't know how they - // will fit into the runtime tree of SESEs - protected Set rootSESEs; - - // simply a set of every reachable SESE in the program, not - // including caller placeholder SESEs - protected Set allSESEs; - - // per method-per node-rblock stacks - protected Hashtable< FlatMethod, - Hashtable< FlatNode, - Stack - > - > fm2relmap; - - - public RBlockRelationAnalysis( State state, - TypeUtil typeUtil, - CallGraph callGraph ) { - this.state = state; - this.typeUtil = typeUtil; - this.callGraph = callGraph; - - rootSESEs = new HashSet(); - allSESEs = new HashSet(); - - fm2relmap = - new Hashtable< FlatMethod, Hashtable< FlatNode, Stack > >(); - - - MethodDescriptor mdSourceEntry = typeUtil.getMain(); - FlatMethod fmMain = state.getMethodFlat( mdSourceEntry ); - - mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 ); - mainSESE.setfmEnclosing( fmMain ); - mainSESE.setmdEnclosing( fmMain.getMethod() ); - mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() ); - - // add all methods transitively reachable from the - // source's main to set for analysis - Set descriptorsToAnalyze = - callGraph.getAllMethods( mdSourceEntry ); - - descriptorsToAnalyze.add( mdSourceEntry ); - - analyzeMethods( descriptorsToAnalyze ); - } - - - public FlatSESEEnterNode getMainSESE() { - return mainSESE; - } - - public Set getRootSESEs() { - return rootSESEs; - } - - public Set getAllSESEs() { - return allSESEs; - } - - public Stack getRBlockStacks( FlatMethod fm, - FlatNode fn ) { - if( !fm2relmap.containsKey( fm ) ) { - fm2relmap.put( fm, computeRBlockRelations( fm ) ); - } - return fm2relmap.get( fm ).get( fn ); - } - - - protected void analyzeMethods( Set descriptorsToAnalyze ) { - - Iterator mdItr = descriptorsToAnalyze.iterator(); - while( mdItr.hasNext() ) { - FlatMethod fm = state.getMethodFlat( mdItr.next() ); - - Hashtable< FlatNode, Stack > relmap = - computeRBlockRelations( fm ); - - fm2relmap.put( fm, relmap ); - } - } - - public Hashtable< FlatNode, Stack > - computeRBlockRelations( FlatMethod fm ) { - - Hashtable< FlatNode, Stack > seseStacks = - new Hashtable< FlatNode, Stack >(); - - // start from flat method top, visit every node in - // method exactly once, find SESE stack on every - // control path - Set flatNodesToVisit = new HashSet(); - flatNodesToVisit.add( fm ); - - Set visited = new HashSet(); - - Stack seseStackFirst = new Stack(); - seseStacks.put( fm, seseStackFirst ); - - while( !flatNodesToVisit.isEmpty() ) { - Iterator fnItr = flatNodesToVisit.iterator(); - FlatNode fn = fnItr.next(); - - Stack seseStack = seseStacks.get( fn ); - assert seseStack != null; - - flatNodesToVisit.remove( fn ); - visited.add( fn ); - - nodeActions( fn, seseStack, fm ); - - for( int i = 0; i < fn.numNext(); i++ ) { - FlatNode nn = fn.getNext( i ); - - if( !visited.contains( nn ) ) { - flatNodesToVisit.add( nn ); - - // clone stack and send along each control path - seseStacks.put( nn, (Stack)seseStack.clone() ); - } - } - } - - return seseStacks; - } - - protected void nodeActions( FlatNode fn, - Stack seseStack, - FlatMethod fm ) { - switch( fn.kind() ) { - - case FKind.FlatSESEEnterNode: { - FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn; - - if( !fsen.getIsCallerSESEplaceholder() ) { - allSESEs.add( fsen ); - } - - fsen.setfmEnclosing( fm ); - fsen.setmdEnclosing( fm.getMethod() ); - fsen.setcdEnclosing( fm.getMethod().getClassDesc() ); - - if( seseStack.empty() ) { - rootSESEs.add( fsen ); - fsen.setParent( null ); - } else { - seseStack.peek().addChild( fsen ); - fsen.setParent( seseStack.peek() ); - } - - seseStack.push( fsen ); - } break; - - case FKind.FlatSESEExitNode: { - FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; - assert !seseStack.empty(); - FlatSESEEnterNode fsen = seseStack.pop(); - } break; - - case FKind.FlatReturnNode: { - FlatReturnNode frn = (FlatReturnNode) fn; - if( !seseStack.empty() && - !seseStack.peek().getIsCallerSESEplaceholder() - ) { - throw new Error( "Error: return statement enclosed within SESE "+ - seseStack.peek().getPrettyIdentifier() ); - } - } break; - - } - } -} diff --git a/Robust/src/Analysis/RBlockStatusAnalysis.java b/Robust/src/Analysis/RBlockStatusAnalysis.java deleted file mode 100644 index 01858600..00000000 --- a/Robust/src/Analysis/RBlockStatusAnalysis.java +++ /dev/null @@ -1,222 +0,0 @@ -package Analysis; - -import java.util.HashSet; -import java.util.Hashtable; -import java.util.Iterator; -import java.util.LinkedList; -import java.util.Set; -import java.util.Stack; -import java.util.Map.Entry; - -import Analysis.CallGraph.CallGraph; -import IR.MethodDescriptor; -import IR.State; -import IR.TypeUtil; -import IR.Flat.FKind; -import IR.Flat.FlatMethod; -import IR.Flat.FlatNode; -import IR.Flat.FlatSESEEnterNode; -import IR.Flat.FlatSESEExitNode; - -public class RBlockStatusAnalysis { - - // compiler data - State state; - TypeUtil typeUtil; - CallGraph callGraph; - RBlockRelationAnalysis rra; - - // per method-per node-rblock stacks - protected Hashtable>> fm2statusmap; - - public RBlockStatusAnalysis(State state, TypeUtil typeUtil, CallGraph callGraph, - RBlockRelationAnalysis rra) { - this.state = state; - this.typeUtil = typeUtil; - this.callGraph = callGraph; - this.rra = rra; - - fm2statusmap = - new Hashtable>>(); - - MethodDescriptor mdSourceEntry = typeUtil.getMain(); - FlatMethod fmMain = state.getMethodFlat(mdSourceEntry); - - // add all methods transitively reachable from the - // source's main to set for analysis - Set descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry); - - descriptorsToAnalyze.add(mdSourceEntry); - - analyzeMethods(descriptorsToAnalyze); - - // analyzeMethodsDebug(descriptorsToAnalyze); - } - - protected void analyzeMethods(Set descriptorsToAnalyze) { - - Iterator mdItr = descriptorsToAnalyze.iterator(); - while (mdItr.hasNext()) { - FlatMethod fm = state.getMethodFlat(mdItr.next()); - - Hashtable> fn2seseStatus = - computeRBlockStatus(fm); - - fm2statusmap.put(fm, fn2seseStatus); - } - } - - public Hashtable> computeRBlockStatus( - FlatMethod fm) { - - Hashtable> seseStacks = - new Hashtable>(); - - Hashtable> fn2seseStatus = - new Hashtable>(); - - LinkedList flatNodesToVisit = new LinkedList(); - flatNodesToVisit.add(fm); - - Stack seseStackFirst = new Stack(); - seseStacks.put(fm, seseStackFirst); - - while (!flatNodesToVisit.isEmpty()) { - Iterator fnItr = flatNodesToVisit.iterator(); - FlatNode fn = fnItr.next(); - - Hashtable prevResult = fn2seseStatus.get(fn); - - Hashtable currentResult = - new Hashtable(); - - for (int i = 0; i < fn.numPrev(); i++) { - FlatNode prevFlatNode = fn.getPrev(i); - Hashtable incoming = fn2seseStatus.get(prevFlatNode); - if (incoming != null) { - merge(currentResult, incoming); - } - } - - flatNodesToVisit.remove(fn); - - nodeActions(fn, fm, currentResult); - - // if we have a new result, schedule forward nodes for - // analysis - if (prevResult == null || !currentResult.equals(prevResult)) { - fn2seseStatus.put(fn, currentResult); - for (int i = 0; i < fn.numNext(); i++) { - FlatNode nn = fn.getNext(i); - flatNodesToVisit.addFirst(nn); - } - } - } - - return fn2seseStatus; - } - - private void merge(Hashtable current, - Hashtable incoming) { - - Iterator inIter = incoming.entrySet().iterator(); - while (inIter.hasNext()) { - Entry inEntry = (Entry) inIter.next(); - FlatSESEEnterNode seseContaining = (FlatSESEEnterNode) inEntry.getKey(); - Boolean isAfter = (Boolean) inEntry.getValue(); - - Boolean currentIsAfter = current.get(seseContaining); - if (currentIsAfter == null || currentIsAfter == Boolean.FALSE) { - current.put(seseContaining, isAfter); - } - } - - } - - public boolean isInCriticalRegion(FlatMethod fmContaining, FlatNode fn) { - FlatSESEEnterNode seseContaining = rra.getRBlockStacks(fmContaining, fn).peek(); - Hashtable> statusMap = - fm2statusmap.get(fmContaining); - Hashtable status = statusMap.get(fn); - - if(status.get(seseContaining).booleanValue()==true){ - System.out.println(fn+" is in the critical region in according to "+seseContaining); - } - - return status.get(seseContaining).booleanValue(); - } - - protected void nodeActions(FlatNode fn, FlatMethod fm, - Hashtable status) { - switch (fn.kind()) { - - case FKind.FlatSESEExitNode: { - FlatSESEExitNode fsexn = (FlatSESEExitNode) fn; - FlatSESEEnterNode fsen = fsexn.getFlatEnter(); - if (fsen.getParent() != null) { - status.put(fsen.getParent(), Boolean.TRUE); - } - } - break; - - default: { - if (!(fn instanceof FlatMethod)) { - Stack seseStack = rra.getRBlockStacks(fm, fn); - if (!seseStack.isEmpty()) { - FlatSESEEnterNode currentParent = seseStack.peek(); - if (!status.containsKey(currentParent)) { - status.put(currentParent, Boolean.FALSE); - } - } - } - - } - break; - } - - } - - /* - * DEBUG - */ - protected void analyzeMethodsDebug(Set descriptorsToAnalyze) { - - Iterator mdItr = descriptorsToAnalyze.iterator(); - while (mdItr.hasNext()) { - FlatMethod fm = state.getMethodFlat(mdItr.next()); - printStatusMap(fm); - - } - } - - protected void printStatusMap(FlatMethod fm) { - - Set flatNodesToVisit = new HashSet(); - flatNodesToVisit.add(fm); - - Set visited = new HashSet(); - - while (!flatNodesToVisit.isEmpty()) { - Iterator fnItr = flatNodesToVisit.iterator(); - FlatNode fn = fnItr.next(); - - flatNodesToVisit.remove(fn); - visited.add(fn); - - System.out.println("------------------"); - System.out.println("fn=" + fn); - System.out.println(fm2statusmap.get(fm).get(fn)); - - for (int i = 0; i < fn.numNext(); i++) { - FlatNode nn = fn.getNext(i); - - if (!visited.contains(nn)) { - flatNodesToVisit.add(nn); - - } - } - } - - } - -} diff --git a/Robust/src/Main/Main.java b/Robust/src/Main/Main.java index 6ef4a871..73224acb 100644 --- a/Robust/src/Main/Main.java +++ b/Robust/src/Main/Main.java @@ -42,7 +42,6 @@ import Analysis.Prefetch.PrefetchAnalysis; import Analysis.FlatIRGraph.FlatIRGraph; import Analysis.OwnershipAnalysis.OwnershipAnalysis; import Analysis.MLP.MLPAnalysis; -import Analysis.RBlockRelationAnalysis; import Analysis.Disjoint.DisjointAnalysis; import Analysis.OoOJava.OoOJavaAnalysis; import Analysis.Loops.*; -- 2.34.1