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