content: /*
   * Copyright (C) 2007 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package com.taobao.android.dx.ssa;
  
  import com.taobao.android.dx.rop.code.LocalItem;
  import com.taobao.android.dx.rop.code.PlainInsn;
  import com.taobao.android.dx.rop.code.RegisterSpec;
  import com.taobao.android.dx.rop.code.RegisterSpecList;
  import com.taobao.android.dx.rop.code.Rops;
  import com.taobao.android.dx.rop.code.SourcePosition;
  import com.taobao.android.dx.rop.type.Type;
  import com.taobao.android.dx.util.IntList;
  import java.util.ArrayList;
  import java.util.BitSet;
  import java.util.HashMap;
  import java.util.HashSet;
  
  /**
   * Complete transformation to SSA form by renaming all registers accessed.<p>
   *
   * See Appel algorithm 19.7<p>
   *
   * Unlike the original algorithm presented in Appel, this renamer converts
   * to a new flat (versionless) register space. The "version 0" registers,
   * which represent the initial state of the Rop registers and should never
   * actually be meaningfully accessed in a legal program, are represented
   * as the first N registers in the SSA namespace. Subsequent assignments
   * are assigned new unique names. Note that the incoming Rop representation
   * has a concept of register widths, where 64-bit values are stored into
   * two adjoining Rop registers. This adjoining register representation is
   * ignored in SSA form conversion and while in SSA form, each register can be e
   * either 32 or 64 bits wide depending on use. The adjoining-register
   * represention is re-created later when converting back to Rop form. <p>
   *
   * But, please note, the SSA Renamer's ignoring of the adjoining-register ROP
   * representation means that unaligned accesses to 64-bit registers are not
   * supported. For example, you cannot do a 32-bit operation on a portion of
   * a 64-bit register. This will never be observed to happen when coming
   * from Java code, of course.<p>
   *
   * The implementation here, rather than keeping a single register version
   * stack for the entire method as the dom tree is walked, instead keeps
   * a mapping table for the current block being processed. Once the
   * current block has been processed, this mapping table is then copied
   * and used as the initial state for child blocks.<p>
   */
  public class SsaRenamer implements Runnable {
      /** debug flag */
      private static final boolean DEBUG = false;
  
      /** method we're processing */
      private final SsaMethod ssaMeth;
  
      /** next available SSA register */
      private int nextSsaReg;
  
      /** the number of original rop registers */
      private final int ropRegCount;
  
      /** work only on registers above this value */
      private int threshold;
  
      /**
       * indexed by block index; register version state for each block start.
       * This list is updated by each dom parent for its children. The only
       * sub-arrays that exist at any one time are the start states for blocks
       * yet to be processed by a {@code BlockRenamer} instance.
       */
      private final RegisterSpec[][] startsForBlocks;
  
      /** map of SSA register number to debug (local var names) or null of n/a */
      private final ArrayList<LocalItem> ssaRegToLocalItems;
  
      /**
       * maps SSA registers back to the original rop number. Used for
       * debug only.
       */
      private IntList ssaRegToRopReg;
  
      /**
       * Constructs an instance of the renamer
       *
       * @param ssaMeth {@code non-null;} un-renamed SSA method that will
       * be renamed.
       */
      public SsaRenamer(SsaMethod ssaMeth) {
          ropRegCount = ssaMeth.getRegCount();
  
          this.ssaMeth = ssaMeth;
  
          /*
           * Reserve the first N registers in the SSA register space for
           * "version 0" registers.
           */
          nextSsaReg = ropRegCount;
          threshold = 0;
          startsForBlocks = new RegisterSpec[ssaMeth.getBlocks().size()][];
  
          ssaRegToLocalItems = new ArrayList<LocalItem>();
  
          if (DEBUG) {
              ssaRegToRopReg = new IntList(ropRegCount);
          }
  
          /*
           * Appel 19.7
           *
           * Initialization:
           *   for each variable a        // register i
           *      Count[a] <- 0           // nextSsaReg, flattened
           *      Stack[a] <- 0           // versionStack
           *      push 0 onto Stack[a]
           *
           */
  
          // top entry for the version stack is version 0
          RegisterSpec[] initialRegMapping = new RegisterSpec[ropRegCount];
          for (int i = 0; i < ropRegCount; i++) {
              // everyone starts with a version 0 register
              initialRegMapping[i] = RegisterSpec.make(i, Type.VOID);
  
              if (DEBUG) {
                  ssaRegToRopReg.add(i);
              }
          }
  
          // Initial state for entry block
          startsForBlocks[ssaMeth.getEntryBlockIndex()] = initialRegMapping;
      }
  
      /**
      * Constructs an instance of the renamer with threshold set
      *
      * @param ssaMeth {@code non-null;} un-renamed SSA method that will
      * be renamed.
      * @param thresh registers below this number are unchanged
      */
     public SsaRenamer(SsaMethod ssaMeth, int thresh) {
         this(ssaMeth);
         threshold = thresh;
     }
  
      /**
       * Performs renaming transformation, modifying the method's instructions
       * in-place.
       */
      public void run() {
          // Rename each block in dom-tree DFS order.
          ssaMeth.forEachBlockDepthFirstDom(new SsaBasicBlock.Visitor() {
              public void visitBlock (SsaBasicBlock block,
                      SsaBasicBlock unused) {
                  new BlockRenamer(block).process();
              }
          });
  
          ssaMeth.setNewRegCount(nextSsaReg);
          ssaMeth.onInsnsChanged();
  
          if (DEBUG) {
              System.out.println("SSA\tRop");
              /*
               * We're going to compute the version of the rop register
               * by keeping a running total of how many times the rop
               * register has been mapped.
               */
              int[] versions = new int[ropRegCount];
  
              int sz = ssaRegToRopReg.size();
              for (int i = 0; i < sz; i++) {
                  int ropReg = ssaRegToRopReg.get(i);
                  System.out.println(i + "\t" + ropReg + "["
                          + versions[ropReg] + "]");
                  versions[ropReg]++;
              }
          }
      }
  
      /**
       * Duplicates a RegisterSpec array.
       *
       * @param orig {@code non-null;} array to duplicate
       * @return {@code non-null;} new instance
       */
      private static  RegisterSpec[] dupArray(RegisterSpec[] orig) {
          RegisterSpec[] copy = new RegisterSpec[orig.length];
  
          System.arraycopy(orig, 0, copy, 0, orig.length);
  
          return copy;
      }
  
      /**
       * Gets a local variable item for a specified register.
       *
       * @param ssaReg register in SSA name space
       * @return {@code null-ok;} Local variable name or null if none
       */
      private LocalItem getLocalForNewReg(int ssaReg) {
          if (ssaReg < ssaRegToLocalItems.size()) {
              return ssaRegToLocalItems.get(ssaReg);
          } else {
              return null;
          }
      }
  
      /**
       * Records a debug (local variable) name for a specified register.
       *
       * @param ssaReg non-null named register spec in SSA name space
       */
      private void setNameForSsaReg(RegisterSpec ssaReg) {
          int reg = ssaReg.getReg();
          LocalItem local = ssaReg.getLocalItem();
  
          ssaRegToLocalItems.ensureCapacity(reg + 1);
          while (ssaRegToLocalItems.size() <= reg) {
              ssaRegToLocalItems.add(null);
          }
  
          ssaRegToLocalItems.set(reg, local);
      }
  
      /**
       * Returns true if this SSA register is below the specified threshold.
       * Used when most code is already in SSA form, and renaming is needed only
       * for registers above a certain threshold.
       *
       * @param ssaReg the SSA register in question
       * @return {@code true} if its register number is below the threshold
       */
      private boolean isBelowThresholdRegister(int ssaReg) {
          return ssaReg < threshold;
      }
  
      /**
       * Returns true if this SSA register is a "version 0"
       * register. All version 0 registers are assigned the first N register
       * numbers, where N is the count of original rop registers.
       *
       * @param ssaReg the SSA register in question
       * @return true if it is a version 0 register.
       */
      private boolean isVersionZeroRegister(int ssaReg) {
          return ssaReg < ropRegCount;
      }
  
      /**
       * Returns true if a and b are equal or are both null.
       *
       * @param a null-ok
       * @param b null-ok
       * @return Returns true if a and b are equal or are both null
       */
      private static boolean equalsHandlesNulls(Object a, Object b) {
          return a == b ||  (a != null && a.equals(b));
      }
  
      /**
       * Processes all insns in a block and renames their registers
       * as appropriate.
       */
      private class BlockRenamer implements SsaInsn.Visitor{
          /** {@code non-null;} block we're processing. */
          private final SsaBasicBlock block;
  
          /**
           * {@code non-null;} indexed by old register name. The current
           * top of the version stack as seen by this block. It's
           * initialized from the ending state of its dom parent,
           * updated as the block's instructions are processed, and then
           * copied to each one of its dom children.
           */
          private final RegisterSpec[] currentMapping;
  
          /**
           * contains the set of moves we need to keep to preserve local
           * var info. All other moves will be deleted.
           */
          private final HashSet<SsaInsn> movesToKeep;
  
          /**
           * maps the set of insns to replace after renaming is finished
           * on the block.
           */
          private final HashMap<SsaInsn, SsaInsn> insnsToReplace;
  
          private final RenamingMapper mapper;
  
          /**
           * Constructs a block renamer instance. Call {@code process}
           * to process.
           *
           * @param block {@code non-null;} block to process
           */
          BlockRenamer(final SsaBasicBlock block) {
              this.block = block;
              currentMapping = startsForBlocks[block.getIndex()];
              movesToKeep = new HashSet<SsaInsn>();
              insnsToReplace = new HashMap<SsaInsn, SsaInsn>();
              mapper =  new RenamingMapper();
  
              // We don't need our own start state anymore
              startsForBlocks[block.getIndex()] = null;
          }
  
          /**
           * Provides a register mapping between the old register space
           * and the current renaming mapping. The mapping is updated
           * as the current block's instructions are processed.
           */
          private class RenamingMapper extends RegisterMapper {
              public RenamingMapper() {
                  // This space intentionally left blank.
              }
  
              /** {@inheritDoc} */
              @Override
              public int getNewRegisterCount() {
                  return nextSsaReg;
              }
  
              /** {@inheritDoc} */
              @Override
              public RegisterSpec map(RegisterSpec registerSpec) {
                  if (registerSpec == null) return null;
  
                  int reg = registerSpec.getReg();
  
                  // For debugging: assert that the mapped types are compatible.
                  if (DEBUG) {
                      RegisterSpec newVersion = currentMapping[reg];
                      if (newVersion.getBasicType() != Type.BT_VOID
                              && registerSpec.getBasicFrameType()
                                  != newVersion.getBasicFrameType()) {
  
                          throw new RuntimeException(
                                  "mapping registers of incompatible types! "
                                  + registerSpec
                                  + " " + currentMapping[reg]);
                      }
                  }
  
                  return registerSpec.withReg(currentMapping[reg].getReg());
              }
          }
  
          /**
           * Renames all the variables in this block and inserts appriopriate
           * phis in successor blocks.
           */
          public void process() {
              /*
               * From Appel:
               *
               * Rename(n) =
               *   for each statement S in block n   // 'statement' in 'block'
               */
  
              block.forEachInsn(this);
  
              updateSuccessorPhis();
  
              // Delete all move insns in this block.
              ArrayList<SsaInsn> insns = block.getInsns();
              int szInsns = insns.size();
  
              for (int i = szInsns - 1; i >= 0 ; i--) {
                  SsaInsn insn = insns.get(i);
                  SsaInsn replaceInsn;
  
                  replaceInsn = insnsToReplace.get(insn);
  
                  if (replaceInsn != null) {
                      insns.set(i, replaceInsn);
                  } else if (insn.isNormalMoveInsn()
                          && !movesToKeep.contains(insn)) {
                      insns.remove(i);
                  }
              }
  
              // Store the start states for our dom children.
              boolean first = true;
              for (SsaBasicBlock child : block.getDomChildren()) {
                  if (child != block) {
                      // Don't bother duplicating the array for the first child.
                      RegisterSpec[] childStart = first ? currentMapping
                          : dupArray(currentMapping);
  
                      startsForBlocks[child.getIndex()] = childStart;
                      first = false;
                  }
              }
  
              // currentMapping is owned by a child now.
          }
  
          /**
           * Enforces a few contraints when a register mapping is added.
           *
           * <ol>
           * <li> Ensures that all new SSA registers specs in the mapping
           * table with the same register number are identical. In effect, once
           * an SSA register spec has received or lost a local variable name,
           * then every old-namespace register that maps to it should gain or
           * lose its local variable name as well.
           * <li> Records the local name associated with the
           * register so that a register is never associated with more than one
           * local.
           * <li> ensures that only one SSA register
           * at a time is considered to be associated with a local variable. When
           * {@code currentMapping} is updated and the newly added element
           * is named, strip that name from any other SSA registers.
           * </ol>
           *
           * @param ropReg {@code >= 0;} rop register number
           * @param ssaReg {@code non-null;} an SSA register that has just
           * been added to {@code currentMapping}
           */
          private void addMapping(int ropReg, RegisterSpec ssaReg) {
              int ssaRegNum = ssaReg.getReg();
              LocalItem ssaRegLocal = ssaReg.getLocalItem();
  
              currentMapping[ropReg] = ssaReg;
  
              /*
               * Ensure all SSA register specs with the same reg are identical.
               */
              for (int i = currentMapping.length - 1; i >= 0; i--) {
                  RegisterSpec cur = currentMapping[i];
  
                  if (ssaRegNum == cur.getReg()) {
                      currentMapping[i] = ssaReg;
                  }
              }
  
              // All further steps are for registers with local information.
              if (ssaRegLocal == null) {
                  return;
              }
  
              // Record that this SSA reg has been associated with a local.
              setNameForSsaReg(ssaReg);
  
              // Ensure that no other SSA regs are associated with this local.
              for (int i = currentMapping.length - 1; i >= 0; i--) {
                  RegisterSpec cur = currentMapping[i];
  
                  if (ssaRegNum != cur.getReg()
                          && ssaRegLocal.equals(cur.getLocalItem())) {
                      currentMapping[i] = cur.withLocalItem(null);
                  }
              }
          }
  
          /**
           * {@inheritDoc}
           *
           * Phi insns have their result registers renamed.
           */
          public void visitPhiInsn(PhiInsn phi) {
              /* don't process sources for phi's */
              processResultReg(phi);
          }
  
          /**
           * {@inheritDoc}
           *
           * Move insns are treated as a simple mapping operation, and
           * will later be removed unless they represent a local variable
           * assignment. If they represent a local variable assignement, they
           * are preserved.
           */
          public void visitMoveInsn(NormalSsaInsn insn) {
              /*
               * For moves: copy propogate the move if we can, but don't
               * if we need to preserve local variable info and the
               * result has a different name than the source.
               */
  
              RegisterSpec ropResult = insn.getResult();
              int ropResultReg = ropResult.getReg();
              int ropSourceReg = insn.getSources().get(0).getReg();
  
              insn.mapSourceRegisters(mapper);
              int ssaSourceReg = insn.getSources().get(0).getReg();
  
              LocalItem sourceLocal
                  = currentMapping[ropSourceReg].getLocalItem();
              LocalItem resultLocal = ropResult.getLocalItem();
  
              /*
               * A move from a register that's currently associated with a local
               * to one that will not be associated with a local does not need
               * to be preserved, but the local association should remain.
               * Hence, we inherit the sourceLocal where the resultLocal is null.
               */
  
              LocalItem newLocal
                  = (resultLocal == null) ? sourceLocal : resultLocal;
              LocalItem associatedLocal = getLocalForNewReg(ssaSourceReg);
  
              /*
               * If we take the new local, will only one local have ever
               * been associated with this SSA reg?
               */
              boolean onlyOneAssociatedLocal
                      = associatedLocal == null || newLocal == null
                      || newLocal.equals(associatedLocal);
  
              /*
               * If we're going to copy-propogate, then the ssa register
               * spec that's going to go into the mapping is made up of
               * the source register number mapped from above, the type
               * of the result, and the name either from the result (if
               * specified) or inherited from the existing mapping.
               *
               * The move source has incomplete type information in null
               * object cases, so the result type is used.
               */
              RegisterSpec ssaReg
                      = RegisterSpec.makeLocalOptional(
                          ssaSourceReg, ropResult.getType(), newLocal);
  
              if (!Optimizer.getPreserveLocals() || (onlyOneAssociatedLocal
                      && equalsHandlesNulls(newLocal, sourceLocal)) &&
                      threshold == 0) {
                  /*
                   * We don't have to keep this move to preserve local
                   * information. Either the name is the same, or the result
                   * register spec is unnamed.
                   */
  
                  addMapping(ropResultReg, ssaReg);
              } else if (onlyOneAssociatedLocal && sourceLocal == null &&
                      threshold == 0) {
                  /*
                   * The register was previously unnamed. This means that a
                   * local starts after it's first assignment in SSA form
                   */
  
                  RegisterSpecList ssaSources = RegisterSpecList.make(
                          RegisterSpec.make(ssaReg.getReg(),
                                  ssaReg.getType(), newLocal));
  
                  SsaInsn newInsn
                          = SsaInsn.makeFromRop(
                              new PlainInsn(Rops.opMarkLocal(ssaReg),
                              SourcePosition.NO_INFO, null, ssaSources),block);
  
                  insnsToReplace.put(insn, newInsn);
  
                  // Just map as above.
                  addMapping(ropResultReg, ssaReg);
              } else {
                  /*
                   * Do not copy-propogate, since the two registers have
                   * two different local-variable names.
                   */
                  processResultReg(insn);
  
                  movesToKeep.add(insn);
              }
          }
  
          /**
           * {@inheritDoc}
           *
           * All insns that are not move or phi insns have their source registers
           * mapped ot the current mapping. Their result registers are then
           * renamed to a new SSA register which is then added to the current
           * register mapping.
           */
          public void visitNonMoveInsn(NormalSsaInsn insn) {
              /* for each use of some variable X in S */
              insn.mapSourceRegisters(mapper);
  
              processResultReg(insn);
          }
  
          /**
           * Renames the result register of this insn and updates the
           * current register mapping. Does nothing if this insn has no result.
           * Applied to all non-move insns.
           *
           * @param insn insn to process.
           */
          void processResultReg(SsaInsn insn) {
              RegisterSpec ropResult = insn.getResult();
  
              if (ropResult == null) {
                  return;
              }
  
              int ropReg = ropResult.getReg();
              if (isBelowThresholdRegister(ropReg)) {
                  return;
              }
  
              insn.changeResultReg(nextSsaReg);
              addMapping(ropReg, insn.getResult());
  
              if (DEBUG) {
                  ssaRegToRopReg.add(ropReg);
              }
  
              nextSsaReg++;
          }
  
          /**
           * Updates the phi insns in successor blocks with operands based
           * on the current mapping of the rop register the phis represent.
           */
          private void updateSuccessorPhis() {
              PhiInsn.Visitor visitor = new PhiInsn.Visitor() {
                  public void visitPhiInsn (PhiInsn insn) {
                      int ropReg;
  
                      ropReg = insn.getRopResultReg();
                      if (isBelowThresholdRegister(ropReg)) {
                          return;
                      }
  
                      /*
                       * Never add a version 0 register as a phi
                       * operand. Version 0 registers represent the
                       * initial register state, and thus are never
                       * significant. Furthermore, the register liveness
                       * algorithm doesn't properly count them as "live
                       * in" at the beginning of the method.
                       */
  
                      RegisterSpec stackTop = currentMapping[ropReg];
                      if (!isVersionZeroRegister(stackTop.getReg())) {
                          insn.addPhiOperand(stackTop, block);
                      }
                  }
              };
  
              BitSet successors = block.getSuccessors();
              for (int i = successors.nextSetBit(0); i >= 0;
                      i = successors.nextSetBit(i + 1)) {
                  SsaBasicBlock successor = ssaMeth.getBlocks().get(i);
                  successor.forEachPhiInsn(visitor);
              }
          }
      }
  }
  