LLVM  7.0.0svn
LiveRegMatrix.h
Go to the documentation of this file.
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"
30 #include <memory>
31 
32 namespace llvm {
33 
34 class AnalysisUsage;
35 class LiveInterval;
36 class LiveIntervals;
37 class MachineFunction;
38 class TargetRegisterInfo;
39 class VirtRegMap;
40 
42  const TargetRegisterInfo *TRI;
43  LiveIntervals *LIS;
44  VirtRegMap *VRM;
45 
46  // UserTag changes whenever virtual registers have been modified.
47  unsigned UserTag = 0;
48 
49  // The matrix is represented as a LiveIntervalUnion per register unit.
52 
53  // Cached queries per register unit.
54  std::unique_ptr<LiveIntervalUnion::Query[]> Queries;
55 
56  // Cached register mask interference info.
57  unsigned RegMaskTag = 0;
58  unsigned RegMaskVirtReg = 0;
59  BitVector RegMaskUsable;
60 
61  // MachineFunctionPass boilerplate.
62  void getAnalysisUsage(AnalysisUsage &) const override;
63  bool runOnMachineFunction(MachineFunction &) override;
64  void releaseMemory() override;
65 
66 public:
67  static char ID;
68 
69  LiveRegMatrix();
70 
71  //===--------------------------------------------------------------------===//
72  // High-level interface.
73  //===--------------------------------------------------------------------===//
74  //
75  // Check for interference before assigning virtual registers to physical
76  // registers.
77  //
78 
79  /// Invalidate cached interference queries after modifying virtual register
80  /// live ranges. Interference checks may return stale information unless
81  /// caches are invalidated.
82  void invalidateVirtRegs() { ++UserTag; }
83 
85  /// No interference, go ahead and assign.
86  IK_Free = 0,
87 
88  /// Virtual register interference. There are interfering virtual registers
89  /// assigned to PhysReg or its aliases. This interference could be resolved
90  /// by unassigning those other virtual registers.
92 
93  /// Register unit interference. A fixed live range is in the way, typically
94  /// argument registers for a call. This can't be resolved by unassigning
95  /// other virtual registers.
97 
98  /// RegMask interference. The live range is crossing an instruction with a
99  /// regmask operand that doesn't preserve PhysReg. This typically means
100  /// VirtReg is live across a call, and PhysReg isn't call-preserved.
102  };
103 
104  /// Check for interference before assigning VirtReg to PhysReg.
105  /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg).
106  /// When there is more than one kind of interference, the InterferenceKind
107  /// with the highest enum value is returned.
108  InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned 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, unsigned 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(LiveInterval &VirtReg, unsigned 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(LiveInterval &VirtReg);
126 
127  /// Returns true if the given \p PhysReg has any live intervals assigned.
128  bool isPhysRegUsed(unsigned 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(LiveInterval &VirtReg, unsigned PhysReg = 0);
141 
142  /// Check for regunit interference only.
143  /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
144  /// register units.
145  bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg);
146 
147  /// Query a line of the assigned virtual register matrix directly.
148  /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
149  /// This returns a reference to an internal Query data structure that is only
150  /// valid until the next query() call.
151  LiveIntervalUnion::Query &query(const LiveRange &LR, unsigned RegUnit);
152 
153  /// Directly access the live interval unions per regunit.
154  /// This returns an array indexed by the regunit number.
155  LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
156 };
157 
158 } // end namespace llvm
159 
160 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H
No interference, go ahead and assign.
Definition: LiveRegMatrix.h:86
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg)
Check for interference before assigning VirtReg to PhysReg.
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
LiveIntervalUnion * getLiveUnions()
Directly access the live interval unions per regunit.
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
Query interferences between a single live virtual register and a live interval union.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
LiveIntervalUnion::Query & query(const LiveRange &LR, unsigned RegUnit)
Query a line of the assigned virtual register matrix directly.
Register unit interference.
Definition: LiveRegMatrix.h:96
bool isPhysRegUsed(unsigned PhysReg) const
Returns true if the given PhysReg has any live intervals assigned.
void assign(LiveInterval &VirtReg, unsigned PhysReg)
Assign VirtReg to PhysReg.
RegMask interference.
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:82
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
Represent the analysis usage information of a pass.
static const unsigned End
LiveSegments::Allocator Allocator
void unassign(LiveInterval &VirtReg)
Unassign VirtReg from its PhysReg.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg)
Check for regunit interference only.
bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg=0)
Check for regmask interference only.
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
Virtual register interference.
Definition: LiveRegMatrix.h:91