View Javadoc

1   // ControlDependence.java, created Wed Jan 30 22:31:58 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.Iterator;
7   import joeq.Class.jq_Method;
8   import joeq.Class.jq_MethodVisitor;
9   import joeq.Compiler.Quad.Operand.AConstOperand;
10  import joeq.Compiler.Quad.Operand.ConditionOperand;
11  import joeq.Compiler.Quad.Operand.FieldOperand;
12  import joeq.Compiler.Quad.Operand.IConstOperand;
13  import joeq.Compiler.Quad.Operator.Getfield;
14  import joeq.Compiler.Quad.Operator.IntIfCmp;
15  import joeq.Compiler.Quad.Operator.Return;
16  import joeq.Util.Templates.List;
17  import joeq.Util.Templates.ListIterator;
18  
19  /***
20   *
21   * @author  John Whaley <jwhaley@alum.mit.edu>
22   * @version $Id: ControlDependence.java 1931 2004-09-22 22:17:47Z joewhaley $
23   */
24  public class ControlDependence extends jq_MethodVisitor.EmptyVisitor {
25  
26      jq_Method current_method;
27      
28      public void visitMethod(jq_Method m) {
29          if (m.getBytecode() == null) return;
30          System.out.println("Visiting method "+m);
31          current_method = m;
32          ControlFlowGraph cfg = joeq.Compiler.Quad.CodeCache.getCode(m);
33          Dominators dom = new Dominators(false);
34          dom.visitMethod(m);
35          Dominators.DominatorNode root = dom.computeTree();
36          
37          // find blocks that end in a throw statement.
38          ListIterator.BasicBlock li = cfg.exit().getPredecessors().basicBlockIterator();
39          while (li.hasNext()) {
40              BasicBlock bb = li.nextBasicBlock();
41              Quad q = bb.getLastQuad();
42              if (q == null) {
43                  System.out.println("NOTE! empty basic block "+bb+" goes to exit");
44                  continue;
45              }
46              if (q.getOperator() == Return.THROW_A.INSTANCE) {
47                  System.out.println("Found throw statement in "+bb+"! "+q);
48                  // find control dependence
49                  Dominators.DominatorNode dn = getDomNode(root, bb);
50                  findControlDependence(dn, root);
51              }
52          }
53      }
54  
55      static Dominators.DominatorNode getDomNode(Dominators.DominatorNode p, BasicBlock bb) {
56          if (p.getBasicBlock() == bb) return p;
57          Iterator i = p.getChildren().iterator();
58          while (i.hasNext()) {
59              Dominators.DominatorNode x = getDomNode((Dominators.DominatorNode)i.next(), bb);
60              if (x != null) return x;
61          }
62          return null;
63      }
64  
65      void findControlDependence(Dominators.DominatorNode p, Dominators.DominatorNode root) {
66          Iterator i = p.getChildren().iterator();
67          if (!i.hasNext()) {
68              if (p.getBasicBlock().isEntry()) {
69                  System.out.println("Post-dominates entry "+p);
70                  return;
71              }
72              //System.out.println("Reached leaf node: "+p);
73              List.BasicBlock preds = p.getBasicBlock().getPredecessors();
74              //System.out.println("Predecessors: "+preds);
75              ListIterator.BasicBlock li = preds.basicBlockIterator();
76              while (li.hasNext()) {
77                  BasicBlock pred = li.nextBasicBlock();
78                  Quad q = pred.getLastQuad();
79                  //System.out.println("last quad of "+pred+" is "+q);
80                  if (pred.size() < 2) break;
81                  Quad q2 = pred.getQuad(pred.size()-2);
82                  //System.out.println("next-to-last quad is "+q2);
83                  if (q.getOperator() instanceof IntIfCmp) {
84                      Operand src2 = IntIfCmp.getSrc2(q);
85                      ConditionOperand cond = IntIfCmp.getCond(q);
86                      if ((q.getOperator() == IntIfCmp.IFCMP_A.INSTANCE) &&
87                         (src2 instanceof AConstOperand) &&
88                         ((AConstOperand)src2).getValue() == null) {
89                          if (q2.getOperator() instanceof Getfield) {
90                              FieldOperand fo = Getfield.getField(q2);
91                              System.out.println("depends on "+cond+" comparison between field "+fo+" and const null");
92                              add(current_method);
93                              findControlDependence(getDomNode(root, pred), root);
94                          }
95                      } else if ((q.getOperator() == IntIfCmp.IFCMP_I.INSTANCE) &&
96                               (src2 instanceof IConstOperand)) {
97                          if (q2.getOperator() instanceof Getfield) {
98                              FieldOperand fo = Getfield.getField(q2);
99                              System.out.println("depends on "+cond+" comparison between field "+fo+" and const "+((IConstOperand)src2).getValue());
100                             add(current_method);
101                             findControlDependence(getDomNode(root, pred), root);
102                         }
103                     }
104                 } 
105             }
106         } else {
107             while (i.hasNext()) {
108                 Dominators.DominatorNode x = (Dominators.DominatorNode)i.next();
109                 findControlDependence(x, root);
110             }
111         }
112     }
113     
114     public java.util.HashSet found_classes = new java.util.HashSet();
115     public java.util.HashSet found_methods = new java.util.HashSet();
116     
117     void add(jq_Method x) {
118         found_methods.add(x);
119         found_classes.add(x.getDeclaringClass());
120     }
121     
122     public String toString() { return "found "+found_methods.size()+" methods in "+found_classes.size()+" classes"; }
123 }