// Copyright (c) 2018, 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.AppInfo;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.DominatorTree;
import com.android.tools.r8.ir.code.FieldInstruction;
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.Phi;
import com.android.tools.r8.ir.code.Value;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Eliminate redundant field loads.
 *
 * <p>Simple algorithm that goes through all blocks in one pass in dominator order and propagates
 * active field sets across control-flow edges where the target has only one predecessor.
 */
// TODO(ager): Evaluate speed/size for computing active field sets in a fixed-point computation.
public class RedundantFieldLoadElimination {

  private final AppView<? extends AppInfo> appView;
  private final DexEncodedMethod method;
  private final IRCode code;
  private final DominatorTree dominatorTree;

  // Maps keeping track of fields that have an already loaded value at basic block entry.
  private final HashMap<BasicBlock, HashMap<FieldAndObject, Instruction>>
      activeInstanceFieldsAtEntry = new HashMap<>();
  private final HashMap<BasicBlock, HashMap<DexField, Instruction>> activeStaticFieldsAtEntry =
      new HashMap<>();

  // Maps keeping track of fields with already loaded values for the current block during
  // elimination.
  private HashMap<FieldAndObject, Instruction> activeInstanceFields;
  private HashMap<DexField, Instruction> activeStaticFields;

  public RedundantFieldLoadElimination(AppView<? extends AppInfo> appView, IRCode code) {
    this.appView = appView;
    this.method = code.method;
    this.code = code;
    dominatorTree = new DominatorTree(code);
  }

  private static class FieldAndObject {
    private final DexField field;
    private final Value object;

    private FieldAndObject(DexField field, Value receiver) {
      this.field = field;
      this.object = receiver;
    }

    @Override
    public int hashCode() {
      return field.hashCode() * 7 + object.hashCode();
    }

    @Override
    public boolean equals(Object other) {
      if (!(other instanceof FieldAndObject)) {
        return false;
      }
      FieldAndObject o = (FieldAndObject) other;
      return o.object == object && o.field == field;
    }
  }

  private boolean couldBeVolatile(DexField field) {
    if (!appView.enableWholeProgramOptimizations()
        && field.holder != method.method.holder) {
      return true;
    }
    DexEncodedField definition = appView.definitionFor(field);
    return definition == null || definition.accessFlags.isVolatile();
  }

  public void run() {
    for (BasicBlock block : dominatorTree.getSortedBlocks()) {
      activeInstanceFields =
          activeInstanceFieldsAtEntry.containsKey(block)
              ? activeInstanceFieldsAtEntry.get(block)
              : new HashMap<>();
      activeStaticFields =
          activeStaticFieldsAtEntry.containsKey(block)
              ? activeStaticFieldsAtEntry.get(block)
              : new HashMap<>();
      InstructionListIterator it = block.listIterator();
      while (it.hasNext()) {
        Instruction instruction = it.next();
        if (instruction.isFieldInstruction()) {
          DexField field = instruction.asFieldInstruction().getField();
          if (instruction.isInstancePut() || instruction.isStaticPut()) {
            killActiveFields(instruction.asFieldInstruction());
          } else if (couldBeVolatile(field)) {
            assert instruction.isInstanceGet() || instruction.isStaticGet();
            killAllActiveFields();
          } else {
            assert instruction.isInstanceGet() || instruction.isStaticGet();
            assert !couldBeVolatile(field);
            if (instruction.isInstanceGet() && !instruction.outValue().hasLocalInfo()) {
              Value object = instruction.asInstanceGet().object();
              // Values from NonNull instructions will always be replaced with their original
              // value before code is generated.
              if (!object.isPhi() && object.definition.isNonNull()) {
                object = object.definition.asNonNull().src();
              }
              FieldAndObject fieldAndObject = new FieldAndObject(field, object);
              if (activeInstanceFields.containsKey(fieldAndObject)) {
                Instruction active = activeInstanceFields.get(fieldAndObject);
                eliminateRedundantRead(it, instruction, active);
              } else {
                activeInstanceFields.put(fieldAndObject, instruction);
              }
            } else if (instruction.isStaticGet() && !instruction.outValue().hasLocalInfo()) {
              if (activeStaticFields.containsKey(field)) {
                Instruction active = activeStaticFields.get(field);
                eliminateRedundantRead(it, instruction, active);
              } else {
                // A field get on a different class can cause <clinit> to run and change static
                // field values.
                killActiveFields(instruction.asFieldInstruction());
                activeStaticFields.put(field, instruction);
              }
            }
          }
        }
        if ((instruction.isMonitor() && instruction.asMonitor().isEnter())
            || instruction.isInvokeMethod()) {
          killAllActiveFields();
        }
      }
      propagateActiveFieldsFrom(block);
    }
    assert code.isConsistentSSA();
  }

  private void propagateActiveFieldsFrom(BasicBlock block) {
    for (BasicBlock successor : block.getSuccessors()) {
      // Allow propagation across exceptional edges, just be careful not to propagate if the
      // throwing instruction is a field instruction.
      if (successor.getPredecessors().size() == 1) {
        if (block.hasCatchSuccessor(successor)) {
          Instruction exceptionalExit = block.exceptionalExit();
          if (exceptionalExit != null && exceptionalExit.isFieldInstruction()) {
            killActiveFieldsForExceptionalExit(exceptionalExit.asFieldInstruction());
          }
        }
        assert !activeInstanceFieldsAtEntry.containsKey(successor);
        activeInstanceFieldsAtEntry.put(successor, new HashMap<>(activeInstanceFields));
        assert !activeStaticFieldsAtEntry.containsKey(successor);
        activeStaticFieldsAtEntry.put(successor, new HashMap<>(activeStaticFields));
      }
    }
  }

  private void killAllActiveFields() {
    activeInstanceFields.clear();
    activeStaticFields.clear();
  }

  private void killActiveFields(FieldInstruction instruction) {
    DexField field = instruction.getField();
    if (instruction.isInstancePut()) {
      // Remove all the field/object pairs that refer to this field to make sure
      // that we are conservative.
      List<FieldAndObject> keysToRemove = new ArrayList<>();
      for (FieldAndObject key : activeInstanceFields.keySet()) {
        if (key.field == field) {
          keysToRemove.add(key);
        }
      }
      keysToRemove.forEach((k) -> activeInstanceFields.remove(k));
    } else if (instruction.isInstanceGet()) {
      Value object = instruction.asInstanceGet().object();
      FieldAndObject fieldAndObject = new FieldAndObject(field, object);
      activeInstanceFields.remove(fieldAndObject);
    } else if (instruction.isStaticPut()) {
      if (field.holder != code.method.method.holder) {
        // Accessing a static field on a different object could cause <clinit> to run which
        // could modify any static field on any other object.
        activeStaticFields.clear();
      } else {
        activeStaticFields.remove(field);
      }
    } else if (instruction.isStaticGet()) {
      if (field.holder != code.method.method.holder) {
        // Accessing a static field on a different object could cause <clinit> to run which
        // could modify any static field on any other object.
        activeStaticFields.clear();
      }
    }
  }

  // If a field get instruction throws an exception it did not have an effect on the
  // value of the field. Therefore, when propagating across exceptional edges for a
  // field get instruction we have to exclude that field from the set of known
  // field values.
  private void killActiveFieldsForExceptionalExit(FieldInstruction instruction) {
    DexField field = instruction.getField();
    if (instruction.isInstanceGet()) {
      Value object = instruction.asInstanceGet().object();
      FieldAndObject fieldAndObject = new FieldAndObject(field, object);
      activeInstanceFields.remove(fieldAndObject);
    } else if (instruction.isStaticGet()) {
      activeStaticFields.remove(field);
    }
  }

  private void eliminateRedundantRead(
      InstructionListIterator it, Instruction redundant, Instruction active) {
    redundant.outValue().replaceUsers(active.outValue());
    it.removeOrReplaceByDebugLocalRead();
    active.outValue().uniquePhiUsers().forEach(Phi::removeTrivialPhi);
  }
}