1/* 2 * ProGuard -- shrinking, optimization, obfuscation, and preverification 3 * of Java bytecode. 4 * 5 * Copyright (c) 2002-2009 Eric Lafortune (eric@graphics.cornell.edu) 6 * 7 * This program is free software; you can redistribute it and/or modify it 8 * under the terms of the GNU General Public License as published by the Free 9 * Software Foundation; either version 2 of the License, or (at your option) 10 * any later version. 11 * 12 * This program is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 15 * more details. 16 * 17 * You should have received a copy of the GNU General Public License along 18 * with this program; if not, write to the Free Software Foundation, Inc., 19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 20 */ 21package proguard.optimize.evaluation; 22 23import proguard.classfile.*; 24import proguard.classfile.attribute.*; 25import proguard.classfile.attribute.visitor.*; 26import proguard.classfile.instruction.*; 27import proguard.classfile.instruction.visitor.InstructionVisitor; 28import proguard.classfile.util.SimplifiedVisitor; 29import proguard.evaluation.value.*; 30 31/** 32 * This AttributeVisitor analyzes the liveness of the variables in the code 33 * attributes that it visits, based on partial evaluation. 34 * 35 * @author Eric Lafortune 36 */ 37public class LivenessAnalyzer 38extends SimplifiedVisitor 39implements AttributeVisitor, 40 InstructionVisitor, 41 ExceptionInfoVisitor 42{ 43 //* 44 private static final boolean DEBUG = false; 45 /*/ 46 private static boolean DEBUG = true; 47 //*/ 48 49 private static final int MAX_VARIABLES_SIZE = 64; 50 51 private final PartialEvaluator partialEvaluator; 52 53 private long[] isAliveBefore = new long[ClassConstants.TYPICAL_CODE_LENGTH]; 54 private long[] isAliveAfter = new long[ClassConstants.TYPICAL_CODE_LENGTH]; 55 private long[] isCategory2 = new long[ClassConstants.TYPICAL_CODE_LENGTH]; 56 57 // Fields acting as global temporary variables. 58 private boolean checkAgain; 59 private long alive; 60 61 62 /** 63 * Creates a new LivenessAnalyzer. 64 */ 65 public LivenessAnalyzer() 66 { 67 this(new PartialEvaluator()); 68 } 69 70 71 /** 72 * Creates a new LivenessAnalyzer that will use the given partial evaluator. 73 * It will run this evaluator on every code attribute that it visits. 74 */ 75 public LivenessAnalyzer(PartialEvaluator partialEvaluator) 76 { 77 this.partialEvaluator = partialEvaluator; 78 } 79 80 81 /** 82 * Returns whether the specified variable is alive before the instruction 83 * at the given offset. 84 */ 85 public boolean isAliveBefore(int instructionOffset, int variableIndex) 86 { 87 return variableIndex >= MAX_VARIABLES_SIZE || 88 (isAliveBefore[instructionOffset] & (1L << variableIndex)) != 0; 89 } 90 91 92 /** 93 * Sets whether the specified variable is alive before the instruction 94 * at the given offset. 95 */ 96 public void setAliveBefore(int instructionOffset, int variableIndex, boolean alive) 97 { 98 if (variableIndex < MAX_VARIABLES_SIZE) 99 { 100 if (alive) 101 { 102 isAliveBefore[instructionOffset] |= 1L << variableIndex; 103 } 104 else 105 { 106 isAliveBefore[instructionOffset] &= ~(1L << variableIndex); 107 } 108 } 109 } 110 111 112 /** 113 * Returns whether the specified variable is alive after the instruction 114 * at the given offset. 115 */ 116 public boolean isAliveAfter(int instructionOffset, int variableIndex) 117 { 118 return variableIndex >= MAX_VARIABLES_SIZE || 119 (isAliveAfter[instructionOffset] & (1L << variableIndex)) != 0; 120 } 121 122 123 /** 124 * Sets whether the specified variable is alive after the instruction 125 * at the given offset. 126 */ 127 public void setAliveAfter(int instructionOffset, int variableIndex, boolean alive) 128 { 129 if (variableIndex < MAX_VARIABLES_SIZE) 130 { 131 if (alive) 132 { 133 isAliveAfter[instructionOffset] |= 1L << variableIndex; 134 } 135 else 136 { 137 isAliveAfter[instructionOffset] &= ~(1L << variableIndex); 138 } 139 } 140 } 141 142 143 /** 144 * Returns whether the specified variable takes up two entries after the 145 * instruction at the given offset. 146 */ 147 public boolean isCategory2(int instructionOffset, int variableIndex) 148 { 149 return variableIndex < MAX_VARIABLES_SIZE && 150 (isCategory2[instructionOffset] & (1L << variableIndex)) != 0; 151 } 152 153 154 /** 155 * Sets whether the specified variable takes up two entries after the 156 * instruction at the given offset. 157 */ 158 public void setCategory2(int instructionOffset, int variableIndex, boolean category2) 159 { 160 if (variableIndex < MAX_VARIABLES_SIZE) 161 { 162 if (category2) 163 { 164 isCategory2[instructionOffset] |= 1L << variableIndex; 165 } 166 else 167 { 168 isCategory2[instructionOffset] &= ~(1L << variableIndex); 169 } 170 } 171 } 172 173 174 // Implementations for AttributeVisitor. 175 176 public void visitAnyAttribute(Clazz clazz, Attribute attribute) {} 177 178 179 public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute) 180 { 181// DEBUG = 182// clazz.getName().equals("abc/Def") && 183// method.getName(clazz).equals("abc"); 184 185 if (DEBUG) 186 { 187 System.out.println(); 188 System.out.println("Liveness analysis: "+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)); 189 } 190 191 // Initialize the global arrays. 192 initializeArrays(codeAttribute); 193 194 // Evaluate the method. 195 partialEvaluator.visitCodeAttribute(clazz, method, codeAttribute); 196 197 int codeLength = codeAttribute.u4codeLength; 198 int variablesSize = codeAttribute.u2maxLocals; 199 200 // We'll only really analyze the first 64 variables. 201 if (variablesSize > MAX_VARIABLES_SIZE) 202 { 203 variablesSize = MAX_VARIABLES_SIZE; 204 } 205 206 // Mark liveness blocks, as many times as necessary. 207 do 208 { 209 checkAgain = false; 210 alive = 0L; 211 212 // Loop over all traced instructions, backward. 213 for (int offset = codeLength - 1; offset >= 0; offset--) 214 { 215 if (partialEvaluator.isTraced(offset)) 216 { 217 // Update the liveness based on the branch targets. 218 InstructionOffsetValue branchTargets = partialEvaluator.branchTargets(offset); 219 if (branchTargets != null) 220 { 221 // Update the liveness right after the branch instruction. 222 alive = combinedLiveness(branchTargets); 223 } 224 225 // Merge the current liveness. 226 alive |= isAliveAfter[offset]; 227 228 // Update the liveness after the instruction. 229 isAliveAfter[offset] = alive; 230 231 // Update the current liveness based on the instruction. 232 codeAttribute.instructionAccept(clazz, method, offset, this); 233 234 // Merge the current liveness. 235 alive |= isAliveBefore[offset]; 236 237 // Update the liveness before the instruction. 238 if ((~isAliveBefore[offset] & alive) != 0L) 239 { 240 isAliveBefore[offset] = alive; 241 242 // Do we have to check again after this loop? 243 checkAgain |= offset < maxOffset(partialEvaluator.branchOrigins(offset)); 244 } 245 } 246 } 247 248 // Account for the liveness at the start of the exception handlers. 249 codeAttribute.exceptionsAccept(clazz, method, this); 250 } 251 while (checkAgain); 252 253 // Loop over all instructions, to mark variables that take up two entries. 254 for (int offset = 0; offset < codeLength; offset++) 255 { 256 if (partialEvaluator.isTraced(offset)) 257 { 258 // Loop over all variables. 259 for (int variableIndex = 0; variableIndex < variablesSize; variableIndex++) 260 { 261 // Is the variable alive and a category 2 type? 262 if (isAliveBefore(offset, variableIndex)) 263 { 264 Value value = partialEvaluator.getVariablesBefore(offset).getValue(variableIndex); 265 if (value != null && value.isCategory2()) 266 { 267 // Mark it as such. 268 setCategory2(offset, variableIndex, true); 269 270 // Mark the next variable as well. 271 setAliveBefore(offset, variableIndex + 1, true); 272 setCategory2( offset, variableIndex + 1, true); 273 } 274 } 275 276 // Is the variable alive and a category 2 type? 277 if (isAliveAfter(offset, variableIndex)) 278 { 279 Value value = partialEvaluator.getVariablesAfter(offset).getValue(variableIndex); 280 if (value != null && value.isCategory2()) 281 { 282 // Mark it as such. 283 setCategory2(offset, variableIndex, true); 284 285 // Mark the next variable as well. 286 setAliveAfter(offset, variableIndex + 1, true); 287 setCategory2( offset, variableIndex + 1, true); 288 } 289 } 290 } 291 } 292 } 293 294 if (DEBUG) 295 { 296 // Loop over all instructions. 297 for (int offset = 0; offset < codeLength; offset++) 298 { 299 if (partialEvaluator.isTraced(offset)) 300 { 301 long aliveBefore = isAliveBefore[offset]; 302 long aliveAfter = isAliveAfter[offset]; 303 long category2 = isCategory2[offset]; 304 305 // Print out the liveness of all variables before the instruction. 306 for (int variableIndex = 0; variableIndex < variablesSize; variableIndex++) 307 { 308 long variableMask = (1L << variableIndex); 309 System.out.print((aliveBefore & variableMask) == 0L ? '.' : 310 (category2 & variableMask) == 0L ? 'x' : 311 '*'); 312 } 313 314 // Print out the instruction itself. 315 System.out.println(" "+ InstructionFactory.create(codeAttribute.code, offset).toString(offset)); 316 317 // Print out the liveness of all variables after the instruction. 318 for (int variableIndex = 0; variableIndex < variablesSize; variableIndex++) 319 { 320 long variableMask = (1L << variableIndex); 321 System.out.print((aliveAfter & variableMask) == 0L ? '.' : 322 (category2 & variableMask) == 0L ? 'x' : 323 '='); 324 } 325 326 System.out.println(); 327 } 328 } 329 } 330 } 331 332 333 // Implementations for InstructionVisitor. 334 335 public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) {} 336 337 338 public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction) 339 { 340 int variableIndex = variableInstruction.variableIndex; 341 if (variableIndex < MAX_VARIABLES_SIZE) 342 { 343 long livenessMask = 1L << variableIndex; 344 345 // Is it a load instruction or a store instruction? 346 if (variableInstruction.isLoad()) 347 { 348 // Start marking the variable before the load instruction. 349 alive |= livenessMask; 350 } 351 else 352 { 353 // Stop marking the variable before the store instruction. 354 alive &= ~livenessMask; 355 356 // But do mark the variable right after the store instruction. 357 isAliveAfter[offset] |= livenessMask; 358 } 359 } 360 } 361 362 363 public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction) 364 { 365 // Special case: variable 0 ('this') in an initializer has to be alive 366 // as long as it hasn't been initialized. 367 if (offset == partialEvaluator.superInitializationOffset()) 368 { 369 alive |= 1L; 370 } 371 } 372 373 374 // Implementations for ExceptionInfoVisitor. 375 376 public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo) 377 { 378 // Are any variables alive at the start of the handler? 379 long alive = isAliveBefore[exceptionInfo.u2handlerPC]; 380 if (alive != 0L) 381 { 382 // Set the same liveness flags for the entire try block. 383 int startOffset = exceptionInfo.u2startPC; 384 int endOffset = exceptionInfo.u2endPC; 385 386 for (int offset = startOffset; offset < endOffset; offset++) 387 { 388 if (partialEvaluator.isTraced(offset)) 389 { 390 if ((~(isAliveBefore[offset] & isAliveAfter[offset]) & alive) != 0L) 391 { 392 isAliveBefore[offset] |= alive; 393 isAliveAfter[offset] |= alive; 394 395 // Check again after having marked this try block. 396 checkAgain = true; 397 } 398 } 399 } 400 } 401 } 402 403 404 // Small utility methods. 405 406 /** 407 * Initializes the global arrays. 408 */ 409 private void initializeArrays(CodeAttribute codeAttribute) 410 { 411 int codeLength = codeAttribute.u4codeLength; 412 413 // Create new arrays for storing information at each instruction offset. 414 if (isAliveBefore.length < codeLength) 415 { 416 isAliveBefore = new long[codeLength]; 417 isAliveAfter = new long[codeLength]; 418 isCategory2 = new long[codeLength]; 419 } 420 else 421 { 422 for (int index = 0; index < codeLength; index++) 423 { 424 isAliveBefore[index] = 0L; 425 isAliveAfter[index] = 0L; 426 isCategory2[index] = 0L; 427 } 428 } 429 } 430 431 432 /** 433 * Returns the combined liveness mask of the variables right before the 434 * specified instruction offsets. 435 */ 436 private long combinedLiveness(InstructionOffsetValue instructionOffsetValue) 437 { 438 long alive = 0L; 439 440 int count = instructionOffsetValue.instructionOffsetCount(); 441 for (int index = 0; index < count; index++) 442 { 443 alive |= isAliveBefore[instructionOffsetValue.instructionOffset(index)]; 444 } 445 446 return alive; 447 } 448 449 450 /** 451 * Returns the minimum offset from the given instruction offsets. 452 */ 453 private int minOffset(Value instructionOffsets) 454 { 455 return minOffset(instructionOffsets, Integer.MAX_VALUE); 456 } 457 458 459 /** 460 * Returns the minimum offset from the given instruction offsets. 461 */ 462 private int minOffset(Value instructionOffsets, int minOffset) 463 { 464 if (instructionOffsets != null) 465 { 466 InstructionOffsetValue instructionOffsetValue = 467 instructionOffsets.instructionOffsetValue(); 468 469 int count = instructionOffsetValue.instructionOffsetCount(); 470 for (int index = 0; index < count; index++) 471 { 472 int offset = instructionOffsetValue.instructionOffset(index); 473 if (minOffset > offset) 474 { 475 minOffset = offset; 476 } 477 } 478 } 479 480 return minOffset; 481 } 482 483 484 /** 485 * Returns the maximum offset from the given instruction offsets. 486 */ 487 private int maxOffset(Value instructionOffsets) 488 { 489 return maxOffset(instructionOffsets, Integer.MIN_VALUE); 490 } 491 492 493 /** 494 * Returns the maximum offset from the given instruction offsets. 495 */ 496 private int maxOffset(Value instructionOffsets, int maxOffset) 497 { 498 if (instructionOffsets != null) 499 { 500 InstructionOffsetValue instructionOffsetValue = 501 instructionOffsets.instructionOffsetValue(); 502 503 int count = instructionOffsetValue.instructionOffsetCount(); 504 for (int index = 0; index < count; index++) 505 { 506 int offset = instructionOffsetValue.instructionOffset(index); 507 if (maxOffset < offset) 508 { 509 maxOffset = offset; 510 } 511 } 512 } 513 514 return maxOffset; 515 } 516} 517