1
2
3
4 package net.sf.bddbddb.ir;
5
6 import java.util.Collection;
7 import java.util.Iterator;
8 import java.util.LinkedList;
9 import java.util.List;
10 import java.util.ListIterator;
11 import java.util.Map;
12 import java.util.Set;
13 import java.io.BufferedWriter;
14 import java.io.FileWriter;
15 import java.io.IOException;
16 import jwutil.io.SystemProperties;
17 import jwutil.util.Assert;
18 import net.sf.bddbddb.Attribute;
19 import net.sf.bddbddb.BDDRelation;
20 import net.sf.bddbddb.IterationFlowGraph;
21 import net.sf.bddbddb.IterationList;
22 import net.sf.bddbddb.Relation;
23 import net.sf.bddbddb.Solver;
24 import net.sf.bddbddb.Stratify;
25 import net.sf.bddbddb.dataflow.ConstantProp;
26 import net.sf.bddbddb.dataflow.CopyProp;
27 import net.sf.bddbddb.dataflow.DataflowSolver;
28 import net.sf.bddbddb.dataflow.DeadCode;
29 import net.sf.bddbddb.dataflow.DefUse;
30 import net.sf.bddbddb.dataflow.IRPass;
31 import net.sf.bddbddb.dataflow.Liveness;
32 import net.sf.bddbddb.dataflow.PartialRedundancy;
33 import net.sf.bddbddb.dataflow.Problem;
34 import net.sf.bddbddb.dataflow.ConstantProp.ConstantPropFacts;
35 import net.sf.bddbddb.dataflow.DataflowSolver.DataflowIterator;
36 import net.sf.bddbddb.dataflow.DefUse.DefUseFact;
37 import net.sf.bddbddb.ir.highlevel.BooleanOperation;
38 import net.sf.bddbddb.ir.highlevel.Copy;
39 import net.sf.bddbddb.ir.highlevel.Invert;
40 import net.sf.bddbddb.ir.highlevel.Load;
41 import net.sf.bddbddb.ir.highlevel.Project;
42 import net.sf.bddbddb.ir.highlevel.Rename;
43 import net.sf.bddbddb.ir.highlevel.Save;
44 import net.sf.bddbddb.ir.lowlevel.ApplyEx;
45 import net.sf.bddbddb.ir.lowlevel.BDDProject;
46 import net.sf.bddbddb.ir.lowlevel.Replace;
47 import net.sf.javabdd.BDDDomain;
48 import net.sf.javabdd.BDDPairing;
49 import net.sf.javabdd.BDDFactory.BDDOp;
50
51 /***
52 * Intermediate representation.
53 *
54 * @author mcarbin
55 * @version $Id: IR.java 562 2005-05-24 05:23:59Z joewhaley $
56 */
57 public class IR {
58 public Solver solver;
59 public IterationFlowGraph graph;
60 boolean ALL_OPTS = !SystemProperties.getProperty("allopts", "no").equals("no");
61 boolean FREE_DEAD = ALL_OPTS && !SystemProperties.getProperty("freedead", "yes").equals("no") || !SystemProperties.getProperty("freedead", "no").equals("no");
62 boolean CONSTANTPROP = ALL_OPTS && !SystemProperties.getProperty("constantprop", "yes").equals("no")
63 || !SystemProperties.getProperty("constantprop", "no").equals("no");
64 boolean DEFUSE = ALL_OPTS && !SystemProperties.getProperty("defuse", "yes").equals("no") || !SystemProperties.getProperty("defuse", "no").equals("no");
65 boolean PRE = ALL_OPTS && !SystemProperties.getProperty("pre", "yes").equals("no") || !SystemProperties.getProperty("pre", "no").equals("no");
66 boolean COPYPROP = ALL_OPTS && !SystemProperties.getProperty("copyprop", "yes").equals("no") || !SystemProperties.getProperty("copyprop", "no").equals("no");
67 boolean DEAD_CODE = ALL_OPTS && !SystemProperties.getProperty("deadcode", "yes").equals("no") || !SystemProperties.getProperty("deadcode", "no").equals("no");
68 boolean DOMAIN_ASSIGNMENT = ALL_OPTS && !SystemProperties.getProperty("domainassign", "yes").equals("no")
69 || !SystemProperties.getProperty("domainassign", "no").equals("no");
70 boolean TRACE = false;
71
72 public static IR create(Stratify s) {
73 return create(s.solver, s.strata, s.innerSccs);
74 }
75
76 public static IR create(Solver solver, List strata, Map innerSccs) {
77 IterationFlowGraph ifg = new IterationFlowGraph(solver.getRules(), strata, innerSccs);
78 IterationList list = ifg.expand();
79
80 if (!solver.getRelationsToLoad().isEmpty()) {
81 Assert._assert(!list.isLoop());
82 IterationList loadList = new IterationList(false);
83 for (Iterator j = solver.getRelationsToLoad().iterator(); j.hasNext();) {
84 Relation r = (Relation) j.next();
85 loadList.addElement(new Load(r, solver.getBaseDir() + r + ".bdd", false));
86 if (r.getNegated() != null) {
87 loadList.addElement(new Invert(r.getNegated(), r));
88 }
89 }
90 list.addElement(0, loadList);
91 }
92
93 if (!solver.getRelationsToSave().isEmpty()) {
94 Assert._assert(!list.isLoop());
95 IterationList saveList = new IterationList(false);
96 for (Iterator j = solver.getRelationsToSave().iterator(); j.hasNext();) {
97 Relation r = (Relation) j.next();
98 saveList.addElement(new Save(r, solver.getBaseDir() + r + ".bdd", false));
99 }
100 list.addElement(saveList);
101 }
102 return new IR(solver, ifg);
103 }
104
105
106 public void optimize() {
107
108 if (CONSTANTPROP) {
109 solver.out.print("Running ConstantProp...");
110 long time = System.currentTimeMillis();
111 DataflowSolver df_solver = new DataflowSolver();
112 Problem problem = new ConstantProp();
113 IterationList list = graph.getIterationList();
114 df_solver.solve(problem, list);
115 DataflowIterator di = df_solver.getIterator(problem, graph);
116 while (di.hasNext()) {
117 Object o = di.next();
118 if (TRACE) solver.out.println("Next: " + o);
119 if (o instanceof Operation) {
120 Operation op = (Operation) o;
121 ConstantPropFacts f = (ConstantPropFacts) di.getFact();
122 Operation op2 = ((ConstantProp) problem).simplify(op, f);
123 if (op != op2) {
124 if (TRACE) solver.out.println("Replacing " + op + " with " + op2);
125 di.set(op2);
126 }
127 } else {
128 IterationList b = (IterationList) o;
129 di.enter(b);
130 }
131 }
132 solver.out.println(((System.currentTimeMillis() - time) / 1000.) + "s");
133 }
134 if (DEFUSE) {
135 if (TRACE) solver.out.print("Running Def Use...");
136 long time = System.currentTimeMillis();
137 boolean changed = false;
138 while (doDefUse())
139 changed = true;
140 solver.out.println(((System.currentTimeMillis() - time) / 1000.) + "s");
141 if (TRACE && changed) solver.out.println("IR Changed after Defuse");
142 }
143 if (true) {
144 solver.out.print("Running Peephole...");
145 long time = System.currentTimeMillis();
146 doPeephole(graph.getIterationList());
147 solver.out.println(((System.currentTimeMillis() - time) / 1000.) + "s");
148 }
149
150 if (DOMAIN_ASSIGNMENT) {
151 solver.out.print("Running DomainAssignment...");
152 long time = System.currentTimeMillis();
153
154
155
156
157
158
159
160
161
162
163
164 DomainAssignment ass = new UFDomainAssignment(this.solver);
165 IterationList list = graph.getIterationList();
166 ass.addConstraints(list);
167 ass.doAssignment();
168 ass.setVariableOrdering();
169 BufferedWriter dos = null;
170 try {
171 dos = new BufferedWriter(new FileWriter("domainassign.gen"));
172 ass.saveDomainAssignment(dos);
173 } catch (IOException x) {
174 x.printStackTrace();
175 } finally {
176 if (dos != null) try {
177 dos.close();
178 } catch (IOException x) {
179 }
180 }
181 solver.out.println("cleaning up");
182 cleanUpAfterAssignment(list);
183 solver.out.println(((System.currentTimeMillis() - time) / 1000.) + "s");
184 }
185
186
187 while (true) {
188
189 boolean changed = false;
190 if (false && PRE) {
191 if (TRACE) solver.out.print("Running Partial Redundancy...");
192 long time = System.currentTimeMillis();
193 IRPass pre = new PartialRedundancy(this);
194 boolean b = pre.run();
195 if (TRACE) solver.out.println(((System.currentTimeMillis() - time) / 1000.) + "s");
196 if (TRACE && b) solver.out.println("IR changed after partial redundancy");
197 changed |= b;
198 }
199 if (COPYPROP) {
200 if (TRACE) solver.out.print("Running Copy Propagation...");
201 long time = System.currentTimeMillis();
202 IRPass copy = new CopyProp(this);
203 boolean b = copy.run();
204 if (TRACE) solver.out.println(((System.currentTimeMillis() - time) / 1000.) + "s");
205 if (TRACE && b) solver.out.println("IR changed after copy propagation");
206 changed |= b;
207 }
208 if (DEAD_CODE) {
209 if (TRACE) solver.out.print("Running Dead Code Elimination...");
210 long time = System.currentTimeMillis();
211 IRPass deadCode = new DeadCode(this);
212 boolean b = deadCode.run();
213 if (TRACE) solver.out.println(((System.currentTimeMillis() - time) / 1000.) + "s");
214 if (TRACE && b) solver.out.println("IR Changed after dead code elimination");
215 changed |= b;
216 }
217 if (!changed) break;
218
219 }
220
221 if (FREE_DEAD) {
222 if (TRACE) solver.out.print("Running Liveness Analysis...");
223 long time = System.currentTimeMillis();
224 IRPass liveness = new Liveness(this);
225 liveness.run();
226 if (TRACE) solver.out.println(((System.currentTimeMillis() - time) / 1000.) + "s");
227 }
228 }
229
230 void verifyRename(Rename r){
231 BDDRelation r0 = (BDDRelation) r.getRelationDest();
232 BDDRelation r1 = (BDDRelation) r.getSrc();
233 Map renameMap = r.getRenameMap();
234 for(Iterator it = r1.getAttributes().iterator(); it.hasNext(); ){
235 Attribute a1 = (Attribute) it.next();
236 Attribute a0 = (Attribute) renameMap.get(a1);
237 if(a0 == null){
238 Assert._assert(r0.getAttributes().contains(a1));
239 a0 = a1;
240 }
241 BDDDomain d1 = ((BDDRelation) r1).getBDDDomain(a1);
242 BDDDomain d0 = ((BDDRelation) r0).getBDDDomain(a0);
243 if( d1 != d0 ){
244 solver.out.println(r);
245 solver.out.println("src attributes: " + r1.getAttributes()+ " domains: " + ((BDDRelation) r1).getBDDDomains() +
246 " dest attributes: " + r0.getAttributes() + "domains: " + ((BDDRelation) r0).getBDDDomains() +
247 Operation.getRenames((BDDRelation) r0, (BDDRelation) r1));
248 solver.out.println( "a0: " + a0 + " d0: " + d0 + " a1: " + a1 +" d1: " + d1);
249 solver.out.println("rename map: " + renameMap);
250 Assert.UNREACHABLE();
251 }
252 }
253 }
254 void cleanUpAfterAssignment(IterationList list) {
255 for (ListIterator i = list.iterator(); i.hasNext();) {
256 Object o = i.next();
257 if (o instanceof Rename) {
258 i.remove();
259 Rename r = (Rename) o;
260 Relation r0 = r.getRelationDest();
261 Relation r1 = r.getSrc();
262 Copy op = new Copy(r0, r1);
263 i.add(op);
264 } else if (o instanceof Replace) {
265 Replace r = (Replace) o;
266 BDDPairing p = r.setPairing();
267 if (p == null) {
268 i.remove();
269 Relation r0 = r.getRelationDest();
270 Relation r1 = r.getSrc();
271 Copy op = new Copy(r0, r1);
272 i.add(op);
273 }
274 }else if (o instanceof ApplyEx){
275 ApplyEx a = (ApplyEx) o;
276 a.setProjectSet();
277 }else if(o instanceof Project){
278 Project p = (Project) o;
279 i.remove();
280 BDDRelation r0 = (BDDRelation) p.getRelationDest();
281 BDDRelation r1 = (BDDRelation) p.getSrc();
282 BDDProject b = new BDDProject(r0,r1);
283 i.add(b);
284 } else if (o instanceof IterationList) {
285 cleanUpAfterAssignment((IterationList) o);
286 }
287 }
288 }
289
290 void doPeephole(IterationList list) {
291 for (ListIterator i = list.iterator(); i.hasNext();) {
292 Object o = i.next();
293 if (o instanceof Copy) {
294 Copy op = (Copy) o;
295 if (op.getRelationDest() == op.getSrc()) i.remove();
296 } else if (o instanceof IterationList) {
297 doPeephole((IterationList) o);
298 }
299 }
300 }
301
302 boolean doDefUse() {
303 solver.out.print("Running DefUse...");
304 long time = System.currentTimeMillis();
305 boolean change = false;
306 DataflowSolver df_solver = new DataflowSolver();
307 DefUse problem = new DefUse(this);
308 IterationList list = graph.getIterationList();
309 df_solver.solve(problem, list);
310 DataflowIterator di = df_solver.getIterator(problem, graph);
311 List to_remove = new LinkedList();
312 outer : while (di.hasNext()) {
313 Object o = di.next();
314 if (TRACE) solver.out.println("Next: " + o);
315 if (o instanceof Operation) {
316 Operation op = (Operation) o;
317 DefUseFact f = (DefUseFact) di.getFact();
318 if (op.getRelationDest() != null) {
319 Collection uses = problem.getUses(op.getRelationDest());
320 if (TRACE) solver.out.println("Uses: " + uses);
321 if (uses.size() == 0) {
322 if (TRACE) solver.out.println("Removing: " + op);
323 di.remove();
324 change = true;
325 continue;
326 }
327 }
328 if (op instanceof Project) {
329 Project p = (Project) op;
330 Relation src = p.getSrc();
331 Set defs = f.getReachingDefs(src);
332 if (TRACE) solver.out.println("Defs: " + defs);
333 if (defs.size() == 1) {
334 Operation op2 = (Operation) defs.iterator().next();
335 if (op2 instanceof BooleanOperation) {
336 BooleanOperation boolop = (BooleanOperation) op2;
337
338
339 Set uses = problem.getUses(src);
340 if (TRACE) solver.out.println("Uses of " + src + ": " + uses);
341 for (Iterator i = uses.iterator(); i.hasNext();) {
342 Operation other = (Operation) i.next();
343 if (other == p) continue;
344 DefUseFact duf2 = (DefUseFact) problem.getFact(other);
345 if (duf2.getReachingDefs(src).contains(boolop)) {
346 continue outer;
347 }
348 }
349 BDDOp bddop = boolop.getBDDOp();
350 ApplyEx new_op = new ApplyEx((BDDRelation) p.getRelationDest(), (BDDRelation) boolop.getSrc1(), bddop,
351 (BDDRelation) boolop.getSrc2());
352 if (TRACE) solver.out.println("Replacing " + op + " with " + new_op);
353 di.set(new_op);
354 if (TRACE) solver.out.println("Marking " + boolop + " for deletion.");
355 to_remove.add(boolop);
356 }
357 }
358 }
359 } else {
360 IterationList b = (IterationList) o;
361 di.enter(b);
362 }
363 }
364 if (!to_remove.isEmpty()) {
365 list.removeElements(to_remove);
366 change = true;
367 }
368 solver.out.println(((System.currentTimeMillis() - time) / 1000.) + "s");
369 return change;
370 }
371
372 /***
373 *
374 */
375 private IR(Solver solver, IterationFlowGraph g) {
376 this.solver = solver;
377 this.graph = g;
378 }
379
380 public Relation getRelation(String name) {
381 return solver.getRelation(name);
382 }
383
384 public Relation getRelation(int index) {
385 return solver.getRelation(index);
386 }
387
388 public int getNumberOfRelations() {
389 return solver.getNumberOfRelations();
390 }
391
392 public void printIR() {
393 printIR(graph.getIterationList(), "");
394 }
395
396 public void printIR(IterationList list, String space) {
397 solver.out.println(space + list + ":");
398 for (Iterator it = list.iterator(); it.hasNext();) {
399 Object o = it.next();
400 if (o instanceof Operation) {
401 solver.out.println(space + " " + o + " " + getRenames((Operation) o));
402 } else {
403 printIR((IterationList) o, space + " ");
404 }
405 }
406 }
407
408 public String getRenames(Operation op) {
409 BDDRelation r0 = (BDDRelation) op.getRelationDest();
410 if (r0 == null) return "";
411 List srcs = op.getSrcs();
412 StringBuffer sb = new StringBuffer();
413 for (Iterator i = srcs.iterator(); i.hasNext();) {
414 BDDRelation r2 = (BDDRelation) i.next();
415 sb.append(Operation.getRenames(r2, r0));
416 }
417 if (sb.length() == 0) return "";
418 return sb.substring(1);
419 }
420 }