LoadStoreOptimizer


1   /* Soot - a J*va Optimization Framework
2    * Copyright (C) 1999 Patrice Pominville
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  /*
21   * Modified by the Sable Research Group and others 1997-1999.  
22   * See the 'credits' file distributed with Soot for the complete list of
23   * contributors.  (Soot is distributed at http://www.sable.mcgill.ca/soot)
24   */
25  
26  
27  package soot.baf.toolkits.base;
28  import soot.options.*;
29  
30  import soot.util.*;
31  import java.util.*;
32  import soot.*;
33  import soot.baf.*;
34  import soot.toolkits.scalar.*;
35  import soot.toolkits.graph.*;
36  import soot.baf.internal.*;
37  
38  public class LoadStoreOptimizer extends BodyTransformer
39  {
40      public LoadStoreOptimizer( Singletons.Global g ) {}
41      public static LoadStoreOptimizer v() { return G.v().soot_baf_toolkits_base_LoadStoreOptimizer(); }
42  
43      // Constants
44      boolean debug = false;
45      
46      // constants returned by the stackIndependent function.
47      final static private int FAILURE = 0;
48      final static private int SUCCESS = 1;
49      final static private int MAKE_DUP = 2;
50      final static private int MAKE_DUP1_X1 = 3;
51      final static private int SPECIAL_SUCCESS = 4;
52      final static private int HAS_CHANGED = 5;
53      final static private int SPECIAL_SUCCESS2 = 6;
54  
55      final static private int STORE_LOAD_ELIMINATION = 0;
56      final static private int STORE_LOAD_LOAD_ELIMINATION = -1;
57  
58          
59      private Map gOptions;
60  
61      /** The method that drives the optimizations. */
62      /* This is the public interface to LoadStoreOptimizer */
63    
64      protected void internalTransform(Body body, String   phaseName, Map options) 
65      {   
66  
67          gOptions = options;
68  
69          Instance instance = new Instance();
70          instance.mBody = body;        
71          instance.mUnits =  body.getUnits();
72          
73          debug = PhaseOptions.getBoolean(gOptions, "debug");
74          
75          if(Options.v().verbose())
76              G.v().out.println("[" + body.getMethod().getName() + "] Performing LoadStore optimizations...");
77  
78          if(debug) { G.v().out.println("\n\nOptimizing Method: " + body.getMethod().getName());}
79          
80          instance.go();
81      }
82  class Instance {
83      // Instance vars.
84      private Chain mUnits;
85      private Body mBody;
86      private ExceptionalUnitGraph mExceptionalUnitGraph;
87      private LocalDefs mLocalDefs;
88      private LocalUses mLocalUses;
89      private Map mUnitToBlockMap;     // maps a unit it's containing block
90      private boolean mPass2 = false;
91  
92  
93      void go() {
94          if(!mUnits.isEmpty()) {                    
95              buildUnitToBlockMap();
96              computeLocalDefsAndLocalUsesInfo();  
97             
98              
99             
100             if(debug){G.v().out.println("Calling optimizeLoadStore(1)\n");}
101             optimizeLoadStores(); 
102         
103             if(PhaseOptions.getBoolean(gOptions, "inter") ) {
104                 if(debug){G.v().out.println("Calling doInterBlockOptimizations");}
105                 doInterBlockOptimizations(); 
106                              
107                 //computeLocalDefsAndLocalUsesInfo();          
108                 //propagateLoadsBackwards();         if(debug)     G.v().out.println("pass 3");         
109                 //optimizeLoadStores();      if(debug)   G.v().out.println("pass 4"); 
110                 //propagateLoadsForward();   if(debug)   G.v().out.println("pass 5"); 
111                 //propagateBackwardsIndependentHunk(); if(debug)  G.v().out.println("pass 6");                        
112             }
113 
114             if(PhaseOptions.getBoolean(gOptions, "sl2") || PhaseOptions.getBoolean(gOptions, "sll2")  ) {        
115                 mPass2 = true;
116                 if(debug){G.v().out.println("Calling optimizeLoadStore(2)");}
117                 optimizeLoadStores();   
118             }
119         }        
120     }
121     /*
122      *  Computes a map binding each unit in a method to the unique basic block    
123      *  that contains it.
124      */    
125     private  void buildUnitToBlockMap()
126     {
127         BlockGraph blockGraph = new ZonedBlockGraph(mBody); 
128         if(debug) {
129             G.v().out.println("Method " +  mBody.getMethod().getName()+ " Block Graph: ");
130             G.v().out.println(blockGraph);
131         }
132        
133         List blocks = blockGraph.getBlocks();
134         mUnitToBlockMap = new HashMap();
135         
136         Iterator blockIt = blocks.iterator();
137         while(blockIt.hasNext() ) {
138             Block block = (Block) blockIt.next();
139             
140             Iterator unitIt = block.iterator();
141             while(unitIt.hasNext()) {
142                 Unit unit = (Unit) unitIt.next();                
143                 mUnitToBlockMap.put(unit, block);                
144             }
145         }
146     }
147 
148     
149     // computes a list of all the stores in mUnits in order of their occurence therein.
150   
151     private  List  buildStoreList()
152     {
153         Iterator it = mUnits.iterator();
154         List storeList = new ArrayList();
155         
156         while(it.hasNext()) {
157             Unit unit = (Unit) it.next();
158             if(unit  instanceof StoreInst)
159                 storeList.add(unit);
160         }     
161         return storeList;
162     }
163     
164 
165     
166     private void computeLocalDefsAndLocalUsesInfo() 
167     {        
168         mExceptionalUnitGraph =  new ExceptionalUnitGraph(mBody);
169         mLocalDefs = new SmartLocalDefs(mExceptionalUnitGraph, new SimpleLiveLocals(mExceptionalUnitGraph));
170         mLocalUses = new SimpleLocalUses(mExceptionalUnitGraph, mLocalDefs);
171     }
172    
173 
174     
175 
176 
177     // main optimizing method
178     private void optimizeLoadStores() 
179     {
180         //if(mBody.getMethod().getName().equals("aM")) {
181         Chain units  = mUnits;
182         List storeList;
183         
184         
185         // build a list of all store units in mUnits
186         storeList = buildStoreList();        
187         
188 
189         // Eliminate store/load  
190         {
191             
192             boolean hasChanged = true;
193         
194             boolean hasChangedFlag = false;
195             while(hasChanged) {
196         
197                 hasChanged = false;
198 
199 
200                 // Iterate over the storeList 
201                 Iterator unitIt = storeList.iterator();
202                 
203             nextUnit:
204                 while(unitIt.hasNext()){
205                     Unit unit = (Unit) unitIt.next();                
206                     List uses = mLocalUses.getUsesOf(unit);
207                   
208 
209                     // if uses of a store < 3, attempt some form of store/load elimination
210                     if(uses.size() < 3) {
211                         
212                         // check that all uses have only the current store as their definition
213                         {
214                             boolean invalidStore = false;
215                             Iterator useIt = uses.iterator();
216                             while(useIt.hasNext()) {
217                                 UnitValueBoxPair pair = (UnitValueBoxPair) useIt.next();
218                                 Unit loadUnit = pair.getUnit();
219                                 if(!(loadUnit instanceof LoadInst))
220                                     continue nextUnit;
221                             
222                                 List defs = mLocalDefs.getDefsOfAt((Local) pair.getValueBox().getValue(), loadUnit);
223                                 if(defs.size() > 1) {
224                                     continue nextUnit;
225                                 }
226                                 else if(defs.get(0) != unit) {
227                                     continue nextUnit; // xxx how can you get here?
228                                 }
229                             }
230                         } 
231                         
232                         // Check that all loads are in the same bb as the store
233                         {
234                             Block storeBlock = (Block) mUnitToBlockMap.get(unit);
235 
236                             Iterator useIt = uses.iterator();
237                             while(useIt.hasNext()) {
238                                 UnitValueBoxPair pair = (UnitValueBoxPair) useIt.next();
239                                 Block useBlock = (Block) mUnitToBlockMap.get(pair.getUnit());
240                                 if(useBlock != storeBlock) 
241                                     continue nextUnit;
242                             }                            
243                         }
244                         
245                         // Check for stack independance (automatic reordering may be performed by stackIndependent() fcnt)
246                         {
247                             Block block;
248                             switch(uses.size()) {
249                             case 0:        /*
250                                 if(Options.getBoolean(gOptions, "s-elimination")) {
251                                 // replace store by a pop and remove store from store list
252                                 replaceUnit(unit, Baf.v().newPopInst(((StoreInst)unit).getOpType()));
253                                 unitIt.remove();
254                                     
255                                 hasChanged = true;        hasChangedFlag = false;
256                                 }*/
257                                 break;
258                                     
259                             case 1:
260                                 if(PhaseOptions.getBoolean(gOptions, "sl")) {
261                                     if(!mPass2 || PhaseOptions.getBoolean(gOptions, "sl2")) {
262                                 // try to eliminate store/load pair
263                                         Unit loadUnit = ((UnitValueBoxPair)uses.get(0)).getUnit();
264                                         block =  (Block) mUnitToBlockMap.get(unit);
265                                         int test = stackIndependent(unit, loadUnit , block, STORE_LOAD_ELIMINATION);
266                                 
267                                 //xxx 
268                                 //if(block.getIndexInMethod() < 1 ) { // <13
269                                         if(test == SUCCESS || test == SPECIAL_SUCCESS){
270                                     
271                                             block.remove(unit);
272                                             block.remove(loadUnit);
273                                             unitIt.remove();
274                                             hasChanged = true;        hasChangedFlag = false;
275                                     
276                                             //delme[
277                                             if(debug) { G.v().out.println("Store/Load elimination occurred case1.");}
278                                             //delme]
279                                         } /*else if (test == SPECIAL_SUCCESS2) {
280                                             if(!hasChangedFlag) {
281                                             hasChangedFlag = true;
282                                             hasChanged = true;
283                                             } 
284                                             }*/
285                                     }
286                                 }
287                                 break;
288                                 
289                             case 2:
290                                 if(PhaseOptions.getBoolean(gOptions, "sll")) {
291                                     if(!mPass2 || PhaseOptions.getBoolean(gOptions, "sll2")) {
292                                 // try to replace store/load/load trio by a flavor of the dup unit
293                                         Unit firstLoad = ((UnitValueBoxPair)uses.get(0)).getUnit();
294                                         Unit secondLoad = ((UnitValueBoxPair)uses.get(1)).getUnit();
295                                         block = (Block) mUnitToBlockMap.get(unit);
296 
297 
298                                 
299                                         Unit temp;  // xxx try to optimize this
300                                         if(mUnits.follows(firstLoad, secondLoad)) {
301                                             temp = secondLoad;
302                                             secondLoad = firstLoad;
303                                             firstLoad = temp;
304                                         }
305 
306                                         int result = stackIndependent(unit, firstLoad, block, STORE_LOAD_ELIMINATION);                                 
307                                         if(result == SUCCESS){        
308                                   
309                                             // move the first load just after its defining store.
310                                             block.remove(firstLoad);
311                                             block.insertAfter(firstLoad, unit);                                
312                                     
313                                  
314                                             int res = stackIndependent(unit, secondLoad, block, STORE_LOAD_LOAD_ELIMINATION);
315                                             if(res == MAKE_DUP) {                                        
316                                                 // replace store by dup, drop both loads
317                                                 Dup1Inst dup = Baf.v().newDup1Inst(((LoadInst) secondLoad).getOpType());
318                                                 dup.addAllTagsOf(unit);
319                                                 replaceUnit(unit, dup);
320                                                 unitIt.remove(); // remove store from store list
321                                         
322                                                 block.remove(firstLoad); 
323                                                 block.remove(secondLoad);
324 
325                                                 hasChanged = true;         hasChangedFlag = false;
326                                         
327                                             }  /* else if(res == MAKE_DUP1_X1) {
328                                           
329                                                   // replace store/load/load by a dup1_x1
330                                                   Unit stackUnit = getStackItemAt2(unit, block, -2); 
331                                         
332                                                   if(stackUnit instanceof PushInst)
333                                                   break;
334                                         
335                                                   Type underType = type(stackUnit);
336                                                   if(underType == null) {                                         
337                                                   throw new RuntimeException("this has to be corrected (loadstoroptimiser.java)" + stackUnit);
338                                                   }
339                                         
340                                                   if(debug) { G.v().out.println("stack unit is: " + stackUnit + " stack type is " + underType);}
341                                                   replaceUnit(unit, Baf.v().newDup1_x1Inst(((LoadInst) secondLoad).getOpType(),underType));
342                                                   unitIt.remove();                
343                                         
344                                                   block.remove(firstLoad); 
345                                                   block.remove(secondLoad);
346                                         
347                                                   hasChanged = true;          hasChangedFlag = false;                                      
348                                                   break;                                        
349                                         
350                                                   } */
351                                     
352                                 
353                                         } else if(result == SPECIAL_SUCCESS || result == HAS_CHANGED || result == SPECIAL_SUCCESS2){
354                                             if(!hasChangedFlag) {
355                                                 hasChangedFlag = true;
356                                                 hasChanged = true;
357                                             } 
358                                         }
359                                     }
360                                     
361                                 }
362                             }                   
363                         }
364                     }
365                 }
366             }
367         }                    
368     }
369   
370     
371     
372     
373        
374     /** 
375      *  Checks if the units occuring between [from, to] consume 
376      *. stack items not produced by these interval units. (ie if the
377      *  stack height ever goes negative between from and to, assuming the 
378      *  stack height is set to 0 upon executing the instruction following 'from'.
379      *  
380      */
381     private boolean isRequiredByFollowingUnits(Unit from, Unit to)
382     {
383         Iterator it = mUnits.iterator(from, to);
384         int stackHeight = 0;
385         boolean res = false;
386         
387         if(from != to)  {
388             // advance past the 'from' unit
389             it.next();
390             while(it.hasNext()) {
391                 Unit  currentInst = (Unit) it.next();
392                 if(currentInst == to)                     
393                     break;
394 
395                 stackHeight -= ((Inst)currentInst).getInCount();
396                 if(stackHeight < 0 ) {
397                     res = true;
398                     break;
399                 }
400                 stackHeight += ((Inst)currentInst).getOutCount();
401             }
402         }
403         return res;
404     }
405             
406 
407     
408     
409     
410     private int pushStoreToLoad(Unit from , Unit to, Block block)
411     {
412         Unit storePred =  (Unit) block.getPredOf(from);
413         if(storePred != null) {
414             if(((Inst)storePred).getOutCount() == 1){
415                 Set unitsToMove = new HashSet();
416                 unitsToMove.add(storePred);
417                 unitsToMove.add(from);
418                 int h = ((Inst)storePred).getInCount();
419                 Unit currentUnit = storePred;
420                 if(h != 0) {           
421                     currentUnit = (Unit)block.getPredOf(storePred);
422                     while(currentUnit != null) {
423                         
424                         h-= ((Inst)currentUnit).getOutCount();
425                         if(h<0){ // xxx could be more flexible here?
426                             if(debug) { G.v().out.println("xxx: negative");}
427                             return FAILURE;
428                         }
429                         h+= ((Inst)currentUnit).getInCount();
430                         unitsToMove.add(currentUnit);
431                         if(h == 0)
432                             break;
433                         currentUnit  = (Unit) block.getPredOf(currentUnit);
434                     }
435                 }
436                 if(currentUnit == null) {
437                     if(debug) { G.v().out.println("xxx: null");}
438                     return FAILURE;        
439                 }
440                 
441                 Unit uu = from;
442                 for(;;) {
443                     uu = (Unit) block.getSuccOf(uu);
444                     if(uu == to)
445                         break;
446                     Iterator it2 = unitsToMove.iterator();
447                     while(it2.hasNext()) {
448                         Unit nu = (Unit) it2.next();
449                         if(debug) { G.v().out.println("xxxspecial;success pushing forward stuff.");}
450                         
451                         
452                         if(!canMoveUnitOver(nu, uu)){
453                             if(debug) { G.v().out.println("xxx: cant move over faillure" + nu);}
454                             return FAILURE;
455                         }
456                         if(debug) { G.v().out.println("can move" + nu + " over " + uu);}
457                     }
458                 }        
459                 
460                 // if we get here it means we can move all the units in the set pass the units in between [to, from]
461                 Unit unitToMove = currentUnit; 
462                 while(unitToMove != from) {        
463                     Unit succ = (Unit) block.getSuccOf(unitToMove);
464                     if(debug) { G.v().out.println("moving " + unitToMove);}
465                     block.remove(unitToMove);
466                     block.insertBefore(unitToMove, to);                            
467                     unitToMove = succ;
468                 }
469                 block.remove(from);
470                 block.insertBefore(from, to);
471                                
472                 if(debug) { G.v().out.println("xxx1success pushing forward stuff.");}
473                 return SPECIAL_SUCCESS;
474             }
475         }
476 
477         return FAILURE;
478     }
479     
480                 
481                 
482    
483     /**
484      *
485      *
486      * @return FAILURE when store load elimination is not possible in any form.
487      * @return SUCCESS when a load in a store load pair can be moved IMMEDIATELY after it's defining store
488      * @return MAKE_DUP when a store/load/load trio can be replaced by a dup unit.
489      * @return MAKE_DUP_X1 when store/load/load trio can be replaced by a dup1_x1 unit
490      * @return SPECIAL_SUCCESS when a store/load pair can AND must be immediately annihilated. 
491      * @return HAS_CHANGED when store load elimination is not possible in any form, but some unit reordering has occured
492      */
493     
494     private  int stackIndependent(Unit from, Unit to, Block block, int aContext) 
495     {                
496         if(debug) { 
497             G.v().out.println("Trying: " + from + "/" + to +  " in block  " + block.getIndexInMethod()+":" );
498             G.v().out.println("context:" + (aContext == STORE_LOAD_ELIMINATION ? 
499                                              "STORE_LOAD_ELIMINATION" :
500                                              "STORE_LOAD_LOAD_ELIMINATION"));
501         }
502 
503 
504         int minStackHeightAttained = 0; // records the min stack height attained between [from, to]
505         int stackHeight = 0;           // records the stack height when similating the effects on the stack
506         Iterator it = mUnits.iterator(mUnits.getSuccOf(from)); 
507         int res = FAILURE;
508         
509         Unit currentInst = (Unit) it.next();   // get unit following the store
510         
511         if(aContext == STORE_LOAD_LOAD_ELIMINATION) {
512             currentInst =  (Unit) it.next(); // jump after first load 
513         } 
514         
515         // find minStackHeightAttained
516         while(currentInst != to) {
517             stackHeight -= ((Inst)currentInst).getInCount();
518             if(stackHeight < minStackHeightAttained)
519                 minStackHeightAttained = stackHeight;
520             
521             
522             stackHeight += ((Inst)currentInst).getOutCount();                
523             
524             currentInst = (Unit) it.next();
525         }
526                 
527         // note: now stackHeight contains the delta height of the stack after executing the units contained in
528         // [from, to] non-inclusive.
529         
530         
531         if(debug) { 
532             G.v().out.println("nshv = " + stackHeight);
533             G.v().out.println("mshv = " + minStackHeightAttained);
534         }
535         
536         
537         boolean hasChanged = true;        
538         
539         // Iterate until an elimination clause is taken or no reordering of the code occurs         
540         while(hasChanged) {
541             hasChanged = false;
542 
543             // check for possible sll elimination
544             if(aContext == STORE_LOAD_LOAD_ELIMINATION) {
545                                 
546                 if(stackHeight == 0 && minStackHeightAttained == 0){
547                     if(debug) { 
548                         G.v().out.println("xxx: succ: -1, makedup ");
549                     }
550                     return MAKE_DUP;
551                 }
552                 else if(stackHeight == -1 && minStackHeightAttained == -1){
553                     if(debug) { G.v().out.println("xxx: succ: -1, makedup , -1");}        
554                     return MAKE_DUP;
555                  }
556                 else if(stackHeight == -2 && minStackHeightAttained == -2){if(debug) { G.v().out.println("xxx: succ -1 , make dupx1 ");}
557                 return MAKE_DUP1_X1; }
558                 
559                 else  if (minStackHeightAttained < -2) {
560                     if(debug) { G.v().out.println("xxx: failled due: minStackHeightAttained < -2 ");}
561                     return FAILURE;
562                 }                
563             }
564             
565             
566             // check for possible sl elimination
567             if(aContext == STORE_LOAD_ELIMINATION) {                
568                 if(stackHeight == 0 && minStackHeightAttained == 0){
569                     if(debug) { G.v().out.println("xxx: success due: 0, SUCCESS ");}
570                     return SUCCESS;
571                 }
572                 /* xxx broken data depensie problem.
573           else if (minStackHeightAttained == -1 && stackHeight == -1) { // try to make it more generic
574                     Unit u = (Unit) block.getPredOf(from);
575                     if(u instanceof FieldGetInst)
576                         if(block.getPredOf(u) instanceof Dup1Inst) {
577                             block.remove(u);
578                             block.insertBefore(u, to);
579                             block.remove(from);
580                             block.insertBefore(from, to);
581                             if(debug) { G.v().out.println("xxx: success due to 1, SPECIAL_SUCCESS2");}
582                             return SPECIAL_SUCCESS2;
583                         }                    
584             }*/
585                 else if (minStackHeightAttained < 0){
586                     return   pushStoreToLoad(from , to, block);
587                 }                  
588             }        
589             
590 
591             it = mUnits.iterator(mUnits.getSuccOf(from), to);
592             
593             Unit unitToMove = null; 
594             Unit u = (Unit) it.next();
595 
596             if(aContext == STORE_LOAD_LOAD_ELIMINATION) {
597                 u =  (Unit) it.next();
598             } 
599             int currentH = 0;
600             
601             // find a candidate to move before the store/load/(load)  group 
602             while( u != to) {        
603                 
604                 if(((Inst)u).getNetCount() == 1) {
605                     // xxx remove this check
606                     if(u instanceof LoadInst || u instanceof PushInst || u instanceof NewInst || u instanceof StaticGetInst || u instanceof Dup1Inst) {
607                         
608                         // verify that unitToMove is not required by following units (until the 'to' unit)
609                         if(!isRequiredByFollowingUnits(u, (LoadInst) to)) {
610                             unitToMove = u;
611                         }
612                         
613                     }
614                     else{
615                         if(debug) { G.v().out.println("1003:(LoadStoreOptimizer@stackIndependent): found unknown unit w/ getNetCount == 1" + u);}
616                     }
617                 }
618                 
619 
620 
621            
622                 
623                 if(unitToMove != null) {
624                     int flag = 0;
625                     //if(aContext == 0 || !(stackHeight > -2 && minStackHeightAttained == -2 ) ) {
626                         
627                     if(tryToMoveUnit(unitToMove, block, from, to, flag)) {
628                         if(stackHeight > -2 && minStackHeightAttained == -2){
629                             return HAS_CHANGED;
630                         }
631                         
632                         stackHeight--;
633                         if(stackHeight < minStackHeightAttained)
634                             minStackHeightAttained = stackHeight;
635                         hasChanged = true;
636                         break;
637                     }
638                 }
639                 
640                 currentH += ((Inst)u).getNetCount();                
641                 unitToMove = null;
642                 u =  (Unit) it.next();
643             }
644         }
645 
646         if(isCommutativeBinOp((Unit) block.getSuccOf(to))) {
647             if(aContext == STORE_LOAD_ELIMINATION && stackHeight == 1 && minStackHeightAttained == 0) {
648                 if(debug) { G.v().out.println("xxx: commutative ");}
649                 return SPECIAL_SUCCESS;
650             }
651             else if( ((Inst) to).getOutCount()  == 1 &&
652                      ((Inst) to).getInCount() == 0  &&
653                      ((Inst) mUnits.getPredOf(to)).getOutCount() == 1 &&
654                      ((Inst) mUnits.getPredOf(to)).getInCount() == 0) {
655                 
656                 Object   toPred =  mUnits.getPredOf(to);
657                 block.remove((Unit) toPred);
658                 block.insertAfter((Unit) toPred, to);
659                 return HAS_CHANGED; // return has changed
660             } 
661             else return FAILURE;
662         }
663         if (aContext == STORE_LOAD_ELIMINATION)
664             return   pushStoreToLoad(from , to, block);
665         
666         return res;
667     }
668 
669     
670     /**
671      * @return true if aUnit perform a non-local read or write. false otherwise.
672      */
673     private boolean isNonLocalReadOrWrite(Unit aUnit)
674     {
675         if((aUnit instanceof FieldArgInst ) ||
676            (aUnit instanceof ArrayReadInst) ||
677            (aUnit instanceof ArrayWriteInst) )
678             return true;
679         else
680             return false;
681     }
682 
683 
684     /**
685      *  When reordering bytecode, check if it is safe to move aUnitToMove past aUnitToGoOver.
686      *  @return true if aUnitToMove can be moved past aUnitToGoOver.
687      */
688     private boolean canMoveUnitOver(Unit aUnitToMove, Unit aUnitToGoOver) // xxx missing cases
689     {
690         
691         // can't change method call order or change fieldargInst and method call order
692         if((aUnitToGoOver instanceof MethodArgInst && aUnitToMove instanceof MethodArgInst) ||
693            (aUnitToGoOver instanceof MethodArgInst && isNonLocalReadOrWrite(aUnitToMove))  ||
694            (isNonLocalReadOrWrite(aUnitToGoOver)  && aUnitToMove instanceof MethodArgInst) ||
695            
696            (aUnitToGoOver instanceof ArrayReadInst  && aUnitToMove instanceof ArrayWriteInst) ||
697            (aUnitToGoOver instanceof ArrayWriteInst && aUnitToMove instanceof ArrayReadInst)  ||
698            (aUnitToGoOver instanceof ArrayWriteInst  && aUnitToMove instanceof ArrayWriteInst)||
699 
700            
701            (aUnitToGoOver instanceof FieldPutInst && aUnitToMove instanceof FieldGetInst &&
702             ((FieldArgInst)aUnitToGoOver).getField() == ((FieldArgInst)aUnitToMove).getField()) ||
703            (aUnitToGoOver instanceof FieldGetInst && aUnitToMove instanceof FieldPutInst && 
704             ((FieldArgInst)aUnitToGoOver).getField() == ((FieldArgInst)aUnitToMove).getField()) ||
705            (aUnitToGoOver instanceof FieldPutInst && aUnitToMove instanceof FieldPutInst && 
706             ((FieldArgInst)aUnitToGoOver).getField() == ((FieldArgInst)aUnitToMove).getField()) ||
707            
708            
709            (aUnitToGoOver instanceof StaticPutInst && aUnitToMove instanceof StaticGetInst &&
710             ((FieldArgInst)aUnitToGoOver).getField() == ((FieldArgInst)aUnitToMove).getField()) ||
711            (aUnitToGoOver instanceof StaticGetInst && aUnitToMove instanceof StaticPutInst && 
712             ((FieldArgInst)aUnitToGoOver).getField() == ((FieldArgInst)aUnitToMove).getField())||
713            (aUnitToGoOver instanceof StaticPutInst && aUnitToMove instanceof StaticPutInst && 
714             ((FieldArgInst)aUnitToGoOver).getField() == ((FieldArgInst)aUnitToMove).getField()))
715             return false;
716            
717 
718         // xxx to be safe don't mess w/ monitors. These rules could be relaxed. ? Maybe.
719         if(aUnitToGoOver instanceof EnterMonitorInst || aUnitToGoOver instanceof ExitMonitorInst)
720             return false;
721 
722         if(aUnitToMove instanceof EnterMonitorInst || aUnitToGoOver instanceof ExitMonitorInst)
723             return false;
724 
725         if(aUnitToGoOver instanceof IdentityInst || aUnitToMove instanceof IdentityInst)
726             return false;
727 
728         
729         if(aUnitToMove instanceof LoadInst ) {
730             if(aUnitToGoOver instanceof StoreInst) {
731                 if(((StoreInst)aUnitToGoOver).getLocal() == ((LoadInst)aUnitToMove).getLocal()) {
732                     return false;
733                 }
734             }
735             else if(aUnitToGoOver instanceof IncInst) {
736                 if(((IncInst)aUnitToGoOver).getLocal() == ((LoadInst)aUnitToMove).getLocal()){
737                     return false;
738                 }
739             }
740         }
741 
742         // don't move def of load  pass it.
743         if(aUnitToMove instanceof StoreInst) {
744             if(aUnitToGoOver instanceof LoadInst) {
745                 if(((LoadInst)aUnitToGoOver).getLocal() == ((StoreInst)aUnitToMove).getLocal()) {
746                     return false;
747                 }
748             }
749             else if(aUnitToGoOver instanceof IncInst) {
750                 if(((IncInst)aUnitToGoOver).getLocal() == ((StoreInst)aUnitToMove).getLocal()){
751                     return false;
752                 }
753             }
754         }
755         
756         if(aUnitToMove instanceof IncInst) {
757             if(aUnitToGoOver instanceof StoreInst) {
758                 if(((StoreInst)aUnitToGoOver).getLocal() == ((IncInst)aUnitToMove).getLocal()) {
759                     return false;
760                 }
761             }
762             else if(aUnitToGoOver instanceof LoadInst) {
763                 if(((LoadInst)aUnitToGoOver).getLocal() == ((IncInst)aUnitToMove).getLocal()){
764                     return false;
765                 }
766             }
767         }
768         return true;
769     }
770 
771 
772 
773 
774 
775 
776     private  boolean tryToMoveUnit(Unit unitToMove, Block block, Unit from, Unit to, int flag) 
777     {
778        
779         int h = 0;
780         Unit current = unitToMove;
781         boolean reachedStore = false;
782         boolean reorderingOccurred =false;
783               
784         if(debug) {G.v().out.println("[tryToMoveUnit]: trying to move:" + unitToMove);}
785         if(unitToMove == null) 
786             return false;                
787                 
788         while( current != block.getHead()) {   // do not go past basic block limit
789             current = (Unit) mUnits.getPredOf(current);
790             
791             if(!canMoveUnitOver(current, unitToMove))
792                 return false;
793 
794             if(current == from)
795                 reachedStore = true;
796                 
797         
798             h -= ((Inst)current).getOutCount();                
799             if(h < 0 ){
800                 if(debug) { G.v().out.println("1006:(LoadStoreOptimizer@stackIndependent): Stack went negative while trying to reorder code.");}
801 
802 
803 
804                 if(flag == 1) {
805                     if(current instanceof DupInst) {
806                         block.remove(unitToMove);
807                         block.insertAfter(unitToMove, current);        
808                         //                        block.insertAfter(  new BSwapInst(  )     ,unitToMove);
809                     }
810                     
811                 }
812                 return false;
813             }
814             h += ((Inst)current).getInCount();
815             
816             
817             if(h == 0 && reachedStore == true) {
818                 if(!isRequiredByFollowingUnits(unitToMove, (LoadInst) to)) {
819                     if(debug) { G.v().out.println("10077:(LoadStoreOptimizer@stackIndependent): reordering bytecode move: " + unitToMove + "before: " + current);}
820                     block.remove(unitToMove);
821                     block.insertBefore(unitToMove, current);
822                     
823                     reorderingOccurred = true;
824                     break;
825                 }                    
826             }                                      
827         }
828             
829         if(reorderingOccurred) {
830             if(debug) { G.v().out.println("reordering occured");}
831             return true;
832         } else {
833             if(debug) { G.v().out.println("1008:(LoadStoreOptimizer@stackIndependent):failled to find a new slot for unit to move");}
834             return false;
835         }
836     }
837 
838     
839 
840 
841     /** 
842      *  Replace 1 or 2 units by a third unit in a block. Both units to 
843      *  replace should be in the same block. The map 'mUnitToBlockMap'   
844      *  is updated. The replacement unit is inserted in the position,
845      *  of the aToReplace2 if not null, otherwise in aToReplace1's slot.
846      *
847      *  @param aToReplace1 Unit to replace. (shouldn't be null)
848      *  @param aToReplace2 Second Unit to replace (can be  null)
849      *  @param aReplacement Unit that replaces the 2 previous units (shouldn't be null)
850      */
851     private void replaceUnit(Unit aToReplace1, Unit aToReplace2,  Unit aReplacement) 
852     {
853         Block block = (Block) mUnitToBlockMap.get(aToReplace1);
854                  
855         if(aToReplace2 != null) {
856             block.insertAfter(aReplacement, aToReplace2);
857             block.remove(aToReplace2);
858         } else {
859             block.insertAfter(aReplacement, aToReplace1);            
860         }
861 
862         block.remove(aToReplace1);
863                                                         
864         // add the new unit the block map
865         mUnitToBlockMap.put(aReplacement, block);        
866     }
867     
868  
869     private void replaceUnit(Unit aToReplace, Unit aReplacement) 
870     {
871         replaceUnit(aToReplace, null, aReplacement);
872     }
873 
874 
875     
876     /**
877      *  Returns the type of the stack item produced by certain Unit objects.
878      */
879     private Type type(Unit aUnit)
880     {
881         if(aUnit instanceof InstanceCastInst || aUnit instanceof NewInst) {
882             return  RefType.v();        
883         } else if(aUnit instanceof LoadInst) {
884             return ((LoadInst)aUnit).getOpType();
885         } else  if (aUnit instanceof FieldGetInst)
886             return ((FieldGetInst)aUnit).getField().getType();
887         else if (aUnit instanceof Dup1Inst)
888             return ((Dup1Inst)aUnit).getOp1Type();
889         else if(aUnit instanceof StaticGetInst)
890             return ((StaticGetInst) aUnit).getField().getType();
891         else if(aUnit instanceof OpTypeArgInst)
892             return ((OpTypeArgInst)aUnit).getOpType();
893         else if(aUnit instanceof PushInst)
894             return ((PushInst)aUnit).getConstant().getType();
895         else if (aUnit instanceof MethodArgInst)
896             return ((MethodArgInst) aUnit).getMethod().getReturnType();
897         else if(aUnit instanceof Dup1_x1Inst)
898             return ((Dup1_x1Inst) aUnit).getOp1Type();
899         else if(aUnit instanceof Dup1Inst)
900             return ((Dup1Inst) aUnit).getOp1Type();
901         else
902             return null;
903     }
904 
905     
906     /* 
907      * @param some block
908      * @return true if the block is an exception handler.
909      */
910     private boolean isExceptionHandlerBlock(Block aBlock)
911     {
912         Unit blockHead = aBlock.getHead();
913         Iterator  it = mBody.getTraps().iterator();
914         while(it.hasNext()) {
915             Trap trap = (Trap) it.next();
916             if(trap.getHandlerUnit() == blockHead)
917                 return true;
918         }
919         return false;
920     }
921 
922     private Unit getStackItemAt2(Unit aUnit, Block aBlock, int aDeltaHeight) 
923     {
924         int h = 0;
925         Unit currentUnit  = aUnit;
926         Unit candidate = null;
927         
928         while(currentUnit != null) {
929             currentUnit  = (Unit) aBlock.getPredOf(currentUnit);
930             if(currentUnit == null) {
931                 if(debug) { G.v().out.println(aBlock);}
932                 G.v().out.println("xxxxxxxxxxxx " + h);
933                 if(isExceptionHandlerBlock(aBlock) ) {
934                     return new BLoadInst( RefType.v("dummy") , ((StoreInst) aUnit).getLocal());                     // we have a ref type. 
935                 }
936 
937                 aBlock = (Block) aBlock.getPreds().get(0);
938                 currentUnit = (Unit) aBlock.getTail();
939 
940             }
941             
942             
943             h -= ((Inst)currentUnit).getOutCount();
944             if(h <= aDeltaHeight) {
945                 candidate = currentUnit;
946                 break;
947             }            
948             h += ((Inst)currentUnit).getInCount();            
949         }        
950         return candidate;
951     }
952     
953 
954 
955     
956     // not a save function :: goes over block boundries
957     private int getDeltaStackHeightFromTo(Unit aFrom, Unit aTo) 
958     {
959         Iterator it = mUnits.iterator(aFrom, aTo);
960         int h = 0;
961         
962         while(it.hasNext()) {
963             h += ((Inst)it.next()).getNetCount();
964         }
965         
966         return h;
967     }
968 
969     
970 
971     /** 
972      *   Performs 2 simple inter-block optimizations in order to keep 
973      *   some variables  on the stack between blocks. Both are intented to catch
974      *   'if' like constructs where the control flow branches temporarely into two paths 
975      *    that join up at a latter point. 
976      *
977      */
978     private void doInterBlockOptimizations() 
979     {
980         boolean hasChanged = true;
981         while(hasChanged) {
982             hasChanged = false;
983             
984             List tempList = new ArrayList();
985             tempList.addAll(mUnits);
986             Iterator it = tempList.iterator();        
987             while(it.hasNext()) {
988                 Unit u = (Unit) it.next();
989                 
990                 if(u instanceof LoadInst) {
991                     if(debug) { G.v().out.println("inter trying: " + u);}
992                     Block loadBlock = (Block) mUnitToBlockMap.get(u);
993                     List defs = mLocalDefs.getDefsOfAt(((LoadInst)u).getLocal(), u);
994 
995                     // first optimization 
996                     if(defs.size() ==  1) {
997                         Block defBlock =(Block)  mUnitToBlockMap.get(defs.get(0));
998                         if(defBlock != loadBlock && !(isExceptionHandlerBlock(loadBlock))) {
999                             Unit storeUnit = (Unit) defs.get(0);
1000                            if(storeUnit instanceof StoreInst) {
1001                                List uses = mLocalUses.getUsesOf(storeUnit);
1002                                if(uses.size() == 1){
1003                                    if(allSuccesorsOfAreThePredecessorsOf(defBlock, loadBlock)) {
1004                                        if(getDeltaStackHeightFromTo((Unit) defBlock.getSuccOf(storeUnit), (Unit)defBlock.getTail()) == 0) {
1005                                            Iterator it2 = defBlock.getSuccs().iterator();
1006                                            boolean res = true;
1007                                            while(it2.hasNext()) {
1008                                                Block b = (Block) it2.next();
1009                                                if(getDeltaStackHeightFromTo((Unit) b.getHead(), (Unit) b.getTail()) != 0) {
1010                                                    res = false;
1011                                                    break;
1012                                                }
1013                                                if(b.getPreds().size() != 1 || b.getSuccs().size() != 1){
1014                                                    res = false;
1015                                                    break;
1016                                                }
1017                                            }                        
1018                                            if(debug) { G.v().out.println(defBlock.toString() + loadBlock.toString());}
1019                                            
1020                                            if(res) {
1021                                                defBlock.remove(storeUnit);                            
1022                                                mUnitToBlockMap.put(storeUnit, loadBlock);
1023                                                loadBlock.insertBefore(storeUnit, loadBlock.getHead());
1024                                                hasChanged = true;
1025                                                if(debug) { G.v().out.println("inter-block opti occurred " + storeUnit + " " + u);}
1026                                                if(debug) { G.v().out.println(defBlock.toString() + loadBlock.toString());}
1027                                            }
1028                                        }
1029                                    }
1030                                }
1031                            }
1032                        }
1033                    } 
1034                    // second optimization
1035                    else if(defs.size() == 2) {
1036                        
1037                        Unit def0 = (Unit) defs.get(0);
1038                        Unit def1 = (Unit) defs.get(1);
1039                            
1040                        Block defBlock0 = (Block)  mUnitToBlockMap.get(def0);
1041                        Block defBlock1 = (Block)  mUnitToBlockMap.get(def1);
1042                        if(defBlock0 != loadBlock && defBlock1 != loadBlock && defBlock0 != defBlock1
1043                           && !(isExceptionHandlerBlock(loadBlock))) {                                
1044                            if(mLocalUses.getUsesOf(def0).size() == 1  && mLocalUses.getUsesOf(def1).size() == 1) {
1045                                List def0Succs = defBlock0.getSuccs();
1046                                List def1Succs  = defBlock1.getSuccs();
1047                                if(def0Succs.size()==1 && def1Succs.size()==1) {
1048                                    if(def0Succs.get(0) == loadBlock && def1Succs.get(0)== loadBlock) {                                         
1049                                        if(loadBlock.getPreds().size() == 2) {
1050                                            if( (def0 == defBlock0.getTail()|| 
1051                                                 getDeltaStackHeightFromTo((Unit)defBlock0.getSuccOf(def0),(Unit) defBlock0.getTail())  == 0) && 
1052                                                (def1 == defBlock1.getTail() ||
1053                                                 getDeltaStackHeightFromTo((Unit)defBlock1.getSuccOf(def1), (Unit) defBlock1.getTail()) == 0)) {
1054                                                defBlock0.remove(def0);                            
1055                                                defBlock1.remove(def1);
1056                                                loadBlock.insertBefore(def0, loadBlock.getHead());
1057                                                mUnitToBlockMap.put(def0, loadBlock);
1058                                                hasChanged = true;
1059                                                if(debug) { G.v().out.println("inter-block opti2 occurred " + def0);}
1060                                            } else { if(debug) { G.v().out.println("failed: inter1");}}
1061                                        } else { if(debug) { G.v().out.println("failed: inter2");}}
1062                                    } else { if(debug) { G.v().out.println("failed: inter3");}}                                        
1063                                } else { if(debug) { G.v().out.println("failed: inter4");}}
1064                            }        else { if(debug) { G.v().out.println("failed: inter5");}}                        
1065                        } else { if(debug) { G.v().out.println("failed: inter6");}}
1066                    }                         
1067                }        
1068            }
1069        }
1070    }
1071    
1072    
1073
1074    /**
1075     *  Given 2 blocks, assertains whether all the succesors of the first block are the predecessors 
1076     *  of the second block.
1077     */    
1078    private boolean allSuccesorsOfAreThePredecessorsOf(Block aFirstBlock, Block aSecondBlock)
1079    {        
1080        int size = aFirstBlock.getSuccs().size();        
1081        Iterator it = aFirstBlock.getSuccs().iterator();
1082        
1083        List preds = aSecondBlock.getPreds();
1084        while(it.hasNext()) {
1085            if(!preds.contains(it.next())) 
1086                return false;
1087        }
1088        
1089        if(size == preds.size())
1090            return true;
1091        else
1092            return false;        
1093    }
1094
1095
1096
1097    
1098     
1099    /**
1100     *  @return true if aUnit is a commutative binary operator
1101     */
1102    private boolean isCommutativeBinOp(Unit aUnit)
1103    {
1104        if(aUnit == null )
1105            return false;
1106        
1107        if(aUnit instanceof AddInst ||
1108           aUnit instanceof MulInst ||
1109           aUnit instanceof AndInst ||
1110           aUnit instanceof OrInst ||
1111           aUnit instanceof XorInst) 
1112            return true;
1113        else
1114            return false;
1115    }
1116
1117    /*
1118     *  @param aInst 
1119     */
1120    private boolean propagateLoadForward(Unit aInst) 
1121    {
1122        Unit currentUnit;
1123        Block block  = (Block) mUnitToBlockMap.get(aInst);
1124        boolean res = false;
1125        int h = 0;
1126        Unit candidate = null;
1127        
1128        if(aInst == block.getTail())
1129            return false;
1130        
1131        currentUnit = (Unit) block.getSuccOf(aInst);
1132       
1133        while( currentUnit != block.getTail()) {
1134            
1135            if(!canMoveUnitOver(aInst,  currentUnit)){ if(debug) { G.v().out.println("can't go over: " + currentUnit);}
1136            break;}
1137            
1138
1139            h -= ((Inst)currentUnit).getInCount();                
1140            if(h < 0){
1141                if(!(aInst instanceof Dup1Inst && currentUnit instanceof Dup1Inst)) {
1142                    if(debug) { G.v().out.println("breaking at: " + currentUnit);}                
1143                    break;
1144                }
1145            }            
1146            
1147            h += ((Inst)currentUnit).getOutCount();
1148            
1149            if(h == 0){
1150                candidate = currentUnit; // don't stop now; try to go still forward.
1151            }
1152            
1153            currentUnit = (Unit) block.getSuccOf(currentUnit);            
1154        }        
1155        if(candidate != null) {
1156            if(debug) { G.v().out.println("successfull propagation "  + candidate + block.getTail());}
1157            block.remove(aInst);
1158            if(block.getTail() == mUnitToBlockMap.get(candidate)){
1159                
1160                block.insertAfter(aInst, candidate);
1161                if(block.getTail() != aInst)
1162                    throw new RuntimeException  ();
1163            }
1164            block.insertAfter(aInst, candidate);            
1165            return true;
1166        }
1167        
1168        return false;
1169    }
1170
1171
1172
1173    /* 
1174     * 
1175     */
1176    private void propagateLoadsForward()
1177    { 
1178        boolean hasChanged = true;
1179
1180        while(hasChanged) {
1181            hasChanged = false;
1182            List tempList = new ArrayList();
1183            tempList.addAll(mUnits);
1184            Iterator it = tempList.iterator();
1185            
1186            while(it.hasNext()) {
1187                Unit u = (Unit) it.next();
1188                if( u instanceof LoadInst || u instanceof Dup1Inst) {
1189                    if(debug) { G.v().out.println("trying to push:"  + u);}
1190                    boolean res =propagateLoadForward(u);
1191                    if(!hasChanged)
1192                        hasChanged = res;
1193                }
1194            }
1195        }
1196    }
1197    
1198
1199    void propagateBackwardsIndependentHunk() 
1200    {
1201        
1202        List tempList = new ArrayList();
1203        tempList.addAll(mUnits);
1204        Iterator it = tempList.iterator();
1205        
1206        while(it.hasNext()) {
1207            Unit u = (Unit) it.next();
1208            
1209            if( u instanceof NewInst) {
1210                Block block  = (Block) mUnitToBlockMap.get(u);
1211                Unit succ = (Unit) block.getSuccOf(u);
1212                if( succ instanceof StoreInst) {
1213                    Unit currentUnit = u;
1214                    Unit candidate = null;
1215                    
1216                    while(currentUnit != block.getHead()) {
1217                        currentUnit = (Unit) block.getPredOf(currentUnit);
1218                        if(canMoveUnitOver(currentUnit, succ)){
1219                            candidate = currentUnit;
1220                        } else
1221                            break;
1222                    }
1223                    if(candidate != null) {
1224                        block.remove(u);
1225                        block.remove(succ);
1226                        block.insertBefore(u, candidate);
1227                        block.insertBefore(succ, candidate);                        
1228                    }                    
1229                }
1230            } 
1231        }
1232    }
1233    
1234
1235
1236    // For each LoadInst in the method body, call propagateLoadBackwards to
1237    // try to relocate the load as close to the start of it's basic block as possible. 
1238    private void propagateLoadsBackwards()
1239    {        
1240        boolean hasChanged = true;
1241        while(hasChanged) {
1242            hasChanged = false;
1243            
1244            List tempList = new ArrayList();
1245            tempList.addAll(mUnits);
1246
1247            Iterator it = tempList.iterator();
1248            while(it.hasNext()) {
1249                Unit currentInst = (Unit) it.next();
1250                    
1251                if(currentInst instanceof LoadInst) {
1252                    Block block = (Block)  mUnitToBlockMap.get(currentInst);                    
1253                    Unit insertPoint = propagateLoadBackwards(currentInst, block);
1254                        
1255                    if(insertPoint != null) {                        
1256                        block.remove(currentInst);
1257                        block.insertBefore(currentInst, insertPoint);
1258                        hasChanged = true;                       
1259                    }
1260                }
1261            }        
1262        }        
1263    }
1264    
1265
1266    // Given a LoadInst  and it's block, try to relocate the load as  close as possible to 
1267    // the start of it's block.
1268    private Unit propagateLoadBackwards(Unit aInst, Block aBlock) 
1269    {
1270        int h = 0;
1271        Unit candidate = null;
1272        Unit currentUnit =  aInst;   
1273        
1274        //List loadDefList = mLocalDefs.getDefsOfAt(((LoadInst)aInst).getLocal(), aInst);
1275                
1276        currentUnit = (Unit) aBlock.getPredOf(currentUnit);        
1277        while( currentUnit != null) {
1278            if(!canMoveUnitOver(currentUnit, aInst))
1279                break;
1280            
1281            h -= ((Inst)currentUnit).getOutCount();                            
1282            if(h < 0) break;                        
1283            h += ((Inst)currentUnit).getInCount();
1284            if(h == 0) candidate = currentUnit;
1285           
1286            
1287            currentUnit = (Unit) aBlock.getPredOf(currentUnit);
1288        }        
1289        
1290        return candidate;
1291    }
1292    
1293
1294
1295    // recycled code:
1296    /*
1297      // convertsa series of loads into dups when applicable
1298      void superDuper1() { 
1299      List tempList = new ArrayList();
1300      tempList.addAll(mUnits);
1301      Iterator it = tempList.iterator();
1302      boolean fetchUnit = true;
1303        
1304      while(it.hasNext()) {
1305      Unit currentInst = null;
1306            
1307      if(fetchUnit) {
1308      currentInst = (Unit) it.next();               
1309      }
1310      fetchUnit = true;
1311            
1312      if(currentInst instanceof LoadInst) {
1313      Block block = (Block) mUnitToBlockMap.get(currentInst);
1314                
1315      Local local = ((LoadInst)currentInst).getLocal();
1316                    
1317      // count the number of identical loads
1318                
1319      Unit u;
1320      for(;;){
1321      if(it.hasNext()) {
1322      u = (Unit) it.next();
1323      if(mUnitToBlockMap.get(u) != block)
1324      break;
1325                        
1326      if(u instanceof LoadInst) {
1327      if(((LoadInst)u).getLocal() == local) {
1328      replaceUnit(u, Baf.v().newDup1Inst(((LoadInst) u).getOpType()));
1329
1330      } else {
1331      fetchUnit =false;
1332      break;
1333      }
1334      } else {                        
1335      break;
1336      }
1337      } else 
1338      break;
1339      }                
1340      }
1341      }
1342      }
1343
1344    
1345      //broken use superDuper1
1346      void superDuper() {
1347      // compress a serie of loads using dup2's and dup's
1348      {
1349      List tempList = new ArrayList();
1350      tempList.addAll(mUnits);
1351      Iterator it = tempList.iterator();
1352      while(it.hasNext()) {
1353      Unit currentInst = (Unit) it.next();
1354                   
1355      if(currentInst instanceof LoadInst) {
1356      Block block = (Block) mUnitToBlockMap.get(currentInst);
1357                    
1358      int loadCount = 1;
1359      Local local = ((LoadInst)currentInst).getLocal();
1360                    
1361      // count the number of identical loads
1362                    
1363      Unit u;
1364      for(;;){
1365      u = (Unit) it.next();
1366      if(mUnitToBlockMap.get(u) != block)
1367      break;
1368                        
1369      if(u instanceof LoadInst) {
1370      if(((LoadInst)u).getLocal() == local)
1371      loadCount++;
1372      else
1373      break;
1374      } else {
1375      break;
1376      }
1377      }
1378                    
1379
1380      if(loadCount > 1) {
1381      Type loadType = ((LoadInst)currentInst).getOpType();
1382        
1383                                // must leave at least one load on stack before dupping
1384                                Unit currentLoad = (Unit) mUnits.getSuccOf(currentInst);
1385                                loadCount--; 
1386                  
1387                                if(loadType instanceof LongType || loadType instanceof DoubleType) {
1388                                
1389                         
1390                                
1391                                while(loadCount > 0) {
1392                                Unit nextLoad = (Unit) mUnits.getSuccOf(currentLoad); 
1393                                replaceUnit(currentLoad,  Baf.v().newDup1Inst(loadType));                                                
1394                                    
1395                                currentLoad = nextLoad;                                 
1396                                loadCount--;
1397                                }                                
1398                                } else {
1399                                boolean canMakeDup2 = false;
1400                                if(loadCount >= 3) {
1401                                canMakeDup2 = true;
1402                                currentLoad = (Unit) mUnits.getSuccOf(currentLoad);
1403                                loadCount--;
1404                                }
1405                            
1406                                while(loadCount > 0) {
1407                                
1408                                if(loadCount == 1 || !canMakeDup2) {
1409                                Unit nextLoad = (Unit) mUnits.getSuccOf(currentLoad); 
1410                                replaceUnit(currentLoad,  Baf.v().newDup1Inst(loadType));                                                
1411                                    
1412                                currentLoad = nextLoad;
1413                                loadCount--;        
1414                                } else {
1415                                if(canMakeDup2) {
1416                                Unit nextLoad = (Unit) mUnits.getSuccOf(mUnits.getSuccOf(currentLoad));
1417                                replaceUnit(currentLoad, (Unit) mUnits.getSuccOf(currentLoad),  Baf.v().newDup2Inst(loadType, loadType));                    
1418                                currentLoad = nextLoad;
1419                                loadCount -= 2;        
1420                                }
1421                                }                                                            
1422                                }
1423                                }
1424                                }                    
1425                                currentInst = u;
1426                                }                
1427                                }
1428                                }
1429                                }
1430    
1431                                void peephole() {
1432                                boolean hasChanged = true;
1433       
1434                                while(hasChanged) {
1435                                hasChanged = false;
1436                                List tempList = new ArrayList();
1437                                tempList.addAll(mUnits);
1438           
1439                                Iterator it = tempList.iterator();
1440                                while(it.hasNext() ) {
1441                                Unit currentUnit = (Unit) it.next();
1442                                if(currentUnit instanceof PopInst) {
1443                                Block popBlock = (Block) mUnitToBlockMap.get(currentUnit);
1444                                Unit prev = (Unit) popBlock.getPredOf(currentUnit);
1445                                Unit succ = (Unit) popBlock.getSuccOf(currentUnit);
1446                   
1447                                if(prev instanceof LoadInst || prev instanceof PushInst) 
1448                                if(((AbstractInst)prev).getOutMachineCount() == ((AbstractInst)currentUnit).getInMachineCount()) {
1449                                popBlock.remove(prev);
1450                                popBlock.remove(currentUnit);
1451                                }
1452                                else if(succ instanceof ReturnInst) {
1453                                popBlock.remove(currentUnit);
1454                                popBlock.remove(succ);
1455                                }                                   
1456                                }
1457                                }       
1458                                }
1459                                }  
1460
1461                
1462                                private boolean propagateStoreForward(Unit aInst, Unit aUnitToReach, Unit aCurrentUnit, int aStackHeight) 
1463                                {
1464                                boolean res = false;
1465                                Unit currentUnit =  aCurrentUnit;           
1466                                Local storeLocal = ((StoreInst)aInst).getLocal();
1467                                Block block  = (Block) mUnitToBlockMap.get(aCurrentUnit);
1468        
1469                                while( currentUnit != block.getTail()) {
1470                                if(currentUnit == aUnitToReach) {
1471                                if(aStackHeight == 0)
1472                                return true;
1473                                else
1474                                return false;
1475                                }
1476            
1477                                if(!canMoveUnitOver(aInst, currentUnit)) {
1478                                res = false;
1479                                break;
1480                                }
1481            
1482                                aStackHeight -= ((Inst)currentUnit).getInCount();                
1483                                if(aStackHeight < 0){
1484                                res = false;
1485                                break;
1486                                }            
1487                                aStackHeight += ((Inst)currentUnit).getOutCount();
1488            
1489                                currentUnit = (Unit) block.getSuccOf(currentUnit);
1490                                }        
1491
1492                                // if we hit the block boundry 
1493                                if( currentUnit == block.getTail()) {
1494                                Iterator it = block.getSuccessors().iterator();        
1495                                while(it.hasNext()) {
1496                                Block b = (Block) it.next();
1497                                if(!propagateStoreForward(aInst, aUnitToReach,  b.getHead(), aStackHeight))
1498                                return false;                
1499                                }
1500                                res = true;
1501                                }        
1502                                return res;
1503                                }
1504
1505    */
1506
1507}   
1508
1509
1510}
1511
1512
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags