include/llvm/CodeGen/LiveRegMatrix.h

   1 //===- LiveRegMatrix.h - Track register interference ----------*- C++ -*---===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // The LiveRegMatrix analysis pass keeps track of virtual register interference
  10 // along two dimensions: Slot indexes and register units. The matrix is used by
  11 // register allocators to ensure that no interfering virtual registers get
  12 // assigned to overlapping physical registers.
  13 //
  14 // Register units are defined in MCRegisterInfo.h, they represent the smallest
  15 // unit of interference when dealing with overlapping physical registers. The
  16 // LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When
  17 // a virtual register is assigned to a physical register, the live range for
  18 // the virtual register is inserted into the LiveIntervalUnion for each regunit
  19 // in the physreg.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #ifndef LLVM_CODEGEN_LIVEREGMATRIX_H
  24 #define LLVM_CODEGEN_LIVEREGMATRIX_H
  25
  26 #include "llvm/ADT/BitVector.h"
  27 #include "llvm/CodeGen/LiveIntervalUnion.h"
  28 #include "llvm/CodeGen/MachineFunctionPass.h"
  29 #include <memory>
  30
  31 namespace llvm {
  32
  33 class AnalysisUsage;
  34 class LiveInterval;
  35 class LiveIntervals;
  36 class MachineFunction;
  37 class TargetRegisterInfo;
  38 class VirtRegMap;
  39
  40 class LiveRegMatrix : public MachineFunctionPass {
  41   const TargetRegisterInfo *TRI;
  42   LiveIntervals *LIS;
  43   VirtRegMap *VRM;
  44
  45   // UserTag changes whenever virtual registers have been modified.
  46   unsigned UserTag = 0;
  47
  48   // The matrix is represented as a LiveIntervalUnion per register unit.
  49   LiveIntervalUnion::Allocator LIUAlloc;
  50   LiveIntervalUnion::Array Matrix;
  51
  52   // Cached queries per register unit.
  53   std::unique_ptr<LiveIntervalUnion::Query[]> Queries;
  54
  55   // Cached register mask interference info.
  56   unsigned RegMaskTag = 0;
  57   unsigned RegMaskVirtReg = 0;
  58   BitVector RegMaskUsable;
  59
  60   // MachineFunctionPass boilerplate.
  61   void getAnalysisUsage(AnalysisUsage &) const override;
  62   bool runOnMachineFunction(MachineFunction &) override;
  63   void releaseMemory() override;
  64
  65 public:
  66   static char ID;
  67
  68   LiveRegMatrix();
  69
  70   //===--------------------------------------------------------------------===//
  71   // High-level interface.
  72   //===--------------------------------------------------------------------===//
  73   //
  74   // Check for interference before assigning virtual registers to physical
  75   // registers.
  76   //
  77
  78   /// Invalidate cached interference queries after modifying virtual register
  79   /// live ranges. Interference checks may return stale information unless
  80   /// caches are invalidated.
  81   void invalidateVirtRegs() { ++UserTag; }
  82
  83   enum InterferenceKind {
  84     /// No interference, go ahead and assign.
  85     IK_Free = 0,
  86
  87     /// Virtual register interference. There are interfering virtual registers
  88     /// assigned to PhysReg or its aliases. This interference could be resolved
  89     /// by unassigning those other virtual registers.
  90     IK_VirtReg,
  91
  92     /// Register unit interference. A fixed live range is in the way, typically
  93     /// argument registers for a call. This can't be resolved by unassigning
  94     /// other virtual registers.
  95     IK_RegUnit,
  96
  97     /// RegMask interference. The live range is crossing an instruction with a
  98     /// regmask operand that doesn't preserve PhysReg. This typically means
  99     /// VirtReg is live across a call, and PhysReg isn't call-preserved.
 100     IK_RegMask
 101   };
 102
 103   /// Check for interference before assigning VirtReg to PhysReg.
 104   /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg).
 105   /// When there is more than one kind of interference, the InterferenceKind
 106   /// with the highest enum value is returned.
 107   InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg);
 108
 109   /// Check for interference in the segment [Start, End) that may prevent
 110   /// assignment to PhysReg. If this function returns true, there is
 111   /// interference in the segment [Start, End) of some other interval already
 112   /// assigned to PhysReg. If this function returns false, PhysReg is free at
 113   /// the segment [Start, End).
 114   bool checkInterference(SlotIndex Start, SlotIndex End, unsigned PhysReg);
 115
 116   /// Assign VirtReg to PhysReg.
 117   /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
 118   /// update VirtRegMap. The live range is expected to be available in PhysReg.
 119   void assign(LiveInterval &VirtReg, unsigned PhysReg);
 120
 121   /// Unassign VirtReg from its PhysReg.
 122   /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
 123   /// the assignment and updates VirtRegMap accordingly.
 124   void unassign(LiveInterval &VirtReg);
 125
 126   /// Returns true if the given \p PhysReg has any live intervals assigned.
 127   bool isPhysRegUsed(unsigned PhysReg) const;
 128
 129   //===--------------------------------------------------------------------===//
 130   // Low-level interface.
 131   //===--------------------------------------------------------------------===//
 132   //
 133   // Provide access to the underlying LiveIntervalUnions.
 134   //
 135
 136   /// Check for regmask interference only.
 137   /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
 138   /// If PhysReg is null, check if VirtReg crosses any regmask operands.
 139   bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0);
 140
 141   /// Check for regunit interference only.
 142   /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
 143   /// register units.
 144   bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg);
 145
 146   /// Query a line of the assigned virtual register matrix directly.
 147   /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
 148   /// This returns a reference to an internal Query data structure that is only
 149   /// valid until the next query() call.
 150   LiveIntervalUnion::Query &query(const LiveRange &LR, unsigned RegUnit);
 151
 152   /// Directly access the live interval unions per regunit.
 153   /// This returns an array indexed by the regunit number.
 154   LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
 155 };
 156
 157 } // end namespace llvm
 158
 159 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H