1
2
3
4 package joeq.Compiler.Dataflow;
5
6 import java.util.Arrays;
7 import java.util.Collections;
8 import java.util.HashMap;
9 import java.util.HashSet;
10 import java.util.Iterator;
11 import java.util.Map;
12 import joeq.Class.jq_Class;
13 import joeq.Class.jq_Method;
14 import joeq.Class.jq_Type;
15 import joeq.Compiler.Quad.BasicBlock;
16 import joeq.Compiler.Quad.CodeCache;
17 import joeq.Compiler.Quad.ControlFlowGraph;
18 import joeq.Compiler.Quad.Quad;
19 import joeq.Compiler.Quad.RegisterFactory.Register;
20 import joeq.Main.HostedVM;
21 import joeq.Util.Templates.List;
22 import joeq.Util.Templates.ListIterator;
23 import jwutil.graphs.EdgeGraph;
24 import jwutil.graphs.Graph;
25 import jwutil.graphs.ReverseGraph;
26 import jwutil.math.BitString;
27 import jwutil.util.Assert;
28
29 /***
30 * LivenessAnalysis
31 *
32 * @author John Whaley
33 * @version $Id: LivenessAnalysis.java 2465 2006-06-07 23:03:17Z joewhaley $
34 */
35 public class LivenessAnalysis extends Problem {
36
37 Map transferFunctions;
38 Fact emptySet;
39 TransferFunction emptyTF;
40
41 Solver mySolver;
42
43 static final boolean TRACE = false;
44
45 public void initialize(Graph g) {
46 Graph g2 = ((EdgeGraph) g).getGraph();
47 ControlFlowGraph cfg = (ControlFlowGraph) ((ReverseGraph) g2).getGraph();
48
49 if (TRACE) System.out.println("Initializing LivenessAnalysis.");
50 if (TRACE) System.out.println(cfg.fullDump());
51
52
53 int bitVectorSize = cfg.getRegisterFactory().size() + 1;
54
55 if (TRACE) System.out.println("Bit vector size: "+bitVectorSize);
56
57
58 transferFunctions = new HashMap();
59 emptySet = new UnionBitVectorFact(bitVectorSize);
60 emptyTF = new GenKillTransferFunction(bitVectorSize);
61
62 List.BasicBlock list = cfg.reversePostOrder(cfg.entry());
63 for (ListIterator.BasicBlock i = list.basicBlockIterator(); i.hasNext(); ) {
64 BasicBlock bb = i.nextBasicBlock();
65 BitString gen = new BitString(bitVectorSize);
66 BitString kill = new BitString(bitVectorSize);
67 for (ListIterator.Quad j = bb.backwardIterator(); j.hasNext(); ) {
68 Quad q = j.nextQuad();
69 for (ListIterator.RegisterOperand k = q.getDefinedRegisters().registerOperandIterator(); k.hasNext(); ) {
70 Register r = k.nextRegisterOperand().getRegister();
71 int index = r.getNumber() + 1;
72 kill.set(index);
73 gen.clear(index);
74 }
75 for (ListIterator.RegisterOperand k = q.getUsedRegisters().registerOperandIterator(); k.hasNext(); ) {
76 Register r = k.nextRegisterOperand().getRegister();
77 int index = r.getNumber() + 1;
78 gen.set(index);
79 }
80 }
81 GenKillTransferFunction tf = new GenKillTransferFunction(gen, new BitString(bitVectorSize));
82 tf.gen.or(gen);
83 tf.kill.or(kill);
84 Assert._assert(!transferFunctions.containsKey(bb));
85 transferFunctions.put(bb, tf);
86 }
87 if (TRACE) {
88 System.out.println("Transfer functions:");
89 for (Iterator i = transferFunctions.entrySet().iterator(); i.hasNext(); ) {
90 Map.Entry e = (Map.Entry) i.next();
91 System.out.println(e.getKey());
92 System.out.println(e.getValue());
93 }
94 }
95 }
96
97
98
99
100 public boolean direction() {
101 return false;
102 }
103
104
105
106
107 public Fact boundary() {
108 return emptySet;
109 }
110
111
112
113
114 public Fact interior() {
115 return emptySet;
116 }
117
118
119
120
121 public TransferFunction getTransferFunction(Object e) {
122 TransferFunction tf = (TransferFunction) transferFunctions.get(e);
123 if (tf == null) tf = emptyTF;
124 return tf;
125 }
126
127 public static void main(String[] args) {
128 HostedVM.initialize();
129 HashSet set = new HashSet();
130 for (int i=0; i<args.length; ++i) {
131 String s = args[i];
132 jq_Class c = (jq_Class) jq_Type.parseType(s);
133 c.load();
134 set.addAll(Arrays.asList(c.getDeclaredStaticMethods()));
135 set.addAll(Arrays.asList(c.getDeclaredInstanceMethods()));
136 }
137 Problem p = new LivenessAnalysis();
138 Solver s1 = new IterativeSolver();
139 Solver s2 = new SortedSetSolver(BBComparator.INSTANCE);
140 Solver s3 = new PriorityQueueSolver();
141 for (Iterator i = set.iterator(); i.hasNext(); ) {
142 jq_Method m = (jq_Method) i.next();
143 if (m.getBytecode() == null) continue;
144 System.out.println("Method "+m);
145 ControlFlowGraph cfg = CodeCache.getCode(m);
146 System.out.println(cfg.fullDump());
147 solve(cfg, s1, p);
148 solve(cfg, s2, p);
149 solve(cfg, s3, p);
150 Solver.dumpResults(cfg, s1);
151 Solver.compareResults(cfg, s1, s2);
152 Solver.compareResults(cfg, s2, s3);
153 }
154 }
155
156 public static LivenessAnalysis solve(ControlFlowGraph cfg) {
157 LivenessAnalysis p = new LivenessAnalysis();
158 Solver s1 = new IterativeSolver();
159 p.mySolver = s1;
160 solve(cfg, s1, p);
161 if (TRACE) {
162 System.out.println("Finished solving Liveness.");
163
164 }
165 return p;
166 }
167
168 private static void solve(ControlFlowGraph cfg, Solver s, Problem p) {
169 s.initialize(p, new EdgeGraph(new ReverseGraph(cfg, Collections.singleton(cfg.exit()))));
170 s.solve();
171 }
172
173 public boolean isLiveAtOut(BasicBlock bb, Register r) {
174 if (bb.getNumberOfSuccessors() > 0)
175 bb = bb.getSuccessors().getBasicBlock(0);
176 BitVectorFact f = (BitVectorFact) mySolver.getDataflowValue(bb);
177 if (f == null) throw new RuntimeException(bb.toString()+" reg "+r);
178 return f.fact.get(r.getNumber()+1);
179 }
180
181 public boolean isLiveAtIn(BasicBlock bb, Register r) {
182 BitVectorFact f = (BitVectorFact) mySolver.getDataflowValue(bb);
183 return f.fact.get(r.getNumber()+1);
184 }
185
186 public void setLiveAtIn(BasicBlock bb, Register r) {
187 BitVectorFact f = (BitVectorFact) mySolver.getDataflowValue(bb);
188 f.fact.set(r.getNumber()+1);
189 GenKillTransferFunction tf = (GenKillTransferFunction) transferFunctions.get(bb);
190 tf.gen.set(r.getNumber()+1);
191 }
192
193 public void setKilledAtIn(BasicBlock bb, Register r) {
194 BitVectorFact f = (BitVectorFact) mySolver.getDataflowValue(bb);
195 f.fact.clear(r.getNumber()+1);
196 GenKillTransferFunction tf = (GenKillTransferFunction) transferFunctions.get(bb);
197 tf.kill.set(r.getNumber()+1);
198 }
199 }