View Javadoc

1   package joeq.Compiler.Analysis.IPSSA.Utils;
2   
3   import java.util.HashMap;
4   import java.util.Iterator;
5   import java.util.List;
6   import java.util.Set;
7   import java.io.PrintStream;
8   import joeq.Class.jq_Method;
9   import joeq.Compiler.Analysis.IPA.ProgramLocation;
10  import joeq.Compiler.Analysis.IPA.ProgramLocation.QuadProgramLocation;
11  import joeq.Compiler.Analysis.IPSSA.DominatorQuery;
12  import joeq.Compiler.Quad.BasicBlock;
13  import joeq.Compiler.Quad.BasicBlockVisitor;
14  import joeq.Compiler.Quad.CodeCache;
15  import joeq.Compiler.Quad.ControlFlowGraph;
16  import joeq.Compiler.Quad.ControlFlowGraphVisitor;
17  import joeq.Compiler.Quad.Dominators;
18  import joeq.Compiler.Quad.Quad;
19  import joeq.Compiler.Quad.QuadIterator;
20  import joeq.Compiler.Quad.Dominators.DominatorNode;
21  import joeq.Util.SyntheticGraphs.Graph;
22  import jwutil.util.Assert;
23  
24  /***
25   * A pretty obvious implementation of DominatorQuery, nothing fancy here. 
26   * Needs to be optimized for future use.
27   * @see DominatorQuery
28   * @author  V.Benjamin Livshits
29   * @version $Id: SimpleDominatorQuery.java 1931 2004-09-22 22:17:47Z joewhaley $
30   * */
31  public class SimpleDominatorQuery implements DominatorQuery {
32      private jq_Method _m;    
33      private ControlFlowGraph _cfg;
34  
35      // Maps we create to answer the queries
36      private HashMap _bb2nodeMap;    
37      private HashMap _quad2BBMap;
38      private boolean _verbose = false;
39  
40      public SimpleDominatorQuery(jq_Method m){
41          this._m = m;
42          this._cfg = CodeCache.getCode(m);
43          
44          // build BB-level dominators
45          Dominators dom = new Dominators(true);
46          dom.visitMethod(m);
47          DominatorNode root = dom.computeTree();
48          
49          // create lookup maps
50          _bb2nodeMap = new HashMap();
51          buildBB2NodeMap(root, _bb2nodeMap);
52          
53          _quad2BBMap = new HashMap();
54          buildQuad2BBMap(_quad2BBMap);
55          
56          //System.out.println("_bb2nodeMap: " + _bb2nodeMap.size() + ", _quad2BBMap: " + _quad2BBMap.size() + "\n");
57      }
58          
59      private void buildBB2NodeMap(DominatorNode root, HashMap map) {
60          BasicBlock bb = root.getBasicBlock();
61          Assert._assert(bb != null);
62          map.put(bb, root);        
63          
64          List children = root. getChildren();
65          //System.out.println(children.size() + " children \n");
66          for(Iterator i = children.iterator(); i.hasNext();){
67              DominatorNode child = (DominatorNode)i.next();
68              
69              buildBB2NodeMap(child, map);
70          }
71      }
72      
73      private void buildQuad2BBMap(final HashMap map) {
74          _cfg.visitBasicBlocks(new BasicBlockVisitor(){
75              public void visitBasicBlock(BasicBlock bb){
76                  //System.out.println("Block " + bb.toString() + "\n");
77                  Quad lastQuad = bb.getLastQuad();
78                  if(lastQuad == null) return;
79                  for(int i = 0; i <= bb.getQuadIndex(lastQuad); i++){
80                      Quad q = (Quad)bb.getQuad(i);
81                      
82                      map.put(q, bb);
83                  }    
84              }
85          });
86      }
87  
88      public Quad getImmediateDominator(Quad q){
89          BasicBlock bb = (BasicBlock)_quad2BBMap.get(q);
90          Assert._assert(bb != null);
91          
92          int pos = bb.getQuadIndex(q);
93          if(pos > 0){
94              return bb.getQuad(pos - 1);
95          }else{
96              DominatorNode node = (DominatorNode)_bb2nodeMap.get(bb);
97              Assert._assert(node != null);
98              
99              DominatorNode dom = node.getParent();
100             if(dom != null){
101                 return dom.getBasicBlock().getLastQuad();     
102             }else{
103                 return null;
104             }
105         }
106     }
107     
108     public boolean isTop(Quad q){
109         return getImmediateDominator(q) == null;
110     }
111     
112     public void getDominanceFrontier(Quad q, Set/*<Quad>*/ set){
113         /*
114          * The idea is to get a dominance frontier from the dominance tree.
115          * DF(n) = {m | n dom pred(m), but n ~dom m}, so, there's a dominated predecessor. 
116          * */
117         Assert._assert(set != null);     
118         DominatorNode node = getNode(q);
119         processChildren(node.getBasicBlock(), node, set);
120         if(_verbose){
121             System.err.println("Dominance frontier for " + q.toString_short() + " is: ");
122             Iterator iter = set.iterator();
123             while(iter.hasNext()){
124                 Quad dom = (Quad) iter.next();
125                 //Assert._assert(q != dom, "Didn't expect " + q.toString() + "@ " + 
126                 //    new QuadProgramLocation(this._m, q).toStringLong() + " to be on its own dom. frontier");
127                 System.err.print(dom.toString() + " ");
128             }
129             System.err.println("");
130         }
131     }
132     
133     /***
134      * Collect nodes on the dominance frontier of root into set. Predecessors of node 
135      * are considered for the dominance frontier. 
136      * */
137     private void processChildren(BasicBlock root, DominatorNode node, Set/*<Quad>*/ set) {
138         BasicBlock bb = node.getBasicBlock();
139         if(bb.size() == 0) return;
140         
141         joeq.Util.Templates.ListIterator.BasicBlock successors = bb.getSuccessors().basicBlockIterator();
142         while(successors.hasNext()){
143             BasicBlock succ = successors.nextBasicBlock();
144             
145             Assert._assert(dominates(root, root));
146             Assert._assert(dominates(succ, succ));
147             if(!dominates(root, succ, true)){
148                 set.add(succ.getQuad(0));
149                 // AT LEAST one predecessor is not dominated -- no need to look at the others
150                 break;
151             }
152         }
153         for(Iterator iter = node.getChildren().iterator(); iter.hasNext(); ){
154             DominatorNode child = (DominatorNode)iter.next();
155             Assert._assert(child != node);
156             
157             // only the first node of a BB is suspect
158             processChildren(root, child, set);                                    
159         }    
160     }
161 
162     /***
163      * The default is non-strict dominance.
164      **/
165     private boolean dominates(BasicBlock root, BasicBlock pred) {
166         return dominates(root, pred, false);
167     }
168 
169     /***
170      * Check for dominance.
171      * */
172     private boolean dominates(BasicBlock root, BasicBlock pred, boolean strict) {
173         DominatorNode root_node = (DominatorNode) _bb2nodeMap.get(root);
174         DominatorNode node         = (DominatorNode) _bb2nodeMap.get(pred);    
175         
176         if(!strict && root == pred){
177             // nodes non-strictly dominates itself
178             return true;
179         }
180         
181         while(node != null){
182             node = node.getParent();
183             if(node == root_node){
184                 return true;
185             }
186         }
187         
188         return false;
189     }
190 
191     private DominatorNode getNode(Quad q) {
192         BasicBlock bb = (BasicBlock)_quad2BBMap.get(q);
193         Assert._assert(bb != null, "No matching basic block for " + q);
194         DominatorNode node = (DominatorNode)_bb2nodeMap.get(bb);
195         Assert._assert(node != null);
196 
197         return node;
198     }
199 
200     public void getIteratedDominanceFrontier(Quad q, Set/*<Quad>*/ set){
201         getDominanceFrontier(q, set);
202         
203         boolean change = false;
204         int i = 1;
205         do {
206             change = false;
207             //System.err.println("Iteration " + i);
208             for(Iterator iter = set.iterator(); iter.hasNext(); ){
209                 Quad domFrontierQuad = (Quad)iter.next();
210                 //Assert._assert(q != domFrontierQuad, "Didn't expect " + q + " to be on its own dom. frontier");
211                 
212                 int oldSetSize = set.size();                
213                 getDominanceFrontier(domFrontierQuad, set);                
214                 Assert._assert(set.size() >= oldSetSize);
215                 
216                 if(set.size() != oldSetSize){
217                     // change detected
218                     change = true;
219                 }
220             }
221             i++;
222         } while (change);
223     }
224         
225     /***
226      * Prints the dominator tree on Quads in dot format.
227      * */
228     public void printDot(PrintStream out){
229         Graph g = new Graph(_m.toString(), new Graph.Direction(Graph.Direction.LR));
230         for(Iterator iter = new QuadIterator(_cfg); iter.hasNext();){
231             Quad q = (Quad)iter.next();
232             
233             // these IDs should be unique, I hope
234             ProgramLocation loc = new QuadProgramLocation(_m, q);
235             String src_loc = loc.getSourceFile().toString() + ":" + loc.getLineNumber();
236             g.addNode(q.getID(), q.toString_short() + "//l" + src_loc);
237             Quad dom = getImmediateDominator(q);
238             if(dom != null){
239                 g.addNode(dom.getID(), dom.toString_short());
240                 g.addEdge(q.getID(), dom.getID());
241             }
242         }
243         
244         // graph creation is complete
245         g.printDot(out);
246     }
247     
248     public static class TestSimpleDominatorQuery implements ControlFlowGraphVisitor {
249         public TestSimpleDominatorQuery(){
250             CodeCache.AlwaysMap = true;
251         }
252         
253         public void visitCFG(ControlFlowGraph cfg) {
254             SimpleDominatorQuery q = new SimpleDominatorQuery(cfg.getMethod());
255             q.printDot(System.out);    
256         }
257         
258         public static void Main(String argv[]){
259             for(int i = 0; i < argv.length; i++){
260                 String arg = argv[i];
261                 
262                 if(arg == "-v"){
263                     // TOOD
264                 }
265             }
266         }
267     }
268 
269     public BasicBlock getBasicBlock(Quad quad) {
270         return (BasicBlock) _quad2BBMap.get(quad);
271     }
272 };
273