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(const LiveInterval &VirtReg,
108                                      MCRegister PhysReg);
109 
110   /// Check for interference in the segment [Start, End) that may prevent
111   /// assignment to PhysReg. If this function returns true, there is
112   /// interference in the segment [Start, End) of some other interval already
113   /// assigned to PhysReg. If this function returns false, PhysReg is free at
114   /// the segment [Start, End).
115   bool checkInterference(SlotIndex Start, SlotIndex End, MCRegister PhysReg);
116 
117   /// Assign VirtReg to PhysReg.
118   /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
119   /// update VirtRegMap. The live range is expected to be available in PhysReg.
120   void assign(const LiveInterval &VirtReg, MCRegister PhysReg);
121 
122   /// Unassign VirtReg from its PhysReg.
123   /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
124   /// the assignment and updates VirtRegMap accordingly.
125   void unassign(const LiveInterval &VirtReg);
126 
127   /// Returns true if the given \p PhysReg has any live intervals assigned.
128   bool isPhysRegUsed(MCRegister PhysReg) const;
129 
130   //===--------------------------------------------------------------------===//
131   // Low-level interface.
132   //===--------------------------------------------------------------------===//
133   //
134   // Provide access to the underlying LiveIntervalUnions.
135   //
136 
137   /// Check for regmask interference only.
138   /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
139   /// If PhysReg is null, check if VirtReg crosses any regmask operands.
140   bool checkRegMaskInterference(const LiveInterval &VirtReg,
141                                 MCRegister PhysReg = MCRegister::NoRegister);
142 
143   /// Check for regunit interference only.
144   /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
145   /// register units.
146   bool checkRegUnitInterference(const LiveInterval &VirtReg,
147                                 MCRegister PhysReg);
148 
149   /// Query a line of the assigned virtual register matrix directly.
150   /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
151   /// This returns a reference to an internal Query data structure that is only
152   /// valid until the next query() call.
153   LiveIntervalUnion::Query &query(const LiveRange &LR, MCRegister RegUnit);
154 
155   /// Directly access the live interval unions per regunit.
156   /// This returns an array indexed by the regunit number.
157   LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
158 
159   Register getOneVReg(unsigned PhysReg) const;
160 };
161 
162 } // end namespace llvm
163 
164 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H
165