1 package Analysis.OoOJava;
5 import Analysis.CallGraph.CallGraph;
6 import IR.MethodDescriptor;
10 // This analysis computes relations between rblocks
11 // and identifies important rblocks.
13 public class RBlockRelationAnalysis {
20 // an implicit SESE is automatically spliced into
21 // the IR graph around the C main before this analysis--it
22 // is nothing special except that we can make assumptions
23 // about it, such as the whole program ends when it ends
24 protected FlatSESEEnterNode mainSESE;
26 // SESEs that are the root of an SESE tree belong to this
27 // set--the main SESE is always a root, statically SESEs
28 // inside methods are a root because we don't know how they
29 // will fit into the runtime tree of SESEs
30 protected Set<FlatSESEEnterNode> rootSESEs;
32 // simply a set of every reachable SESE in the program, not
33 // including caller placeholder SESEs
34 protected Set<FlatSESEEnterNode> allSESEs;
36 // per method-per node-rblock stacks
37 protected Hashtable< FlatMethod,
39 Stack<FlatSESEEnterNode>
44 public RBlockRelationAnalysis( State state,
46 CallGraph callGraph ) {
48 this.typeUtil = typeUtil;
49 this.callGraph = callGraph;
51 rootSESEs = new HashSet<FlatSESEEnterNode>();
52 allSESEs = new HashSet<FlatSESEEnterNode>();
55 new Hashtable< FlatMethod, Hashtable< FlatNode, Stack<FlatSESEEnterNode> > >();
58 MethodDescriptor mdSourceEntry = typeUtil.getMain();
59 FlatMethod fmMain = state.getMethodFlat( mdSourceEntry );
61 mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
62 mainSESE.setfmEnclosing( fmMain );
63 mainSESE.setmdEnclosing( fmMain.getMethod() );
64 mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
66 // add all methods transitively reachable from the
67 // source's main to set for analysis
68 Set<MethodDescriptor> descriptorsToAnalyze =
69 callGraph.getAllMethods( mdSourceEntry );
71 descriptorsToAnalyze.add( mdSourceEntry );
73 analyzeMethods( descriptorsToAnalyze );
77 public FlatSESEEnterNode getMainSESE() {
81 public Set<FlatSESEEnterNode> getRootSESEs() {
85 public Set<FlatSESEEnterNode> getAllSESEs() {
89 public Stack<FlatSESEEnterNode> getRBlockStacks( FlatMethod fm,
91 if( !fm2relmap.containsKey( fm ) ) {
92 fm2relmap.put( fm, computeRBlockRelations( fm ) );
94 return fm2relmap.get( fm ).get( fn );
98 protected void analyzeMethods( Set<MethodDescriptor> descriptorsToAnalyze ) {
100 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
101 while( mdItr.hasNext() ) {
102 FlatMethod fm = state.getMethodFlat( mdItr.next() );
104 Hashtable< FlatNode, Stack<FlatSESEEnterNode> > relmap =
105 computeRBlockRelations( fm );
107 fm2relmap.put( fm, relmap );
111 public Hashtable< FlatNode, Stack<FlatSESEEnterNode> >
112 computeRBlockRelations( FlatMethod fm ) {
114 Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
115 new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
117 // start from flat method top, visit every node in
118 // method exactly once, find SESE stack on every
120 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
121 flatNodesToVisit.add( fm );
123 Set<FlatNode> visited = new HashSet<FlatNode>();
125 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
126 seseStacks.put( fm, seseStackFirst );
128 while( !flatNodesToVisit.isEmpty() ) {
129 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
130 FlatNode fn = fnItr.next();
132 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
133 assert seseStack != null;
135 flatNodesToVisit.remove( fn );
138 nodeActions( fn, seseStack, fm );
140 for( int i = 0; i < fn.numNext(); i++ ) {
141 FlatNode nn = fn.getNext( i );
143 if( !visited.contains( nn ) ) {
144 flatNodesToVisit.add( nn );
146 // clone stack and send along each control path
147 seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
155 protected void nodeActions( FlatNode fn,
156 Stack<FlatSESEEnterNode> seseStack,
158 switch( fn.kind() ) {
160 case FKind.FlatSESEEnterNode: {
161 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
163 if( !fsen.getIsCallerSESEplaceholder() ) {
164 allSESEs.add( fsen );
167 fsen.setfmEnclosing( fm );
168 fsen.setmdEnclosing( fm.getMethod() );
169 fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
171 if( seseStack.empty() ) {
172 rootSESEs.add( fsen );
173 fsen.setParent( null );
175 seseStack.peek().addChild( fsen );
176 fsen.setParent( seseStack.peek() );
179 seseStack.push( fsen );
182 case FKind.FlatSESEExitNode: {
183 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
184 assert !seseStack.empty();
185 FlatSESEEnterNode fsen = seseStack.pop();
188 case FKind.FlatReturnNode: {
189 FlatReturnNode frn = (FlatReturnNode) fn;
190 if( !seseStack.empty() &&
191 !seseStack.peek().getIsCallerSESEplaceholder()
193 throw new Error( "Error: return statement enclosed within SESE "+
194 seseStack.peek().getPrettyIdentifier() );