/*
 * 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.android.jack.dx.ssa;

import com.android.jack.dx.rop.code.RegisterSpec;
import com.android.jack.dx.rop.code.RopMethod;
import com.android.jack.dx.util.IntIterator;

import java.util.ArrayList;
import java.util.BitSet;

/**
 * Converts ROP methods to SSA Methods
 */
public class SsaConverter {
  public static final boolean DEBUG = false;

  /**
   * Returns an SSA representation, edge-split and with phi
   * functions placed.
   *
   * @param rmeth input
   * @param paramWidth the total width, in register-units, of the method's
   * parameters
   * @param isStatic {@code true} if this method has no {@code this}
   * pointer argument
   * @return output in SSA form
   */
  public static SsaMethod convertToSsaMethod(RopMethod rmeth, int paramWidth, boolean isStatic) {
    SsaMethod result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);

    edgeSplit(result);

    LocalVariableInfo localInfo = LocalVariableExtractor.extract(result);

    placePhiFunctions(result, localInfo, 0);
    new SsaRenamer(result).run();

    /*
     * The exit block, added here, is not considered for edge splitting
     * or phi placement since no actual control flows to it.
     */
    result.makeExitBlock();

    return result;
  }

  /**
   * Updates an SSA representation, placing phi functions and renaming all
   * registers above a certain threshold number.
   *
   * @param ssaMeth input
   * @param threshold registers below this number are unchanged
   */
  public static void updateSsaMethod(SsaMethod ssaMeth, int threshold) {
    LocalVariableInfo localInfo = LocalVariableExtractor.extract(ssaMeth);
    placePhiFunctions(ssaMeth, localInfo, threshold);
    new SsaRenamer(ssaMeth, threshold).run();
  }

  /**
   * Returns an SSA represention with only the edge-splitter run.
   *
   * @param rmeth method to process
   * @param paramWidth width of all arguments in the method
   * @param isStatic {@code true} if this method has no {@code this}
   * pointer argument
   * @return an SSA represention with only the edge-splitter run
   */
  public static SsaMethod testEdgeSplit(RopMethod rmeth, int paramWidth, boolean isStatic) {
    SsaMethod result;

    result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);

    edgeSplit(result);
    return result;
  }

  /**
   * Returns an SSA represention with only the steps through the
   * phi placement run.
   *
   * @param rmeth method to process
   * @param paramWidth width of all arguments in the method
   * @param isStatic {@code true} if this method has no {@code this}
   * pointer argument
   * @return an SSA represention with only the edge-splitter run
   */
  public static SsaMethod testPhiPlacement(RopMethod rmeth, int paramWidth, boolean isStatic) {
    SsaMethod result;

    result = SsaMethod.newFromRopMethod(rmeth, paramWidth, isStatic);

    edgeSplit(result);

    LocalVariableInfo localInfo = LocalVariableExtractor.extract(result);

    placePhiFunctions(result, localInfo, 0);
    return result;
  }

  /**
   * See Appel section 19.1:
   *
   * Converts CFG into "edge-split" form, such that each node either a
   * unique successor or unique predecessor.<p>
   *
   * In addition, the SSA form we use enforces a further constraint,
   * requiring each block with a final instruction that returns a
   * value to have a primary successor that has no other
   * predecessor. This ensures move statements can always be
   * inserted correctly when phi statements are removed.
   *
   * @param result method to process
   */
  private static void edgeSplit(SsaMethod result) {
    edgeSplitPredecessors(result);
    edgeSplitMoveExceptionsAndResults(result);
    edgeSplitSuccessors(result);
  }

  /**
   * Inserts Z nodes as new predecessors for every node that has multiple
   * successors and multiple predecessors.
   *
   * @param result {@code non-null;} method to process
   */
  private static void edgeSplitPredecessors(SsaMethod result) {
    ArrayList<SsaBasicBlock> blocks = result.getBlocks();

    /*
     * New blocks are added to the end of the block list during
     * this iteration.
     */
    for (int i = blocks.size() - 1; i >= 0; i--) {
      SsaBasicBlock block = blocks.get(i);
      if (nodeNeedsUniquePredecessor(block)) {
        block.insertNewPredecessor();
      }
    }
  }

  /**
   * @param block {@code non-null;} block in question
   * @return {@code true} if this node needs to have a unique
   * predecessor created for it
   */
  private static boolean nodeNeedsUniquePredecessor(SsaBasicBlock block) {
    /*
     * Any block with that has both multiple successors and multiple
     * predecessors needs a new predecessor node.
     */

int countPredecessors = block.getPredecessors().cardinality();
    int countSuccessors = block.getSuccessors().cardinality();

    return (countPredecessors > 1 && countSuccessors > 1);
  }

  /**
   * In ROP form, move-exception must occur as the first insn in a block
   * immediately succeeding the insn that could thrown an exception.
   * We may need room to insert move insns later, so make sure to split
   * any block that starts with a move-exception such that there is a
   * unique move-exception block for each predecessor.
   *
   * @param ssaMeth method to process
   */
  private static void edgeSplitMoveExceptionsAndResults(SsaMethod ssaMeth) {
    ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks();

    /*
     * New blocks are added to the end of the block list during
     * this iteration.
     */
    for (int i = blocks.size() - 1; i >= 0; i--) {
      SsaBasicBlock block = blocks.get(i);

      /*
       * Any block that starts with a move-exception and has more than
       * one predecessor...
       */
      if (!block.isExitBlock() && block.getPredecessors().cardinality() > 1
          && block.getInsns().get(0).isMoveException()) {

        // block.getPredecessors() is changed in the loop below.
        BitSet preds = (BitSet) block.getPredecessors().clone();
        for (int j = preds.nextSetBit(0); j >= 0; j = preds.nextSetBit(j + 1)) {
          SsaBasicBlock predecessor = blocks.get(j);
          SsaBasicBlock zNode = predecessor.insertNewSuccessor(block);

          /*
           * Make sure to place the move-exception as the
           * first insn.
           */
          zNode.getInsns().add(0, block.getInsns().get(0).clone());
        }

        // Remove the move-exception from the original block.
        block.getInsns().remove(0);
      }
    }
  }

  /**
   * Inserts Z nodes for every node that needs a new
   * successor.
   *
   * @param result {@code non-null;} method to process
   */
  private static void edgeSplitSuccessors(SsaMethod result) {
    ArrayList<SsaBasicBlock> blocks = result.getBlocks();

    /*
     * New blocks are added to the end of the block list during
     * this iteration.
     */
    for (int i = blocks.size() - 1; i >= 0; i--) {
      SsaBasicBlock block = blocks.get(i);

      // Successors list is modified in loop below.
      BitSet successors = (BitSet) block.getSuccessors().clone();
      for (int j = successors.nextSetBit(0); j >= 0; j = successors.nextSetBit(j + 1)) {

        SsaBasicBlock succ = blocks.get(j);

        if (needsNewSuccessor(block, succ)) {
          block.insertNewSuccessor(succ);
        }
      }
    }
  }

  /**
   * Returns {@code true} if block and successor need a Z-node
   * between them. Presently, this is {@code true} if the final
   * instruction has any sources or results and the current
   * successor block has more than one predecessor.
   *
   * @param block predecessor node
   * @param succ successor node
   * @return {@code true} if a Z node is needed
   */
  private static boolean needsNewSuccessor(SsaBasicBlock block, SsaBasicBlock succ) {
    ArrayList<SsaInsn> insns = block.getInsns();
    SsaInsn lastInsn = insns.get(insns.size() - 1);

    return ((lastInsn.getResult() != null) || (lastInsn.getSources().size() > 0))
        && succ.getPredecessors().cardinality() > 1;
  }

  /**
   * See Appel algorithm 19.6:
   *
   * Place Phi functions in appropriate locations.
   *
   * @param ssaMeth {@code non-null;} method to process.
   * Modifications are made in-place.
   * @param localInfo {@code non-null;} local variable info, used
   * when placing phis
   * @param threshold registers below this number are ignored
   */
  private static void placePhiFunctions(SsaMethod ssaMeth, LocalVariableInfo localInfo,
      int threshold) {
    ArrayList<SsaBasicBlock> ssaBlocks;
    int regCount;
    int blockCount;

    ssaBlocks = ssaMeth.getBlocks();
    blockCount = ssaBlocks.size();
    regCount = ssaMeth.getRegCount() - threshold;

    DomFront df = new DomFront(ssaMeth);
    DomFront.DomInfo[] domInfos = df.run();

    // Bit set of registers vs block index "definition sites"
    BitSet[] defsites = new BitSet[regCount];

    // Bit set of registers vs block index "phi placement sites"
    BitSet[] phisites = new BitSet[regCount];

    for (int i = 0; i < regCount; i++) {
      defsites[i] = new BitSet(blockCount);
      phisites[i] = new BitSet(blockCount);
    }

    /*
     * For each register, build a set of all basic blocks where
     * containing an assignment to that register.
     */
    for (int bi = 0, s = ssaBlocks.size(); bi < s; bi++) {
      SsaBasicBlock b = ssaBlocks.get(bi);

      for (SsaInsn insn : b.getInsns()) {
        RegisterSpec rs = insn.getResult();

        if (rs != null && rs.getReg() - threshold >= 0) {
          defsites[rs.getReg() - threshold].set(bi);
        }
      }
    }

    if (DEBUG) {
      System.out.println("defsites");

      for (int i = 0; i < regCount; i++) {
        StringBuilder sb = new StringBuilder();
        sb.append('v').append(i).append(": ");
        sb.append(defsites[i].toString());
        System.out.println(sb);
      }
    }

    BitSet worklist;

    /*
     * For each register, compute all locations for phi placement
     * based on dominance-frontier algorithm.
     */
    for (int reg = 0, s = regCount; reg < s; reg++) {
      int workBlockIndex;

      /* Worklist set starts out with each node where reg is assigned. */

worklist =
          (BitSet) (defsites[reg].clone());

      while (0 <= (workBlockIndex = worklist.nextSetBit(0))) {
        worklist.clear(workBlockIndex);
        IntIterator dfIterator = domInfos[workBlockIndex].dominanceFrontiers.iterator();

        while (dfIterator.hasNext()) {
          int dfBlockIndex = dfIterator.next();

          if (!phisites[reg].get(dfBlockIndex)) {
            phisites[reg].set(dfBlockIndex);

            int tReg = reg + threshold;
            RegisterSpec rs = localInfo.getStarts(dfBlockIndex).get(tReg);

            if (rs == null) {
              ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(tReg);
            } else {
              ssaBlocks.get(dfBlockIndex).addPhiInsnForReg(rs);
            }

            if (!defsites[reg].get(dfBlockIndex)) {
              worklist.set(dfBlockIndex);
            }
          }
        }
      }
    }

    if (DEBUG) {
      System.out.println("phisites");

      for (int i = 0; i < regCount; i++) {
        StringBuilder sb = new StringBuilder();
        sb.append('v').append(i).append(": ");
        sb.append(phisites[i].toString());
        System.out.println(sb);
      }
    }
  }
}