LiveRegMatrix.h

Go to the documentation of this file.

//===- LiveRegMatrix.h - Track register interference ----------*- C++ -*---===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// The LiveRegMatrix analysis pass keeps track of virtual register interference
// along two dimensions: Slot indexes and register units. The matrix is used by
// register allocators to ensure that no interfering virtual registers get
// assigned to overlapping physical registers.
//
// Register units are defined in MCRegisterInfo.h, they represent the smallest
// unit of interference when dealing with overlapping physical registers. The
// LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When
// a virtual register is assigned to a physical register, the live range for
// the virtual register is inserted into the LiveIntervalUnion for each regunit
// in the physreg.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_CODEGEN_LIVEREGMATRIX_H
#define LLVM_CODEGEN_LIVEREGMATRIX_H
 
#include "llvm/ADT/BitVector.h"
#include "llvm/CodeGen/LiveIntervalUnion.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include <memory>
 
namespace llvm {
 
class AnalysisUsage;
class LiveInterval;
class LiveIntervals;
class MachineFunction;
class TargetRegisterInfo;
class VirtRegMap;
 
class LiveRegMatrix {
  friend class LiveRegMatrixWrapperLegacy;
  friend class LiveRegMatrixAnalysis;
  const TargetRegisterInfo *TRI = nullptr;
  LiveIntervals *LIS = nullptr;
  VirtRegMap *VRM = nullptr;
 
  // UserTag changes whenever virtual registers have been modified.
  unsigned UserTag = 0;
 
  // The matrix is represented as a LiveIntervalUnion per register unit.
  std::unique_ptr<LiveIntervalUnion::Allocator> LIUAlloc;
  LiveIntervalUnion::Array Matrix;
 
  // Cached queries per register unit.
  std::unique_ptr<LiveIntervalUnion::Query[]> Queries;
 
  // Cached register mask interference info.
  unsigned RegMaskTag = 0;
  Register RegMaskVirtReg;
  BitVector RegMaskUsable;
 
  LiveRegMatrix()
      : LIUAlloc(std::make_unique<LiveIntervalUnion::Allocator>()) {};
  void releaseMemory();
 
  /// Check regmask interference only, restricted to the segment
  /// [Start, End). Returns true if a regmask operand in that segment
  /// clobbers PhysReg.
  bool checkRegMaskInterference(SlotIndex Start, SlotIndex End,
                                MCRegister PhysReg);
 
  /// Check regunit interference only, restricted to the segment
  /// [Start, End). Returns true if a fixed live range on one of PhysReg's
  /// register units overlaps [Start, End).
  bool checkRegUnitInterference(SlotIndex Start, SlotIndex End,
                                MCRegister PhysReg);
 
public:
  LiveRegMatrix(LiveRegMatrix &&Other) = default;
 
  LLVM_ABI void init(MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM);
 
  //===--------------------------------------------------------------------===//
  // High-level interface.
  //===--------------------------------------------------------------------===//
  //
  // Check for interference before assigning virtual registers to physical
  // registers.
  //
 
  /// Invalidate cached interference queries after modifying virtual register
  /// live ranges. Interference checks may return stale information unless
  /// caches are invalidated.
  void invalidateVirtRegs() { ++UserTag; }
 
  enum InterferenceKind {
    /// No interference, go ahead and assign.
    IK_Free = 0,
 
    /// Virtual register interference. There are interfering virtual registers
    /// assigned to PhysReg or its aliases. This interference could be resolved
    /// by unassigning those other virtual registers.
    IK_VirtReg,
 
    /// Register unit interference. A fixed live range is in the way, typically
    /// argument registers for a call. This can't be resolved by unassigning
    /// other virtual registers.
    IK_RegUnit,
 
    /// RegMask interference. The live range is crossing an instruction with a
    /// regmask operand that doesn't preserve PhysReg. This typically means
    /// VirtReg is live across a call, and PhysReg isn't call-preserved.
    IK_RegMask
  };
 
  /// Check for interference before assigning VirtReg to PhysReg.
  /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg).
  /// When there is more than one kind of interference, the InterferenceKind
  /// with the highest enum value is returned.
  LLVM_ABI InterferenceKind checkInterference(const LiveInterval &VirtReg,
                                              MCRegister PhysReg);
 
  /// Check for interference in the segment [Start, End) that may prevent
  /// assignment to PhysReg. This checks regmask interference (e.g. PhysReg
  /// is clobbered by a call in [Start, End)), fixed register unit
  /// interference (e.g. PhysReg is used directly by some instruction in
  /// [Start, End)), and virtual register interference (some other interval
  /// already assigned to PhysReg overlaps [Start, End)) -- the same kinds of
  /// interference considered by the checkInterference(LiveInterval&, ...)
  /// overload above, restricted to a single contiguous segment. If this
  /// function returns true, there is interference in the segment
  /// [Start, End). If this function returns false, PhysReg is free at the
  /// segment [Start, End).
  LLVM_ABI bool checkInterference(SlotIndex Start, SlotIndex End,
                                  MCRegister PhysReg);
 
  /// Check for interference in the segment [Start, End) that may prevent
  /// assignment to PhysReg, like checkInterference. Returns a lane mask of
  /// which lanes of the physical register interfere in the segment [Start, End)
  /// of some other interval already assigned to PhysReg.
  ///
  /// If this function returns LaneBitmask::getNone(), PhysReg is completely
  /// free at the segment [Start, End).
  LLVM_ABI LaneBitmask checkInterferenceLanes(SlotIndex Start, SlotIndex End,
                                              MCRegister PhysReg);
 
  /// Assign VirtReg to PhysReg.
  /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
  /// update VirtRegMap. The live range is expected to be available in PhysReg.
  LLVM_ABI void assign(const LiveInterval &VirtReg, MCRegister PhysReg);
 
  /// Unassign VirtReg from its PhysReg.
  /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
  /// the assignment and updates VirtRegMap accordingly.
  /// ClearAllReferencingSegments changes the way segments are removed from
  /// the matrix:
  ///   - If false (default), only segments that exactly match VirtReg's live
  ///     range are removed.
  ///   - If true, all segments that reference VirtReg are removed. This is
  ///     useful when VirtReg's live range(s) is already empty.
  LLVM_ABI void unassign(const LiveInterval &VirtReg,
                         bool ClearAllReferencingSegments = false);
 
  /// Returns true if the given \p PhysReg has any live intervals assigned.
  LLVM_ABI bool isPhysRegUsed(MCRegister PhysReg) const;
 
  //===--------------------------------------------------------------------===//
  // Low-level interface.
  //===--------------------------------------------------------------------===//
  //
  // Provide access to the underlying LiveIntervalUnions.
  //
 
  /// Check for regmask interference only.
  /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
  /// If PhysReg is null, check if VirtReg crosses any regmask operands.
  LLVM_ABI bool
  checkRegMaskInterference(const LiveInterval &VirtReg,
                           MCRegister PhysReg = MCRegister::NoRegister);
 
  /// Check for regunit interference only.
  /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
  /// register units.
  LLVM_ABI bool checkRegUnitInterference(const LiveInterval &VirtReg,
                                         MCRegister PhysReg);
 
  /// Query a line of the assigned virtual register matrix directly.
  /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
  /// This returns a reference to an internal Query data structure that is only
  /// valid until the next query() call.
  LLVM_ABI LiveIntervalUnion::Query &query(const LiveRange &LR,
                                           MCRegUnit RegUnit);
 
  /// Directly access the live interval unions per regunit.
  /// This returns an array indexed by the regunit number.
  LiveIntervalUnion *getLiveUnions() {
    return &Matrix[static_cast<MCRegUnit>(0)];
  }
 
  LLVM_ABI Register getOneVReg(unsigned PhysReg) const;
 
#ifndef NDEBUG
  /// This checks that each LiveInterval referenced in LiveIntervalUnion
  /// actually exists in LiveIntervals and is not a dangling pointer.
  bool isValid() const;
#endif
};
 
class LLVM_ABI LiveRegMatrixWrapperLegacy : public MachineFunctionPass {
  LiveRegMatrix LRM;
 
public:
  static char ID;
 
  LiveRegMatrixWrapperLegacy() : MachineFunctionPass(ID) {}
 
  LiveRegMatrix &getLRM() { return LRM; }
  const LiveRegMatrix &getLRM() const { return LRM; }
 
  void getAnalysisUsage(AnalysisUsage &AU) const override;
  bool runOnMachineFunction(MachineFunction &MF) override;
  void releaseMemory() override;
};
 
class LiveRegMatrixAnalysis : public AnalysisInfoMixin<LiveRegMatrixAnalysis> {
  friend AnalysisInfoMixin<LiveRegMatrixAnalysis>;
  static AnalysisKey Key;
 
public:
  using Result = LiveRegMatrix;
 
  LLVM_ABI LiveRegMatrix run(MachineFunction &MF,
                             MachineFunctionAnalysisManager &MFAM);
};
 
} // end namespace llvm
 
#endif // LLVM_CODEGEN_LIVEREGMATRIX_H