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>
43 // to support calculation of leaf SESEs (no children even
44 // through method calls) for optimization during code gen
45 protected Set<MethodDescriptor> methodsContainingSESEs;
48 public RBlockRelationAnalysis( State state,
50 CallGraph callGraph ) {
52 this.typeUtil = typeUtil;
53 this.callGraph = callGraph;
55 rootSESEs = new HashSet<FlatSESEEnterNode>();
56 allSESEs = new HashSet<FlatSESEEnterNode>();
58 methodsContainingSESEs = new HashSet<MethodDescriptor>();
61 new Hashtable< FlatMethod, Hashtable< FlatNode, Stack<FlatSESEEnterNode> > >();
64 MethodDescriptor mdSourceEntry = typeUtil.getMain();
65 FlatMethod fmMain = state.getMethodFlat( mdSourceEntry );
67 mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
68 mainSESE.setfmEnclosing( fmMain );
69 mainSESE.setmdEnclosing( fmMain.getMethod() );
70 mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
72 // add all methods transitively reachable from the
73 // source's main to set for analysis
74 Set<MethodDescriptor> descriptorsToAnalyze =
75 callGraph.getAllMethods( mdSourceEntry );
77 descriptorsToAnalyze.add( mdSourceEntry );
79 analyzeMethods( descriptorsToAnalyze );
85 public FlatSESEEnterNode getMainSESE() {
89 public Set<FlatSESEEnterNode> getRootSESEs() {
93 public Set<FlatSESEEnterNode> getAllSESEs() {
97 public Stack<FlatSESEEnterNode> getRBlockStacks( FlatMethod fm,
99 if( !fm2relmap.containsKey( fm ) ) {
100 fm2relmap.put( fm, computeRBlockRelations( fm ) );
102 return fm2relmap.get( fm ).get( fn );
106 protected void analyzeMethods( Set<MethodDescriptor> descriptorsToAnalyze ) {
108 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
109 while( mdItr.hasNext() ) {
110 FlatMethod fm = state.getMethodFlat( mdItr.next() );
112 Hashtable< FlatNode, Stack<FlatSESEEnterNode> > relmap =
113 computeRBlockRelations( fm );
115 fm2relmap.put( fm, relmap );
119 public Hashtable< FlatNode, Stack<FlatSESEEnterNode> >
120 computeRBlockRelations( FlatMethod fm ) {
122 Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
123 new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
125 // start from flat method top, visit every node in
126 // method exactly once, find SESE stack on every
128 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
129 flatNodesToVisit.add( fm );
131 Set<FlatNode> visited = new HashSet<FlatNode>();
133 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
134 seseStacks.put( fm, seseStackFirst );
136 while( !flatNodesToVisit.isEmpty() ) {
137 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
138 FlatNode fn = fnItr.next();
140 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
141 assert seseStack != null;
143 flatNodesToVisit.remove( fn );
146 nodeActions( fn, seseStack, fm );
148 for( int i = 0; i < fn.numNext(); i++ ) {
149 FlatNode nn = fn.getNext( i );
151 if( !visited.contains( nn ) ) {
152 flatNodesToVisit.add( nn );
154 // clone stack and send along each control path
155 seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
163 protected void nodeActions( FlatNode fn,
164 Stack<FlatSESEEnterNode> seseStack,
166 switch( fn.kind() ) {
168 case FKind.FlatSESEEnterNode: {
169 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
171 if( !fsen.getIsCallerSESEplaceholder() ) {
172 allSESEs.add( fsen );
173 methodsContainingSESEs.add( fm.getMethod() );
176 fsen.setfmEnclosing( fm );
177 fsen.setmdEnclosing( fm.getMethod() );
178 fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
180 if( seseStack.empty() ) {
181 rootSESEs.add( fsen );
182 fsen.setParent( null );
184 seseStack.peek().addChild( fsen );
185 fsen.setParent( seseStack.peek() );
188 seseStack.push( fsen );
191 case FKind.FlatSESEExitNode: {
192 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
193 assert !seseStack.empty();
194 FlatSESEEnterNode fsen = seseStack.pop();
197 case FKind.FlatReturnNode: {
198 FlatReturnNode frn = (FlatReturnNode) fn;
199 if( !seseStack.empty() &&
200 !seseStack.peek().getIsCallerSESEplaceholder()
202 throw new Error( "Error: return statement enclosed within SESE "+
203 seseStack.peek().getPrettyIdentifier() );
211 protected void computeLeafSESEs() {
212 for( Iterator<FlatSESEEnterNode> itr = allSESEs.iterator();
215 FlatSESEEnterNode fsen = itr.next();
217 boolean hasNoNestedChildren = !fsen.getChildren().isEmpty();
218 boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
220 fsen.setIsLeafSESE( hasNoNestedChildren &&
221 hasNoChildrenByCall );
226 protected boolean hasChildrenByCall( FlatSESEEnterNode fsen ) {
228 // visit every flat node in SESE body, find method calls that
229 // may transitively call methods with SESEs enclosed
230 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
231 flatNodesToVisit.add( fsen );
233 Set<FlatNode> visited = new HashSet<FlatNode>();
235 while( !flatNodesToVisit.isEmpty() ) {
236 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
237 FlatNode fn = fnItr.next();
239 flatNodesToVisit.remove( fn );
242 if( fn.kind() == FKind.FlatCall ) {
243 FlatCall fc = (FlatCall) fn;
244 MethodDescriptor mdCallee = fc.getMethod();
245 Set reachable = new HashSet();
247 reachable.addAll( callGraph.getAllMethods( mdCallee ) );
248 reachable.retainAll( methodsContainingSESEs );
250 if( !reachable.isEmpty() ) {
255 if( fn == fsen.getFlatExit() ) {
256 // don't enqueue any futher nodes
260 for( int i = 0; i < fn.numNext(); i++ ) {
261 FlatNode nn = fn.getNext( i );
263 if( !visited.contains( nn ) ) {
264 flatNodesToVisit.add( nn );