// Copyright (c) 2016, 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.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.CatchHandlers;
import com.android.tools.r8.ir.code.DominatorTree;
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 com.android.tools.r8.utils.InternalOptions;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class DeadCodeRemover {

  public static void removeDeadCode(
      IRCode code, CodeRewriter codeRewriter, InternalOptions options) {
    Queue<BasicBlock> worklist = new LinkedList<>();
    DominatorTree dominator = new DominatorTree(code);
    code.clearMarks();
    worklist.addAll(code.blocks);
    for (BasicBlock block = worklist.poll(); block != null; block = worklist.poll()) {
      if (block.isMarked()) {
        // Ignore marked blocks, as they are scheduled for removal.
        continue;
      }
      removeDeadInstructions(worklist, code, block, options);
      removeDeadPhis(worklist, block, options);
      removeUnneededCatchHandlers(worklist, block, dominator);
    }
    code.removeMarkedBlocks();
    assert code.isConsistentSSA();
    codeRewriter.rewriteMoveResult(code);
  }

  // Add the block from where the value originates to the worklist.
  private static void updateWorklist(Queue<BasicBlock> worklist, Value value) {
    BasicBlock block;
    if (value.isPhi()) {
      block = value.asPhi().getBlock();
    } else {
      block = value.definition.getBlock();
    }
    if (!block.isMarked()) {
      worklist.add(block);
    }
  }

  // Add all blocks from where the in/debug-values to the instruction originates.
  private static void updateWorklist(Queue<BasicBlock> worklist, Instruction instruction) {
    for (Value inValue : instruction.inValues()) {
      updateWorklist(worklist, inValue);
    }
    for (Value debugValue : instruction.getDebugValues()) {
      updateWorklist(worklist, debugValue);
    }
    Value previousLocalValue = instruction.getPreviousLocalValue();
    if (previousLocalValue != null) {
      updateWorklist(worklist, previousLocalValue);
    }
  }

  private static void removeDeadPhis(
      Queue<BasicBlock> worklist, BasicBlock block, InternalOptions options) {
    List<Phi> toRemove = new ArrayList<>();
    for (Phi phi : block.getPhis()) {
      if (phi.isDead(options)) {
        toRemove.add(phi);
        for (Value operand : phi.getOperands()) {
          operand.removePhiUser(phi);
          updateWorklist(worklist, operand);
        }
      }
    }
    if (!toRemove.isEmpty()) {
      List<Phi> newPhis = new ArrayList<>(block.getPhis().size() - toRemove.size());
      int toRemoveIndex = 0;
      List<Phi> phis = block.getPhis();
      int i = 0;
      for (; i < phis.size() && toRemoveIndex < toRemove.size(); i++) {
        Phi phi = phis.get(i);
        if (phi == toRemove.get(toRemoveIndex)) {
          toRemoveIndex++;
        } else {
          newPhis.add(phi);
        }
      }
      newPhis.addAll(phis.subList(i, phis.size()));
      block.setPhis(newPhis);
    }
  }

  private static void removeDeadInstructions(
      Queue<BasicBlock> worklist, IRCode code, BasicBlock block, InternalOptions options) {
    InstructionListIterator iterator = block.listIterator(block.getInstructions().size());
    while (iterator.hasPrevious()) {
      Instruction current = iterator.previous();
      // Remove unused invoke results.
      if (current.isInvoke()
          && current.outValue() != null
          && !current.outValue().isUsed()) {
        current.setOutValue(null);
      }
      // Never remove instructions that can have side effects, except for const-class.
      if (!current.canBeDeadCode(code, options)) {
        continue;
      }
      Value outValue = current.outValue();
      // Instructions with no out value cannot be dead code by the current definition
      // (unused out value). They typically side-effect input values or deals with control-flow.
      assert outValue != null;
      if (!outValue.isDead(options)) {
        continue;

      }
      updateWorklist(worklist, current);
      // All users will be removed for this instruction. Eagerly clear them so further inspection
      // of this instruction during dead code elimination will terminate here.
      outValue.clearUsers();
      iterator.remove();
    }
  }

  private static void removeUnneededCatchHandlers(
      Queue<BasicBlock> worklist, BasicBlock block, DominatorTree dominator) {
    if (block.hasCatchHandlers() && !block.canThrow()) {
      CatchHandlers<BasicBlock> handlers = block.getCatchHandlers();
      for (BasicBlock target : handlers.getUniqueTargets()) {
        for (BasicBlock unlinked : block.unlink(target, dominator)) {
          if (!unlinked.isMarked()) {
            Iterator<Instruction> iterator = unlinked.iterator();
            while (iterator.hasNext()) {
              updateWorklist(worklist, iterator.next());
            }
            unlinked.mark();
          }
        }
      }
    }
  }
}