Skip to content

Commit ffbc9c7

Browse files
wmi-11wmi-11
committedApr 4, 2016
Replace analyzeSiblingValues with new algorithm to fix its compile
time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Differential Revision: http://reviews.llvm.org/D15302 llvm-svn: 265309
1 parent 68374d1 commit ffbc9c7

16 files changed

+949
-1053
lines changed
 

‎llvm/include/llvm/CodeGen/LiveRangeEdit.h

Lines changed: 35 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -72,6 +72,10 @@ class LiveRangeEdit : private MachineRegisterInfo::Delegate {
7272
/// ScannedRemattable - true when remattable values have been identified.
7373
bool ScannedRemattable;
7474

75+
/// DeadRemats - The saved instructions which have already been dead after
76+
/// rematerialization but not deleted yet -- to be done in postOptimization.
77+
SmallPtrSet<MachineInstr *, 32> *DeadRemats;
78+
7579
/// Remattable - Values defined by remattable instructions as identified by
7680
/// tii.isTriviallyReMaterializable().
7781
SmallPtrSet<const VNInfo*,4> Remattable;
@@ -116,13 +120,16 @@ class LiveRangeEdit : private MachineRegisterInfo::Delegate {
116120
/// @param vrm Map of virtual registers to physical registers for this
117121
/// function. If NULL, no virtual register map updates will
118122
/// be done. This could be the case if called before Regalloc.
123+
/// @param deadRemats The collection of all the instructions defining an
124+
/// original reg and are dead after remat.
119125
LiveRangeEdit(LiveInterval *parent, SmallVectorImpl<unsigned> &newRegs,
120126
MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm,
121-
Delegate *delegate = nullptr)
127+
Delegate *delegate = nullptr,
128+
SmallPtrSet<MachineInstr *, 32> *deadRemats = nullptr)
122129
: Parent(parent), NewRegs(newRegs), MRI(MF.getRegInfo()), LIS(lis),
123-
VRM(vrm), TII(*MF.getSubtarget().getInstrInfo()),
124-
TheDelegate(delegate), FirstNew(newRegs.size()),
125-
ScannedRemattable(false) {
130+
VRM(vrm), TII(*MF.getSubtarget().getInstrInfo()), TheDelegate(delegate),
131+
FirstNew(newRegs.size()), ScannedRemattable(false),
132+
DeadRemats(deadRemats) {
126133
MRI.setDelegate(this);
127134
}
128135

@@ -142,6 +149,16 @@ class LiveRangeEdit : private MachineRegisterInfo::Delegate {
142149
bool empty() const { return size() == 0; }
143150
unsigned get(unsigned idx) const { return NewRegs[idx+FirstNew]; }
144151

152+
/// pop_back - It allows LiveRangeEdit users to drop new registers.
153+
/// The context is when an original def instruction of a register is
154+
/// dead after rematerialization, we still want to keep it for following
155+
/// rematerializations. We save the def instruction in DeadRemats,
156+
/// and replace the original dst register with a new dummy register so
157+
/// the live range of original dst register can be shrinked normally.
158+
/// We don't want to allocate phys register for the dummy register, so
159+
/// we want to drop it from the NewRegs set.
160+
void pop_back() { NewRegs.pop_back(); }
161+
145162
ArrayRef<unsigned> regs() const {
146163
return makeArrayRef(NewRegs).slice(FirstNew);
147164
}
@@ -175,15 +192,15 @@ class LiveRangeEdit : private MachineRegisterInfo::Delegate {
175192
/// Remat - Information needed to rematerialize at a specific location.
176193
struct Remat {
177194
VNInfo *ParentVNI; // parent_'s value at the remat location.
178-
MachineInstr *OrigMI; // Instruction defining ParentVNI.
195+
MachineInstr *OrigMI; // Instruction defining OrigVNI. It contains the
196+
// real expr for remat.
179197
explicit Remat(VNInfo *ParentVNI) : ParentVNI(ParentVNI), OrigMI(nullptr) {}
180198
};
181199

182200
/// canRematerializeAt - Determine if ParentVNI can be rematerialized at
183201
/// UseIdx. It is assumed that parent_.getVNINfoAt(UseIdx) == ParentVNI.
184202
/// When cheapAsAMove is set, only cheap remats are allowed.
185-
bool canRematerializeAt(Remat &RM,
186-
SlotIndex UseIdx,
203+
bool canRematerializeAt(Remat &RM, VNInfo *OrigVNI, SlotIndex UseIdx,
187204
bool cheapAsAMove);
188205

189206
/// rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an
@@ -208,6 +225,12 @@ class LiveRangeEdit : private MachineRegisterInfo::Delegate {
208225
return Rematted.count(ParentVNI);
209226
}
210227

228+
void markDeadRemat(MachineInstr *inst) {
229+
// DeadRemats is an optional field.
230+
if (DeadRemats)
231+
DeadRemats->insert(inst);
232+
}
233+
211234
/// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try
212235
/// to erase it from LIS.
213236
void eraseVirtReg(unsigned Reg);
@@ -218,8 +241,11 @@ class LiveRangeEdit : private MachineRegisterInfo::Delegate {
218241
/// RegsBeingSpilled lists registers currently being spilled by the register
219242
/// allocator. These registers should not be split into new intervals
220243
/// as currently those new intervals are not guaranteed to spill.
221-
void eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
222-
ArrayRef<unsigned> RegsBeingSpilled = None);
244+
/// NoSplit indicates this func is used after the iterations of selectOrSplit
245+
/// where registers should not be split into new intervals.
246+
void eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
247+
ArrayRef<unsigned> RegsBeingSpilled = None,
248+
bool NoSplit = false);
223249

224250
/// calculateRegClassAndHint - Recompute register class and hint for each new
225251
/// register.

0 commit comments

Comments
 (0)