//===-- WebAssemblyDebugValueManager.cpp - WebAssembly DebugValue Manager -===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file implements the manager for MachineInstr DebugValues.
///
//===----------------------------------------------------------------------===//

#include "WebAssemblyDebugValueManager.h"
#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"
#include "WebAssemblyMachineFunctionInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/IR/DebugInfoMetadata.h"

using namespace llvm;

WebAssemblyDebugValueManager::WebAssemblyDebugValueManager(MachineInstr *Def)
    : Def(Def) {
  // This code differs from MachineInstr::collectDebugValues in that it scans
  // the whole BB, not just contiguous DBG_VALUEs, until another definition to
  // the same register is encountered.
  if (!Def->getOperand(0).isReg())
    return;
  CurrentReg = Def->getOperand(0).getReg();

  for (MachineBasicBlock::iterator MI = std::next(Def->getIterator()),
                                   ME = Def->getParent()->end();
       MI != ME; ++MI) {
    // If another definition appears, stop
    if (MI->definesRegister(CurrentReg))
      break;
    if (MI->isDebugValue() && MI->hasDebugOperandForReg(CurrentReg))
      DbgValues.push_back(&*MI);
  }
}

// Returns true if both A and B are the same CONST_I32/I64/F32/F64 instructions.
// Doesn't include CONST_V128.
static bool isSameScalarConst(const MachineInstr *A, const MachineInstr *B) {
  if (A->getOpcode() != B->getOpcode() ||
      !WebAssembly::isScalarConst(A->getOpcode()) ||
      !WebAssembly::isScalarConst(B->getOpcode()))
    return false;
  const MachineOperand &OpA = A->getOperand(1), &OpB = B->getOperand(1);
  if ((OpA.isImm() && OpB.isImm() && OpA.getImm() == OpB.getImm()) ||
      (OpA.isFPImm() && OpB.isFPImm() && OpA.getFPImm() == OpB.getFPImm()) ||
      (OpA.isGlobal() && OpB.isGlobal() && OpA.getGlobal() == OpB.getGlobal()))
    return true;
  return false;
}

SmallVector<MachineInstr *, 1>
WebAssemblyDebugValueManager::getSinkableDebugValues(
    MachineInstr *Insert) const {
  if (DbgValues.empty())
    return {};
  // DBG_VALUEs between Def and Insert
  SmallVector<MachineInstr *, 8> DbgValuesInBetween;

  if (Def->getParent() == Insert->getParent()) {
    // When Def and Insert are within the same BB, check if Insert comes after
    // Def, because we only support sinking.
    bool DefFirst = false;
    for (MachineBasicBlock::iterator MI = std::next(Def->getIterator()),
                                     ME = Def->getParent()->end();
         MI != ME; ++MI) {
      if (&*MI == Insert) {
        DefFirst = true;
        break;
      }
      if (MI->isDebugValue())
        DbgValuesInBetween.push_back(&*MI);
    }
    if (!DefFirst) // Not a sink
      return {};

  } else { // Def and Insert are in different BBs
    // If Def and Insert are in different BBs, we only handle a simple case in
    // which Insert's BB is a successor of Def's BB.
    if (!Def->getParent()->isSuccessor(Insert->getParent()))
      return {};

    // Gather DBG_VALUEs between 'Def~Def BB's end' and
    // 'Insert BB's begin~Insert'
    for (MachineBasicBlock::iterator MI = std::next(Def->getIterator()),
                                     ME = Def->getParent()->end();
         MI != ME; ++MI) {
      if (MI->isDebugValue())
        DbgValuesInBetween.push_back(&*MI);
    }
    for (MachineBasicBlock::iterator MI = Insert->getParent()->begin(),
                                     ME = Insert->getIterator();
         MI != ME; ++MI) {
      if (MI->isDebugValue())
        DbgValuesInBetween.push_back(&*MI);
    }
  }

  // Gather DebugVariables that are seen between Def and Insert, excluding our
  // own DBG_VALUEs in DbgValues.
  SmallDenseMap<DebugVariable, SmallVector<MachineInstr *, 2>>
      SeenDbgVarToDbgValues;
  for (auto *DV : DbgValuesInBetween) {
    if (std::find(DbgValues.begin(), DbgValues.end(), DV) == DbgValues.end()) {
      DebugVariable Var(DV->getDebugVariable(), DV->getDebugExpression(),
                        DV->getDebugLoc()->getInlinedAt());
      SeenDbgVarToDbgValues[Var].push_back(DV);
    }
  }

  // Gather sinkable DBG_VALUEs. We should not sink a DBG_VALUE if there is
  // another DBG_VALUE between Def and Insert referring to the same
  // DebugVariable. For example,
  //   %0 = someinst
  //   DBG_VALUE %0, !"a", !DIExpression() // Should not sink with %0
  //   %1 = anotherinst
  //   DBG_VALUE %1, !"a", !DIExpression()
  // Where if %0 were to sink, the DBG_VAUE should not sink with it, as that
  // would re-order assignments.
  SmallVector<MachineInstr *, 1> SinkableDbgValues;
  MachineRegisterInfo &MRI = Def->getParent()->getParent()->getRegInfo();
  for (auto *DV : DbgValues) {
    DebugVariable Var(DV->getDebugVariable(), DV->getDebugExpression(),
                      DV->getDebugLoc()->getInlinedAt());
    auto It = SeenDbgVarToDbgValues.find(Var);
    if (It == SeenDbgVarToDbgValues.end()) {
      SinkableDbgValues.push_back(DV);
      continue;
    }
    if (!WebAssembly::isScalarConst(Def->getOpcode()))
      continue;
    auto &OverlappingDbgValues = It->second;
    bool Sinkable = true;
    for (auto *OverlappingDV : OverlappingDbgValues) {
      MachineOperand &DbgOp = OverlappingDV->getDebugOperand(0);
      if (!DbgOp.isReg()) {
        Sinkable = false;
        break;
      }
      Register OtherReg = DbgOp.getReg();
      MachineInstr *OtherDef = MRI.getUniqueVRegDef(OtherReg);
      // We have an exception to allow encoutering other DBG_VALUEs with the
      // smae DebugVariables, only when they are referring to the same scalar
      // CONST instruction. For example,
      //   %0 = CONST_I32 1
      //   DBG_VALUE %0, !"a", !DIExpression() // Can sink with %0
      //   %1 = CONST_I32 1
      //   DBG_VALUE %1, !"a", !DIExpression()
      // When %0 were to be sunk/cloneed, the DBG_VALUE can be sunk/cloned with
      // it because even though the second DBG_VALUE refers to the same
      // DebugVariable, its value in effect is the same CONST instruction.
      //
      // This is to allow a case that can happen with RegStackify's
      // "rematerializeCheapDef". For example, we have this program with two
      // BBs:
      // bb0:
      //   %0 = CONST_I32 1
      //   DBG_VALUE %0, !"a", ...
      //   ...
      //   INST0 ..., $0 ...
      //  bb1:
      //   INST1 ..., $0 ...
      //   INST2 ..., $0 ...
      //
      // We process bb0 first. Because %0 is used multiple times, %0 is cloned
      // before INST0:
      // bb0:
      //   %0 = CONST_I32 1
      //   DBG_VALUE %0, !"a", ...
      //   ...
      //   %1 = CONST_I32 1
      //   DBG_VALUE %1, !"a", ...
      //   INST0 ..., $1 ...
      //
      // And when we process bb1, we clone %0 and its DBG_VALUE again:
      // bb0:
      //   %0 = CONST_I32 1
      //   DBG_VALUE %0, !"a", ...
      //   ...
      //   %1 = CONST_I32 1
      //   DBG_VALUE %1, !"a", ...
      //   INST0 ..., $1 ...
      //  bb1:
      //   %2 = CONST_I32 1
      //   DBG_VALUE %2, !"a", ... // !!!
      //   INST1 ..., $2 ...
      //   %3 = CONST_I32 1
      //   DBG_VALUE %3, !"a", ... // !!!
      //   INST2 ..., $3 ...
      //
      // But (without this exception) the cloned DBG_VALUEs marked with !!! are
      // not possible to be cloned, because there is a previously cloned
      // 'DBG_VALUE %1, !"a"' at the end of bb0 referring to the same
      // DebugVariable "a". But in this case they are OK to be cloned, because
      // the interfering DBG_VALUE is pointing to the same 'CONST_I32 1',
      // because it was cloned from the same instruction.
      if (!OtherDef || !isSameScalarConst(Def, OtherDef)) {
        Sinkable = false;
        break;
      }
    }
    if (Sinkable)
      SinkableDbgValues.push_back(DV);
  }
  return SinkableDbgValues;
}

// Returns true if the insertion point is the same as the current place.
// Following DBG_VALUEs for 'Def' are ignored.
bool WebAssemblyDebugValueManager::isInsertSamePlace(
    MachineInstr *Insert) const {
  if (Def->getParent() != Insert->getParent())
    return false;
  for (MachineBasicBlock::iterator MI = std::next(Def->getIterator()),
                                   ME = Insert;
       MI != ME; ++MI) {
    if (std::find(DbgValues.begin(), DbgValues.end(), MI) == DbgValues.end()) {
      return false;
    }
  }
  return true;
}

// Returns true if any instruction in MBB has the same debug location as DL.
// Also returns true if DL is an empty location.
static bool hasSameDebugLoc(const MachineBasicBlock *MBB, DebugLoc DL) {
  for (const auto &MI : *MBB)
    if (MI.getDebugLoc() == DL)
      return true;
  return false;
}

// Sink 'Def', and also sink its eligible DBG_VALUEs to the place before
// 'Insert'. Convert the original DBG_VALUEs into undefs.
//
// For DBG_VALUEs to sink properly, if 'Def' and 'Insert' are within the same
// BB, 'Insert' should be below 'Def'; if they are in different BBs, 'Insert'
// should be in one of 'Def's BBs successors. Def will be sunk regardless of the
// location.
//
// This DebugValueManager's new Def and DbgValues will be updated to the newly
// sinked Def + DBG_VALUEs.
void WebAssemblyDebugValueManager::sink(MachineInstr *Insert) {
  // In case Def is requested to be sunk to
  // the same place, we don't need to do anything. If we actually do the sink,
  // it will create unnecessary undef DBG_VALUEs. For example, if the original
  // code is:
  //   %0 = someinst           // Def
  //   DBG_VALUE %0, ...
  //   %1 = anotherinst        // Insert
  //
  // If we actually sink %0 and the following DBG_VALUE and setting the original
  // DBG_VALUE undef, the result will be:
  //   DBG_VALUE %noreg, ...   // Unnecessary!
  //   %0 = someinst           // Def
  //   DBG_VALUE %0, ...
  //   %1 = anotherinst        // Insert
  if (isInsertSamePlace(Insert))
    return;

  MachineBasicBlock *MBB = Insert->getParent();
  MachineFunction *MF = MBB->getParent();

  // Get the list of sinkable DBG_VALUEs. This should be done before sinking
  // Def, because we need to examine instructions between Def and Insert.
  SmallVector<MachineInstr *, 1> SinkableDbgValues =
      getSinkableDebugValues(Insert);

  // Sink Def first.
  //
  // When moving to a different BB, we preserve the debug loc only if the
  // destination BB contains the same location. See
  // https://llvm.org/docs/HowToUpdateDebugInfo.html#when-to-preserve-an-instruction-location.
  if (Def->getParent() != MBB && !hasSameDebugLoc(MBB, Def->getDebugLoc()))
      Def->setDebugLoc(DebugLoc());
  MBB->splice(Insert, Def->getParent(), Def);

  if (DbgValues.empty())
    return;

  // Clone sinkable DBG_VALUEs and insert them.
  SmallVector<MachineInstr *, 1> NewDbgValues;
  for (MachineInstr *DV : SinkableDbgValues) {
    MachineInstr *Clone = MF->CloneMachineInstr(DV);
    MBB->insert(Insert, Clone);
    NewDbgValues.push_back(Clone);
  }

  // When sinking a Def and its DBG_VALUEs, we shouldn't just remove the
  // original DBG_VALUE instructions; we should set them to undef not to create
  // an impossible combination of variable assignments in the original program.
  // For example, this is the original program in order:
  //   %0 = CONST_I32 0
  //   DBG_VALUE %0, !"a", !DIExpression()  // a = 0, b = ?
  //   %1 = CONST_I32 1
  //   DBG_VALUE %1, !"b", !DIExpression()  // a = 0, b = 1
  //   %2 = CONST_I32 2
  //   DBG_VALUE %2, !"a", !DIExpression()  // a = 2, b = 1
  //   %3 = CONST_I32 3
  //   DBG_VALUE %3, !"b", !DIExpression()  // a = 2, b = 3
  //
  // If %2 were to sink below %3, if we just sink DBG_VALUE %1 with it, the
  // debug info will show the variable "b" is updated to 2, creating the
  // variable assignment combination of (a = 0, b = 3), which is not possible in
  // the original program:
  //   %0 = CONST_I32 0
  //   DBG_VALUE %0, !"a", !DIExpression()  // a = 0, b = ?
  //   %1 = CONST_I32 1
  //   DBG_VALUE %1, !"b", !DIExpression()  // a = 0, b = 1
  //   %3 = CONST_I32 3
  //   DBG_VALUE %3, !"b", !DIExpression()  // a = 0, b = 3 (Incorrect!)
  //   %2 = CONST_I32 2
  //   DBG_VALUE %2, !"a", !DIExpression()  // a = 2, b = 3
  //
  // To fix this,we leave an undef DBG_VALUE in its original place, so that the
  // result will be
  //   %0 = CONST_I32 0
  //   DBG_VALUE %0, !"a", !DIExpression()      // a = 0, b = ?
  //   %1 = CONST_I32 1
  //   DBG_VALUE %1, !"b", !DIExpression()      // a = 0, b = 1
  //   DBG_VALUE $noreg, !"a", !DIExpression()  // a = ?, b = 1
  //   %3 = CONST_I32 3
  //   DBG_VALUE %3, !"b", !DIExpression()      // a = ?, b = 3
  //   %2 = CONST_I32 2
  //   DBG_VALUE %2, !"a", !DIExpression()      // a = 2, b = 3
  // Now in the middle "a" will be shown as "optimized out", but it wouldn't
  // show the impossible combination of (a = 0, b = 3).
  for (MachineInstr *DV : DbgValues)
    DV->setDebugValueUndef();

  DbgValues.swap(NewDbgValues);
}

// Clone 'Def', and also clone its eligible DBG_VALUEs to the place before
// 'Insert'.
//
// For DBG_VALUEs to be cloned properly, if 'Def' and 'Insert' are within the
// same BB, 'Insert' should be below 'Def'; if they are in different BBs,
// 'Insert' should be in one of 'Def's BBs successors. Def will be cloned
// regardless of the location.
//
// If NewReg is not $noreg, the newly cloned DBG_VALUEs will have the new
// register as its operand.
void WebAssemblyDebugValueManager::cloneSink(MachineInstr *Insert,
                                             Register NewReg,
                                             bool CloneDef) const {
  MachineBasicBlock *MBB = Insert->getParent();
  MachineFunction *MF = MBB->getParent();

  SmallVector<MachineInstr *> SinkableDbgValues =
      getSinkableDebugValues(Insert);

  // Clone Def first.
  if (CloneDef) {
    MachineInstr *Clone = MF->CloneMachineInstr(Def);
    // When cloning to a different BB, we preserve the debug loc only if the
    // destination BB contains the same location. See
    // https://llvm.org/docs/HowToUpdateDebugInfo.html#when-to-preserve-an-instruction-location.
    if (Def->getParent() != MBB && !hasSameDebugLoc(MBB, Def->getDebugLoc()))
      Clone->setDebugLoc(DebugLoc());
    if (NewReg != CurrentReg && NewReg.isValid())
      Clone->getOperand(0).setReg(NewReg);
    MBB->insert(Insert, Clone);
  }

  if (DbgValues.empty())
    return;

  // Clone sinkable DBG_VALUEs and insert them.
  SmallVector<MachineInstr *, 1> NewDbgValues;
  for (MachineInstr *DV : SinkableDbgValues) {
    MachineInstr *Clone = MF->CloneMachineInstr(DV);
    MBB->insert(Insert, Clone);
    NewDbgValues.push_back(Clone);
  }

  if (NewReg != CurrentReg && NewReg.isValid())
    for (auto *DBI : NewDbgValues)
      for (auto &MO : DBI->getDebugOperandsForReg(CurrentReg))
        MO.setReg(NewReg);
}

// Update the register for Def and DBG_VALUEs.
void WebAssemblyDebugValueManager::updateReg(Register Reg) {
  if (Reg != CurrentReg && Reg.isValid()) {
    for (auto *DBI : DbgValues)
      for (auto &MO : DBI->getDebugOperandsForReg(CurrentReg))
        MO.setReg(Reg);
    CurrentReg = Reg;
    Def->getOperand(0).setReg(Reg);
  }
}

void WebAssemblyDebugValueManager::replaceWithLocal(unsigned LocalId) {
  for (auto *DBI : DbgValues) {
    auto IndexType = DBI->isIndirectDebugValue()
                         ? llvm::WebAssembly::TI_LOCAL_INDIRECT
                         : llvm::WebAssembly::TI_LOCAL;
    for (auto &MO : DBI->getDebugOperandsForReg(CurrentReg))
      MO.ChangeToTargetIndex(IndexType, LocalId);
  }
}

// Remove Def, and set its DBG_VALUEs to undef.
void WebAssemblyDebugValueManager::removeDef() {
  Def->removeFromParent();
  for (MachineInstr *DV : DbgValues)
    DV->setDebugValueUndef();
}