ForLoopCreationHelper


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 java.util.*;
23  import soot.*;
24  import soot.jimple.*;
25  import soot.dava.*;
26  import soot.dava.internal.SET.*;
27  import soot.dava.internal.asg.*;
28  import soot.dava.internal.AST.*;
29  import soot.util.*;
30  
31  public class ForLoopCreationHelper{
32  
33      ASTStatementSequenceNode stmtSeqNode;
34      ASTWhileNode whileNode;
35  
36      ASTStatementSequenceNode newStmtSeqNode;
37      ASTForLoopNode forNode;
38  
39      Map varToStmtMap;
40  
41      /*
42       * Bug Reported by Steffen Pingel on the soot mailing list (january 2006)
43       * Fixed by Nomair February 6th, 2006
44       *
45       * There was a bug in the getUpdate method since it removed the update statement whenver it found one
46       * Later on if the ForLoop Creation terminated the update stmt had been removed
47       * We delay the removal of the update stmt until we are sure that the for loop is being created
48       * This is done by storing the list of stmts from which to remove the update statement in the following
49       * field. The boolean (although redundant) indicates when such an update stmt should be removed
50       */
51      List myStmts;//stores the statementseq list of statements whose last stmt has to be removed
52      boolean removeLast=false;//the last stmt in the above stmts is removed if this boolean is true
53  
54      
55  
56      public ForLoopCreationHelper(ASTStatementSequenceNode stmtSeqNode, ASTWhileNode whileNode){
57      this.stmtSeqNode=stmtSeqNode;
58      this.whileNode=whileNode;
59      varToStmtMap = new HashMap();
60      }
61  
62  
63      /*
64        The purpose of this method is to replace the statement sequence node
65        given by the var nodeNumber with the new statement sequence node
66        and to replace the next node (which sould be a while node
67        with the for loop node
68  
69        The new body is then returned;
70  
71      */
72      public List createNewBody(List oldSubBody, int nodeNumber){
73      List newSubBody = new ArrayList();
74  
75      if(oldSubBody.size()<= nodeNumber){
76          //something is wrong since the oldSubBody has lesser nodes than nodeNumber
77          return null;
78      }
79  
80      Iterator oldIt = oldSubBody.iterator();
81      int index=0;
82      while(index!=nodeNumber){
83          newSubBody.add(oldIt.next());
84          index++;
85      }
86  
87      //check to see that the next is a stmtseq and the one afteris while node
88      ASTNode temp = (ASTNode)oldIt.next();
89      if(!(temp instanceof ASTStatementSequenceNode))
90          return null;
91      temp = (ASTNode)oldIt.next();
92      if(!(temp instanceof ASTWhileNode))
93          return null;
94      
95      //add new stmtseqnode to the newSubBody
96      if(newStmtSeqNode!=null){
97          newSubBody.add(newStmtSeqNode);
98      }
99      else{
100         //System.out.println("Stmt seq was empty hence not putting a node in");
101     }
102 
103     //add new For Loop Node
104     newSubBody.add(forNode);
105 
106 
107     //copy any remaining nodes
108     while(oldIt.hasNext()){
109         newSubBody.add(oldIt.next());
110     }
111     
112     return newSubBody;
113     }
114 
115 
116 
117     /*
118       Go through the stmtseq node
119       and collect all defs
120 
121       Important: if a def is followed by a non def stmt
122       clear def list and continue 
123 
124       i.e. we are conservatively checking when a def can be 
125       moved into a for loop body
126     */
127     private List getDefs(){
128     if(stmtSeqNode==null){
129         return null;
130     }
131     
132     List toReturn= new ArrayList();
133 
134     List statements = stmtSeqNode.getStatements();
135     Iterator stmtIt = statements.iterator();
136     int stmtNum=0;
137     while(stmtIt.hasNext()){
138         AugmentedStmt as = (AugmentedStmt)stmtIt.next();
139         Stmt s = as.get_Stmt();
140         
141         //check if this is a def
142         if(s instanceof DefinitionStmt){
143         Value left = ((DefinitionStmt)s).getLeftOp();
144         toReturn.add(left.toString());
145         varToStmtMap.put(left.toString(),new Integer  (stmtNum));
146         }
147         else{
148         toReturn = new ArrayList();
149         varToStmtMap = new HashMap();
150         }
151         stmtNum++;
152     }//going through all statements
153     return toReturn;
154     }
155 
156     /*
157       Go through the ASTCondition of the whileNode
158       Make a list of all vars being uses in the conditions
159       Since any of them could be being used to drive the loop
160     */
161     private List getCondUses(){
162     if(whileNode == null){
163         return null;
164     }
165     ASTCondition cond = whileNode.get_Condition();
166 
167     return getCond(cond);
168     }
169 
170     private List getCond(ASTCondition cond){
171     List toReturn=new ArrayList();
172     
173     if(cond instanceof ASTUnaryCondition){
174         toReturn.add(((ASTUnaryCondition)cond).toString());
175     }
176     else if (cond instanceof ASTBinaryCondition){
177         ConditionExpr condExpr = ((ASTBinaryCondition)cond).getConditionExpr();
178         toReturn.add(condExpr.getOp1().toString());
179         toReturn.add(condExpr.getOp2().toString());
180     }
181     else if (cond instanceof ASTAggregatedCondition){
182         toReturn.addAll(getCond(((ASTAggregatedCondition)cond).getLeftOp()));
183         toReturn.addAll(getCond(((ASTAggregatedCondition)cond).getRightOp()));
184     }
185     return toReturn;
186 
187     }
188 
189 
190 
191     private List getCommonVars(List defs, List condUses){
192 
193     List toReturn = new ArrayList();
194     Iterator defIt = defs.iterator();
195 
196     while(defIt.hasNext()){
197         String   defString = (String  )defIt.next();
198         Iterator condIt = condUses.iterator();
199         while(condIt.hasNext()){
200         String   condString = (String  )condIt.next();
201         
202         if(condString.compareTo(defString)==0){
203             //match
204             toReturn.add(defString);
205             break;
206         }
207         }
208     }
209 
210     return toReturn;
211     }
212 
213 
214     /*
215       Given the StmtSequenceNode and the while Node
216       Check if the while can be converted to a for
217       
218       If this can be done. create the replacement stmt sequence node
219       and the new for loop and return TRUE;
220 
221       else return FALSE;
222     */
223     public boolean checkPattern(){
224     List defs = getDefs();
225     if(defs==null){
226         return false;
227     }
228     if(defs.size()==0){
229         return false;
230     }
231 
232     List condUses = getCondUses();
233     if(condUses==null){
234         return false;
235     }
236     if(condUses.size()==0){
237         return false;
238     }
239 
240     /*
241       find common vars between the defs and the condition
242     */
243     List commonVars = getCommonVars(defs,condUses);
244 
245     /*
246       Find the update list
247       Also at the same time see if the update list has
248       some update stmt whose var should be added to commonVars
249     */
250 
251     List update = getUpdate(defs,condUses,commonVars);
252     if(update==null  || update.size() == 0){
253         //System.out.println("Aborting because of update");
254         return false;
255     }
256 
257     if(commonVars==null || commonVars.size()==0){
258         //System.out.println("Aborting because of commonVars");
259         return false;
260     }
261     
262     //there are some vars which are 
263     //1, defined in the stmtseq node
264     //2, used in the condition
265     //System.out.println(commonVars);
266 
267 
268 
269     //create new stmtSeqNode and get the init list for the for loop
270     List init= createNewStmtSeqNodeAndGetInit(commonVars);
271     if(init.size()==0){
272         //System.out.println("Aborting because of init size");
273         return false;
274     }
275 
276 
277 
278     ASTCondition condition = whileNode.get_Condition();
279     List body = (List)whileNode.get_SubBodies().get(0);
280     SETNodeLabel label = ((ASTLabeledNode)whileNode).get_Label();
281 
282 
283 
284     /*
285       Check that anything in init is not a first time initialization
286       if it is and it is not used outside the for loop then 
287       we need to declare it as int i = bla bla instead of i = bla bla
288     */
289     //init=analyzeInit(init);
290     
291     //about to create loop make sure to remove the update stmt
292     if(removeLast){
293         //System.out.println("Removing"+myStmts.get(myStmts.size()-1));
294         myStmts.remove(myStmts.size()-1);
295         removeLast=false;
296     }
297 
298     forNode = new ASTForLoopNode(label,init,condition,update,body);
299     return true;
300     }
301 
302 
303 
304 
305     private List getUpdate(List defs,List condUses, List commonUses){
306     List toReturn = new ArrayList();
307 
308     //most naive approach
309     List subBodies = whileNode.get_SubBodies();
310     if(subBodies.size()!=1){
311         //whileNode should always have oneSubBody
312         return toReturn;
313     }
314 
315     List subBody = (List)subBodies.get(0);
316     Iterator it = subBody.iterator();
317     while(it.hasNext()){
318         ASTNode temp = (ASTNode)it.next();
319 
320         if(it.hasNext()){
321         //not the last node in the loop body
322         continue;
323         }
324 
325         //this is the last node in the loop body
326 
327         if(!(temp instanceof ASTStatementSequenceNode)){
328         //not a statementsequence node
329         //System.out.println("Aborting because last node is not a stmtseqnode");
330         return null;
331         }
332 
333         List stmts = ((ASTStatementSequenceNode)temp).getStatements();
334         AugmentedStmt last = (AugmentedStmt)stmts.get(stmts.size()-1);
335         Stmt lastStmt = last.get_Stmt();
336 
337         if(!(lastStmt instanceof DefinitionStmt)){
338         //not a definition stmt
339         //System.out.println("Aborting because last stmt is not definition stmt");
340         return null;
341         }
342 
343 
344 
345 
346         //check if it assigns to a def
347         Value left = ((DefinitionStmt)lastStmt).getLeftOp();
348         Iterator defIt = defs.iterator();
349         while(defIt.hasNext()){
350         String   defString = (String  )defIt.next();
351         if(left.toString().compareTo(defString)==0){
352             //match
353             toReturn.add(last);
354 
355             myStmts=stmts;
356             removeLast=true;
357             //stmts.remove(stmts.size()-1);
358             
359             //see if commonUses has this otherwise add it
360             Iterator coIt = commonUses.iterator();
361             boolean matched=false;
362             while(coIt.hasNext()){
363             if (defString.compareTo((String  )coIt.next())==0){
364                 matched=true;
365             }
366             }
367             if(!matched){
368             //it is not in commonUses
369             commonUses.add(defString);
370             }
371             
372             return toReturn;
373         }
374         }
375 
376         //the code gets here only in the case when none of the def strings matched the updated variable
377         Iterator condIt = condUses.iterator();
378         while(condIt.hasNext()){
379         String   condString = (String  )condIt.next();
380         if(left.toString().compareTo(condString)==0){
381             //match
382             toReturn.add(last);
383 
384             myStmts=stmts;
385             removeLast=true;            
386             //stmts.remove(stmts.size()-1);
387             
388             //see if commonUses has this otherwise add it
389             Iterator coIt = commonUses.iterator();
390             boolean matched=false;
391             while(coIt.hasNext()){
392             if (condString.compareTo((String  )coIt.next())==0){
393                 matched=true;
394             }
395             }
396             if(!matched){
397             //it is not in commonUses
398             commonUses.add(condString);
399             }
400             return toReturn;
401         }
402         }
403     }//going through ASTNodes
404     
405     return toReturn;
406     }
407 
408 
409     private List createNewStmtSeqNodeAndGetInit(List commonVars){
410     //get stmt number of each def of commonVar keeping the lowest
411     int currentLowestPosition=999;
412     Iterator it = commonVars.iterator();
413     while(it.hasNext()){
414         String   temp = (String  )it.next();
415         Integer   tempInt = (Integer  )varToStmtMap.get(temp);
416         if(tempInt !=null){
417         if(tempInt.intValue()<currentLowestPosition){
418             currentLowestPosition=tempInt.intValue();
419         }
420         }
421     }
422 
423     List stmts = new ArrayList();
424     
425     
426     List statements = stmtSeqNode.getStatements();
427     Iterator stmtIt = statements.iterator();
428     int stmtNum=0;
429 
430     while(stmtNum<currentLowestPosition   && stmtIt.hasNext()){
431         stmts.add(stmtIt.next());
432         stmtNum++;
433     }
434 
435     if(stmts.size()>0){
436         newStmtSeqNode = new ASTStatementSequenceNode(stmts);
437     }
438     else{
439         newStmtSeqNode = null;
440     }
441 
442 
443     List init = new ArrayList();
444     while(stmtIt.hasNext()){
445         init.add(stmtIt.next());
446     }
447     
448     return init;
449     }
450 
451 
452 
453     /*    private List analyzeInit(List init){
454     Iterator it = init.iterator();
455     while(it.hasNext()){
456         AugmentedStmt as = (AugmentedStmt)it.next();
457         Stmt s = as.get_Stmt();
458         if(!(s instanceof DefinitionStmt)){
459         //there is something wrong so dont do anything fancy
460         return init; 
461         }
462         else{
463         //get the local being initialized
464         Value left = ((DefinitionStmt)s).getLeftOp();
465 
466         }
467     }
468     return init;
469     }
470     */
471 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags