1 /* 2 * Copyright (C) 2007 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.BasicBlockList; 20 import com.android.dx.rop.code.Insn; 21 import com.android.dx.rop.code.PlainInsn; 22 import com.android.dx.rop.code.RegOps; 23 import com.android.dx.rop.code.RegisterSpec; 24 import com.android.dx.rop.code.RegisterSpecList; 25 import com.android.dx.rop.code.Rop; 26 import com.android.dx.rop.code.RopMethod; 27 import com.android.dx.rop.code.Rops; 28 import com.android.dx.rop.code.SourcePosition; 29 import com.android.dx.util.IntList; 30 31 import java.util.ArrayList; 32 import java.util.BitSet; 33 import java.util.Collections; 34 import java.util.List; 35 import java.util.Set; 36 import java.util.Stack; 37 38 /** 39 * A method in SSA form. 40 */ 41 public final class SsaMethod { 42 /** basic blocks, indexed by block index */ 43 private ArrayList<SsaBasicBlock> blocks; 44 45 /** Index of first executed block in method */ 46 private int entryBlockIndex; 47 48 /** 49 * Index of exit block, which exists only in SSA form, 50 * or or {@code -1} if there is none 51 */ 52 private int exitBlockIndex; 53 54 /** total number of registers required */ 55 private int registerCount; 56 57 /** first register number to use for any temporary "spares" */ 58 private int spareRegisterBase; 59 60 /** current count of spare registers used */ 61 private int borrowedSpareRegisters; 62 63 /** really one greater than the max label */ 64 private int maxLabel; 65 66 /** the total width, in register-units, of the method's parameters */ 67 private final int paramWidth; 68 69 /** true if this method has no {@code this} pointer argument */ 70 private final boolean isStatic; 71 72 /** 73 * indexed by register: the insn where said register is defined or null 74 * if undefined. null until (lazily) created. 75 */ 76 private SsaInsn[] definitionList; 77 78 /** indexed by register: the list of all insns that use a register */ 79 private ArrayList<SsaInsn>[] useList; 80 81 /** A version of useList with each List unmodifiable */ 82 private List<SsaInsn>[] unmodifiableUseList; 83 84 /** 85 * "back-convert mode". Set during back-conversion when registers 86 * are about to be mapped into a non-SSA namespace. When true, 87 * use and def lists are unavailable. 88 * 89 * TODO: Remove this mode, and place the functionality elsewhere 90 */ 91 private boolean backMode; 92 93 /** 94 * @param ropMethod rop-form method to convert from 95 * @param paramWidth the total width, in register-units, of the 96 * method's parameters 97 * @param isStatic {@code true} if this method has no {@code this} 98 * pointer argument 99 */ newFromRopMethod(RopMethod ropMethod, int paramWidth, boolean isStatic)100 public static SsaMethod newFromRopMethod(RopMethod ropMethod, 101 int paramWidth, boolean isStatic) { 102 SsaMethod result = new SsaMethod(ropMethod, paramWidth, isStatic); 103 104 result.convertRopToSsaBlocks(ropMethod); 105 106 return result; 107 } 108 109 /** 110 * Constructs an instance. 111 * 112 * @param ropMethod {@code non-null;} the original rop-form method that 113 * this instance is based on 114 * @param paramWidth the total width, in register-units, of the 115 * method's parameters 116 * @param isStatic {@code true} if this method has no {@code this} 117 * pointer argument 118 */ SsaMethod(RopMethod ropMethod, int paramWidth, boolean isStatic)119 private SsaMethod(RopMethod ropMethod, int paramWidth, boolean isStatic) { 120 this.paramWidth = paramWidth; 121 this.isStatic = isStatic; 122 this.backMode = false; 123 this.maxLabel = ropMethod.getBlocks().getMaxLabel(); 124 this.registerCount = ropMethod.getBlocks().getRegCount(); 125 this.spareRegisterBase = registerCount; 126 } 127 128 /** 129 * Builds a BitSet of block indices from a basic block list and a list 130 * of labels taken from Rop form. 131 * 132 * @param blocks Rop blocks 133 * @param labelList list of rop block labels 134 * @return BitSet of block indices 135 */ bitSetFromLabelList(BasicBlockList blocks, IntList labelList)136 static BitSet bitSetFromLabelList(BasicBlockList blocks, 137 IntList labelList) { 138 BitSet result = new BitSet(blocks.size()); 139 140 for (int i = 0, sz = labelList.size(); i < sz; i++) { 141 result.set(blocks.indexOfLabel(labelList.get(i))); 142 } 143 144 return result; 145 } 146 147 /** 148 * Builds an IntList of block indices from a basic block list and a list 149 * of labels taken from Rop form. 150 * 151 * @param ropBlocks Rop blocks 152 * @param labelList list of rop block labels 153 * @return IntList of block indices 154 */ indexListFromLabelList(BasicBlockList ropBlocks, IntList labelList)155 public static IntList indexListFromLabelList(BasicBlockList ropBlocks, 156 IntList labelList) { 157 158 IntList result = new IntList(labelList.size()); 159 160 for (int i = 0, sz = labelList.size(); i < sz; i++) { 161 result.add(ropBlocks.indexOfLabel(labelList.get(i))); 162 } 163 164 return result; 165 } 166 convertRopToSsaBlocks(RopMethod rmeth)167 private void convertRopToSsaBlocks(RopMethod rmeth) { 168 BasicBlockList ropBlocks = rmeth.getBlocks(); 169 int sz = ropBlocks.size(); 170 171 blocks = new ArrayList<SsaBasicBlock>(sz + 2); 172 173 for (int i = 0; i < sz; i++) { 174 SsaBasicBlock sbb = SsaBasicBlock.newFromRop(rmeth, i, this); 175 blocks.add(sbb); 176 } 177 178 // Add an no-op entry block. 179 int origEntryBlockIndex = rmeth.getBlocks() 180 .indexOfLabel(rmeth.getFirstLabel()); 181 182 SsaBasicBlock entryBlock 183 = blocks.get(origEntryBlockIndex).insertNewPredecessor(); 184 185 entryBlockIndex = entryBlock.getIndex(); 186 exitBlockIndex = -1; // This gets made later. 187 } 188 189 /** 190 * Creates an exit block and attaches it to the CFG if this method 191 * exits. Methods that never exit will not have an exit block. This 192 * is called after edge-splitting and phi insertion, since the edges 193 * going into the exit block should not be considered in those steps. 194 */ makeExitBlock()195 /*package*/ void makeExitBlock() { 196 if (exitBlockIndex >= 0) { 197 throw new RuntimeException("must be called at most once"); 198 } 199 200 exitBlockIndex = blocks.size(); 201 SsaBasicBlock exitBlock 202 = new SsaBasicBlock(exitBlockIndex, maxLabel++, this); 203 204 blocks.add(exitBlock); 205 206 for (SsaBasicBlock block : blocks) { 207 block.exitBlockFixup(exitBlock); 208 } 209 210 if (exitBlock.getPredecessors().cardinality() == 0) { 211 // In cases where there is no exit... 212 blocks.remove(exitBlockIndex); 213 exitBlockIndex = -1; 214 maxLabel--; 215 } 216 } 217 218 /** 219 * Gets a new {@code GOTO} insn. 220 * 221 * @param block block to which this GOTO will be added 222 * (not it's destination!) 223 * @return an appropriately-constructed instance. 224 */ getGoto(SsaBasicBlock block)225 private static SsaInsn getGoto(SsaBasicBlock block) { 226 return new NormalSsaInsn ( 227 new PlainInsn(Rops.GOTO, SourcePosition.NO_INFO, 228 null, RegisterSpecList.EMPTY), block); 229 } 230 231 /** 232 * Makes a new basic block for this method, which is empty besides 233 * a single {@code GOTO}. Successors and predecessors are not yet 234 * set. 235 * 236 * @return new block 237 */ makeNewGotoBlock()238 public SsaBasicBlock makeNewGotoBlock() { 239 int newIndex = blocks.size(); 240 SsaBasicBlock newBlock = new SsaBasicBlock(newIndex, maxLabel++, this); 241 242 newBlock.getInsns().add(getGoto(newBlock)); 243 blocks.add(newBlock); 244 245 return newBlock; 246 } 247 248 /** 249 * @return block index of first execution block 250 */ getEntryBlockIndex()251 public int getEntryBlockIndex() { 252 return entryBlockIndex; 253 } 254 255 /** 256 * @return first execution block 257 */ getEntryBlock()258 public SsaBasicBlock getEntryBlock() { 259 return blocks.get(entryBlockIndex); 260 } 261 262 /** 263 * @return block index of exit block or {@code -1} if there is none 264 */ getExitBlockIndex()265 public int getExitBlockIndex() { 266 return exitBlockIndex; 267 } 268 269 /** 270 * @return {@code null-ok;} block of exit block or {@code null} if 271 * there is none 272 */ getExitBlock()273 public SsaBasicBlock getExitBlock() { 274 return exitBlockIndex < 0 ? null : blocks.get(exitBlockIndex); 275 } 276 277 /** 278 * @param bi block index or {@code -1} for none 279 * @return rop label or {code -1} if {@code bi} was {@code -1} 280 */ blockIndexToRopLabel(int bi)281 public int blockIndexToRopLabel(int bi) { 282 if (bi < 0) { 283 return -1; 284 } 285 return blocks.get(bi).getRopLabel(); 286 } 287 288 /** 289 * @return count of registers used in this method 290 */ getRegCount()291 public int getRegCount() { 292 return registerCount; 293 } 294 295 /** 296 * @return the total width, in register units, of the method's 297 * parameters 298 */ getParamWidth()299 public int getParamWidth() { 300 return paramWidth; 301 } 302 303 /** 304 * Returns {@code true} if this is a static method. 305 * 306 * @return {@code true} if this is a static method 307 */ isStatic()308 public boolean isStatic() { 309 return isStatic; 310 } 311 312 /** 313 * Borrows a register to use as a temp. Used in the phi removal process. 314 * Call returnSpareRegisters() when done. 315 * 316 * @param category width (1 or 2) of the register 317 * @return register number to use 318 */ borrowSpareRegister(int category)319 public int borrowSpareRegister(int category) { 320 int result = spareRegisterBase + borrowedSpareRegisters; 321 322 borrowedSpareRegisters += category; 323 registerCount = Math.max(registerCount, result + category); 324 325 return result; 326 } 327 328 /** 329 * Returns all borrowed registers. 330 */ returnSpareRegisters()331 public void returnSpareRegisters() { 332 borrowedSpareRegisters = 0; 333 } 334 335 /** 336 * @return {@code non-null;} basic block list. Do not modify. 337 */ getBlocks()338 public ArrayList<SsaBasicBlock> getBlocks() { 339 return blocks; 340 } 341 342 /** 343 * Returns the count of reachable blocks in this method: blocks that have 344 * predecessors (or are the start block) 345 * 346 * @return {@code >= 0;} number of reachable basic blocks 347 */ getCountReachableBlocks()348 public int getCountReachableBlocks() { 349 int ret = 0; 350 351 for (SsaBasicBlock b : blocks) { 352 // Blocks that have been disconnected don't count. 353 if (b.isReachable()) { 354 ret++; 355 } 356 } 357 358 return ret; 359 } 360 361 /** 362 * Computes reachability for all blocks in the method. First clears old 363 * values from all blocks, then starts with the entry block and walks down 364 * the control flow graph, marking all blocks it finds as reachable. 365 */ computeReachability()366 public void computeReachability() { 367 for (SsaBasicBlock block : blocks) { 368 block.setReachable(0); 369 } 370 371 ArrayList<SsaBasicBlock> blockList = new ArrayList<SsaBasicBlock>(); 372 blockList.add(this.getEntryBlock()); 373 374 while (!blockList.isEmpty()) { 375 SsaBasicBlock block = blockList.remove(0); 376 if (block.isReachable()) continue; 377 378 block.setReachable(1); 379 BitSet succs = block.getSuccessors(); 380 for (int i = succs.nextSetBit(0); i >= 0; 381 i = succs.nextSetBit(i + 1)) { 382 blockList.add(blocks.get(i)); 383 } 384 } 385 } 386 387 /** 388 * Remaps unversioned registers. 389 * 390 * @param mapper maps old registers to new. 391 */ mapRegisters(RegisterMapper mapper)392 public void mapRegisters(RegisterMapper mapper) { 393 for (SsaBasicBlock block : getBlocks()) { 394 for (SsaInsn insn : block.getInsns()) { 395 insn.mapRegisters(mapper); 396 } 397 } 398 399 registerCount = mapper.getNewRegisterCount(); 400 spareRegisterBase = registerCount; 401 } 402 403 /** 404 * Returns the insn that defines the given register 405 * @param reg register in question 406 * @return insn (actual instance from code) that defined this reg or null 407 * if reg is not defined. 408 */ getDefinitionForRegister(int reg)409 public SsaInsn getDefinitionForRegister(int reg) { 410 if (backMode) { 411 throw new RuntimeException("No def list in back mode"); 412 } 413 414 if (definitionList != null) { 415 return definitionList[reg]; 416 } 417 418 definitionList = new SsaInsn[getRegCount()]; 419 420 forEachInsn(new SsaInsn.Visitor() { 421 public void visitMoveInsn (NormalSsaInsn insn) { 422 definitionList[insn.getResult().getReg()] = insn; 423 } 424 public void visitPhiInsn (PhiInsn phi) { 425 definitionList[phi.getResult().getReg()] = phi; 426 } 427 public void visitNonMoveInsn (NormalSsaInsn insn) { 428 RegisterSpec result = insn.getResult(); 429 if (result != null) { 430 definitionList[insn.getResult().getReg()] = insn; 431 } 432 } 433 }); 434 435 return definitionList[reg]; 436 } 437 438 /** 439 * Builds useList and unmodifiableUseList. 440 */ buildUseList()441 private void buildUseList() { 442 if (backMode) { 443 throw new RuntimeException("No use list in back mode"); 444 } 445 446 useList = new ArrayList[registerCount]; 447 448 for (int i = 0; i < registerCount; i++) { 449 useList[i] = new ArrayList(); 450 } 451 452 forEachInsn(new SsaInsn.Visitor() { 453 /** {@inheritDoc} */ 454 public void visitMoveInsn (NormalSsaInsn insn) { 455 addToUses(insn); 456 } 457 /** {@inheritDoc} */ 458 public void visitPhiInsn (PhiInsn phi) { 459 addToUses(phi); 460 } 461 /** {@inheritDoc} */ 462 public void visitNonMoveInsn (NormalSsaInsn insn) { 463 addToUses(insn); 464 } 465 /** 466 * Adds specified insn to the uses list for all of its sources. 467 * @param insn {@code non-null;} insn to process 468 */ 469 private void addToUses(SsaInsn insn) { 470 RegisterSpecList rl = insn.getSources(); 471 int sz = rl.size(); 472 473 for (int i = 0; i < sz; i++) { 474 useList[rl.get(i).getReg()].add(insn); 475 } 476 } 477 }); 478 479 unmodifiableUseList = new List[registerCount]; 480 481 for (int i = 0; i < registerCount; i++) { 482 unmodifiableUseList[i] = Collections.unmodifiableList(useList[i]); 483 } 484 } 485 486 /** 487 * Updates the use list for a single change in source register. 488 * 489 * @param insn {@code non-null;} insn being changed 490 * @param oldSource {@code null-ok;} The source that was used, if 491 * applicable 492 * @param newSource {@code non-null;} the new source being used 493 */ onSourceChanged(SsaInsn insn, RegisterSpec oldSource, RegisterSpec newSource)494 /*package*/ void onSourceChanged(SsaInsn insn, 495 RegisterSpec oldSource, RegisterSpec newSource) { 496 if (useList == null) return; 497 498 if (oldSource != null) { 499 int reg = oldSource.getReg(); 500 useList[reg].remove(insn); 501 } 502 503 int reg = newSource.getReg(); 504 if (useList.length <= reg) { 505 useList = null; 506 return; 507 } 508 useList[reg].add(insn); 509 } 510 511 /** 512 * Updates the use list for a source list change. 513 * 514 * @param insn {@code insn non-null;} insn being changed. 515 * {@code insn.getSources()} must return the new source list. 516 * @param oldSources {@code null-ok;} list of sources that were 517 * previously used 518 */ onSourcesChanged(SsaInsn insn, RegisterSpecList oldSources)519 /*package*/ void onSourcesChanged(SsaInsn insn, 520 RegisterSpecList oldSources) { 521 if (useList == null) return; 522 523 if (oldSources != null) { 524 removeFromUseList(insn, oldSources); 525 } 526 527 RegisterSpecList sources = insn.getSources(); 528 int szNew = sources.size(); 529 530 for (int i = 0; i < szNew; i++) { 531 int reg = sources.get(i).getReg(); 532 useList[reg].add(insn); 533 } 534 } 535 536 /** 537 * Removes a given {@code insn} from the use lists for the given 538 * {@code oldSources} (rather than the sources currently 539 * returned by insn.getSources()). 540 * 541 * @param insn {@code non-null;} insn in question 542 * @param oldSources {@code null-ok;} registers whose use lists 543 * {@code insn} should be removed form 544 */ removeFromUseList(SsaInsn insn, RegisterSpecList oldSources)545 private void removeFromUseList(SsaInsn insn, RegisterSpecList oldSources) { 546 if (oldSources == null) { 547 return; 548 } 549 550 int szNew = oldSources.size(); 551 for (int i = 0; i < szNew; i++) { 552 if (!useList[oldSources.get(i).getReg()].remove(insn)) { 553 throw new RuntimeException("use not found"); 554 } 555 } 556 } 557 558 /** 559 * Adds an insn to both the use and def lists. For use when adding 560 * a new insn to the method. 561 * 562 * @param insn {@code non-null;} insn to add 563 */ onInsnAdded(SsaInsn insn)564 /*package*/ void onInsnAdded(SsaInsn insn) { 565 onSourcesChanged(insn, null); 566 updateOneDefinition(insn, null); 567 } 568 569 /** 570 * Removes an instruction from use and def lists. For use during 571 * instruction removal. 572 * 573 * @param insn {@code non-null;} insn to remove 574 */ onInsnRemoved(SsaInsn insn)575 /*package*/ void onInsnRemoved(SsaInsn insn) { 576 if (useList != null) { 577 removeFromUseList(insn, insn.getSources()); 578 } 579 580 RegisterSpec resultReg = insn.getResult(); 581 if (definitionList != null && resultReg != null) { 582 definitionList[resultReg.getReg()] = null; 583 } 584 } 585 586 /** 587 * Indicates that the instruction list has changed or the SSA register 588 * count has increased, so that internal datastructures that rely on 589 * it should be rebuild. In general, the various other on* methods 590 * should be called in preference when changes occur if they are 591 * applicable. 592 */ onInsnsChanged()593 public void onInsnsChanged() { 594 // Definition list will need to be recomputed 595 definitionList = null; 596 597 // Use list will need to be recomputed 598 useList = null; 599 unmodifiableUseList = null; 600 } 601 602 /** 603 * Updates a single definition. 604 * 605 * @param insn {@code non-null;} insn who's result should be recorded as 606 * a definition 607 * @param oldResult {@code null-ok;} a previous result that should 608 * be no longer considered a definition by this insn 609 */ updateOneDefinition(SsaInsn insn, RegisterSpec oldResult)610 /*package*/ void updateOneDefinition(SsaInsn insn, 611 RegisterSpec oldResult) { 612 if (definitionList == null) return; 613 614 if (oldResult != null) { 615 int reg = oldResult.getReg(); 616 definitionList[reg] = null; 617 } 618 619 RegisterSpec resultReg = insn.getResult(); 620 621 if (resultReg != null) { 622 int reg = resultReg.getReg(); 623 624 if (definitionList[reg] != null) { 625 throw new RuntimeException("Duplicate add of insn"); 626 } else { 627 definitionList[resultReg.getReg()] = insn; 628 } 629 } 630 } 631 632 /** 633 * Returns the list of all source uses (not results) for a register. 634 * 635 * @param reg register in question 636 * @return unmodifiable instruction list 637 */ getUseListForRegister(int reg)638 public List<SsaInsn> getUseListForRegister(int reg) { 639 640 if (unmodifiableUseList == null) { 641 buildUseList(); 642 } 643 644 return unmodifiableUseList[reg]; 645 } 646 647 /** 648 * Returns a modifiable copy of the register use list. 649 * 650 * @return modifiable copy of the use-list, indexed by register 651 */ getUseListCopy()652 public ArrayList<SsaInsn>[] getUseListCopy() { 653 if (useList == null) { 654 buildUseList(); 655 } 656 657 ArrayList<SsaInsn>[] useListCopy 658 = (ArrayList<SsaInsn>[])(new ArrayList[registerCount]); 659 660 for (int i = 0; i < registerCount; i++) { 661 useListCopy[i] = (ArrayList<SsaInsn>)(new ArrayList(useList[i])); 662 } 663 664 return useListCopy; 665 } 666 667 /** 668 * Checks to see if the given SSA reg is ever associated with a local 669 * local variable. Each SSA reg may be associated with at most one 670 * local var. 671 * 672 * @param spec {@code non-null;} ssa reg 673 * @return true if reg is ever associated with a local 674 */ isRegALocal(RegisterSpec spec)675 public boolean isRegALocal(RegisterSpec spec) { 676 SsaInsn defn = getDefinitionForRegister(spec.getReg()); 677 678 if (defn == null) { 679 // version 0 registers are never used as locals 680 return false; 681 } 682 683 // Does the definition have a local associated with it? 684 if (defn.getLocalAssignment() != null) return true; 685 686 // If not, is there a mark-local insn? 687 for (SsaInsn use : getUseListForRegister(spec.getReg())) { 688 Insn insn = use.getOriginalRopInsn(); 689 690 if (insn != null 691 && insn.getOpcode().getOpcode() == RegOps.MARK_LOCAL) { 692 return true; 693 } 694 } 695 696 return false; 697 } 698 699 /** 700 * Sets the new register count after renaming. 701 * 702 * @param newRegCount new register count 703 */ setNewRegCount(int newRegCount)704 /*package*/ void setNewRegCount(int newRegCount) { 705 registerCount = newRegCount; 706 spareRegisterBase = registerCount; 707 onInsnsChanged(); 708 } 709 710 /** 711 * Makes a new SSA register. For use after renaming has completed. 712 * 713 * @return {@code >=0;} new SSA register. 714 */ makeNewSsaReg()715 public int makeNewSsaReg() { 716 int reg = registerCount++; 717 spareRegisterBase = registerCount; 718 onInsnsChanged(); 719 return reg; 720 } 721 722 /** 723 * Visits all insns in this method. 724 * 725 * @param visitor {@code non-null;} callback interface 726 */ forEachInsn(SsaInsn.Visitor visitor)727 public void forEachInsn(SsaInsn.Visitor visitor) { 728 for (SsaBasicBlock block : blocks) { 729 block.forEachInsn(visitor); 730 } 731 } 732 733 /** 734 * Visits each phi insn in this method 735 * @param v {@code non-null;} callback. 736 * 737 */ forEachPhiInsn(PhiInsn.Visitor v)738 public void forEachPhiInsn(PhiInsn.Visitor v) { 739 for (SsaBasicBlock block : blocks) { 740 block.forEachPhiInsn(v); 741 } 742 } 743 744 745 /** 746 * Walks the basic block tree in depth-first order, calling the visitor 747 * method once for every block. This depth-first walk may be run forward 748 * from the method entry point or backwards from the method exit points. 749 * 750 * @param reverse true if this should walk backwards from the exit points 751 * @param v {@code non-null;} callback interface. {@code parent} is set 752 * unless this is the root node 753 */ forEachBlockDepthFirst(boolean reverse, SsaBasicBlock.Visitor v)754 public void forEachBlockDepthFirst(boolean reverse, 755 SsaBasicBlock.Visitor v) { 756 BitSet visited = new BitSet(blocks.size()); 757 758 // We push the parent first, then the child on the stack. 759 Stack<SsaBasicBlock> stack = new Stack<SsaBasicBlock>(); 760 761 SsaBasicBlock rootBlock = reverse ? getExitBlock() : getEntryBlock(); 762 763 if (rootBlock == null) { 764 // in the case there's no exit block 765 return; 766 } 767 768 stack.add(null); // Start with null parent. 769 stack.add(rootBlock); 770 771 while (stack.size() > 0) { 772 SsaBasicBlock cur = stack.pop(); 773 SsaBasicBlock parent = stack.pop(); 774 775 if (!visited.get(cur.getIndex())) { 776 BitSet children 777 = reverse ? cur.getPredecessors() : cur.getSuccessors(); 778 for (int i = children.nextSetBit(0); i >= 0 779 ; i = children.nextSetBit(i + 1)) { 780 stack.add(cur); 781 stack.add(blocks.get(i)); 782 } 783 visited.set(cur.getIndex()); 784 v.visitBlock(cur, parent); 785 } 786 } 787 } 788 789 /** 790 * Visits blocks in dom-tree order, starting at the current node. 791 * The {@code parent} parameter of the Visitor.visitBlock callback 792 * is currently always set to null. 793 * 794 * @param v {@code non-null;} callback interface 795 */ forEachBlockDepthFirstDom(SsaBasicBlock.Visitor v)796 public void forEachBlockDepthFirstDom(SsaBasicBlock.Visitor v) { 797 BitSet visited = new BitSet(getBlocks().size()); 798 Stack<SsaBasicBlock> stack = new Stack<SsaBasicBlock>(); 799 800 stack.add(getEntryBlock()); 801 802 while (stack.size() > 0) { 803 SsaBasicBlock cur = stack.pop(); 804 ArrayList<SsaBasicBlock> curDomChildren = cur.getDomChildren(); 805 806 if (!visited.get(cur.getIndex())) { 807 // We walk the tree this way for historical reasons... 808 for (int i = curDomChildren.size() - 1; i >= 0; i--) { 809 SsaBasicBlock child = curDomChildren.get(i); 810 stack.add(child); 811 } 812 visited.set(cur.getIndex()); 813 v.visitBlock(cur, null); 814 } 815 } 816 } 817 818 /** 819 * Deletes all insns in the set from this method. 820 * 821 * @param deletedInsns {@code non-null;} insns to delete 822 */ deleteInsns(Set<SsaInsn> deletedInsns)823 public void deleteInsns(Set<SsaInsn> deletedInsns) { 824 for (SsaBasicBlock block : getBlocks()) { 825 ArrayList<SsaInsn> insns = block.getInsns(); 826 827 for (int i = insns.size() - 1; i >= 0; i--) { 828 SsaInsn insn = insns.get(i); 829 830 if (deletedInsns.contains(insn)) { 831 onInsnRemoved(insn); 832 insns.remove(i); 833 } 834 } 835 836 // Check to see if we need to add a GOTO 837 838 int insnsSz = insns.size(); 839 SsaInsn lastInsn = (insnsSz == 0) ? null : insns.get(insnsSz - 1); 840 841 if (block != getExitBlock() && (insnsSz == 0 842 || lastInsn.getOriginalRopInsn() == null 843 || lastInsn.getOriginalRopInsn().getOpcode() 844 .getBranchingness() == Rop.BRANCH_NONE)) { 845 // We managed to eat a throwable insn 846 847 Insn gotoInsn = new PlainInsn(Rops.GOTO, 848 SourcePosition.NO_INFO, null, RegisterSpecList.EMPTY); 849 insns.add(SsaInsn.makeFromRop(gotoInsn, block)); 850 851 // Remove secondary successors from this block 852 BitSet succs = block.getSuccessors(); 853 for (int i = succs.nextSetBit(0); i >= 0; 854 i = succs.nextSetBit(i + 1)) { 855 if (i != block.getPrimarySuccessorIndex()) { 856 block.removeSuccessor(i); 857 } 858 } 859 } 860 } 861 } 862 863 /** 864 * Sets "back-convert mode". Set during back-conversion when registers 865 * are about to be mapped into a non-SSA namespace. When true, 866 * use and def lists are unavailable. 867 */ setBackMode()868 public void setBackMode() { 869 backMode = true; 870 useList = null; 871 definitionList = null; 872 } 873 } 874