/*
 * 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.LocalItem;
import com.android.jack.dx.rop.code.RegisterSpec;
import com.android.jack.dx.rop.code.RegisterSpecList;
import com.android.jack.dx.rop.type.Type;
import com.android.jack.dx.rop.type.TypeBearer;

import java.util.BitSet;
import java.util.List;

/**
 * Resolves the result types of phi instructions. When phi instructions
 * are inserted, their result types are set to BT_VOID (which is a nonsensical
 * type for a register) but must be resolve to a real type before converting
 * out of SSA form.<p>
 *
 * The resolve is done as an iterative merge of each phi's operand types.
 * Phi operands may be themselves be the result of unresolved phis,
 * and the algorithm tries to find the most-fit type (for example, if every
 * operand is the same constant value or the same local variable info, we want
 * that to be reflected).<p>
 *
 * This algorithm assumes a dead-code remover has already removed all
 * circular-only phis that may have been inserted.
 */
public class PhiTypeResolver {

  SsaMethod ssaMeth;
  /** indexed by register; all registers still defined by unresolved phis */
  private final BitSet worklist;

  /**
   * Resolves all phi types in the method
   * @param ssaMeth method to process
   */
  public static void process(SsaMethod ssaMeth) {
    new PhiTypeResolver(ssaMeth).run();
  }

  private PhiTypeResolver(SsaMethod ssaMeth) {
    this.ssaMeth = ssaMeth;
    worklist = new BitSet(ssaMeth.getRegCount());
  }

  /**
   * Runs the phi-type resolver.
   */
  private void run() {

    int regCount = ssaMeth.getRegCount();

    for (int reg = 0; reg < regCount; reg++) {
      SsaInsn definsn = ssaMeth.getDefinitionForRegister(reg);

      if (definsn != null && (definsn.getResult().getBasicType() == Type.BT_VOID)) {
        worklist.set(reg);
      }
    }

    int reg;
    while (0 <= (reg = worklist.nextSetBit(0))) {
      worklist.clear(reg);

      /*
       * definitions on the worklist have a type of BT_VOID, which
       * must have originated from a PhiInsn.
       */
      PhiInsn definsn = (PhiInsn) ssaMeth.getDefinitionForRegister(reg);

      if (resolveResultType(definsn)) {
        /*
         * If the result type has changed, re-resolve all phis
         * that use this.
         */

List<SsaInsn> useList = ssaMeth.getUseListForRegister(reg);

        int sz = useList.size();
        for (int i = 0; i < sz; i++) {
          SsaInsn useInsn = useList.get(i);
          RegisterSpec resultReg = useInsn.getResult();
          if (resultReg != null && useInsn instanceof PhiInsn) {
            worklist.set(resultReg.getReg());
          }
        }
      }
    }
  }

  /**
   * Returns true if a and b are equal, whether
   * or not either of them are null.
   * @param a
   * @param b
   * @return true if equal
   */
  private static boolean equalsHandlesNulls(LocalItem a, LocalItem b) {
    return (a == b) || ((a != null) && a.equals(b));
  }

  /**
   * Resolves the result of a phi insn based on its operands. The "void"
   * type, which is a nonsensical type for a register, is used for
   * registers defined by as-of-yet-unresolved phi operations.
   *
   * @return true if the result type changed, false if no change
   */
  boolean resolveResultType(PhiInsn insn) {
    insn.updateSourcesToDefinitions(ssaMeth);

    RegisterSpecList sources = insn.getSources();

    // Start by finding the first non-void operand
    RegisterSpec first = null;
    int firstIndex = -1;

    int szSources = sources.size();
    for (int i = 0; i < szSources; i++) {
      RegisterSpec rs = sources.get(i);

      if (rs.getBasicType() != Type.BT_VOID) {
        first = rs;
        firstIndex = i;
      }
    }

    if (first == null) {
      // All operands are void -- we're not ready to resolve yet
      return false;
    }

    LocalItem firstLocal = first.getLocalItem();
    TypeBearer mergedType = first.getType();
    boolean sameLocals = true;
    for (int i = 0; i < szSources; i++) {
      if (i == firstIndex) {
        continue;
      }

      RegisterSpec rs = sources.get(i);

      // Just skip void (unresolved phi results) for now
      if (rs.getBasicType() == Type.BT_VOID) {
        continue;
      }

      sameLocals = sameLocals && equalsHandlesNulls(firstLocal, rs.getLocalItem());

      mergedType = mergeType(mergedType, rs.getType());
    }

    TypeBearer newResultType;

    if (mergedType != null) {
      newResultType = mergedType;
    } else {
      StringBuilder sb = new StringBuilder();

      for (int i = 0; i < szSources; i++) {
        sb.append(sources.get(i).toString());
        sb.append(' ');
      }

      throw new RuntimeException("Couldn't map types in phi insn:" + sb);
    }

    LocalItem newLocal = sameLocals ? firstLocal : null;

    RegisterSpec result = insn.getResult();

    if ((result.getTypeBearer() == newResultType)
        && equalsHandlesNulls(newLocal, result.getLocalItem())) {
      return false;
    }

    insn.changeResultType(newResultType, newLocal);

    return true;
  }

  /**
   * Merges two frame types.
   *
   * @param ft1 {@code non-null;} a frame type
   * @param ft2 {@code non-null;} another frame type
   * @return {@code non-null;} the result of merging the two types
   */
  private static TypeBearer mergeType(TypeBearer ft1, TypeBearer ft2) {
    if ((ft1 == null) || ft1.equals(ft2)) {
      return ft1;
    } else if (ft2 == null) {
      return null;
    } else {
      Type type1 = ft1.getType();
      Type type2 = ft2.getType();

      if (type1 == type2) {
        return type1;
      } else if (type1.isReference() && type2.isReference()) {
        if (type1 == Type.KNOWN_NULL) {
          /*
           * A known-null merges with any other reference type to
           * be that reference type.
           */
          return type2;
        } else if (type2 == Type.KNOWN_NULL) {
          /*
           * The same as above, but this time it's type2 that's
           * the known-null.
           */
          return type1;
        } else if (type1.isArray() && type2.isArray()) {
          TypeBearer componentUnion = mergeType(type1.getComponentType(), type2.getComponentType());
          if (componentUnion == null) {
            /*
             * At least one of the types is a primitive type,
             * so the merged result is just Object.
             */
            return Type.OBJECT;
          }
          return ((Type) componentUnion).getArrayType();
        } else {
          /*
           * All other unequal reference types get merged to be
           * Object in this phase. This is fine here, but it
           * won't be the right thing to do in the verifier.
           */
          return Type.OBJECT;
        }
      } else if (type1.isIntlike() && type2.isIntlike()) {
        /*
         * Merging two non-identical int-like types results in
         * the type int.
         */
        return Type.INT;
      } else {
        return null;
      }
    }
  }

}