1 package polyglot.visit; 2 3 import polyglot.ast.*; 4 import polyglot.frontend.Job; 5 import polyglot.main.Report; 6 import polyglot.types.*; 7 import polyglot.util.InternalCompilerError; 8 import polyglot.util.Position; 9 10 import java.util.*; 11 12 15 public class DeadCodeEliminator extends DataFlow { 16 public DeadCodeEliminator(Job job, TypeSystem ts, NodeFactory nf) { 17 super(job, ts, nf, 18 false , 19 true ); 20 } 21 22 protected static class DataFlowItem extends Item { 23 private Set liveVars; 25 26 private Set liveDecls; 29 30 33 protected DataFlowItem() { 34 this.liveVars = new HashSet(); 35 this.liveDecls = new HashSet(); 36 } 37 38 41 protected DataFlowItem(DataFlowItem dfi) { 42 liveVars = new HashSet(dfi.liveVars); 43 liveDecls = new HashSet(dfi.liveDecls); 44 } 45 46 public void add(LocalInstance li) { 47 liveVars.add(li); 48 liveDecls.add(li); 49 } 50 51 public void addAll(Set lis) { 52 liveVars.addAll(lis); 53 liveDecls.addAll(lis); 54 } 55 56 public void remove(LocalInstance li) { 57 liveVars.remove(li); 58 } 59 60 public void removeAll(Set lis) { 61 liveVars.removeAll(lis); 62 } 63 64 public void removeDecl(LocalInstance li) { 65 liveVars.remove(li); 66 liveDecls.remove(li); 67 } 68 69 public void union(DataFlowItem dfi) { 70 liveVars.addAll(dfi.liveVars); 71 liveDecls.addAll(dfi.liveDecls); 72 } 73 74 protected boolean needDecl(LocalInstance li) { 75 return liveDecls.contains(li); 76 } 77 78 protected boolean needDef(LocalInstance li) { 79 return liveVars.contains(li); 80 } 81 82 public int hashCode() { 83 int result = 0; 84 for (Iterator it = liveVars.iterator(); it.hasNext(); ) { 85 result = 31*result + it.next().hashCode(); 86 } 87 88 for (Iterator it = liveDecls.iterator(); it.hasNext(); ) { 89 result = 31*result + it.next().hashCode(); 90 } 91 92 return result; 93 } 94 95 public boolean equals(Object o) { 96 if (!(o instanceof DataFlowItem)) return false; 97 98 DataFlowItem dfi = (DataFlowItem)o; 99 return liveVars.equals(dfi.liveVars) 100 && liveDecls.equals(dfi.liveDecls); 101 } 102 103 public String toString() { 104 return "<vars=" + liveVars + " ; decls=" + liveDecls + ">"; 105 } 106 } 107 108 public Item createInitialItem(FlowGraph graph, Term node) { 109 return new DataFlowItem(); 110 } 111 112 public Item confluence(List inItems, Term node, FlowGraph graph) { 113 DataFlowItem result = null; 114 for (Iterator it = inItems.iterator(); it.hasNext(); ) { 115 DataFlowItem inItem = (DataFlowItem)it.next(); 116 if (result == null) { 117 result = new DataFlowItem(inItem); 118 } else { 119 result.union(inItem); 120 } 121 } 122 123 return result; 124 } 125 126 public Map flow(Item in, FlowGraph graph, Term t, Set succEdgeKeys) { 127 return itemToMap(flow(in, graph, t), succEdgeKeys); 128 } 129 130 protected DataFlowItem flow(Item in, FlowGraph graph, Term t) { 131 DataFlowItem result = new DataFlowItem((DataFlowItem)in); 132 133 Set[] du = null; 134 135 if (t instanceof LocalDecl) { 136 LocalDecl n = (LocalDecl)t; 137 138 LocalInstance to = n.localInstance(); 139 result.removeDecl(to); 140 141 du = getDefUse(n.init()); 142 } else if (t instanceof Stmt && !(t instanceof CompoundStmt)) { 143 du = getDefUse((Stmt)t); 144 } else if (t instanceof CompoundStmt) { 145 if (t instanceof If) { 146 du = getDefUse(((If)t).cond()); 147 } else if (t instanceof Switch) { 148 du = getDefUse(((Switch)t).expr()); 149 } else if (t instanceof Do) { 150 du = getDefUse(((Do)t).cond()); 151 } else if (t instanceof For) { 152 du = getDefUse(((For)t).cond()); 153 } else if (t instanceof While) { 154 du = getDefUse(((While)t).cond()); 155 } 156 } 157 158 if (du != null) { 159 result.removeAll(du[0]); 160 result.addAll(du[1]); 161 } 162 163 return result; 164 } 165 166 public void post(FlowGraph graph, Term root) throws SemanticException { 167 if (Report.should_report(Report.cfg, 2)) { 169 dumpFlowGraph(graph, root); 170 } 171 } 172 173 public void check(FlowGraph graph, Term n, Item inItem, Map outItems) 174 throws SemanticException { 175 176 throw new InternalCompilerError("DeadCodeEliminator.check should " 177 + "never be called."); 178 } 179 180 private DataFlowItem getItem(Term n) { 181 FlowGraph g = currentFlowGraph(); 182 if (g == null) return null; 183 184 Collection peers = g.peers(n); 185 if (peers == null || peers.isEmpty()) return null; 186 187 List items = new ArrayList(); 188 for (Iterator it = peers.iterator(); it.hasNext(); ) { 189 FlowGraph.Peer p = (FlowGraph.Peer)it.next(); 190 if (p.inItem() != null) items.add(p.inItem()); 191 } 192 193 return (DataFlowItem)confluence(items, n, g); 194 } 195 196 public Node leaveCall(Node old, Node n, NodeVisitor v) 197 throws SemanticException { 198 199 if (n instanceof LocalDecl) { 200 LocalDecl ld = (LocalDecl)n; 201 DataFlowItem in = getItem(ld); 202 if (in == null || in.needDecl(ld.localInstance())) return n; 203 return getEffects(ld.init()); 204 } 205 206 if (n instanceof Eval) { 207 Eval eval = (Eval)n; 208 Expr expr = eval.expr(); 209 Local local; 210 Expr right = null; 211 212 if (expr instanceof Assign) { 213 Assign assign = (Assign)expr; 214 Expr left = assign.left(); 215 right = assign.right(); 216 217 if (!(left instanceof Local)) return n; 218 local = (Local)left; 219 } else if (expr instanceof Unary) { 220 Unary unary = (Unary)expr; 221 expr = unary.expr(); 222 if (!(expr instanceof Local)) return n; 223 local = (Local)expr; 224 } else { 225 return n; 226 } 227 228 DataFlowItem in = getItem(eval); 229 if (in == null || in.needDef(local.localInstance())) return n; 230 231 if (right != null) { 232 return getEffects(right); 233 } 234 235 return nf.Empty(Position.COMPILER_GENERATED); 236 } 237 238 if (n instanceof Block) { 239 Block b = (Block)n; 241 List stmts = new ArrayList(b.statements()); 242 for (Iterator it = stmts.iterator(); it.hasNext(); ) { 243 if (it.next() instanceof Empty) it.remove(); 244 } 245 246 return b.statements(stmts); 247 } 248 249 return n; 250 } 251 252 257 protected Set[] getDefUse(Node n) { 258 final Set def = new HashSet(); 259 final Set use = new HashSet(); 260 261 if (n != null) { 262 n.visit(createDefUseFinder(def, use)); 263 } 264 265 return new Set[] {def, use}; 266 } 267 268 protected NodeVisitor createDefUseFinder(Set def, Set use) { 269 return new DefUseFinder(def, use); 270 } 271 272 protected static class DefUseFinder extends HaltingVisitor { 273 protected Set def; 274 protected Set use; 275 276 public DefUseFinder(Set def, Set use) { 277 this.def = def; 278 this.use = use; 279 } 280 281 public NodeVisitor enter(Node n) { 282 if (n instanceof LocalAssign) { 283 return bypass(((Assign)n).left()); 284 } 285 286 return super.enter(n); 287 } 288 289 public Node leave(Node old, Node n, NodeVisitor v) { 290 if (n instanceof Local) { 291 use.add(((Local)n).localInstance()); 292 } else if (n instanceof Assign) { 293 Expr left = ((Assign)n).left(); 294 if (left instanceof Local) { 295 def.add(((Local)left).localInstance()); 296 } 297 } 298 299 return n; 300 } 301 } 302 303 307 protected Stmt getEffects(Expr expr) { 308 Stmt empty = nf.Empty(Position.COMPILER_GENERATED); 309 if (expr == null) return empty; 310 311 final List result = new LinkedList(); 312 final Position pos = Position.COMPILER_GENERATED; 313 314 NodeVisitor v = new HaltingVisitor() { 315 public NodeVisitor enter(Node n) { 316 if (n instanceof Assign || n instanceof ProcedureCall) { 317 return bypassChildren(n); 318 } 319 320 322 if (n instanceof Unary) { 323 Unary.Operator op = ((Unary)n).operator(); 324 if (op == Unary.POST_INC || op == Unary.POST_DEC 325 || op == Unary.PRE_INC || op == Unary.PRE_INC) { 326 327 return bypassChildren(n); 328 } 329 } 330 331 return this; 332 } 333 334 public Node leave(Node old, Node n, NodeVisitor v) { 335 if (n instanceof Assign || n instanceof ProcedureCall) { 336 result.add(nf.Eval(pos, (Expr)n)); 337 } else if (n instanceof Unary) { 338 Unary.Operator op = ((Unary)n).operator(); 339 if (op == Unary.POST_INC || op == Unary.POST_DEC 340 || op == Unary.PRE_INC || op == Unary.PRE_INC) { 341 342 result.add(nf.Eval(pos, (Expr)n)); 343 } 344 } 345 346 348 return n; 349 } 350 }; 351 352 expr.visit(v); 353 354 if (result.isEmpty()) return empty; 355 if (result.size() == 1) return (Stmt)result.get(0); 356 return nf.Block(Position.COMPILER_GENERATED, result); 357 } 358 } 359 360 | Popular Tags |