1 /* 2 * Javassist, a Java-bytecode translator toolkit. 3 * Copyright (C) 1999-2007 Shigeru Chiba. All Rights Reserved. 4 * 5 * The contents of this file are subject to the Mozilla Public License Version 6 * 1.1 (the "License"); you may not use this file except in compliance with 7 * the License. Alternatively, the contents of this file may be used under 8 * the terms of the GNU Lesser General Public License Version 2.1 or later. 9 * 10 * Software distributed under the License is distributed on an "AS IS" basis, 11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License 12 * for the specific language governing rights and limitations under the 13 * License. 14 */ 15 16 package javassist.bytecode.stackmap; 17 18 import javassist.bytecode.*; 19 20 public class Liveness { 21 protected static final byte UNKNOWN = 0; 22 protected static final byte READ = 1; 23 protected static final byte UPDATED = 2; 24 protected byte[] localsUsage; 25 26 /** 27 * If true, all the arguments become alive within the whole method body. 28 * 29 * To correctly compute a stack map table, all the arguments must 30 * be alive (localsUsage[?] must be READ) at least in the first block. 31 */ 32 public static boolean useArgs = true; 33 compute(CodeIterator ci, TypedBlock[] blocks, int maxLocals, TypeData[] args)34 public void compute(CodeIterator ci, TypedBlock[] blocks, int maxLocals, 35 TypeData[] args) 36 throws BadBytecode 37 { 38 computeUsage(ci, blocks, maxLocals); 39 if (useArgs) 40 useAllArgs(blocks, args); 41 42 computeLiveness1(blocks[0]); 43 while (hasChanged(blocks)) 44 computeLiveness2(blocks[0]); 45 } 46 useAllArgs(TypedBlock[] blocks, TypeData[] args)47 private void useAllArgs(TypedBlock[] blocks, TypeData[] args) { 48 for (int k = 0; k < blocks.length; k++) { 49 byte[] usage = blocks[k].localsUsage; 50 for (int i = 0; i < args.length; i++) 51 if (args[i] != TypeTag.TOP) 52 usage[i] = READ; 53 } 54 } 55 56 static final int NOT_YET = 0; 57 static final int CHANGED_LAST = 1; 58 static final int DONE = 2; 59 static final int CHANGED_NOW = 3; 60 computeLiveness1(TypedBlock tb)61 private void computeLiveness1(TypedBlock tb) { 62 if (tb.updating) { 63 // a loop was detected. 64 computeLiveness1u(tb); 65 return; 66 } 67 68 if (tb.inputs != null) 69 return; 70 71 tb.updating = true; 72 byte[] usage = tb.localsUsage; 73 int n = usage.length; 74 boolean[] in = new boolean[n]; 75 for (int i = 0; i < n; i++) 76 in[i] = usage[i] == READ; 77 78 BasicBlock.Catch handlers = tb.toCatch; 79 while (handlers != null) { 80 TypedBlock h = (TypedBlock)handlers.body; 81 computeLiveness1(h); 82 for (int k = 0; k < n; k++) 83 if (h.inputs[k]) 84 in[k] = true; 85 86 handlers = handlers.next; 87 } 88 89 if (tb.exit != null) { 90 for (int i = 0; i < tb.exit.length; i++) { 91 TypedBlock e = (TypedBlock)tb.exit[i]; 92 computeLiveness1(e); 93 for (int k = 0; k < n; k++) 94 if (!in[k]) 95 in[k] = usage[k] == UNKNOWN && e.inputs[k]; 96 } 97 } 98 99 tb.updating = false; 100 if (tb.inputs == null) { 101 tb.inputs = in; 102 tb.status = DONE; 103 } 104 else { 105 for (int i = 0; i < n; i++) 106 if (in[i] && !tb.inputs[i]) { 107 tb.inputs[i] = true; 108 tb.status = CHANGED_NOW; 109 } 110 } 111 } 112 computeLiveness1u(TypedBlock tb)113 private void computeLiveness1u(TypedBlock tb) { 114 if (tb.inputs == null) { 115 byte[] usage = tb.localsUsage; 116 int n = usage.length; 117 boolean[] in = new boolean[n]; 118 for (int i = 0; i < n; i++) 119 in[i] = usage[i] == READ; 120 121 tb.inputs = in; 122 tb.status = DONE; 123 } 124 } 125 computeLiveness2(TypedBlock tb)126 private void computeLiveness2(TypedBlock tb) { 127 if (tb.updating || tb.status >= DONE) 128 return; 129 130 tb.updating = true; 131 if (tb.exit == null) 132 tb.status = DONE; 133 else { 134 boolean changed = false; 135 for (int i = 0; i < tb.exit.length; i++) { 136 TypedBlock e = (TypedBlock)tb.exit[i]; 137 computeLiveness2(e); 138 if (e.status != DONE) 139 changed = true; 140 } 141 142 if (changed) { 143 changed = false; 144 byte[] usage = tb.localsUsage; 145 int n = usage.length; 146 for (int i = 0; i < tb.exit.length; i++) { 147 TypedBlock e = (TypedBlock)tb.exit[i]; 148 if (e.status != DONE) 149 for (int k = 0; k < n; k++) 150 if (!tb.inputs[k]) { 151 if (usage[k] == UNKNOWN && e.inputs[k]) { 152 tb.inputs[k] = true; 153 changed = true; 154 } 155 } 156 } 157 158 tb.status = changed ? CHANGED_NOW : DONE; 159 } 160 else 161 tb.status = DONE; 162 } 163 164 if (computeLiveness2except(tb)) 165 tb.status = CHANGED_NOW; 166 167 tb.updating = false; 168 } 169 computeLiveness2except(TypedBlock tb)170 private boolean computeLiveness2except(TypedBlock tb) { 171 BasicBlock.Catch handlers = tb.toCatch; 172 boolean changed = false; 173 while (handlers != null) { 174 TypedBlock h = (TypedBlock)handlers.body; 175 computeLiveness2(h); 176 if (h.status != DONE) { 177 boolean[] in = tb.inputs; 178 int n = in.length; 179 for (int k = 0; k < n; k++) 180 if (!in[k] && h.inputs[k]) { 181 in[k] = true; 182 changed = true; 183 } 184 } 185 186 handlers = handlers.next; 187 } 188 189 return changed; 190 } 191 hasChanged(TypedBlock[] blocks)192 private boolean hasChanged(TypedBlock[] blocks) { 193 int n = blocks.length; 194 boolean changed = false; 195 for (int i = 0; i < n; i++) { 196 TypedBlock tb = blocks[i]; 197 if (tb.status == CHANGED_NOW) { 198 tb.status = CHANGED_LAST; 199 changed = true; 200 } 201 else 202 tb.status = NOT_YET; 203 } 204 205 return changed; 206 } 207 computeUsage(CodeIterator ci, TypedBlock[] blocks, int maxLocals)208 private void computeUsage(CodeIterator ci, TypedBlock[] blocks, int maxLocals) 209 throws BadBytecode 210 { 211 int n = blocks.length; 212 for (int i = 0; i < n; i++) { 213 TypedBlock tb = blocks[i]; 214 localsUsage = tb.localsUsage = new byte[maxLocals]; 215 int pos = tb.position; 216 analyze(ci, pos, pos + tb.length); 217 localsUsage = null; 218 } 219 } 220 readLocal(int reg)221 protected final void readLocal(int reg) { 222 if (localsUsage[reg] == UNKNOWN) 223 localsUsage[reg] = READ; 224 } 225 writeLocal(int reg)226 protected final void writeLocal(int reg) { 227 if (localsUsage[reg] == UNKNOWN) 228 localsUsage[reg] = UPDATED; 229 } 230 analyze(CodeIterator ci, int begin, int end)231 protected void analyze(CodeIterator ci, int begin, int end) 232 throws BadBytecode 233 { 234 ci.begin(); 235 ci.move(begin); 236 while (ci.hasNext()) { 237 int index = ci.next(); 238 if (index >= end) 239 break; 240 241 int op = ci.byteAt(index); 242 if (op < 96) 243 if (op < 54) 244 doOpcode0_53(ci, index, op); 245 else 246 doOpcode54_95(ci, index, op); 247 else 248 if (op == Opcode.IINC) { 249 // this does not call writeLocal(). 250 readLocal(ci.byteAt(index + 1)); 251 } 252 else if (op == Opcode.WIDE) 253 doWIDE(ci, index); 254 } 255 } 256 doOpcode0_53(CodeIterator ci, int pos, int op)257 private void doOpcode0_53(CodeIterator ci, int pos, int op) { 258 switch (op) { 259 case Opcode.ILOAD : 260 case Opcode.LLOAD : 261 case Opcode.FLOAD : 262 case Opcode.DLOAD : 263 case Opcode.ALOAD : 264 readLocal(ci.byteAt(pos + 1)); 265 break; 266 case Opcode.ILOAD_0 : 267 case Opcode.ILOAD_1 : 268 case Opcode.ILOAD_2 : 269 case Opcode.ILOAD_3 : 270 readLocal(op - Opcode.ILOAD_0); 271 break; 272 case Opcode.LLOAD_0 : 273 case Opcode.LLOAD_1 : 274 case Opcode.LLOAD_2 : 275 case Opcode.LLOAD_3 : 276 readLocal(op - Opcode.LLOAD_0); 277 break; 278 case Opcode.FLOAD_0 : 279 case Opcode.FLOAD_1 : 280 case Opcode.FLOAD_2 : 281 case Opcode.FLOAD_3 : 282 readLocal(op - Opcode.FLOAD_0); 283 break; 284 case Opcode.DLOAD_0 : 285 case Opcode.DLOAD_1 : 286 case Opcode.DLOAD_2 : 287 case Opcode.DLOAD_3 : 288 readLocal(op - Opcode.DLOAD_0); 289 break; 290 case Opcode.ALOAD_0 : 291 case Opcode.ALOAD_1 : 292 case Opcode.ALOAD_2 : 293 case Opcode.ALOAD_3 : 294 readLocal(op - Opcode.ALOAD_0); 295 break; 296 } 297 } 298 doOpcode54_95(CodeIterator ci, int pos, int op)299 private void doOpcode54_95(CodeIterator ci, int pos, int op) { 300 switch (op) { 301 case Opcode.ISTORE : 302 case Opcode.LSTORE : 303 case Opcode.FSTORE : 304 case Opcode.DSTORE : 305 case Opcode.ASTORE : 306 writeLocal(ci.byteAt(pos + 1)); 307 break; 308 case Opcode.ISTORE_0 : 309 case Opcode.ISTORE_1 : 310 case Opcode.ISTORE_2 : 311 case Opcode.ISTORE_3 : 312 writeLocal(op - Opcode.ISTORE_0); 313 break; 314 case Opcode.LSTORE_0 : 315 case Opcode.LSTORE_1 : 316 case Opcode.LSTORE_2 : 317 case Opcode.LSTORE_3 : 318 writeLocal(op - Opcode.LSTORE_0); 319 break; 320 case Opcode.FSTORE_0 : 321 case Opcode.FSTORE_1 : 322 case Opcode.FSTORE_2 : 323 case Opcode.FSTORE_3 : 324 writeLocal(op - Opcode.FSTORE_0); 325 break; 326 case Opcode.DSTORE_0 : 327 case Opcode.DSTORE_1 : 328 case Opcode.DSTORE_2 : 329 case Opcode.DSTORE_3 : 330 writeLocal(op - Opcode.DSTORE_0); 331 break; 332 case Opcode.ASTORE_0 : 333 case Opcode.ASTORE_1 : 334 case Opcode.ASTORE_2 : 335 case Opcode.ASTORE_3 : 336 writeLocal(op - Opcode.ASTORE_0); 337 break; 338 } 339 } 340 doWIDE(CodeIterator ci, int pos)341 private void doWIDE(CodeIterator ci, int pos) throws BadBytecode { 342 int op = ci.byteAt(pos + 1); 343 int var = ci.u16bitAt(pos + 2); 344 switch (op) { 345 case Opcode.ILOAD : 346 case Opcode.LLOAD : 347 case Opcode.FLOAD : 348 case Opcode.DLOAD : 349 case Opcode.ALOAD : 350 readLocal(var); 351 break; 352 case Opcode.ISTORE : 353 case Opcode.LSTORE : 354 case Opcode.FSTORE : 355 case Opcode.DSTORE : 356 case Opcode.ASTORE : 357 writeLocal(var); 358 break; 359 case Opcode.IINC : 360 readLocal(var); 361 // this does not call writeLocal(). 362 break; 363 } 364 } 365 } 366