SsaBasicBlockWrapper


1   /*
2    * Created on Sep 14, 2004 @author Matthias Kempka
3    */
4   package de.uka.ipd.coverage.natures.all_uses;
5   
6   import java.util.*;
7   
8   import org.apache.bcel.generic.*;
9   
10  import de.uka.ipd.coverage.recording.*;
11  import de.uka.ipd.coverage.utils.BCELFillIn;
12  
13  /**
14   * @author Matthias Kempka
15   */
16  public class SsaBasicBlockWrapper implements IBasicBlock {
17  
18      private InstructionHandle blockFirstHandle, blockLastHandle = null;
19      private BasicBlock wrappedBasicBlock;
20  
21      //  maps local variable indizes as Integer object to Integer objects,
22      //  the latter representing the local variable index in the ssa block.
23      private Map indexMap = new HashMap();
24      
25      /*
26       * this Map is only necessary in special cases, thus initialized only in 
27       * those cases. It holds the history of indices for a local variable.
28       * This is necessary when there is a store after a load and the loads
29       * original index would be forgotten otherwise. 
30       * This history of indices is not necessary for the ssa form, but 
31       * used by the class
32       * de.uka.ipd.coverage.natures.all_uses.DefinitionFreePath
33       */
34      private Map historyIndexMap = null;
35      
36      // maps field indices to local variable indices: Integer -> Integer
37      // the local variable indices are those that are created as field
38      // replacement, not the SSA indices.
39      // this method must be set from the SSABasicBlockBuilder for it must
40      // be the same for all blocks for a method.
41      private Map fieldMap; 
42  
43      private boolean ssaForm = false;
44      private MethodGen methodGen;
45      
46      private Map basicBlockMap;
47      private InstructionList il;
48  
49      public SsaBasicBlockWrapper(BasicBlock originalBlock, InstructionList il,
50              MethodGen methodGen) {
51          this.wrappedBasicBlock = originalBlock;
52          this.methodGen = methodGen;
53          this.il = il;
54          setBeginAndEndInstructionHandles();
55          assert blockFirstHandle != null && blockLastHandle != null 
56                  : "Begin and end instructions not found in instructionlist"; //$NON-NLS-1$
57      }
58      
59      protected SsaBasicBlockWrapper(SsaBasicBlockWrapper original) {
60          this.basicBlockMap = original.basicBlockMap;
61          this.blockFirstHandle = original.blockFirstHandle;
62          this.blockLastHandle = original.blockLastHandle;
63          this.fieldMap = original.fieldMap;
64          this.historyIndexMap = original.historyIndexMap;
65          this.il = original.il;
66          this.indexMap = original.indexMap;
67          this.methodGen = original.methodGen;
68          this.ssaForm = original.ssaForm;
69          this.wrappedBasicBlock = original.wrappedBasicBlock;
70      }
71  
72      protected void setBeginAndEndInstructionHandles() {
73          int begin = getStartLine();
74          int end = getEndLine();
75          for (Iterator iter = il.iterator(); iter.hasNext();) {
76              InstructionHandle handle = (InstructionHandle) iter.next();
77              if (handle.getPosition() == begin) {
78                  blockFirstHandle = handle;
79              }
80              if (handle.getPosition() == end) {
81                  blockLastHandle = handle;
82                  assert blockFirstHandle != null 
83                          : "found block end before block start."; //$NON-NLS-1$
84                  return;
85              }
86          }
87      }
88  
89      public RegisteredMethod getRegisteredMethod() {
90          return wrappedBasicBlock.getRegisteredMethod();
91      }
92  
93      public CoverageState covers(IBasicBlock obj) {
94          return wrappedBasicBlock.covers(obj);
95      }
96  
97      public boolean referencesSameBytecodeAs(BasicBlock compBlock) {
98          return wrappedBasicBlock.referencesSameBytecodeAs(compBlock);
99      }
100 
101     public int getEndLine() {
102         return wrappedBasicBlock.getEndLine();
103     }
104 
105     public int getStartLine() {
106         return wrappedBasicBlock.getStartLine();
107     }
108 
109     public boolean isSsaForm() {
110         return ssaForm;
111     }
112 
113     /**
114      * first, this method replaces all IINC instruction in the given instruction
115      * list with load, add and store instructions. <br>
116      * then, it replaces all uses of fields with local variables.<br>
117      * then, it sets the stores to "define" the arguments.
118      */
119     protected void generateSSACompatibleForm() {
120         InstructionList il = methodGen.getInstructionList();
121         replaceIINCInstructions(il);
122         replaceFieldsWithLocalVariables(il);
123         setArgumentStores(il);
124     }
125 
126     private void setArgumentStores(InstructionList il) {
127         // only do something if this is the first block of the method
128         if (getPredecessorWrappers().length == 0) {
129             // if this is an exception handler, do nothing.
130             CodeExceptionGen[] eh = methodGen.getExceptionHandlers();
131             for (int i = 0; i < eh.length; i++) {
132                 if (eh[i].getStartPC() == blockFirstHandle) {
133                     return;
134                 }
135             }
136             String  [] arguments = getMethodGen().getArgumentNames();
137             LocalVariableGen[] lvg = getMethodGen().getLocalVariables();
138             // first local variable is "this"
139             // then the arguments are passed and after that the local variables
140             // of the method.
141             for (int i = 1; i <= arguments.length && i < lvg.length; i++) {
142                 //TODO: find more reliable way to get line of argument definition!
143                 int sourceLine = getRegisteredMethod().getMethod().
144                     getLineNumberTable().getSourceLine(
145                         lvg[i].getStart().getPosition());
146                 Instruction store = new PseudoStore(lvg[i].getIndex(), sourceLine - 1);
147                 il.insert(blockFirstHandle, store);
148                 blockFirstHandle = blockFirstHandle.getPrev();
149 
150             }
151         }
152     }
153 
154     /*
155      * This method replaces field getters and setters with local variables.
156      * Every field used in this method is stored in a local variable at the
157      * beginning of the method, and all uses of fields are redirected to 
158      * that local variable.
159      * This is done to standardize the generation of the SSA form and won't
160      * produce code that actually runs. To achieve this, at method exit 
161      * the local variables would have to be stored back into the fields 
162      * and racing conditions must be considered.
163      * However, since the only purpose of this SSA form is to achieve 
164      * data flow control this procedure is good enough. 
165      */
166     private void replaceFieldsWithLocalVariables(InstructionList il) {
167         for (InstructionHandle element = blockFirstHandle; 
168                 element != blockLastHandle; 
169                 element = element.getNext()) {
170             if (element.getInstruction() instanceof FieldInstruction) {
171                 ConstantPoolGen cpg = methodGen.getConstantPool();
172                 FieldInstruction fi = (FieldInstruction) element.getInstruction();
173                 Integer   index = new Integer  (fi.getIndex());
174                 if (!fieldMap.containsKey(index)) {
175                     weaveInFieldReplacement(fi);
176                 }
177                 int lvnIndex = ((Integer  ) fieldMap.get(index)).intValue();
178                 if (       element.getInstruction() instanceof GETFIELD
179                         || element.getInstruction() instanceof GETSTATIC) {
180                     // replace field getters with loads for the appropriate 
181                     // local variable.
182                     element.setInstruction(InstructionFactory.createLoad(
183                         fi.getFieldType(cpg), 
184                         lvnIndex));
185                 } else if (element.getInstruction() instanceof PUTFIELD
186                         || element.getInstruction() instanceof PUTSTATIC) {
187                     // replace field setters with stores for the appropriate
188                     // local variable.
189                     element.setInstruction(InstructionFactory.createStore(
190                         fi.getFieldType(cpg), 
191                         lvnIndex));
192                 }
193             } else if (element.getInstruction() instanceof ReturnInstruction){
194                 for (Iterator iter = fieldMap.values().iterator(); iter.hasNext();) {
195                     int index = ((Integer  ) iter.next()).intValue();
196                     Type type = BCELFillIn.findType(
197                         methodGen.getConstantPool().getConstant(index));
198                     il.insert(element, InstructionFactory.createLoad(type, index));
199                 }
200             }
201         }
202     }
203 
204 
205     /**
206      * @param gf
207      */
208     private void weaveInFieldReplacement(FieldInstruction gf) {
209         LocalVariableGen lvg = 
210             createLocalVariableAsFieldReplacement(gf);
211         InstructionList il = methodGen.getInstructionList();
212         il.insert(il.getStart(), InstructionFactory.createLoad(
213                 lvg.getType(), lvg.getIndex()));
214         fieldMap.put(new Integer  (gf.getIndex()), new Integer  (lvg.getIndex()));
215     }
216 
217     private void replaceIINCInstructions(InstructionList il) {
218         if (blockFirstHandle != blockLastHandle) {
219             for (InstructionHandle element = blockFirstHandle; 
220                     element != blockLastHandle; 
221                     element = element.getNext()) {
222                 if (element.getInstruction() instanceof IINC) {
223                     replaceIINCWithReplacementCode(il, element);
224                 }
225             }
226         }
227         if (blockLastHandle.getInstruction() instanceof IINC) {
228             replaceIINCWithReplacementCode(il, blockLastHandle);
229             blockLastHandle = blockLastHandle.getNext().getNext().getNext();
230         }
231     }
232 
233     /*
234      * replaces the IINC instruction, element points to with code that looks
235      * like: iload lvn iconst increment iadd istore lvn
236      */
237     private void replaceIINCWithReplacementCode(InstructionList il,
238             InstructionHandle element) {
239         assert element.getInstruction() instanceof IINC;
240         IINC iinc = (IINC) element.getInstruction();
241         int increment = iinc.getIncrement();
242         int lvn = iinc.getIndex();
243         int sourceLine = getRegisteredMethod().getMethod().getLineNumberTable().getSourceLine(element.getPosition());
244         PseudoStore store = new PseudoStore(lvn, sourceLine);
245         il.append(element, store);
246         il.append(element, new IADD());
247         il.append(element, new ICONST(increment));
248         element.setInstruction(new ILOAD(lvn));
249     }
250 
251     /**
252      * generates the SSA form for this block. 
253      */
254     public void generateSSAForm() {
255         // make sure the instructionlist is in ssa compatible form.
256         // namely, redirect field instructions to local variable instructions
257         // and replace iinc with load and store instructions.
258         generateSSACompatibleForm();
259 
260         // iterate over the instructions of this block.
261         // insert phi-functions where necessary,
262         // replace loadinstruction indizes,
263         // replace storeinstruction indizes.
264 
265         InstructionHandle runningHandle = blockFirstHandle;
266         while (runningHandle != blockLastHandle.getNext()) {
267             Instruction instruction = runningHandle.getInstruction();
268             if (instruction instanceof LoadInstruction) {
269                 LoadInstruction load = (LoadInstruction) instruction;
270                 int index = getSSAIndex(load.getIndex());
271                 load.setIndex(index);
272             } else if (instruction instanceof StoreInstruction) {
273                 StoreInstruction store = (StoreInstruction) instruction;
274                 LocalVariableGen lvn = createNewLocalVariable(store.getIndex());
275                 putSSAIndex(store.getIndex(), lvn.getIndex());
276                 store.setIndex(lvn.getIndex());
277             }
278             runningHandle = runningHandle.getNext();
279         }
280     }
281 
282     /**
283      * this method will check if the SSA form can be finished. It first checks
284      * whether all predecessors are in SSA form, and if so, it will replace
285      * existing PhiDashFunctions with PhiFunctions.
286      */
287     public void tryFinishing() {
288         SsaBasicBlockWrapper[] preds = getPredecessorWrappers();
289         if (isPredecessorsInSSAForm(preds)) {
290             InstructionHandle runningHandle = blockFirstHandle;
291             while (runningHandle != blockLastHandle.getNext()) {
292                 if (runningHandle.getInstruction() instanceof PhiDashFunction
293                         && !(runningHandle.getInstruction() instanceof PhiFunction)) {
294                     PhiFunction phiF = new PhiFunction(
295                             (PhiDashFunction) runningHandle.getInstruction());
296                     for (int i = 0; i < preds.length; i++) {
297                         phiF.addPredecessorIndex(preds[i].getSSAIndex(phiF
298                                 .getOriginalIndex()));
299                     }
300                     runningHandle.setInstruction(phiF);
301                 }
302                 runningHandle = runningHandle.getNext();
303             }
304         }
305     }
306 
307     //  private boolean hasPhiDashFunctions() {
308     //      InstructionHandle runningHandle = blockFirstHandle;
309     //      while (runningHandle != blockLastHandle.getNext()) {
310     //          if (runningHandle.getInstruction() instanceof PhiDashFunction
311     //                  && !(runningHandle.getInstruction() instanceof PhiFunction)) {
312     //              return true;
313     //          }
314     //          runningHandle = runningHandle.getNext();
315     //      }
316     //        return false;
317     //    }
318 
319     protected int getSSAIndex(int index) {
320         Integer   iIndex = new Integer  (index);
321         if (indexMap.containsKey(iIndex)) {
322             return ((Integer  ) indexMap.get(iIndex)).intValue();
323         }
324         return generateSSAIndex(index);
325     }
326 
327     /**
328      * @param index
329      */
330     private int generateSSAIndex(int index) {
331         int result = Integer.MIN_VALUE;
332         SsaBasicBlockWrapper[] predecessors = getPredecessorWrappers();
333 
334         // check whether predecessors are in SSA form.
335         boolean predInSSA = isPredecessorsInSSAForm(predecessors);
336 
337         //      System.out.println("now getting index for " + index + " of block: " +
338         // blockFirstHandle.getPosition() + ":" + blockLastHandle.getPosition()
339         // + ". Predecessors
340         // are in ssa form: " + predInSSA);
341         if (predecessors.length == 0) {
342             result = index;
343             putSSAIndex(index, result);
344         } else if (predecessors.length == 1) {
345             result = predecessors[0].getSSAIndex(index);
346             putSSAIndex(index, result);
347         } else if (predInSSA) {
348             // if all predecessors are in SSA form, the index can be decided
349             // predecessors.length > 1
350             // alongside, we take the chance to replace existing Phi'-Functions
351             // with real Phi-Functions
352             PhiFunction phiFunction = new PhiFunction(index);
353             result = setReplacingLocalVariableForAbstractPhiFunction(index,
354                                                                         phiFunction);
355             putSSAIndex(index, result);
356             for (int i = 0; i < predecessors.length; i++) {
357                 phiFunction.addPredecessorIndex(predecessors[i]
358                         .getSSAIndex(index));
359             }
360         } else {
361             // If the predecessors are not in SSA form,
362             // we create a Phi'-Function that knows the original index of the
363             // variable and the local variable the variable is redirected to
364             // in this block.
365             PhiDashFunction phiDashFunction = new PhiDashFunction(index);
366             result = setReplacingLocalVariableForAbstractPhiFunction(index,
367                                                                         phiDashFunction);
368             putSSAIndex(index, result);
369         }
370         return result;
371     }
372 
373     /**
374      * @param index
375      * @param ssaIndex
376      */
377     private void putSSAIndex(int index, int ssaIndex) {
378         Integer   iIndex = new Integer  (index);
379         Integer   iResult = new Integer  (ssaIndex);
380         if (indexMap.containsKey(iIndex)) {
381             Integer   oldIndex = (Integer  ) indexMap.get(iIndex);
382             
383             assert oldIndex != null : 
384                 "null is not a valid mapping in the indexMap."; //$NON-NLS-1$
385             assert !oldIndex.equals(iResult) : 
386                 "put index found where the new index is already the " + //$NON-NLS-1$
387                 "mapping in the list."; //$NON-NLS-1$
388             
389             if (historyIndexMap == null) {
390                 historyIndexMap = new HashMap();
391             }
392             if (!historyIndexMap.containsKey(iIndex)) {
393                 historyIndexMap.put(iIndex, new ArrayList());
394             }
395             List oldIndices = (List) historyIndexMap.get(iIndex);
396             oldIndices.add(oldIndex);
397         }
398         indexMap.put(iIndex, iResult);
399     }
400 
401     /**
402      * @param predecessors
403      */
404     private boolean isPredecessorsInSSAForm(SsaBasicBlockWrapper[] predecessors) {
405         boolean predInSSA = true;
406         for (int i = 0; i < predecessors.length; i++) {
407             if (!predecessors[i].isSsaForm()) {
408                 predInSSA = false;
409             }
410         }
411         return predInSSA;
412     }
413 
414     /**
415      * @param index
416      * @param phiDashFunction
417      */
418     private int setReplacingLocalVariableForAbstractPhiFunction(int index,
419             PhiDashFunction phiDashFunction) {
420         int result;
421         phiDashFunction.setVariable(createNewLocalVariable(index));
422         weaveInPhiFunction(phiDashFunction);
423         result = phiDashFunction.getLocalVariable().getIndex();
424         return result;
425     }
426 
427     /**
428      * weaves in a code at the beginning of the block that symbolizes the phi
429      * function and the redirection of indizes. <br>
430      * redirects blockFirstHandle and the branch targeters to the begin of the
431      * phi function to ensure the block begins there.
432      * 
433      * @param phiFunction
434      */
435     private void weaveInPhiFunction(AbstractPhiFunction phiFunction) {
436         InstructionList il = methodGen.getInstructionList();
437         /*
438          * this inserts code like: 
439          * phifunction 
440          * //pseudo load 
441          * //store
442          * phifunction.variable
443          */
444         il.insert(blockFirstHandle, phiFunction);
445         //      il.insert(blockFirstHandle, InstructionFactory.createStore(
446         //              phiFunction.getLocalVariable().getType(),
447         //              phiFunction.getLocalVariable().getIndex()));
448 
449         //      InstructionHandle newBlockStart =
450         // blockFirstHandle.getPrev().getPrev();
451         InstructionHandle newBlockStart = blockFirstHandle.getPrev();
452 
453         // redirect targeters
454         if (blockFirstHandle.hasTargeters()) {
455             InstructionTargeter[] targeters = blockFirstHandle.getTargeters();
456             for (int i = 0; i < targeters.length; i++) {
457                 targeters[i].updateTarget(blockFirstHandle, newBlockStart);
458             }
459         }
460         // redirect blockFirstHandle
461         blockFirstHandle = newBlockStart;
462     }
463 
464     /**
465      * adds a new LocalVariable to the methodGen as replacement for the local
466      * variable with the given index and returns the new variable.
467      */
468     private LocalVariableGen createNewLocalVariable(int index) {
469 
470         LocalVariableGen lvn = getLocalVariableWithIndex(index);
471 
472         LocalVariableGen lvar = methodGen
473                 .addLocalVariable("ssaReplacementForLocalVariable" //$NON-NLS-1$
474                         + lvn.getName() + "[" + lvn.getIndex() + "]", lvn //$NON-NLS-1$ //$NON-NLS-2$
475                         .getType(), lvn.getStart(), lvn.getEnd());
476         return lvar;
477     }
478 
479     private LocalVariableGen getLocalVariableWithIndex(int index) {
480         LocalVariableGen[] lvns = methodGen.getLocalVariables();
481         LocalVariableGen lvn = null;
482         for (int i = 0; i < lvns.length; i++) {
483             if (lvns[i].getIndex() == index) {
484                 lvn = lvns[i];
485                 break;
486             }
487         }
488         assert lvn != null : "index not found in localvariabletable"; //$NON-NLS-1$
489         return lvn;
490     }
491     
492     /**
493      * creates a local variable that is the replacement of the field
494      * the given FieldInstruction points to.
495      */
496     private LocalVariableGen createLocalVariableAsFieldReplacement(FieldInstruction inst) {
497         ConstantPoolGen cpg = methodGen.getConstantPool();
498         LocalVariableGen lvar = methodGen
499                 .addLocalVariable("ssaReplacementForField "  //$NON-NLS-1$
500                                   + inst.getFieldName(cpg) + "[" //$NON-NLS-1$
501                                   + inst.getIndex() + "]", //$NON-NLS-1$
502                                   inst.getType(cpg),
503                                   methodGen.getInstructionList().getStart(),
504                                   methodGen.getInstructionList().getEnd());
505         return lvar;
506     }
507 
508     public SsaBasicBlockWrapper[] getPredecessorWrappers() {
509         BasicBlock[] predecessors = wrappedBasicBlock.getPredecessors();
510         SsaBasicBlockWrapper[] wrappers = new SsaBasicBlockWrapper[predecessors.length];
511         for (int i = 0; i < wrappers.length; i++) {
512             wrappers[i] = (SsaBasicBlockWrapper) basicBlockMap
513                     .get(predecessors[i]);
514         }
515         return wrappers;
516     }
517 
518     protected SsaBasicBlockWrapper[] getSuccessorWrappers() {
519         BasicBlock[] succs = wrappedBasicBlock.getSuccessors();
520         SsaBasicBlockWrapper[] wrappers = new SsaBasicBlockWrapper[succs.length];
521         for (int i = 0; i < wrappers.length; i++) {
522             wrappers[i] = (SsaBasicBlockWrapper) basicBlockMap.get(succs[i]);
523         }
524         return wrappers;
525     }
526 
527     protected void triggerSSAForm() {
528         ssaForm = true;
529     }
530 
531     /**
532      * @return returns the Instruction handles for this block.
533      */
534     InstructionHandle[] getInstructionHandles() {
535         List ihs = new ArrayList();
536         InstructionHandle runner = blockFirstHandle;
537         while (runner != blockLastHandle.getNext()) {
538             ihs.add(runner);
539             runner = runner.getNext();
540         }
541         return (InstructionHandle[]) ihs.toArray(new InstructionHandle[ihs.size()]);
542     }
543 
544     /**
545      * returns a list of keys that map to the given value.
546      * 
547      * @param value
548      */
549     List getKeys(Integer   value) {
550         assert value != null : "value must not be null"; //$NON-NLS-1$
551         Collection values = indexMap.keySet();
552         List result = new ArrayList();
553         for (Iterator iter = values.iterator(); iter.hasNext();) {
554             Integer   cv = (Integer  ) iter.next();
555             if (value.equals(indexMap.get(cv))) {
556                 result.add(cv);
557             }
558         }
559         return result;
560     }
561     
562     Integer  [] getIndexHistory(Integer   originalIndex) {
563         if (historyIndexMap == null) {
564             return new Integer  [] {};
565         } 
566         List history = (List) historyIndexMap.get(originalIndex);
567         if (history == null) {
568             return new Integer  [] {};
569         }
570         return (Integer  []) history.toArray(new Integer  [history.size()]);
571     }
572     
573     /**
574      * @param basicBlockMap
575      */
576     public void setBasicBlockMap(Map basicBlockMap) {
577         this.basicBlockMap = basicBlockMap;
578     }
579 
580     protected BasicBlock getWrappedBasicBlock() {
581         return wrappedBasicBlock;
582     }
583 
584     protected void setFieldMap(Map fieldMap) {
585         this.fieldMap = fieldMap;
586     }
587     public String   toString() {
588         return "SSABasicBlockWrapper wrapping: " + wrappedBasicBlock.toString(); //$NON-NLS-1$
589     }
590     protected MethodGen getMethodGen() {
591         return methodGen;
592     }
593     public boolean equals(Object   obj) {
594         return wrappedBasicBlock.equals(obj);
595     }
596 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags