From f3f73447efa7996d1c0eacbe4649d207435d8199 Mon Sep 17 00:00:00 2001 From: jjenista Date: Thu, 24 Jun 2010 00:21:36 +0000 Subject: [PATCH] add rblock relation analysis and makefile aware of new analysis files --- .../src/Analysis/RBlockRelationAnalysis.java | 200 ++++++++++++++++++ Robust/src/Makefile | 8 +- 2 files changed, 207 insertions(+), 1 deletion(-) create mode 100644 Robust/src/Analysis/RBlockRelationAnalysis.java diff --git a/Robust/src/Analysis/RBlockRelationAnalysis.java b/Robust/src/Analysis/RBlockRelationAnalysis.java new file mode 100644 index 00000000..14e04817 --- /dev/null +++ b/Robust/src/Analysis/RBlockRelationAnalysis.java @@ -0,0 +1,200 @@ +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/Makefile b/Robust/src/Makefile index d3fbb1b7..15920cac 100644 --- a/Robust/src/Makefile +++ b/Robust/src/Makefile @@ -98,6 +98,11 @@ Analysis/MLP/SVKey.class \ Analysis/MLP/VarSrcTokTable.class \ Analysis/MLP/CodePlan.class \ Analysis/OoOJava/OoOJavaAnalysis.class \ +Analysis/OoOJava/CodePlan.class \ +Analysis/OoOJava/SVKey.class \ +Analysis/OoOJava/VSTWrapper.class \ +Analysis/OoOJava/VarSrcTokTable.class \ +Analysis/OoOJava/VariableSourceToken.class \ Util/GraphNode.class Util/Namer.class Util/Relation.class \ Util/UtilAlgorithms.class \ Interface/HTTPHeader.class Interface/HTTPResponse.class \ @@ -132,6 +137,7 @@ JAVAFILES=IR/*.java \ Analysis/OwnershipAnalysis/*.java \ Analysis/Disjoint/*.java \ Analysis/MLP/*.java \ + Analysis/OoOJava/*.java \ Analysis/Prefetch/*.java \ Analysis/Scheduling/*.java \ Analysis/TaskStateAnalysis/*.java \ @@ -185,7 +191,7 @@ javadoc: javadoc -classpath ../cup:.:$(CLASSPATH) -sourcepath . -private -d javadoc Lex Util IR IR.Tree IR.Flat Analysis Analysis.CallGraph Analysis.Flag Analysis.TaskStateAnalysis Analysis.Locality Analysis.Prefetch Main Analysis.OwnershipAnalysis Analysis.Disjoint Analysis.MLP Analysis.Scheduling clean: - rm -f IR/*.class IR/Tree/*.class Main/*.class Lex/*.class Parse/*.class Parse/Sym.java Parse/Parser.java IR/Flat/*.class classdefs.h methodheaders.h methods.c structdefs.h virtualtable.h task.h taskdefs.c taskdefs.h Analysis/*.class Analysis/Flag/*.class Analysis/CallGraph/*.class Analysis/TaskStateAnalysis/*.class Interface/*.class Util/*.class Analysis/Locality/*.class Analysis/Prefetch/*.class Analysis/FlatIRGraph/*.class Analysis/OwnershipAnalysis/*.class Analysis/Disjoint/*.class Analysis/MLP/*.class Analysis/Scheduling/*.class Analysis/Loops/*.class + rm -f IR/*.class IR/Tree/*.class Main/*.class Lex/*.class Parse/*.class Parse/Sym.java Parse/Parser.java IR/Flat/*.class classdefs.h methodheaders.h methods.c structdefs.h virtualtable.h task.h taskdefs.c taskdefs.h Analysis/*.class Analysis/Flag/*.class Analysis/CallGraph/*.class Analysis/TaskStateAnalysis/*.class Interface/*.class Util/*.class Analysis/Locality/*.class Analysis/Prefetch/*.class Analysis/FlatIRGraph/*.class Analysis/OwnershipAnalysis/*.class Analysis/Disjoint/*.class Analysis/OoOJava/*.class Analysis/MLP/*.class Analysis/Scheduling/*.class Analysis/Loops/*.class cleanclass: rm -f IR/*.class IR/Tree/*.class Main/*.class IR/Flat/*.class Analysis/*.class Analysis/Flag/*.class Analysis/CallGraph/*.class Analysis/TaskStateAnalysis/*.class Interface/*.class Util/*.class Analysis/Locality/*.class Analysis/Prefetch/*.class Analysis/FlatIRGraph/*.class Analysis/OwnershipAnalysis/*.class Analysis/Disjoint/*.class Analysis/MLP/*.class Analysis/Scheduling/*.class Analysis/Loops/*.class -- 2.34.1