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