View Javadoc

1   // BasicBlock.java, created Fri Jan 11 16:42:38 2002 by joewhaley
2   // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.Quad;
5   
6   import java.util.Collection;
7   import java.util.Iterator;
8   import joeq.Compiler.Quad.Operand.RegisterOperand;
9   import joeq.Compiler.Quad.Operator.Move;
10  import joeq.Compiler.Quad.Operator.Ret;
11  import joeq.Util.Templates.List;
12  import joeq.Util.Templates.ListIterator;
13  import joeq.Util.Templates.ListWrapper;
14  import joeq.Util.Templates.UnmodifiableList;
15  import jwutil.collections.BackwardIterator;
16  import jwutil.strings.Strings;
17  import jwutil.util.Assert;
18  
19  /***
20   * Represents a basic block in the quad intermediate representation.
21   * Basic blocks are single-entry regions, but not necessarily single-exit regions
22   * due to the fact that control flow may exit a basic block early due to a
23   * run time exception.  That is to say, a potential exception point does not
24   * end a basic block.
25   *
26   * Each basic block contains a list of quads, a list of predecessors, a list of
27   * successors, and a list of exception handlers.  It also has an id number that
28   * is unique within its control flow graph, and some flags.
29   *
30   * You should never create a basic block directly.  You should create one via a
31   * ControlFlowGraph so that the id number is correct.
32   *
33   * @author  John Whaley <jwhaley@alum.mit.edu>
34   * @see  Quad
35   * @see  ControlFlowGraph
36   * @see  ExceptionHandlerList
37   * @version  $Id: BasicBlock.java 2465 2006-06-07 23:03:17Z joewhaley $
38   */
39  
40  public class BasicBlock {
41  
42      /*** Unique id number for this basic block. */
43      private int id_number;
44      /*** List of instructions. */
45      private final java.util.List/*<Quad>*/ instructions;
46      /*** List of successor basic blocks. */
47      private final java.util.List/*<BasicBlock>*/ successors;
48      /*** List of predecessor basic blocks. */
49      private final java.util.List/*<BasicBlock>*/ predecessors;
50      
51      /*** List of exception handlers for this basic block. */
52      private ExceptionHandlerList exception_handler_list;
53      
54      /*** Flags for this basic block. */
55      private int flags;
56      
57      /*** Exception handler entry point. */
58      private static final int EXCEPTION_HANDLER_ENTRY = 0x1;
59      /*** JSR subroutine entry point. */
60      private static final int JSR_ENTRY = 0x2;
61      
62      /*** Creates new entry node. Only to be called by ControlFlowGraph. */
63      static BasicBlock createStartNode() {
64          return new BasicBlock();
65      }
66      /*** Private constructor for the entry node. */
67      private BasicBlock() {
68          this.id_number = 0;
69          this.instructions = null;
70          this.predecessors = null;
71          this.successors = new java.util.ArrayList(1);
72          this.exception_handler_list = null;
73      }
74      /*** Creates new exit node */
75      static BasicBlock createEndNode(int numOfPredecessors) {
76          return new BasicBlock(numOfPredecessors);
77      }
78      /*** Private constructor for the exit node. */
79      private BasicBlock(int numOfExits) {
80          this.id_number = 1;
81          this.instructions = null;
82          this.successors = null;
83          this.predecessors = new java.util.ArrayList(numOfExits);
84          this.exception_handler_list = null;
85      }
86      /*** Create new basic block with no exception handlers.
87       * Only to be called by ControlFlowGraph. */
88      static BasicBlock createBasicBlock(int id, int numOfPredecessors, int numOfSuccessors, int numOfInstructions) {
89          return new BasicBlock(id, numOfPredecessors, numOfSuccessors, numOfInstructions, null);
90      }
91      /*** Create new basic block with the given exception handlers.
92       * Only to be called by ControlFlowGraph. */
93      static BasicBlock createBasicBlock(int id, int numOfPredecessors, int numOfSuccessors, int numOfInstructions, ExceptionHandlerList ehs) {
94          return new BasicBlock(id, numOfPredecessors, numOfSuccessors, numOfInstructions, ehs);
95      }
96      /*** Private constructor for internal nodes. */
97      private BasicBlock(int id, int numOfPredecessors, int numOfSuccessors, int numOfInstructions,
98                         ExceptionHandlerList ehs) {
99          this.id_number = id;
100         this.predecessors = new java.util.ArrayList(numOfPredecessors);
101         this.successors = new java.util.ArrayList(numOfSuccessors);
102         this.instructions = new java.util.ArrayList(numOfInstructions);
103         this.exception_handler_list = ehs;
104     }
105 
106     /*** Returns true if this is the entry basic block.
107      * @return  true if this is the entry basic block. */
108     public boolean isEntry() { return predecessors == null; }
109     /*** Returns true if this is the exit basic block.
110      * @return  true if this is the exit basic block. */
111     public boolean isExit() { return successors == null; }
112     
113     /*** Returns an iterator over the quads in this basic block in forward order.
114      * @return  an iterator over the quads in this basic block in forward order. */
115     public ListIterator.Quad iterator() {
116         if (instructions == null) return ListWrapper.Quad.EmptyIterator.INSTANCE;
117         return new ListWrapper.Quad.Iterator(instructions.listIterator());
118     }
119     
120     /*** Returns an iterator over the quads in this basic block in backward order.
121      * @return  an iterator over the quads in this basic block in backward order. */
122     public ListIterator.Quad backwardIterator() {
123         if (instructions == null) return ListWrapper.Quad.EmptyIterator.INSTANCE;
124         return new ListWrapper.Quad.Iterator(new BackwardIterator(instructions.listIterator()));
125     }
126 
127     /*** Visit all of the quads in this basic block in forward order
128      * with the given quad visitor.
129      * @see  QuadVisitor
130      * @param qv  QuadVisitor to visit the quads with. */
131     public void visitQuads(QuadVisitor qv) {
132         for (ListIterator.Quad i = iterator(); i.hasNext(); ) {
133             Quad q = i.nextQuad();
134             q.accept(qv);
135         }
136     }
137     
138     /*** Visit all of the quads in this basic block in backward order
139      * with the given quad visitor.
140      * @see  QuadVisitor
141      * @param qv  QuadVisitor to visit the quads with. */
142     public void backwardVisitQuads(QuadVisitor qv) {
143         for (ListIterator.Quad i = backwardIterator(); i.hasNext(); ) {
144             Quad q = i.nextQuad();
145             q.accept(qv);
146         }
147     }
148     
149     /*** Returns the number of quads in this basic block.
150      * @return  the number of quads in this basic block. */
151     public int size() {
152         if (instructions == null) return 0; // entry or exit block
153         return instructions.size();
154     }
155     
156     public Quad getQuad(int i) {
157         return (Quad)instructions.get(i);
158     }
159     
160     public Quad getLastQuad() {
161         if (size() == 0) return null;
162         return (Quad)instructions.get(instructions.size()-1);
163     }
164 
165     public int getQuadIndex(Quad q) {
166         return instructions == null ? -1 : instructions.indexOf(q);
167     }
168     
169     public Quad removeQuad(int i) {
170         return (Quad)instructions.remove(i);
171     }
172     
173     public boolean removeQuad(Quad q) {
174         return instructions.remove(q);
175     }
176     
177     public void removeAllQuads() {
178         instructions.clear();
179     }
180     
181     /*** Add a quad to this basic block at the given location.
182      * Cannot add quads to the entry or exit basic blocks.
183      * @param index  the index to add the quad
184      * @param q  quad to add */
185     public void addQuad(int index, Quad q) {
186         Assert._assert(instructions != null, "Cannot add instructions to entry/exit basic block");
187         instructions.add(index, q);
188     }
189     /*** Append a quad to the end of this basic block.
190      * Cannot add quads to the entry or exit basic blocks.
191      * @param q  quad to add */
192     public void appendQuad(Quad q) {
193         Assert._assert(instructions != null, "Cannot add instructions to entry/exit basic block");
194         instructions.add(q);
195     }
196     
197     /***
198      * Replace the quad at position pos.
199      * */
200     public void replaceQuad(int pos, Quad q) {
201         Assert._assert(instructions != null, "Cannot add instructions to entry/exit basic block");
202         instructions.set(pos, q);
203     }
204     
205     /*** Add a predecessor basic block to this basic block.
206      * Cannot add predecessors to the entry basic block.
207      * @param b  basic block to add as a predecessor */
208     public void addPredecessor(BasicBlock b) {
209         Assert._assert(predecessors != null, "Cannot add predecessor to entry basic block");
210         predecessors.add(b);
211     }
212     /*** Add a successor basic block to this basic block.
213      * Cannot add successors to the exit basic block.
214      * @param b  basic block to add as a successor */
215     public void addSuccessor(BasicBlock b) {
216         Assert._assert(successors != null, "Cannot add successor to exit basic block");
217         successors.add(b);
218     }
219     
220     public boolean removePredecessor(BasicBlock bb) {
221         Assert._assert(predecessors != null, "Cannot remove predecessor from entry basic block");
222         return predecessors.remove(bb);
223     }
224     public void removePredecessor(int i) {
225         Assert._assert(predecessors != null, "Cannot remove predecessor from entry basic block");
226         predecessors.remove(i);
227     }
228     public boolean removePredecessors(Collection bb) {
229         Assert._assert(predecessors != null, "Cannot remove predecessor from entry basic block");
230         return predecessors.removeAll(bb);
231     }
232     public boolean removeSuccessor(BasicBlock bb) {
233         Assert._assert(successors != null, "Cannot remove successor from exit basic block");
234         return successors.remove(bb);
235     }
236     public void removeSuccessor(int i) {
237         Assert._assert(successors != null, "Cannot remove successor from exit basic block");
238         successors.remove(i);
239     }
240     public void removeAllPredecessors() {
241         Assert._assert(predecessors != null, "Cannot remove predecessors from entry basic block");
242         predecessors.clear();
243     }
244     public void removeAllSuccessors() {
245         Assert._assert(successors != null, "Cannot remove successors from exit basic block");
246         successors.clear();
247     }
248         
249     public int getNumberOfSuccessors() {
250         if (successors == null) return 0;
251         return successors.size();
252     }
253 
254     public int getNumberOfPredecessors() {
255         if (predecessors == null) return 0;
256         return predecessors.size();
257     }
258 
259     /*** Returns the fallthrough successor to this basic block, if it exists.
260      * If there is none, returns null.
261      * @return  the fallthrough successor, or null if there is none. */
262     public BasicBlock getFallthroughSuccessor() {
263         if (successors == null) return null;
264         return (BasicBlock)successors.get(0);
265     }
266 
267     /*** Returns the fallthrough predecessor to this basic block, if it exists.
268      * If there is none, returns null.
269      * @return  the fallthrough predecessor, or null if there is none. */
270     public BasicBlock getFallthroughPredecessor() {
271         if (predecessors == null) return null;
272         return (BasicBlock)predecessors.get(0);
273     }
274 
275     /*** Returns a list of the successors of this basic block.
276      * @return  a list of the successors of this basic block. */
277     public List.BasicBlock getSuccessors() {
278         if (successors == null) return UnmodifiableList.BasicBlock.getEmptyList();
279         return new ListWrapper.BasicBlock(successors);
280     }
281     
282     /*** Returns an list of the predecessors of this basic block.
283      * @return  an iterator of the predecessors of this basic block. */
284     public List.BasicBlock getPredecessors() {
285         if (predecessors == null) return UnmodifiableList.BasicBlock.getEmptyList();
286         return new ListWrapper.BasicBlock(predecessors);
287     }
288     
289     void addExceptionHandler_first(ExceptionHandlerList eh) {
290         eh.getHandler().addHandledBasicBlock(this);
291         Assert._assert(eh.parent == null);
292         eh.parent = this.exception_handler_list;
293         this.exception_handler_list = eh;
294     }
295     ExceptionHandlerList addExceptionHandler(ExceptionHandlerList eh) {
296         eh.getHandler().addHandledBasicBlock(this);
297         if (eh.parent == this.exception_handler_list)
298             return this.exception_handler_list = eh;
299         else
300             return this.exception_handler_list = new ExceptionHandlerList(eh.getHandler(), this.exception_handler_list);
301     }
302     void setExceptionHandlerList(ExceptionHandlerList ehl) {
303         this.exception_handler_list = ehl;
304     }
305     
306     /*** Returns the list of exception handlers that guard this basic block.
307      * @see ExceptionHandlerList
308      * @return  an iterator of the exception handlers that guard this basic block. */
309     public ExceptionHandlerList getExceptionHandlers() {
310         if (exception_handler_list == null) return ExceptionHandlerList.getEmptyList();
311         return exception_handler_list;
312     }
313 
314     /*** Appends the list of exception handlers to the current list of
315      * exception handlers. Doesn't append if it is already there.
316      */
317     public void appendExceptionHandlerList(ExceptionHandlerList list) {
318         if (list == null || list.size() == 0) return;
319         ExceptionHandlerList p = this.exception_handler_list;
320         if (p == null) {
321             this.exception_handler_list = list; return;
322         }
323         for (;;) {
324             if (p == list) return;
325             ExceptionHandlerList q = p.getParent();
326             if (q == null) {
327                 p.setParent(list); return;
328             }
329             p = q;
330         }
331     }
332     
333     /*** Returns the unique id number for this basic block.
334      * @return  the unique id number for this basic block. */
335     public int getID() { return id_number; }
336 
337     public List.BasicBlock getExceptionHandlerEntries() {
338         if (exception_handler_list == null) return UnmodifiableList.BasicBlock.getEmptyList();
339         java.util.ArrayList result = new java.util.ArrayList(exception_handler_list.size());
340         for (ListIterator.ExceptionHandler i = exception_handler_list.exceptionHandlerIterator();
341              i.hasNext(); ) {
342             ExceptionHandler eh = i.nextExceptionHandler();
343             result.add(eh.getEntry());
344         }
345         return new ListWrapper.BasicBlock(result);
346     }
347     
348     /*** Returns true if this basic block has been marked as an exception handler
349      * entry point.  Returns false otherwise.
350      * @return  if this basic block has been marked as an exception handler entry point. */
351     public boolean isExceptionHandlerEntry() { return (flags & EXCEPTION_HANDLER_ENTRY) != 0; }
352     /*** Marks this basic block as an exception handler entry point.
353      */
354     public void setExceptionHandlerEntry() { flags |= EXCEPTION_HANDLER_ENTRY; }
355     
356     /*** Returns true if this basic block has been marked as a JSR entry.
357      * entry point.  Returns false otherwise.
358      * @return  if this basic block has been marked as a JSR entry. */
359     public boolean isJSREntry() { return (flags & JSR_ENTRY) != 0; }
360     /*** Marks this basic block as a JSR entry.
361      */
362     public void setJSREntry() { flags |= JSR_ENTRY; }
363     
364     public boolean endsInRet() {
365         Quad last = getLastQuad();
366         if (last == null) return false;
367         return last.getOperator() == Ret.RET.INSTANCE;
368     }
369     
370     public void appendQuadBeforeBranchOrPEI(Quad c) {
371         java.util.ListIterator li = instructions.listIterator();
372         while (li.hasNext()) li.next();
373         while (li.hasPrevious()) {
374             Quad q = (Quad) li.previous();
375             if (q.getOperator() instanceof Operator.Branch) continue;
376             if (!q.getThrownExceptions().isEmpty()) continue;
377             break;
378         }
379         li.add(c);
380     }
381     
382     /*** Returns the name of this basic block.
383      * @return  the name of this basic block. */
384     public String toString() {
385         if (isEntry()) {
386             Assert._assert(getID() == 0);
387             return "BB0 (ENTRY)";
388         }
389         if (isExit()) {
390             Assert._assert(getID() == 1);
391             return "BB1 (EXIT)";
392         }
393         return "BB"+getID();
394     }
395     
396     public void addAtEnd(ControlFlowGraph ir, Quad c) {
397         appendQuadBeforeBranchOrPEI(c);
398         RegisterOperand aux = null;
399         RegisterOperand lhs = Move.getDest(c);
400         java.util.ListIterator li = this.instructions.listIterator();
401         while (li.next() != c) ;
402         while (li.hasNext()) {
403             Quad i = (Quad) li.next();
404             for (Iterator os = i.getUsedRegisters().iterator(); os.hasNext(); ) {
405                 Operand op = (Operand) os.next();
406                 if (lhs.isSimilar(op)) {
407                     if (aux == null) {
408                         aux = ir.getRegisterFactory().makeRegOp(lhs.getRegister(), lhs.getType());
409                         Quad m = Move.create(ir.getNewQuadID(), aux.getRegister(), lhs.getRegister(), lhs.getType());
410                         int index = instructions.indexOf(c);
411                         instructions.add(index, m);
412                     }
413                     ((RegisterOperand)op).setRegister(aux.getRegister());
414                 }
415             }
416         }
417     }
418     /*** Returns a String describing the name, predecessor, successor, exception
419      * handlers, and quads of this basic block.
420      * @return  a verbose string describing this basic block */    
421     public String fullDump() {
422         StringBuffer sb = new StringBuffer();
423         sb.append(toString());
424         sb.append("\t(in: ");
425         ListIterator.BasicBlock bbi = getPredecessors().basicBlockIterator();
426         if (!bbi.hasNext()) sb.append("<none>");
427         else {
428             sb.append(bbi.nextBasicBlock().toString());
429             while (bbi.hasNext()) {
430                 sb.append(", ");
431                 sb.append(bbi.nextBasicBlock().toString());
432             }
433         }
434         sb.append(", out: ");
435         bbi = getSuccessors().basicBlockIterator();
436         if (!bbi.hasNext()) sb.append("<none>");
437         else {
438             sb.append(bbi.nextBasicBlock().toString());
439             while (bbi.hasNext()) {
440                 sb.append(", ");
441                 sb.append(bbi.nextBasicBlock().toString());
442             }
443         }
444         sb.append(')');
445         ListIterator.ExceptionHandler ehi = getExceptionHandlers().exceptionHandlerIterator();
446         if (ehi.hasNext()) {
447             sb.append(Strings.lineSep+"\texception handlers: ");
448             sb.append(ehi.next().toString());
449             while (ehi.hasNext()) {
450                 sb.append(", ");
451                 sb.append(ehi.next().toString());
452             }
453         }
454         sb.append(Strings.lineSep);
455         ListIterator.Quad qi = iterator();
456         while (qi.hasNext()) {
457             sb.append(qi.nextQuad().toString());
458             sb.append(Strings.lineSep);
459         }
460         sb.append(Strings.lineSep);
461         return sb.toString();
462     }
463     
464 }