blob: 25d22a02d33bd35626724b11ee42bdc71bbdb24e [file] [log] [blame]
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +00001//===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===//
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// Implementation of the LiveRangeCalc class.
11//
12//===----------------------------------------------------------------------===//
13
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +000014#include "LiveRangeCalc.h"
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +000015#include "llvm/ADT/SetVector.h"
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +000016#include "llvm/CodeGen/MachineDominators.h"
Jakob Stoklund Olesen989b3b12012-06-05 21:54:09 +000017#include "llvm/CodeGen/MachineRegisterInfo.h"
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +000018
19using namespace llvm;
20
Chandler Carruth1b9dde02014-04-22 02:02:50 +000021#define DEBUG_TYPE "regalloc"
22
Matthias Braun1aed6ff2014-12-16 04:03:38 +000023void LiveRangeCalc::resetLiveOutMap() {
24 unsigned NumBlocks = MF->getNumBlockIDs();
25 Seen.clear();
26 Seen.resize(NumBlocks);
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +000027 EntryInfoMap.clear();
Matthias Braun1aed6ff2014-12-16 04:03:38 +000028 Map.resize(NumBlocks);
29}
30
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +000031void LiveRangeCalc::reset(const MachineFunction *mf,
Jakob Stoklund Olesen5ef0e0b2012-06-04 18:21:16 +000032 SlotIndexes *SI,
33 MachineDominatorTree *MDT,
34 VNInfo::Allocator *VNIA) {
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +000035 MF = mf;
Jakob Stoklund Olesen5ef0e0b2012-06-04 18:21:16 +000036 MRI = &MF->getRegInfo();
37 Indexes = SI;
38 DomTree = MDT;
39 Alloc = VNIA;
Matthias Braun1aed6ff2014-12-16 04:03:38 +000040 resetLiveOutMap();
Matthias Braunc3a72c22014-12-15 21:36:35 +000041 LiveIn.clear();
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +000042}
43
44
Matthias Braun1aed6ff2014-12-16 04:03:38 +000045static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
46 LiveRange &LR, const MachineOperand &MO) {
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +000047 const MachineInstr &MI = *MO.getParent();
48 SlotIndex DefIdx =
49 Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber());
Matthias Braunc3a72c22014-12-15 21:36:35 +000050
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +000051 // Create the def in LR. This may find an existing def.
52 LR.createDeadDef(DefIdx, Alloc);
Matthias Braun2f662322014-12-10 01:12:12 +000053}
54
Matthias Brauna25e13a2015-03-19 00:21:58 +000055void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
Matthias Braun2f662322014-12-10 01:12:12 +000056 assert(MRI && Indexes && "call reset() first");
57
Matthias Braun1aed6ff2014-12-16 04:03:38 +000058 // Step 1: Create minimal live segments for every definition of Reg.
Matthias Braun2f662322014-12-10 01:12:12 +000059 // Visit all def operands. If the same instruction has multiple defs of Reg,
Matthias Braun1aed6ff2014-12-16 04:03:38 +000060 // createDeadDef() will deduplicate.
Matthias Braun2f662322014-12-10 01:12:12 +000061 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
62 unsigned Reg = LI.reg;
Matthias Braun1aed6ff2014-12-16 04:03:38 +000063 for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
64 if (!MO.isDef() && !MO.readsReg())
65 continue;
66
Matthias Braun2f662322014-12-10 01:12:12 +000067 unsigned SubReg = MO.getSubReg();
Matthias Brauna25e13a2015-03-19 00:21:58 +000068 if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +000069 LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
Krzysztof Parzyszek0a955d62016-08-29 13:15:35 +000070 : MRI->getMaxLaneMaskForVReg(Reg);
Matthias Braun2f662322014-12-10 01:12:12 +000071 // If this is the first time we see a subregister def, initialize
72 // subranges by creating a copy of the main range.
73 if (!LI.hasSubRanges() && !LI.empty()) {
Matthias Braune6a24852015-09-25 21:51:14 +000074 LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
Matthias Braun2f662322014-12-10 01:12:12 +000075 LI.createSubRangeFrom(*Alloc, ClassMask, LI);
76 }
77
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +000078 LaneBitmask Mask = SubMask;
Matthias Braun09afa1e2014-12-11 00:59:06 +000079 for (LiveInterval::SubRange &S : LI.subranges()) {
Matthias Braun2f662322014-12-10 01:12:12 +000080 // A Mask for subregs common to the existing subrange and current def.
Matthias Braune6a24852015-09-25 21:51:14 +000081 LaneBitmask Common = S.LaneMask & Mask;
Matthias Braun2f662322014-12-10 01:12:12 +000082 if (Common == 0)
83 continue;
Matthias Braun2f662322014-12-10 01:12:12 +000084 LiveInterval::SubRange *CommonRange;
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +000085 // A Mask for subregs covered by the subrange but not the current def.
86 if (LaneBitmask RM = S.LaneMask & ~Mask) {
87 // Split the subrange S into two parts: one covered by the current
88 // def (CommonRange), and the one not affected by it (updated S).
89 S.LaneMask = RM;
Matthias Braun09afa1e2014-12-11 00:59:06 +000090 CommonRange = LI.createSubRangeFrom(*Alloc, Common, S);
Matthias Braun2f662322014-12-10 01:12:12 +000091 } else {
Matthias Braun09afa1e2014-12-11 00:59:06 +000092 assert(Common == S.LaneMask);
93 CommonRange = &S;
Matthias Braun2f662322014-12-10 01:12:12 +000094 }
Matthias Braun1aed6ff2014-12-16 04:03:38 +000095 if (MO.isDef())
96 createDeadDef(*Indexes, *Alloc, *CommonRange, MO);
Matthias Braun2f662322014-12-10 01:12:12 +000097 Mask &= ~Common;
98 }
Matthias Braun1aed6ff2014-12-16 04:03:38 +000099 // Create a new SubRange for subregs we did not cover yet.
Matthias Braun2f662322014-12-10 01:12:12 +0000100 if (Mask != 0) {
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000101 LiveInterval::SubRange *NewRange = LI.createSubRange(*Alloc, Mask);
102 if (MO.isDef())
103 createDeadDef(*Indexes, *Alloc, *NewRange, MO);
Matthias Braun2f662322014-12-10 01:12:12 +0000104 }
105 }
106
Matthias Braundbcca0d2014-12-24 02:11:51 +0000107 // Create the def in the main liverange. We do not have to do this if
108 // subranges are tracked as we recreate the main range later in this case.
109 if (MO.isDef() && !LI.hasSubRanges())
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000110 createDeadDef(*Indexes, *Alloc, LI, MO);
Matthias Braun2f662322014-12-10 01:12:12 +0000111 }
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000112
113 // We may have created empty live ranges for partially undefined uses, we
114 // can't keep them because we won't find defs in them later.
115 LI.removeEmptySubRanges();
116
117 // Step 2: Extend live segments to all uses, constructing SSA form as
118 // necessary.
Matthias Braundbcca0d2014-12-24 02:11:51 +0000119 if (LI.hasSubRanges()) {
120 for (LiveInterval::SubRange &S : LI.subranges()) {
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000121 LiveRangeCalc SubLRC;
122 SubLRC.reset(MF, Indexes, DomTree, Alloc);
123 SubLRC.extendToUses(S, Reg, S.LaneMask, &LI);
Matthias Braundbcca0d2014-12-24 02:11:51 +0000124 }
125 LI.clear();
Matthias Braun71f95642016-05-20 23:14:56 +0000126 constructMainRangeFromSubranges(LI);
Matthias Braundbcca0d2014-12-24 02:11:51 +0000127 } else {
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000128 resetLiveOutMap();
Matthias Braundbcca0d2014-12-24 02:11:51 +0000129 extendToUses(LI, Reg, ~0u);
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000130 }
Matthias Braun2f662322014-12-10 01:12:12 +0000131}
132
Matthias Braun71f95642016-05-20 23:14:56 +0000133void LiveRangeCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
134 // First create dead defs at all defs found in subranges.
135 LiveRange &MainRange = LI;
136 assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
137 "Expect empty main liverange");
138
139 for (const LiveInterval::SubRange &SR : LI.subranges()) {
140 for (const VNInfo *VNI : SR.valnos) {
141 if (!VNI->isUnused() && !VNI->isPHIDef())
142 MainRange.createDeadDef(VNI->def, *Alloc);
143 }
144 }
Matthias Braun71f95642016-05-20 23:14:56 +0000145 resetLiveOutMap();
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000146 extendToUses(MainRange, LI.reg, ~0U, &LI);
Matthias Braun71f95642016-05-20 23:14:56 +0000147}
Matthias Braun2f662322014-12-10 01:12:12 +0000148
Matthias Braunc3a72c22014-12-15 21:36:35 +0000149void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
Jakob Stoklund Olesen989b3b12012-06-05 21:54:09 +0000150 assert(MRI && Indexes && "call reset() first");
151
152 // Visit all def operands. If the same instruction has multiple defs of Reg,
Matthias Braun2d5c32b2013-10-10 21:28:57 +0000153 // LR.createDeadDef() will deduplicate.
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000154 for (MachineOperand &MO : MRI->def_operands(Reg))
155 createDeadDef(*Indexes, *Alloc, LR, MO);
Jakob Stoklund Olesen989b3b12012-06-05 21:54:09 +0000156}
157
158
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000159void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask Mask,
160 LiveInterval *LI) {
161 SmallVector<SlotIndex, 4> Undefs;
162 if (LI != nullptr)
163 LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
164
Jakob Stoklund Olesen989b3b12012-06-05 21:54:09 +0000165 // Visit all operands that read Reg. This may include partial defs.
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000166 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
Owen Andersonb36376e2014-03-17 19:36:09 +0000167 for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
Jakob Stoklund Olesen4aed4702012-09-06 18:15:15 +0000168 // Clear all kill flags. They will be reinserted after register allocation
169 // by LiveIntervalAnalysis::addKillFlags().
170 if (MO.isUse())
171 MO.setIsKill(false);
Matthias Braunc3a72c22014-12-15 21:36:35 +0000172 if (!MO.readsReg())
Jakob Stoklund Olesen989b3b12012-06-05 21:54:09 +0000173 continue;
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000174
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000175 unsigned SubReg = MO.getSubReg();
176 if (SubReg != 0) {
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000177 LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
178 if (MO.isDef())
Krzysztof Parzyszek0a955d62016-08-29 13:15:35 +0000179 SLM = ~SLM;
180 // Ignore uses not reading the current (sub)range.
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000181 if ((SLM & Mask) == 0)
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000182 continue;
183 }
184
185 // Determine the actual place of the use.
186 const MachineInstr *MI = MO.getParent();
187 unsigned OpNo = (&MO - &MI->getOperand(0));
188 SlotIndex UseIdx;
189 if (MI->isPHI()) {
190 assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
191 // The actual place where a phi operand is used is the end of the pred
192 // MBB. PHI operands are paired: (Reg, PredMBB).
193 UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB());
194 } else {
195 // Check for early-clobber redefs.
196 bool isEarlyClobber = false;
197 unsigned DefIdx;
198 if (MO.isDef())
199 isEarlyClobber = MO.isEarlyClobber();
200 else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
201 // FIXME: This would be a lot easier if tied early-clobber uses also
202 // had an early-clobber flag.
203 isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
204 }
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000205 UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000206 }
207
Jakob Stoklund Olesen989b3b12012-06-05 21:54:09 +0000208 // MI is reading Reg. We may have visited MI before if it happens to be
209 // reading Reg multiple times. That is OK, extend() is idempotent.
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000210 extend(LR, UseIdx, Reg, Undefs);
Jakob Stoklund Olesen989b3b12012-06-05 21:54:09 +0000211 }
212}
213
214
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000215void LiveRangeCalc::updateFromLiveIns() {
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000216 LiveRangeUpdater Updater;
Matthias Braun42fab342014-12-15 19:40:46 +0000217 for (const LiveInBlock &I : LiveIn) {
218 if (!I.DomNode)
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000219 continue;
Matthias Braun42fab342014-12-15 19:40:46 +0000220 MachineBasicBlock *MBB = I.DomNode->getBlock();
221 assert(I.Value && "No live-in value found");
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000222 SlotIndex Start, End;
Benjamin Kramerd6f1f842014-03-02 13:30:33 +0000223 std::tie(Start, End) = Indexes->getMBBRange(MBB);
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000224
Matthias Braun42fab342014-12-15 19:40:46 +0000225 if (I.Kill.isValid())
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000226 // Value is killed inside this block.
Matthias Braun42fab342014-12-15 19:40:46 +0000227 End = I.Kill;
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000228 else {
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000229 // The value is live-through, update LiveOut as well.
230 // Defer the Domtree lookup until it is needed.
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000231 assert(Seen.test(MBB->getNumber()));
232 Map[MBB] = LiveOutPair(I.Value, nullptr);
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000233 }
Matthias Braun42fab342014-12-15 19:40:46 +0000234 Updater.setDest(&I.LR);
235 Updater.add(Start, End, I.Value);
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000236 }
237 LiveIn.clear();
238}
239
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000240void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
241 ArrayRef<SlotIndex> Undefs) {
Matthias Braun11042c82015-02-18 01:50:52 +0000242 assert(Use.isValid() && "Invalid SlotIndex");
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000243 assert(Indexes && "Missing SlotIndexes");
244 assert(DomTree && "Missing dominator tree");
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000245
Matthias Braun11042c82015-02-18 01:50:52 +0000246 MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
247 assert(UseMBB && "No MBB at Use");
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000248
249 // Is there a def in the same MBB we can extend?
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000250 auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
251 if (EP.first != nullptr || EP.second)
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000252 return;
253
Matthias Braun11042c82015-02-18 01:50:52 +0000254 // Find the single reaching def, or determine if Use is jointly dominated by
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000255 // multiple values, and we may need to create even more phi-defs to preserve
256 // VNInfo SSA form. Perform a search for all predecessor blocks where we
257 // know the dominating VNInfo.
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000258 if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000259 return;
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000260
261 // When there were multiple different values, we may need new PHIs.
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000262 calculateValues();
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000263}
264
265
266// This function is called by a client after using the low-level API to add
267// live-out and live-in blocks. The unique value optimization is not
268// available, SplitEditor::transferValues handles that case directly anyway.
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000269void LiveRangeCalc::calculateValues() {
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000270 assert(Indexes && "Missing SlotIndexes");
271 assert(DomTree && "Missing dominator tree");
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000272 updateSSA();
273 updateFromLiveIns();
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000274}
275
276
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000277bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
278 MachineBasicBlock &MBB, BitVector &DefOnEntry,
279 BitVector &UndefOnEntry) {
280 unsigned BN = MBB.getNumber();
281 if (DefOnEntry[BN])
282 return true;
283 if (UndefOnEntry[BN])
284 return false;
285
286 auto MarkDefined =
287 [this,BN,&DefOnEntry,&UndefOnEntry] (MachineBasicBlock &B) -> bool {
288 for (MachineBasicBlock *S : B.successors())
289 DefOnEntry[S->getNumber()] = true;
290 DefOnEntry[BN] = true;
291 return true;
292 };
293
294 SetVector<unsigned> WorkList;
295 // Checking if the entry of MBB is reached by some def: add all predecessors
296 // that are potentially defined-on-exit to the work list.
297 for (MachineBasicBlock *P : MBB.predecessors())
298 WorkList.insert(P->getNumber());
299
300 for (unsigned i = 0; i != WorkList.size(); ++i) {
301 // Determine if the exit from the block is reached by some def.
302 unsigned N = WorkList[i];
303 MachineBasicBlock &B = *MF->getBlockNumbered(N);
304 if (Seen[N] && Map[&B].first != nullptr)
305 return MarkDefined(B);
306 SlotIndex Begin, End;
307 std::tie(Begin, End) = Indexes->getMBBRange(&B);
308 LiveRange::iterator UB = std::upper_bound(LR.begin(), LR.end(), End);
309 if (UB != LR.begin()) {
310 LiveRange::Segment &Seg = *std::prev(UB);
311 if (Seg.end > Begin) {
312 // There is a segment that overlaps B. If the range is not explicitly
313 // undefined between the end of the segment and the end of the block,
314 // treat the block as defined on exit. If it is, go to the next block
315 // on the work list.
316 if (LR.isUndefIn(Undefs, Seg.end, End))
317 continue;
318 return MarkDefined(B);
319 }
320 }
321
322 // No segment overlaps with this block. If this block is not defined on
323 // entry, or it undefines the range, do not process its predecessors.
324 if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
325 UndefOnEntry[N] = true;
326 continue;
327 }
328 if (DefOnEntry[N])
329 return MarkDefined(B);
330
331 // Still don't know: add all predecessors to the work list.
332 for (MachineBasicBlock *P : B.predecessors())
333 WorkList.insert(P->getNumber());
334 }
335
336 UndefOnEntry[BN] = true;
337 return false;
338}
339
Matthias Braun11042c82015-02-18 01:50:52 +0000340bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000341 SlotIndex Use, unsigned PhysReg,
342 ArrayRef<SlotIndex> Undefs) {
Matthias Braun11042c82015-02-18 01:50:52 +0000343 unsigned UseMBBNum = UseMBB.getNumber();
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000344
Matthias Braun2d5c32b2013-10-10 21:28:57 +0000345 // Block numbers where LR should be live-in.
Matthias Braun11042c82015-02-18 01:50:52 +0000346 SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000347
348 // Remember if we have seen more than one value.
349 bool UniqueVNI = true;
Craig Topperc0196b12014-04-14 00:51:57 +0000350 VNInfo *TheVNI = nullptr;
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000351
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000352 bool FoundUndef = false;
353
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000354 // Using Seen as a visited set, perform a BFS for all reaching defs.
355 for (unsigned i = 0; i != WorkList.size(); ++i) {
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000356 MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
Jakob Stoklund Olesen3d604ab2012-07-13 23:39:05 +0000357
358#ifndef NDEBUG
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000359 if (Undefs.size() > 0 && MBB->pred_empty()) {
Jakob Stoklund Olesen3d604ab2012-07-13 23:39:05 +0000360 MBB->getParent()->verify();
Matthias Braun53917542015-05-11 18:47:47 +0000361 errs() << "Use of " << PrintReg(PhysReg)
362 << " does not have a corresponding definition on every path:\n";
363 const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
364 if (MI != nullptr)
365 errs() << Use << " " << *MI;
Jakob Stoklund Olesen3d604ab2012-07-13 23:39:05 +0000366 llvm_unreachable("Use not jointly dominated by defs.");
367 }
368
369 if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
370 !MBB->isLiveIn(PhysReg)) {
371 MBB->getParent()->verify();
Matthias Braun53917542015-05-11 18:47:47 +0000372 errs() << "The register " << PrintReg(PhysReg)
373 << " needs to be live in to BB#" << MBB->getNumber()
Jakob Stoklund Olesen3d604ab2012-07-13 23:39:05 +0000374 << ", but is missing from the live-in list.\n";
375 llvm_unreachable("Invalid global physical register");
376 }
377#endif
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000378 FoundUndef |= MBB->pred_empty();
Jakob Stoklund Olesen3d604ab2012-07-13 23:39:05 +0000379
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000380 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
Matthias Braun2d5c32b2013-10-10 21:28:57 +0000381 PE = MBB->pred_end(); PI != PE; ++PI) {
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000382 MachineBasicBlock *Pred = *PI;
383
384 // Is this a known live-out block?
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000385 if (Seen.test(Pred->getNumber())) {
386 if (VNInfo *VNI = Map[Pred].first) {
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000387 if (TheVNI && TheVNI != VNI)
388 UniqueVNI = false;
389 TheVNI = VNI;
390 }
391 continue;
392 }
393
394 SlotIndex Start, End;
Benjamin Kramerd6f1f842014-03-02 13:30:33 +0000395 std::tie(Start, End) = Indexes->getMBBRange(Pred);
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000396
397 // First time we see Pred. Try to determine the live-out value, but set
398 // it as null if Pred is live-through with an unknown value.
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000399 auto EP = LR.extendInBlock(Undefs, Start, End);
400 VNInfo *VNI = EP.first;
401 FoundUndef |= EP.second;
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000402 setLiveOutValue(Pred, VNI);
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000403 if (VNI) {
404 if (TheVNI && TheVNI != VNI)
405 UniqueVNI = false;
406 TheVNI = VNI;
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000407 }
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000408 if (VNI || EP.second)
409 continue;
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000410
411 // No, we need a live-in value for Pred as well
Matthias Braun11042c82015-02-18 01:50:52 +0000412 if (Pred != &UseMBB)
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000413 WorkList.push_back(Pred->getNumber());
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000414 else
Matthias Braun11042c82015-02-18 01:50:52 +0000415 // Loopback to UseMBB, so value is really live through.
416 Use = SlotIndex();
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000417 }
418 }
419
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000420 LiveIn.clear();
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000421 FoundUndef |= (TheVNI == nullptr);
422 if (Undefs.size() > 0 && FoundUndef)
423 UniqueVNI = false;
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000424
425 // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
426 // neither require it. Skip the sorting overhead for small updates.
427 if (WorkList.size() > 4)
428 array_pod_sort(WorkList.begin(), WorkList.end());
429
430 // If a unique reaching def was found, blit in the live ranges immediately.
431 if (UniqueVNI) {
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000432 assert(TheVNI != nullptr);
Matthias Braun2d5c32b2013-10-10 21:28:57 +0000433 LiveRangeUpdater Updater(&LR);
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000434 for (unsigned BN : WorkList) {
435 SlotIndex Start, End;
436 std::tie(Start, End) = Indexes->getMBBRange(BN);
437 // Trim the live range in UseMBB.
438 if (BN == UseMBBNum && Use.isValid())
439 End = Use;
440 else
441 Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
442 Updater.add(Start, End, TheVNI);
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000443 }
444 return true;
445 }
446
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000447 // Prepare the defined/undefined bit vectors.
448 auto EF = EntryInfoMap.find(&LR);
449 if (EF == EntryInfoMap.end()) {
450 unsigned N = MF->getNumBlockIDs();
451 EF = EntryInfoMap.insert({&LR, {BitVector(), BitVector()}}).first;
452 EF->second.first.resize(N);
453 EF->second.second.resize(N);
454 }
455 BitVector &DefOnEntry = EF->second.first;
456 BitVector &UndefOnEntry = EF->second.second;
457
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000458 // Multiple values were found, so transfer the work list to the LiveIn array
459 // where UpdateSSA will use it as a work list.
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000460 LiveIn.reserve(WorkList.size());
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000461 for (unsigned BN : WorkList) {
462 MachineBasicBlock *MBB = MF->getBlockNumbered(BN);
463 if (Undefs.size() > 0 && !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
464 continue;
Matthias Braun2d5c32b2013-10-10 21:28:57 +0000465 addLiveInBlock(LR, DomTree->getNode(MBB));
Matthias Braun11042c82015-02-18 01:50:52 +0000466 if (MBB == &UseMBB)
467 LiveIn.back().Kill = Use;
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000468 }
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000469
Jakob Stoklund Olesenb3892712013-02-20 23:08:26 +0000470 return false;
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000471}
472
473
474// This is essentially the same iterative algorithm that SSAUpdater uses,
475// except we already have a dominator tree, so we don't have to recompute it.
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000476void LiveRangeCalc::updateSSA() {
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000477 assert(Indexes && "Missing SlotIndexes");
478 assert(DomTree && "Missing dominator tree");
479
480 // Interate until convergence.
481 unsigned Changes;
482 do {
483 Changes = 0;
484 // Propagate live-out values down the dominator tree, inserting phi-defs
485 // when necessary.
Matthias Braun42fab342014-12-15 19:40:46 +0000486 for (LiveInBlock &I : LiveIn) {
487 MachineDomTreeNode *Node = I.DomNode;
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000488 // Skip block if the live-in value has already been determined.
489 if (!Node)
490 continue;
491 MachineBasicBlock *MBB = Node->getBlock();
492 MachineDomTreeNode *IDom = Node->getIDom();
493 LiveOutPair IDomValue;
494
495 // We need a live-in value to a block with no immediate dominator?
496 // This is probably an unreachable block that has survived somehow.
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000497 bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000498
499 // IDom dominates all of our predecessors, but it may not be their
500 // immediate dominator. Check if any of them have live-out values that are
501 // properly dominated by IDom. If so, we need a phi-def here.
502 if (!needPHI) {
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000503 IDomValue = Map[IDom->getBlock()];
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000504
505 // Cache the DomTree node that defined the value.
506 if (IDomValue.first && !IDomValue.second)
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000507 Map[IDom->getBlock()].second = IDomValue.second =
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000508 DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
509
510 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
511 PE = MBB->pred_end(); PI != PE; ++PI) {
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000512 LiveOutPair &Value = Map[*PI];
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000513 if (!Value.first || Value.first == IDomValue.first)
514 continue;
515
516 // Cache the DomTree node that defined the value.
517 if (!Value.second)
518 Value.second =
519 DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
520
521 // This predecessor is carrying something other than IDomValue.
522 // It could be because IDomValue hasn't propagated yet, or it could be
523 // because MBB is in the dominance frontier of that value.
524 if (DomTree->dominates(IDom, Value.second)) {
525 needPHI = true;
526 break;
527 }
528 }
529 }
530
531 // The value may be live-through even if Kill is set, as can happen when
532 // we are called from extendRange. In that case LiveOutSeen is true, and
533 // LiveOut indicates a foreign or missing value.
Matthias Braun1aed6ff2014-12-16 04:03:38 +0000534 LiveOutPair &LOP = Map[MBB];
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000535
536 // Create a phi-def if required.
537 if (needPHI) {
538 ++Changes;
539 assert(Alloc && "Need VNInfo allocator to create PHI-defs");
540 SlotIndex Start, End;
Benjamin Kramerd6f1f842014-03-02 13:30:33 +0000541 std::tie(Start, End) = Indexes->getMBBRange(MBB);
Matthias Braun42fab342014-12-15 19:40:46 +0000542 LiveRange &LR = I.LR;
Matthias Braun2d5c32b2013-10-10 21:28:57 +0000543 VNInfo *VNI = LR.getNextValue(Start, *Alloc);
Matthias Braun42fab342014-12-15 19:40:46 +0000544 I.Value = VNI;
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000545 // This block is done, we know the final value.
Matthias Braun42fab342014-12-15 19:40:46 +0000546 I.DomNode = nullptr;
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000547
Matthias Braun2f662322014-12-10 01:12:12 +0000548 // Add liveness since updateFromLiveIns now skips this node.
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000549 if (I.Kill.isValid()) {
550 if (VNI)
551 LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
552 } else {
553 if (VNI)
554 LR.addSegment(LiveInterval::Segment(Start, End, VNI));
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000555 LOP = LiveOutPair(VNI, Node);
556 }
557 } else if (IDomValue.first) {
558 // No phi-def here. Remember incoming value.
Matthias Braun42fab342014-12-15 19:40:46 +0000559 I.Value = IDomValue.first;
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000560
561 // If the IDomValue is killed in the block, don't propagate through.
Matthias Braun42fab342014-12-15 19:40:46 +0000562 if (I.Kill.isValid())
Jakob Stoklund Olesen487f2a32011-09-13 01:34:21 +0000563 continue;
564
565 // Propagate IDomValue if it isn't killed:
566 // MBB is live-out and doesn't define its own value.
567 if (LOP.first == IDomValue.first)
568 continue;
569 ++Changes;
570 LOP = IDomValue;
571 }
572 }
573 } while (Changes);
574}