1 kkz 1.1.2.1 // QuadLiveness.java, created Wed Oct 27 17:17:49 1999 by kkz
2 cananian 1.1.2.11 // Copyright (C) 1999 Karen K. Zee <kkz@alum.mit.edu>
3 kkz 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 kkz 1.1.2.1 package harpoon.Analysis.Quads;
5 kkz 1.1.2.1
6 kkz 1.1.2.1 import harpoon.Analysis.Liveness;
7 kkz 1.1.2.1 import harpoon.ClassFile.HCode;
8 kkz 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
9 kkz 1.1.2.1 import harpoon.ClassFile.HCodeElement;
10 kkz 1.1.2.1 import harpoon.IR.Quads.Quad;
11 bdemsky 1.1.2.7 import harpoon.IR.Quads.PHI;
12 cananian 1.4 import harpoon.Temp.Temp;
13 bdemsky 1.1.2.4 import harpoon.Util.Util;
14 kkz 1.1.2.1
15 cananian 1.4 import java.util.ArrayList;
16 cananian 1.4 import java.util.Collections;
17 cananian 1.2.2.1 import java.util.HashMap;
18 kkz 1.1.2.1 import java.util.Iterator;
19 cananian 1.4 import java.util.List;
20 cananian 1.2.2.1 import java.util.Map;
21 kkz 1.1.2.1 import java.util.Set;
22 kkz 1.1.2.1
23 cananian 1.4 import net.cscott.jutil.Default;
24 cananian 1.4 import net.cscott.jutil.WorkSet;
25 kkz 1.1.2.1 /**
26 kkz 1.1.2.1 * <code>QuadLiveness</code> performs live variable analysis for a given
27 kkz 1.1.2.1 * <code>HCode</code>. Since it caches results, you should create a new
28 kkz 1.1.2.1 * <code>QuadLiveness</code> if you have changed the <code>HCode</code>.
29 kkz 1.1.2.1 *
30 cananian 1.1.2.11 * @author Karen K. Zee <kkz@alum.mit.edu>
31 cananian 1.4 * @version $Id: QuadLiveness.java,v 1.4 2004/02/08 01:53:14 cananian Exp $
32 kkz 1.1.2.1 */
33 cananian 1.2.2.1 public class QuadLiveness extends Liveness<Quad> {
34 cananian 1.2.2.1 final Map<Quad,Set<Temp>> livein, liveout;
35 cananian 1.2.2.1 final Map<Quad,Temp[]> tempin, tempout, tempinout;
36 kkz 1.1.2.1
37 kkz 1.1.2.1 /** Creates a <code>QuadLiveness</code>. Requires
38 kkz 1.1.2.1 * that the <code>HCode</code> be quad-no-ssa.
39 kkz 1.1.2.1 */
40 cananian 1.2.2.1 public QuadLiveness(HCode<Quad> hc) {
41 kkz 1.1.2.1 super(hc);
42 cananian 1.4 List<Map<Quad,Set<Temp>>> live = this.analyze();
43 cananian 1.4 this.livein = live.get(0);
44 cananian 1.4 this.liveout = live.get(1);
45 cananian 1.2.2.1 this.tempin = new HashMap<Quad,Temp[]>();
46 cananian 1.2.2.1 this.tempout = new HashMap<Quad,Temp[]>();
47 cananian 1.2.2.1 this.tempinout = new HashMap<Quad,Temp[]>();
48 kkz 1.1.2.1 }
49 kkz 1.1.2.1
50 kkz 1.1.2.1 /** Returns the <code>Set</code> of <code>Temp</code>s
51 kkz 1.1.2.1 * that are live-in at the <code>HCodeElement</code>.
52 kkz 1.1.2.1 * Requires that the <code>HCodeElement</code> be in
53 kkz 1.1.2.1 * quad-no-ssa form. Returns <code>null</code> if there
54 kkz 1.1.2.1 * no live-in variables.
55 kkz 1.1.2.1 */
56 cananian 1.2.2.1 public Set<Temp> getLiveIn(Quad hce) {
57 cananian 1.2.2.1 return new WorkSet<Temp>(livein.get(hce));
58 kkz 1.1.2.1 }
59 bdemsky 1.1.2.4 /** Same as getLiveIn, but returns array of <code>Temp</code>s. This
60 bdemsky 1.1.2.4 array is guaranteed to have the Temp's in the same order for a given
61 bdemsky 1.1.2.4 QuadLiveness object,Quad pair.**/
62 kkz 1.1.2.1
63 cananian 1.2.2.1 public Temp[] getLiveInArray(Quad hce) {
64 bdemsky 1.1.2.4 if (tempin.containsKey(hce))
65 cananian 1.2.2.1 return Util.safeCopy(Temp.arrayFactory, tempin.get(hce));
66 bdemsky 1.1.2.4 else {
67 cananian 1.2.2.1 Set<Temp> set = this.livein.get(hce);
68 cananian 1.2.2.1 Temp[] retval = set.toArray(new Temp[set.size()]);
69 bdemsky 1.1.2.4 tempin.put(hce,retval);
70 cananian 1.2.2.1 return Util.safeCopy(Temp.arrayFactory, retval);
71 bdemsky 1.1.2.4 }
72 bdemsky 1.1.2.3 }
73 kkz 1.1.2.1 /** Returns the <code>Set</code> of <code>Temp</code>s
74 kkz 1.1.2.1 * that are live-out at the <code>HCodeElement</code>.
75 kkz 1.1.2.1 * Requires that the <code>HCodeElement</code> be in
76 kkz 1.1.2.1 * quad-no-ssa form. Returns <code>null</code> if there
77 kkz 1.1.2.1 * no live-in variables.
78 kkz 1.1.2.1 */
79 cananian 1.2.2.1 public Set<Temp> getLiveOut(Quad hce) {
80 cananian 1.2.2.1 return new WorkSet<Temp>(liveout.get(hce));
81 bdemsky 1.1.2.3 }
82 bdemsky 1.1.2.3
83 bdemsky 1.1.2.4 /** Same as getLiveOut, but returns array of <code>Temp</code>s.
84 bdemsky 1.1.2.4 Makes the same order guarantees as <code>getLiveInArray</code>.**/
85 cananian 1.2.2.1 public Temp[] getLiveOutArray(Quad hce) {
86 bdemsky 1.1.2.4 if (tempout.containsKey(hce))
87 cananian 1.2.2.1 return Util.safeCopy(Temp.arrayFactory, tempout.get(hce));
88 bdemsky 1.1.2.4 else {
89 cananian 1.2.2.1 Set<Temp> set = this.liveout.get(hce);
90 cananian 1.2.2.1 Temp[] retval = set.toArray(new Temp[set.size()]);
91 bdemsky 1.1.2.4 tempout.put(hce, retval);
92 cananian 1.2.2.1 return Util.safeCopy(Temp.arrayFactory, retval);
93 cananian 1.1.2.5 }
94 cananian 1.1.2.5 }
95 cananian 1.1.2.5
96 cananian 1.2.2.1 public Temp[] getLiveInandOutArray(Quad hce) {
97 cananian 1.1.2.5 if (tempinout.containsKey(hce))
98 cananian 1.2.2.1 return Util.safeCopy(Temp.arrayFactory, tempinout.get(hce));
99 cananian 1.1.2.5 else {
100 cananian 1.2.2.1 Set<Temp> set = this.liveout.get(hce);
101 cananian 1.2.2.1 Set<Temp> setin = this.livein.get(hce);
102 cananian 1.2.2.1 Iterator<Temp> iter=set.iterator();
103 cananian 1.1.2.5 int count=0;
104 cananian 1.1.2.5 while (iter.hasNext())
105 cananian 1.1.2.5 if (setin.contains(iter.next()))
106 cananian 1.1.2.5 count++;
107 cananian 1.1.2.5 Temp[] retval=new Temp[count];
108 cananian 1.1.2.5 iter=set.iterator();
109 cananian 1.1.2.5 count=0;
110 cananian 1.1.2.5 while (iter.hasNext()) {
111 cananian 1.2.2.1 Temp tt = iter.next();
112 cananian 1.1.2.5 if (setin.contains(tt))
113 cananian 1.1.2.5 retval[count++]=tt;
114 cananian 1.1.2.5 }
115 cananian 1.1.2.5 tempinout.put(hce, retval);
116 cananian 1.2.2.1 return Util.safeCopy(Temp.arrayFactory, retval);
117 bdemsky 1.1.2.4 }
118 kkz 1.1.2.1 }
119 kkz 1.1.2.1
120 cananian 1.4 private List<Map<Quad,Set<Temp>>> analyze() {
121 cananian 1.1.2.6 //System.err.println("Entering QuadLiveness.analyze()");
122 cananian 1.2.2.1 WorkSet<Quad> ws = new WorkSet<Quad>(this.hc.getElementsL());
123 kkz 1.1.2.1
124 kkz 1.1.2.1 if (ws.isEmpty()) {
125 cananian 1.1.2.6 //System.err.println("Leaving QuadLiveness.analyze()");
126 cananian 1.4 return Collections.<Map<Quad,Set<Temp>>>nCopies
127 cananian 1.4 (2, Default.<Quad,Set<Temp>>EMPTY_MAP());
128 kkz 1.1.2.1 }
129 kkz 1.1.2.1
130 cananian 1.2.2.1 Quad[] leaves = this.hc.getLeafElements();
131 kkz 1.1.2.1
132 kkz 1.1.2.1 // For efficiency reasons, we want to start w/ a leaf
133 kkz 1.1.2.1 // element if one exists. Otherwise, just start w/
134 kkz 1.1.2.1 // any element.
135 kkz 1.1.2.1 Quad hce = null;
136 kkz 1.1.2.1 if (leaves != null) {
137 cananian 1.2.2.1 hce = leaves[0];
138 kkz 1.1.2.1 ws.remove(hce);
139 kkz 1.1.2.1 } else {
140 cananian 1.4 hce = ws.removeLast();
141 kkz 1.1.2.1 }
142 kkz 1.1.2.1
143 cananian 1.2.2.1 Map<Quad,Set<Temp>> in = new HashMap<Quad,Set<Temp>>();
144 cananian 1.2.2.1 Map<Quad,Set<Temp>> out = new HashMap<Quad,Set<Temp>>();
145 kkz 1.1.2.1
146 kkz 1.1.2.1 while (true) {
147 cananian 1.2.2.1 Set<Temp> out_ = new WorkSet<Temp>();
148 kkz 1.1.2.1
149 kkz 1.1.2.1
150 bdemsky 1.1.2.7 for (int i=0;i<hce.nextLength();i++) {
151 bdemsky 1.1.2.7 Quad successor=hce.next(i);
152 kkz 1.1.2.1 if (in.containsKey(successor)) {
153 bdemsky 1.1.2.7 if (successor instanceof PHI) {
154 cananian 1.2.2.1 WorkSet<Temp> w=new WorkSet<Temp>(out.get(successor));
155 bdemsky 1.1.2.9
156 bdemsky 1.1.2.9 //search for successor
157 bdemsky 1.1.2.9 int edge=hce.nextEdge(i).which_pred();
158 bdemsky 1.1.2.9 PHI phi=(PHI)successor;
159 bdemsky 1.1.2.9
160 bdemsky 1.1.2.9 for (int j=0;j<phi.numPhis();j++)
161 bdemsky 1.1.2.9 w.remove(phi.dst(j));
162 bdemsky 1.1.2.9
163 bdemsky 1.1.2.9 for (int j=0;j<phi.numPhis();j++)
164 bdemsky 1.1.2.9 w.add(phi.src(j,edge));
165 bdemsky 1.1.2.9 out_.addAll(w);
166 bdemsky 1.1.2.9 } else
167 cananian 1.2.2.1 out_.addAll(in.get(successor));
168 kkz 1.1.2.1 }
169 kkz 1.1.2.1 }
170 kkz 1.1.2.1
171 kkz 1.1.2.8 // Calculate "in" Set
172 cananian 1.2.2.1 Set<Temp> in_ = new WorkSet<Temp>(out_);
173 kkz 1.1.2.8 in_.removeAll(hce.defC());
174 kkz 1.1.2.8 in_.addAll(hce.useC());
175 kkz 1.1.2.1
176 kkz 1.1.2.1 // If we have grown our live-in or live-out variables,
177 kkz 1.1.2.1 // we need to update all of its predecessors.
178 cananian 1.2.2.1 // TRICK: doing a put on a Map returns the previous mapping
179 cananian 1.2.2.1 Set<Temp> old_in = in.put(hce, in_);
180 cananian 1.2.2.1 Set<Temp> old_out = out.put(hce, out_);
181 bdemsky 1.1.2.7 if ((old_in == null)|| (old_in.size() < in_.size())) {
182 bdemsky 1.1.2.7 for (int i=0;i<hce.prevLength();i++)
183 kkz 1.1.2.8 ws.push(hce.prev(i));
184 bdemsky 1.1.2.7 } else if ((old_out == null)|| ( old_out.size() < out_.size())) {
185 bdemsky 1.1.2.7 for (int i=0;i<hce.prevLength();i++)
186 kkz 1.1.2.8 ws.push(hce.prev(i));
187 kkz 1.1.2.1 }
188 kkz 1.1.2.1
189 kkz 1.1.2.8 if (ws.isEmpty()) break;
190 cananian 1.4 hce = ws.removeLast();
191 kkz 1.1.2.1 }
192 cananian 1.4 List<Map<Quad,Set<Temp>>> retval=new ArrayList<Map<Quad,Set<Temp>>>(2);
193 cananian 1.4 retval.add(in); retval.add(out);
194 cananian 1.4 return retval;
195 kkz 1.1.2.1 }
196 kkz 1.1.2.1 }
197 cananian 1.2