InstrRefBasedImpl.h | Explore in Territory

//===- 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/IndexedMap.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/MachineInstr.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include <optional>

#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;
class DbgOpIDMap;

usingnamespacellvm;

DebugVariableID;
VarAndLoc;

/// Mapping from DebugVariable to/from a unique identifying number. Each
/// DebugVariable consists of three pointers, and after a small amount of
/// work to identify overlapping fragments of variables we mostly only use
/// DebugVariables as identities of variables. It's much more compile-time
/// efficient to use an ID number instead, which this class provides.
class DebugVariableMap { … };

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

// The location at which a spilled value resides. It consists of a register and
// an offset.
struct SpillLoc { … };

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

} // End namespace LiveDebugValues

namespace llvm {
usingnamespaceLiveDebugValues;

template <> struct DenseMapInfo<LocIdx> { … };

template <> struct DenseMapInfo<ValueIDNum> { … };

} // end namespace llvm

namespace LiveDebugValues {
usingnamespacellvm;

/// Type for a table of values in a block.
ValueTable;

/// A collection of ValueTables, one per BB in a function, with convenient
/// accessor methods.
struct FuncValueTable { … };

/// Thin wrapper around an integer -- designed to give more type safety to
/// spill location numbers.
class SpillLocationNo { … };

/// Meta qualifiers for a value. Pair of whatever expression is used to qualify
/// the value, and Boolean of whether or not it's indirect.
class DbgValueProperties { … };

/// TODO: Might pack better if we changed this to a Struct of Arrays, since
/// MachineOperand is width 32, making this struct width 33. We could also
/// potentially avoid storing the whole MachineOperand (sizeof=32), instead
/// choosing to store just the contents portion (sizeof=8) and a Kind enum,
/// since we already know it is some type of immediate value.
/// Stores a single debug operand, which can either be a MachineOperand for
/// directly storing immediate values, or a ValueIDNum representing some value
/// computed at some point in the program. IsConst is used as a discriminator.
struct DbgOp { … };

/// A DbgOp whose ID (if any) has resolved to an actual location, LocIdx. Used
/// when working with concrete debug values, i.e. when joining MLocs and VLocs
/// in the TransferTracker or emitting DBG_VALUE/DBG_VALUE_LIST instructions in
/// the MLocTracker.
struct ResolvedDbgOp { … };

/// An ID used in the DbgOpIDMap (below) to lookup a stored DbgOp. This is used
/// in place of actual DbgOps inside of a DbgValue to reduce its size, as
/// DbgValue is very frequently used and passed around, and the actual DbgOp is
/// over 8x larger than this class, due to storing a MachineOperand. This ID
/// should be equal for all equal DbgOps, and also encodes whether the mapped
/// DbgOp is a constant, meaning that for simple equality or const-ness checks
/// it is not necessary to lookup this ID.
struct DbgOpID { … };

/// Class storing the complete set of values that are observed by DbgValues
/// within the current function. Allows 2-way lookup, with `find` returning the
/// Op for a given ID and `insert` returning the ID for a given Op (creating one
/// if none exists).
class DbgOpIDMap { … };

// We set the maximum number of operands that we will handle to keep DbgValue
// within a reasonable size (64 bytes), as we store and pass a lot of them
// around.
#define MAX_DBG_OPS …

/// Class recording the (high level) _value_ of a variable. Identifies the value
/// of the variable as a list of ValueIDNums and constant MachineOperands, or as
/// an empty list for undef debug values or VPHI values which we have not found
/// valid locations for.
/// This class also stores meta-information about how the value is qualified.
/// Used to reason about variable values when performing the second
/// (DebugVariable specific) dataflow analysis.
class DbgValue { … };

class LocIdxToIndexFunctor { … };

/// Tracker for what values are in machine locations. Listens to the Things
/// being Done by various instructions, and maintains a table of what machine
/// locations have what values (as defined by a ValueIDNum).
///
/// There are potentially a much larger number of machine locations on the
/// target machine than the actual working-set size of the function. On x86 for
/// example, we're extremely unlikely to want to track values through control
/// or debug registers. To avoid doing so, MLocTracker has several layers of
/// indirection going on, described below, to avoid unnecessarily tracking
/// any location.
///
/// Here's a sort of diagram of the indexes, read from the bottom up:
///
///           Size on stack   Offset on stack
///                 \              /
///          Stack Idx (Where in slot is this?)
///                         /
///                        /
/// Slot Num (%stack.0)   /
/// FrameIdx => SpillNum /
///              \      /
///           SpillID (int)   Register number (int)
///                      \       /
///                      LocationID => LocIdx
///                                |
///                       LocIdx => ValueIDNum
///
/// The aim here is that the LocIdx => ValueIDNum vector is just an array of
/// values in numbered locations, so that later analyses can ignore whether the
/// location is a register or otherwise. To map a register / spill location to
/// a LocIdx, you have to use the (sparse) LocationID => LocIdx map. And to
/// build a LocationID for a stack slot, you need to combine identifiers for
/// which stack slot it is and where within that slot is being described.
///
/// Register mask operands cause trouble by technically defining every register;
/// various hacks are used to avoid tracking registers that are never read and
/// only written by regmasks.
class MLocTracker { … };

/// Types for recording sets of variable fragments that overlap. For a given
/// local variable, we record all other fragments of that variable that could
/// overlap it, to reduce search time.
FragmentOfVar;
OverlapMap;

/// Collection of DBG_VALUEs observed when traversing a block. Records each
/// variable and the value the DBG_VALUE refers to. Requires the machine value
/// location dataflow algorithm to have run already, so that values can be
/// identified.
class VLocTracker { … };

// XXX XXX docs
class InstrRefBasedLDV : public LDVImpl { … };

} // namespace LiveDebugValues

#endif /* LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H */
llvm/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h
