1 /* 2 * Copyright (C) 2010 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.dx.ssa; 18 19 import com.android.dx.rop.code.Exceptions; 20 import com.android.dx.rop.code.FillArrayDataInsn; 21 import com.android.dx.rop.code.Insn; 22 import com.android.dx.rop.code.PlainCstInsn; 23 import com.android.dx.rop.code.PlainInsn; 24 import com.android.dx.rop.code.RegOps; 25 import com.android.dx.rop.code.RegisterSpec; 26 import com.android.dx.rop.code.RegisterSpecList; 27 import com.android.dx.rop.code.Rop; 28 import com.android.dx.rop.code.Rops; 29 import com.android.dx.rop.code.ThrowingCstInsn; 30 import com.android.dx.rop.code.ThrowingInsn; 31 import com.android.dx.rop.cst.Constant; 32 import com.android.dx.rop.cst.CstLiteralBits; 33 import com.android.dx.rop.cst.CstMethodRef; 34 import com.android.dx.rop.cst.CstNat; 35 import com.android.dx.rop.cst.CstString; 36 import com.android.dx.rop.cst.CstType; 37 import com.android.dx.rop.cst.TypedConstant; 38 import com.android.dx.rop.cst.Zeroes; 39 import com.android.dx.rop.type.StdTypeList; 40 import com.android.dx.rop.type.Type; 41 import com.android.dx.rop.type.TypeBearer; 42 import java.util.ArrayList; 43 import java.util.BitSet; 44 import java.util.HashSet; 45 import java.util.List; 46 47 /** 48 * Simple intraprocedural escape analysis. Finds new arrays that don't escape 49 * the method they are created in and replaces the array values with registers. 50 */ 51 public class EscapeAnalysis { 52 /** 53 * Struct used to generate and maintain escape analysis results. 54 */ 55 static class EscapeSet { 56 /** set containing all registers related to an object */ 57 BitSet regSet; 58 /** escape state of the object */ 59 EscapeState escape; 60 /** list of objects that are put into this object */ 61 ArrayList<EscapeSet> childSets; 62 /** list of objects that this object is put into */ 63 ArrayList<EscapeSet> parentSets; 64 /** flag to indicate this object is a scalar replaceable array */ 65 boolean replaceableArray; 66 67 /** 68 * Constructs an instance of an EscapeSet 69 * 70 * @param reg the SSA register that defines the object 71 * @param size the number of registers in the method 72 * @param escState the lattice value to initially set this to 73 */ 74 EscapeSet(int reg, int size, EscapeState escState) { 75 regSet = new BitSet(size); 76 regSet.set(reg); 77 escape = escState; 78 childSets = new ArrayList<EscapeSet>(); 79 parentSets = new ArrayList<EscapeSet>(); 80 replaceableArray = false; 81 } 82 } 83 84 /** 85 * Lattice values used to indicate escape state for an object. Analysis can 86 * only raise escape state values, not lower them. 87 * 88 * TOP - Used for objects that haven't been analyzed yet 89 * NONE - Object does not escape, and is eligible for scalar replacement. 90 * METHOD - Object remains local to method, but can't be scalar replaced. 91 * INTER - Object is passed between methods. (treated as globally escaping 92 * since this is an intraprocedural analysis) 93 * GLOBAL - Object escapes globally. 94 */ 95 public enum EscapeState { 96 TOP, NONE, METHOD, INTER, GLOBAL 97 } 98 99 /** method we're processing */ 100 private final SsaMethod ssaMeth; 101 /** ssaMeth.getRegCount() */ 102 private final int regCount; 103 /** Lattice values for each object register group */ 104 private final ArrayList<EscapeSet> latticeValues; 105 106 /** 107 * Constructs an instance. 108 * 109 * @param ssaMeth method to process 110 */ 111 private EscapeAnalysis(SsaMethod ssaMeth) { 112 this.ssaMeth = ssaMeth; 113 this.regCount = ssaMeth.getRegCount(); 114 this.latticeValues = new ArrayList<EscapeSet>(); 115 } 116 117 /** 118 * Finds the index in the lattice for a particular register. 119 * Returns the size of the lattice if the register wasn't found. 120 * 121 * @param reg {@code non-null;} register being looked up 122 * @return index of the register or size of the lattice if it wasn't found. 123 */ 124 private int findSetIndex(RegisterSpec reg) { 125 int i; 126 for (i = 0; i < latticeValues.size(); i++) { 127 EscapeSet e = latticeValues.get(i); 128 if (e.regSet.get(reg.getReg())) { 129 return i; 130 } 131 } 132 return i; 133 } 134 135 /** 136 * Finds the corresponding instruction for a given move result 137 * 138 * @param moveInsn {@code non-null;} a move result instruction 139 * @return {@code non-null;} the instruction that produces the result for 140 * the move 141 */ 142 private SsaInsn getInsnForMove(SsaInsn moveInsn) { 143 int pred = moveInsn.getBlock().getPredecessors().nextSetBit(0); 144 ArrayList<SsaInsn> predInsns = ssaMeth.getBlocks().get(pred).getInsns(); 145 return predInsns.get(predInsns.size()-1); 146 } 147 148 /** 149 * Finds the corresponding move result for a given instruction 150 * 151 * @param insn {@code non-null;} an instruction that must always be 152 * followed by a move result 153 * @return {@code non-null;} the move result for the given instruction 154 */ 155 private SsaInsn getMoveForInsn(SsaInsn insn) { 156 int succ = insn.getBlock().getSuccessors().nextSetBit(0); 157 ArrayList<SsaInsn> succInsns = ssaMeth.getBlocks().get(succ).getInsns(); 158 return succInsns.get(0); 159 } 160 161 /** 162 * Creates a link in the lattice between two EscapeSets due to a put 163 * instruction. The object being put is the child and the object being put 164 * into is the parent. A child set must always have an escape state at 165 * least as high as its parent. 166 * 167 * @param parentSet {@code non-null;} the EscapeSet for the object being put 168 * into 169 * @param childSet {@code non-null;} the EscapeSet for the object being put 170 */ 171 private void addEdge(EscapeSet parentSet, EscapeSet childSet) { 172 if (!childSet.parentSets.contains(parentSet)) { 173 childSet.parentSets.add(parentSet); 174 } 175 if (!parentSet.childSets.contains(childSet)) { 176 parentSet.childSets.add(childSet); 177 } 178 } 179 180 /** 181 * Merges all links in the lattice among two EscapeSets. On return, the 182 * newNode will have its old links as well as all links from the oldNode. 183 * The oldNode has all its links removed. 184 * 185 * @param newNode {@code non-null;} the EscapeSet to merge all links into 186 * @param oldNode {@code non-null;} the EscapeSet to remove all links from 187 */ 188 private void replaceNode(EscapeSet newNode, EscapeSet oldNode) { 189 for (EscapeSet e : oldNode.parentSets) { 190 e.childSets.remove(oldNode); 191 e.childSets.add(newNode); 192 newNode.parentSets.add(e); 193 } 194 for (EscapeSet e : oldNode.childSets) { 195 e.parentSets.remove(oldNode); 196 e.parentSets.add(newNode); 197 newNode.childSets.add(e); 198 } 199 } 200 201 /** 202 * Performs escape analysis on a method. Finds scalar replaceable arrays and 203 * replaces them with equivalent registers. 204 * 205 * @param ssaMethod {@code non-null;} method to process 206 */ 207 public static void process(SsaMethod ssaMethod) { 208 new EscapeAnalysis(ssaMethod).run(); 209 } 210 211 /** 212 * Process a single instruction, looking for new objects resulting from 213 * move result or move param. 214 * 215 * @param insn {@code non-null;} instruction to process 216 */ 217 private void processInsn(SsaInsn insn) { 218 int op = insn.getOpcode().getOpcode(); 219 RegisterSpec result = insn.getResult(); 220 EscapeSet escSet; 221 222 // Identify new objects 223 if (op == RegOps.MOVE_RESULT_PSEUDO && 224 result.getTypeBearer().getBasicType() == Type.BT_OBJECT) { 225 // Handle objects generated through move_result_pseudo 226 escSet = processMoveResultPseudoInsn(insn); 227 processRegister(result, escSet); 228 } else if (op == RegOps.MOVE_PARAM && 229 result.getTypeBearer().getBasicType() == Type.BT_OBJECT) { 230 // Track method arguments that are objects 231 escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE); 232 latticeValues.add(escSet); 233 processRegister(result, escSet); 234 } else if (op == RegOps.MOVE_RESULT && 235 result.getTypeBearer().getBasicType() == Type.BT_OBJECT) { 236 // Track method return values that are objects 237 escSet = new EscapeSet(result.getReg(), regCount, EscapeState.NONE); 238 latticeValues.add(escSet); 239 processRegister(result, escSet); 240 } 241 } 242 243 /** 244 * Determine the origin of a move result pseudo instruction that generates 245 * an object. Creates a new EscapeSet for the new object accordingly. 246 * 247 * @param insn {@code non-null;} move result pseudo instruction to process 248 * @return {@code non-null;} an EscapeSet for the object referred to by the 249 * move result pseudo instruction 250 */ 251 private EscapeSet processMoveResultPseudoInsn(SsaInsn insn) { 252 RegisterSpec result = insn.getResult(); 253 SsaInsn prevSsaInsn = getInsnForMove(insn); 254 int prevOpcode = prevSsaInsn.getOpcode().getOpcode(); 255 EscapeSet escSet; 256 RegisterSpec prevSource; 257 258 switch(prevOpcode) { 259 // New instance / Constant 260 case RegOps.NEW_INSTANCE: 261 case RegOps.CONST: 262 escSet = new EscapeSet(result.getReg(), regCount, 263 EscapeState.NONE); 264 break; 265 // New array 266 case RegOps.NEW_ARRAY: 267 case RegOps.FILLED_NEW_ARRAY: 268 prevSource = prevSsaInsn.getSources().get(0); 269 if (prevSource.getTypeBearer().isConstant()) { 270 // New fixed array 271 escSet = new EscapeSet(result.getReg(), regCount, 272 EscapeState.NONE); 273 escSet.replaceableArray = true; 274 } else { 275 // New variable array 276 escSet = new EscapeSet(result.getReg(), regCount, 277 EscapeState.GLOBAL); 278 } 279 break; 280 // Loading a static object 281 case RegOps.GET_STATIC: 282 escSet = new EscapeSet(result.getReg(), regCount, 283 EscapeState.GLOBAL); 284 break; 285 // Type cast / load an object from a field or array 286 case RegOps.CHECK_CAST: 287 case RegOps.GET_FIELD: 288 case RegOps.AGET: 289 prevSource = prevSsaInsn.getSources().get(0); 290 int setIndex = findSetIndex(prevSource); 291 292 // Set should already exist, try to find it 293 if (setIndex != latticeValues.size()) { 294 escSet = latticeValues.get(setIndex); 295 escSet.regSet.set(result.getReg()); 296 return escSet; 297 } 298 299 // Set not found, must be either null or unknown 300 if (prevSource.getType() == Type.KNOWN_NULL) { 301 escSet = new EscapeSet(result.getReg(), regCount, 302 EscapeState.NONE); 303 } else { 304 escSet = new EscapeSet(result.getReg(), regCount, 305 EscapeState.GLOBAL); 306 } 307 break; 308 default: 309 return null; 310 } 311 312 // Add the newly created escSet to the lattice and return it 313 latticeValues.add(escSet); 314 return escSet; 315 } 316 317 /** 318 * Iterate through all the uses of a new object. 319 * 320 * @param result {@code non-null;} register where new object is stored 321 * @param escSet {@code non-null;} EscapeSet for the new object 322 */ 323 private void processRegister(RegisterSpec result, EscapeSet escSet) { 324 ArrayList<RegisterSpec> regWorklist = new ArrayList<RegisterSpec>(); 325 regWorklist.add(result); 326 327 // Go through the worklist 328 while (!regWorklist.isEmpty()) { 329 int listSize = regWorklist.size() - 1; 330 RegisterSpec def = regWorklist.remove(listSize); 331 List<SsaInsn> useList = ssaMeth.getUseListForRegister(def.getReg()); 332 333 // Handle all the uses of this register 334 for (SsaInsn use : useList) { 335 Rop useOpcode = use.getOpcode(); 336 337 if (useOpcode == null) { 338 // Handle phis 339 processPhiUse(use, escSet, regWorklist); 340 } else { 341 // Handle other opcodes 342 processUse(def, use, escSet, regWorklist); 343 } 344 } 345 } 346 } 347 348 /** 349 * Handles phi uses of new objects. Will merge together the sources of a phi 350 * into a single EscapeSet. Adds the result of the phi to the worklist so 351 * its uses can be followed. 352 * 353 * @param use {@code non-null;} phi use being processed 354 * @param escSet {@code non-null;} EscapeSet for the object 355 * @param regWorklist {@code non-null;} worklist of instructions left to 356 * process for this object 357 */ 358 private void processPhiUse(SsaInsn use, EscapeSet escSet, 359 ArrayList<RegisterSpec> regWorklist) { 360 int setIndex = findSetIndex(use.getResult()); 361 if (setIndex != latticeValues.size()) { 362 // Check if result is in a set already 363 EscapeSet mergeSet = latticeValues.get(setIndex); 364 if (mergeSet != escSet) { 365 // If it is, merge the sets and states, then delete the copy 366 escSet.replaceableArray = false; 367 escSet.regSet.or(mergeSet.regSet); 368 if (escSet.escape.compareTo(mergeSet.escape) < 0) { 369 escSet.escape = mergeSet.escape; 370 } 371 replaceNode(escSet, mergeSet); 372 latticeValues.remove(setIndex); 373 } 374 } else { 375 // If no set is found, add it to this escSet and the worklist 376 escSet.regSet.set(use.getResult().getReg()); 377 regWorklist.add(use.getResult()); 378 } 379 } 380 381 /** 382 * Handles non-phi uses of new objects. Checks to see how instruction is 383 * used and updates the escape state accordingly. 384 * 385 * @param def {@code non-null;} register holding definition of new object 386 * @param use {@code non-null;} use of object being processed 387 * @param escSet {@code non-null;} EscapeSet for the object 388 * @param regWorklist {@code non-null;} worklist of instructions left to 389 * process for this object 390 */ 391 private void processUse(RegisterSpec def, SsaInsn use, EscapeSet escSet, 392 ArrayList<RegisterSpec> regWorklist) { 393 int useOpcode = use.getOpcode().getOpcode(); 394 switch (useOpcode) { 395 case RegOps.MOVE: 396 // Follow uses of the move by adding it to the worklist 397 escSet.regSet.set(use.getResult().getReg()); 398 regWorklist.add(use.getResult()); 399 break; 400 case RegOps.IF_EQ: 401 case RegOps.IF_NE: 402 case RegOps.CHECK_CAST: 403 // Compared objects can't be replaced, so promote if necessary 404 if (escSet.escape.compareTo(EscapeState.METHOD) < 0) { 405 escSet.escape = EscapeState.METHOD; 406 } 407 break; 408 case RegOps.APUT: 409 // For array puts, check for a constant array index 410 RegisterSpec putIndex = use.getSources().get(2); 411 if (!putIndex.getTypeBearer().isConstant()) { 412 // If not constant, array can't be replaced 413 escSet.replaceableArray = false; 414 } 415 // Intentional fallthrough 416 case RegOps.PUT_FIELD: 417 // Skip non-object puts 418 RegisterSpec putValue = use.getSources().get(0); 419 if (putValue.getTypeBearer().getBasicType() != Type.BT_OBJECT) { 420 break; 421 } 422 escSet.replaceableArray = false; 423 424 // Raise 1st object's escape state to 2nd if 2nd is higher 425 RegisterSpecList sources = use.getSources(); 426 if (sources.get(0).getReg() == def.getReg()) { 427 int setIndex = findSetIndex(sources.get(1)); 428 if (setIndex != latticeValues.size()) { 429 EscapeSet parentSet = latticeValues.get(setIndex); 430 addEdge(parentSet, escSet); 431 if (escSet.escape.compareTo(parentSet.escape) < 0) { 432 escSet.escape = parentSet.escape; 433 } 434 } 435 } else { 436 int setIndex = findSetIndex(sources.get(0)); 437 if (setIndex != latticeValues.size()) { 438 EscapeSet childSet = latticeValues.get(setIndex); 439 addEdge(escSet, childSet); 440 if (childSet.escape.compareTo(escSet.escape) < 0) { 441 childSet.escape = escSet.escape; 442 } 443 } 444 } 445 break; 446 case RegOps.AGET: 447 // For array gets, check for a constant array index 448 RegisterSpec getIndex = use.getSources().get(1); 449 if (!getIndex.getTypeBearer().isConstant()) { 450 // If not constant, array can't be replaced 451 escSet.replaceableArray = false; 452 } 453 break; 454 case RegOps.PUT_STATIC: 455 // Static puts cause an object to escape globally 456 escSet.escape = EscapeState.GLOBAL; 457 break; 458 case RegOps.INVOKE_STATIC: 459 case RegOps.INVOKE_VIRTUAL: 460 case RegOps.INVOKE_SUPER: 461 case RegOps.INVOKE_DIRECT: 462 case RegOps.INVOKE_INTERFACE: 463 case RegOps.RETURN: 464 case RegOps.THROW: 465 // These operations cause an object to escape interprocedurally 466 escSet.escape = EscapeState.INTER; 467 break; 468 default: 469 break; 470 } 471 } 472 473 /** 474 * Performs scalar replacement on all eligible arrays. 475 */ 476 private void scalarReplacement() { 477 // Iterate through lattice, looking for non-escaping replaceable arrays 478 for (EscapeSet escSet : latticeValues) { 479 if (!escSet.replaceableArray || escSet.escape != EscapeState.NONE) { 480 continue; 481 } 482 483 // Get the instructions for the definition and move of the array 484 int e = escSet.regSet.nextSetBit(0); 485 SsaInsn def = ssaMeth.getDefinitionForRegister(e); 486 SsaInsn prev = getInsnForMove(def); 487 488 // Create a map for the new registers that will be created 489 TypeBearer lengthReg = prev.getSources().get(0).getTypeBearer(); 490 int length = ((CstLiteralBits) lengthReg).getIntBits(); 491 ArrayList<RegisterSpec> newRegs = 492 new ArrayList<RegisterSpec>(length); 493 HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>(); 494 495 // Replace the definition of the array with registers 496 replaceDef(def, prev, length, newRegs); 497 498 // Mark definition instructions for deletion 499 deletedInsns.add(prev); 500 deletedInsns.add(def); 501 502 // Go through all uses of the array 503 List<SsaInsn> useList = ssaMeth.getUseListForRegister(e); 504 for (SsaInsn use : useList) { 505 // Replace the use with scalars and then mark it for deletion 506 replaceUse(use, prev, newRegs, deletedInsns); 507 deletedInsns.add(use); 508 } 509 510 // Delete all marked instructions 511 ssaMeth.deleteInsns(deletedInsns); 512 ssaMeth.onInsnsChanged(); 513 514 // Convert the method back to SSA form 515 SsaConverter.updateSsaMethod(ssaMeth, regCount); 516 517 // Propagate and remove extra moves added by scalar replacement 518 movePropagate(); 519 } 520 } 521 522 /** 523 * Replaces the instructions that define an array with equivalent registers. 524 * For each entry in the array, a register is created, initialized to zero. 525 * A mapping between this register and the corresponding array index is 526 * added. 527 * 528 * @param def {@code non-null;} move result instruction for array 529 * @param prev {@code non-null;} instruction for instantiating new array 530 * @param length size of the new array 531 * @param newRegs {@code non-null;} mapping of array indices to new 532 * registers to be populated 533 */ 534 private void replaceDef(SsaInsn def, SsaInsn prev, int length, 535 ArrayList<RegisterSpec> newRegs) { 536 Type resultType = def.getResult().getType(); 537 538 // Create new zeroed out registers for each element in the array 539 for (int i = 0; i < length; i++) { 540 Constant newZero = Zeroes.zeroFor(resultType.getComponentType()); 541 TypedConstant typedZero = (TypedConstant) newZero; 542 RegisterSpec newReg = 543 RegisterSpec.make(ssaMeth.makeNewSsaReg(), typedZero); 544 newRegs.add(newReg); 545 insertPlainInsnBefore(def, RegisterSpecList.EMPTY, newReg, 546 RegOps.CONST, newZero); 547 } 548 } 549 550 /** 551 * Replaces the use for a scalar replaceable array. Gets and puts become 552 * move instructions, and array lengths and fills are handled. Can also 553 * identify ArrayIndexOutOfBounds exceptions and throw them if detected. 554 * 555 * @param use {@code non-null;} move result instruction for array 556 * @param prev {@code non-null;} instruction for instantiating new array 557 * @param newRegs {@code non-null;} mapping of array indices to new 558 * registers 559 * @param deletedInsns {@code non-null;} set of instructions marked for 560 * deletion 561 */ 562 private void replaceUse(SsaInsn use, SsaInsn prev, 563 ArrayList<RegisterSpec> newRegs, 564 HashSet<SsaInsn> deletedInsns) { 565 int index; 566 int length = newRegs.size(); 567 SsaInsn next; 568 RegisterSpecList sources; 569 RegisterSpec source, result; 570 CstLiteralBits indexReg; 571 572 switch (use.getOpcode().getOpcode()) { 573 case RegOps.AGET: 574 // Replace array gets with moves 575 next = getMoveForInsn(use); 576 sources = use.getSources(); 577 indexReg = ((CstLiteralBits) sources.get(1).getTypeBearer()); 578 index = indexReg.getIntBits(); 579 if (index < length) { 580 source = newRegs.get(index); 581 result = source.withReg(next.getResult().getReg()); 582 insertPlainInsnBefore(next, RegisterSpecList.make(source), 583 result, RegOps.MOVE, null); 584 } else { 585 // Throw an exception if the index is out of bounds 586 insertExceptionThrow(next, sources.get(1), deletedInsns); 587 deletedInsns.add(next.getBlock().getInsns().get(2)); 588 } 589 deletedInsns.add(next); 590 break; 591 case RegOps.APUT: 592 // Replace array puts with moves 593 sources = use.getSources(); 594 indexReg = ((CstLiteralBits) sources.get(2).getTypeBearer()); 595 index = indexReg.getIntBits(); 596 if (index < length) { 597 source = sources.get(0); 598 result = source.withReg(newRegs.get(index).getReg()); 599 insertPlainInsnBefore(use, RegisterSpecList.make(source), 600 result, RegOps.MOVE, null); 601 // Update the newReg entry to mark value as unknown now 602 newRegs.set(index, result.withSimpleType()); 603 } else { 604 // Throw an exception if the index is out of bounds 605 insertExceptionThrow(use, sources.get(2), deletedInsns); 606 } 607 break; 608 case RegOps.ARRAY_LENGTH: 609 // Replace array lengths with const instructions 610 TypeBearer lengthReg = prev.getSources().get(0).getTypeBearer(); 611 //CstInteger lengthReg = CstInteger.make(length); 612 next = getMoveForInsn(use); 613 insertPlainInsnBefore(next, RegisterSpecList.EMPTY, 614 next.getResult(), RegOps.CONST, 615 (Constant) lengthReg); 616 deletedInsns.add(next); 617 break; 618 case RegOps.MARK_LOCAL: 619 // Remove mark local instructions 620 break; 621 case RegOps.FILL_ARRAY_DATA: 622 // Create const instructions for each fill value 623 Insn ropUse = use.getOriginalRopInsn(); 624 FillArrayDataInsn fill = (FillArrayDataInsn) ropUse; 625 ArrayList<Constant> constList = fill.getInitValues(); 626 for (int i = 0; i < length; i++) { 627 RegisterSpec newFill = 628 RegisterSpec.make(newRegs.get(i).getReg(), 629 (TypeBearer) constList.get(i)); 630 insertPlainInsnBefore(use, RegisterSpecList.EMPTY, newFill, 631 RegOps.CONST, constList.get(i)); 632 // Update the newRegs to hold the new const value 633 newRegs.set(i, newFill); 634 } 635 break; 636 default: 637 } 638 } 639 640 /** 641 * Identifies extra moves added by scalar replacement and propagates the 642 * source of the move to any users of the result. 643 */ 644 private void movePropagate() { 645 for (int i = 0; i < ssaMeth.getRegCount(); i++) { 646 SsaInsn insn = ssaMeth.getDefinitionForRegister(i); 647 648 // Look for move instructions only 649 if (insn == null || insn.getOpcode() == null || 650 insn.getOpcode().getOpcode() != RegOps.MOVE) { 651 continue; 652 } 653 654 final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy(); 655 final RegisterSpec source = insn.getSources().get(0); 656 final RegisterSpec result = insn.getResult(); 657 658 // Ignore moves that weren't added due to scalar replacement 659 if (source.getReg() < regCount && result.getReg() < regCount) { 660 continue; 661 } 662 663 // Create a mapping from source to result 664 RegisterMapper mapper = new RegisterMapper() { 665 @Override 666 public int getNewRegisterCount() { 667 return ssaMeth.getRegCount(); 668 } 669 670 @Override 671 public RegisterSpec map(RegisterSpec registerSpec) { 672 if (registerSpec.getReg() == result.getReg()) { 673 return source; 674 } 675 676 return registerSpec; 677 } 678 }; 679 680 // Modify all uses of the move to use the source of the move instead 681 for (SsaInsn use : useList[result.getReg()]) { 682 use.mapSourceRegisters(mapper); 683 } 684 } 685 } 686 687 /** 688 * Runs escape analysis and scalar replacement of arrays. 689 */ 690 private void run() { 691 ssaMeth.forEachBlockDepthFirstDom(new SsaBasicBlock.Visitor() { 692 @Override 693 public void visitBlock (SsaBasicBlock block, 694 SsaBasicBlock unused) { 695 block.forEachInsn(new SsaInsn.Visitor() { 696 @Override 697 public void visitMoveInsn(NormalSsaInsn insn) { 698 // do nothing 699 } 700 701 @Override 702 public void visitPhiInsn(PhiInsn insn) { 703 // do nothing 704 } 705 706 @Override 707 public void visitNonMoveInsn(NormalSsaInsn insn) { 708 processInsn(insn); 709 } 710 }); 711 } 712 }); 713 714 // Go through lattice and promote fieldSets as necessary 715 for (EscapeSet e : latticeValues) { 716 if (e.escape != EscapeState.NONE) { 717 for (EscapeSet field : e.childSets) { 718 if (e.escape.compareTo(field.escape) > 0) { 719 field.escape = e.escape; 720 } 721 } 722 } 723 } 724 725 // Perform scalar replacement for arrays 726 scalarReplacement(); 727 } 728 729 /** 730 * Replaces instructions that trigger an ArrayIndexOutofBounds exception 731 * with an actual throw of the exception. 732 * 733 * @param insn {@code non-null;} instruction causing the exception 734 * @param index {@code non-null;} index value that is out of bounds 735 * @param deletedInsns {@code non-null;} set of instructions marked for 736 * deletion 737 */ 738 private void insertExceptionThrow(SsaInsn insn, RegisterSpec index, 739 HashSet<SsaInsn> deletedInsns) { 740 // Create a new ArrayIndexOutOfBoundsException 741 CstType exception = 742 new CstType(Exceptions.TYPE_ArrayIndexOutOfBoundsException); 743 insertThrowingInsnBefore(insn, RegisterSpecList.EMPTY, null, 744 RegOps.NEW_INSTANCE, exception); 745 746 // Add a successor block with a move result pseudo for the exception 747 SsaBasicBlock currBlock = insn.getBlock(); 748 SsaBasicBlock newBlock = 749 currBlock.insertNewSuccessor(currBlock.getPrimarySuccessor()); 750 SsaInsn newInsn = newBlock.getInsns().get(0); 751 RegisterSpec newReg = 752 RegisterSpec.make(ssaMeth.makeNewSsaReg(), exception); 753 insertPlainInsnBefore(newInsn, RegisterSpecList.EMPTY, newReg, 754 RegOps.MOVE_RESULT_PSEUDO, null); 755 756 // Add another successor block to initialize the exception 757 SsaBasicBlock newBlock2 = 758 newBlock.insertNewSuccessor(newBlock.getPrimarySuccessor()); 759 SsaInsn newInsn2 = newBlock2.getInsns().get(0); 760 CstNat newNat = new CstNat(new CstString("<init>"), new CstString("(I)V")); 761 CstMethodRef newRef = new CstMethodRef(exception, newNat); 762 insertThrowingInsnBefore(newInsn2, RegisterSpecList.make(newReg, index), 763 null, RegOps.INVOKE_DIRECT, newRef); 764 deletedInsns.add(newInsn2); 765 766 // Add another successor block to throw the new exception 767 SsaBasicBlock newBlock3 = 768 newBlock2.insertNewSuccessor(newBlock2.getPrimarySuccessor()); 769 SsaInsn newInsn3 = newBlock3.getInsns().get(0); 770 insertThrowingInsnBefore(newInsn3, RegisterSpecList.make(newReg), null, 771 RegOps.THROW, null); 772 newBlock3.replaceSuccessor(newBlock3.getPrimarySuccessorIndex(), 773 ssaMeth.getExitBlock().getIndex()); 774 deletedInsns.add(newInsn3); 775 } 776 777 /** 778 * Inserts a new PlainInsn before the given instruction. 779 * TODO: move this somewhere more appropriate 780 * 781 * @param insn {@code non-null;} instruction to insert before 782 * @param newSources {@code non-null;} sources of new instruction 783 * @param newResult {@code non-null;} result of new instruction 784 * @param newOpcode opcode of new instruction 785 * @param cst {@code null-ok;} constant for new instruction, if any 786 */ 787 private void insertPlainInsnBefore(SsaInsn insn, 788 RegisterSpecList newSources, RegisterSpec newResult, int newOpcode, 789 Constant cst) { 790 791 Insn originalRopInsn = insn.getOriginalRopInsn(); 792 Rop newRop; 793 if (newOpcode == RegOps.MOVE_RESULT_PSEUDO) { 794 newRop = Rops.opMoveResultPseudo(newResult.getType()); 795 } else { 796 newRop = Rops.ropFor(newOpcode, newResult, newSources, cst); 797 } 798 799 Insn newRopInsn; 800 if (cst == null) { 801 newRopInsn = new PlainInsn(newRop, 802 originalRopInsn.getPosition(), newResult, newSources); 803 } else { 804 newRopInsn = new PlainCstInsn(newRop, 805 originalRopInsn.getPosition(), newResult, newSources, cst); 806 } 807 808 NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock()); 809 List<SsaInsn> insns = insn.getBlock().getInsns(); 810 811 insns.add(insns.lastIndexOf(insn), newInsn); 812 ssaMeth.onInsnAdded(newInsn); 813 } 814 815 /** 816 * Inserts a new ThrowingInsn before the given instruction. 817 * TODO: move this somewhere more appropriate 818 * 819 * @param insn {@code non-null;} instruction to insert before 820 * @param newSources {@code non-null;} sources of new instruction 821 * @param newResult {@code non-null;} result of new instruction 822 * @param newOpcode opcode of new instruction 823 * @param cst {@code null-ok;} constant for new instruction, if any 824 */ 825 private void insertThrowingInsnBefore(SsaInsn insn, 826 RegisterSpecList newSources, RegisterSpec newResult, int newOpcode, 827 Constant cst) { 828 829 Insn origRopInsn = insn.getOriginalRopInsn(); 830 Rop newRop = Rops.ropFor(newOpcode, newResult, newSources, cst); 831 Insn newRopInsn; 832 if (cst == null) { 833 newRopInsn = new ThrowingInsn(newRop, 834 origRopInsn.getPosition(), newSources, StdTypeList.EMPTY); 835 } else { 836 newRopInsn = new ThrowingCstInsn(newRop, 837 origRopInsn.getPosition(), newSources, StdTypeList.EMPTY, cst); 838 } 839 840 NormalSsaInsn newInsn = new NormalSsaInsn(newRopInsn, insn.getBlock()); 841 List<SsaInsn> insns = insn.getBlock().getInsns(); 842 843 insns.add(insns.lastIndexOf(insn), newInsn); 844 ssaMeth.onInsnAdded(newInsn); 845 } 846 } 847
