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.LocalItem; 20 import com.android.dx.rop.code.PlainInsn; 21 import com.android.dx.rop.code.RegisterSpec; 22 import com.android.dx.rop.code.RegisterSpecList; 23 import com.android.dx.rop.code.Rops; 24 import com.android.dx.rop.code.SourcePosition; 25 import com.android.dx.rop.type.Type; 26 import com.android.dx.util.IntList; 27 import java.util.ArrayList; 28 import java.util.BitSet; 29 import java.util.HashMap; 30 import java.util.HashSet; 31 32 /** 33 * Complete transformation to SSA form by renaming all registers accessed.<p> 34 * 35 * See Appel algorithm 19.7<p> 36 * 37 * Unlike the original algorithm presented in Appel, this renamer converts 38 * to a new flat (versionless) register space. The "version 0" registers, 39 * which represent the initial state of the Rop registers and should never 40 * actually be meaningfully accessed in a legal program, are represented 41 * as the first N registers in the SSA namespace. Subsequent assignments 42 * are assigned new unique names. Note that the incoming Rop representation 43 * has a concept of register widths, where 64-bit values are stored into 44 * two adjoining Rop registers. This adjoining register representation is 45 * ignored in SSA form conversion and while in SSA form, each register can be e 46 * either 32 or 64 bits wide depending on use. The adjoining-register 47 * represention is re-created later when converting back to Rop form. <p> 48 * 49 * But, please note, the SSA Renamer's ignoring of the adjoining-register ROP 50 * representation means that unaligned accesses to 64-bit registers are not 51 * supported. For example, you cannot do a 32-bit operation on a portion of 52 * a 64-bit register. This will never be observed to happen when coming 53 * from Java code, of course.<p> 54 * 55 * The implementation here, rather than keeping a single register version 56 * stack for the entire method as the dom tree is walked, instead keeps 57 * a mapping table for the current block being processed. Once the 58 * current block has been processed, this mapping table is then copied 59 * and used as the initial state for child blocks.<p> 60 */ 61 public class SsaRenamer implements Runnable { 62 /** debug flag */ 63 private static final boolean DEBUG = false; 64 65 /** method we're processing */ 66 private final SsaMethod ssaMeth; 67 68 /** next available SSA register */ 69 private int nextSsaReg; 70 71 /** the number of original rop registers */ 72 private final int ropRegCount; 73 74 /** work only on registers above this value */ 75 private int threshold; 76 77 /** 78 * indexed by block index; register version state for each block start. 79 * This list is updated by each dom parent for its children. The only 80 * sub-arrays that exist at any one time are the start states for blocks 81 * yet to be processed by a {@code BlockRenamer} instance. 82 */ 83 private final RegisterSpec[][] startsForBlocks; 84 85 /** map of SSA register number to debug (local var names) or null of n/a */ 86 private final ArrayList<LocalItem> ssaRegToLocalItems; 87 88 /** 89 * maps SSA registers back to the original rop number. Used for 90 * debug only. 91 */ 92 private IntList ssaRegToRopReg; 93 94 /** 95 * Constructs an instance of the renamer 96 * 97 * @param ssaMeth {@code non-null;} un-renamed SSA method that will 98 * be renamed. 99 */ 100 public SsaRenamer(SsaMethod ssaMeth) { 101 ropRegCount = ssaMeth.getRegCount(); 102 103 this.ssaMeth = ssaMeth; 104 105 /* 106 * Reserve the first N registers in the SSA register space for 107 * "version 0" registers. 108 */ 109 nextSsaReg = ropRegCount; 110 threshold = 0; 111 startsForBlocks = new RegisterSpec[ssaMeth.getBlocks().size()][]; 112 113 ssaRegToLocalItems = new ArrayList<LocalItem>(); 114 115 if (DEBUG) { 116 ssaRegToRopReg = new IntList(ropRegCount); 117 } 118 119 /* 120 * Appel 19.7 121 * 122 * Initialization: 123 * for each variable a // register i 124 * Count[a] <- 0 // nextSsaReg, flattened 125 * Stack[a] <- 0 // versionStack 126 * push 0 onto Stack[a] 127 * 128 */ 129 130 // top entry for the version stack is version 0 131 RegisterSpec[] initialRegMapping = new RegisterSpec[ropRegCount]; 132 for (int i = 0; i < ropRegCount; i++) { 133 // everyone starts with a version 0 register 134 initialRegMapping[i] = RegisterSpec.make(i, Type.VOID); 135 136 if (DEBUG) { 137 ssaRegToRopReg.add(i); 138 } 139 } 140 141 // Initial state for entry block 142 startsForBlocks[ssaMeth.getEntryBlockIndex()] = initialRegMapping; 143 } 144 145 /** 146 * Constructs an instance of the renamer with threshold set 147 * 148 * @param ssaMeth {@code non-null;} un-renamed SSA method that will 149 * be renamed. 150 * @param thresh registers below this number are unchanged 151 */ 152 public SsaRenamer(SsaMethod ssaMeth, int thresh) { 153 this(ssaMeth); 154 threshold = thresh; 155 } 156 157 /** 158 * Performs renaming transformation, modifying the method's instructions 159 * in-place. 160 */ 161 @Override 162 public void run() { 163 // Rename each block in dom-tree DFS order. 164 ssaMeth.forEachBlockDepthFirstDom(new SsaBasicBlock.Visitor() { 165 @Override 166 public void visitBlock (SsaBasicBlock block, 167 SsaBasicBlock unused) { 168 new BlockRenamer(block).process(); 169 } 170 }); 171 172 ssaMeth.setNewRegCount(nextSsaReg); 173 ssaMeth.onInsnsChanged(); 174 175 if (DEBUG) { 176 System.out.println("SSA\tRop"); 177 /* 178 * We're going to compute the version of the rop register 179 * by keeping a running total of how many times the rop 180 * register has been mapped. 181 */ 182 int[] versions = new int[ropRegCount]; 183 184 int sz = ssaRegToRopReg.size(); 185 for (int i = 0; i < sz; i++) { 186 int ropReg = ssaRegToRopReg.get(i); 187 System.out.println(i + "\t" + ropReg + "[" 188 + versions[ropReg] + "]"); 189 versions[ropReg]++; 190 } 191 } 192 } 193 194 /** 195 * Duplicates a RegisterSpec array. 196 * 197 * @param orig {@code non-null;} array to duplicate 198 * @return {@code non-null;} new instance 199 */ 200 private static RegisterSpec[] dupArray(RegisterSpec[] orig) { 201 RegisterSpec[] copy = new RegisterSpec[orig.length]; 202 203 System.arraycopy(orig, 0, copy, 0, orig.length); 204 205 return copy; 206 } 207 208 /** 209 * Gets a local variable item for a specified register. 210 * 211 * @param ssaReg register in SSA name space 212 * @return {@code null-ok;} Local variable name or null if none 213 */ 214 private LocalItem getLocalForNewReg(int ssaReg) { 215 if (ssaReg < ssaRegToLocalItems.size()) { 216 return ssaRegToLocalItems.get(ssaReg); 217 } else { 218 return null; 219 } 220 } 221 222 /** 223 * Records a debug (local variable) name for a specified register. 224 * 225 * @param ssaReg non-null named register spec in SSA name space 226 */ 227 private void setNameForSsaReg(RegisterSpec ssaReg) { 228 int reg = ssaReg.getReg(); 229 LocalItem local = ssaReg.getLocalItem(); 230 231 ssaRegToLocalItems.ensureCapacity(reg + 1); 232 while (ssaRegToLocalItems.size() <= reg) { 233 ssaRegToLocalItems.add(null); 234 } 235 236 ssaRegToLocalItems.set(reg, local); 237 } 238 239 /** 240 * Returns true if this SSA register is below the specified threshold. 241 * Used when most code is already in SSA form, and renaming is needed only 242 * for registers above a certain threshold. 243 * 244 * @param ssaReg the SSA register in question 245 * @return {@code true} if its register number is below the threshold 246 */ 247 private boolean isBelowThresholdRegister(int ssaReg) { 248 return ssaReg < threshold; 249 } 250 251 /** 252 * Returns true if this SSA register is a "version 0" 253 * register. All version 0 registers are assigned the first N register 254 * numbers, where N is the count of original rop registers. 255 * 256 * @param ssaReg the SSA register in question 257 * @return true if it is a version 0 register. 258 */ 259 private boolean isVersionZeroRegister(int ssaReg) { 260 return ssaReg < ropRegCount; 261 } 262 263 /** 264 * Returns true if a and b are equal or are both null. 265 * 266 * @param a null-ok 267 * @param b null-ok 268 * @return Returns true if a and b are equal or are both null 269 */ 270 private static boolean equalsHandlesNulls(Object a, Object b) { 271 return a == b || (a != null && a.equals(b)); 272 } 273 274 /** 275 * Processes all insns in a block and renames their registers 276 * as appropriate. 277 */ 278 private class BlockRenamer implements SsaInsn.Visitor{ 279 /** {@code non-null;} block we're processing. */ 280 private final SsaBasicBlock block; 281 282 /** 283 * {@code non-null;} indexed by old register name. The current 284 * top of the version stack as seen by this block. It's 285 * initialized from the ending state of its dom parent, 286 * updated as the block's instructions are processed, and then 287 * copied to each one of its dom children. 288 */ 289 private final RegisterSpec[] currentMapping; 290 291 /** 292 * contains the set of moves we need to keep to preserve local 293 * var info. All other moves will be deleted. 294 */ 295 private final HashSet<SsaInsn> movesToKeep; 296 297 /** 298 * maps the set of insns to replace after renaming is finished 299 * on the block. 300 */ 301 private final HashMap<SsaInsn, SsaInsn> insnsToReplace; 302 303 private final RenamingMapper mapper; 304 305 /** 306 * Constructs a block renamer instance. Call {@code process} 307 * to process. 308 * 309 * @param block {@code non-null;} block to process 310 */ 311 BlockRenamer(final SsaBasicBlock block) { 312 this.block = block; 313 currentMapping = startsForBlocks[block.getIndex()]; 314 movesToKeep = new HashSet<SsaInsn>(); 315 insnsToReplace = new HashMap<SsaInsn, SsaInsn>(); 316 mapper = new RenamingMapper(); 317 318 // We don't need our own start state anymore 319 startsForBlocks[block.getIndex()] = null; 320 } 321 322 /** 323 * Provides a register mapping between the old register space 324 * and the current renaming mapping. The mapping is updated 325 * as the current block's instructions are processed. 326 */ 327 private class RenamingMapper extends RegisterMapper { 328 public RenamingMapper() { 329 // This space intentionally left blank. 330 } 331 332 /** {@inheritDoc} */ 333 @Override 334 public int getNewRegisterCount() { 335 return nextSsaReg; 336 } 337 338 /** {@inheritDoc} */ 339 @Override 340 public RegisterSpec map(RegisterSpec registerSpec) { 341 if (registerSpec == null) return null; 342 343 int reg = registerSpec.getReg(); 344 345 // For debugging: assert that the mapped types are compatible. 346 if (DEBUG) { 347 RegisterSpec newVersion = currentMapping[reg]; 348 if (newVersion.getBasicType() != Type.BT_VOID 349 && registerSpec.getBasicFrameType() 350 != newVersion.getBasicFrameType()) { 351 352 throw new RuntimeException( 353 "mapping registers of incompatible types! " 354 + registerSpec 355 + " " + currentMapping[reg]); 356 } 357 } 358 359 return registerSpec.withReg(currentMapping[reg].getReg()); 360 } 361 } 362 363 /** 364 * Renames all the variables in this block and inserts appriopriate 365 * phis in successor blocks. 366 */ 367 public void process() { 368 /* 369 * From Appel: 370 * 371 * Rename(n) = 372 * for each statement S in block n // 'statement' in 'block' 373 */ 374 375 block.forEachInsn(this); 376 377 updateSuccessorPhis(); 378 379 // Delete all move insns in this block. 380 ArrayList<SsaInsn> insns = block.getInsns(); 381 int szInsns = insns.size(); 382 383 for (int i = szInsns - 1; i >= 0 ; i--) { 384 SsaInsn insn = insns.get(i); 385 SsaInsn replaceInsn; 386 387 replaceInsn = insnsToReplace.get(insn); 388 389 if (replaceInsn != null) { 390 insns.set(i, replaceInsn); 391 } else if (insn.isNormalMoveInsn() 392 && !movesToKeep.contains(insn)) { 393 insns.remove(i); 394 } 395 } 396 397 // Store the start states for our dom children. 398 boolean first = true; 399 for (SsaBasicBlock child : block.getDomChildren()) { 400 if (child != block) { 401 // Don't bother duplicating the array for the first child. 402 RegisterSpec[] childStart = first ? currentMapping 403 : dupArray(currentMapping); 404 405 startsForBlocks[child.getIndex()] = childStart; 406 first = false; 407 } 408 } 409 410 // currentMapping is owned by a child now. 411 } 412 413 /** 414 * Enforces a few contraints when a register mapping is added. 415 * 416 * <ol> 417 * <li> Ensures that all new SSA registers specs in the mapping 418 * table with the same register number are identical. In effect, once 419 * an SSA register spec has received or lost a local variable name, 420 * then every old-namespace register that maps to it should gain or 421 * lose its local variable name as well. 422 * <li> Records the local name associated with the 423 * register so that a register is never associated with more than one 424 * local. 425 * <li> ensures that only one SSA register 426 * at a time is considered to be associated with a local variable. When 427 * {@code currentMapping} is updated and the newly added element 428 * is named, strip that name from any other SSA registers. 429 * </ol> 430 * 431 * @param ropReg {@code >= 0;} rop register number 432 * @param ssaReg {@code non-null;} an SSA register that has just 433 * been added to {@code currentMapping} 434 */ 435 private void addMapping(int ropReg, RegisterSpec ssaReg) { 436 int ssaRegNum = ssaReg.getReg(); 437 LocalItem ssaRegLocal = ssaReg.getLocalItem(); 438 439 currentMapping[ropReg] = ssaReg; 440 441 /* 442 * Ensure all SSA register specs with the same reg are identical. 443 */ 444 for (int i = currentMapping.length - 1; i >= 0; i--) { 445 RegisterSpec cur = currentMapping[i]; 446 447 if (ssaRegNum == cur.getReg()) { 448 currentMapping[i] = ssaReg; 449 } 450 } 451 452 // All further steps are for registers with local information. 453 if (ssaRegLocal == null) { 454 return; 455 } 456 457 // Record that this SSA reg has been associated with a local. 458 setNameForSsaReg(ssaReg); 459 460 // Ensure that no other SSA regs are associated with this local. 461 for (int i = currentMapping.length - 1; i >= 0; i--) { 462 RegisterSpec cur = currentMapping[i]; 463 464 if (ssaRegNum != cur.getReg() 465 && ssaRegLocal.equals(cur.getLocalItem())) { 466 currentMapping[i] = cur.withLocalItem(null); 467 } 468 } 469 } 470 471 /** 472 * {@inheritDoc} 473 * 474 * Phi insns have their result registers renamed. 475 */ 476 @Override 477 public void visitPhiInsn(PhiInsn phi) { 478 /* don't process sources for phi's */ 479 processResultReg(phi); 480 } 481 482 /** 483 * {@inheritDoc} 484 * 485 * Move insns are treated as a simple mapping operation, and 486 * will later be removed unless they represent a local variable 487 * assignment. If they represent a local variable assignement, they 488 * are preserved. 489 */ 490 @Override 491 public void visitMoveInsn(NormalSsaInsn insn) { 492 /* 493 * For moves: copy propogate the move if we can, but don't 494 * if we need to preserve local variable info and the 495 * result has a different name than the source. 496 */ 497 498 RegisterSpec ropResult = insn.getResult(); 499 int ropResultReg = ropResult.getReg(); 500 int ropSourceReg = insn.getSources().get(0).getReg(); 501 502 insn.mapSourceRegisters(mapper); 503 int ssaSourceReg = insn.getSources().get(0).getReg(); 504 505 LocalItem sourceLocal 506 = currentMapping[ropSourceReg].getLocalItem(); 507 LocalItem resultLocal = ropResult.getLocalItem(); 508 509 /* 510 * A move from a register that's currently associated with a local 511 * to one that will not be associated with a local does not need 512 * to be preserved, but the local association should remain. 513 * Hence, we inherit the sourceLocal where the resultLocal is null. 514 */ 515 516 LocalItem newLocal 517 = (resultLocal == null) ? sourceLocal : resultLocal; 518 LocalItem associatedLocal = getLocalForNewReg(ssaSourceReg); 519 520 /* 521 * If we take the new local, will only one local have ever 522 * been associated with this SSA reg? 523 */ 524 boolean onlyOneAssociatedLocal 525 = associatedLocal == null || newLocal == null 526 || newLocal.equals(associatedLocal); 527 528 /* 529 * If we're going to copy-propogate, then the ssa register 530 * spec that's going to go into the mapping is made up of 531 * the source register number mapped from above, the type 532 * of the result, and the name either from the result (if 533 * specified) or inherited from the existing mapping. 534 * 535 * The move source has incomplete type information in null 536 * object cases, so the result type is used. 537 */ 538 RegisterSpec ssaReg 539 = RegisterSpec.makeLocalOptional( 540 ssaSourceReg, ropResult.getType(), newLocal); 541 542 if (!Optimizer.getPreserveLocals() || (onlyOneAssociatedLocal 543 && equalsHandlesNulls(newLocal, sourceLocal)) && 544 threshold == 0) { 545 /* 546 * We don't have to keep this move to preserve local 547 * information. Either the name is the same, or the result 548 * register spec is unnamed. 549 */ 550 551 addMapping(ropResultReg, ssaReg); 552 } else if (onlyOneAssociatedLocal && sourceLocal == null && 553 threshold == 0) { 554 /* 555 * The register was previously unnamed. This means that a 556 * local starts after it's first assignment in SSA form 557 */ 558 559 RegisterSpecList ssaSources = RegisterSpecList.make( 560 RegisterSpec.make(ssaReg.getReg(), 561 ssaReg.getType(), newLocal)); 562 563 SsaInsn newInsn 564 = SsaInsn.makeFromRop( 565 new PlainInsn(Rops.opMarkLocal(ssaReg), 566 SourcePosition.NO_INFO, null, ssaSources),block); 567 568 insnsToReplace.put(insn, newInsn); 569 570 // Just map as above. 571 addMapping(ropResultReg, ssaReg); 572 } else { 573 /* 574 * Do not copy-propogate, since the two registers have 575 * two different local-variable names. 576 */ 577 processResultReg(insn); 578 579 movesToKeep.add(insn); 580 } 581 } 582 583 /** 584 * {@inheritDoc} 585 * 586 * All insns that are not move or phi insns have their source registers 587 * mapped ot the current mapping. Their result registers are then 588 * renamed to a new SSA register which is then added to the current 589 * register mapping. 590 */ 591 @Override 592 public void visitNonMoveInsn(NormalSsaInsn insn) { 593 /* for each use of some variable X in S */ 594 insn.mapSourceRegisters(mapper); 595 596 processResultReg(insn); 597 } 598 599 /** 600 * Renames the result register of this insn and updates the 601 * current register mapping. Does nothing if this insn has no result. 602 * Applied to all non-move insns. 603 * 604 * @param insn insn to process. 605 */ 606 void processResultReg(SsaInsn insn) { 607 RegisterSpec ropResult = insn.getResult(); 608 609 if (ropResult == null) { 610 return; 611 } 612 613 int ropReg = ropResult.getReg(); 614 if (isBelowThresholdRegister(ropReg)) { 615 return; 616 } 617 618 insn.changeResultReg(nextSsaReg); 619 addMapping(ropReg, insn.getResult()); 620 621 if (DEBUG) { 622 ssaRegToRopReg.add(ropReg); 623 } 624 625 nextSsaReg++; 626 } 627 628 /** 629 * Updates the phi insns in successor blocks with operands based 630 * on the current mapping of the rop register the phis represent. 631 */ 632 private void updateSuccessorPhis() { 633 PhiInsn.Visitor visitor = new PhiInsn.Visitor() { 634 @Override 635 public void visitPhiInsn (PhiInsn insn) { 636 int ropReg; 637 638 ropReg = insn.getRopResultReg(); 639 if (isBelowThresholdRegister(ropReg)) { 640 return; 641 } 642 643 /* 644 * Never add a version 0 register as a phi 645 * operand. Version 0 registers represent the 646 * initial register state, and thus are never 647 * significant. Furthermore, the register liveness 648 * algorithm doesn't properly count them as "live 649 * in" at the beginning of the method. 650 */ 651 652 RegisterSpec stackTop = currentMapping[ropReg]; 653 if (!isVersionZeroRegister(stackTop.getReg())) { 654 insn.addPhiOperand(stackTop, block); 655 } 656 } 657 }; 658 659 BitSet successors = block.getSuccessors(); 660 for (int i = successors.nextSetBit(0); i >= 0; 661 i = successors.nextSetBit(i + 1)) { 662 SsaBasicBlock successor = ssaMeth.getBlocks().get(i); 663 successor.forEachPhiInsn(visitor); 664 } 665 } 666 } 667 } 668