+++ /dev/null
-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<FlatSESEEnterNode> rootSESEs;
-
- // simply a set of every reachable SESE in the program, not
- // including caller placeholder SESEs
- protected Set<FlatSESEEnterNode> allSESEs;
-
- // per method-per node-rblock stacks
- protected Hashtable< FlatMethod,
- Hashtable< FlatNode,
- Stack<FlatSESEEnterNode>
- >
- > fm2relmap;
-
-
- public RBlockRelationAnalysis( State state,
- TypeUtil typeUtil,
- CallGraph callGraph ) {
- this.state = state;
- this.typeUtil = typeUtil;
- this.callGraph = callGraph;
-
- rootSESEs = new HashSet<FlatSESEEnterNode>();
- allSESEs = new HashSet<FlatSESEEnterNode>();
-
- fm2relmap =
- new Hashtable< FlatMethod, Hashtable< FlatNode, Stack<FlatSESEEnterNode> > >();
-
-
- 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<MethodDescriptor> descriptorsToAnalyze =
- callGraph.getAllMethods( mdSourceEntry );
-
- descriptorsToAnalyze.add( mdSourceEntry );
-
- analyzeMethods( descriptorsToAnalyze );
- }
-
-
- public FlatSESEEnterNode getMainSESE() {
- return mainSESE;
- }
-
- public Set<FlatSESEEnterNode> getRootSESEs() {
- return rootSESEs;
- }
-
- public Set<FlatSESEEnterNode> getAllSESEs() {
- return allSESEs;
- }
-
- public Stack<FlatSESEEnterNode> getRBlockStacks( FlatMethod fm,
- FlatNode fn ) {
- if( !fm2relmap.containsKey( fm ) ) {
- fm2relmap.put( fm, computeRBlockRelations( fm ) );
- }
- return fm2relmap.get( fm ).get( fn );
- }
-
-
- protected void analyzeMethods( Set<MethodDescriptor> descriptorsToAnalyze ) {
-
- Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
- while( mdItr.hasNext() ) {
- FlatMethod fm = state.getMethodFlat( mdItr.next() );
-
- Hashtable< FlatNode, Stack<FlatSESEEnterNode> > relmap =
- computeRBlockRelations( fm );
-
- fm2relmap.put( fm, relmap );
- }
- }
-
- public Hashtable< FlatNode, Stack<FlatSESEEnterNode> >
- computeRBlockRelations( FlatMethod fm ) {
-
- Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
- new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
-
- // start from flat method top, visit every node in
- // method exactly once, find SESE stack on every
- // control path
- Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
- flatNodesToVisit.add( fm );
-
- Set<FlatNode> visited = new HashSet<FlatNode>();
-
- Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
- seseStacks.put( fm, seseStackFirst );
-
- while( !flatNodesToVisit.isEmpty() ) {
- Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
- FlatNode fn = fnItr.next();
-
- Stack<FlatSESEEnterNode> 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<FlatSESEEnterNode>)seseStack.clone() );
- }
- }
- }
-
- return seseStacks;
- }
-
- protected void nodeActions( FlatNode fn,
- Stack<FlatSESEEnterNode> 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;
-
- }
- }
-}
+++ /dev/null
-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<FlatMethod, Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>> 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<FlatMethod, Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>>();
-
- MethodDescriptor mdSourceEntry = typeUtil.getMain();
- FlatMethod fmMain = state.getMethodFlat(mdSourceEntry);
-
- // add all methods transitively reachable from the
- // source's main to set for analysis
- Set<MethodDescriptor> descriptorsToAnalyze = callGraph.getAllMethods(mdSourceEntry);
-
- descriptorsToAnalyze.add(mdSourceEntry);
-
- analyzeMethods(descriptorsToAnalyze);
-
- // analyzeMethodsDebug(descriptorsToAnalyze);
- }
-
- protected void analyzeMethods(Set<MethodDescriptor> descriptorsToAnalyze) {
-
- Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
- while (mdItr.hasNext()) {
- FlatMethod fm = state.getMethodFlat(mdItr.next());
-
- Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> fn2seseStatus =
- computeRBlockStatus(fm);
-
- fm2statusmap.put(fm, fn2seseStatus);
- }
- }
-
- public Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> computeRBlockStatus(
- FlatMethod fm) {
-
- Hashtable<FlatNode, Stack<FlatSESEEnterNode>> seseStacks =
- new Hashtable<FlatNode, Stack<FlatSESEEnterNode>>();
-
- Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> fn2seseStatus =
- new Hashtable<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>>();
-
- LinkedList<FlatNode> flatNodesToVisit = new LinkedList<FlatNode>();
- flatNodesToVisit.add(fm);
-
- Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
- seseStacks.put(fm, seseStackFirst);
-
- while (!flatNodesToVisit.isEmpty()) {
- Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
- FlatNode fn = fnItr.next();
-
- Hashtable<FlatSESEEnterNode, Boolean> prevResult = fn2seseStatus.get(fn);
-
- Hashtable<FlatSESEEnterNode, Boolean> currentResult =
- new Hashtable<FlatSESEEnterNode, Boolean>();
-
- for (int i = 0; i < fn.numPrev(); i++) {
- FlatNode prevFlatNode = fn.getPrev(i);
- Hashtable<FlatSESEEnterNode, Boolean> 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<FlatSESEEnterNode, Boolean> current,
- Hashtable<FlatSESEEnterNode, Boolean> 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<FlatNode, Hashtable<FlatSESEEnterNode, Boolean>> statusMap =
- fm2statusmap.get(fmContaining);
- Hashtable<FlatSESEEnterNode, Boolean> 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<FlatSESEEnterNode, Boolean> 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<FlatSESEEnterNode> 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<MethodDescriptor> descriptorsToAnalyze) {
-
- Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
- while (mdItr.hasNext()) {
- FlatMethod fm = state.getMethodFlat(mdItr.next());
- printStatusMap(fm);
-
- }
- }
-
- protected void printStatusMap(FlatMethod fm) {
-
- Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
- flatNodesToVisit.add(fm);
-
- Set<FlatNode> visited = new HashSet<FlatNode>();
-
- while (!flatNodesToVisit.isEmpty()) {
- Iterator<FlatNode> 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);
-
- }
- }
- }
-
- }
-
-}
projects / IRC.git / commitdiff