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;
47 // maps method descriptor to SESE defined inside of it
48 // only contains top-level SESE definition in corresponding method
49 protected Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>> md2seseSet;
51 public RBlockRelationAnalysis( State state,
53 CallGraph callGraph ) {
55 this.typeUtil = typeUtil;
56 this.callGraph = callGraph;
58 rootSESEs = new HashSet<FlatSESEEnterNode>();
59 allSESEs = new HashSet<FlatSESEEnterNode>();
61 methodsContainingSESEs = new HashSet<MethodDescriptor>();
64 new Hashtable< FlatMethod, Hashtable< FlatNode, Stack<FlatSESEEnterNode> > >();
66 md2seseSet = new Hashtable<MethodDescriptor, Set<FlatSESEEnterNode>>();
69 MethodDescriptor mdSourceEntry = typeUtil.getMain();
70 FlatMethod fmMain = state.getMethodFlat( mdSourceEntry );
72 mainSESE = (FlatSESEEnterNode) fmMain.getNext( 0 );
73 mainSESE.setfmEnclosing( fmMain );
74 mainSESE.setmdEnclosing( fmMain.getMethod() );
75 mainSESE.setcdEnclosing( fmMain.getMethod().getClassDesc() );
77 // add all methods transitively reachable from the
78 // source's main to set for analysis
79 Set<MethodDescriptor> descriptorsToAnalyze =
80 callGraph.getAllMethods( mdSourceEntry );
82 descriptorsToAnalyze.add( mdSourceEntry );
84 analyzeMethods( descriptorsToAnalyze );
90 public FlatSESEEnterNode getMainSESE() {
94 public Set<FlatSESEEnterNode> getRootSESEs() {
98 public Set<FlatSESEEnterNode> getAllSESEs() {
102 public Stack<FlatSESEEnterNode> getRBlockStacks( FlatMethod fm,
104 if( !fm2relmap.containsKey( fm ) ) {
105 fm2relmap.put( fm, computeRBlockRelations( fm ) );
107 return fm2relmap.get( fm ).get( fn );
111 protected void analyzeMethods( Set<MethodDescriptor> descriptorsToAnalyze ) {
113 Iterator<MethodDescriptor> mdItr = descriptorsToAnalyze.iterator();
114 while( mdItr.hasNext() ) {
115 FlatMethod fm = state.getMethodFlat( mdItr.next() );
117 Hashtable< FlatNode, Stack<FlatSESEEnterNode> > relmap =
118 computeRBlockRelations( fm );
120 fm2relmap.put( fm, relmap );
124 public Hashtable< FlatNode, Stack<FlatSESEEnterNode> >
125 computeRBlockRelations( FlatMethod fm ) {
127 Hashtable< FlatNode, Stack<FlatSESEEnterNode> > seseStacks =
128 new Hashtable< FlatNode, Stack<FlatSESEEnterNode> >();
130 // start from flat method top, visit every node in
131 // method exactly once, find SESE stack on every
133 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
134 flatNodesToVisit.add( fm );
136 Set<FlatNode> visited = new HashSet<FlatNode>();
138 Stack<FlatSESEEnterNode> seseStackFirst = new Stack<FlatSESEEnterNode>();
139 seseStacks.put( fm, seseStackFirst );
141 while( !flatNodesToVisit.isEmpty() ) {
142 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
143 FlatNode fn = fnItr.next();
145 Stack<FlatSESEEnterNode> seseStack = seseStacks.get( fn );
146 assert seseStack != null;
148 flatNodesToVisit.remove( fn );
151 nodeActions( fn, seseStack, fm );
153 for( int i = 0; i < fn.numNext(); i++ ) {
154 FlatNode nn = fn.getNext( i );
156 if( !visited.contains( nn ) ) {
157 flatNodesToVisit.add( nn );
159 // clone stack and send along each control path
160 seseStacks.put( nn, (Stack<FlatSESEEnterNode>)seseStack.clone() );
168 protected void nodeActions( FlatNode fn,
169 Stack<FlatSESEEnterNode> seseStack,
171 switch( fn.kind() ) {
173 case FKind.FlatSESEEnterNode: {
174 FlatSESEEnterNode fsen = (FlatSESEEnterNode) fn;
176 if( !fsen.getIsCallerSESEplaceholder() ) {
177 allSESEs.add( fsen );
178 methodsContainingSESEs.add( fm.getMethod() );
181 fsen.setfmEnclosing( fm );
182 fsen.setmdEnclosing( fm.getMethod() );
183 fsen.setcdEnclosing( fm.getMethod().getClassDesc() );
185 if(!fsen.getIsCallerSESEplaceholder() && fsen.getParent()==null ){
186 Set<FlatSESEEnterNode> seseSet=md2seseSet.get(fm.getMethod());
188 seseSet=new HashSet<FlatSESEEnterNode>();
191 md2seseSet.put(fm.getMethod(), seseSet);
194 if( seseStack.empty() ) {
195 rootSESEs.add( fsen );
196 fsen.setParent( null );
198 seseStack.peek().addChild( fsen );
199 fsen.setParent( seseStack.peek() );
202 seseStack.push( fsen );
205 case FKind.FlatSESEExitNode: {
206 FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
207 assert !seseStack.empty();
208 FlatSESEEnterNode fsen = seseStack.pop();
211 case FKind.FlatReturnNode: {
212 FlatReturnNode frn = (FlatReturnNode) fn;
213 if( !seseStack.empty() &&
214 !seseStack.peek().getIsCallerSESEplaceholder()
216 throw new Error( "Error: return statement enclosed within SESE "+
217 seseStack.peek().getPrettyIdentifier() );
225 protected void computeLeafSESEs() {
226 for( Iterator<FlatSESEEnterNode> itr = allSESEs.iterator();
229 FlatSESEEnterNode fsen = itr.next();
231 boolean hasNoNestedChildren = fsen.getChildren().isEmpty();
232 boolean hasNoChildrenByCall = !hasChildrenByCall( fsen );
234 fsen.setIsLeafSESE( hasNoNestedChildren &&
235 hasNoChildrenByCall );
240 protected boolean hasChildrenByCall(FlatSESEEnterNode fsen) {
242 boolean hasChildrenByCall=false;
244 // visit every flat node in SESE body, find method calls that
245 // may transitively call methods with SESEs enclosed
246 Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
247 flatNodesToVisit.add(fsen);
249 Set<FlatNode> visited = new HashSet<FlatNode>();
251 while (!flatNodesToVisit.isEmpty()) {
252 Iterator<FlatNode> fnItr = flatNodesToVisit.iterator();
253 FlatNode fn = fnItr.next();
255 flatNodesToVisit.remove(fn);
258 if (fn.kind() == FKind.FlatCall) {
259 FlatCall fc = (FlatCall) fn;
260 MethodDescriptor mdCallee = fc.getMethod();
261 Set reachable = new HashSet();
263 reachable.add(mdCallee);
264 reachable.addAll(callGraph.getAllMethods(mdCallee));
266 reachable.retainAll(methodsContainingSESEs);
268 if (!reachable.isEmpty()) {
269 hasChildrenByCall = true;
271 Set reachableSESEMethodSet =
272 callGraph.getFirstReachableMethodContainingSESE(mdCallee, methodsContainingSESEs);
274 if (methodsContainingSESEs.contains(mdCallee)) {
275 reachableSESEMethodSet.add(mdCallee);
278 for (Iterator iterator = reachableSESEMethodSet.iterator(); iterator.hasNext();) {
279 MethodDescriptor md = (MethodDescriptor) iterator.next();
280 Set<FlatSESEEnterNode> seseSet = md2seseSet.get(md);
281 if (seseSet != null) {
282 fsen.addSESEChildren(seseSet);
289 if (fn == fsen.getFlatExit()) {
290 // don't enqueue any futher nodes
294 for (int i = 0; i < fn.numNext(); i++) {
295 FlatNode nn = fn.getNext(i);
297 if (!visited.contains(nn)) {
298 flatNodesToVisit.add(nn);
303 return hasChildrenByCall;