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