//===-- 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 "llvm/ADT/DenseSet.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Function.h"

using namespace llvm;

WebAssemblyDebugValueManager::WebAssemblyDebugValueManager(MachineInstr *Def)
    : Def(Def) {
  if (!Def->getMF()->getFunction().getSubprogram())
    return;

  // This code differs from MachineInstr::collectDebugValues in that it scans
  // all users in the 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();

  // Collect all the uses of this def.
  MachineRegisterInfo &MRI = Def->getMF()->getRegInfo();
  MachineBasicBlock *MBB = Def->getParent();
  unsigned RemainingUses = 0;
  for (MachineInstr &MI : MRI.use_instructions(CurrentReg))
    if (MI.isDebugValue() && MI.getParent() == MBB)
      ++RemainingUses;
  if (RemainingUses == 0)
    return;

  // Scan forward to collect DBG_VALUEs in block order.
  // Scan backward at the same pace to account for earlier uses and stop once
  // all possible matches have been found.
  // Only the forward scan collects DBG_VALUEs.
  MachineBasicBlock::iterator Down = std::next(Def->getIterator()),
                              DownEnd = MBB->end(), Up = Def->getIterator(),
                              UpBegin = MBB->begin();
  while (RemainingUses > 0 && Down != DownEnd) {
    if (Down->isDebugValue()) {
      if (Down->hasDebugOperandForReg(CurrentReg)) {
        DbgValues.push_back(&*Down);
        --RemainingUses;
      }
    } else if (Down->definesRegister(CurrentReg, /*TRI=*/nullptr)) {
      break;
    }
    ++Down;
    if (Up != UpBegin) {
      --Up;
      if (Up->isDebugValue() && Up->hasDebugOperandForReg(CurrentReg))
        --RemainingUses;
    }
  }
}

// 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 {};

  // 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() != Insert->getParent() &&
      !Def->getParent()->isSuccessor(Insert->getParent()))
    return {};

  SmallDenseSet<DebugVariable, 4> OurVars;
  for (MachineInstr *DV : DbgValues)
    OurVars.insert(DebugVariable(DV->getDebugVariable(),
                                 DV->getDebugExpression(),
                                 DV->getDebugLoc()->getInlinedAt()));

  SmallDenseMap<DebugVariable, SmallVector<MachineInstr *, 2>>
      SeenDbgVarToDbgValues;
  auto RecordDbgValue = [&](MachineInstr &MI) {
    if (!MI.isDebugValue())
      return;
    DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                      MI.getDebugLoc()->getInlinedAt());
    if (OurVars.contains(Var) && !llvm::is_contained(DbgValues, &MI))
      SeenDbgVarToDbgValues[Var].push_back(&MI);
  };

  if (Def->getParent() == Insert->getParent()) {
    // Search both ways to quickly determine whether Insert follows Def.
    // Only the forward scan collects DBG_VALUEs.
    MachineBasicBlock::iterator Down = std::next(Def->getIterator()),
                                DownEnd = Def->getParent()->end(),
                                Up = Def->getIterator(),
                                UpBegin = Def->getParent()->begin();
    bool DefFirst = false;
    while (Down != DownEnd || Up != UpBegin) {
      if (Down != DownEnd) {
        if (&*Down == Insert) {
          DefFirst = true;
          break;
        }
        RecordDbgValue(*Down);
        ++Down;
      }
      if (Up != UpBegin) {
        --Up;
        if (&*Up == Insert)
          break;
      }
    }
    if (!DefFirst) // Not a sink
      return {};

  } else { // Def and Insert are in different BBs
    // 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)
      RecordDbgValue(*MI);
    for (MachineBasicBlock::iterator MI = Insert->getParent()->begin(),
                                     ME = Insert->getIterator();
         MI != ME; ++MI)
      RecordDbgValue(*MI);
  }

  // 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 encountering other DBG_VALUEs with the
      // same 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 (!llvm::is_contained(DbgValues, MI)) {
      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();
}