src/llvm-project/llvm/lib/Target/WebAssembly/WebAssemblyDebugValueManager.cpp - toolchain/rustc - Git at Google

 //===-- 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 (!llvm::is_contained(DbgValues, DV)) {
       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 (!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();
 }
	//===-- 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 (!llvm::is_contained(DbgValues, DV)) {
	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 (!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();
	}