// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.optimize;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.ConstClass;
import com.android.tools.r8.ir.code.ConstInstruction;
import com.android.tools.r8.ir.code.ConstNumber;
import com.android.tools.r8.ir.code.ConstString;
import com.android.tools.r8.ir.code.DexItemBasedConstString;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.logging.Log;
import com.android.tools.r8.utils.StringUtils;
import it.unimi.dsi.fastutil.Hash.Strategy;
import it.unimi.dsi.fastutil.objects.Object2IntArrayMap;
import it.unimi.dsi.fastutil.objects.Object2IntMap;
import it.unimi.dsi.fastutil.objects.Object2ObjectLinkedOpenCustomHashMap;
import it.unimi.dsi.fastutil.objects.Object2ObjectSortedMap.FastSortedEntrySet;
import java.util.ArrayList;
import java.util.List;

/**
 * Canonicalize constants.
 */
public class ConstantCanonicalizer {
  // Threshold to limit the number of constant canonicalization.
  private static final int MAX_CANONICALIZED_CONSTANT = 22;

  private int numberOfConstNumberCanonicalization = 0;
  private int numberOfConstStringCanonicalization = 0;
  private int numberOfDexItemBasedConstStringCanonicalization = 0;
  private int numberOfConstClassCanonicalization = 0;
  private final Object2IntMap<Long> histogramOfCanonicalizationCandidatesPerMethod;

  public ConstantCanonicalizer() {
    if (Log.ENABLED) {
      histogramOfCanonicalizationCandidatesPerMethod = new Object2IntArrayMap<>();
    } else {
      histogramOfCanonicalizationCandidatesPerMethod = null;
    }
  }

  public void logResults() {
    assert Log.ENABLED;
    Log.info(getClass(),
        "# const-number canonicalization: %s", numberOfConstNumberCanonicalization);
    Log.info(getClass(),
        "# const-string canonicalization: %s", numberOfConstStringCanonicalization);
    Log.info(getClass(),
        "# item-based const-string canonicalization: %s",
        numberOfDexItemBasedConstStringCanonicalization);
    Log.info(getClass(),
        "# const-class canonicalization: %s", numberOfConstClassCanonicalization);
    assert histogramOfCanonicalizationCandidatesPerMethod != null;
    Log.info(getClass(), "------ histogram of constant canonicalization candidates ------");
    histogramOfCanonicalizationCandidatesPerMethod.forEach((length, count) -> {
      Log.info(getClass(),
          "%s: %s (%s)", length, StringUtils.times("*", Math.min(count, 53)), count);
    });
  }

  public void canonicalize(AppView<?> appView, IRCode code) {
    Object2ObjectLinkedOpenCustomHashMap<ConstInstruction, List<Value>> valuesDefinedByConstant =
        new Object2ObjectLinkedOpenCustomHashMap<>(
            new Strategy<ConstInstruction>() {
              @Override
              public int hashCode(ConstInstruction constInstruction) {
                assert constInstruction.isConstNumber()
                    || constInstruction.isConstString()
                    || constInstruction.isDexItemBasedConstString()
                    || constInstruction.isConstClass();
                if (constInstruction.isConstNumber()) {
                  return Long.hashCode(constInstruction.asConstNumber().getRawValue())
                      + 13 * constInstruction.outType().hashCode();
                }
                if (constInstruction.isConstString()) {
                  return constInstruction.asConstString().getValue().hashCode();
                }
                if (constInstruction.isDexItemBasedConstString()) {
                  return constInstruction.asDexItemBasedConstString().getItem().hashCode();
                }
                return constInstruction.asConstClass().getValue().hashCode();
              }

              @Override
              public boolean equals(ConstInstruction a, ConstInstruction b) {
                // Constants with local info must not be canonicalized and must be filtered.
                assert a == null || !a.outValue().hasLocalInfo();
                assert b == null || !b.outValue().hasLocalInfo();
                return a == b
                    || (a != null && b != null && a.identicalNonValueNonPositionParts(b));
              }
            });

    // Collect usages of constants that can be canonicalized.
    for (Instruction current : code.instructions()) {
      // Interested in ConstNumber, (DexItemBased)?ConstString, and ConstClass
      if (!current.isConstNumber()
          && !current.isConstString()
          && !current.isDexItemBasedConstString()
          && !current.isConstClass()) {
        continue;
      }
      // Do not canonicalize ConstClass that may have side effects. Its original instructions
      // will not be removed by dead code remover due to the side effects.
      if (current.isConstClass()
          && current.instructionMayHaveSideEffects(appView, code.method.method.holder)) {
        continue;
      }
      // Do not canonicalize ConstString instructions if there are monitor operations in the code.
      // That could lead to unbalanced locking and could lead to situations where OOM exceptions
      // could leave a synchronized method without unlocking the monitor.
      if ((current.isConstString() || current.isDexItemBasedConstString())
          && code.metadata().mayHaveMonitorInstruction()) {
        continue;
      }
      // Constants with local info must not be canonicalized and must be filtered.
      if (current.outValue().hasLocalInfo()) {
        continue;
      }
      // Constants that are used by invoke range are not canonicalized to be compliant with the
      // optimization splitRangeInvokeConstant that gives the register allocator more freedom in
      // assigning register to ranged invokes which can greatly reduce the number of register
      // needed (and thereby code size as well). Thus no need to do a transformation that should
      // be removed later by another optimization.
      if (constantUsedByInvokeRange(current.asConstInstruction())) {
        continue;
      }
      List<Value> oldValuesDefinedByConstant =
          valuesDefinedByConstant.computeIfAbsent(
              current.asConstInstruction(), k -> new ArrayList<>());
      oldValuesDefinedByConstant.add(current.outValue());
    }

    if (valuesDefinedByConstant.isEmpty()) {
      return;
    }

    // Double-check the entry block does not have catch handlers.
    // Otherwise, we need to split it before moving canonicalized const-string, which may throw.
    assert !code.entryBlock().hasCatchHandlers();
    final Position firstNonNonePosition = code.findFirstNonNonePosition();
    FastSortedEntrySet<ConstInstruction, List<Value>> entries =
        valuesDefinedByConstant.object2ObjectEntrySet();
    // Sort the most frequently used constant first and exclude constant use only one time, such
    // as the {@code MAX_CANONICALIZED_CONSTANT} will be canonicalized into the entry block.
    if (Log.ENABLED && Log.isLoggingEnabledFor(ConstantCanonicalizer.class)) {
      Long numOfCandidates = entries.stream().filter(a -> a.getValue().size() > 1).count();
      synchronized (histogramOfCanonicalizationCandidatesPerMethod) {
        int count = histogramOfCanonicalizationCandidatesPerMethod.getOrDefault(numOfCandidates, 0);
        histogramOfCanonicalizationCandidatesPerMethod.put(numOfCandidates, count + 1);
      }
    }
    entries.stream()
        .filter(a -> a.getValue().size() > 1)
        .sorted((a, b) -> Integer.compare(b.getValue().size(), a.getValue().size()))
        .limit(MAX_CANONICALIZED_CONSTANT)
        .forEach((entry) -> {
          ConstInstruction canonicalizedConstant = entry.getKey().asConstInstruction();
          assert canonicalizedConstant.isConstNumber()
              || canonicalizedConstant.isConstString()
              || canonicalizedConstant.isDexItemBasedConstString()
              || canonicalizedConstant.isConstClass();
          ConstInstruction newConst;
          if (canonicalizedConstant.isConstNumber()) {
            if (Log.ENABLED) {
              numberOfConstNumberCanonicalization++;
            }
            newConst = ConstNumber.copyOf(code, canonicalizedConstant.asConstNumber());
          } else if (canonicalizedConstant.isConstString()) {
            if (Log.ENABLED) {
              numberOfConstStringCanonicalization++;
            }
            newConst = ConstString.copyOf(code, canonicalizedConstant.asConstString());
          } else if (canonicalizedConstant.isDexItemBasedConstString()) {
            if (Log.ENABLED) {
              numberOfDexItemBasedConstStringCanonicalization++;
            }
            newConst = DexItemBasedConstString.copyOf(
                code, canonicalizedConstant.asDexItemBasedConstString());
          } else {
            if (Log.ENABLED) {
              numberOfConstClassCanonicalization++;
            }
            newConst = ConstClass.copyOf(code, canonicalizedConstant.asConstClass());
          }
          newConst.setPosition(firstNonNonePosition);
          insertCanonicalizedConstant(code, newConst);
          for (Value outValue : entry.getValue()) {
            outValue.replaceUsers(newConst.outValue());
          }
        });

    code.removeAllTrivialPhis();
    assert code.isConsistentSSA();
  }

  private static void insertCanonicalizedConstant(
      IRCode code, ConstInstruction canonicalizedConstant) {
    BasicBlock entryBlock = code.entryBlock();
    // Insert the constant instruction at the start of the block right after the argument
    // instructions. It is important that the const instruction is put before any instruction
    // that can throw exceptions (since the value could be used on the exceptional edge).
    InstructionListIterator it = entryBlock.listIterator(code);
    while (it.hasNext()) {
      if (!it.next().isArgument()) {
        it.previous();
        break;
      }
    }
    it.add(canonicalizedConstant);
  }

  private static boolean constantUsedByInvokeRange(ConstInstruction constant) {
    for (Instruction user : constant.outValue().uniqueUsers()) {
      if (user.isInvoke() && user.asInvoke().requiredArgumentRegisters() > 5) {
        return true;
      }
    }
    return false;
  }
}