1 pnkfelix 1.1.2.1 // SpaceHeavyLiveTemps.java, created Wed Aug 23 17:20:37 2000 by pnkfelix
2 cananian 1.1.2.5 // Copyright (C) 2000 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis.DataFlow;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.1 import harpoon.Analysis.BasicBlock;
7 pnkfelix 1.1.2.1 import harpoon.IR.Properties.UseDefer;
8 pnkfelix 1.1.2.4 import harpoon.IR.Properties.CFGrapher;
9 pnkfelix 1.1.2.1 import harpoon.IR.Properties.CFGEdge;
10 pnkfelix 1.1.2.1 import harpoon.ClassFile.HCode;
11 pnkfelix 1.1.2.1 import harpoon.ClassFile.HCodeElement;
12 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
13 pnkfelix 1.1.2.1 import harpoon.Util.CloneableIterator;
14 pnkfelix 1.1.2.1 import harpoon.Util.Util;
15 cananian 1.7 import net.cscott.jutil.BitSetFactory;
16 cananian 1.7 import net.cscott.jutil.ReverseIterator;
17 cananian 1.7 import net.cscott.jutil.SetFactory;
18 pnkfelix 1.1.2.1
19 pnkfelix 1.1.2.1 import java.util.Set;
20 pnkfelix 1.1.2.1 import java.util.List;
21 pnkfelix 1.1.2.1 import java.util.Collection;
22 pnkfelix 1.1.2.1 import java.util.Map;
23 pnkfelix 1.1.2.1 import java.util.HashSet;
24 pnkfelix 1.1.2.1 import java.util.HashMap;
25 pnkfelix 1.1.2.1 import java.util.Iterator;
26 pnkfelix 1.1.2.1
27 pnkfelix 1.1.2.1 /**
28 pnkfelix 1.1.2.1 * <code>SpaceHeavyLiveTemps</code> is an extension of
29 pnkfelix 1.1.2.1 * <code>LiveTemps</code> that keeps ALL of the results of the queries
30 pnkfelix 1.1.2.1 * that it has calculated alive. This can lead to large space
31 pnkfelix 1.1.2.1 * overhead but this is offset by the decrease in required time for
32 pnkfelix 1.1.2.1 * repeated queries.
33 pnkfelix 1.1.2.1 *
34 pnkfelix 1.1.2.1 * I plan to eventually paraterize this class with a scaling factor so
35 pnkfelix 1.1.2.1 * that space can be decreased by a constant-factor at the cost of a
36 pnkfelix 1.1.2.1 * corresponding increase in recomputation-times; for now the class
37 pnkfelix 1.1.2.1 * can be treated as if the scaling factor were equal to 1.
38 pnkfelix 1.1.2.1 *
39 cananian 1.1.2.5 * @author Felix S. Klock II <pnkfelix@mit.edu>
40 cananian 1.7 * @version $Id: SpaceHeavyLiveTemps.java,v 1.7 2004/02/08 01:51:05 cananian Exp $
41 pnkfelix 1.1.2.1 */
42 pnkfelix 1.1.2.1 public class SpaceHeavyLiveTemps extends LiveTemps {
43 pnkfelix 1.1.2.4 CFGrapher grapher;
44 pnkfelix 1.1.2.1
45 pnkfelix 1.1.2.1 public static LiveTemps make(HCode code, Set liveOnExit) {
46 pnkfelix 1.1.2.1 BasicBlock.Factory bbf = new BasicBlock.Factory(code);
47 pnkfelix 1.1.2.1 LiveTemps lt = new SpaceHeavyLiveTemps(bbf, liveOnExit);
48 pnkfelix 1.1.2.1 Solver.worklistSolve
49 pnkfelix 1.1.2.1 // (bbFact.preorderBlocksIter(),
50 cananian 1.5 (new ReverseIterator(bbf.postorderBlocksIter()),
51 pnkfelix 1.1.2.1 lt);
52 pnkfelix 1.1.2.1 return lt;
53 pnkfelix 1.1.2.1
54 pnkfelix 1.1.2.1 }
55 pnkfelix 1.1.2.1
56 pnkfelix 1.1.2.1 /** Creates a <code>SpaceHeavyLiveTemps</code>. */
57 pnkfelix 1.1.2.1 public SpaceHeavyLiveTemps(BasicBlock.Factory bbf, Set liveOnExit) {
58 pnkfelix 1.1.2.4 this(bbf, liveOnExit, UseDefer.DEFAULT);
59 pnkfelix 1.1.2.1 }
60 pnkfelix 1.1.2.1
61 pnkfelix 1.1.2.1 public SpaceHeavyLiveTemps(BasicBlock.Factory bbf, Set liveOnExit,
62 pnkfelix 1.1.2.1 UseDefer ud) {
63 pnkfelix 1.1.2.4 this(bbf, liveOnExit, ud, CFGrapher.DEFAULT);
64 pnkfelix 1.1.2.1 }
65 pnkfelix 1.1.2.4
66 pnkfelix 1.1.2.4 public SpaceHeavyLiveTemps(BasicBlock.Factory bbf, Set liveOnExit,
67 pnkfelix 1.1.2.4 UseDefer ud, CFGrapher grapher) {
68 pnkfelix 1.1.2.4 super(bbf, liveOnExit, ud);
69 pnkfelix 1.1.2.4 this.grapher = grapher;
70 pnkfelix 1.1.2.4 }
71 pnkfelix 1.1.2.4
72 pnkfelix 1.1.2.1
73 pnkfelix 1.1.2.1 public SpaceHeavyLiveTemps(BasicBlock.Factory bbf, Set liveOnExit,
74 pnkfelix 1.1.2.1 SetFactory tempSetFact, UseDefer ud) {
75 pnkfelix 1.1.2.4 this(bbf, liveOnExit, tempSetFact, ud, CFGrapher.DEFAULT);
76 pnkfelix 1.1.2.4 }
77 pnkfelix 1.1.2.4
78 pnkfelix 1.1.2.4 public SpaceHeavyLiveTemps(BasicBlock.Factory bbf, Set liveOnExit,
79 pnkfelix 1.1.2.4 SetFactory tempSetFact, UseDefer ud, CFGrapher grapher) {
80 pnkfelix 1.1.2.1 super(bbf, liveOnExit, tempSetFact, ud);
81 pnkfelix 1.1.2.4 this.grapher = grapher;
82 pnkfelix 1.1.2.1 }
83 pnkfelix 1.1.2.1
84 pnkfelix 1.1.2.1 private HashMap hce2liveAfter = new HashMap();
85 pnkfelix 1.1.2.1
86 pnkfelix 1.1.2.1 public Set getLiveAfter(HCodeElement hce) {
87 pnkfelix 1.1.2.2 if (hce2liveAfter.containsKey(hce)) {
88 pnkfelix 1.1.2.2 return (Set) hce2liveAfter.get(hce);
89 pnkfelix 1.1.2.2 }
90 pnkfelix 1.1.2.2
91 pnkfelix 1.1.2.1 BasicBlock bb = bbFact.getBlock(hce);
92 witchel 1.1.2.3 if(bb == null) return java.util.Collections.EMPTY_SET;
93 pnkfelix 1.1.2.1 List stms = bb.statements();
94 pnkfelix 1.1.2.4 HCodeElement last = (HCodeElement) stms.get(stms.size() - 1);
95 pnkfelix 1.1.2.4 HCodeElement cfg = hce;
96 pnkfelix 1.1.2.1 while (!hce2liveAfter.containsKey(cfg)) {
97 pnkfelix 1.1.2.1 if (cfg.equals(last)) {
98 pnkfelix 1.1.2.1 Set liveAfter =
99 pnkfelix 1.1.2.1 mySetFactory.makeSet(getLiveOnExit(bb));
100 pnkfelix 1.1.2.1 hce2liveAfter.put(cfg, liveAfter);
101 pnkfelix 1.1.2.1 break;
102 pnkfelix 1.1.2.1 } else {
103 pnkfelix 1.1.2.4 Collection succC = grapher.succC(cfg);
104 cananian 1.3.2.1 assert succC.size() == 1 : cfg;
105 cananian 1.6 cfg = ((CFGEdge) succC.iterator().next()).to();
106 pnkfelix 1.1.2.1 }
107 pnkfelix 1.1.2.1 }
108 pnkfelix 1.1.2.1
109 pnkfelix 1.1.2.1 Set liveAfter = (Set) hce2liveAfter.get(cfg);
110 pnkfelix 1.1.2.1 while(!cfg.equals(hce)) {
111 pnkfelix 1.1.2.4 Collection predC = grapher.predC(cfg);
112 cananian 1.3.2.1 assert predC.size() == 1 : cfg;
113 pnkfelix 1.1.2.1 liveAfter = mySetFactory.makeSet(liveAfter);
114 pnkfelix 1.1.2.1 liveAfter.removeAll(ud.defC(cfg));
115 pnkfelix 1.1.2.1 liveAfter.addAll(ud.useC(cfg));
116 cananian 1.6 cfg = ((CFGEdge) predC.iterator().next()).from();
117 pnkfelix 1.1.2.1 hce2liveAfter.put(cfg, liveAfter);
118 pnkfelix 1.1.2.1 }
119 pnkfelix 1.1.2.1
120 pnkfelix 1.1.2.1 return (Set) hce2liveAfter.get(hce);
121 pnkfelix 1.1.2.1 }
122 pnkfelix 1.1.2.1
123 cananian 1.2 }