LoopStrengthener


1   /* Soot - a J*va Optimization Framework
2    * Copyright (C) 2005 Nomair A. Naeem
3    *
4    * This library is free software; you can redistribute it and/or
5    * modify it under the terms of the GNU Lesser General Public
6    * License as published by the Free Software Foundation; either
7    * version 2.1 of the License, or (at your option) any later version.
8    *
9    * This library is distributed in the hope that it will be useful,
10   * but WITHOUT ANY WARRANTY; without even the implied warranty of
11   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12   * Lesser General Public License for more details.
13   *
14   * You should have received a copy of the GNU Lesser General Public
15   * License along with this library; if not, write to the
16   * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17   * Boston, MA 02111-1307, USA.
18   */
19  
20  package soot.dava.toolkits.base.AST.transformations;
21  
22  import soot.*;
23  import java.util.*;
24  import soot.dava.internal.SET.*;
25  import soot.dava.internal.AST.*;
26  import soot.dava.toolkits.base.AST.analysis.*;
27  
28  
29  /*
30    Nomair A. Naeem 21-FEB-2005
31  
32    In the depthFirstAdaptor children of a ASTNode
33    are gotten in three ways
34    a, ASTStatementSequenceNode uses one way see caseASTStatementSequenceNode in DepthFirstAdapter
35    b, ASTTryNode uses another way see caseASTTryNode in DepthFirstAdapter
36    c, All other nodes use normalRetrieving method to retrieve the children
37  
38    TO MAKE CODE EFFECIENT BLOCK THE ANALYSIS TO GOING INTO STATEMENTS
39    this is done by overriding the caseASTStatementSequenceNode
40  
41    Current tasks of the cleaner:
42  
43  */
44  
45  public class LoopStrengthener extends DepthFirstAdapter{
46  
47      public LoopStrengthener(){
48      }
49  
50      public LoopStrengthener(boolean verbose){
51      super(verbose);
52      }
53  
54      
55      public void caseASTStatementSequenceNode(ASTStatementSequenceNode node){
56      }
57  
58      /*
59        Note the ASTNode in this case can be any of the following:
60        ASTMethodNode
61        ASTSwitchNode
62        ASTIfNode
63        ASTIfElseNode
64        ASTUnconditionalWhileNode
65        ASTWhileNode
66        ASTDoWhileNode
67        ASTForLoopNode
68        ASTLabeledBlockNode
69        ASTSynchronizedBlockNode
70      */
71      public void normalRetrieving(ASTNode node){
72      if(node instanceof ASTSwitchNode){
73          dealWithSwitchNode((ASTSwitchNode)node);
74          return;
75      }
76  
77      //from the Node get the subBodes
78      Iterator sbit = node.get_SubBodies().iterator();
79  
80      //onlyASTIfElseNode has 2 subBodies but we need to deal with that
81      int subBodyNumber=0; 
82      while (sbit.hasNext()) {
83          Object   subBody = sbit.next();
84          Iterator it = ((List) subBody).iterator();
85  
86          int nodeNumber=0;
87          //go over the ASTNodes in this subBody and apply
88          while (it.hasNext()){
89          ASTNode temp = (ASTNode) it.next();
90  
91          if(temp instanceof ASTWhileNode || temp instanceof ASTUnconditionalLoopNode ||
92             temp instanceof ASTDoWhileNode){
93              
94              ASTNode oneNode=getOnlySubNode(temp);
95              if(oneNode !=null){
96              List newNode=null;
97              if(oneNode instanceof ASTIfNode){
98                  newNode=StrengthenByIf.getNewNode(temp,(ASTIfNode)oneNode);
99              }
100             else if (oneNode instanceof ASTIfElseNode){
101                 newNode=StrengthenByIfElse.getNewNode(temp,(ASTIfElseNode)oneNode);
102             }
103             
104             if(newNode!=null){
105                 //some pattern was matched
106                 //replace the temp node with the newNode
107                 replaceNode(node,subBodyNumber,nodeNumber,temp,newNode);
108                 UselessLabelFinder.v().findAndKill(node);
109             }
110             }
111         }
112         
113         temp.apply(this);
114         nodeNumber++;
115         }
116         subBodyNumber++;
117     }//end of going over subBodies
118     }
119 
120     public void caseASTTryNode(ASTTryNode node){
121     inASTTryNode(node);
122 
123     //get try body 
124     List tryBody = node.get_TryBody();
125     Iterator it = tryBody.iterator();
126 
127     int nodeNumber=0;
128     //go over the ASTNodes and apply
129     while (it.hasNext()){
130         ASTNode temp = (ASTNode) it.next();
131         if(temp instanceof ASTWhileNode || temp instanceof ASTUnconditionalLoopNode ||
132            temp instanceof ASTDoWhileNode){
133             
134         ASTNode oneNode=getOnlySubNode(temp);
135         if(oneNode !=null){
136             List newNode=null;
137             if(oneNode instanceof ASTIfNode){
138             newNode=StrengthenByIf.getNewNode(temp,(ASTIfNode)oneNode);
139             }
140             else if (oneNode instanceof ASTIfElseNode){
141             newNode=StrengthenByIfElse.getNewNode(temp,(ASTIfElseNode)oneNode);
142             }
143             
144             if(newNode!=null){
145             //some pattern was matched
146             //replace the temp node with the newNode
147 
148             List newBody=createNewSubBody(tryBody,nodeNumber,temp,newNode);
149             if(newBody!=null){
150                 //something did not go wrong
151                 node.replaceTryBody(newBody);
152                 G.v().ASTTransformations_modified = true;
153                 //System.out.println("strengthened loop within trybody");
154             }
155             UselessLabelFinder.v().findAndKill(node);
156             }
157         }
158         }//it was a loop node
159         temp.apply(this);
160         nodeNumber++;
161     }
162 
163 
164 
165 
166     Map exceptionMap = node.get_ExceptionMap();
167     Map paramMap = node.get_ParamMap();
168     //get catch list and apply on the following
169     // a, type of exception caught
170     // b, local of exception
171     // c, catchBody
172     List catchList = node.get_CatchList();
173     Iterator itBody=null;
174         it = catchList.iterator();
175     while (it.hasNext()) {
176         ASTTryNode.container catchBody = (ASTTryNode.container)it.next();
177         
178         SootClass sootClass = ((SootClass)exceptionMap.get(catchBody));
179         Type type = sootClass.getType();
180         
181         //apply on type of exception
182         caseType(type);
183 
184         //apply on local of exception
185         Local local = (Local)paramMap.get(catchBody);
186         decideCaseExprOrRef(local);
187 
188         //apply on catchBody
189         List body = (List)catchBody.o;
190         itBody = body.iterator();
191 
192         nodeNumber=0;
193         //go over the ASTNodes and apply
194         while (itBody.hasNext()){
195         ASTNode temp = (ASTNode) itBody.next();
196         if(temp instanceof ASTWhileNode || temp instanceof ASTUnconditionalLoopNode ||
197            temp instanceof ASTDoWhileNode){
198             
199             ASTNode oneNode=getOnlySubNode(temp);
200             if(oneNode !=null){
201             List newNode=null;
202             if(oneNode instanceof ASTIfNode){
203                 newNode=StrengthenByIf.getNewNode(temp,(ASTIfNode)oneNode);
204             }
205             else if (oneNode instanceof ASTIfElseNode){
206                 newNode=StrengthenByIfElse.getNewNode(temp,(ASTIfElseNode)oneNode);
207             }
208             
209             if(newNode!=null){
210                 //some pattern was matched
211                 //replace the temp node with the newNode
212                 
213                 List newBody=createNewSubBody(body,nodeNumber,temp,newNode);
214                 if(newBody!=null){
215                 //something did not go wrong
216                 catchBody.replaceBody(newBody);
217                 G.v().ASTTransformations_modified = true;
218                 //System.out.println("strengthened loop within catchbody");
219                 }
220                 UselessLabelFinder.v().findAndKill(node);
221             }
222             }
223         }//it was a loop node
224         temp.apply(this);
225         nodeNumber++;
226         }
227     }
228     
229     outASTTryNode(node);
230     }
231 
232 
233     private void dealWithSwitchNode(ASTSwitchNode node){
234     //do a depthfirst on elements of the switchNode
235 
236     List indexList = node.getIndexList();
237     Map index2BodyList = node.getIndex2BodyList();
238 
239     Iterator it = indexList.iterator();
240     while (it.hasNext()) {//going through all the cases of the switch statement
241         Object   currentIndex = it.next();
242         List body = (List) index2BodyList.get( currentIndex);
243         
244         if (body != null){
245         //this body is a list of ASTNodes 
246 
247         Iterator itBody = body.iterator();
248         int nodeNumber=0;
249         //go over the ASTNodes and apply
250         while (itBody.hasNext()){
251             ASTNode temp = (ASTNode) itBody.next();
252             if(temp instanceof ASTWhileNode || temp instanceof ASTUnconditionalLoopNode ||
253                temp instanceof ASTDoWhileNode){
254             
255             ASTNode oneNode=getOnlySubNode(temp);
256             if(oneNode !=null){
257                 List newNode=null;
258                 if(oneNode instanceof ASTIfNode){
259                 newNode=StrengthenByIf.getNewNode(temp,(ASTIfNode)oneNode);
260                 }
261                 else if (oneNode instanceof ASTIfElseNode){
262                 newNode=StrengthenByIfElse.getNewNode(temp,(ASTIfElseNode)oneNode);
263                 }
264                 
265                 if(newNode!=null){
266                 //some pattern was matched
267                 //replace the temp node with the newNode
268                 
269                 List newBody=createNewSubBody(body,nodeNumber,temp,newNode);
270                 if(newBody!=null){
271                     //something did not go wrong put this body in the Map
272                      index2BodyList.put(currentIndex,newBody);
273                     //replace in actual switchNode
274                     node.replaceIndex2BodyList(index2BodyList);
275                     G.v().ASTTransformations_modified = true;
276                     //System.out.println("strengthened loop within switch body");
277                 }
278                 UselessLabelFinder.v().findAndKill(node);
279                 }
280             }
281             }//it was a loop node
282             temp.apply(this);
283             nodeNumber++;
284         }
285         }
286     }
287     }
288 
289 
290 
291 
292 
293 
294     /*
295       Given an ASTNode as input this method checks the following:
296       1, The node is either ASTWhile, ASTDoWhile or ASTUnconditionalLoop
297       2, The node has one subBody
298       3, The onlySubBody has one node
299 
300       it returns the only node in the only SubBody
301     */
302     private ASTNode getOnlySubNode(ASTNode node){
303     if(!(node instanceof ASTWhileNode || node instanceof ASTDoWhileNode || 
304          node instanceof ASTUnconditionalLoopNode)){
305         //not one of these loops
306         return null;
307     }
308     List subBodies = node.get_SubBodies();
309     if(subBodies.size()!=1){
310         //we are coming from loop nodes so subBodies should always be one
311         return null;
312     }
313     List subBody = (List)subBodies.get(0);
314     if(subBody.size()!=1){
315         //only want the case which the subBody has a single node
316         return null;
317     }
318     return (ASTNode)subBody.get(0);
319     }
320 
321 
322 
323 
324 
325 
326 
327 
328 
329 
330 
331 
332 
333     /*
334       - Go through the node bodies till you find subBodyNumber 
335       - Go through this subBody until you find nodeNumber
336       - This is the temp node Replace it with the newNodes
337 
338       Node is the node which contains the loop node
339       subBodyNumber is the subBody which of the node which contains the loopNode
340       nodeNumber is the location of the loopNode in the subBody
341       newNode is the loopNode which will replace the old loopNode
342     */
343     private void replaceNode(ASTNode node,int subBodyNumber,int nodeNumber,ASTNode loopNode,List newNode){
344     if(!(node instanceof ASTIfElseNode)){
345         //these are the nodes which always have one subBody
346         List subBodies = node.get_SubBodies();
347         if(subBodies.size()!=1){
348         //there is something wrong
349         throw new RuntimeException  ("Please report this benchmark to the programmer");
350         }
351         List onlySubBody = (List)subBodies.get(0);
352 
353         /*
354           The onlySubBody contains the loopNode to be replaced 
355           at location given by the nodeNumber variable
356         */
357         List newBody = createNewSubBody(onlySubBody,nodeNumber,loopNode,newNode);
358         if(newBody==null){
359         //something went wrong
360         return;
361         }
362         if(node instanceof ASTMethodNode){
363         ((ASTMethodNode)node).replaceBody(newBody);
364         G.v().ASTTransformations_modified = true;
365         //System.out.println("Stenghtened Loop");
366         }
367         else if(node instanceof ASTSynchronizedBlockNode){
368         ((ASTSynchronizedBlockNode)node).replaceBody(newBody);
369         G.v().ASTTransformations_modified = true;
370         //System.out.println("Stenghtened Loop in synchblock");
371         }
372         else if(node instanceof ASTLabeledBlockNode){
373         ((ASTLabeledBlockNode)node).replaceBody(newBody);
374         G.v().ASTTransformations_modified = true;
375         //System.out.println("Stenghtened Loop in labeledblock node");
376         }
377         else if(node instanceof ASTUnconditionalLoopNode){
378         ((ASTUnconditionalLoopNode)node).replaceBody(newBody);
379         G.v().ASTTransformations_modified = true;
380         //System.out.println("Stenghtened Loop in unconditionalloopNode");
381         }
382         else if(node instanceof ASTIfNode){
383         ((ASTIfNode)node).replaceBody(newBody);
384         G.v().ASTTransformations_modified = true;
385         //System.out.println("Stenghtened Loop in ifnode");
386         }
387         else if(node instanceof ASTWhileNode){
388         ((ASTWhileNode)node).replaceBody(newBody);
389         G.v().ASTTransformations_modified = true;
390         //System.out.println("Stenghtened Loop in whilenode");
391         }
392         else if(node instanceof ASTDoWhileNode){
393         ((ASTDoWhileNode)node).replaceBody(newBody);
394         G.v().ASTTransformations_modified = true;
395         //System.out.println("Stenghtened Loop in dowhile node");
396         }
397         else {
398         //there is no other case something is wrong if we get here
399         return;
400         }
401     }
402     else{//its an ASTIfElseNode
403         //if its an ASIfElseNode then check which Subbody has the labeledBlock
404         if(subBodyNumber!=0 && subBodyNumber!=1){
405         //something bad is happening dont do nothin
406         //System.out.println("Error-------not modifying AST");
407         return;
408         }
409         List subBodies = node.get_SubBodies();
410         if(subBodies.size()!=2){
411         //there is something wrong
412         throw new RuntimeException  ("Please report this benchmark to the programmer");
413         }
414 
415         List toModifySubBody = (List)subBodies.get(subBodyNumber);
416 
417         /*
418           The toModifySubBody contains the labeledBlockNode to be removed
419           at location given by the nodeNumber variable
420         */
421         List newBody = createNewSubBody(toModifySubBody,nodeNumber,loopNode,newNode);
422         if(newBody==null){
423         //something went wrong
424         return;
425         }
426         if(subBodyNumber==0){
427         //the if body was modified
428         //System.out.println("Stenghtened Loop");
429         G.v().ASTTransformations_modified = true;
430         ((ASTIfElseNode)node).replaceBody(newBody,(List)subBodies.get(1));
431         }
432         else if(subBodyNumber==1){
433         //else body was modified
434         //System.out.println("Stenghtened Loop");
435         G.v().ASTTransformations_modified = true;
436         ((ASTIfElseNode)node).replaceBody((List)subBodies.get(0),newBody);
437         }
438         else{//realllly shouldnt come here
439         //something bad is happening dont do nothin
440         //System.out.println("Error-------not modifying AST");
441         return;
442         }
443 
444     }//end of ASTIfElseNode
445     }
446 
447 
448 
449 
450 
451 
452     
453     public static List createNewSubBody(List oldSubBody,int nodeNumber,ASTNode oldNode,List newNode){
454     //create a new SubBody
455     List newSubBody = new ArrayList();
456     
457     //this is an iterator of ASTNodes
458     Iterator it = oldSubBody.iterator();
459     
460     //copy to newSubBody all nodes until you get to nodeNumber
461     int index=0;
462     while(index!=nodeNumber ){
463         if(!it.hasNext()){
464         return null;
465         }
466         newSubBody.add(it.next());
467         index++;
468     }
469 
470     //at this point the iterator is pointing to the ASTNode to be removed
471     //just to make sure check this
472     ASTNode toRemove = (ASTNode)it.next();
473     if(toRemove.toString().compareTo(oldNode.toString())!=0){
474         System.out.println("The replace nodes dont match please report benchmark to developer");
475         return null;
476     }
477     else{
478         //not adding the oldNode into the newSubBody but adding its replacement
479         newSubBody.addAll(newNode);
480     }
481 
482     //add any remaining nodes in the oldSubBody to the new one
483     while(it.hasNext()){
484         newSubBody.add(it.next());
485     }
486 
487     //newSubBody is ready return it
488     return newSubBody;
489     }
490      
491 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags