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(); }
  static LocIdx MakeTombstoneLoc() {
    LocIdx L = LocIdx();
    --L.Location;
    return L;
  }

  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 {
  union {
    struct {
      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.
    } s;
    uint64_t Value;
  } u;

  static_assert(sizeof(u) == 8, "Badly packed ValueIDNum?");

public:
  // Default-initialize to EmptyValue. This is necessary to make IndexedMaps
  // of values to work.
  ValueIDNum() { u.Value = EmptyValue.asU64(); }

  ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc) {
    u.s = {Block, Inst, Loc};
  }

  ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc) {
    u.s = {Block, Inst, Loc.asU64()};
  }

  ValueIDNum &operator=(const ValueIDNum &Other) {
    u.Value = Other.u.Value;
    return *this;
  }

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

  uint64_t asU64() const { return u.Value; }

  static ValueIDNum fromU64(uint64_t v) {
    ValueIDNum Val;
    Val.u.Value = v;
    return Val;
  }

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

  bool operator==(const ValueIDNum &Other) const {
    return u.Value == Other.u.Value;
  }

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

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

  static ValueIDNum EmptyValue;
  static ValueIDNum TombstoneValue;
};

/// 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.