InstrRefBasedImpl.h

//===- InstrRefBasedImpl.h - Tracking Debug Value MIs ---------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H
#define LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/UniqueVector.h"
#include "llvm/CodeGen/LexicalScopes.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/TargetFrameLowering.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/IR/DebugInfoMetadata.h"

#include "LiveDebugValues.h"

class TransferTracker;

// Forward dec of unit test class, so that we can peer into the LDV object.
class InstrRefLDVTest;

namespace LiveDebugValues {

class MLocTracker;

using namespace llvm;

/// Handle-class for a particular "location". This value-type uniquely
/// symbolises a register or stack location, allowing manipulation of locations
/// without concern for where that location is. Practically, this allows us to
/// treat the state of the machine at a particular point as an array of values,
/// rather than a map of values.
class LocIdx {
  unsigned Location;

  // Default constructor is private, initializing to an illegal location number.
  // Use only for "not an entry" elements in IndexedMaps.
  LocIdx() : Location(UINT_MAX) {}

public:
#define NUM_LOC_BITS 24
  LocIdx(unsigned L) : Location(L) {
    assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits");
  }

  static LocIdx MakeIllegalLoc() { return LocIdx(); }

  bool isIllegal() const { return Location == UINT_MAX; }

  uint64_t asU64() const { return Location; }

  bool operator==(unsigned L) const { return Location == L; }

  bool operator==(const LocIdx &L) const { return Location == L.Location; }

  bool operator!=(unsigned L) const { return !(*this == L); }

  bool operator!=(const LocIdx &L) const { return !(*this == L); }

  bool operator<(const LocIdx &Other) const {
    return Location < Other.Location;
  }
};

// The location at which a spilled value resides. It consists of a register and
// an offset.
struct SpillLoc {
  unsigned SpillBase;
  StackOffset SpillOffset;
  bool operator==(const SpillLoc &Other) const {
    return std::make_pair(SpillBase, SpillOffset) ==
           std::make_pair(Other.SpillBase, Other.SpillOffset);
  }
  bool operator<(const SpillLoc &Other) const {
    return std::make_tuple(SpillBase, SpillOffset.getFixed(),
                           SpillOffset.getScalable()) <
           std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(),
                           Other.SpillOffset.getScalable());
  }
};

/// Unique identifier for a value defined by an instruction, as a value type.
/// Casts back and forth to a uint64_t. Probably replacable with something less
/// bit-constrained. Each value identifies the instruction and machine location
/// where the value is defined, although there may be no corresponding machine
/// operand for it (ex: regmasks clobbering values). The instructions are
/// one-based, and definitions that are PHIs have instruction number zero.
///
/// The obvious limits of a 1M block function or 1M instruction blocks are
/// problematic; but by that point we should probably have bailed out of
/// trying to analyse the function.
class ValueIDNum {
  uint64_t BlockNo : 20;         /// The block where the def happens.
  uint64_t InstNo : 20;          /// The Instruction where the def happens.
                                 /// One based, is distance from start of block.
  uint64_t LocNo : NUM_LOC_BITS; /// The machine location where the def happens.

public:
  // Default-initialize to EmptyValue. This is necessary to make IndexedMaps
  // of values to work.
  ValueIDNum() : BlockNo(0xFFFFF), InstNo(0xFFFFF), LocNo(0xFFFFFF) {}

  ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc)
      : BlockNo(Block), InstNo(Inst), LocNo(Loc) {}

  ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc)
      : BlockNo(Block), InstNo(Inst), LocNo(Loc.asU64()) {}

  uint64_t getBlock() const { return BlockNo; }
  uint64_t getInst() const { return InstNo; }
  uint64_t getLoc() const { return LocNo; }
  bool isPHI() const { return InstNo == 0; }

  uint64_t asU64() const {
    uint64_t TmpBlock = BlockNo;
    uint64_t TmpInst = InstNo;
    return TmpBlock << 44ull | TmpInst << NUM_LOC_BITS | LocNo;
  }

  static ValueIDNum fromU64(uint64_t v) {
    uint64_t L = (v & 0x3FFF);
    return {v >> 44ull, ((v >> NUM_LOC_BITS) & 0xFFFFF), L};
  }

  bool operator<(const ValueIDNum &Other) const {
    return asU64() < Other.asU64();
  }

  bool operator==(const ValueIDNum &Other) const {
    return std::tie(BlockNo, InstNo, LocNo) ==
           std::tie(Other.BlockNo, Other.InstNo, Other.LocNo);
  }

  bool operator!=(const ValueIDNum &Other) const { return !(*this == Other); }

  std::string asString(const std::string &mlocname) const {
    return Twine("Value{bb: ")
        .concat(Twine(BlockNo).concat(
            Twine(", inst: ")
                .concat((InstNo ? Twine(InstNo) : Twine("live-in"))
                            .concat(Twine(", loc: ").concat(Twine(mlocname)))
                            .concat(Twine("}")))))
        .str();
  }

  static ValueIDNum EmptyValue;
};

/// Thin wrapper around an integer -- designed to give more type safety to
/// spill location numbers.
class SpillLocationNo {
public:
  explicit SpillLocationNo(unsigned SpillNo) : SpillNo(SpillNo) {}
  unsigned SpillNo;
  unsigned id() const { return SpillNo; }

  bool operator<(const SpillLocationNo &Other) const {
    return SpillNo < Other.SpillNo;
  }

  bool operator==(const SpillLocationNo &Other) const {
    return SpillNo == Other.SpillNo;
  }
  bool operator!=(const SpillLocationNo &Other) const {
    return !(*this == Other);
  }
};

/// Meta qualifiers for a value. Pair of whatever expression is used to qualify
/// the the value, and Boolean of whether or not it's indirect.
class DbgValueProperties {
public:
  DbgValueProperties(const DIExpression *DIExpr, bool Indirect)
      : DIExpr(DIExpr), Indirect(Indirect) {}

  /// Extract properties from an existing DBG_VALUE instruction.
  DbgValueProperties(const MachineInstr &MI) {
    assert(MI.isDebugValue());
    DIExpr = MI.getDebugExpression();
    Indirect = MI.getOperand(1).isImm();
  }

  bool operator==(const DbgValueProperties &Other) const {
    return std::tie(DIExpr, Indirect) == std::tie(Other.DIExpr, Other.Indirect);
  }

  bool operator!=(const DbgValueProperties &Other) const {
    return !(*this == Other);
  }