KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > dava > toolkits > base > AST > transformations > OrAggregatorFour


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.jimple.*;
25 import soot.dava.internal.SET.*;
26 import soot.dava.internal.AST.*;
27 import soot.dava.internal.asg.*;
28 import soot.dava.internal.javaRep.*;
29 import soot.dava.toolkits.base.AST.analysis.*;
30
31
32 /*
33   Nomair A. Naeem 18-FEB-2005
34
35   The class is responsible to do the following transformation on the AST
36   
37   label_1:
38      while(cond){ label_1:
39          BodyA; while(cond){
40          label_2:{ BodyA;
41             if(cond1){ if(cond1 || ..... || !cond2){
42                 break label_2; BodyB
43             } }
44             //same as above }//end of while
45             .
46             . remove label_1 if BodyA and BodyB
47             if(cond2){ dont have any reference to label_1 (highly likely)
48                 continue label_1; ------> should be done as a separate analysis
49         }
50          }//end of label_2
51          BodyB
52   }//end while
53
54
55   This pattern is applicable to the four cycle nodes representing
56   while(true), while(cond) and dowhile(cond) for loops
57
58   TO MAKE CODE EFFECIENT BLOCK THE ANALYSIS TO GOING INTO STATEMENTS
59   this is done by overriding the caseASTStatementSequenceNode
60 */
61
62 public class OrAggregatorFour extends DepthFirstAdapter{
63
64     public OrAggregatorFour(){
65     }
66     public OrAggregatorFour(boolean verbose){
67     super(verbose);
68     }
69
70     public void caseASTStatementSequenceNode(ASTStatementSequenceNode node){
71     }
72
73
74
75
76     public void outASTForLoopNode(ASTForLoopNode node){
77     String JavaDoc label = node.get_Label().toString();
78     if(label==null)
79         return;
80     
81     List subBodies=node.get_SubBodies();
82     List newBody=matchPattern(label,subBodies);
83     if(newBody!=null){
84         node.replaceBody(newBody);
85         //System.out.println("OR AGGREGATOR FOUR");
86 G.v().ASTTransformations_modified = true;
87     }
88     
89     /*
90       see if we can remove the label from this construct
91     */
92     UselessLabelFinder.v().findAndKill(node);
93     }
94
95
96
97     public void outASTWhileNode(ASTWhileNode node){
98     String JavaDoc label = node.get_Label().toString();
99     if(label==null)
100         return;
101     
102     List subBodies=node.get_SubBodies();
103     List newBody=matchPattern(label,subBodies);
104     if(newBody!=null){
105         node.replaceBody(newBody);
106         //System.out.println("OR AGGREGATOR FOUR");
107 G.v().ASTTransformations_modified = true;
108     }
109     
110     /*
111       see if we can remove the label from this construct
112     */
113     UselessLabelFinder.v().findAndKill(node);
114     }
115
116     public void outASTDoWhileNode(ASTDoWhileNode node){
117     String JavaDoc label = node.get_Label().toString();
118     if(label==null)
119         return;
120
121     List subBodies=node.get_SubBodies();
122     List newBody=matchPattern(label,subBodies);
123     if(newBody!=null){
124         node.replaceBody(newBody);
125         //System.out.println("OR AGGREGATOR FOUR");
126 G.v().ASTTransformations_modified = true;
127     }
128     /*
129       see if we can remove the label from this construct
130     */
131     UselessLabelFinder.v().findAndKill(node);
132     }
133
134     public void outASTUnconditionalLoopNode(ASTUnconditionalLoopNode node){
135     String JavaDoc label = node.get_Label().toString();
136     if(label==null)
137         return;
138
139     List subBodies=node.get_SubBodies();
140     List newBody=matchPattern(label,subBodies);
141     if(newBody!=null){
142         node.replaceBody(newBody);
143         //System.out.println("OR AGGREGATOR FOUR");
144 G.v().ASTTransformations_modified = true;
145     }
146     /*
147       see if we can remove the label from this construct
148     */
149     UselessLabelFinder.v().findAndKill(node);
150     }
151
152     public List matchPattern(String JavaDoc whileLabel,List subBodies){
153     //since the subBodies are coming from a cycle node we know
154 //there is only one subBody
155 if(subBodies.size()!=1){
156         //size should be one
157 return null;
158     }
159
160     List subBody = (List)subBodies.get(0);
161     Iterator it = subBody.iterator();
162     int nodeNumber=0;
163     while(it.hasNext()){//going through the ASTNodes
164 //look for a labeledBlock
165 ASTNode temp = (ASTNode)it.next();
166         if(temp instanceof ASTLabeledBlockNode){
167         //see if the inner pattern matches
168 ASTLabeledBlockNode labeledNode = (ASTLabeledBlockNode)temp;
169         String JavaDoc innerLabel=labeledNode.get_Label().toString();
170         if(innerLabel==null){//label better not be null
171 nodeNumber++;
172             continue;
173         }
174         
175         //get labeledBlocksBodies
176 List labeledBlocksSubBodies = labeledNode.get_SubBodies();
177         if(labeledBlocksSubBodies.size()!=1){
178             //should always be one
179 nodeNumber++;
180             continue;
181         }
182
183         //get the subBody
184 List labeledBlocksSubBody = (List)labeledBlocksSubBodies.get(0);
185         
186         boolean allIfs = checkAllAreIfsWithProperBreaks(labeledBlocksSubBody.iterator(),whileLabel,innerLabel);
187         if(!allIfs){
188             //pattern doesnt match
189 nodeNumber++;
190             continue;
191         }
192
193         //the pattern has been matched do the transformation
194
195         //nodeNumber is the location of the ASTLabeledBlockNode
196 List whileBody = createWhileBody(subBody,labeledBlocksSubBody,nodeNumber);
197         if(whileBody!=null){
198             return whileBody;
199         }
200         }//if its an ASTLabeledBlockNode
201 nodeNumber++;
202     }//end of going through ASTNodes
203 return null;
204     }
205
206     private List createWhileBody(List subBody,List labeledBlocksSubBody,int nodeNumber){
207     //create BodyA, Nodes from 0 to nodeNumber
208 List bodyA = new ArrayList();
209     
210     //this is an iterator of ASTNodes
211 Iterator it = subBody.iterator();
212     
213     //copy to bodyA all nodes until you get to nodeNumber
214 int index=0;
215     while(index!=nodeNumber ){
216         if(!it.hasNext()){
217         return null;
218         }
219         bodyA.add(it.next());
220         index++;
221     }
222        
223     
224     //create ASTIfNode
225 // Create a list of conditions to be Ored together
226 // remembering that the last ones condition is to be flipped
227 List conditions = getConditions(labeledBlocksSubBody.iterator());
228
229     //create an aggregated condition
230 Iterator condIt = conditions.iterator();
231     ASTCondition newCond=null;;
232     while(condIt.hasNext()){
233         ASTCondition next = (ASTCondition)condIt.next();
234         if(newCond==null)
235         newCond=next;
236         else
237         newCond=new ASTOrCondition(newCond,next);
238     }
239
240     
241     //create BodyB
242 it.next();//this skips the LabeledBlockNode
243 List bodyB = new ArrayList();
244     while(it.hasNext()){
245         bodyB.add(it.next());
246     }
247     
248     ASTIfNode newNode = new ASTIfNode(new SETNodeLabel(),newCond,bodyB);
249
250
251     //add this node to the bodyA
252 bodyA.add(newNode);
253     return bodyA;
254     }
255
256     /*
257       The method will go through the iterator because of the sequence
258       of methods called before in the outASTLabeledBlockNode
259       it knows the following:
260        All nodes are ASTIFNodes
261     */
262     private List getConditions(Iterator it){
263     List toReturn = new ArrayList();
264     while(it.hasNext()){
265         //safe cast since we know these are all ASTIfNodes
266 ASTIfNode node = (ASTIfNode)it.next();
267         
268         ASTCondition cond = node.get_Condition();
269         //check if this is the last in which case we need to flip
270 if(it.hasNext()){
271         //no need to flip
272 toReturn.add(cond);
273         }
274         else{
275         //need to flip condition
276 //System.out.println("old:"+cond);
277 cond.flip();
278         //System.out.println("new"+cond);
279 toReturn.add(cond);
280         }
281     }//end of while
282 return toReturn;
283     }
284
285
286
287
288     private boolean checkAllAreIfsWithProperBreaks(Iterator it,String JavaDoc outerLabel, String JavaDoc innerLabel){
289     //the pattern says that ALL bodies in this list should be IF statements
290 while(it.hasNext()){
291         ASTNode secondLabelsBody = (ASTNode)it.next();
292         
293         //check that this is a ifNode with a single statement
294
295         Stmt stmt = isIfNodeWithOneStatement(secondLabelsBody);
296         if(stmt == null){
297         //pattern is broken
298 return false;
299         }
300     
301         //check if the single stmt follows the pattern
302 boolean abrupt = abruptLabel(stmt,outerLabel,innerLabel,it.hasNext());
303
304         if(!abrupt){
305         //stmt does not follow the pattern
306 return false;
307         }
308     }//end of while going through all the bodies of the secondlabel
309
310     //if we get here that means everything was according to the pattern
311 return true;
312     }
313
314
315
316
317
318
319
320
321     /*
322       If the stmt is a break stmt then see it breaks the inner label and thee boolean is true return true
323       If the stmt is a continue then see it continues the outer label and the boolean is false return true
324       else return false
325     */
326     private boolean abruptLabel(Stmt stmt, String JavaDoc outerLabel, String JavaDoc innerLabel, boolean hasNext){
327     if(!(stmt instanceof DAbruptStmt)){
328         //this is not a break/continue stmt
329 return false;
330     }
331     DAbruptStmt abStmt = (DAbruptStmt)stmt;
332     SETNodeLabel label = abStmt.getLabel();
333     String JavaDoc abruptLabel=label.toString();
334
335
336     if(abruptLabel==null)
337         return false;
338
339     if(abStmt.is_Break() && abruptLabel.compareTo(innerLabel)==0 && hasNext){
340         return true;
341     }
342     else if (abStmt.is_Continue() && abruptLabel.compareTo(outerLabel)==0 && !hasNext){
343         return true;
344     }
345     else
346         return false;
347     }
348
349
350
351
352
353
354
355
356
357
358
359
360     private Stmt isIfNodeWithOneStatement(ASTNode secondLabelsBody){
361     if(!(secondLabelsBody instanceof ASTIfNode)){
362         //pattern broken as this should be a IfNode
363 return null;
364     }
365     //check that the body of ASTIfNode has a single ASTStatementSequence
366
367     ASTIfNode ifNode =(ASTIfNode)secondLabelsBody;
368     List ifSubBodies =ifNode.get_SubBodies();
369     if(ifSubBodies.size()!=1){
370         //if body should always have oneSubBody
371 return null;
372     }
373     
374     //if has one SubBody
375 List ifBody = (List)ifSubBodies.get(0);
376     
377     //Looking for a statement sequence node with a single stmt
378 if(ifBody.size()!=1){
379         //there should only be one body
380 return null;
381     }
382
383     //The only subBody has one ASTNode
384 ASTNode ifBodysBody = (ASTNode)ifBody.get(0);
385     if(!(ifBodysBody instanceof ASTStatementSequenceNode)){
386         //had to be a STMTSEQ node
387 return null;
388     }
389
390     //the only ASTnode is a ASTStatementSequence
391 List statements = ((ASTStatementSequenceNode)ifBodysBody).getStatements();
392     if(statements.size()!=1){
393         //there is more than one statement
394 return null;
395     }
396
397     //there is only one statement return the statement
398 AugmentedStmt as = (AugmentedStmt)statements.get(0);
399     Stmt s = as.get_Stmt();
400     return s;
401     }
402
403 }
Popular Tags