dalvik/dx/src/com/android/dx/ssa/SsaRenamer.java

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