SPatchingChain


1   /* Soot - a J*va Optimization Framework
2    * Copyright (C) 2003 Navindra Umanee <navindra@cs.mcgill.ca>
3    *
4    * This library is free software; you can redistribute it and/or
5    * modify it under the terms of the GNU Lesser General Public
6    * License as published by the Free Software Foundation; either
7    * version 2.1 of the License, or (at your option) any later version.
8    *
9    * This library is distributed in the hope that it will be useful,
10   * but WITHOUT ANY WARRANTY; without even the implied warranty of
11   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12   * Lesser General Public License for more details.
13   *
14   * You should have received a copy of the GNU Lesser General Public
15   * License along with this library; if not, write to the
16   * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17   * Boston, MA 02111-1307, USA.
18   */
19  
20  package soot.shimple.internal;
21  
22  import soot.*;
23  import soot.options.Options;
24  import soot.util.*;
25  import soot.shimple.*;
26  import java.util.*;
27  
28  /**
29   * Internal Shimple extension of PatchingChain.
30   *
31   * @author Navindra Umanee
32   * @see soot.PatchingChain
33   **/
34  public class SPatchingChain extends PatchingChain
35  {
36      /**
37       * Needed to find non-trapped Units of the body.
38       **/
39      Body body = null;
40      boolean debug;
41      
42      public SPatchingChain(Body aBody, Chain aChain)
43      {
44          super(aChain);
45          this.body = aBody;
46          this.debug = Options.v().debug();
47          if(aBody instanceof ShimpleBody)
48              debug |= ((ShimpleBody)aBody).getOptions().debug();
49      }
50  
51      public boolean add(Object   o)
52      {
53          processPhiNode(o);
54          return super.add(o);
55      }
56  
57      public void swapWith(Object   out, Object   in)
58      {
59          // Ensure that branching statements are swapped correctly.
60          // The normal swapWith implementation would still work
61          // correctly but redirectToPreds performed during the remove
62          // would be more expensive and might print warnings if no
63          // actual CFG predecessors for out was found due to the
64          // insertion of branching statement in.
65          processPhiNode(in);
66          Shimple.redirectPointers((Unit) out, (Unit) in);
67          super.insertBefore(in, out);
68          super.remove(out);
69      }
70      
71      public void insertAfter(Object   toInsert, Object   point)
72      {
73          // important to do these before the patching, so that
74          // computeNeedsPatching works properly
75          processPhiNode(toInsert);
76          super.insertAfter(toInsert, point);
77  
78          Unit unit = (Unit) point;
79  
80          // update any pointers from Phi nodes only if the unit
81          // being inserted is in the same basic block as point, or if
82          // control flows through to the Phi node
83          patchpointers:
84          {
85              // no need to move the pointers
86              if(!unit.fallsThrough())
87                  break patchpointers;
88  
89              // move pointers unconditionally, needed as a special case
90              if(!unit.branches()){
91                  Set trappedUnits = Collections.EMPTY_SET;
92                  if(body != null)
93                      trappedUnits = TrapManager.getTrappedUnitsOf(body);
94                  if(!trappedUnits.contains(unit)){
95                      Shimple.redirectPointers(unit, (Unit) toInsert);
96                      break patchpointers;
97                  }
98              }
99              
100             /* handle each UnitBox individually */
101 
102             Object  [] boxes = unit.getBoxesPointingToThis().toArray();
103 
104             for(int i = 0; i < boxes.length; i++){
105                 UnitBox ub = (UnitBox) boxes[i];
106 
107                 if(ub.getUnit() != unit)
108                     throw new RuntimeException  ("Assertion failed.");
109                 if(ub.isBranchTarget())
110                     continue;
111 
112                 SUnitBox box = getSBox(ub);
113                 Boolean   needsPatching = (Boolean  ) boxToNeedsPatching.get(box);
114                 
115                 if(needsPatching == null || box.isUnitChanged()){
116                     // if boxes were added or removed to the known Phi
117                     if(!boxToPhiNode.containsKey(box)){
118                         reprocessPhiNodes();
119 
120                         // *** FIXME: Disabling this allows us to have
121                         // PiExpr that have UnitBox pointers.
122                         // I think this means that any changes 
123                         // to the relevant Unit will be ignored by
124                         //  SPatchingChain.
125                         //
126                         // Hopefully this also means that any
127                         // transformation that moves/removes/modifies
128                         // a Unit pointed at by a PiExpr knows what
129                         // it's doing.
130                         if(!boxToPhiNode.containsKey(box) && debug)
131                             throw new RuntimeException  ("SPatchingChain has pointers from a Phi node that has never been seen.");
132                     }
133                     
134                     computeNeedsPatching();
135                     needsPatching = (Boolean  ) boxToNeedsPatching.get(box);
136 
137                     if(needsPatching == null){
138                         // maybe the user forgot to clearUnitBoxes()
139                         // when removing a Phi node, or the user removed
140                         // a Phi node and hasn't put it back yet
141                         if(debug)
142                             G.v().out.println("Warning: Orphaned UnitBox to " + unit + "?  SPatchingChain will not move the pointer.");
143                         continue;
144                     }
145                 }
146                     
147                 if(needsPatching.booleanValue()){
148                     box.setUnit((Unit)toInsert);
149                     box.setUnitChanged(false);
150                 }
151             }
152         }
153     }
154 
155     public void insertAfter(List toInsert, Object   point)
156     {
157         processPhiNode(toInsert);
158         super.insertAfter(toInsert, point);
159     }
160     
161     public void insertBefore(List toInsert, Object   point)
162     {
163         processPhiNode(toInsert);
164         super.insertBefore(toInsert, point);
165     }
166 
167     public void insertBefore(Object   toInsert, Object   point)
168     {
169         processPhiNode(toInsert);
170         super.insertBefore(toInsert, point);
171     }
172 
173     public void addFirst(Object   u)
174     {
175         processPhiNode(u);
176         super.addFirst(u);
177     }
178     
179     public void addLast(Object   u)
180     {
181         processPhiNode(u);
182         super.addLast(u);
183     }
184 
185     public boolean remove(Object   obj)
186     {
187         if(contains(obj)){
188             Shimple.redirectToPreds(body, (Unit)obj);
189         }
190         
191         return super.remove(obj);
192     }
193     
194     /**
195      * Map from UnitBox to the Phi node owning it.
196      **/
197     protected Map boxToPhiNode = new HashMap();
198 
199     /**
200      * Flag that indicates whether control flow falls through from the
201      * box to the Phi node.  null indicates we probably need a call to
202      * computeInternal().
203      **/
204     protected Map boxToNeedsPatching = new HashMap();
205 
206     
207     protected void processPhiNode(Object   o)
208     {
209         Unit phiNode = (Unit) o;
210         PhiExpr phi = Shimple.getPhiExpr(phiNode);
211 
212         // not a Phi node
213         if(phi == null)
214             return;
215 
216         // already processed previously, unit chain manipulations?
217         if(boxToPhiNode.values().contains(phiNode))
218             return;
219 
220         Iterator boxesIt = phi.getUnitBoxes().iterator();
221         while(boxesIt.hasNext()){
222             UnitBox box = (UnitBox) boxesIt.next();
223             boxToPhiNode.put(box, phiNode);
224         }
225     }
226 
227     protected void reprocessPhiNodes()
228     {
229         Set phiNodes = new HashSet(boxToPhiNode.values());
230         boxToPhiNode = new HashMap();
231         boxToNeedsPatching = new HashMap();
232 
233         Iterator phiNodesIt = phiNodes.iterator();
234         while(phiNodesIt.hasNext())
235             processPhiNode(phiNodesIt.next());
236     }
237     
238     /**
239      * NOTE: This will *miss* all the Phi nodes outside a chain.  So
240      * make sure you know what you are doing if you remove a Phi node
241      * from a chain and don't put it back or call clearUnitBoxes() on
242      * it.
243      **/
244     protected void computeNeedsPatching()
245     {
246         {
247             Set boxes = boxToPhiNode.keySet();
248 
249             if(boxes.isEmpty())
250                 return;
251         }
252 
253         // we track the fallthrough control flow from boxes to the
254         // corresponding Phi statements.  trackedPhi provides a
255         // mapping from the Phi being tracked to its relevant boxes.
256         MultiMap trackedPhiToBoxes = new HashMultiMap();
257 
258         // consider:
259         //
260         // if blah goto label1
261         // label1:
262         //
263         // Here control flow both fallsthrough and branches to label1.
264         // If such an if statement is encountered, we do not want to
265         // move any UnitBox pointers beyond the if statement.
266         Set trackedBranchTargets = new HashSet();
267         
268         Iterator unitsIt = iterator();
269         while(unitsIt.hasNext()){
270             Unit u = (Unit) unitsIt.next();
271 
272             // update trackedPhiToBoxes
273             List boxesToTrack = u.getBoxesPointingToThis();
274             if(boxesToTrack != null){
275                 Iterator boxesToTrackIt = boxesToTrack.iterator();
276                 while(boxesToTrackIt.hasNext()){
277                     UnitBox boxToTrack = (UnitBox) boxesToTrackIt.next();
278 
279                     if(!boxToTrack.isBranchTarget())
280                         trackedPhiToBoxes.put(boxToPhiNode.get(boxToTrack),
281                                               boxToTrack);
282                 }
283             }
284 
285             // update trackedBranchTargets
286             if(u.fallsThrough() && u.branches())
287                 trackedBranchTargets.addAll(u.getUnitBoxes());
288             
289             // the tracked Phi nodes may be reached through branching.
290             // (note: if u is a Phi node and not a trackedBranchTarget,
291             // this is not triggered since u would fall through in that
292             // case.)
293             if(!u.fallsThrough() || trackedBranchTargets.contains(u)){
294                 Iterator boxesIt = trackedPhiToBoxes.values().iterator();
295                 while(boxesIt.hasNext()){
296                     SUnitBox box = getSBox(boxesIt.next());
297                     boxToNeedsPatching.put(box, Boolean.FALSE);
298                     box.setUnitChanged(false);
299                 }
300 
301                 trackedPhiToBoxes = new HashMultiMap();
302                 continue;
303             }
304 
305             // we found one of the Phi nodes pointing to a Unit
306             Set boxes = trackedPhiToBoxes.get(u);
307             if(boxes != null){
308                 Iterator boxesIt = boxes.iterator();
309                 while(boxesIt.hasNext()){
310                     SUnitBox box = getSBox(boxesIt.next());
311 
312                     // falls through
313                     boxToNeedsPatching.put(box, Boolean.TRUE);
314                     box.setUnitChanged(false);
315                 }
316 
317                 trackedPhiToBoxes.remove(u);
318             }
319         }
320 
321         // after the iteration, the rest do not fall through
322         Iterator boxesIt = trackedPhiToBoxes.values().iterator();
323         while(boxesIt.hasNext()){
324             SUnitBox box = getSBox(boxesIt.next());
325             boxToNeedsPatching.put(box, Boolean.FALSE);
326             box.setUnitChanged(false);
327         }
328     }
329 
330     protected SUnitBox getSBox(Object   box)
331     {
332         if(!(box instanceof SUnitBox))
333             throw new RuntimeException  ("Shimple box not an SUnitBox?");
334 
335         return (SUnitBox) box;
336     }
337 
338     protected class SPatchingIterator extends PatchingIterator
339     {
340         SPatchingIterator(Chain innerChain)
341         {
342             super(innerChain);
343         }
344 
345         SPatchingIterator(Chain innerChain, Object   u)
346         {
347             super(innerChain, u);
348         }
349 
350         SPatchingIterator(Chain innerChain, Object   head, Object   tail)
351         {
352             super(innerChain, head, tail);
353         }
354         
355         public void remove()
356         {
357             Unit victim = (Unit) lastObject;
358             
359             if(!state)
360                 throw new IllegalStateException  ("remove called before first next() call");
361             Shimple.redirectToPreds(SPatchingChain.this.body, victim);
362 
363             // work around for inadequate inner class support in javac 1.2
364             // super.remove();
365             Unit successor;
366 
367             if((successor = (Unit)getSuccOf(victim)) == null)
368                 successor = (Unit)getPredOf(victim);
369 
370             innerIterator.remove();
371             victim.redirectJumpsToThisTo(successor);
372         }
373     }
374 
375     public Iterator iterator()
376     {
377         return new SPatchingIterator(innerChain);
378     }
379 
380     public Iterator iterator(Object   u)
381     {
382         return new SPatchingIterator(innerChain, u);
383     }
384 
385     public Iterator iterator(Object   head, Object   tail)
386     {
387         return new SPatchingIterator(innerChain, head, tail);
388     }
389 }
390
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags