1 19 20 package soot.toolkits.graph; 21 22 import soot.*; 23 import soot.util.*; 24 import java.util.*; 25 import soot.jimple.*; 26 import soot.options.*; 27 import soot.toolkits.graph.*; 28 import soot.toolkits.scalar.*; 29 30 37 public class SimpleDominatorsFinder implements DominatorsFinder 38 { 39 protected DirectedGraph graph; 40 protected Map nodeToDominators; 41 42 45 public SimpleDominatorsFinder(DirectedGraph graph) 46 { 47 51 this.graph = graph; 52 SimpleDominatorsAnalysis analysis = new SimpleDominatorsAnalysis(graph); 53 54 { 56 nodeToDominators = new HashMap(graph.size() * 2 + 1, 0.7f); 57 58 for(Iterator nodeIt = graph.iterator(); nodeIt.hasNext();) { 59 Object node = nodeIt.next(); 60 FlowSet set = (FlowSet) analysis.getFlowAfter(node); 61 nodeToDominators.put(node, set); 62 } 63 } 64 } 65 66 public DirectedGraph getGraph() 67 { 68 return graph; 69 } 70 71 public List getDominators(Object node) 72 { 73 return ((FlowSet) nodeToDominators.get(node)).toList(); 75 } 76 77 public Object getImmediateDominator(Object node) 78 { 79 if(getGraph().getHeads().contains(node)) 81 return null; 82 83 85 List dominatorsList = getDominators(node); 86 dominatorsList.remove(node); 87 88 Iterator dominatorsIt = dominatorsList.iterator(); 89 Object immediateDominator = null; 90 91 while((immediateDominator == null) && dominatorsIt.hasNext()){ 92 Object dominator = dominatorsIt.next(); 93 94 if(isDominatedByAll(dominator, dominatorsList)) 95 immediateDominator = dominator; 96 } 97 98 if(immediateDominator == null) 99 throw new RuntimeException ("Assertion failed."); 100 101 return immediateDominator; 102 } 103 104 public boolean isDominatedBy(Object node, Object dominator) 105 { 106 return getDominators(node).contains(dominator); 107 } 108 109 public boolean isDominatedByAll(Object node, Collection dominators) 110 { 111 return getDominators(node).containsAll(dominators); 112 } 113 } 114 115 126 class SimpleDominatorsAnalysis extends ForwardFlowAnalysis 127 { 128 FlowSet emptySet; 129 Map nodeToGenerateSet; 130 131 SimpleDominatorsAnalysis(DirectedGraph graph) 132 { 133 super(graph); 134 135 { 137 List nodes = new ArrayList(); 138 139 for(Iterator nodesIt = graph.iterator(); nodesIt.hasNext();) 140 nodes.add(nodesIt.next()); 141 142 FlowUniverse nodeUniverse = new CollectionFlowUniverse(nodes); 143 emptySet = new ArrayPackedSet(nodeUniverse); 144 } 145 146 { 148 nodeToGenerateSet = new HashMap(graph.size() * 2 + 1, 0.7f); 149 150 for(Iterator nodeIt = graph.iterator(); nodeIt.hasNext();){ 151 Object s = nodeIt.next(); 152 FlowSet genSet = (FlowSet) emptySet.clone(); 153 genSet.add(s, genSet); 154 nodeToGenerateSet.put(s, genSet); 155 } 156 } 157 158 doAnalysis(); 159 } 160 161 165 protected Object newInitialFlow() 166 { 167 BoundedFlowSet initSet = (BoundedFlowSet) emptySet.clone(); 168 initSet.complement(); 169 return initSet; 170 } 171 172 175 protected Object entryInitialFlow() 176 { 177 List heads = graph.getHeads(); 178 179 if(heads.size() != 1) 180 throw new RuntimeException ("Assertion failed: Only one head expected."); 181 182 BoundedFlowSet initSet = (BoundedFlowSet) emptySet.clone(); 183 initSet.add(heads.get(0)); 184 return initSet; 185 } 186 187 190 protected void flowThrough(Object inValue, Object block, Object outValue) 191 { 192 FlowSet in = (FlowSet) inValue, out = (FlowSet) outValue; 193 194 in.union((FlowSet) nodeToGenerateSet.get(block), out); 196 } 197 198 201 protected void merge(Object in1, Object in2, Object out) 202 { 203 FlowSet inSet1 = (FlowSet) in1, 204 inSet2 = (FlowSet) in2; 205 206 FlowSet outSet = (FlowSet) out; 207 208 inSet1.intersection(inSet2, outSet); 209 } 210 211 protected void copy(Object source, Object dest) 212 { 213 FlowSet sourceSet = (FlowSet) source, 214 destSet = (FlowSet) dest; 215 216 sourceSet.copy(destSet); 217 } 218 } 219 | Popular Tags |