1 cananian 1.1.2.1 // Liveness.java, created Mon Feb 22 23:03:30 1999 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1999 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.IR.Bytecode;
5 cananian 1.1.2.1
6 cananian 1.1.2.3 import java.util.AbstractSet;
7 cananian 1.1.2.1 import java.util.BitSet;
8 cananian 1.1.2.1 import java.util.HashMap;
9 cananian 1.1.2.1 import java.util.Iterator;
10 cananian 1.1.2.1 import java.util.Set;
11 cananian 1.1.2.1
12 cananian 1.4 import net.cscott.jutil.FilterIterator;
13 cananian 1.4 import net.cscott.jutil.UnmodifiableIterator;
14 cananian 1.4 import net.cscott.jutil.WorkSet;
15 cananian 1.1.2.1 /**
16 cananian 1.1.2.1 * <code>Liveness</code> is a local-variable liveness analysis on Bytecode
17 cananian 1.1.2.1 * form.
18 cananian 1.1.2.1 *
19 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
20 cananian 1.4 * @version $Id: Liveness.java,v 1.4 2004/02/08 01:55:10 cananian Exp $
21 cananian 1.1.2.1 */
22 cananian 1.1.2.1 public class Liveness {
23 cananian 1.1.2.1 /** internal data structure is a hashtable of boolean arrays */
24 cananian 1.1.2.1 private LiveMap live;
25 cananian 1.1.2.1 /** Return the liveness of local variable #<code>lv_index</code> at
26 cananian 1.1.2.1 * instruction <code>where</code>. */
27 cananian 1.1.2.1 public boolean isLive(Instr where, int lv_index) {
28 cananian 1.1.2.1 return live.get(where).isLive(lv_index);
29 cananian 1.1.2.1 }
30 cananian 1.1.2.3 /** Return a <code>Collection</code> of live local variables at the
31 cananian 1.1.2.3 * given instruction <code>where</code>. */
32 cananian 1.1.2.3 public Set liveSet(Instr where) {
33 cananian 1.1.2.3 return live.get(where).asCollection();
34 cananian 1.1.2.3 }
35 cananian 1.1.2.1
36 cananian 1.1.2.1 /** Creates a <code>Liveness</code>. */
37 cananian 1.1.2.1 public Liveness(Code bcode) {
38 cananian 1.1.2.1 int max_locals = bcode.getMaxLocals();
39 cananian 1.1.2.1 this.live = new LiveMap(max_locals);
40 cananian 1.1.2.1 /* add all elements to the workset initially. */
41 cananian 1.1.2.1 WorkSet workset = new WorkSet(bcode.getElementsL());
42 cananian 1.1.2.1 /* iterate until stable. */
43 cananian 1.1.2.1 while (!workset.isEmpty()) {
44 cananian 1.1.2.4 Instr in = (Instr) workset.pop();
45 cananian 1.1.2.1 LiveSet liveIn = new LiveSet(max_locals);
46 cananian 1.1.2.1 if (Op.JSR == in.getOpcode() || Op.JSR_W == in.getOpcode()) {
47 cananian 1.1.2.1 // jsrs are special: live set of subroutine except where
48 cananian 1.1.2.1 // undefined, where we use live set of next instr.
49 cananian 1.1.2.1 LiveSet liveNext=live.get(in.next(0));//live set of next instr
50 cananian 1.1.2.1 liveIn.or(live.get(in.next(1))); // live set of subroutine.
51 cananian 1.1.2.1 for (int i=0; i<max_locals; i++)
52 cananian 1.1.2.1 // for those locals which the subroutine doesn't touch...
53 cananian 1.1.2.1 if (!liveIn.isDefined(i) && liveNext.isDefined(i))
54 cananian 1.1.2.1 // use the liveSet of the next instruction.
55 cananian 1.1.2.1 if (liveNext.isLive(i))
56 cananian 1.1.2.1 liveIn.markLive(i);
57 cananian 1.1.2.1 else
58 cananian 1.1.2.1 liveIn.markDead(i);
59 cananian 1.1.2.1 } else {
60 cananian 1.1.2.1 // if it is in the live set of a successor and I don't define
61 cananian 1.1.2.1 // it, then it is in the live set here.
62 cananian 1.1.2.1 for (Iterator i=in.next.iterator(); i.hasNext(); )
63 cananian 1.1.2.1 liveIn.or(live.get((Instr) i.next()));
64 cananian 1.1.2.1 }
65 cananian 1.1.2.1 // if it is defined here, then it is dead.
66 cananian 1.1.2.1 int defs = def(in);
67 cananian 1.1.2.1 if (defs != -1) {
68 cananian 1.1.2.1 liveIn.markDead(defs);
69 cananian 1.1.2.1 if (isLong(in))
70 cananian 1.1.2.1 liveIn.markDead(defs+1);
71 cananian 1.1.2.1 }
72 cananian 1.1.2.1 // if this instruction uses a local variable, it is in the live set
73 cananian 1.1.2.1 // (note how liveness beats deadness in the case of Op.IINC)
74 cananian 1.1.2.1 int uses = use(in);
75 cananian 1.1.2.1 if (uses!=-1) {
76 cananian 1.1.2.1 liveIn.markLive(uses);
77 cananian 1.1.2.1 if (isLong(in))
78 cananian 1.1.2.1 liveIn.markLive(uses+1);
79 cananian 1.1.2.1 }
80 cananian 1.1.2.2 // optimization hack: try to share LiveSets.
81 cananian 1.1.2.2 if (in.next.size()>0 && live.get(in.next(0)).equals(liveIn))
82 cananian 1.1.2.2 liveIn = live.get(in.next(0)); // share livesets if equal.
83 cananian 1.1.2.2
84 cananian 1.1.2.2 // if live set has changed, add predecessors to work set
85 cananian 1.1.2.1 boolean changed = live.update(in, liveIn);
86 cananian 1.1.2.1 if (changed)
87 cananian 1.1.2.1 for (Iterator i=in.prev.iterator(); i.hasNext(); )
88 cananian 1.1.2.1 workset.add(i.next());
89 cananian 1.1.2.1 }
90 cananian 1.1.2.1 }
91 cananian 1.1.2.1 // opcode properties.
92 cananian 1.1.2.1 private static int def(Instr in) {
93 cananian 1.1.2.1 switch(in.getOpcode()) {
94 cananian 1.1.2.1 case Op.ASTORE:
95 cananian 1.1.2.1 case Op.ASTORE_0: case Op.ASTORE_1:
96 cananian 1.1.2.1 case Op.ASTORE_2: case Op.ASTORE_3:
97 cananian 1.1.2.1 case Op.FSTORE:
98 cananian 1.1.2.1 case Op.FSTORE_0: case Op.FSTORE_1:
99 cananian 1.1.2.1 case Op.FSTORE_2: case Op.FSTORE_3:
100 cananian 1.1.2.1 case Op.ISTORE:
101 cananian 1.1.2.1 case Op.ISTORE_0: case Op.ISTORE_1:
102 cananian 1.1.2.1 case Op.ISTORE_2: case Op.ISTORE_3:
103 cananian 1.1.2.1 case Op.DSTORE:
104 cananian 1.1.2.1 case Op.DSTORE_0: case Op.DSTORE_1:
105 cananian 1.1.2.1 case Op.DSTORE_2: case Op.DSTORE_3:
106 cananian 1.1.2.1 case Op.LSTORE:
107 cananian 1.1.2.1 case Op.LSTORE_0: case Op.LSTORE_1:
108 cananian 1.1.2.1 case Op.LSTORE_2: case Op.LSTORE_3:
109 cananian 1.1.2.1 case Op.IINC: // both use *and* definition.
110 cananian 1.1.2.1 return ((OpLocalVariable)((InGen)in).getOperand(0)).getIndex();
111 cananian 1.1.2.1 default:
112 cananian 1.1.2.1 return -1;
113 cananian 1.1.2.1 }
114 cananian 1.1.2.1 }
115 cananian 1.1.2.1 private static int use(Instr in) {
116 cananian 1.1.2.1 switch(in.getOpcode()) {
117 cananian 1.1.2.1 case Op.ALOAD:
118 cananian 1.1.2.1 case Op.ALOAD_0: case Op.ALOAD_1:
119 cananian 1.1.2.1 case Op.ALOAD_2: case Op.ALOAD_3:
120 cananian 1.1.2.1 case Op.FLOAD:
121 cananian 1.1.2.1 case Op.FLOAD_0: case Op.FLOAD_1:
122 cananian 1.1.2.1 case Op.FLOAD_2: case Op.FLOAD_3:
123 cananian 1.1.2.1 case Op.ILOAD:
124 cananian 1.1.2.1 case Op.ILOAD_0: case Op.ILOAD_1:
125 cananian 1.1.2.1 case Op.ILOAD_2: case Op.ILOAD_3:
126 cananian 1.1.2.1 case Op.DLOAD:
127 cananian 1.1.2.1 case Op.DLOAD_0: case Op.DLOAD_1:
128 cananian 1.1.2.1 case Op.DLOAD_2: case Op.DLOAD_3:
129 cananian 1.1.2.1 case Op.LLOAD:
130 cananian 1.1.2.1 case Op.LLOAD_0: case Op.LLOAD_1:
131 cananian 1.1.2.1 case Op.LLOAD_2: case Op.LLOAD_3:
132 cananian 1.1.2.1 case Op.IINC: // both use *and* definition.
133 cananian 1.1.2.1 return ((OpLocalVariable)((InGen)in).getOperand(0)).getIndex();
134 cananian 1.1.2.1 case Op.RET: // use of local variable.
135 cananian 1.1.2.1 return ((OpLocalVariable)((InRet)in).getOperand()).getIndex();
136 cananian 1.1.2.1 default:
137 cananian 1.1.2.1 return -1;
138 cananian 1.1.2.1 }
139 cananian 1.1.2.1 }
140 cananian 1.1.2.1 private static boolean isLong(Instr in) {
141 cananian 1.1.2.1 switch (in.getOpcode()) {
142 cananian 1.1.2.1 case Op.DLOAD:
143 cananian 1.1.2.1 case Op.DLOAD_0: case Op.DLOAD_1:
144 cananian 1.1.2.1 case Op.DLOAD_2: case Op.DLOAD_3:
145 cananian 1.1.2.1 case Op.LLOAD:
146 cananian 1.1.2.1 case Op.LLOAD_0: case Op.LLOAD_1:
147 cananian 1.1.2.1 case Op.LLOAD_2: case Op.LLOAD_3:
148 cananian 1.1.2.1 case Op.DSTORE:
149 cananian 1.1.2.1 case Op.DSTORE_0: case Op.DSTORE_1:
150 cananian 1.1.2.1 case Op.DSTORE_2: case Op.DSTORE_3:
151 cananian 1.1.2.1 case Op.LSTORE:
152 cananian 1.1.2.1 case Op.LSTORE_0: case Op.LSTORE_1:
153 cananian 1.1.2.1 case Op.LSTORE_2: case Op.LSTORE_3:
154 cananian 1.1.2.1 return true;
155 cananian 1.1.2.1 default:
156 cananian 1.1.2.1 return false;
157 cananian 1.1.2.1 }
158 cananian 1.1.2.1 }
159 cananian 1.1.2.1 // liveness bitset
160 cananian 1.1.2.1 private class LiveSet extends java.util.BitSet {
161 cananian 1.1.2.1 LiveSet(int max_locals) { super(2*max_locals); }
162 cananian 1.1.2.1 // treat bits in pairs: (defined, live)
163 cananian 1.1.2.1 // so that: 0X = undefined, 10 = defined but dead, 11 = live.
164 cananian 1.1.2.1 public boolean isDefined(int which_lv) {
165 cananian 1.1.2.1 return get(2*which_lv);
166 cananian 1.1.2.1 }
167 cananian 1.1.2.1 public boolean isLive(int which_lv) {
168 cananian 1.1.2.1 return get(2*which_lv)/*defined*/ && get(2*which_lv+1)/*live*/;
169 cananian 1.1.2.1 }
170 cananian 1.1.2.1 public void markDead(int which_lv) {
171 cananian 1.1.2.1 set(2*which_lv); // defined.
172 cananian 1.1.2.1 clear(2*which_lv+1); // but dead.
173 cananian 1.1.2.1 }
174 cananian 1.1.2.1 public void markLive(int which_lv) {
175 cananian 1.1.2.1 set(2*which_lv); // defined
176 cananian 1.1.2.1 set(2*which_lv+1); // and live.
177 cananian 1.1.2.3 }
178 cananian 1.1.2.3 // collection view.
179 cananian 1.1.2.3 public Set asCollection() {
180 cananian 1.1.2.3 final int lvsize = size()/2;
181 cananian 1.1.2.3 return new AbstractSet() {
182 cananian 1.1.2.3 public int size() {
183 cananian 1.1.2.3 int size=0;
184 cananian 1.1.2.3 for (int i=0; i < lvsize; i++)
185 cananian 1.1.2.3 if (isLive(i)) size++;
186 cananian 1.1.2.3 return size;
187 cananian 1.1.2.3 }
188 cananian 1.1.2.3 public Iterator iterator() {
189 cananian 1.1.2.3 // simple integer iterator
190 cananian 1.1.2.5 Iterator i = new UnmodifiableIterator() {
191 cananian 1.1.2.3 int i=0;
192 cananian 1.1.2.3 public boolean hasNext() { return (i < lvsize); }
193 cananian 1.1.2.3 public Object next() { return new Integer(i++); }
194 cananian 1.1.2.3 };
195 cananian 1.1.2.3 // filtered by liveness method.
196 cananian 1.1.2.3 return new FilterIterator(i, new FilterIterator.Filter() {
197 cananian 1.1.2.3 public boolean isElement(Object o) {
198 cananian 1.1.2.3 return isLive(((Integer)o).intValue());
199 cananian 1.1.2.3 }
200 cananian 1.1.2.3 });
201 cananian 1.1.2.3 }
202 cananian 1.1.2.3 };
203 cananian 1.1.2.1 }
204 cananian 1.1.2.1 }
205 cananian 1.1.2.1
206 cananian 1.1.2.1 // liveness map data structure.
207 cananian 1.1.2.1 private class LiveMap {
208 cananian 1.1.2.1 private final HashMap hm = new HashMap();
209 cananian 1.1.2.1
210 cananian 1.1.2.1 private final LiveSet EMPTY; // all zero.
211 cananian 1.1.2.1 LiveMap(int max_locals) {
212 cananian 1.1.2.1 this.EMPTY = new LiveSet(max_locals);
213 cananian 1.1.2.1 }
214 cananian 1.1.2.1 LiveSet get(Instr in) {
215 cananian 1.1.2.1 if (!hm.containsKey(in)) return EMPTY;
216 cananian 1.1.2.1 return (LiveSet) hm.get(in);
217 cananian 1.1.2.1 }
218 cananian 1.1.2.1 boolean update(Instr in, LiveSet newset) {
219 cananian 1.1.2.1 if (get(in).equals(newset)) return false;
220 cananian 1.1.2.1 hm.put(in, newset);
221 cananian 1.1.2.1 return true;
222 cananian 1.1.2.1 }
223 cananian 1.1.2.1 }
224 cananian 1.2 }