// Copyright (c) 2017 Google Inc.
//
// 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.

// This file implements conditional constant propagation as described in
//
//      Constant propagation with conditional branches,
//      Wegman and Zadeck, ACM TOPLAS 13(2):181-210.

#include "source/opt/ccp_pass.h"

#include <algorithm>
#include <limits>

#include "source/opt/fold.h"
#include "source/opt/function.h"
#include "source/opt/module.h"
#include "source/opt/propagator.h"

namespace spvtools {
namespace opt {

namespace {

// This SSA id is never defined nor referenced in the IR.  It is a special ID
// which represents varying values.  When an ID is found to have a varying
// value, its entry in the |values_| table maps to kVaryingSSAId.
const uint32_t kVaryingSSAId = std::numeric_limits<uint32_t>::max();

}  // namespace

bool CCPPass::IsVaryingValue(uint32_t id) const { return id == kVaryingSSAId; }

SSAPropagator::PropStatus CCPPass::MarkInstructionVarying(Instruction* instr) {
  assert(instr->result_id() != 0 &&
         "Instructions with no result cannot be marked varying.");
  values_[instr->result_id()] = kVaryingSSAId;
  return SSAPropagator::kVarying;
}

SSAPropagator::PropStatus CCPPass::VisitPhi(Instruction* phi) {
  uint32_t meet_val_id = 0;

  // Implement the lattice meet operation. The result of this Phi instruction is
  // interesting only if the meet operation over arguments coming through
  // executable edges yields the same constant value.
  for (uint32_t i = 2; i < phi->NumOperands(); i += 2) {
    if (!propagator_->IsPhiArgExecutable(phi, i)) {
      // Ignore arguments coming through non-executable edges.
      continue;
    }
    uint32_t phi_arg_id = phi->GetSingleWordOperand(i);
    auto it = values_.find(phi_arg_id);
    if (it != values_.end()) {
      // We found an argument with a constant value.  Apply the meet operation
      // with the previous arguments.
      if (it->second == kVaryingSSAId) {
        // The "constant" value is actually a placeholder for varying. Return
        // varying for this phi.
        return MarkInstructionVarying(phi);
      } else if (meet_val_id == 0) {
        // This is the first argument we find.  Initialize the result to its
        // constant value id.
        meet_val_id = it->second;
      } else if (it->second == meet_val_id) {
        // The argument is the same constant value already computed. Continue
        // looking.
        continue;
      } else {
        // We either found a varying value, or another constant value different
        // from the previous computed meet value.  This Phi will never be
        // constant.
        return MarkInstructionVarying(phi);
      }
    } else {
      // The incoming value has no recorded value and is therefore not
      // interesting. A not interesting value joined with any other value is the
      // other value.
      continue;
    }
  }

  // If there are no incoming executable edges, the meet ID will still be 0. In
  // that case, return not interesting to evaluate the Phi node again.
  if (meet_val_id == 0) {
    return SSAPropagator::kNotInteresting;
  }

  // All the operands have the same constant value represented by |meet_val_id|.
  // Set the Phi's result to that value and declare it interesting.
  values_[phi->result_id()] = meet_val_id;
  return SSAPropagator::kInteresting;
}

uint32_t CCPPass::ComputeLatticeMeet(Instruction* instr, uint32_t val2) {
  // Given two values val1 and val2, the meet operation in the constant
  // lattice uses the following rules:
  //
  // meet(val1, UNDEFINED) = val1
  // meet(val1, VARYING)   = VARYING
  // meet(val1, val2)      = val1     if val1 == val2
  // meet(val1, val2)      = VARYING  if val1 != val2
  //
  // When two different values meet, the result is always varying because CCP
  // does not allow lateral transitions in the lattice.  This prevents
  // infinite cycles during propagation.
  auto val1_it = values_.find(instr->result_id());
  if (val1_it == values_.end()) {
    return val2;
  }

  uint32_t val1 = val1_it->second;
  if (IsVaryingValue(val1)) {
    return val1;
  } else if (IsVaryingValue(val2)) {
    return val2;
  } else if (val1 != val2) {
    return kVaryingSSAId;
  }
  return val2;
}

SSAPropagator::PropStatus CCPPass::VisitAssignment(Instruction* instr) {
  assert(instr->result_id() != 0 &&
         "Expecting an instruction that produces a result");

  // If this is a copy operation, and the RHS is a known constant, assign its
  // value to the LHS.
  if (instr->opcode() == SpvOpCopyObject) {
    uint32_t rhs_id = instr->GetSingleWordInOperand(0);
    auto it = values_.find(rhs_id);
    if (it != values_.end()) {
      if (IsVaryingValue(it->second)) {
        return MarkInstructionVarying(instr);
      } else {
        uint32_t new_val = ComputeLatticeMeet(instr, it->second);
        values_[instr->result_id()] = new_val;
        return IsVaryingValue(new_val) ? SSAPropagator::kVarying
                                       : SSAPropagator::kInteresting;
      }
    }
    return SSAPropagator::kNotInteresting;
  }

  // Instructions with a RHS that cannot produce a constant are always varying.
  if (!instr->IsFoldable()) {
    return MarkInstructionVarying(instr);
  }

  // See if the RHS of the assignment folds into a constant value.
  auto map_func = [this](uint32_t id) {
    auto it = values_.find(id);
    if (it == values_.end() || IsVaryingValue(it->second)) {
      return id;
    }
    return it->second;
  };
  Instruction* folded_inst =
      context()->get_instruction_folder().FoldInstructionToConstant(instr,
                                                                    map_func);

  if (folded_inst != nullptr) {
    // We do not want to change the body of the function by adding new
    // instructions.  When folding we can only generate new constants.
    assert(folded_inst->IsConstant() &&
           "CCP is only interested in constant values.");
    uint32_t new_val = ComputeLatticeMeet(instr, folded_inst->result_id());
    values_[instr->result_id()] = new_val;
    return IsVaryingValue(new_val) ? SSAPropagator::kVarying
                                   : SSAPropagator::kInteresting;
  }

  // Conservatively mark this instruction as varying if any input id is varying.
  if (!instr->WhileEachInId([this](uint32_t* op_id) {
        auto iter = values_.find(*op_id);
        if (iter != values_.end() && IsVaryingValue(iter->second)) return false;
        return true;
      })) {
    return MarkInstructionVarying(instr);
  }

  // If not, see if there is a least one unknown operand to the instruction.  If
  // so, we might be able to fold it later.
  if (!instr->WhileEachInId([this](uint32_t* op_id) {
        auto it = values_.find(*op_id);
        if (it == values_.end()) return false;
        return true;
      })) {
    return SSAPropagator::kNotInteresting;
  }

  // Otherwise, we will never be able to fold this instruction, so mark it
  // varying.
  return MarkInstructionVarying(instr);
}

SSAPropagator::PropStatus CCPPass::VisitBranch(Instruction* instr,
                                               BasicBlock** dest_bb) const {
  assert(instr->IsBranch() && "Expected a branch instruction.");

  *dest_bb = nullptr;
  uint32_t dest_label = 0;
  if (instr->opcode() == SpvOpBranch) {
    // An unconditional jump always goes to its unique destination.
    dest_label = instr->GetSingleWordInOperand(0);
  } else if (instr->opcode() == SpvOpBranchConditional) {
    // For a conditional branch, determine whether the predicate selector has a
    // known value in |values_|.  If it does, set the destination block
    // according to the selector's boolean value.
    uint32_t pred_id = instr->GetSingleWordOperand(0);
    auto it = values_.find(pred_id);
    if (it == values_.end() || IsVaryingValue(it->second)) {
      // The predicate has an unknown value, either branch could be taken.
      return SSAPropagator::kVarying;
    }

    // Get the constant value for the predicate selector from the value table.
    // Use it to decide which branch will be taken.
    uint32_t pred_val_id = it->second;
    const analysis::Constant* c = const_mgr_->FindDeclaredConstant(pred_val_id);
    assert(c && "Expected to find a constant declaration for a known value.");
    // Undef values should have returned as varying above.
    assert(c->AsBoolConstant() || c->AsNullConstant());
    if (c->AsNullConstant()) {
      dest_label = instr->GetSingleWordOperand(2u);
    } else {
      const analysis::BoolConstant* val = c->AsBoolConstant();
      dest_label = val->value() ? instr->GetSingleWordOperand(1)
                                : instr->GetSingleWordOperand(2);
    }
  } else {
    // For an OpSwitch, extract the value taken by the switch selector and check
    // which of the target literals it matches.  The branch associated with that
    // literal is the taken branch.
    assert(instr->opcode() == SpvOpSwitch);
    if (instr->GetOperand(0).words.size() != 1) {
      // If the selector is wider than 32-bits, return varying. TODO(dnovillo):
      // Add support for wider constants.
      return SSAPropagator::kVarying;
    }
    uint32_t select_id = instr->GetSingleWordOperand(0);
    auto it = values_.find(select_id);
    if (it == values_.end() || IsVaryingValue(it->second)) {
      // The selector has an unknown value, any of the branches could be taken.
      return SSAPropagator::kVarying;
    }

    // Get the constant value for the selector from the value table. Use it to
    // decide which branch will be taken.
    uint32_t select_val_id = it->second;
    const analysis::Constant* c =
        const_mgr_->FindDeclaredConstant(select_val_id);
    assert(c && "Expected to find a constant declaration for a known value.");
    // TODO: support 64-bit integer switches.
    uint32_t constant_cond = 0;
    if (const analysis::IntConstant* val = c->AsIntConstant()) {
      constant_cond = val->words()[0];
    } else {
      // Undef values should have returned varying above.
      assert(c->AsNullConstant());
      constant_cond = 0;
    }

    // Start assuming that the selector will take the default value;
    dest_label = instr->GetSingleWordOperand(1);
    for (uint32_t i = 2; i < instr->NumOperands(); i += 2) {
      if (constant_cond == instr->GetSingleWordOperand(i)) {
        dest_label = instr->GetSingleWordOperand(i + 1);
        break;
      }
    }
  }

  assert(dest_label && "Destination label should be set at this point.");
  *dest_bb = context()->cfg()->block(dest_label);
  return SSAPropagator::kInteresting;
}

SSAPropagator::PropStatus CCPPass::VisitInstruction(Instruction* instr,
                                                    BasicBlock** dest_bb) {
  *dest_bb = nullptr;
  if (instr->opcode() == SpvOpPhi) {
    return VisitPhi(instr);
  } else if (instr->IsBranch()) {
    return VisitBranch(instr, dest_bb);
  } else if (instr->result_id()) {
    return VisitAssignment(instr);
  }
  return SSAPropagator::kVarying;
}

bool CCPPass::ReplaceValues() {
  // Even if we make no changes to the function's IR, propagation may have
  // created new constants.  Even if those constants cannot be replaced in
  // the IR, the constant definition itself is a change.  To reflect this,
  // we check whether the next ID to be given by the module is different than
  // the original bound ID. If that happens, new instructions were added to the
  // module during propagation.
  //
  // See https://github.com/KhronosGroup/SPIRV-Tools/issues/3636 and
  // https://github.com/KhronosGroup/SPIRV-Tools/issues/3991 for details.
  bool changed_ir = (context()->module()->IdBound() > original_id_bound_);

  for (const auto& it : values_) {
    uint32_t id = it.first;
    uint32_t cst_id = it.second;
    if (!IsVaryingValue(cst_id) && id != cst_id) {
      context()->KillNamesAndDecorates(id);
      changed_ir |= context()->ReplaceAllUsesWith(id, cst_id);
    }
  }

  return changed_ir;
}

bool CCPPass::PropagateConstants(Function* fp) {
  if (fp->IsDeclaration()) {
    return false;
  }

  // Mark function parameters as varying.
  fp->ForEachParam([this](const Instruction* inst) {
    values_[inst->result_id()] = kVaryingSSAId;
  });

  const auto visit_fn = [this](Instruction* instr, BasicBlock** dest_bb) {
    return VisitInstruction(instr, dest_bb);
  };

  propagator_ =
      std::unique_ptr<SSAPropagator>(new SSAPropagator(context(), visit_fn));

  if (propagator_->Run(fp)) {
    return ReplaceValues();
  }

  return false;
}

void CCPPass::Initialize() {
  const_mgr_ = context()->get_constant_mgr();

  // Populate the constant table with values from constant declarations in the
  // module.  The values of each OpConstant declaration is the identity
  // assignment (i.e., each constant is its own value).
  for (const auto& inst : get_module()->types_values()) {
    // Record compile time constant ids. Treat all other global values as
    // varying.
    if (inst.IsConstant()) {
      values_[inst.result_id()] = inst.result_id();
    } else {
      values_[inst.result_id()] = kVaryingSSAId;
    }
  }

  original_id_bound_ = context()->module()->IdBound();
}

Pass::Status CCPPass::Process() {
  Initialize();

  // Process all entry point functions.
  ProcessFunction pfn = [this](Function* fp) { return PropagateConstants(fp); };
  bool modified = context()->ProcessReachableCallTree(pfn);
  return modified ? Pass::Status::SuccessWithChange
                  : Pass::Status::SuccessWithoutChange;
}

}  // namespace opt
}  // namespace spvtools