File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/GenericDomTree.h |
Warning: | line 494, column 12 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- SplitKit.cpp - Toolkit for splitting live ranges -------------------===// | |||
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 | // This file contains the SplitAnalysis class as well as mutator functions for | |||
10 | // live range splitting. | |||
11 | // | |||
12 | //===----------------------------------------------------------------------===// | |||
13 | ||||
14 | #include "SplitKit.h" | |||
15 | #include "llvm/ADT/None.h" | |||
16 | #include "llvm/ADT/STLExtras.h" | |||
17 | #include "llvm/ADT/Statistic.h" | |||
18 | #include "llvm/Analysis/AliasAnalysis.h" | |||
19 | #include "llvm/CodeGen/LiveRangeEdit.h" | |||
20 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" | |||
21 | #include "llvm/CodeGen/MachineDominators.h" | |||
22 | #include "llvm/CodeGen/MachineInstr.h" | |||
23 | #include "llvm/CodeGen/MachineInstrBuilder.h" | |||
24 | #include "llvm/CodeGen/MachineLoopInfo.h" | |||
25 | #include "llvm/CodeGen/MachineOperand.h" | |||
26 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |||
27 | #include "llvm/CodeGen/TargetInstrInfo.h" | |||
28 | #include "llvm/CodeGen/TargetOpcodes.h" | |||
29 | #include "llvm/CodeGen/TargetRegisterInfo.h" | |||
30 | #include "llvm/CodeGen/TargetSubtargetInfo.h" | |||
31 | #include "llvm/CodeGen/VirtRegMap.h" | |||
32 | #include "llvm/Config/llvm-config.h" | |||
33 | #include "llvm/IR/DebugLoc.h" | |||
34 | #include "llvm/Support/Allocator.h" | |||
35 | #include "llvm/Support/BlockFrequency.h" | |||
36 | #include "llvm/Support/Debug.h" | |||
37 | #include "llvm/Support/ErrorHandling.h" | |||
38 | #include "llvm/Support/raw_ostream.h" | |||
39 | #include <algorithm> | |||
40 | #include <cassert> | |||
41 | #include <iterator> | |||
42 | #include <limits> | |||
43 | #include <tuple> | |||
44 | ||||
45 | using namespace llvm; | |||
46 | ||||
47 | #define DEBUG_TYPE"regalloc" "regalloc" | |||
48 | ||||
49 | STATISTIC(NumFinished, "Number of splits finished")static llvm::Statistic NumFinished = {"regalloc", "NumFinished" , "Number of splits finished"}; | |||
50 | STATISTIC(NumSimple, "Number of splits that were simple")static llvm::Statistic NumSimple = {"regalloc", "NumSimple", "Number of splits that were simple" }; | |||
51 | STATISTIC(NumCopies, "Number of copies inserted for splitting")static llvm::Statistic NumCopies = {"regalloc", "NumCopies", "Number of copies inserted for splitting" }; | |||
52 | STATISTIC(NumRemats, "Number of rematerialized defs for splitting")static llvm::Statistic NumRemats = {"regalloc", "NumRemats", "Number of rematerialized defs for splitting" }; | |||
53 | STATISTIC(NumRepairs, "Number of invalid live ranges repaired")static llvm::Statistic NumRepairs = {"regalloc", "NumRepairs" , "Number of invalid live ranges repaired"}; | |||
54 | ||||
55 | //===----------------------------------------------------------------------===// | |||
56 | // Last Insert Point Analysis | |||
57 | //===----------------------------------------------------------------------===// | |||
58 | ||||
59 | InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis, | |||
60 | unsigned BBNum) | |||
61 | : LIS(lis), LastInsertPoint(BBNum) {} | |||
62 | ||||
63 | SlotIndex | |||
64 | InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI, | |||
65 | const MachineBasicBlock &MBB) { | |||
66 | unsigned Num = MBB.getNumber(); | |||
67 | std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num]; | |||
68 | SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB); | |||
69 | ||||
70 | SmallVector<const MachineBasicBlock *, 1> ExceptionalSuccessors; | |||
71 | bool EHPadSuccessor = false; | |||
72 | for (const MachineBasicBlock *SMBB : MBB.successors()) { | |||
73 | if (SMBB->isEHPad()) { | |||
74 | ExceptionalSuccessors.push_back(SMBB); | |||
75 | EHPadSuccessor = true; | |||
76 | } else if (SMBB->isInlineAsmBrIndirectTarget()) | |||
77 | ExceptionalSuccessors.push_back(SMBB); | |||
78 | } | |||
79 | ||||
80 | // Compute insert points on the first call. The pair is independent of the | |||
81 | // current live interval. | |||
82 | if (!LIP.first.isValid()) { | |||
83 | MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator(); | |||
84 | if (FirstTerm == MBB.end()) | |||
85 | LIP.first = MBBEnd; | |||
86 | else | |||
87 | LIP.first = LIS.getInstructionIndex(*FirstTerm); | |||
88 | ||||
89 | // If there is a landing pad or inlineasm_br successor, also find the | |||
90 | // instruction. If there is no such instruction, we don't need to do | |||
91 | // anything special. We assume there cannot be multiple instructions that | |||
92 | // are Calls with EHPad successors or INLINEASM_BR in a block. Further, we | |||
93 | // assume that if there are any, they will be after any other call | |||
94 | // instructions in the block. | |||
95 | if (ExceptionalSuccessors.empty()) | |||
96 | return LIP.first; | |||
97 | for (const MachineInstr &MI : llvm::reverse(MBB)) { | |||
98 | if ((EHPadSuccessor && MI.isCall()) || | |||
99 | MI.getOpcode() == TargetOpcode::INLINEASM_BR) { | |||
100 | LIP.second = LIS.getInstructionIndex(MI); | |||
101 | break; | |||
102 | } | |||
103 | } | |||
104 | } | |||
105 | ||||
106 | // If CurLI is live into a landing pad successor, move the last insert point | |||
107 | // back to the call that may throw. | |||
108 | if (!LIP.second) | |||
109 | return LIP.first; | |||
110 | ||||
111 | if (none_of(ExceptionalSuccessors, [&](const MachineBasicBlock *EHPad) { | |||
112 | return LIS.isLiveInToMBB(CurLI, EHPad); | |||
113 | })) | |||
114 | return LIP.first; | |||
115 | ||||
116 | // Find the value leaving MBB. | |||
117 | const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd); | |||
118 | if (!VNI) | |||
119 | return LIP.first; | |||
120 | ||||
121 | // The def of statepoint instruction is a gc relocation and it should be alive | |||
122 | // in landing pad. So we cannot split interval after statepoint instruction. | |||
123 | if (SlotIndex::isSameInstr(VNI->def, LIP.second)) | |||
124 | if (auto *I = LIS.getInstructionFromIndex(LIP.second)) | |||
125 | if (I->getOpcode() == TargetOpcode::STATEPOINT) | |||
126 | return LIP.second; | |||
127 | ||||
128 | // If the value leaving MBB was defined after the call in MBB, it can't | |||
129 | // really be live-in to the landing pad. This can happen if the landing pad | |||
130 | // has a PHI, and this register is undef on the exceptional edge. | |||
131 | // <rdar://problem/10664933> | |||
132 | if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd) | |||
133 | return LIP.first; | |||
134 | ||||
135 | // Value is properly live-in to the landing pad. | |||
136 | // Only allow inserts before the call. | |||
137 | return LIP.second; | |||
138 | } | |||
139 | ||||
140 | MachineBasicBlock::iterator | |||
141 | InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI, | |||
142 | MachineBasicBlock &MBB) { | |||
143 | SlotIndex LIP = getLastInsertPoint(CurLI, MBB); | |||
144 | if (LIP == LIS.getMBBEndIdx(&MBB)) | |||
145 | return MBB.end(); | |||
146 | return LIS.getInstructionFromIndex(LIP); | |||
147 | } | |||
148 | ||||
149 | //===----------------------------------------------------------------------===// | |||
150 | // Split Analysis | |||
151 | //===----------------------------------------------------------------------===// | |||
152 | ||||
153 | SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, | |||
154 | const MachineLoopInfo &mli) | |||
155 | : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli), | |||
156 | TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {} | |||
157 | ||||
158 | void SplitAnalysis::clear() { | |||
159 | UseSlots.clear(); | |||
160 | UseBlocks.clear(); | |||
161 | ThroughBlocks.clear(); | |||
162 | CurLI = nullptr; | |||
163 | DidRepairRange = false; | |||
164 | } | |||
165 | ||||
166 | /// analyzeUses - Count instructions, basic blocks, and loops using CurLI. | |||
167 | void SplitAnalysis::analyzeUses() { | |||
168 | assert(UseSlots.empty() && "Call clear first")((void)0); | |||
169 | ||||
170 | // First get all the defs from the interval values. This provides the correct | |||
171 | // slots for early clobbers. | |||
172 | for (const VNInfo *VNI : CurLI->valnos) | |||
173 | if (!VNI->isPHIDef() && !VNI->isUnused()) | |||
174 | UseSlots.push_back(VNI->def); | |||
175 | ||||
176 | // Get use slots form the use-def chain. | |||
177 | const MachineRegisterInfo &MRI = MF.getRegInfo(); | |||
178 | for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg())) | |||
179 | if (!MO.isUndef()) | |||
180 | UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot()); | |||
181 | ||||
182 | array_pod_sort(UseSlots.begin(), UseSlots.end()); | |||
183 | ||||
184 | // Remove duplicates, keeping the smaller slot for each instruction. | |||
185 | // That is what we want for early clobbers. | |||
186 | UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), | |||
187 | SlotIndex::isSameInstr), | |||
188 | UseSlots.end()); | |||
189 | ||||
190 | // Compute per-live block info. | |||
191 | if (!calcLiveBlockInfo()) { | |||
192 | // FIXME: calcLiveBlockInfo found inconsistencies in the live range. | |||
193 | // I am looking at you, RegisterCoalescer! | |||
194 | DidRepairRange = true; | |||
195 | ++NumRepairs; | |||
196 | LLVM_DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n")do { } while (false); | |||
197 | const_cast<LiveIntervals&>(LIS) | |||
198 | .shrinkToUses(const_cast<LiveInterval*>(CurLI)); | |||
199 | UseBlocks.clear(); | |||
200 | ThroughBlocks.clear(); | |||
201 | bool fixed = calcLiveBlockInfo(); | |||
202 | (void)fixed; | |||
203 | assert(fixed && "Couldn't fix broken live interval")((void)0); | |||
204 | } | |||
205 | ||||
206 | LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots.size() << " instrs in "do { } while (false) | |||
207 | << UseBlocks.size() << " blocks, through "do { } while (false) | |||
208 | << NumThroughBlocks << " blocks.\n")do { } while (false); | |||
209 | } | |||
210 | ||||
211 | /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks | |||
212 | /// where CurLI is live. | |||
213 | bool SplitAnalysis::calcLiveBlockInfo() { | |||
214 | ThroughBlocks.resize(MF.getNumBlockIDs()); | |||
215 | NumThroughBlocks = NumGapBlocks = 0; | |||
216 | if (CurLI->empty()) | |||
217 | return true; | |||
218 | ||||
219 | LiveInterval::const_iterator LVI = CurLI->begin(); | |||
220 | LiveInterval::const_iterator LVE = CurLI->end(); | |||
221 | ||||
222 | SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; | |||
223 | UseI = UseSlots.begin(); | |||
224 | UseE = UseSlots.end(); | |||
225 | ||||
226 | // Loop over basic blocks where CurLI is live. | |||
227 | MachineFunction::iterator MFI = | |||
228 | LIS.getMBBFromIndex(LVI->start)->getIterator(); | |||
229 | while (true) { | |||
230 | BlockInfo BI; | |||
231 | BI.MBB = &*MFI; | |||
232 | SlotIndex Start, Stop; | |||
233 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); | |||
234 | ||||
235 | // If the block contains no uses, the range must be live through. At one | |||
236 | // point, RegisterCoalescer could create dangling ranges that ended | |||
237 | // mid-block. | |||
238 | if (UseI == UseE || *UseI >= Stop) { | |||
239 | ++NumThroughBlocks; | |||
240 | ThroughBlocks.set(BI.MBB->getNumber()); | |||
241 | // The range shouldn't end mid-block if there are no uses. This shouldn't | |||
242 | // happen. | |||
243 | if (LVI->end < Stop) | |||
244 | return false; | |||
245 | } else { | |||
246 | // This block has uses. Find the first and last uses in the block. | |||
247 | BI.FirstInstr = *UseI; | |||
248 | assert(BI.FirstInstr >= Start)((void)0); | |||
249 | do ++UseI; | |||
250 | while (UseI != UseE && *UseI < Stop); | |||
251 | BI.LastInstr = UseI[-1]; | |||
252 | assert(BI.LastInstr < Stop)((void)0); | |||
253 | ||||
254 | // LVI is the first live segment overlapping MBB. | |||
255 | BI.LiveIn = LVI->start <= Start; | |||
256 | ||||
257 | // When not live in, the first use should be a def. | |||
258 | if (!BI.LiveIn) { | |||
259 | assert(LVI->start == LVI->valno->def && "Dangling Segment start")((void)0); | |||
260 | assert(LVI->start == BI.FirstInstr && "First instr should be a def")((void)0); | |||
261 | BI.FirstDef = BI.FirstInstr; | |||
262 | } | |||
263 | ||||
264 | // Look for gaps in the live range. | |||
265 | BI.LiveOut = true; | |||
266 | while (LVI->end < Stop) { | |||
267 | SlotIndex LastStop = LVI->end; | |||
268 | if (++LVI == LVE || LVI->start >= Stop) { | |||
269 | BI.LiveOut = false; | |||
270 | BI.LastInstr = LastStop; | |||
271 | break; | |||
272 | } | |||
273 | ||||
274 | if (LastStop < LVI->start) { | |||
275 | // There is a gap in the live range. Create duplicate entries for the | |||
276 | // live-in snippet and the live-out snippet. | |||
277 | ++NumGapBlocks; | |||
278 | ||||
279 | // Push the Live-in part. | |||
280 | BI.LiveOut = false; | |||
281 | UseBlocks.push_back(BI); | |||
282 | UseBlocks.back().LastInstr = LastStop; | |||
283 | ||||
284 | // Set up BI for the live-out part. | |||
285 | BI.LiveIn = false; | |||
286 | BI.LiveOut = true; | |||
287 | BI.FirstInstr = BI.FirstDef = LVI->start; | |||
288 | } | |||
289 | ||||
290 | // A Segment that starts in the middle of the block must be a def. | |||
291 | assert(LVI->start == LVI->valno->def && "Dangling Segment start")((void)0); | |||
292 | if (!BI.FirstDef) | |||
293 | BI.FirstDef = LVI->start; | |||
294 | } | |||
295 | ||||
296 | UseBlocks.push_back(BI); | |||
297 | ||||
298 | // LVI is now at LVE or LVI->end >= Stop. | |||
299 | if (LVI == LVE) | |||
300 | break; | |||
301 | } | |||
302 | ||||
303 | // Live segment ends exactly at Stop. Move to the next segment. | |||
304 | if (LVI->end == Stop && ++LVI == LVE) | |||
305 | break; | |||
306 | ||||
307 | // Pick the next basic block. | |||
308 | if (LVI->start < Stop) | |||
309 | ++MFI; | |||
310 | else | |||
311 | MFI = LIS.getMBBFromIndex(LVI->start)->getIterator(); | |||
312 | } | |||
313 | ||||
314 | assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count")((void)0); | |||
315 | return true; | |||
316 | } | |||
317 | ||||
318 | unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { | |||
319 | if (cli->empty()) | |||
320 | return 0; | |||
321 | LiveInterval *li = const_cast<LiveInterval*>(cli); | |||
322 | LiveInterval::iterator LVI = li->begin(); | |||
323 | LiveInterval::iterator LVE = li->end(); | |||
324 | unsigned Count = 0; | |||
325 | ||||
326 | // Loop over basic blocks where li is live. | |||
327 | MachineFunction::const_iterator MFI = | |||
328 | LIS.getMBBFromIndex(LVI->start)->getIterator(); | |||
329 | SlotIndex Stop = LIS.getMBBEndIdx(&*MFI); | |||
330 | while (true) { | |||
331 | ++Count; | |||
332 | LVI = li->advanceTo(LVI, Stop); | |||
333 | if (LVI == LVE) | |||
334 | return Count; | |||
335 | do { | |||
336 | ++MFI; | |||
337 | Stop = LIS.getMBBEndIdx(&*MFI); | |||
338 | } while (Stop <= LVI->start); | |||
339 | } | |||
340 | } | |||
341 | ||||
342 | bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { | |||
343 | unsigned OrigReg = VRM.getOriginal(CurLI->reg()); | |||
344 | const LiveInterval &Orig = LIS.getInterval(OrigReg); | |||
345 | assert(!Orig.empty() && "Splitting empty interval?")((void)0); | |||
346 | LiveInterval::const_iterator I = Orig.find(Idx); | |||
347 | ||||
348 | // Range containing Idx should begin at Idx. | |||
349 | if (I != Orig.end() && I->start <= Idx) | |||
350 | return I->start == Idx; | |||
351 | ||||
352 | // Range does not contain Idx, previous must end at Idx. | |||
353 | return I != Orig.begin() && (--I)->end == Idx; | |||
354 | } | |||
355 | ||||
356 | void SplitAnalysis::analyze(const LiveInterval *li) { | |||
357 | clear(); | |||
358 | CurLI = li; | |||
359 | analyzeUses(); | |||
360 | } | |||
361 | ||||
362 | //===----------------------------------------------------------------------===// | |||
363 | // Split Editor | |||
364 | //===----------------------------------------------------------------------===// | |||
365 | ||||
366 | /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. | |||
367 | SplitEditor::SplitEditor(SplitAnalysis &SA, AliasAnalysis &AA, | |||
368 | LiveIntervals &LIS, VirtRegMap &VRM, | |||
369 | MachineDominatorTree &MDT, | |||
370 | MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI) | |||
371 | : SA(SA), AA(AA), LIS(LIS), VRM(VRM), | |||
372 | MRI(VRM.getMachineFunction().getRegInfo()), MDT(MDT), | |||
373 | TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()), | |||
374 | TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()), | |||
375 | MBFI(MBFI), VRAI(VRAI), RegAssign(Allocator) {} | |||
376 | ||||
377 | void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { | |||
378 | Edit = &LRE; | |||
379 | SpillMode = SM; | |||
380 | OpenIdx = 0; | |||
381 | RegAssign.clear(); | |||
382 | Values.clear(); | |||
383 | ||||
384 | // Reset the LiveIntervalCalc instances needed for this spill mode. | |||
385 | LICalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, | |||
386 | &LIS.getVNInfoAllocator()); | |||
387 | if (SpillMode) | |||
388 | LICalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, | |||
389 | &LIS.getVNInfoAllocator()); | |||
390 | ||||
391 | // We don't need an AliasAnalysis since we will only be performing | |||
392 | // cheap-as-a-copy remats anyway. | |||
393 | Edit->anyRematerializable(nullptr); | |||
394 | } | |||
395 | ||||
396 | #if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP) | |||
397 | LLVM_DUMP_METHOD__attribute__((noinline)) void SplitEditor::dump() const { | |||
398 | if (RegAssign.empty()) { | |||
399 | dbgs() << " empty\n"; | |||
400 | return; | |||
401 | } | |||
402 | ||||
403 | for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) | |||
404 | dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); | |||
405 | dbgs() << '\n'; | |||
406 | } | |||
407 | #endif | |||
408 | ||||
409 | LiveInterval::SubRange &SplitEditor::getSubRangeForMaskExact(LaneBitmask LM, | |||
410 | LiveInterval &LI) { | |||
411 | for (LiveInterval::SubRange &S : LI.subranges()) | |||
412 | if (S.LaneMask == LM) | |||
413 | return S; | |||
414 | llvm_unreachable("SubRange for this mask not found")__builtin_unreachable(); | |||
415 | } | |||
416 | ||||
417 | LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM, | |||
418 | LiveInterval &LI) { | |||
419 | for (LiveInterval::SubRange &S : LI.subranges()) | |||
420 | if ((S.LaneMask & LM) == LM) | |||
421 | return S; | |||
422 | llvm_unreachable("SubRange for this mask not found")__builtin_unreachable(); | |||
423 | } | |||
424 | ||||
425 | void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) { | |||
426 | if (!LI.hasSubRanges()) { | |||
427 | LI.createDeadDef(VNI); | |||
428 | return; | |||
429 | } | |||
430 | ||||
431 | SlotIndex Def = VNI->def; | |||
432 | if (Original) { | |||
433 | // If we are transferring a def from the original interval, make sure | |||
434 | // to only update the subranges for which the original subranges had | |||
435 | // a def at this location. | |||
436 | for (LiveInterval::SubRange &S : LI.subranges()) { | |||
437 | auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent()); | |||
438 | VNInfo *PV = PS.getVNInfoAt(Def); | |||
439 | if (PV != nullptr && PV->def == Def) | |||
440 | S.createDeadDef(Def, LIS.getVNInfoAllocator()); | |||
441 | } | |||
442 | } else { | |||
443 | // This is a new def: either from rematerialization, or from an inserted | |||
444 | // copy. Since rematerialization can regenerate a definition of a sub- | |||
445 | // register, we need to check which subranges need to be updated. | |||
446 | const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def); | |||
447 | assert(DefMI != nullptr)((void)0); | |||
448 | LaneBitmask LM; | |||
449 | for (const MachineOperand &DefOp : DefMI->defs()) { | |||
450 | Register R = DefOp.getReg(); | |||
451 | if (R != LI.reg()) | |||
452 | continue; | |||
453 | if (unsigned SR = DefOp.getSubReg()) | |||
454 | LM |= TRI.getSubRegIndexLaneMask(SR); | |||
455 | else { | |||
456 | LM = MRI.getMaxLaneMaskForVReg(R); | |||
457 | break; | |||
458 | } | |||
459 | } | |||
460 | for (LiveInterval::SubRange &S : LI.subranges()) | |||
461 | if ((S.LaneMask & LM).any()) | |||
462 | S.createDeadDef(Def, LIS.getVNInfoAllocator()); | |||
463 | } | |||
464 | } | |||
465 | ||||
466 | VNInfo *SplitEditor::defValue(unsigned RegIdx, | |||
467 | const VNInfo *ParentVNI, | |||
468 | SlotIndex Idx, | |||
469 | bool Original) { | |||
470 | assert(ParentVNI && "Mapping NULL value")((void)0); | |||
471 | assert(Idx.isValid() && "Invalid SlotIndex")((void)0); | |||
472 | assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI")((void)0); | |||
473 | LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); | |||
474 | ||||
475 | // Create a new value. | |||
476 | VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator()); | |||
477 | ||||
478 | bool Force = LI->hasSubRanges(); | |||
479 | ValueForcePair FP(Force ? nullptr : VNI, Force); | |||
480 | // Use insert for lookup, so we can add missing values with a second lookup. | |||
481 | std::pair<ValueMap::iterator, bool> InsP = | |||
482 | Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP)); | |||
483 | ||||
484 | // This was the first time (RegIdx, ParentVNI) was mapped, and it is not | |||
485 | // forced. Keep it as a simple def without any liveness. | |||
486 | if (!Force && InsP.second) | |||
487 | return VNI; | |||
488 | ||||
489 | // If the previous value was a simple mapping, add liveness for it now. | |||
490 | if (VNInfo *OldVNI = InsP.first->second.getPointer()) { | |||
491 | addDeadDef(*LI, OldVNI, Original); | |||
492 | ||||
493 | // No longer a simple mapping. Switch to a complex mapping. If the | |||
494 | // interval has subranges, make it a forced mapping. | |||
495 | InsP.first->second = ValueForcePair(nullptr, Force); | |||
496 | } | |||
497 | ||||
498 | // This is a complex mapping, add liveness for VNI | |||
499 | addDeadDef(*LI, VNI, Original); | |||
500 | return VNI; | |||
501 | } | |||
502 | ||||
503 | void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) { | |||
504 | ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)]; | |||
505 | VNInfo *VNI = VFP.getPointer(); | |||
506 | ||||
507 | // ParentVNI was either unmapped or already complex mapped. Either way, just | |||
508 | // set the force bit. | |||
509 | if (!VNI) { | |||
510 | VFP.setInt(true); | |||
511 | return; | |||
512 | } | |||
513 | ||||
514 | // This was previously a single mapping. Make sure the old def is represented | |||
515 | // by a trivial live range. | |||
516 | addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false); | |||
517 | ||||
518 | // Mark as complex mapped, forced. | |||
519 | VFP = ValueForcePair(nullptr, true); | |||
520 | } | |||
521 | ||||
522 | SlotIndex SplitEditor::buildSingleSubRegCopy(Register FromReg, Register ToReg, | |||
523 | MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore, | |||
524 | unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def) { | |||
525 | const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY); | |||
526 | bool FirstCopy = !Def.isValid(); | |||
527 | MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc) | |||
528 | .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy) | |||
529 | | getInternalReadRegState(!FirstCopy), SubIdx) | |||
530 | .addReg(FromReg, 0, SubIdx); | |||
531 | ||||
532 | BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); | |||
533 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); | |||
534 | if (FirstCopy) { | |||
535 | Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot(); | |||
536 | } else { | |||
537 | CopyMI->bundleWithPred(); | |||
538 | } | |||
539 | LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx); | |||
540 | DestLI.refineSubRanges(Allocator, LaneMask, | |||
541 | [Def, &Allocator](LiveInterval::SubRange &SR) { | |||
542 | SR.createDeadDef(Def, Allocator); | |||
543 | }, | |||
544 | Indexes, TRI); | |||
545 | return Def; | |||
546 | } | |||
547 | ||||
548 | SlotIndex SplitEditor::buildCopy(Register FromReg, Register ToReg, | |||
549 | LaneBitmask LaneMask, MachineBasicBlock &MBB, | |||
550 | MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) { | |||
551 | const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY); | |||
552 | if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) { | |||
553 | // The full vreg is copied. | |||
554 | MachineInstr *CopyMI = | |||
555 | BuildMI(MBB, InsertBefore, DebugLoc(), Desc, ToReg).addReg(FromReg); | |||
556 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); | |||
557 | return Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot(); | |||
558 | } | |||
559 | ||||
560 | // Only a subset of lanes needs to be copied. The following is a simple | |||
561 | // heuristic to construct a sequence of COPYs. We could add a target | |||
562 | // specific callback if this turns out to be suboptimal. | |||
563 | LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx)); | |||
564 | ||||
565 | // First pass: Try to find a perfectly matching subregister index. If none | |||
566 | // exists find the one covering the most lanemask bits. | |||
567 | const TargetRegisterClass *RC = MRI.getRegClass(FromReg); | |||
568 | assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class")((void)0); | |||
569 | ||||
570 | SmallVector<unsigned, 8> Indexes; | |||
571 | ||||
572 | // Abort if we cannot possibly implement the COPY with the given indexes. | |||
573 | if (!TRI.getCoveringSubRegIndexes(MRI, RC, LaneMask, Indexes)) | |||
574 | report_fatal_error("Impossible to implement partial COPY"); | |||
575 | ||||
576 | SlotIndex Def; | |||
577 | for (unsigned BestIdx : Indexes) { | |||
578 | Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx, | |||
579 | DestLI, Late, Def); | |||
580 | } | |||
581 | ||||
582 | return Def; | |||
583 | } | |||
584 | ||||
585 | VNInfo *SplitEditor::defFromParent(unsigned RegIdx, | |||
586 | VNInfo *ParentVNI, | |||
587 | SlotIndex UseIdx, | |||
588 | MachineBasicBlock &MBB, | |||
589 | MachineBasicBlock::iterator I) { | |||
590 | SlotIndex Def; | |||
591 | LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); | |||
592 | ||||
593 | // We may be trying to avoid interference that ends at a deleted instruction, | |||
594 | // so always begin RegIdx 0 early and all others late. | |||
595 | bool Late = RegIdx != 0; | |||
596 | ||||
597 | // Attempt cheap-as-a-copy rematerialization. | |||
598 | unsigned Original = VRM.getOriginal(Edit->get(RegIdx)); | |||
599 | LiveInterval &OrigLI = LIS.getInterval(Original); | |||
600 | VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx); | |||
601 | ||||
602 | Register Reg = LI->reg(); | |||
603 | bool DidRemat = false; | |||
604 | if (OrigVNI) { | |||
605 | LiveRangeEdit::Remat RM(ParentVNI); | |||
606 | RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def); | |||
607 | if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) { | |||
608 | Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late); | |||
609 | ++NumRemats; | |||
610 | DidRemat = true; | |||
611 | } | |||
612 | } | |||
613 | if (!DidRemat) { | |||
614 | LaneBitmask LaneMask; | |||
615 | if (OrigLI.hasSubRanges()) { | |||
616 | LaneMask = LaneBitmask::getNone(); | |||
617 | for (LiveInterval::SubRange &S : OrigLI.subranges()) { | |||
618 | if (S.liveAt(UseIdx)) | |||
619 | LaneMask |= S.LaneMask; | |||
620 | } | |||
621 | } else { | |||
622 | LaneMask = LaneBitmask::getAll(); | |||
623 | } | |||
624 | ||||
625 | if (LaneMask.none()) { | |||
626 | const MCInstrDesc &Desc = TII.get(TargetOpcode::IMPLICIT_DEF); | |||
627 | MachineInstr *ImplicitDef = BuildMI(MBB, I, DebugLoc(), Desc, Reg); | |||
628 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); | |||
629 | Def = Indexes.insertMachineInstrInMaps(*ImplicitDef, Late).getRegSlot(); | |||
630 | } else { | |||
631 | ++NumCopies; | |||
632 | Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx); | |||
633 | } | |||
634 | } | |||
635 | ||||
636 | // Define the value in Reg. | |||
637 | return defValue(RegIdx, ParentVNI, Def, false); | |||
638 | } | |||
639 | ||||
640 | /// Create a new virtual register and live interval. | |||
641 | unsigned SplitEditor::openIntv() { | |||
642 | // Create the complement as index 0. | |||
643 | if (Edit->empty()) | |||
644 | Edit->createEmptyInterval(); | |||
645 | ||||
646 | // Create the open interval. | |||
647 | OpenIdx = Edit->size(); | |||
648 | Edit->createEmptyInterval(); | |||
649 | return OpenIdx; | |||
650 | } | |||
651 | ||||
652 | void SplitEditor::selectIntv(unsigned Idx) { | |||
653 | assert(Idx != 0 && "Cannot select the complement interval")((void)0); | |||
654 | assert(Idx < Edit->size() && "Can only select previously opened interval")((void)0); | |||
655 | LLVM_DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n')do { } while (false); | |||
656 | OpenIdx = Idx; | |||
657 | } | |||
658 | ||||
659 | SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { | |||
660 | assert(OpenIdx && "openIntv not called before enterIntvBefore")((void)0); | |||
661 | LLVM_DEBUG(dbgs() << " enterIntvBefore " << Idx)do { } while (false); | |||
662 | Idx = Idx.getBaseIndex(); | |||
663 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); | |||
664 | if (!ParentVNI) { | |||
665 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
666 | return Idx; | |||
667 | } | |||
668 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n')do { } while (false); | |||
669 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); | |||
670 | assert(MI && "enterIntvBefore called with invalid index")((void)0); | |||
671 | ||||
672 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); | |||
673 | return VNI->def; | |||
674 | } | |||
675 | ||||
676 | SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { | |||
677 | assert(OpenIdx && "openIntv not called before enterIntvAfter")((void)0); | |||
678 | LLVM_DEBUG(dbgs() << " enterIntvAfter " << Idx)do { } while (false); | |||
679 | Idx = Idx.getBoundaryIndex(); | |||
680 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); | |||
681 | if (!ParentVNI) { | |||
682 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
683 | return Idx; | |||
684 | } | |||
685 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n')do { } while (false); | |||
686 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); | |||
687 | assert(MI && "enterIntvAfter called with invalid index")((void)0); | |||
688 | ||||
689 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), | |||
690 | std::next(MachineBasicBlock::iterator(MI))); | |||
691 | return VNI->def; | |||
692 | } | |||
693 | ||||
694 | SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { | |||
695 | assert(OpenIdx && "openIntv not called before enterIntvAtEnd")((void)0); | |||
696 | SlotIndex End = LIS.getMBBEndIdx(&MBB); | |||
697 | SlotIndex Last = End.getPrevSlot(); | |||
698 | LLVM_DEBUG(dbgs() << " enterIntvAtEnd " << printMBBReference(MBB) << ", "do { } while (false) | |||
699 | << Last)do { } while (false); | |||
700 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); | |||
701 | if (!ParentVNI) { | |||
702 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
703 | return End; | |||
704 | } | |||
705 | SlotIndex LSP = SA.getLastSplitPoint(&MBB); | |||
706 | if (LSP < Last) { | |||
707 | // It could be that the use after LSP is a def, and thus the ParentVNI | |||
708 | // just selected starts at that def. For this case to exist, the def | |||
709 | // must be part of a tied def/use pair (as otherwise we'd have split | |||
710 | // distinct live ranges into individual live intervals), and thus we | |||
711 | // can insert the def into the VNI of the use and the tied def/use | |||
712 | // pair can live in the resulting interval. | |||
713 | Last = LSP; | |||
714 | ParentVNI = Edit->getParent().getVNInfoAt(Last); | |||
715 | if (!ParentVNI) { | |||
716 | // undef use --> undef tied def | |||
717 | LLVM_DEBUG(dbgs() << ": tied use not live\n")do { } while (false); | |||
718 | return End; | |||
719 | } | |||
720 | } | |||
721 | ||||
722 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id)do { } while (false); | |||
723 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, | |||
724 | SA.getLastSplitPointIter(&MBB)); | |||
725 | RegAssign.insert(VNI->def, End, OpenIdx); | |||
726 | LLVM_DEBUG(dump())do { } while (false); | |||
727 | return VNI->def; | |||
728 | } | |||
729 | ||||
730 | /// useIntv - indicate that all instructions in MBB should use OpenLI. | |||
731 | void SplitEditor::useIntv(const MachineBasicBlock &MBB) { | |||
732 | useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); | |||
733 | } | |||
734 | ||||
735 | void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { | |||
736 | assert(OpenIdx && "openIntv not called before useIntv")((void)0); | |||
737 | LLVM_DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):")do { } while (false); | |||
738 | RegAssign.insert(Start, End, OpenIdx); | |||
739 | LLVM_DEBUG(dump())do { } while (false); | |||
740 | } | |||
741 | ||||
742 | SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { | |||
743 | assert(OpenIdx && "openIntv not called before leaveIntvAfter")((void)0); | |||
744 | LLVM_DEBUG(dbgs() << " leaveIntvAfter " << Idx)do { } while (false); | |||
745 | ||||
746 | // The interval must be live beyond the instruction at Idx. | |||
747 | SlotIndex Boundary = Idx.getBoundaryIndex(); | |||
748 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary); | |||
749 | if (!ParentVNI) { | |||
750 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
751 | return Boundary.getNextSlot(); | |||
752 | } | |||
753 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n')do { } while (false); | |||
754 | MachineInstr *MI = LIS.getInstructionFromIndex(Boundary); | |||
755 | assert(MI && "No instruction at index")((void)0); | |||
756 | ||||
757 | // In spill mode, make live ranges as short as possible by inserting the copy | |||
758 | // before MI. This is only possible if that instruction doesn't redefine the | |||
759 | // value. The inserted COPY is not a kill, and we don't need to recompute | |||
760 | // the source live range. The spiller also won't try to hoist this copy. | |||
761 | if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) && | |||
762 | MI->readsVirtualRegister(Edit->getReg())) { | |||
763 | forceRecompute(0, *ParentVNI); | |||
764 | defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); | |||
765 | return Idx; | |||
766 | } | |||
767 | ||||
768 | VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(), | |||
769 | std::next(MachineBasicBlock::iterator(MI))); | |||
770 | return VNI->def; | |||
771 | } | |||
772 | ||||
773 | SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { | |||
774 | assert(OpenIdx && "openIntv not called before leaveIntvBefore")((void)0); | |||
775 | LLVM_DEBUG(dbgs() << " leaveIntvBefore " << Idx)do { } while (false); | |||
776 | ||||
777 | // The interval must be live into the instruction at Idx. | |||
778 | Idx = Idx.getBaseIndex(); | |||
779 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); | |||
780 | if (!ParentVNI) { | |||
781 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
782 | return Idx.getNextSlot(); | |||
783 | } | |||
784 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n')do { } while (false); | |||
785 | ||||
786 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); | |||
787 | assert(MI && "No instruction at index")((void)0); | |||
788 | VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); | |||
789 | return VNI->def; | |||
790 | } | |||
791 | ||||
792 | SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { | |||
793 | assert(OpenIdx && "openIntv not called before leaveIntvAtTop")((void)0); | |||
794 | SlotIndex Start = LIS.getMBBStartIdx(&MBB); | |||
795 | LLVM_DEBUG(dbgs() << " leaveIntvAtTop " << printMBBReference(MBB) << ", "do { } while (false) | |||
796 | << Start)do { } while (false); | |||
797 | ||||
798 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); | |||
799 | if (!ParentVNI) { | |||
800 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
801 | return Start; | |||
802 | } | |||
803 | ||||
804 | VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, | |||
805 | MBB.SkipPHIsLabelsAndDebug(MBB.begin())); | |||
806 | RegAssign.insert(Start, VNI->def, OpenIdx); | |||
807 | LLVM_DEBUG(dump())do { } while (false); | |||
808 | return VNI->def; | |||
809 | } | |||
810 | ||||
811 | static bool hasTiedUseOf(MachineInstr &MI, unsigned Reg) { | |||
812 | return any_of(MI.defs(), [Reg](const MachineOperand &MO) { | |||
813 | return MO.isReg() && MO.isTied() && MO.getReg() == Reg; | |||
814 | }); | |||
815 | } | |||
816 | ||||
817 | void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { | |||
818 | assert(OpenIdx && "openIntv not called before overlapIntv")((void)0); | |||
819 | const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); | |||
820 | assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&((void)0) | |||
821 | "Parent changes value in extended range")((void)0); | |||
822 | assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&((void)0) | |||
823 | "Range cannot span basic blocks")((void)0); | |||
824 | ||||
825 | // The complement interval will be extended as needed by LICalc.extend(). | |||
826 | if (ParentVNI) | |||
827 | forceRecompute(0, *ParentVNI); | |||
828 | ||||
829 | // If the last use is tied to a def, we can't mark it as live for the | |||
830 | // interval which includes only the use. That would cause the tied pair | |||
831 | // to end up in two different intervals. | |||
832 | if (auto *MI = LIS.getInstructionFromIndex(End)) | |||
833 | if (hasTiedUseOf(*MI, Edit->getReg())) { | |||
834 | LLVM_DEBUG(dbgs() << "skip overlap due to tied def at end\n")do { } while (false); | |||
835 | return; | |||
836 | } | |||
837 | ||||
838 | LLVM_DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):")do { } while (false); | |||
839 | RegAssign.insert(Start, End, OpenIdx); | |||
840 | LLVM_DEBUG(dump())do { } while (false); | |||
841 | } | |||
842 | ||||
843 | //===----------------------------------------------------------------------===// | |||
844 | // Spill modes | |||
845 | //===----------------------------------------------------------------------===// | |||
846 | ||||
847 | void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) { | |||
848 | LiveInterval *LI = &LIS.getInterval(Edit->get(0)); | |||
849 | LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n")do { } while (false); | |||
850 | RegAssignMap::iterator AssignI; | |||
851 | AssignI.setMap(RegAssign); | |||
852 | ||||
853 | for (const VNInfo *C : Copies) { | |||
854 | SlotIndex Def = C->def; | |||
855 | MachineInstr *MI = LIS.getInstructionFromIndex(Def); | |||
856 | assert(MI && "No instruction for back-copy")((void)0); | |||
857 | ||||
858 | MachineBasicBlock *MBB = MI->getParent(); | |||
859 | MachineBasicBlock::iterator MBBI(MI); | |||
860 | bool AtBegin; | |||
861 | do AtBegin = MBBI == MBB->begin(); | |||
862 | while (!AtBegin && (--MBBI)->isDebugOrPseudoInstr()); | |||
863 | ||||
864 | LLVM_DEBUG(dbgs() << "Removing " << Def << '\t' << *MI)do { } while (false); | |||
865 | LIS.removeVRegDefAt(*LI, Def); | |||
866 | LIS.RemoveMachineInstrFromMaps(*MI); | |||
867 | MI->eraseFromParent(); | |||
868 | ||||
869 | // Adjust RegAssign if a register assignment is killed at Def. We want to | |||
870 | // avoid calculating the live range of the source register if possible. | |||
871 | AssignI.find(Def.getPrevSlot()); | |||
872 | if (!AssignI.valid() || AssignI.start() >= Def) | |||
873 | continue; | |||
874 | // If MI doesn't kill the assigned register, just leave it. | |||
875 | if (AssignI.stop() != Def) | |||
876 | continue; | |||
877 | unsigned RegIdx = AssignI.value(); | |||
878 | // We could hoist back-copy right after another back-copy. As a result | |||
879 | // MMBI points to copy instruction which is actually dead now. | |||
880 | // We cannot set its stop to MBBI which will be the same as start and | |||
881 | // interval does not support that. | |||
882 | SlotIndex Kill = | |||
883 | AtBegin ? SlotIndex() : LIS.getInstructionIndex(*MBBI).getRegSlot(); | |||
884 | if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg()) || | |||
885 | Kill <= AssignI.start()) { | |||
886 | LLVM_DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdxdo { } while (false) | |||
887 | << '\n')do { } while (false); | |||
888 | forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def)); | |||
889 | } else { | |||
890 | LLVM_DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI)do { } while (false); | |||
891 | AssignI.setStop(Kill); | |||
892 | } | |||
893 | } | |||
894 | } | |||
895 | ||||
896 | MachineBasicBlock* | |||
897 | SplitEditor::findShallowDominator(MachineBasicBlock *MBB, | |||
898 | MachineBasicBlock *DefMBB) { | |||
899 | if (MBB == DefMBB) | |||
900 | return MBB; | |||
901 | assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.")((void)0); | |||
902 | ||||
903 | const MachineLoopInfo &Loops = SA.Loops; | |||
904 | const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB); | |||
905 | MachineDomTreeNode *DefDomNode = MDT[DefMBB]; | |||
906 | ||||
907 | // Best candidate so far. | |||
908 | MachineBasicBlock *BestMBB = MBB; | |||
909 | unsigned BestDepth = std::numeric_limits<unsigned>::max(); | |||
910 | ||||
911 | while (true) { | |||
912 | const MachineLoop *Loop = Loops.getLoopFor(MBB); | |||
913 | ||||
914 | // MBB isn't in a loop, it doesn't get any better. All dominators have a | |||
915 | // higher frequency by definition. | |||
916 | if (!Loop) { | |||
917 | LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)do { } while (false) | |||
918 | << " dominates " << printMBBReference(*MBB)do { } while (false) | |||
919 | << " at depth 0\n")do { } while (false); | |||
920 | return MBB; | |||
921 | } | |||
922 | ||||
923 | // We'll never be able to exit the DefLoop. | |||
924 | if (Loop == DefLoop) { | |||
925 | LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)do { } while (false) | |||
926 | << " dominates " << printMBBReference(*MBB)do { } while (false) | |||
927 | << " in the same loop\n")do { } while (false); | |||
928 | return MBB; | |||
929 | } | |||
930 | ||||
931 | // Least busy dominator seen so far. | |||
932 | unsigned Depth = Loop->getLoopDepth(); | |||
933 | if (Depth < BestDepth) { | |||
934 | BestMBB = MBB; | |||
935 | BestDepth = Depth; | |||
936 | LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)do { } while (false) | |||
937 | << " dominates " << printMBBReference(*MBB)do { } while (false) | |||
938 | << " at depth " << Depth << '\n')do { } while (false); | |||
939 | } | |||
940 | ||||
941 | // Leave loop by going to the immediate dominator of the loop header. | |||
942 | // This is a bigger stride than simply walking up the dominator tree. | |||
943 | MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom(); | |||
944 | ||||
945 | // Too far up the dominator tree? | |||
946 | if (!IDom || !MDT.dominates(DefDomNode, IDom)) | |||
947 | return BestMBB; | |||
948 | ||||
949 | MBB = IDom->getBlock(); | |||
950 | } | |||
951 | } | |||
952 | ||||
953 | void SplitEditor::computeRedundantBackCopies( | |||
954 | DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) { | |||
955 | LiveInterval *LI = &LIS.getInterval(Edit->get(0)); | |||
956 | LiveInterval *Parent = &Edit->getParent(); | |||
957 | SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums()); | |||
958 | SmallPtrSet<VNInfo *, 8> DominatedVNIs; | |||
959 | ||||
960 | // Aggregate VNIs having the same value as ParentVNI. | |||
961 | for (VNInfo *VNI : LI->valnos) { | |||
962 | if (VNI->isUnused()) | |||
963 | continue; | |||
964 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); | |||
965 | EqualVNs[ParentVNI->id].insert(VNI); | |||
966 | } | |||
967 | ||||
968 | // For VNI aggregation of each ParentVNI, collect dominated, i.e., | |||
969 | // redundant VNIs to BackCopies. | |||
970 | for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { | |||
971 | VNInfo *ParentVNI = Parent->getValNumInfo(i); | |||
972 | if (!NotToHoistSet.count(ParentVNI->id)) | |||
973 | continue; | |||
974 | SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin(); | |||
975 | SmallPtrSetIterator<VNInfo *> It2 = It1; | |||
976 | for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) { | |||
977 | It2 = It1; | |||
978 | for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) { | |||
979 | if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2)) | |||
980 | continue; | |||
981 | ||||
982 | MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def); | |||
983 | MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def); | |||
984 | if (MBB1 == MBB2) { | |||
985 | DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1)); | |||
986 | } else if (MDT.dominates(MBB1, MBB2)) { | |||
987 | DominatedVNIs.insert(*It2); | |||
988 | } else if (MDT.dominates(MBB2, MBB1)) { | |||
989 | DominatedVNIs.insert(*It1); | |||
990 | } | |||
991 | } | |||
992 | } | |||
993 | if (!DominatedVNIs.empty()) { | |||
994 | forceRecompute(0, *ParentVNI); | |||
995 | append_range(BackCopies, DominatedVNIs); | |||
996 | DominatedVNIs.clear(); | |||
997 | } | |||
998 | } | |||
999 | } | |||
1000 | ||||
1001 | /// For SM_Size mode, find a common dominator for all the back-copies for | |||
1002 | /// the same ParentVNI and hoist the backcopies to the dominator BB. | |||
1003 | /// For SM_Speed mode, if the common dominator is hot and it is not beneficial | |||
1004 | /// to do the hoisting, simply remove the dominated backcopies for the same | |||
1005 | /// ParentVNI. | |||
1006 | void SplitEditor::hoistCopies() { | |||
1007 | // Get the complement interval, always RegIdx 0. | |||
1008 | LiveInterval *LI = &LIS.getInterval(Edit->get(0)); | |||
1009 | LiveInterval *Parent = &Edit->getParent(); | |||
1010 | ||||
1011 | // Track the nearest common dominator for all back-copies for each ParentVNI, | |||
1012 | // indexed by ParentVNI->id. | |||
1013 | using DomPair = std::pair<MachineBasicBlock *, SlotIndex>; | |||
1014 | SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums()); | |||
1015 | // The total cost of all the back-copies for each ParentVNI. | |||
1016 | SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums()); | |||
1017 | // The ParentVNI->id set for which hoisting back-copies are not beneficial | |||
1018 | // for Speed. | |||
1019 | DenseSet<unsigned> NotToHoistSet; | |||
1020 | ||||
1021 | // Find the nearest common dominator for parent values with multiple | |||
1022 | // back-copies. If a single back-copy dominates, put it in DomPair.second. | |||
1023 | for (VNInfo *VNI : LI->valnos) { | |||
1024 | if (VNI->isUnused()) | |||
1025 | continue; | |||
1026 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); | |||
1027 | assert(ParentVNI && "Parent not live at complement def")((void)0); | |||
1028 | ||||
1029 | // Don't hoist remats. The complement is probably going to disappear | |||
1030 | // completely anyway. | |||
1031 | if (Edit->didRematerialize(ParentVNI)) | |||
1032 | continue; | |||
1033 | ||||
1034 | MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def); | |||
1035 | ||||
1036 | DomPair &Dom = NearestDom[ParentVNI->id]; | |||
1037 | ||||
1038 | // Keep directly defined parent values. This is either a PHI or an | |||
1039 | // instruction in the complement range. All other copies of ParentVNI | |||
1040 | // should be eliminated. | |||
1041 | if (VNI->def == ParentVNI->def) { | |||
1042 | LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n')do { } while (false); | |||
1043 | Dom = DomPair(ValMBB, VNI->def); | |||
1044 | continue; | |||
1045 | } | |||
1046 | // Skip the singly mapped values. There is nothing to gain from hoisting a | |||
1047 | // single back-copy. | |||
1048 | if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) { | |||
1049 | LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n')do { } while (false); | |||
1050 | continue; | |||
1051 | } | |||
1052 | ||||
1053 | if (!Dom.first) { | |||
1054 | // First time we see ParentVNI. VNI dominates itself. | |||
1055 | Dom = DomPair(ValMBB, VNI->def); | |||
1056 | } else if (Dom.first == ValMBB) { | |||
1057 | // Two defs in the same block. Pick the earlier def. | |||
1058 | if (!Dom.second.isValid() || VNI->def < Dom.second) | |||
1059 | Dom.second = VNI->def; | |||
1060 | } else { | |||
1061 | // Different basic blocks. Check if one dominates. | |||
1062 | MachineBasicBlock *Near = | |||
1063 | MDT.findNearestCommonDominator(Dom.first, ValMBB); | |||
1064 | if (Near == ValMBB) | |||
1065 | // Def ValMBB dominates. | |||
1066 | Dom = DomPair(ValMBB, VNI->def); | |||
1067 | else if (Near != Dom.first) | |||
1068 | // None dominate. Hoist to common dominator, need new def. | |||
1069 | Dom = DomPair(Near, SlotIndex()); | |||
1070 | Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB); | |||
1071 | } | |||
1072 | ||||
1073 | LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@'do { } while (false) | |||
1074 | << VNI->def << " for parent " << ParentVNI->id << '@'do { } while (false) | |||
1075 | << ParentVNI->def << " hoist to "do { } while (false) | |||
1076 | << printMBBReference(*Dom.first) << ' ' << Dom.seconddo { } while (false) | |||
1077 | << '\n')do { } while (false); | |||
1078 | } | |||
1079 | ||||
1080 | // Insert the hoisted copies. | |||
1081 | for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { | |||
1082 | DomPair &Dom = NearestDom[i]; | |||
1083 | if (!Dom.first || Dom.second.isValid()) | |||
1084 | continue; | |||
1085 | // This value needs a hoisted copy inserted at the end of Dom.first. | |||
1086 | VNInfo *ParentVNI = Parent->getValNumInfo(i); | |||
1087 | MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def); | |||
1088 | // Get a less loopy dominator than Dom.first. | |||
1089 | Dom.first = findShallowDominator(Dom.first, DefMBB); | |||
1090 | if (SpillMode == SM_Speed && | |||
1091 | MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) { | |||
1092 | NotToHoistSet.insert(ParentVNI->id); | |||
1093 | continue; | |||
1094 | } | |||
1095 | SlotIndex LSP = SA.getLastSplitPoint(Dom.first); | |||
1096 | if (LSP <= ParentVNI->def) { | |||
1097 | NotToHoistSet.insert(ParentVNI->id); | |||
1098 | continue; | |||
1099 | } | |||
1100 | Dom.second = defFromParent(0, ParentVNI, LSP, *Dom.first, | |||
1101 | SA.getLastSplitPointIter(Dom.first))->def; | |||
1102 | } | |||
1103 | ||||
1104 | // Remove redundant back-copies that are now known to be dominated by another | |||
1105 | // def with the same value. | |||
1106 | SmallVector<VNInfo*, 8> BackCopies; | |||
1107 | for (VNInfo *VNI : LI->valnos) { | |||
1108 | if (VNI->isUnused()) | |||
1109 | continue; | |||
1110 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); | |||
1111 | const DomPair &Dom = NearestDom[ParentVNI->id]; | |||
1112 | if (!Dom.first || Dom.second == VNI->def || | |||
1113 | NotToHoistSet.count(ParentVNI->id)) | |||
1114 | continue; | |||
1115 | BackCopies.push_back(VNI); | |||
1116 | forceRecompute(0, *ParentVNI); | |||
1117 | } | |||
1118 | ||||
1119 | // If it is not beneficial to hoist all the BackCopies, simply remove | |||
1120 | // redundant BackCopies in speed mode. | |||
1121 | if (SpillMode == SM_Speed && !NotToHoistSet.empty()) | |||
1122 | computeRedundantBackCopies(NotToHoistSet, BackCopies); | |||
1123 | ||||
1124 | removeBackCopies(BackCopies); | |||
1125 | } | |||
1126 | ||||
1127 | /// transferValues - Transfer all possible values to the new live ranges. | |||
1128 | /// Values that were rematerialized are left alone, they need LICalc.extend(). | |||
1129 | bool SplitEditor::transferValues() { | |||
1130 | bool Skipped = false; | |||
1131 | RegAssignMap::const_iterator AssignI = RegAssign.begin(); | |||
1132 | for (const LiveRange::Segment &S : Edit->getParent()) { | |||
1133 | LLVM_DEBUG(dbgs() << " blit " << S << ':')do { } while (false); | |||
1134 | VNInfo *ParentVNI = S.valno; | |||
1135 | // RegAssign has holes where RegIdx 0 should be used. | |||
1136 | SlotIndex Start = S.start; | |||
1137 | AssignI.advanceTo(Start); | |||
1138 | do { | |||
1139 | unsigned RegIdx; | |||
1140 | SlotIndex End = S.end; | |||
1141 | if (!AssignI.valid()) { | |||
1142 | RegIdx = 0; | |||
1143 | } else if (AssignI.start() <= Start) { | |||
1144 | RegIdx = AssignI.value(); | |||
1145 | if (AssignI.stop() < End) { | |||
1146 | End = AssignI.stop(); | |||
1147 | ++AssignI; | |||
1148 | } | |||
1149 | } else { | |||
1150 | RegIdx = 0; | |||
1151 | End = std::min(End, AssignI.start()); | |||
1152 | } | |||
1153 | ||||
1154 | // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. | |||
1155 | LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '('do { } while (false) | |||
1156 | << printReg(Edit->get(RegIdx)) << ')')do { } while (false); | |||
1157 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); | |||
1158 | ||||
1159 | // Check for a simply defined value that can be blitted directly. | |||
1160 | ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id)); | |||
1161 | if (VNInfo *VNI = VFP.getPointer()) { | |||
1162 | LLVM_DEBUG(dbgs() << ':' << VNI->id)do { } while (false); | |||
1163 | LI.addSegment(LiveInterval::Segment(Start, End, VNI)); | |||
1164 | Start = End; | |||
1165 | continue; | |||
1166 | } | |||
1167 | ||||
1168 | // Skip values with forced recomputation. | |||
1169 | if (VFP.getInt()) { | |||
1170 | LLVM_DEBUG(dbgs() << "(recalc)")do { } while (false); | |||
1171 | Skipped = true; | |||
1172 | Start = End; | |||
1173 | continue; | |||
1174 | } | |||
1175 | ||||
1176 | LiveIntervalCalc &LIC = getLICalc(RegIdx); | |||
1177 | ||||
1178 | // This value has multiple defs in RegIdx, but it wasn't rematerialized, | |||
1179 | // so the live range is accurate. Add live-in blocks in [Start;End) to the | |||
1180 | // LiveInBlocks. | |||
1181 | MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator(); | |||
1182 | SlotIndex BlockStart, BlockEnd; | |||
1183 | std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB); | |||
1184 | ||||
1185 | // The first block may be live-in, or it may have its own def. | |||
1186 | if (Start != BlockStart) { | |||
1187 | VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End)); | |||
1188 | assert(VNI && "Missing def for complex mapped value")((void)0); | |||
1189 | LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB))do { } while (false); | |||
1190 | // MBB has its own def. Is it also live-out? | |||
1191 | if (BlockEnd <= End) | |||
1192 | LIC.setLiveOutValue(&*MBB, VNI); | |||
1193 | ||||
1194 | // Skip to the next block for live-in. | |||
1195 | ++MBB; | |||
1196 | BlockStart = BlockEnd; | |||
1197 | } | |||
1198 | ||||
1199 | // Handle the live-in blocks covered by [Start;End). | |||
1200 | assert(Start <= BlockStart && "Expected live-in block")((void)0); | |||
1201 | while (BlockStart < End) { | |||
1202 | LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB))do { } while (false); | |||
1203 | BlockEnd = LIS.getMBBEndIdx(&*MBB); | |||
1204 | if (BlockStart == ParentVNI->def) { | |||
1205 | // This block has the def of a parent PHI, so it isn't live-in. | |||
1206 | assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?")((void)0); | |||
1207 | VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End)); | |||
1208 | assert(VNI && "Missing def for complex mapped parent PHI")((void)0); | |||
1209 | if (End >= BlockEnd) | |||
1210 | LIC.setLiveOutValue(&*MBB, VNI); // Live-out as well. | |||
1211 | } else { | |||
1212 | // This block needs a live-in value. The last block covered may not | |||
1213 | // be live-out. | |||
1214 | if (End < BlockEnd) | |||
1215 | LIC.addLiveInBlock(LI, MDT[&*MBB], End); | |||
1216 | else { | |||
1217 | // Live-through, and we don't know the value. | |||
1218 | LIC.addLiveInBlock(LI, MDT[&*MBB]); | |||
1219 | LIC.setLiveOutValue(&*MBB, nullptr); | |||
1220 | } | |||
1221 | } | |||
1222 | BlockStart = BlockEnd; | |||
1223 | ++MBB; | |||
1224 | } | |||
1225 | Start = End; | |||
1226 | } while (Start != S.end); | |||
1227 | LLVM_DEBUG(dbgs() << '\n')do { } while (false); | |||
1228 | } | |||
1229 | ||||
1230 | LICalc[0].calculateValues(); | |||
1231 | if (SpillMode) | |||
1232 | LICalc[1].calculateValues(); | |||
1233 | ||||
1234 | return Skipped; | |||
1235 | } | |||
1236 | ||||
1237 | static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) { | |||
1238 | const LiveRange::Segment *Seg = LR.getSegmentContaining(Def); | |||
1239 | if (Seg == nullptr) | |||
1240 | return true; | |||
1241 | if (Seg->end != Def.getDeadSlot()) | |||
1242 | return false; | |||
1243 | // This is a dead PHI. Remove it. | |||
1244 | LR.removeSegment(*Seg, true); | |||
1245 | return true; | |||
1246 | } | |||
1247 | ||||
1248 | void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC, | |||
1249 | LiveRange &LR, LaneBitmask LM, | |||
1250 | ArrayRef<SlotIndex> Undefs) { | |||
1251 | for (MachineBasicBlock *P : B.predecessors()) { | |||
1252 | SlotIndex End = LIS.getMBBEndIdx(P); | |||
1253 | SlotIndex LastUse = End.getPrevSlot(); | |||
1254 | // The predecessor may not have a live-out value. That is OK, like an | |||
1255 | // undef PHI operand. | |||
1256 | LiveInterval &PLI = Edit->getParent(); | |||
1257 | // Need the cast because the inputs to ?: would otherwise be deemed | |||
1258 | // "incompatible": SubRange vs LiveInterval. | |||
1259 | LiveRange &PSR = !LM.all() ? getSubRangeForMaskExact(LM, PLI) | |||
1260 | : static_cast<LiveRange &>(PLI); | |||
1261 | if (PSR.liveAt(LastUse)) | |||
1262 | LIC.extend(LR, End, /*PhysReg=*/0, Undefs); | |||
1263 | } | |||
1264 | } | |||
1265 | ||||
1266 | void SplitEditor::extendPHIKillRanges() { | |||
1267 | // Extend live ranges to be live-out for successor PHI values. | |||
1268 | ||||
1269 | // Visit each PHI def slot in the parent live interval. If the def is dead, | |||
1270 | // remove it. Otherwise, extend the live interval to reach the end indexes | |||
1271 | // of all predecessor blocks. | |||
1272 | ||||
1273 | LiveInterval &ParentLI = Edit->getParent(); | |||
1274 | for (const VNInfo *V : ParentLI.valnos) { | |||
1275 | if (V->isUnused() || !V->isPHIDef()) | |||
1276 | continue; | |||
1277 | ||||
1278 | unsigned RegIdx = RegAssign.lookup(V->def); | |||
1279 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); | |||
1280 | LiveIntervalCalc &LIC = getLICalc(RegIdx); | |||
1281 | MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def); | |||
1282 | if (!removeDeadSegment(V->def, LI)) | |||
1283 | extendPHIRange(B, LIC, LI, LaneBitmask::getAll(), /*Undefs=*/{}); | |||
1284 | } | |||
1285 | ||||
1286 | SmallVector<SlotIndex, 4> Undefs; | |||
1287 | LiveIntervalCalc SubLIC; | |||
1288 | ||||
1289 | for (LiveInterval::SubRange &PS : ParentLI.subranges()) { | |||
1290 | for (const VNInfo *V : PS.valnos) { | |||
1291 | if (V->isUnused() || !V->isPHIDef()) | |||
1292 | continue; | |||
1293 | unsigned RegIdx = RegAssign.lookup(V->def); | |||
1294 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); | |||
1295 | LiveInterval::SubRange &S = getSubRangeForMaskExact(PS.LaneMask, LI); | |||
1296 | if (removeDeadSegment(V->def, S)) | |||
1297 | continue; | |||
1298 | ||||
1299 | MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def); | |||
1300 | SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, | |||
1301 | &LIS.getVNInfoAllocator()); | |||
1302 | Undefs.clear(); | |||
1303 | LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes()); | |||
1304 | extendPHIRange(B, SubLIC, S, PS.LaneMask, Undefs); | |||
1305 | } | |||
1306 | } | |||
1307 | } | |||
1308 | ||||
1309 | /// rewriteAssigned - Rewrite all uses of Edit->getReg(). | |||
1310 | void SplitEditor::rewriteAssigned(bool ExtendRanges) { | |||
1311 | struct ExtPoint { | |||
1312 | ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N) | |||
1313 | : MO(O), RegIdx(R), Next(N) {} | |||
1314 | ||||
1315 | MachineOperand MO; | |||
1316 | unsigned RegIdx; | |||
1317 | SlotIndex Next; | |||
1318 | }; | |||
1319 | ||||
1320 | SmallVector<ExtPoint,4> ExtPoints; | |||
1321 | ||||
1322 | for (MachineOperand &MO : | |||
1323 | llvm::make_early_inc_range(MRI.reg_operands(Edit->getReg()))) { | |||
1324 | MachineInstr *MI = MO.getParent(); | |||
1325 | // LiveDebugVariables should have handled all DBG_VALUE instructions. | |||
1326 | if (MI->isDebugValue()) { | |||
1327 | LLVM_DEBUG(dbgs() << "Zapping " << *MI)do { } while (false); | |||
1328 | MO.setReg(0); | |||
1329 | continue; | |||
1330 | } | |||
1331 | ||||
1332 | // <undef> operands don't really read the register, so it doesn't matter | |||
1333 | // which register we choose. When the use operand is tied to a def, we must | |||
1334 | // use the same register as the def, so just do that always. | |||
1335 | SlotIndex Idx = LIS.getInstructionIndex(*MI); | |||
1336 | if (MO.isDef() || MO.isUndef()) | |||
1337 | Idx = Idx.getRegSlot(MO.isEarlyClobber()); | |||
1338 | ||||
1339 | // Rewrite to the mapped register at Idx. | |||
1340 | unsigned RegIdx = RegAssign.lookup(Idx); | |||
1341 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); | |||
1342 | MO.setReg(LI.reg()); | |||
1343 | LLVM_DEBUG(dbgs() << " rewr " << printMBBReference(*MI->getParent())do { } while (false) | |||
1344 | << '\t' << Idx << ':' << RegIdx << '\t' << *MI)do { } while (false); | |||
1345 | ||||
1346 | // Extend liveness to Idx if the instruction reads reg. | |||
1347 | if (!ExtendRanges || MO.isUndef()) | |||
1348 | continue; | |||
1349 | ||||
1350 | // Skip instructions that don't read Reg. | |||
1351 | if (MO.isDef()) { | |||
1352 | if (!MO.getSubReg() && !MO.isEarlyClobber()) | |||
1353 | continue; | |||
1354 | // We may want to extend a live range for a partial redef, or for a use | |||
1355 | // tied to an early clobber. | |||
1356 | Idx = Idx.getPrevSlot(); | |||
1357 | if (!Edit->getParent().liveAt(Idx)) | |||
1358 | continue; | |||
1359 | } else | |||
1360 | Idx = Idx.getRegSlot(true); | |||
1361 | ||||
1362 | SlotIndex Next = Idx.getNextSlot(); | |||
1363 | if (LI.hasSubRanges()) { | |||
1364 | // We have to delay extending subranges until we have seen all operands | |||
1365 | // defining the register. This is because a <def,read-undef> operand | |||
1366 | // will create an "undef" point, and we cannot extend any subranges | |||
1367 | // until all of them have been accounted for. | |||
1368 | if (MO.isUse()) | |||
1369 | ExtPoints.push_back(ExtPoint(MO, RegIdx, Next)); | |||
1370 | } else { | |||
1371 | LiveIntervalCalc &LIC = getLICalc(RegIdx); | |||
1372 | LIC.extend(LI, Next, 0, ArrayRef<SlotIndex>()); | |||
1373 | } | |||
1374 | } | |||
1375 | ||||
1376 | for (ExtPoint &EP : ExtPoints) { | |||
1377 | LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx)); | |||
1378 | assert(LI.hasSubRanges())((void)0); | |||
1379 | ||||
1380 | LiveIntervalCalc SubLIC; | |||
1381 | Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg(); | |||
1382 | LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub) | |||
1383 | : MRI.getMaxLaneMaskForVReg(Reg); | |||
1384 | for (LiveInterval::SubRange &S : LI.subranges()) { | |||
1385 | if ((S.LaneMask & LM).none()) | |||
1386 | continue; | |||
1387 | // The problem here can be that the new register may have been created | |||
1388 | // for a partially defined original register. For example: | |||
1389 | // %0:subreg_hireg<def,read-undef> = ... | |||
1390 | // ... | |||
1391 | // %1 = COPY %0 | |||
1392 | if (S.empty()) | |||
1393 | continue; | |||
1394 | SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, | |||
1395 | &LIS.getVNInfoAllocator()); | |||
1396 | SmallVector<SlotIndex, 4> Undefs; | |||
1397 | LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes()); | |||
1398 | SubLIC.extend(S, EP.Next, 0, Undefs); | |||
1399 | } | |||
1400 | } | |||
1401 | ||||
1402 | for (Register R : *Edit) { | |||
1403 | LiveInterval &LI = LIS.getInterval(R); | |||
1404 | if (!LI.hasSubRanges()) | |||
1405 | continue; | |||
1406 | LI.clear(); | |||
1407 | LI.removeEmptySubRanges(); | |||
1408 | LIS.constructMainRangeFromSubranges(LI); | |||
1409 | } | |||
1410 | } | |||
1411 | ||||
1412 | void SplitEditor::deleteRematVictims() { | |||
1413 | SmallVector<MachineInstr*, 8> Dead; | |||
1414 | for (const Register &R : *Edit) { | |||
1415 | LiveInterval *LI = &LIS.getInterval(R); | |||
1416 | for (const LiveRange::Segment &S : LI->segments) { | |||
1417 | // Dead defs end at the dead slot. | |||
1418 | if (S.end != S.valno->def.getDeadSlot()) | |||
1419 | continue; | |||
1420 | if (S.valno->isPHIDef()) | |||
1421 | continue; | |||
1422 | MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def); | |||
1423 | assert(MI && "Missing instruction for dead def")((void)0); | |||
1424 | MI->addRegisterDead(LI->reg(), &TRI); | |||
1425 | ||||
1426 | if (!MI->allDefsAreDead()) | |||
1427 | continue; | |||
1428 | ||||
1429 | LLVM_DEBUG(dbgs() << "All defs dead: " << *MI)do { } while (false); | |||
1430 | Dead.push_back(MI); | |||
1431 | } | |||
1432 | } | |||
1433 | ||||
1434 | if (Dead.empty()) | |||
1435 | return; | |||
1436 | ||||
1437 | Edit->eliminateDeadDefs(Dead, None, &AA); | |||
1438 | } | |||
1439 | ||||
1440 | void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) { | |||
1441 | // Fast-path for common case. | |||
1442 | if (!ParentVNI.isPHIDef()) { | |||
1443 | for (unsigned I = 0, E = Edit->size(); I != E; ++I) | |||
1444 | forceRecompute(I, ParentVNI); | |||
1445 | return; | |||
1446 | } | |||
1447 | ||||
1448 | // Trace value through phis. | |||
1449 | SmallPtrSet<const VNInfo *, 8> Visited; ///< whether VNI was/is in worklist. | |||
1450 | SmallVector<const VNInfo *, 4> WorkList; | |||
1451 | Visited.insert(&ParentVNI); | |||
1452 | WorkList.push_back(&ParentVNI); | |||
1453 | ||||
1454 | const LiveInterval &ParentLI = Edit->getParent(); | |||
1455 | const SlotIndexes &Indexes = *LIS.getSlotIndexes(); | |||
1456 | do { | |||
1457 | const VNInfo &VNI = *WorkList.back(); | |||
1458 | WorkList.pop_back(); | |||
1459 | for (unsigned I = 0, E = Edit->size(); I != E; ++I) | |||
1460 | forceRecompute(I, VNI); | |||
1461 | if (!VNI.isPHIDef()) | |||
1462 | continue; | |||
1463 | ||||
1464 | MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(VNI.def); | |||
1465 | for (const MachineBasicBlock *Pred : MBB.predecessors()) { | |||
1466 | SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred); | |||
1467 | VNInfo *PredVNI = ParentLI.getVNInfoBefore(PredEnd); | |||
1468 | assert(PredVNI && "Value available in PhiVNI predecessor")((void)0); | |||
1469 | if (Visited.insert(PredVNI).second) | |||
1470 | WorkList.push_back(PredVNI); | |||
1471 | } | |||
1472 | } while(!WorkList.empty()); | |||
1473 | } | |||
1474 | ||||
1475 | void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { | |||
1476 | ++NumFinished; | |||
1477 | ||||
1478 | // At this point, the live intervals in Edit contain VNInfos corresponding to | |||
1479 | // the inserted copies. | |||
1480 | ||||
1481 | // Add the original defs from the parent interval. | |||
1482 | for (const VNInfo *ParentVNI : Edit->getParent().valnos) { | |||
| ||||
1483 | if (ParentVNI->isUnused()) | |||
1484 | continue; | |||
1485 | unsigned RegIdx = RegAssign.lookup(ParentVNI->def); | |||
1486 | defValue(RegIdx, ParentVNI, ParentVNI->def, true); | |||
1487 | ||||
1488 | // Force rematted values to be recomputed everywhere. | |||
1489 | // The new live ranges may be truncated. | |||
1490 | if (Edit->didRematerialize(ParentVNI)) | |||
1491 | forceRecomputeVNI(*ParentVNI); | |||
1492 | } | |||
1493 | ||||
1494 | // Hoist back-copies to the complement interval when in spill mode. | |||
1495 | switch (SpillMode) { | |||
1496 | case SM_Partition: | |||
1497 | // Leave all back-copies as is. | |||
1498 | break; | |||
1499 | case SM_Size: | |||
1500 | case SM_Speed: | |||
1501 | // hoistCopies will behave differently between size and speed. | |||
1502 | hoistCopies(); | |||
1503 | } | |||
1504 | ||||
1505 | // Transfer the simply mapped values, check if any are skipped. | |||
1506 | bool Skipped = transferValues(); | |||
1507 | ||||
1508 | // Rewrite virtual registers, possibly extending ranges. | |||
1509 | rewriteAssigned(Skipped); | |||
1510 | ||||
1511 | if (Skipped) | |||
1512 | extendPHIKillRanges(); | |||
1513 | else | |||
1514 | ++NumSimple; | |||
1515 | ||||
1516 | // Delete defs that were rematted everywhere. | |||
1517 | if (Skipped) | |||
1518 | deleteRematVictims(); | |||
1519 | ||||
1520 | // Get rid of unused values and set phi-kill flags. | |||
1521 | for (Register Reg : *Edit) { | |||
1522 | LiveInterval &LI = LIS.getInterval(Reg); | |||
1523 | LI.removeEmptySubRanges(); | |||
1524 | LI.RenumberValues(); | |||
1525 | } | |||
1526 | ||||
1527 | // Provide a reverse mapping from original indices to Edit ranges. | |||
1528 | if (LRMap) { | |||
1529 | LRMap->clear(); | |||
1530 | for (unsigned i = 0, e = Edit->size(); i != e; ++i) | |||
1531 | LRMap->push_back(i); | |||
1532 | } | |||
1533 | ||||
1534 | // Now check if any registers were separated into multiple components. | |||
1535 | ConnectedVNInfoEqClasses ConEQ(LIS); | |||
1536 | for (unsigned i = 0, e = Edit->size(); i != e; ++i) { | |||
1537 | // Don't use iterators, they are invalidated by create() below. | |||
1538 | Register VReg = Edit->get(i); | |||
1539 | LiveInterval &LI = LIS.getInterval(VReg); | |||
1540 | SmallVector<LiveInterval*, 8> SplitLIs; | |||
1541 | LIS.splitSeparateComponents(LI, SplitLIs); | |||
1542 | Register Original = VRM.getOriginal(VReg); | |||
1543 | for (LiveInterval *SplitLI : SplitLIs) | |||
1544 | VRM.setIsSplitFromReg(SplitLI->reg(), Original); | |||
1545 | ||||
1546 | // The new intervals all map back to i. | |||
1547 | if (LRMap) | |||
1548 | LRMap->resize(Edit->size(), i); | |||
1549 | } | |||
1550 | ||||
1551 | // Calculate spill weight and allocation hints for new intervals. | |||
1552 | Edit->calculateRegClassAndHint(VRM.getMachineFunction(), VRAI); | |||
1553 | ||||
1554 | assert(!LRMap || LRMap->size() == Edit->size())((void)0); | |||
1555 | } | |||
1556 | ||||
1557 | //===----------------------------------------------------------------------===// | |||
1558 | // Single Block Splitting | |||
1559 | //===----------------------------------------------------------------------===// | |||
1560 | ||||
1561 | bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, | |||
1562 | bool SingleInstrs) const { | |||
1563 | // Always split for multiple instructions. | |||
1564 | if (!BI.isOneInstr()) | |||
1565 | return true; | |||
1566 | // Don't split for single instructions unless explicitly requested. | |||
1567 | if (!SingleInstrs) | |||
1568 | return false; | |||
1569 | // Splitting a live-through range always makes progress. | |||
1570 | if (BI.LiveIn && BI.LiveOut) | |||
1571 | return true; | |||
1572 | // No point in isolating a copy. It has no register class constraints. | |||
1573 | if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike()) | |||
1574 | return false; | |||
1575 | // Finally, don't isolate an end point that was created by earlier splits. | |||
1576 | return isOriginalEndpoint(BI.FirstInstr); | |||
1577 | } | |||
1578 | ||||
1579 | void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { | |||
1580 | openIntv(); | |||
1581 | SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB); | |||
1582 | SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr, | |||
1583 | LastSplitPoint)); | |||
1584 | if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { | |||
1585 | useIntv(SegStart, leaveIntvAfter(BI.LastInstr)); | |||
1586 | } else { | |||
1587 | // The last use is after the last valid split point. | |||
1588 | SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); | |||
1589 | useIntv(SegStart, SegStop); | |||
1590 | overlapIntv(SegStop, BI.LastInstr); | |||
1591 | } | |||
1592 | } | |||
1593 | ||||
1594 | //===----------------------------------------------------------------------===// | |||
1595 | // Global Live Range Splitting Support | |||
1596 | //===----------------------------------------------------------------------===// | |||
1597 | ||||
1598 | // These methods support a method of global live range splitting that uses a | |||
1599 | // global algorithm to decide intervals for CFG edges. They will insert split | |||
1600 | // points and color intervals in basic blocks while avoiding interference. | |||
1601 | // | |||
1602 | // Note that splitSingleBlock is also useful for blocks where both CFG edges | |||
1603 | // are on the stack. | |||
1604 | ||||
1605 | void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, | |||
1606 | unsigned IntvIn, SlotIndex LeaveBefore, | |||
1607 | unsigned IntvOut, SlotIndex EnterAfter){ | |||
1608 | SlotIndex Start, Stop; | |||
1609 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); | |||
1610 | ||||
1611 | LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stopdo { } while (false) | |||
1612 | << ") intf " << LeaveBefore << '-' << EnterAfterdo { } while (false) | |||
1613 | << ", live-through " << IntvIn << " -> " << IntvOut)do { } while (false); | |||
1614 | ||||
1615 | assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks")((void)0); | |||
1616 | ||||
1617 | assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block")((void)0); | |||
1618 | assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf")((void)0); | |||
1619 | assert((!EnterAfter || EnterAfter >= Start) && "Interference before block")((void)0); | |||
1620 | ||||
1621 | MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); | |||
1622 | ||||
1623 | if (!IntvOut) { | |||
1624 | LLVM_DEBUG(dbgs() << ", spill on entry.\n")do { } while (false); | |||
1625 | // | |||
1626 | // <<<<<<<<< Possible LeaveBefore interference. | |||
1627 | // |-----------| Live through. | |||
1628 | // -____________ Spill on entry. | |||
1629 | // | |||
1630 | selectIntv(IntvIn); | |||
1631 | SlotIndex Idx = leaveIntvAtTop(*MBB); | |||
1632 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference")((void)0); | |||
1633 | (void)Idx; | |||
1634 | return; | |||
1635 | } | |||
1636 | ||||
1637 | if (!IntvIn) { | |||
1638 | LLVM_DEBUG(dbgs() << ", reload on exit.\n")do { } while (false); | |||
1639 | // | |||
1640 | // >>>>>>> Possible EnterAfter interference. | |||
1641 | // |-----------| Live through. | |||
1642 | // ___________-- Reload on exit. | |||
1643 | // | |||
1644 | selectIntv(IntvOut); | |||
1645 | SlotIndex Idx = enterIntvAtEnd(*MBB); | |||
1646 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference")((void)0); | |||
1647 | (void)Idx; | |||
1648 | return; | |||
1649 | } | |||
1650 | ||||
1651 | if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { | |||
1652 | LLVM_DEBUG(dbgs() << ", straight through.\n")do { } while (false); | |||
1653 | // | |||
1654 | // |-----------| Live through. | |||
1655 | // ------------- Straight through, same intv, no interference. | |||
1656 | // | |||
1657 | selectIntv(IntvOut); | |||
1658 | useIntv(Start, Stop); | |||
1659 | return; | |||
1660 | } | |||
1661 | ||||
1662 | // We cannot legally insert splits after LSP. | |||
1663 | SlotIndex LSP = SA.getLastSplitPoint(MBBNum); | |||
1664 | assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf")((void)0); | |||
1665 | ||||
1666 | if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || | |||
1667 | LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { | |||
1668 | LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n")do { } while (false); | |||
1669 | // | |||
1670 | // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. | |||
1671 | // |-----------| Live through. | |||
1672 | // ------======= Switch intervals between interference. | |||
1673 | // | |||
1674 | selectIntv(IntvOut); | |||
1675 | SlotIndex Idx; | |||
1676 | if (LeaveBefore && LeaveBefore < LSP) { | |||
1677 | Idx = enterIntvBefore(LeaveBefore); | |||
1678 | useIntv(Idx, Stop); | |||
1679 | } else { | |||
1680 | Idx = enterIntvAtEnd(*MBB); | |||
1681 | } | |||
1682 | selectIntv(IntvIn); | |||
1683 | useIntv(Start, Idx); | |||
1684 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference")((void)0); | |||
1685 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference")((void)0); | |||
1686 | return; | |||
1687 | } | |||
1688 | ||||
1689 | LLVM_DEBUG(dbgs() << ", create local intv for interference.\n")do { } while (false); | |||
1690 | // | |||
1691 | // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. | |||
1692 | // |-----------| Live through. | |||
1693 | // ==---------== Switch intervals before/after interference. | |||
1694 | // | |||
1695 | assert(LeaveBefore <= EnterAfter && "Missed case")((void)0); | |||
1696 | ||||
1697 | selectIntv(IntvOut); | |||
1698 | SlotIndex Idx = enterIntvAfter(EnterAfter); | |||
1699 | useIntv(Idx, Stop); | |||
1700 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference")((void)0); | |||
1701 | ||||
1702 | selectIntv(IntvIn); | |||
1703 | Idx = leaveIntvBefore(LeaveBefore); | |||
1704 | useIntv(Start, Idx); | |||
1705 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference")((void)0); | |||
1706 | } | |||
1707 | ||||
1708 | void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, | |||
1709 | unsigned IntvIn, SlotIndex LeaveBefore) { | |||
1710 | SlotIndex Start, Stop; | |||
1711 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); | |||
1712 | ||||
1713 | LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'do { } while (false) | |||
1714 | << Stop << "), uses " << BI.FirstInstr << '-'do { } while (false) | |||
1715 | << BI.LastInstr << ", reg-in " << IntvIndo { } while (false) | |||
1716 | << ", leave before " << LeaveBeforedo { } while (false) | |||
1717 | << (BI.LiveOut ? ", stack-out" : ", killed in block"))do { } while (false); | |||
1718 | ||||
1719 | assert(IntvIn && "Must have register in")((void)0); | |||
1720 | assert(BI.LiveIn && "Must be live-in")((void)0); | |||
1721 | assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference")((void)0); | |||
1722 | ||||
1723 | if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { | |||
1724 | LLVM_DEBUG(dbgs() << " before interference.\n")do { } while (false); | |||
1725 | // | |||
1726 | // <<< Interference after kill. | |||
1727 | // |---o---x | Killed in block. | |||
1728 | // ========= Use IntvIn everywhere. | |||
1729 | // | |||
1730 | selectIntv(IntvIn); | |||
1731 | useIntv(Start, BI.LastInstr); | |||
1732 | return; | |||
1733 | } | |||
1734 | ||||
1735 | SlotIndex LSP = SA.getLastSplitPoint(BI.MBB); | |||
1736 | ||||
1737 | if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { | |||
1738 | // | |||
1739 | // <<< Possible interference after last use. | |||
1740 | // |---o---o---| Live-out on stack. | |||
1741 | // =========____ Leave IntvIn after last use. | |||
1742 | // | |||
1743 | // < Interference after last use. | |||
1744 | // |---o---o--o| Live-out on stack, late last use. | |||
1745 | // ============ Copy to stack after LSP, overlap IntvIn. | |||
1746 | // \_____ Stack interval is live-out. | |||
1747 | // | |||
1748 | if (BI.LastInstr < LSP) { | |||
1749 | LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n")do { } while (false); | |||
1750 | selectIntv(IntvIn); | |||
1751 | SlotIndex Idx = leaveIntvAfter(BI.LastInstr); | |||
1752 | useIntv(Start, Idx); | |||
1753 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference")((void)0); | |||
1754 | } else { | |||
1755 | LLVM_DEBUG(dbgs() << ", spill before last split point.\n")do { } while (false); | |||
1756 | selectIntv(IntvIn); | |||
1757 | SlotIndex Idx = leaveIntvBefore(LSP); | |||
1758 | overlapIntv(Idx, BI.LastInstr); | |||
1759 | useIntv(Start, Idx); | |||
1760 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference")((void)0); | |||
1761 | } | |||
1762 | return; | |||
1763 | } | |||
1764 | ||||
1765 | // The interference is overlapping somewhere we wanted to use IntvIn. That | |||
1766 | // means we need to create a local interval that can be allocated a | |||
1767 | // different register. | |||
1768 | unsigned LocalIntv = openIntv(); | |||
1769 | (void)LocalIntv; | |||
1770 | LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n")do { } while (false); | |||
1771 | ||||
1772 | if (!BI.LiveOut || BI.LastInstr < LSP) { | |||
1773 | // | |||
1774 | // <<<<<<< Interference overlapping uses. | |||
1775 | // |---o---o---| Live-out on stack. | |||
1776 | // =====----____ Leave IntvIn before interference, then spill. | |||
1777 | // | |||
1778 | SlotIndex To = leaveIntvAfter(BI.LastInstr); | |||
1779 | SlotIndex From = enterIntvBefore(LeaveBefore); | |||
1780 | useIntv(From, To); | |||
1781 | selectIntv(IntvIn); | |||
1782 | useIntv(Start, From); | |||
1783 | assert((!LeaveBefore || From <= LeaveBefore) && "Interference")((void)0); | |||
1784 | return; | |||
1785 | } | |||
1786 | ||||
1787 | // <<<<<<< Interference overlapping uses. | |||
1788 | // |---o---o--o| Live-out on stack, late last use. | |||
1789 | // =====------- Copy to stack before LSP, overlap LocalIntv. | |||
1790 | // \_____ Stack interval is live-out. | |||
1791 | // | |||
1792 | SlotIndex To = leaveIntvBefore(LSP); | |||
1793 | overlapIntv(To, BI.LastInstr); | |||
1794 | SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); | |||
1795 | useIntv(From, To); | |||
1796 | selectIntv(IntvIn); | |||
1797 | useIntv(Start, From); | |||
1798 | assert((!LeaveBefore || From <= LeaveBefore) && "Interference")((void)0); | |||
1799 | } | |||
1800 | ||||
1801 | void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, | |||
1802 | unsigned IntvOut, SlotIndex EnterAfter) { | |||
1803 | SlotIndex Start, Stop; | |||
1804 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); | |||
1805 | ||||
1806 | LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'do { } while (false) | |||
1807 | << Stop << "), uses " << BI.FirstInstr << '-'do { } while (false) | |||
1808 | << BI.LastInstr << ", reg-out " << IntvOutdo { } while (false) | |||
1809 | << ", enter after " << EnterAfterdo { } while (false) | |||
1810 | << (BI.LiveIn ? ", stack-in" : ", defined in block"))do { } while (false); | |||
1811 | ||||
1812 | SlotIndex LSP = SA.getLastSplitPoint(BI.MBB); | |||
1813 | ||||
1814 | assert(IntvOut && "Must have register out")((void)0); | |||
1815 | assert(BI.LiveOut && "Must be live-out")((void)0); | |||
1816 | assert((!EnterAfter || EnterAfter < LSP) && "Bad interference")((void)0); | |||
1817 | ||||
1818 | if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { | |||
1819 | LLVM_DEBUG(dbgs() << " after interference.\n")do { } while (false); | |||
1820 | // | |||
1821 | // >>>> Interference before def. | |||
1822 | // | o---o---| Defined in block. | |||
1823 | // ========= Use IntvOut everywhere. | |||
1824 | // | |||
1825 | selectIntv(IntvOut); | |||
1826 | useIntv(BI.FirstInstr, Stop); | |||
1827 | return; | |||
1828 | } | |||
1829 | ||||
1830 | if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { | |||
1831 | LLVM_DEBUG(dbgs() << ", reload after interference.\n")do { } while (false); | |||
1832 | // | |||
1833 | // >>>> Interference before def. | |||
1834 | // |---o---o---| Live-through, stack-in. | |||
1835 | // ____========= Enter IntvOut before first use. | |||
1836 | // | |||
1837 | selectIntv(IntvOut); | |||
1838 | SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr)); | |||
1839 | useIntv(Idx, Stop); | |||
1840 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference")((void)0); | |||
1841 | return; | |||
1842 | } | |||
1843 | ||||
1844 | // The interference is overlapping somewhere we wanted to use IntvOut. That | |||
1845 | // means we need to create a local interval that can be allocated a | |||
1846 | // different register. | |||
1847 | LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n")do { } while (false); | |||
1848 | // | |||
1849 | // >>>>>>> Interference overlapping uses. | |||
1850 | // |---o---o---| Live-through, stack-in. | |||
1851 | // ____---====== Create local interval for interference range. | |||
1852 | // | |||
1853 | selectIntv(IntvOut); | |||
1854 | SlotIndex Idx = enterIntvAfter(EnterAfter); | |||
1855 | useIntv(Idx, Stop); | |||
1856 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference")((void)0); | |||
1857 | ||||
1858 | openIntv(); | |||
1859 | SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr)); | |||
1860 | useIntv(From, Idx); | |||
1861 | } | |||
1862 | ||||
1863 | void SplitAnalysis::BlockInfo::print(raw_ostream &OS) const { | |||
1864 | OS << "{" << printMBBReference(*MBB) << ", " | |||
1865 | << "uses " << FirstInstr << " to " << LastInstr << ", " | |||
1866 | << "1st def " << FirstDef << ", " | |||
1867 | << (LiveIn ? "live in" : "dead in") << ", " | |||
1868 | << (LiveOut ? "live out" : "dead out") << "}"; | |||
1869 | } | |||
1870 | ||||
1871 | void SplitAnalysis::BlockInfo::dump() const { | |||
1872 | print(dbgs()); | |||
1873 | dbgs() << "\n"; | |||
1874 | } |
1 | //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- 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 | // This file defines classes mirroring those in llvm/Analysis/Dominators.h, |
10 | // but for target-specific code rather than target-independent IR. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H |
15 | #define LLVM_CODEGEN_MACHINEDOMINATORS_H |
16 | |
17 | #include "llvm/ADT/SmallSet.h" |
18 | #include "llvm/ADT/SmallVector.h" |
19 | #include "llvm/CodeGen/MachineBasicBlock.h" |
20 | #include "llvm/CodeGen/MachineFunctionPass.h" |
21 | #include "llvm/CodeGen/MachineInstr.h" |
22 | #include "llvm/Support/GenericDomTree.h" |
23 | #include "llvm/Support/GenericDomTreeConstruction.h" |
24 | #include <cassert> |
25 | #include <memory> |
26 | |
27 | namespace llvm { |
28 | |
29 | template <> |
30 | inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot( |
31 | MachineBasicBlock *MBB) { |
32 | this->Roots.push_back(MBB); |
33 | } |
34 | |
35 | extern template class DomTreeNodeBase<MachineBasicBlock>; |
36 | extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree |
37 | extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree |
38 | |
39 | using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; |
40 | |
41 | //===------------------------------------- |
42 | /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to |
43 | /// compute a normal dominator tree. |
44 | /// |
45 | class MachineDominatorTree : public MachineFunctionPass { |
46 | using DomTreeT = DomTreeBase<MachineBasicBlock>; |
47 | |
48 | /// Helper structure used to hold all the basic blocks |
49 | /// involved in the split of a critical edge. |
50 | struct CriticalEdge { |
51 | MachineBasicBlock *FromBB; |
52 | MachineBasicBlock *ToBB; |
53 | MachineBasicBlock *NewBB; |
54 | }; |
55 | |
56 | /// Pile up all the critical edges to be split. |
57 | /// The splitting of a critical edge is local and thus, it is possible |
58 | /// to apply several of those changes at the same time. |
59 | mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit; |
60 | |
61 | /// Remember all the basic blocks that are inserted during |
62 | /// edge splitting. |
63 | /// Invariant: NewBBs == all the basic blocks contained in the NewBB |
64 | /// field of all the elements of CriticalEdgesToSplit. |
65 | /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs |
66 | /// such as BB == elt.NewBB. |
67 | mutable SmallSet<MachineBasicBlock *, 32> NewBBs; |
68 | |
69 | /// The DominatorTreeBase that is used to compute a normal dominator tree. |
70 | std::unique_ptr<DomTreeT> DT; |
71 | |
72 | /// Apply all the recorded critical edges to the DT. |
73 | /// This updates the underlying DT information in a way that uses |
74 | /// the fast query path of DT as much as possible. |
75 | /// |
76 | /// \post CriticalEdgesToSplit.empty(). |
77 | void applySplitCriticalEdges() const; |
78 | |
79 | public: |
80 | static char ID; // Pass ID, replacement for typeid |
81 | |
82 | MachineDominatorTree(); |
83 | explicit MachineDominatorTree(MachineFunction &MF) : MachineFunctionPass(ID) { |
84 | calculate(MF); |
85 | } |
86 | |
87 | DomTreeT &getBase() { |
88 | if (!DT) DT.reset(new DomTreeT()); |
89 | applySplitCriticalEdges(); |
90 | return *DT; |
91 | } |
92 | |
93 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
94 | |
95 | MachineBasicBlock *getRoot() const { |
96 | applySplitCriticalEdges(); |
97 | return DT->getRoot(); |
98 | } |
99 | |
100 | MachineDomTreeNode *getRootNode() const { |
101 | applySplitCriticalEdges(); |
102 | return DT->getRootNode(); |
103 | } |
104 | |
105 | bool runOnMachineFunction(MachineFunction &F) override; |
106 | |
107 | void calculate(MachineFunction &F); |
108 | |
109 | bool dominates(const MachineDomTreeNode *A, |
110 | const MachineDomTreeNode *B) const { |
111 | applySplitCriticalEdges(); |
112 | return DT->dominates(A, B); |
113 | } |
114 | |
115 | bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const { |
116 | applySplitCriticalEdges(); |
117 | return DT->dominates(A, B); |
118 | } |
119 | |
120 | // dominates - Return true if A dominates B. This performs the |
121 | // special checks necessary if A and B are in the same basic block. |
122 | bool dominates(const MachineInstr *A, const MachineInstr *B) const { |
123 | applySplitCriticalEdges(); |
124 | const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); |
125 | if (BBA != BBB) return DT->dominates(BBA, BBB); |
126 | |
127 | // Loop through the basic block until we find A or B. |
128 | MachineBasicBlock::const_iterator I = BBA->begin(); |
129 | for (; &*I != A && &*I != B; ++I) |
130 | /*empty*/ ; |
131 | |
132 | return &*I == A; |
133 | } |
134 | |
135 | bool properlyDominates(const MachineDomTreeNode *A, |
136 | const MachineDomTreeNode *B) const { |
137 | applySplitCriticalEdges(); |
138 | return DT->properlyDominates(A, B); |
139 | } |
140 | |
141 | bool properlyDominates(const MachineBasicBlock *A, |
142 | const MachineBasicBlock *B) const { |
143 | applySplitCriticalEdges(); |
144 | return DT->properlyDominates(A, B); |
145 | } |
146 | |
147 | /// findNearestCommonDominator - Find nearest common dominator basic block |
148 | /// for basic block A and B. If there is no such block then return NULL. |
149 | MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, |
150 | MachineBasicBlock *B) { |
151 | applySplitCriticalEdges(); |
152 | return DT->findNearestCommonDominator(A, B); |
153 | } |
154 | |
155 | MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { |
156 | applySplitCriticalEdges(); |
157 | return DT->getNode(BB); |
158 | } |
159 | |
160 | /// getNode - return the (Post)DominatorTree node for the specified basic |
161 | /// block. This is the same as using operator[] on this class. |
162 | /// |
163 | MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { |
164 | applySplitCriticalEdges(); |
165 | return DT->getNode(BB); |
166 | } |
167 | |
168 | /// addNewBlock - Add a new node to the dominator tree information. This |
169 | /// creates a new node as a child of DomBB dominator node,linking it into |
170 | /// the children list of the immediate dominator. |
171 | MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, |
172 | MachineBasicBlock *DomBB) { |
173 | applySplitCriticalEdges(); |
174 | return DT->addNewBlock(BB, DomBB); |
175 | } |
176 | |
177 | /// changeImmediateDominator - This method is used to update the dominator |
178 | /// tree information when a node's immediate dominator changes. |
179 | /// |
180 | void changeImmediateDominator(MachineBasicBlock *N, |
181 | MachineBasicBlock *NewIDom) { |
182 | applySplitCriticalEdges(); |
183 | DT->changeImmediateDominator(N, NewIDom); |
184 | } |
185 | |
186 | void changeImmediateDominator(MachineDomTreeNode *N, |
187 | MachineDomTreeNode *NewIDom) { |
188 | applySplitCriticalEdges(); |
189 | DT->changeImmediateDominator(N, NewIDom); |
190 | } |
191 | |
192 | /// eraseNode - Removes a node from the dominator tree. Block must not |
193 | /// dominate any other blocks. Removes node from its immediate dominator's |
194 | /// children list. Deletes dominator node associated with basic block BB. |
195 | void eraseNode(MachineBasicBlock *BB) { |
196 | applySplitCriticalEdges(); |
197 | DT->eraseNode(BB); |
198 | } |
199 | |
200 | /// splitBlock - BB is split and now it has one successor. Update dominator |
201 | /// tree to reflect this change. |
202 | void splitBlock(MachineBasicBlock* NewBB) { |
203 | applySplitCriticalEdges(); |
204 | DT->splitBlock(NewBB); |
205 | } |
206 | |
207 | /// isReachableFromEntry - Return true if A is dominated by the entry |
208 | /// block of the function containing it. |
209 | bool isReachableFromEntry(const MachineBasicBlock *A) { |
210 | applySplitCriticalEdges(); |
211 | return DT->isReachableFromEntry(A); |
212 | } |
213 | |
214 | void releaseMemory() override; |
215 | |
216 | void verifyAnalysis() const override; |
217 | |
218 | void print(raw_ostream &OS, const Module*) const override; |
219 | |
220 | /// Record that the critical edge (FromBB, ToBB) has been |
221 | /// split with NewBB. |
222 | /// This is best to use this method instead of directly update the |
223 | /// underlying information, because this helps mitigating the |
224 | /// number of time the DT information is invalidated. |
225 | /// |
226 | /// \note Do not use this method with regular edges. |
227 | /// |
228 | /// \note To benefit from the compile time improvement incurred by this |
229 | /// method, the users of this method have to limit the queries to the DT |
230 | /// interface between two edges splitting. In other words, they have to |
231 | /// pack the splitting of critical edges as much as possible. |
232 | void recordSplitCriticalEdge(MachineBasicBlock *FromBB, |
233 | MachineBasicBlock *ToBB, |
234 | MachineBasicBlock *NewBB) { |
235 | bool Inserted = NewBBs.insert(NewBB).second; |
236 | (void)Inserted; |
237 | assert(Inserted &&((void)0) |
238 | "A basic block inserted via edge splitting cannot appear twice")((void)0); |
239 | CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB}); |
240 | } |
241 | }; |
242 | |
243 | //===------------------------------------- |
244 | /// DominatorTree GraphTraits specialization so the DominatorTree can be |
245 | /// iterable by generic graph iterators. |
246 | /// |
247 | |
248 | template <class Node, class ChildIterator> |
249 | struct MachineDomTreeGraphTraitsBase { |
250 | using NodeRef = Node *; |
251 | using ChildIteratorType = ChildIterator; |
252 | |
253 | static NodeRef getEntryNode(NodeRef N) { return N; } |
254 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
255 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
256 | }; |
257 | |
258 | template <class T> struct GraphTraits; |
259 | |
260 | template <> |
261 | struct GraphTraits<MachineDomTreeNode *> |
262 | : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode, |
263 | MachineDomTreeNode::const_iterator> { |
264 | }; |
265 | |
266 | template <> |
267 | struct GraphTraits<const MachineDomTreeNode *> |
268 | : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode, |
269 | MachineDomTreeNode::const_iterator> { |
270 | }; |
271 | |
272 | template <> struct GraphTraits<MachineDominatorTree*> |
273 | : public GraphTraits<MachineDomTreeNode *> { |
274 | static NodeRef getEntryNode(MachineDominatorTree *DT) { |
275 | return DT->getRootNode(); |
276 | } |
277 | }; |
278 | |
279 | } // end namespace llvm |
280 | |
281 | #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H |
1 | //===- GenericDomTree.h - Generic dominator trees for graphs ----*- 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 | /// \file | |||
9 | /// | |||
10 | /// This file defines a set of templates that efficiently compute a dominator | |||
11 | /// tree over a generic graph. This is used typically in LLVM for fast | |||
12 | /// dominance queries on the CFG, but is fully generic w.r.t. the underlying | |||
13 | /// graph types. | |||
14 | /// | |||
15 | /// Unlike ADT/* graph algorithms, generic dominator tree has more requirements | |||
16 | /// on the graph's NodeRef. The NodeRef should be a pointer and, | |||
17 | /// NodeRef->getParent() must return the parent node that is also a pointer. | |||
18 | /// | |||
19 | /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits. | |||
20 | /// | |||
21 | //===----------------------------------------------------------------------===// | |||
22 | ||||
23 | #ifndef LLVM_SUPPORT_GENERICDOMTREE_H | |||
24 | #define LLVM_SUPPORT_GENERICDOMTREE_H | |||
25 | ||||
26 | #include "llvm/ADT/DenseMap.h" | |||
27 | #include "llvm/ADT/GraphTraits.h" | |||
28 | #include "llvm/ADT/STLExtras.h" | |||
29 | #include "llvm/ADT/SmallPtrSet.h" | |||
30 | #include "llvm/ADT/SmallVector.h" | |||
31 | #include "llvm/Support/CFGDiff.h" | |||
32 | #include "llvm/Support/CFGUpdate.h" | |||
33 | #include "llvm/Support/raw_ostream.h" | |||
34 | #include <algorithm> | |||
35 | #include <cassert> | |||
36 | #include <cstddef> | |||
37 | #include <iterator> | |||
38 | #include <memory> | |||
39 | #include <type_traits> | |||
40 | #include <utility> | |||
41 | ||||
42 | namespace llvm { | |||
43 | ||||
44 | template <typename NodeT, bool IsPostDom> | |||
45 | class DominatorTreeBase; | |||
46 | ||||
47 | namespace DomTreeBuilder { | |||
48 | template <typename DomTreeT> | |||
49 | struct SemiNCAInfo; | |||
50 | } // namespace DomTreeBuilder | |||
51 | ||||
52 | /// Base class for the actual dominator tree node. | |||
53 | template <class NodeT> class DomTreeNodeBase { | |||
54 | friend class PostDominatorTree; | |||
55 | friend class DominatorTreeBase<NodeT, false>; | |||
56 | friend class DominatorTreeBase<NodeT, true>; | |||
57 | friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>; | |||
58 | friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>; | |||
59 | ||||
60 | NodeT *TheBB; | |||
61 | DomTreeNodeBase *IDom; | |||
62 | unsigned Level; | |||
63 | SmallVector<DomTreeNodeBase *, 4> Children; | |||
64 | mutable unsigned DFSNumIn = ~0; | |||
65 | mutable unsigned DFSNumOut = ~0; | |||
66 | ||||
67 | public: | |||
68 | DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) | |||
69 | : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {} | |||
70 | ||||
71 | using iterator = typename SmallVector<DomTreeNodeBase *, 4>::iterator; | |||
72 | using const_iterator = | |||
73 | typename SmallVector<DomTreeNodeBase *, 4>::const_iterator; | |||
74 | ||||
75 | iterator begin() { return Children.begin(); } | |||
76 | iterator end() { return Children.end(); } | |||
77 | const_iterator begin() const { return Children.begin(); } | |||
78 | const_iterator end() const { return Children.end(); } | |||
79 | ||||
80 | DomTreeNodeBase *const &back() const { return Children.back(); } | |||
81 | DomTreeNodeBase *&back() { return Children.back(); } | |||
82 | ||||
83 | iterator_range<iterator> children() { return make_range(begin(), end()); } | |||
84 | iterator_range<const_iterator> children() const { | |||
85 | return make_range(begin(), end()); | |||
86 | } | |||
87 | ||||
88 | NodeT *getBlock() const { return TheBB; } | |||
89 | DomTreeNodeBase *getIDom() const { return IDom; } | |||
90 | unsigned getLevel() const { return Level; } | |||
91 | ||||
92 | std::unique_ptr<DomTreeNodeBase> addChild( | |||
93 | std::unique_ptr<DomTreeNodeBase> C) { | |||
94 | Children.push_back(C.get()); | |||
95 | return C; | |||
96 | } | |||
97 | ||||
98 | bool isLeaf() const { return Children.empty(); } | |||
99 | size_t getNumChildren() const { return Children.size(); } | |||
100 | ||||
101 | void clearAllChildren() { Children.clear(); } | |||
102 | ||||
103 | bool compare(const DomTreeNodeBase *Other) const { | |||
104 | if (getNumChildren() != Other->getNumChildren()) | |||
105 | return true; | |||
106 | ||||
107 | if (Level != Other->Level) return true; | |||
108 | ||||
109 | SmallPtrSet<const NodeT *, 4> OtherChildren; | |||
110 | for (const DomTreeNodeBase *I : *Other) { | |||
111 | const NodeT *Nd = I->getBlock(); | |||
112 | OtherChildren.insert(Nd); | |||
113 | } | |||
114 | ||||
115 | for (const DomTreeNodeBase *I : *this) { | |||
116 | const NodeT *N = I->getBlock(); | |||
117 | if (OtherChildren.count(N) == 0) | |||
118 | return true; | |||
119 | } | |||
120 | return false; | |||
121 | } | |||
122 | ||||
123 | void setIDom(DomTreeNodeBase *NewIDom) { | |||
124 | assert(IDom && "No immediate dominator?")((void)0); | |||
125 | if (IDom == NewIDom) return; | |||
126 | ||||
127 | auto I = find(IDom->Children, this); | |||
128 | assert(I != IDom->Children.end() &&((void)0) | |||
129 | "Not in immediate dominator children set!")((void)0); | |||
130 | // I am no longer your child... | |||
131 | IDom->Children.erase(I); | |||
132 | ||||
133 | // Switch to new dominator | |||
134 | IDom = NewIDom; | |||
135 | IDom->Children.push_back(this); | |||
136 | ||||
137 | UpdateLevel(); | |||
138 | } | |||
139 | ||||
140 | /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes | |||
141 | /// in the dominator tree. They are only guaranteed valid if | |||
142 | /// updateDFSNumbers() has been called. | |||
143 | unsigned getDFSNumIn() const { return DFSNumIn; } | |||
144 | unsigned getDFSNumOut() const { return DFSNumOut; } | |||
145 | ||||
146 | private: | |||
147 | // Return true if this node is dominated by other. Use this only if DFS info | |||
148 | // is valid. | |||
149 | bool DominatedBy(const DomTreeNodeBase *other) const { | |||
150 | return this->DFSNumIn >= other->DFSNumIn && | |||
151 | this->DFSNumOut <= other->DFSNumOut; | |||
152 | } | |||
153 | ||||
154 | void UpdateLevel() { | |||
155 | assert(IDom)((void)0); | |||
156 | if (Level == IDom->Level + 1) return; | |||
157 | ||||
158 | SmallVector<DomTreeNodeBase *, 64> WorkStack = {this}; | |||
159 | ||||
160 | while (!WorkStack.empty()) { | |||
161 | DomTreeNodeBase *Current = WorkStack.pop_back_val(); | |||
162 | Current->Level = Current->IDom->Level + 1; | |||
163 | ||||
164 | for (DomTreeNodeBase *C : *Current) { | |||
165 | assert(C->IDom)((void)0); | |||
166 | if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C); | |||
167 | } | |||
168 | } | |||
169 | } | |||
170 | }; | |||
171 | ||||
172 | template <class NodeT> | |||
173 | raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) { | |||
174 | if (Node->getBlock()) | |||
175 | Node->getBlock()->printAsOperand(O, false); | |||
176 | else | |||
177 | O << " <<exit node>>"; | |||
178 | ||||
179 | O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} [" | |||
180 | << Node->getLevel() << "]\n"; | |||
181 | ||||
182 | return O; | |||
183 | } | |||
184 | ||||
185 | template <class NodeT> | |||
186 | void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O, | |||
187 | unsigned Lev) { | |||
188 | O.indent(2 * Lev) << "[" << Lev << "] " << N; | |||
189 | for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), | |||
190 | E = N->end(); | |||
191 | I != E; ++I) | |||
192 | PrintDomTree<NodeT>(*I, O, Lev + 1); | |||
193 | } | |||
194 | ||||
195 | namespace DomTreeBuilder { | |||
196 | // The routines below are provided in a separate header but referenced here. | |||
197 | template <typename DomTreeT> | |||
198 | void Calculate(DomTreeT &DT); | |||
199 | ||||
200 | template <typename DomTreeT> | |||
201 | void CalculateWithUpdates(DomTreeT &DT, | |||
202 | ArrayRef<typename DomTreeT::UpdateType> Updates); | |||
203 | ||||
204 | template <typename DomTreeT> | |||
205 | void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, | |||
206 | typename DomTreeT::NodePtr To); | |||
207 | ||||
208 | template <typename DomTreeT> | |||
209 | void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, | |||
210 | typename DomTreeT::NodePtr To); | |||
211 | ||||
212 | template <typename DomTreeT> | |||
213 | void ApplyUpdates(DomTreeT &DT, | |||
214 | GraphDiff<typename DomTreeT::NodePtr, | |||
215 | DomTreeT::IsPostDominator> &PreViewCFG, | |||
216 | GraphDiff<typename DomTreeT::NodePtr, | |||
217 | DomTreeT::IsPostDominator> *PostViewCFG); | |||
218 | ||||
219 | template <typename DomTreeT> | |||
220 | bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL); | |||
221 | } // namespace DomTreeBuilder | |||
222 | ||||
223 | /// Core dominator tree base class. | |||
224 | /// | |||
225 | /// This class is a generic template over graph nodes. It is instantiated for | |||
226 | /// various graphs in the LLVM IR or in the code generator. | |||
227 | template <typename NodeT, bool IsPostDom> | |||
228 | class DominatorTreeBase { | |||
229 | public: | |||
230 | static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value, | |||
231 | "Currently DominatorTreeBase supports only pointer nodes"); | |||
232 | using NodeType = NodeT; | |||
233 | using NodePtr = NodeT *; | |||
234 | using ParentPtr = decltype(std::declval<NodeT *>()->getParent()); | |||
235 | static_assert(std::is_pointer<ParentPtr>::value, | |||
236 | "Currently NodeT's parent must be a pointer type"); | |||
237 | using ParentType = std::remove_pointer_t<ParentPtr>; | |||
238 | static constexpr bool IsPostDominator = IsPostDom; | |||
239 | ||||
240 | using UpdateType = cfg::Update<NodePtr>; | |||
241 | using UpdateKind = cfg::UpdateKind; | |||
242 | static constexpr UpdateKind Insert = UpdateKind::Insert; | |||
243 | static constexpr UpdateKind Delete = UpdateKind::Delete; | |||
244 | ||||
245 | enum class VerificationLevel { Fast, Basic, Full }; | |||
246 | ||||
247 | protected: | |||
248 | // Dominators always have a single root, postdominators can have more. | |||
249 | SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots; | |||
250 | ||||
251 | using DomTreeNodeMapType = | |||
252 | DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>; | |||
253 | DomTreeNodeMapType DomTreeNodes; | |||
254 | DomTreeNodeBase<NodeT> *RootNode = nullptr; | |||
255 | ParentPtr Parent = nullptr; | |||
256 | ||||
257 | mutable bool DFSInfoValid = false; | |||
258 | mutable unsigned int SlowQueries = 0; | |||
259 | ||||
260 | friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>; | |||
261 | ||||
262 | public: | |||
263 | DominatorTreeBase() {} | |||
264 | ||||
265 | DominatorTreeBase(DominatorTreeBase &&Arg) | |||
266 | : Roots(std::move(Arg.Roots)), | |||
267 | DomTreeNodes(std::move(Arg.DomTreeNodes)), | |||
268 | RootNode(Arg.RootNode), | |||
269 | Parent(Arg.Parent), | |||
270 | DFSInfoValid(Arg.DFSInfoValid), | |||
271 | SlowQueries(Arg.SlowQueries) { | |||
272 | Arg.wipe(); | |||
273 | } | |||
274 | ||||
275 | DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { | |||
276 | Roots = std::move(RHS.Roots); | |||
277 | DomTreeNodes = std::move(RHS.DomTreeNodes); | |||
278 | RootNode = RHS.RootNode; | |||
279 | Parent = RHS.Parent; | |||
280 | DFSInfoValid = RHS.DFSInfoValid; | |||
281 | SlowQueries = RHS.SlowQueries; | |||
282 | RHS.wipe(); | |||
283 | return *this; | |||
284 | } | |||
285 | ||||
286 | DominatorTreeBase(const DominatorTreeBase &) = delete; | |||
287 | DominatorTreeBase &operator=(const DominatorTreeBase &) = delete; | |||
288 | ||||
289 | /// Iteration over roots. | |||
290 | /// | |||
291 | /// This may include multiple blocks if we are computing post dominators. | |||
292 | /// For forward dominators, this will always be a single block (the entry | |||
293 | /// block). | |||
294 | using root_iterator = typename SmallVectorImpl<NodeT *>::iterator; | |||
295 | using const_root_iterator = typename SmallVectorImpl<NodeT *>::const_iterator; | |||
296 | ||||
297 | root_iterator root_begin() { return Roots.begin(); } | |||
298 | const_root_iterator root_begin() const { return Roots.begin(); } | |||
299 | root_iterator root_end() { return Roots.end(); } | |||
300 | const_root_iterator root_end() const { return Roots.end(); } | |||
301 | ||||
302 | size_t root_size() const { return Roots.size(); } | |||
303 | ||||
304 | iterator_range<root_iterator> roots() { | |||
305 | return make_range(root_begin(), root_end()); | |||
306 | } | |||
307 | iterator_range<const_root_iterator> roots() const { | |||
308 | return make_range(root_begin(), root_end()); | |||
309 | } | |||
310 | ||||
311 | /// isPostDominator - Returns true if analysis based of postdoms | |||
312 | /// | |||
313 | bool isPostDominator() const { return IsPostDominator; } | |||
314 | ||||
315 | /// compare - Return false if the other dominator tree base matches this | |||
316 | /// dominator tree base. Otherwise return true. | |||
317 | bool compare(const DominatorTreeBase &Other) const { | |||
318 | if (Parent != Other.Parent) return true; | |||
319 | ||||
320 | if (Roots.size() != Other.Roots.size()) | |||
321 | return true; | |||
322 | ||||
323 | if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin())) | |||
324 | return true; | |||
325 | ||||
326 | const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; | |||
327 | if (DomTreeNodes.size() != OtherDomTreeNodes.size()) | |||
328 | return true; | |||
329 | ||||
330 | for (const auto &DomTreeNode : DomTreeNodes) { | |||
331 | NodeT *BB = DomTreeNode.first; | |||
332 | typename DomTreeNodeMapType::const_iterator OI = | |||
333 | OtherDomTreeNodes.find(BB); | |||
334 | if (OI == OtherDomTreeNodes.end()) | |||
335 | return true; | |||
336 | ||||
337 | DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second; | |||
338 | DomTreeNodeBase<NodeT> &OtherNd = *OI->second; | |||
339 | ||||
340 | if (MyNd.compare(&OtherNd)) | |||
341 | return true; | |||
342 | } | |||
343 | ||||
344 | return false; | |||
345 | } | |||
346 | ||||
347 | /// getNode - return the (Post)DominatorTree node for the specified basic | |||
348 | /// block. This is the same as using operator[] on this class. The result | |||
349 | /// may (but is not required to) be null for a forward (backwards) | |||
350 | /// statically unreachable block. | |||
351 | DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const { | |||
352 | auto I = DomTreeNodes.find(BB); | |||
353 | if (I != DomTreeNodes.end()) | |||
354 | return I->second.get(); | |||
355 | return nullptr; | |||
356 | } | |||
357 | ||||
358 | /// See getNode. | |||
359 | DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const { | |||
360 | return getNode(BB); | |||
361 | } | |||
362 | ||||
363 | /// getRootNode - This returns the entry node for the CFG of the function. If | |||
364 | /// this tree represents the post-dominance relations for a function, however, | |||
365 | /// this root may be a node with the block == NULL. This is the case when | |||
366 | /// there are multiple exit nodes from a particular function. Consumers of | |||
367 | /// post-dominance information must be capable of dealing with this | |||
368 | /// possibility. | |||
369 | /// | |||
370 | DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } | |||
371 | const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } | |||
372 | ||||
373 | /// Get all nodes dominated by R, including R itself. | |||
374 | void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { | |||
375 | Result.clear(); | |||
376 | const DomTreeNodeBase<NodeT> *RN = getNode(R); | |||
377 | if (!RN) | |||
378 | return; // If R is unreachable, it will not be present in the DOM tree. | |||
379 | SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; | |||
380 | WL.push_back(RN); | |||
381 | ||||
382 | while (!WL.empty()) { | |||
383 | const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); | |||
384 | Result.push_back(N->getBlock()); | |||
385 | WL.append(N->begin(), N->end()); | |||
386 | } | |||
387 | } | |||
388 | ||||
389 | /// properlyDominates - Returns true iff A dominates B and A != B. | |||
390 | /// Note that this is not a constant time operation! | |||
391 | /// | |||
392 | bool properlyDominates(const DomTreeNodeBase<NodeT> *A, | |||
393 | const DomTreeNodeBase<NodeT> *B) const { | |||
394 | if (!A || !B) | |||
395 | return false; | |||
396 | if (A == B) | |||
397 | return false; | |||
398 | return dominates(A, B); | |||
399 | } | |||
400 | ||||
401 | bool properlyDominates(const NodeT *A, const NodeT *B) const; | |||
402 | ||||
403 | /// isReachableFromEntry - Return true if A is dominated by the entry | |||
404 | /// block of the function containing it. | |||
405 | bool isReachableFromEntry(const NodeT *A) const { | |||
406 | assert(!this->isPostDominator() &&((void)0) | |||
407 | "This is not implemented for post dominators")((void)0); | |||
408 | return isReachableFromEntry(getNode(const_cast<NodeT *>(A))); | |||
409 | } | |||
410 | ||||
411 | bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; } | |||
412 | ||||
413 | /// dominates - Returns true iff A dominates B. Note that this is not a | |||
414 | /// constant time operation! | |||
415 | /// | |||
416 | bool dominates(const DomTreeNodeBase<NodeT> *A, | |||
417 | const DomTreeNodeBase<NodeT> *B) const { | |||
418 | // A node trivially dominates itself. | |||
419 | if (B == A) | |||
420 | return true; | |||
421 | ||||
422 | // An unreachable node is dominated by anything. | |||
423 | if (!isReachableFromEntry(B)) | |||
424 | return true; | |||
425 | ||||
426 | // And dominates nothing. | |||
427 | if (!isReachableFromEntry(A)) | |||
428 | return false; | |||
429 | ||||
430 | if (B->getIDom() == A) return true; | |||
431 | ||||
432 | if (A->getIDom() == B) return false; | |||
433 | ||||
434 | // A can only dominate B if it is higher in the tree. | |||
435 | if (A->getLevel() >= B->getLevel()) return false; | |||
436 | ||||
437 | // Compare the result of the tree walk and the dfs numbers, if expensive | |||
438 | // checks are enabled. | |||
439 | #ifdef EXPENSIVE_CHECKS | |||
440 | assert((!DFSInfoValid ||((void)0) | |||
441 | (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&((void)0) | |||
442 | "Tree walk disagrees with dfs numbers!")((void)0); | |||
443 | #endif | |||
444 | ||||
445 | if (DFSInfoValid) | |||
446 | return B->DominatedBy(A); | |||
447 | ||||
448 | // If we end up with too many slow queries, just update the | |||
449 | // DFS numbers on the theory that we are going to keep querying. | |||
450 | SlowQueries++; | |||
451 | if (SlowQueries > 32) { | |||
452 | updateDFSNumbers(); | |||
453 | return B->DominatedBy(A); | |||
454 | } | |||
455 | ||||
456 | return dominatedBySlowTreeWalk(A, B); | |||
457 | } | |||
458 | ||||
459 | bool dominates(const NodeT *A, const NodeT *B) const; | |||
460 | ||||
461 | NodeT *getRoot() const { | |||
462 | assert(this->Roots.size() == 1 && "Should always have entry node!")((void)0); | |||
463 | return this->Roots[0]; | |||
464 | } | |||
465 | ||||
466 | /// Find nearest common dominator basic block for basic block A and B. A and B | |||
467 | /// must have tree nodes. | |||
468 | NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const { | |||
469 | assert(A && B && "Pointers are not valid")((void)0); | |||
470 | assert(A->getParent() == B->getParent() &&((void)0) | |||
471 | "Two blocks are not in same function")((void)0); | |||
472 | ||||
473 | // If either A or B is a entry block then it is nearest common dominator | |||
474 | // (for forward-dominators). | |||
475 | if (!isPostDominator()) { | |||
476 | NodeT &Entry = A->getParent()->front(); | |||
477 | if (A == &Entry || B == &Entry) | |||
478 | return &Entry; | |||
479 | } | |||
480 | ||||
481 | DomTreeNodeBase<NodeT> *NodeA = getNode(A); | |||
482 | DomTreeNodeBase<NodeT> *NodeB = getNode(B); | |||
483 | assert(NodeA && "A must be in the tree")((void)0); | |||
484 | assert(NodeB && "B must be in the tree")((void)0); | |||
485 | ||||
486 | // Use level information to go up the tree until the levels match. Then | |||
487 | // continue going up til we arrive at the same node. | |||
488 | while (NodeA != NodeB) { | |||
489 | if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB); | |||
490 | ||||
491 | NodeA = NodeA->IDom; | |||
492 | } | |||
493 | ||||
494 | return NodeA->getBlock(); | |||
| ||||
495 | } | |||
496 | ||||
497 | const NodeT *findNearestCommonDominator(const NodeT *A, | |||
498 | const NodeT *B) const { | |||
499 | // Cast away the const qualifiers here. This is ok since | |||
500 | // const is re-introduced on the return type. | |||
501 | return findNearestCommonDominator(const_cast<NodeT *>(A), | |||
502 | const_cast<NodeT *>(B)); | |||
503 | } | |||
504 | ||||
505 | bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const { | |||
506 | return isPostDominator() && !A->getBlock(); | |||
507 | } | |||
508 | ||||
509 | //===--------------------------------------------------------------------===// | |||
510 | // API to update (Post)DominatorTree information based on modifications to | |||
511 | // the CFG... | |||
512 | ||||
513 | /// Inform the dominator tree about a sequence of CFG edge insertions and | |||
514 | /// deletions and perform a batch update on the tree. | |||
515 | /// | |||
516 | /// This function should be used when there were multiple CFG updates after | |||
517 | /// the last dominator tree update. It takes care of performing the updates | |||
518 | /// in sync with the CFG and optimizes away the redundant operations that | |||
519 | /// cancel each other. | |||
520 | /// The functions expects the sequence of updates to be balanced. Eg.: | |||
521 | /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because | |||
522 | /// logically it results in a single insertions. | |||
523 | /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make | |||
524 | /// sense to insert the same edge twice. | |||
525 | /// | |||
526 | /// What's more, the functions assumes that it's safe to ask every node in the | |||
527 | /// CFG about its children and inverse children. This implies that deletions | |||
528 | /// of CFG edges must not delete the CFG nodes before calling this function. | |||
529 | /// | |||
530 | /// The applyUpdates function can reorder the updates and remove redundant | |||
531 | /// ones internally. The batch updater is also able to detect sequences of | |||
532 | /// zero and exactly one update -- it's optimized to do less work in these | |||
533 | /// cases. | |||
534 | /// | |||
535 | /// Note that for postdominators it automatically takes care of applying | |||
536 | /// updates on reverse edges internally (so there's no need to swap the | |||
537 | /// From and To pointers when constructing DominatorTree::UpdateType). | |||
538 | /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T> | |||
539 | /// with the same template parameter T. | |||
540 | /// | |||
541 | /// \param Updates An unordered sequence of updates to perform. The current | |||
542 | /// CFG and the reverse of these updates provides the pre-view of the CFG. | |||
543 | /// | |||
544 | void applyUpdates(ArrayRef<UpdateType> Updates) { | |||
545 | GraphDiff<NodePtr, IsPostDominator> PreViewCFG( | |||
546 | Updates, /*ReverseApplyUpdates=*/true); | |||
547 | DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, nullptr); | |||
548 | } | |||
549 | ||||
550 | /// \param Updates An unordered sequence of updates to perform. The current | |||
551 | /// CFG and the reverse of these updates provides the pre-view of the CFG. | |||
552 | /// \param PostViewUpdates An unordered sequence of update to perform in order | |||
553 | /// to obtain a post-view of the CFG. The DT will be updated assuming the | |||
554 | /// obtained PostViewCFG is the desired end state. | |||
555 | void applyUpdates(ArrayRef<UpdateType> Updates, | |||
556 | ArrayRef<UpdateType> PostViewUpdates) { | |||
557 | if (Updates.empty()) { | |||
558 | GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates); | |||
559 | DomTreeBuilder::ApplyUpdates(*this, PostViewCFG, &PostViewCFG); | |||
560 | } else { | |||
561 | // PreViewCFG needs to merge Updates and PostViewCFG. The updates in | |||
562 | // Updates need to be reversed, and match the direction in PostViewCFG. | |||
563 | // The PostViewCFG is created with updates reversed (equivalent to changes | |||
564 | // made to the CFG), so the PreViewCFG needs all the updates reverse | |||
565 | // applied. | |||
566 | SmallVector<UpdateType> AllUpdates(Updates.begin(), Updates.end()); | |||
567 | append_range(AllUpdates, PostViewUpdates); | |||
568 | GraphDiff<NodePtr, IsPostDom> PreViewCFG(AllUpdates, | |||
569 | /*ReverseApplyUpdates=*/true); | |||
570 | GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates); | |||
571 | DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, &PostViewCFG); | |||
572 | } | |||
573 | } | |||
574 | ||||
575 | /// Inform the dominator tree about a CFG edge insertion and update the tree. | |||
576 | /// | |||
577 | /// This function has to be called just before or just after making the update | |||
578 | /// on the actual CFG. There cannot be any other updates that the dominator | |||
579 | /// tree doesn't know about. | |||
580 | /// | |||
581 | /// Note that for postdominators it automatically takes care of inserting | |||
582 | /// a reverse edge internally (so there's no need to swap the parameters). | |||
583 | /// | |||
584 | void insertEdge(NodeT *From, NodeT *To) { | |||
585 | assert(From)((void)0); | |||
586 | assert(To)((void)0); | |||
587 | assert(From->getParent() == Parent)((void)0); | |||
588 | assert(To->getParent() == Parent)((void)0); | |||
589 | DomTreeBuilder::InsertEdge(*this, From, To); | |||
590 | } | |||
591 | ||||
592 | /// Inform the dominator tree about a CFG edge deletion and update the tree. | |||
593 | /// | |||
594 | /// This function has to be called just after making the update on the actual | |||
595 | /// CFG. An internal functions checks if the edge doesn't exist in the CFG in | |||
596 | /// DEBUG mode. There cannot be any other updates that the | |||
597 | /// dominator tree doesn't know about. | |||
598 | /// | |||
599 | /// Note that for postdominators it automatically takes care of deleting | |||
600 | /// a reverse edge internally (so there's no need to swap the parameters). | |||
601 | /// | |||
602 | void deleteEdge(NodeT *From, NodeT *To) { | |||
603 | assert(From)((void)0); | |||
604 | assert(To)((void)0); | |||
605 | assert(From->getParent() == Parent)((void)0); | |||
606 | assert(To->getParent() == Parent)((void)0); | |||
607 | DomTreeBuilder::DeleteEdge(*this, From, To); | |||
608 | } | |||
609 | ||||
610 | /// Add a new node to the dominator tree information. | |||
611 | /// | |||
612 | /// This creates a new node as a child of DomBB dominator node, linking it | |||
613 | /// into the children list of the immediate dominator. | |||
614 | /// | |||
615 | /// \param BB New node in CFG. | |||
616 | /// \param DomBB CFG node that is dominator for BB. | |||
617 | /// \returns New dominator tree node that represents new CFG node. | |||
618 | /// | |||
619 | DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { | |||
620 | assert(getNode(BB) == nullptr && "Block already in dominator tree!")((void)0); | |||
621 | DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); | |||
622 | assert(IDomNode && "Not immediate dominator specified for block!")((void)0); | |||
623 | DFSInfoValid = false; | |||
624 | return createChild(BB, IDomNode); | |||
625 | } | |||
626 | ||||
627 | /// Add a new node to the forward dominator tree and make it a new root. | |||
628 | /// | |||
629 | /// \param BB New node in CFG. | |||
630 | /// \returns New dominator tree node that represents new CFG node. | |||
631 | /// | |||
632 | DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) { | |||
633 | assert(getNode(BB) == nullptr && "Block already in dominator tree!")((void)0); | |||
634 | assert(!this->isPostDominator() &&((void)0) | |||
635 | "Cannot change root of post-dominator tree")((void)0); | |||
636 | DFSInfoValid = false; | |||
637 | DomTreeNodeBase<NodeT> *NewNode = createNode(BB); | |||
638 | if (Roots.empty()) { | |||
639 | addRoot(BB); | |||
640 | } else { | |||
641 | assert(Roots.size() == 1)((void)0); | |||
642 | NodeT *OldRoot = Roots.front(); | |||
643 | auto &OldNode = DomTreeNodes[OldRoot]; | |||
644 | OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot])); | |||
645 | OldNode->IDom = NewNode; | |||
646 | OldNode->UpdateLevel(); | |||
647 | Roots[0] = BB; | |||
648 | } | |||
649 | return RootNode = NewNode; | |||
650 | } | |||
651 | ||||
652 | /// changeImmediateDominator - This method is used to update the dominator | |||
653 | /// tree information when a node's immediate dominator changes. | |||
654 | /// | |||
655 | void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, | |||
656 | DomTreeNodeBase<NodeT> *NewIDom) { | |||
657 | assert(N && NewIDom && "Cannot change null node pointers!")((void)0); | |||
658 | DFSInfoValid = false; | |||
659 | N->setIDom(NewIDom); | |||
660 | } | |||
661 | ||||
662 | void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { | |||
663 | changeImmediateDominator(getNode(BB), getNode(NewBB)); | |||
664 | } | |||
665 | ||||
666 | /// eraseNode - Removes a node from the dominator tree. Block must not | |||
667 | /// dominate any other blocks. Removes node from its immediate dominator's | |||
668 | /// children list. Deletes dominator node associated with basic block BB. | |||
669 | void eraseNode(NodeT *BB) { | |||
670 | DomTreeNodeBase<NodeT> *Node = getNode(BB); | |||
671 | assert(Node && "Removing node that isn't in dominator tree.")((void)0); | |||
672 | assert(Node->isLeaf() && "Node is not a leaf node.")((void)0); | |||
673 | ||||
674 | DFSInfoValid = false; | |||
675 | ||||
676 | // Remove node from immediate dominator's children list. | |||
677 | DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); | |||
678 | if (IDom) { | |||
679 | const auto I = find(IDom->Children, Node); | |||
680 | assert(I != IDom->Children.end() &&((void)0) | |||
681 | "Not in immediate dominator children set!")((void)0); | |||
682 | // I am no longer your child... | |||
683 | IDom->Children.erase(I); | |||
684 | } | |||
685 | ||||
686 | DomTreeNodes.erase(BB); | |||
687 | ||||
688 | if (!IsPostDom) return; | |||
689 | ||||
690 | // Remember to update PostDominatorTree roots. | |||
691 | auto RIt = llvm::find(Roots, BB); | |||
692 | if (RIt != Roots.end()) { | |||
693 | std::swap(*RIt, Roots.back()); | |||
694 | Roots.pop_back(); | |||
695 | } | |||
696 | } | |||
697 | ||||
698 | /// splitBlock - BB is split and now it has one successor. Update dominator | |||
699 | /// tree to reflect this change. | |||
700 | void splitBlock(NodeT *NewBB) { | |||
701 | if (IsPostDominator) | |||
702 | Split<Inverse<NodeT *>>(NewBB); | |||
703 | else | |||
704 | Split<NodeT *>(NewBB); | |||
705 | } | |||
706 | ||||
707 | /// print - Convert to human readable form | |||
708 | /// | |||
709 | void print(raw_ostream &O) const { | |||
710 | O << "=============================--------------------------------\n"; | |||
711 | if (IsPostDominator) | |||
712 | O << "Inorder PostDominator Tree: "; | |||
713 | else | |||
714 | O << "Inorder Dominator Tree: "; | |||
715 | if (!DFSInfoValid) | |||
716 | O << "DFSNumbers invalid: " << SlowQueries << " slow queries."; | |||
717 | O << "\n"; | |||
718 | ||||
719 | // The postdom tree can have a null root if there are no returns. | |||
720 | if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1); | |||
721 | O << "Roots: "; | |||
722 | for (const NodePtr Block : Roots) { | |||
723 | Block->printAsOperand(O, false); | |||
724 | O << " "; | |||
725 | } | |||
726 | O << "\n"; | |||
727 | } | |||
728 | ||||
729 | public: | |||
730 | /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking | |||
731 | /// dominator tree in dfs order. | |||
732 | void updateDFSNumbers() const { | |||
733 | if (DFSInfoValid) { | |||
734 | SlowQueries = 0; | |||
735 | return; | |||
736 | } | |||
737 | ||||
738 | SmallVector<std::pair<const DomTreeNodeBase<NodeT> *, | |||
739 | typename DomTreeNodeBase<NodeT>::const_iterator>, | |||
740 | 32> WorkStack; | |||
741 | ||||
742 | const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); | |||
743 | assert((!Parent || ThisRoot) && "Empty constructed DomTree")((void)0); | |||
744 | if (!ThisRoot) | |||
745 | return; | |||
746 | ||||
747 | // Both dominators and postdominators have a single root node. In the case | |||
748 | // case of PostDominatorTree, this node is a virtual root. | |||
749 | WorkStack.push_back({ThisRoot, ThisRoot->begin()}); | |||
750 | ||||
751 | unsigned DFSNum = 0; | |||
752 | ThisRoot->DFSNumIn = DFSNum++; | |||
753 | ||||
754 | while (!WorkStack.empty()) { | |||
755 | const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; | |||
756 | const auto ChildIt = WorkStack.back().second; | |||
757 | ||||
758 | // If we visited all of the children of this node, "recurse" back up the | |||
759 | // stack setting the DFOutNum. | |||
760 | if (ChildIt == Node->end()) { | |||
761 | Node->DFSNumOut = DFSNum++; | |||
762 | WorkStack.pop_back(); | |||
763 | } else { | |||
764 | // Otherwise, recursively visit this child. | |||
765 | const DomTreeNodeBase<NodeT> *Child = *ChildIt; | |||
766 | ++WorkStack.back().second; | |||
767 | ||||
768 | WorkStack.push_back({Child, Child->begin()}); | |||
769 | Child->DFSNumIn = DFSNum++; | |||
770 | } | |||
771 | } | |||
772 | ||||
773 | SlowQueries = 0; | |||
774 | DFSInfoValid = true; | |||
775 | } | |||
776 | ||||
777 | /// recalculate - compute a dominator tree for the given function | |||
778 | void recalculate(ParentType &Func) { | |||
779 | Parent = &Func; | |||
780 | DomTreeBuilder::Calculate(*this); | |||
781 | } | |||
782 | ||||
783 | void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) { | |||
784 | Parent = &Func; | |||
785 | DomTreeBuilder::CalculateWithUpdates(*this, Updates); | |||
786 | } | |||
787 | ||||
788 | /// verify - checks if the tree is correct. There are 3 level of verification: | |||
789 | /// - Full -- verifies if the tree is correct by making sure all the | |||
790 | /// properties (including the parent and the sibling property) | |||
791 | /// hold. | |||
792 | /// Takes O(N^3) time. | |||
793 | /// | |||
794 | /// - Basic -- checks if the tree is correct, but compares it to a freshly | |||
795 | /// constructed tree instead of checking the sibling property. | |||
796 | /// Takes O(N^2) time. | |||
797 | /// | |||
798 | /// - Fast -- checks basic tree structure and compares it with a freshly | |||
799 | /// constructed tree. | |||
800 | /// Takes O(N^2) time worst case, but is faster in practise (same | |||
801 | /// as tree construction). | |||
802 | bool verify(VerificationLevel VL = VerificationLevel::Full) const { | |||
803 | return DomTreeBuilder::Verify(*this, VL); | |||
804 | } | |||
805 | ||||
806 | void reset() { | |||
807 | DomTreeNodes.clear(); | |||
808 | Roots.clear(); | |||
809 | RootNode = nullptr; | |||
810 | Parent = nullptr; | |||
811 | DFSInfoValid = false; | |||
812 | SlowQueries = 0; | |||
813 | } | |||
814 | ||||
815 | protected: | |||
816 | void addRoot(NodeT *BB) { this->Roots.push_back(BB); } | |||
817 | ||||
818 | DomTreeNodeBase<NodeT> *createChild(NodeT *BB, DomTreeNodeBase<NodeT> *IDom) { | |||
819 | return (DomTreeNodes[BB] = IDom->addChild( | |||
820 | std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom))) | |||
821 | .get(); | |||
822 | } | |||
823 | ||||
824 | DomTreeNodeBase<NodeT> *createNode(NodeT *BB) { | |||
825 | return (DomTreeNodes[BB] = | |||
826 | std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)) | |||
827 | .get(); | |||
828 | } | |||
829 | ||||
830 | // NewBB is split and now it has one successor. Update dominator tree to | |||
831 | // reflect this change. | |||
832 | template <class N> | |||
833 | void Split(typename GraphTraits<N>::NodeRef NewBB) { | |||
834 | using GraphT = GraphTraits<N>; | |||
835 | using NodeRef = typename GraphT::NodeRef; | |||
836 | assert(std::distance(GraphT::child_begin(NewBB),((void)0) | |||
837 | GraphT::child_end(NewBB)) == 1 &&((void)0) | |||
838 | "NewBB should have a single successor!")((void)0); | |||
839 | NodeRef NewBBSucc = *GraphT::child_begin(NewBB); | |||
840 | ||||
841 | SmallVector<NodeRef, 4> PredBlocks(children<Inverse<N>>(NewBB)); | |||
842 | ||||
843 | assert(!PredBlocks.empty() && "No predblocks?")((void)0); | |||
844 | ||||
845 | bool NewBBDominatesNewBBSucc = true; | |||
846 | for (auto Pred : children<Inverse<N>>(NewBBSucc)) { | |||
847 | if (Pred != NewBB && !dominates(NewBBSucc, Pred) && | |||
848 | isReachableFromEntry(Pred)) { | |||
849 | NewBBDominatesNewBBSucc = false; | |||
850 | break; | |||
851 | } | |||
852 | } | |||
853 | ||||
854 | // Find NewBB's immediate dominator and create new dominator tree node for | |||
855 | // NewBB. | |||
856 | NodeT *NewBBIDom = nullptr; | |||
857 | unsigned i = 0; | |||
858 | for (i = 0; i < PredBlocks.size(); ++i) | |||
859 | if (isReachableFromEntry(PredBlocks[i])) { | |||
860 | NewBBIDom = PredBlocks[i]; | |||
861 | break; | |||
862 | } | |||
863 | ||||
864 | // It's possible that none of the predecessors of NewBB are reachable; | |||
865 | // in that case, NewBB itself is unreachable, so nothing needs to be | |||
866 | // changed. | |||
867 | if (!NewBBIDom) return; | |||
868 | ||||
869 | for (i = i + 1; i < PredBlocks.size(); ++i) { | |||
870 | if (isReachableFromEntry(PredBlocks[i])) | |||
871 | NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); | |||
872 | } | |||
873 | ||||
874 | // Create the new dominator tree node... and set the idom of NewBB. | |||
875 | DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom); | |||
876 | ||||
877 | // If NewBB strictly dominates other blocks, then it is now the immediate | |||
878 | // dominator of NewBBSucc. Update the dominator tree as appropriate. | |||
879 | if (NewBBDominatesNewBBSucc) { | |||
880 | DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc); | |||
881 | changeImmediateDominator(NewBBSuccNode, NewBBNode); | |||
882 | } | |||
883 | } | |||
884 | ||||
885 | private: | |||
886 | bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, | |||
887 | const DomTreeNodeBase<NodeT> *B) const { | |||
888 | assert(A != B)((void)0); | |||
889 | assert(isReachableFromEntry(B))((void)0); | |||
890 | assert(isReachableFromEntry(A))((void)0); | |||
891 | ||||
892 | const unsigned ALevel = A->getLevel(); | |||
893 | const DomTreeNodeBase<NodeT> *IDom; | |||
894 | ||||
895 | // Don't walk nodes above A's subtree. When we reach A's level, we must | |||
896 | // either find A or be in some other subtree not dominated by A. | |||
897 | while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel) | |||
898 | B = IDom; // Walk up the tree | |||
899 | ||||
900 | return B == A; | |||
901 | } | |||
902 | ||||
903 | /// Wipe this tree's state without releasing any resources. | |||
904 | /// | |||
905 | /// This is essentially a post-move helper only. It leaves the object in an | |||
906 | /// assignable and destroyable state, but otherwise invalid. | |||
907 | void wipe() { | |||
908 | DomTreeNodes.clear(); | |||
909 | RootNode = nullptr; | |||
910 | Parent = nullptr; | |||
911 | } | |||
912 | }; | |||
913 | ||||
914 | template <typename T> | |||
915 | using DomTreeBase = DominatorTreeBase<T, false>; | |||
916 | ||||
917 | template <typename T> | |||
918 | using PostDomTreeBase = DominatorTreeBase<T, true>; | |||
919 | ||||
920 | // These two functions are declared out of line as a workaround for building | |||
921 | // with old (< r147295) versions of clang because of pr11642. | |||
922 | template <typename NodeT, bool IsPostDom> | |||
923 | bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A, | |||
924 | const NodeT *B) const { | |||
925 | if (A == B) | |||
926 | return true; | |||
927 | ||||
928 | // Cast away the const qualifiers here. This is ok since | |||
929 | // this function doesn't actually return the values returned | |||
930 | // from getNode. | |||
931 | return dominates(getNode(const_cast<NodeT *>(A)), | |||
932 | getNode(const_cast<NodeT *>(B))); | |||
933 | } | |||
934 | template <typename NodeT, bool IsPostDom> | |||
935 | bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates( | |||
936 | const NodeT *A, const NodeT *B) const { | |||
937 | if (A == B) | |||
938 | return false; | |||
939 | ||||
940 | // Cast away the const qualifiers here. This is ok since | |||
941 | // this function doesn't actually return the values returned | |||
942 | // from getNode. | |||
943 | return dominates(getNode(const_cast<NodeT *>(A)), | |||
944 | getNode(const_cast<NodeT *>(B))); | |||
945 | } | |||
946 | ||||
947 | } // end namespace llvm | |||
948 | ||||
949 | #endif // LLVM_SUPPORT_GENERICDOMTREE_H |
1 | //===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- 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 | // This file defines the DenseMap class. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_ADT_DENSEMAP_H |
14 | #define LLVM_ADT_DENSEMAP_H |
15 | |
16 | #include "llvm/ADT/DenseMapInfo.h" |
17 | #include "llvm/ADT/EpochTracker.h" |
18 | #include "llvm/Support/AlignOf.h" |
19 | #include "llvm/Support/Compiler.h" |
20 | #include "llvm/Support/MathExtras.h" |
21 | #include "llvm/Support/MemAlloc.h" |
22 | #include "llvm/Support/ReverseIteration.h" |
23 | #include "llvm/Support/type_traits.h" |
24 | #include <algorithm> |
25 | #include <cassert> |
26 | #include <cstddef> |
27 | #include <cstring> |
28 | #include <initializer_list> |
29 | #include <iterator> |
30 | #include <new> |
31 | #include <type_traits> |
32 | #include <utility> |
33 | |
34 | namespace llvm { |
35 | |
36 | namespace detail { |
37 | |
38 | // We extend a pair to allow users to override the bucket type with their own |
39 | // implementation without requiring two members. |
40 | template <typename KeyT, typename ValueT> |
41 | struct DenseMapPair : public std::pair<KeyT, ValueT> { |
42 | using std::pair<KeyT, ValueT>::pair; |
43 | |
44 | KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; } |
45 | const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; } |
46 | ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; } |
47 | const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; } |
48 | }; |
49 | |
50 | } // end namespace detail |
51 | |
52 | template <typename KeyT, typename ValueT, |
53 | typename KeyInfoT = DenseMapInfo<KeyT>, |
54 | typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>, |
55 | bool IsConst = false> |
56 | class DenseMapIterator; |
57 | |
58 | template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, |
59 | typename BucketT> |
60 | class DenseMapBase : public DebugEpochBase { |
61 | template <typename T> |
62 | using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; |
63 | |
64 | public: |
65 | using size_type = unsigned; |
66 | using key_type = KeyT; |
67 | using mapped_type = ValueT; |
68 | using value_type = BucketT; |
69 | |
70 | using iterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT>; |
71 | using const_iterator = |
72 | DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>; |
73 | |
74 | inline iterator begin() { |
75 | // When the map is empty, avoid the overhead of advancing/retreating past |
76 | // empty buckets. |
77 | if (empty()) |
78 | return end(); |
79 | if (shouldReverseIterate<KeyT>()) |
80 | return makeIterator(getBucketsEnd() - 1, getBuckets(), *this); |
81 | return makeIterator(getBuckets(), getBucketsEnd(), *this); |
82 | } |
83 | inline iterator end() { |
84 | return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true); |
85 | } |
86 | inline const_iterator begin() const { |
87 | if (empty()) |
88 | return end(); |
89 | if (shouldReverseIterate<KeyT>()) |
90 | return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this); |
91 | return makeConstIterator(getBuckets(), getBucketsEnd(), *this); |
92 | } |
93 | inline const_iterator end() const { |
94 | return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true); |
95 | } |
96 | |
97 | LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { |
98 | return getNumEntries() == 0; |
99 | } |
100 | unsigned size() const { return getNumEntries(); } |
101 | |
102 | /// Grow the densemap so that it can contain at least \p NumEntries items |
103 | /// before resizing again. |
104 | void reserve(size_type NumEntries) { |
105 | auto NumBuckets = getMinBucketToReserveForEntries(NumEntries); |
106 | incrementEpoch(); |
107 | if (NumBuckets > getNumBuckets()) |
108 | grow(NumBuckets); |
109 | } |
110 | |
111 | void clear() { |
112 | incrementEpoch(); |
113 | if (getNumEntries() == 0 && getNumTombstones() == 0) return; |
114 | |
115 | // If the capacity of the array is huge, and the # elements used is small, |
116 | // shrink the array. |
117 | if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { |
118 | shrink_and_clear(); |
119 | return; |
120 | } |
121 | |
122 | const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); |
123 | if (std::is_trivially_destructible<ValueT>::value) { |
124 | // Use a simpler loop when values don't need destruction. |
125 | for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) |
126 | P->getFirst() = EmptyKey; |
127 | } else { |
128 | unsigned NumEntries = getNumEntries(); |
129 | for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { |
130 | if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) { |
131 | if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { |
132 | P->getSecond().~ValueT(); |
133 | --NumEntries; |
134 | } |
135 | P->getFirst() = EmptyKey; |
136 | } |
137 | } |
138 | assert(NumEntries == 0 && "Node count imbalance!")((void)0); |
139 | } |
140 | setNumEntries(0); |
141 | setNumTombstones(0); |
142 | } |
143 | |
144 | /// Return 1 if the specified key is in the map, 0 otherwise. |
145 | size_type count(const_arg_type_t<KeyT> Val) const { |
146 | const BucketT *TheBucket; |
147 | return LookupBucketFor(Val, TheBucket) ? 1 : 0; |
148 | } |
149 | |
150 | iterator find(const_arg_type_t<KeyT> Val) { |
151 | BucketT *TheBucket; |
152 | if (LookupBucketFor(Val, TheBucket)) |
153 | return makeIterator(TheBucket, |
154 | shouldReverseIterate<KeyT>() ? getBuckets() |
155 | : getBucketsEnd(), |
156 | *this, true); |
157 | return end(); |
158 | } |
159 | const_iterator find(const_arg_type_t<KeyT> Val) const { |
160 | const BucketT *TheBucket; |
161 | if (LookupBucketFor(Val, TheBucket)) |
162 | return makeConstIterator(TheBucket, |
163 | shouldReverseIterate<KeyT>() ? getBuckets() |
164 | : getBucketsEnd(), |
165 | *this, true); |
166 | return end(); |
167 | } |
168 | |
169 | /// Alternate version of find() which allows a different, and possibly |
170 | /// less expensive, key type. |
171 | /// The DenseMapInfo is responsible for supplying methods |
172 | /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key |
173 | /// type used. |
174 | template<class LookupKeyT> |
175 | iterator find_as(const LookupKeyT &Val) { |
176 | BucketT *TheBucket; |
177 | if (LookupBucketFor(Val, TheBucket)) |
178 | return makeIterator(TheBucket, |
179 | shouldReverseIterate<KeyT>() ? getBuckets() |
180 | : getBucketsEnd(), |
181 | *this, true); |
182 | return end(); |
183 | } |
184 | template<class LookupKeyT> |
185 | const_iterator find_as(const LookupKeyT &Val) const { |
186 | const BucketT *TheBucket; |
187 | if (LookupBucketFor(Val, TheBucket)) |
188 | return makeConstIterator(TheBucket, |
189 | shouldReverseIterate<KeyT>() ? getBuckets() |
190 | : getBucketsEnd(), |
191 | *this, true); |
192 | return end(); |
193 | } |
194 | |
195 | /// lookup - Return the entry for the specified key, or a default |
196 | /// constructed value if no such entry exists. |
197 | ValueT lookup(const_arg_type_t<KeyT> Val) const { |
198 | const BucketT *TheBucket; |
199 | if (LookupBucketFor(Val, TheBucket)) |
200 | return TheBucket->getSecond(); |
201 | return ValueT(); |
202 | } |
203 | |
204 | // Inserts key,value pair into the map if the key isn't already in the map. |
205 | // If the key is already in the map, it returns false and doesn't update the |
206 | // value. |
207 | std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { |
208 | return try_emplace(KV.first, KV.second); |
209 | } |
210 | |
211 | // Inserts key,value pair into the map if the key isn't already in the map. |
212 | // If the key is already in the map, it returns false and doesn't update the |
213 | // value. |
214 | std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { |
215 | return try_emplace(std::move(KV.first), std::move(KV.second)); |
216 | } |
217 | |
218 | // Inserts key,value pair into the map if the key isn't already in the map. |
219 | // The value is constructed in-place if the key is not in the map, otherwise |
220 | // it is not moved. |
221 | template <typename... Ts> |
222 | std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) { |
223 | BucketT *TheBucket; |
224 | if (LookupBucketFor(Key, TheBucket)) |
225 | return std::make_pair(makeIterator(TheBucket, |
226 | shouldReverseIterate<KeyT>() |
227 | ? getBuckets() |
228 | : getBucketsEnd(), |
229 | *this, true), |
230 | false); // Already in map. |
231 | |
232 | // Otherwise, insert the new element. |
233 | TheBucket = |
234 | InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...); |
235 | return std::make_pair(makeIterator(TheBucket, |
236 | shouldReverseIterate<KeyT>() |
237 | ? getBuckets() |
238 | : getBucketsEnd(), |
239 | *this, true), |
240 | true); |
241 | } |
242 | |
243 | // Inserts key,value pair into the map if the key isn't already in the map. |
244 | // The value is constructed in-place if the key is not in the map, otherwise |
245 | // it is not moved. |
246 | template <typename... Ts> |
247 | std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) { |
248 | BucketT *TheBucket; |
249 | if (LookupBucketFor(Key, TheBucket)) |
250 | return std::make_pair(makeIterator(TheBucket, |
251 | shouldReverseIterate<KeyT>() |
252 | ? getBuckets() |
253 | : getBucketsEnd(), |
254 | *this, true), |
255 | false); // Already in map. |
256 | |
257 | // Otherwise, insert the new element. |
258 | TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...); |
259 | return std::make_pair(makeIterator(TheBucket, |
260 | shouldReverseIterate<KeyT>() |
261 | ? getBuckets() |
262 | : getBucketsEnd(), |
263 | *this, true), |
264 | true); |
265 | } |
266 | |
267 | /// Alternate version of insert() which allows a different, and possibly |
268 | /// less expensive, key type. |
269 | /// The DenseMapInfo is responsible for supplying methods |
270 | /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key |
271 | /// type used. |
272 | template <typename LookupKeyT> |
273 | std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV, |
274 | const LookupKeyT &Val) { |
275 | BucketT *TheBucket; |
276 | if (LookupBucketFor(Val, TheBucket)) |
277 | return std::make_pair(makeIterator(TheBucket, |
278 | shouldReverseIterate<KeyT>() |
279 | ? getBuckets() |
280 | : getBucketsEnd(), |
281 | *this, true), |
282 | false); // Already in map. |
283 | |
284 | // Otherwise, insert the new element. |
285 | TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first), |
286 | std::move(KV.second), Val); |
287 | return std::make_pair(makeIterator(TheBucket, |
288 | shouldReverseIterate<KeyT>() |
289 | ? getBuckets() |
290 | : getBucketsEnd(), |
291 | *this, true), |
292 | true); |
293 | } |
294 | |
295 | /// insert - Range insertion of pairs. |
296 | template<typename InputIt> |
297 | void insert(InputIt I, InputIt E) { |
298 | for (; I != E; ++I) |
299 | insert(*I); |
300 | } |
301 | |
302 | bool erase(const KeyT &Val) { |
303 | BucketT *TheBucket; |
304 | if (!LookupBucketFor(Val, TheBucket)) |
305 | return false; // not in map. |
306 | |
307 | TheBucket->getSecond().~ValueT(); |
308 | TheBucket->getFirst() = getTombstoneKey(); |
309 | decrementNumEntries(); |
310 | incrementNumTombstones(); |
311 | return true; |
312 | } |
313 | void erase(iterator I) { |
314 | BucketT *TheBucket = &*I; |
315 | TheBucket->getSecond().~ValueT(); |
316 | TheBucket->getFirst() = getTombstoneKey(); |
317 | decrementNumEntries(); |
318 | incrementNumTombstones(); |
319 | } |
320 | |
321 | value_type& FindAndConstruct(const KeyT &Key) { |
322 | BucketT *TheBucket; |
323 | if (LookupBucketFor(Key, TheBucket)) |
324 | return *TheBucket; |
325 | |
326 | return *InsertIntoBucket(TheBucket, Key); |
327 | } |
328 | |
329 | ValueT &operator[](const KeyT &Key) { |
330 | return FindAndConstruct(Key).second; |
331 | } |
332 | |
333 | value_type& FindAndConstruct(KeyT &&Key) { |
334 | BucketT *TheBucket; |
335 | if (LookupBucketFor(Key, TheBucket)) |
336 | return *TheBucket; |
337 | |
338 | return *InsertIntoBucket(TheBucket, std::move(Key)); |
339 | } |
340 | |
341 | ValueT &operator[](KeyT &&Key) { |
342 | return FindAndConstruct(std::move(Key)).second; |
343 | } |
344 | |
345 | /// isPointerIntoBucketsArray - Return true if the specified pointer points |
346 | /// somewhere into the DenseMap's array of buckets (i.e. either to a key or |
347 | /// value in the DenseMap). |
348 | bool isPointerIntoBucketsArray(const void *Ptr) const { |
349 | return Ptr >= getBuckets() && Ptr < getBucketsEnd(); |
350 | } |
351 | |
352 | /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets |
353 | /// array. In conjunction with the previous method, this can be used to |
354 | /// determine whether an insertion caused the DenseMap to reallocate. |
355 | const void *getPointerIntoBucketsArray() const { return getBuckets(); } |
356 | |
357 | protected: |
358 | DenseMapBase() = default; |
359 | |
360 | void destroyAll() { |
361 | if (getNumBuckets() == 0) // Nothing to do. |
362 | return; |
363 | |
364 | const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); |
365 | for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { |
366 | if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) && |
367 | !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) |
368 | P->getSecond().~ValueT(); |
369 | P->getFirst().~KeyT(); |
370 | } |
371 | } |
372 | |
373 | void initEmpty() { |
374 | setNumEntries(0); |
375 | setNumTombstones(0); |
376 | |
377 | assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&((void)0) |
378 | "# initial buckets must be a power of two!")((void)0); |
379 | const KeyT EmptyKey = getEmptyKey(); |
380 | for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) |
381 | ::new (&B->getFirst()) KeyT(EmptyKey); |
382 | } |
383 | |
384 | /// Returns the number of buckets to allocate to ensure that the DenseMap can |
385 | /// accommodate \p NumEntries without need to grow(). |
386 | unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { |
387 | // Ensure that "NumEntries * 4 < NumBuckets * 3" |
388 | if (NumEntries == 0) |
389 | return 0; |
390 | // +1 is required because of the strict equality. |
391 | // For example if NumEntries is 48, we need to return 401. |
392 | return NextPowerOf2(NumEntries * 4 / 3 + 1); |
393 | } |
394 | |
395 | void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { |
396 | initEmpty(); |
397 | |
398 | // Insert all the old elements. |
399 | const KeyT EmptyKey = getEmptyKey(); |
400 | const KeyT TombstoneKey = getTombstoneKey(); |
401 | for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { |
402 | if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) && |
403 | !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) { |
404 | // Insert the key/value into the new table. |
405 | BucketT *DestBucket; |
406 | bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket); |
407 | (void)FoundVal; // silence warning. |
408 | assert(!FoundVal && "Key already in new map?")((void)0); |
409 | DestBucket->getFirst() = std::move(B->getFirst()); |
410 | ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond())); |
411 | incrementNumEntries(); |
412 | |
413 | // Free the value. |
414 | B->getSecond().~ValueT(); |
415 | } |
416 | B->getFirst().~KeyT(); |
417 | } |
418 | } |
419 | |
420 | template <typename OtherBaseT> |
421 | void copyFrom( |
422 | const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) { |
423 | assert(&other != this)((void)0); |
424 | assert(getNumBuckets() == other.getNumBuckets())((void)0); |
425 | |
426 | setNumEntries(other.getNumEntries()); |
427 | setNumTombstones(other.getNumTombstones()); |
428 | |
429 | if (std::is_trivially_copyable<KeyT>::value && |
430 | std::is_trivially_copyable<ValueT>::value) |
431 | memcpy(reinterpret_cast<void *>(getBuckets()), other.getBuckets(), |
432 | getNumBuckets() * sizeof(BucketT)); |
433 | else |
434 | for (size_t i = 0; i < getNumBuckets(); ++i) { |
435 | ::new (&getBuckets()[i].getFirst()) |
436 | KeyT(other.getBuckets()[i].getFirst()); |
437 | if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) && |
438 | !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey())) |
439 | ::new (&getBuckets()[i].getSecond()) |
440 | ValueT(other.getBuckets()[i].getSecond()); |
441 | } |
442 | } |
443 | |
444 | static unsigned getHashValue(const KeyT &Val) { |
445 | return KeyInfoT::getHashValue(Val); |
446 | } |
447 | |
448 | template<typename LookupKeyT> |
449 | static unsigned getHashValue(const LookupKeyT &Val) { |
450 | return KeyInfoT::getHashValue(Val); |
451 | } |
452 | |
453 | static const KeyT getEmptyKey() { |
454 | static_assert(std::is_base_of<DenseMapBase, DerivedT>::value, |
455 | "Must pass the derived type to this template!"); |
456 | return KeyInfoT::getEmptyKey(); |
457 | } |
458 | |
459 | static const KeyT getTombstoneKey() { |
460 | return KeyInfoT::getTombstoneKey(); |
461 | } |
462 | |
463 | private: |
464 | iterator makeIterator(BucketT *P, BucketT *E, |
465 | DebugEpochBase &Epoch, |
466 | bool NoAdvance=false) { |
467 | if (shouldReverseIterate<KeyT>()) { |
468 | BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1; |
469 | return iterator(B, E, Epoch, NoAdvance); |
470 | } |
471 | return iterator(P, E, Epoch, NoAdvance); |
472 | } |
473 | |
474 | const_iterator makeConstIterator(const BucketT *P, const BucketT *E, |
475 | const DebugEpochBase &Epoch, |
476 | const bool NoAdvance=false) const { |
477 | if (shouldReverseIterate<KeyT>()) { |
478 | const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1; |
479 | return const_iterator(B, E, Epoch, NoAdvance); |
480 | } |
481 | return const_iterator(P, E, Epoch, NoAdvance); |
482 | } |
483 | |
484 | unsigned getNumEntries() const { |
485 | return static_cast<const DerivedT *>(this)->getNumEntries(); |
486 | } |
487 | |
488 | void setNumEntries(unsigned Num) { |
489 | static_cast<DerivedT *>(this)->setNumEntries(Num); |
490 | } |
491 | |
492 | void incrementNumEntries() { |
493 | setNumEntries(getNumEntries() + 1); |
494 | } |
495 | |
496 | void decrementNumEntries() { |
497 | setNumEntries(getNumEntries() - 1); |
498 | } |
499 | |
500 | unsigned getNumTombstones() const { |
501 | return static_cast<const DerivedT *>(this)->getNumTombstones(); |
502 | } |
503 | |
504 | void setNumTombstones(unsigned Num) { |
505 | static_cast<DerivedT *>(this)->setNumTombstones(Num); |
506 | } |
507 | |
508 | void incrementNumTombstones() { |
509 | setNumTombstones(getNumTombstones() + 1); |
510 | } |
511 | |
512 | void decrementNumTombstones() { |
513 | setNumTombstones(getNumTombstones() - 1); |
514 | } |
515 | |
516 | const BucketT *getBuckets() const { |
517 | return static_cast<const DerivedT *>(this)->getBuckets(); |
518 | } |
519 | |
520 | BucketT *getBuckets() { |
521 | return static_cast<DerivedT *>(this)->getBuckets(); |
522 | } |
523 | |
524 | unsigned getNumBuckets() const { |
525 | return static_cast<const DerivedT *>(this)->getNumBuckets(); |
526 | } |
527 | |
528 | BucketT *getBucketsEnd() { |
529 | return getBuckets() + getNumBuckets(); |
530 | } |
531 | |
532 | const BucketT *getBucketsEnd() const { |
533 | return getBuckets() + getNumBuckets(); |
534 | } |
535 | |
536 | void grow(unsigned AtLeast) { |
537 | static_cast<DerivedT *>(this)->grow(AtLeast); |
538 | } |
539 | |
540 | void shrink_and_clear() { |
541 | static_cast<DerivedT *>(this)->shrink_and_clear(); |
542 | } |
543 | |
544 | template <typename KeyArg, typename... ValueArgs> |
545 | BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key, |
546 | ValueArgs &&... Values) { |
547 | TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket); |
548 | |
549 | TheBucket->getFirst() = std::forward<KeyArg>(Key); |
550 | ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...); |
551 | return TheBucket; |
552 | } |
553 | |
554 | template <typename LookupKeyT> |
555 | BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key, |
556 | ValueT &&Value, LookupKeyT &Lookup) { |
557 | TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket); |
558 | |
559 | TheBucket->getFirst() = std::move(Key); |
560 | ::new (&TheBucket->getSecond()) ValueT(std::move(Value)); |
561 | return TheBucket; |
562 | } |
563 | |
564 | template <typename LookupKeyT> |
565 | BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup, |
566 | BucketT *TheBucket) { |
567 | incrementEpoch(); |
568 | |
569 | // If the load of the hash table is more than 3/4, or if fewer than 1/8 of |
570 | // the buckets are empty (meaning that many are filled with tombstones), |
571 | // grow the table. |
572 | // |
573 | // The later case is tricky. For example, if we had one empty bucket with |
574 | // tons of tombstones, failing lookups (e.g. for insertion) would have to |
575 | // probe almost the entire table until it found the empty bucket. If the |
576 | // table completely filled with tombstones, no lookup would ever succeed, |
577 | // causing infinite loops in lookup. |
578 | unsigned NewNumEntries = getNumEntries() + 1; |
579 | unsigned NumBuckets = getNumBuckets(); |
580 | if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)__builtin_expect((bool)(NewNumEntries * 4 >= NumBuckets * 3 ), false)) { |
581 | this->grow(NumBuckets * 2); |
582 | LookupBucketFor(Lookup, TheBucket); |
583 | NumBuckets = getNumBuckets(); |
584 | } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=__builtin_expect((bool)(NumBuckets-(NewNumEntries+getNumTombstones ()) <= NumBuckets/8), false) |
585 | NumBuckets/8)__builtin_expect((bool)(NumBuckets-(NewNumEntries+getNumTombstones ()) <= NumBuckets/8), false)) { |
586 | this->grow(NumBuckets); |
587 | LookupBucketFor(Lookup, TheBucket); |
588 | } |
589 | assert(TheBucket)((void)0); |
590 | |
591 | // Only update the state after we've grown our bucket space appropriately |
592 | // so that when growing buckets we have self-consistent entry count. |
593 | incrementNumEntries(); |
594 | |
595 | // If we are writing over a tombstone, remember this. |
596 | const KeyT EmptyKey = getEmptyKey(); |
597 | if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey)) |
598 | decrementNumTombstones(); |
599 | |
600 | return TheBucket; |
601 | } |
602 | |
603 | /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in |
604 | /// FoundBucket. If the bucket contains the key and a value, this returns |
605 | /// true, otherwise it returns a bucket with an empty marker or tombstone and |
606 | /// returns false. |
607 | template<typename LookupKeyT> |
608 | bool LookupBucketFor(const LookupKeyT &Val, |
609 | const BucketT *&FoundBucket) const { |
610 | const BucketT *BucketsPtr = getBuckets(); |
611 | const unsigned NumBuckets = getNumBuckets(); |
612 | |
613 | if (NumBuckets == 0) { |
614 | FoundBucket = nullptr; |
615 | return false; |
616 | } |
617 | |
618 | // FoundTombstone - Keep track of whether we find a tombstone while probing. |
619 | const BucketT *FoundTombstone = nullptr; |
620 | const KeyT EmptyKey = getEmptyKey(); |
621 | const KeyT TombstoneKey = getTombstoneKey(); |
622 | assert(!KeyInfoT::isEqual(Val, EmptyKey) &&((void)0) |
623 | !KeyInfoT::isEqual(Val, TombstoneKey) &&((void)0) |
624 | "Empty/Tombstone value shouldn't be inserted into map!")((void)0); |
625 | |
626 | unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); |
627 | unsigned ProbeAmt = 1; |
628 | while (true) { |
629 | const BucketT *ThisBucket = BucketsPtr + BucketNo; |
630 | // Found Val's bucket? If so, return it. |
631 | if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))__builtin_expect((bool)(KeyInfoT::isEqual(Val, ThisBucket-> getFirst())), true)) { |
632 | FoundBucket = ThisBucket; |
633 | return true; |
634 | } |
635 | |
636 | // If we found an empty bucket, the key doesn't exist in the set. |
637 | // Insert it and return the default value. |
638 | if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))__builtin_expect((bool)(KeyInfoT::isEqual(ThisBucket->getFirst (), EmptyKey)), true)) { |
639 | // If we've already seen a tombstone while probing, fill it in instead |
640 | // of the empty bucket we eventually probed to. |
641 | FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; |
642 | return false; |
643 | } |
644 | |
645 | // If this is a tombstone, remember it. If Val ends up not in the map, we |
646 | // prefer to return it than something that would require more probing. |
647 | if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) && |
648 | !FoundTombstone) |
649 | FoundTombstone = ThisBucket; // Remember the first tombstone found. |
650 | |
651 | // Otherwise, it's a hash collision or a tombstone, continue quadratic |
652 | // probing. |
653 | BucketNo += ProbeAmt++; |
654 | BucketNo &= (NumBuckets-1); |
655 | } |
656 | } |
657 | |
658 | template <typename LookupKeyT> |
659 | bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { |
660 | const BucketT *ConstFoundBucket; |
661 | bool Result = const_cast<const DenseMapBase *>(this) |
662 | ->LookupBucketFor(Val, ConstFoundBucket); |
663 | FoundBucket = const_cast<BucketT *>(ConstFoundBucket); |
664 | return Result; |
665 | } |
666 | |
667 | public: |
668 | /// Return the approximate size (in bytes) of the actual map. |
669 | /// This is just the raw memory used by DenseMap. |
670 | /// If entries are pointers to objects, the size of the referenced objects |
671 | /// are not included. |
672 | size_t getMemorySize() const { |
673 | return getNumBuckets() * sizeof(BucketT); |
674 | } |
675 | }; |
676 | |
677 | /// Equality comparison for DenseMap. |
678 | /// |
679 | /// Iterates over elements of LHS confirming that each (key, value) pair in LHS |
680 | /// is also in RHS, and that no additional pairs are in RHS. |
681 | /// Equivalent to N calls to RHS.find and N value comparisons. Amortized |
682 | /// complexity is linear, worst case is O(N^2) (if every hash collides). |
683 | template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, |
684 | typename BucketT> |
685 | bool operator==( |
686 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS, |
687 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) { |
688 | if (LHS.size() != RHS.size()) |
689 | return false; |
690 | |
691 | for (auto &KV : LHS) { |
692 | auto I = RHS.find(KV.first); |
693 | if (I == RHS.end() || I->second != KV.second) |
694 | return false; |
695 | } |
696 | |
697 | return true; |
698 | } |
699 | |
700 | /// Inequality comparison for DenseMap. |
701 | /// |
702 | /// Equivalent to !(LHS == RHS). See operator== for performance notes. |
703 | template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, |
704 | typename BucketT> |
705 | bool operator!=( |
706 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS, |
707 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) { |
708 | return !(LHS == RHS); |
709 | } |
710 | |
711 | template <typename KeyT, typename ValueT, |
712 | typename KeyInfoT = DenseMapInfo<KeyT>, |
713 | typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>> |
714 | class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>, |
715 | KeyT, ValueT, KeyInfoT, BucketT> { |
716 | friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
717 | |
718 | // Lift some types from the dependent base class into this class for |
719 | // simplicity of referring to them. |
720 | using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
721 | |
722 | BucketT *Buckets; |
723 | unsigned NumEntries; |
724 | unsigned NumTombstones; |
725 | unsigned NumBuckets; |
726 | |
727 | public: |
728 | /// Create a DenseMap with an optional \p InitialReserve that guarantee that |
729 | /// this number of elements can be inserted in the map without grow() |
730 | explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); } |
731 | |
732 | DenseMap(const DenseMap &other) : BaseT() { |
733 | init(0); |
734 | copyFrom(other); |
735 | } |
736 | |
737 | DenseMap(DenseMap &&other) : BaseT() { |
738 | init(0); |
739 | swap(other); |
740 | } |
741 | |
742 | template<typename InputIt> |
743 | DenseMap(const InputIt &I, const InputIt &E) { |
744 | init(std::distance(I, E)); |
745 | this->insert(I, E); |
746 | } |
747 | |
748 | DenseMap(std::initializer_list<typename BaseT::value_type> Vals) { |
749 | init(Vals.size()); |
750 | this->insert(Vals.begin(), Vals.end()); |
751 | } |
752 | |
753 | ~DenseMap() { |
754 | this->destroyAll(); |
755 | deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); |
756 | } |
757 | |
758 | void swap(DenseMap& RHS) { |
759 | this->incrementEpoch(); |
760 | RHS.incrementEpoch(); |
761 | std::swap(Buckets, RHS.Buckets); |
762 | std::swap(NumEntries, RHS.NumEntries); |
763 | std::swap(NumTombstones, RHS.NumTombstones); |
764 | std::swap(NumBuckets, RHS.NumBuckets); |
765 | } |
766 | |
767 | DenseMap& operator=(const DenseMap& other) { |
768 | if (&other != this) |
769 | copyFrom(other); |
770 | return *this; |
771 | } |
772 | |
773 | DenseMap& operator=(DenseMap &&other) { |
774 | this->destroyAll(); |
775 | deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); |
776 | init(0); |
777 | swap(other); |
778 | return *this; |
779 | } |
780 | |
781 | void copyFrom(const DenseMap& other) { |
782 | this->destroyAll(); |
783 | deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); |
784 | if (allocateBuckets(other.NumBuckets)) { |
785 | this->BaseT::copyFrom(other); |
786 | } else { |
787 | NumEntries = 0; |
788 | NumTombstones = 0; |
789 | } |
790 | } |
791 | |
792 | void init(unsigned InitNumEntries) { |
793 | auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries); |
794 | if (allocateBuckets(InitBuckets)) { |
795 | this->BaseT::initEmpty(); |
796 | } else { |
797 | NumEntries = 0; |
798 | NumTombstones = 0; |
799 | } |
800 | } |
801 | |
802 | void grow(unsigned AtLeast) { |
803 | unsigned OldNumBuckets = NumBuckets; |
804 | BucketT *OldBuckets = Buckets; |
805 | |
806 | allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1)))); |
807 | assert(Buckets)((void)0); |
808 | if (!OldBuckets) { |
809 | this->BaseT::initEmpty(); |
810 | return; |
811 | } |
812 | |
813 | this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); |
814 | |
815 | // Free the old table. |
816 | deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets, |
817 | alignof(BucketT)); |
818 | } |
819 | |
820 | void shrink_and_clear() { |
821 | unsigned OldNumBuckets = NumBuckets; |
822 | unsigned OldNumEntries = NumEntries; |
823 | this->destroyAll(); |
824 | |
825 | // Reduce the number of buckets. |
826 | unsigned NewNumBuckets = 0; |
827 | if (OldNumEntries) |
828 | NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); |
829 | if (NewNumBuckets == NumBuckets) { |
830 | this->BaseT::initEmpty(); |
831 | return; |
832 | } |
833 | |
834 | deallocate_buffer(Buckets, sizeof(BucketT) * OldNumBuckets, |
835 | alignof(BucketT)); |
836 | init(NewNumBuckets); |
837 | } |
838 | |
839 | private: |
840 | unsigned getNumEntries() const { |
841 | return NumEntries; |
842 | } |
843 | |
844 | void setNumEntries(unsigned Num) { |
845 | NumEntries = Num; |
846 | } |
847 | |
848 | unsigned getNumTombstones() const { |
849 | return NumTombstones; |
850 | } |
851 | |
852 | void setNumTombstones(unsigned Num) { |
853 | NumTombstones = Num; |
854 | } |
855 | |
856 | BucketT *getBuckets() const { |
857 | return Buckets; |
858 | } |
859 | |
860 | unsigned getNumBuckets() const { |
861 | return NumBuckets; |
862 | } |
863 | |
864 | bool allocateBuckets(unsigned Num) { |
865 | NumBuckets = Num; |
866 | if (NumBuckets == 0) { |
867 | Buckets = nullptr; |
868 | return false; |
869 | } |
870 | |
871 | Buckets = static_cast<BucketT *>( |
872 | allocate_buffer(sizeof(BucketT) * NumBuckets, alignof(BucketT))); |
873 | return true; |
874 | } |
875 | }; |
876 | |
877 | template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4, |
878 | typename KeyInfoT = DenseMapInfo<KeyT>, |
879 | typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>> |
880 | class SmallDenseMap |
881 | : public DenseMapBase< |
882 | SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT, |
883 | ValueT, KeyInfoT, BucketT> { |
884 | friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
885 | |
886 | // Lift some types from the dependent base class into this class for |
887 | // simplicity of referring to them. |
888 | using BaseT = DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
889 | |
890 | static_assert(isPowerOf2_64(InlineBuckets), |
891 | "InlineBuckets must be a power of 2."); |
892 | |
893 | unsigned Small : 1; |
894 | unsigned NumEntries : 31; |
895 | unsigned NumTombstones; |
896 | |
897 | struct LargeRep { |
898 | BucketT *Buckets; |
899 | unsigned NumBuckets; |
900 | }; |
901 | |
902 | /// A "union" of an inline bucket array and the struct representing |
903 | /// a large bucket. This union will be discriminated by the 'Small' bit. |
904 | AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage; |
905 | |
906 | public: |
907 | explicit SmallDenseMap(unsigned NumInitBuckets = 0) { |
908 | init(NumInitBuckets); |
909 | } |
910 | |
911 | SmallDenseMap(const SmallDenseMap &other) : BaseT() { |
912 | init(0); |
913 | copyFrom(other); |
914 | } |
915 | |
916 | SmallDenseMap(SmallDenseMap &&other) : BaseT() { |
917 | init(0); |
918 | swap(other); |
919 | } |
920 | |
921 | template<typename InputIt> |
922 | SmallDenseMap(const InputIt &I, const InputIt &E) { |
923 | init(NextPowerOf2(std::distance(I, E))); |
924 | this->insert(I, E); |
925 | } |
926 | |
927 | SmallDenseMap(std::initializer_list<typename BaseT::value_type> Vals) |
928 | : SmallDenseMap(Vals.begin(), Vals.end()) {} |
929 | |
930 | ~SmallDenseMap() { |
931 | this->destroyAll(); |
932 | deallocateBuckets(); |
933 | } |
934 | |
935 | void swap(SmallDenseMap& RHS) { |
936 | unsigned TmpNumEntries = RHS.NumEntries; |
937 | RHS.NumEntries = NumEntries; |
938 | NumEntries = TmpNumEntries; |
939 | std::swap(NumTombstones, RHS.NumTombstones); |
940 | |
941 | const KeyT EmptyKey = this->getEmptyKey(); |
942 | const KeyT TombstoneKey = this->getTombstoneKey(); |
943 | if (Small && RHS.Small) { |
944 | // If we're swapping inline bucket arrays, we have to cope with some of |
945 | // the tricky bits of DenseMap's storage system: the buckets are not |
946 | // fully initialized. Thus we swap every key, but we may have |
947 | // a one-directional move of the value. |
948 | for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { |
949 | BucketT *LHSB = &getInlineBuckets()[i], |
950 | *RHSB = &RHS.getInlineBuckets()[i]; |
951 | bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) && |
952 | !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey)); |
953 | bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) && |
954 | !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey)); |
955 | if (hasLHSValue && hasRHSValue) { |
956 | // Swap together if we can... |
957 | std::swap(*LHSB, *RHSB); |
958 | continue; |
959 | } |
960 | // Swap separately and handle any asymmetry. |
961 | std::swap(LHSB->getFirst(), RHSB->getFirst()); |
962 | if (hasLHSValue) { |
963 | ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond())); |
964 | LHSB->getSecond().~ValueT(); |
965 | } else if (hasRHSValue) { |
966 | ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond())); |
967 | RHSB->getSecond().~ValueT(); |
968 | } |
969 | } |
970 | return; |
971 | } |
972 | if (!Small && !RHS.Small) { |
973 | std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets); |
974 | std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets); |
975 | return; |
976 | } |
977 | |
978 | SmallDenseMap &SmallSide = Small ? *this : RHS; |
979 | SmallDenseMap &LargeSide = Small ? RHS : *this; |
980 | |
981 | // First stash the large side's rep and move the small side across. |
982 | LargeRep TmpRep = std::move(*LargeSide.getLargeRep()); |
983 | LargeSide.getLargeRep()->~LargeRep(); |
984 | LargeSide.Small = true; |
985 | // This is similar to the standard move-from-old-buckets, but the bucket |
986 | // count hasn't actually rotated in this case. So we have to carefully |
987 | // move construct the keys and values into their new locations, but there |
988 | // is no need to re-hash things. |
989 | for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { |
990 | BucketT *NewB = &LargeSide.getInlineBuckets()[i], |
991 | *OldB = &SmallSide.getInlineBuckets()[i]; |
992 | ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst())); |
993 | OldB->getFirst().~KeyT(); |
994 | if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) && |
995 | !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) { |
996 | ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond())); |
997 | OldB->getSecond().~ValueT(); |
998 | } |
999 | } |
1000 | |
1001 | // The hard part of moving the small buckets across is done, just move |
1002 | // the TmpRep into its new home. |
1003 | SmallSide.Small = false; |
1004 | new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep)); |
1005 | } |
1006 | |
1007 | SmallDenseMap& operator=(const SmallDenseMap& other) { |
1008 | if (&other != this) |
1009 | copyFrom(other); |
1010 | return *this; |
1011 | } |
1012 | |
1013 | SmallDenseMap& operator=(SmallDenseMap &&other) { |
1014 | this->destroyAll(); |
1015 | deallocateBuckets(); |
1016 | init(0); |
1017 | swap(other); |
1018 | return *this; |
1019 | } |
1020 | |
1021 | void copyFrom(const SmallDenseMap& other) { |
1022 | this->destroyAll(); |
1023 | deallocateBuckets(); |
1024 | Small = true; |
1025 | if (other.getNumBuckets() > InlineBuckets) { |
1026 | Small = false; |
1027 | new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets())); |
1028 | } |
1029 | this->BaseT::copyFrom(other); |
1030 | } |
1031 | |
1032 | void init(unsigned InitBuckets) { |
1033 | Small = true; |
1034 | if (InitBuckets > InlineBuckets) { |
1035 | Small = false; |
1036 | new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets)); |
1037 | } |
1038 | this->BaseT::initEmpty(); |
1039 | } |
1040 | |
1041 | void grow(unsigned AtLeast) { |
1042 | if (AtLeast > InlineBuckets) |
1043 | AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1)); |
1044 | |
1045 | if (Small) { |
1046 | // First move the inline buckets into a temporary storage. |
1047 | AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage; |
1048 | BucketT *TmpBegin = reinterpret_cast<BucketT *>(&TmpStorage); |
1049 | BucketT *TmpEnd = TmpBegin; |
1050 | |
1051 | // Loop over the buckets, moving non-empty, non-tombstones into the |
1052 | // temporary storage. Have the loop move the TmpEnd forward as it goes. |
1053 | const KeyT EmptyKey = this->getEmptyKey(); |
1054 | const KeyT TombstoneKey = this->getTombstoneKey(); |
1055 | for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { |
1056 | if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) && |
1057 | !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { |
1058 | assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&((void)0) |
1059 | "Too many inline buckets!")((void)0); |
1060 | ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst())); |
1061 | ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond())); |
1062 | ++TmpEnd; |
1063 | P->getSecond().~ValueT(); |
1064 | } |
1065 | P->getFirst().~KeyT(); |
1066 | } |
1067 | |
1068 | // AtLeast == InlineBuckets can happen if there are many tombstones, |
1069 | // and grow() is used to remove them. Usually we always switch to the |
1070 | // large rep here. |
1071 | if (AtLeast > InlineBuckets) { |
1072 | Small = false; |
1073 | new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); |
1074 | } |
1075 | this->moveFromOldBuckets(TmpBegin, TmpEnd); |
1076 | return; |
1077 | } |
1078 | |
1079 | LargeRep OldRep = std::move(*getLargeRep()); |
1080 | getLargeRep()->~LargeRep(); |
1081 | if (AtLeast <= InlineBuckets) { |
1082 | Small = true; |
1083 | } else { |
1084 | new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); |
1085 | } |
1086 | |
1087 | this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets); |
1088 | |
1089 | // Free the old table. |
1090 | deallocate_buffer(OldRep.Buckets, sizeof(BucketT) * OldRep.NumBuckets, |
1091 | alignof(BucketT)); |
1092 | } |
1093 | |
1094 | void shrink_and_clear() { |
1095 | unsigned OldSize = this->size(); |
1096 | this->destroyAll(); |
1097 | |
1098 | // Reduce the number of buckets. |
1099 | unsigned NewNumBuckets = 0; |
1100 | if (OldSize) { |
1101 | NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1); |
1102 | if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u) |
1103 | NewNumBuckets = 64; |
1104 | } |
1105 | if ((Small && NewNumBuckets <= InlineBuckets) || |
1106 | (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) { |
1107 | this->BaseT::initEmpty(); |
1108 | return; |
1109 | } |
1110 | |
1111 | deallocateBuckets(); |
1112 | init(NewNumBuckets); |
1113 | } |
1114 | |
1115 | private: |
1116 | unsigned getNumEntries() const { |
1117 | return NumEntries; |
1118 | } |
1119 | |
1120 | void setNumEntries(unsigned Num) { |
1121 | // NumEntries is hardcoded to be 31 bits wide. |
1122 | assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries")((void)0); |
1123 | NumEntries = Num; |
1124 | } |
1125 | |
1126 | unsigned getNumTombstones() const { |
1127 | return NumTombstones; |
1128 | } |
1129 | |
1130 | void setNumTombstones(unsigned Num) { |
1131 | NumTombstones = Num; |
1132 | } |
1133 | |
1134 | const BucketT *getInlineBuckets() const { |
1135 | assert(Small)((void)0); |
1136 | // Note that this cast does not violate aliasing rules as we assert that |
1137 | // the memory's dynamic type is the small, inline bucket buffer, and the |
1138 | // 'storage' is a POD containing a char buffer. |
1139 | return reinterpret_cast<const BucketT *>(&storage); |
1140 | } |
1141 | |
1142 | BucketT *getInlineBuckets() { |
1143 | return const_cast<BucketT *>( |
1144 | const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); |
1145 | } |
1146 | |
1147 | const LargeRep *getLargeRep() const { |
1148 | assert(!Small)((void)0); |
1149 | // Note, same rule about aliasing as with getInlineBuckets. |
1150 | return reinterpret_cast<const LargeRep *>(&storage); |
1151 | } |
1152 | |
1153 | LargeRep *getLargeRep() { |
1154 | return const_cast<LargeRep *>( |
1155 | const_cast<const SmallDenseMap *>(this)->getLargeRep()); |
1156 | } |
1157 | |
1158 | const BucketT *getBuckets() const { |
1159 | return Small ? getInlineBuckets() : getLargeRep()->Buckets; |
1160 | } |
1161 | |
1162 | BucketT *getBuckets() { |
1163 | return const_cast<BucketT *>( |
1164 | const_cast<const SmallDenseMap *>(this)->getBuckets()); |
1165 | } |
1166 | |
1167 | unsigned getNumBuckets() const { |
1168 | return Small ? InlineBuckets : getLargeRep()->NumBuckets; |
1169 | } |
1170 | |
1171 | void deallocateBuckets() { |
1172 | if (Small) |
1173 | return; |
1174 | |
1175 | deallocate_buffer(getLargeRep()->Buckets, |
1176 | sizeof(BucketT) * getLargeRep()->NumBuckets, |
1177 | alignof(BucketT)); |
1178 | getLargeRep()->~LargeRep(); |
1179 | } |
1180 | |
1181 | LargeRep allocateBuckets(unsigned Num) { |
1182 | assert(Num > InlineBuckets && "Must allocate more buckets than are inline")((void)0); |
1183 | LargeRep Rep = {static_cast<BucketT *>(allocate_buffer( |
1184 | sizeof(BucketT) * Num, alignof(BucketT))), |
1185 | Num}; |
1186 | return Rep; |
1187 | } |
1188 | }; |
1189 | |
1190 | template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket, |
1191 | bool IsConst> |
1192 | class DenseMapIterator : DebugEpochBase::HandleBase { |
1193 | friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>; |
1194 | friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>; |
1195 | |
1196 | public: |
1197 | using difference_type = ptrdiff_t; |
1198 | using value_type = |
1199 | typename std::conditional<IsConst, const Bucket, Bucket>::type; |
1200 | using pointer = value_type *; |
1201 | using reference = value_type &; |
1202 | using iterator_category = std::forward_iterator_tag; |
1203 | |
1204 | private: |
1205 | pointer Ptr = nullptr; |
1206 | pointer End = nullptr; |
1207 | |
1208 | public: |
1209 | DenseMapIterator() = default; |
1210 | |
1211 | DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch, |
1212 | bool NoAdvance = false) |
1213 | : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { |
1214 | assert(isHandleInSync() && "invalid construction!")((void)0); |
1215 | |
1216 | if (NoAdvance) return; |
1217 | if (shouldReverseIterate<KeyT>()) { |
1218 | RetreatPastEmptyBuckets(); |
1219 | return; |
1220 | } |
1221 | AdvancePastEmptyBuckets(); |
1222 | } |
1223 | |
1224 | // Converting ctor from non-const iterators to const iterators. SFINAE'd out |
1225 | // for const iterator destinations so it doesn't end up as a user defined copy |
1226 | // constructor. |
1227 | template <bool IsConstSrc, |
1228 | typename = std::enable_if_t<!IsConstSrc && IsConst>> |
1229 | DenseMapIterator( |
1230 | const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I) |
1231 | : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {} |
1232 | |
1233 | reference operator*() const { |
1234 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
1235 | assert(Ptr != End && "dereferencing end() iterator")((void)0); |
1236 | if (shouldReverseIterate<KeyT>()) |
1237 | return Ptr[-1]; |
1238 | return *Ptr; |
1239 | } |
1240 | pointer operator->() const { |
1241 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
1242 | assert(Ptr != End && "dereferencing end() iterator")((void)0); |
1243 | if (shouldReverseIterate<KeyT>()) |
1244 | return &(Ptr[-1]); |
1245 | return Ptr; |
1246 | } |
1247 | |
1248 | friend bool operator==(const DenseMapIterator &LHS, |
1249 | const DenseMapIterator &RHS) { |
1250 | assert((!LHS.Ptr || LHS.isHandleInSync()) && "handle not in sync!")((void)0); |
1251 | assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!")((void)0); |
1252 | assert(LHS.getEpochAddress() == RHS.getEpochAddress() &&((void)0) |
1253 | "comparing incomparable iterators!")((void)0); |
1254 | return LHS.Ptr == RHS.Ptr; |
1255 | } |
1256 | |
1257 | friend bool operator!=(const DenseMapIterator &LHS, |
1258 | const DenseMapIterator &RHS) { |
1259 | return !(LHS == RHS); |
1260 | } |
1261 | |
1262 | inline DenseMapIterator& operator++() { // Preincrement |
1263 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
1264 | assert(Ptr != End && "incrementing end() iterator")((void)0); |
1265 | if (shouldReverseIterate<KeyT>()) { |
1266 | --Ptr; |
1267 | RetreatPastEmptyBuckets(); |
1268 | return *this; |
1269 | } |
1270 | ++Ptr; |
1271 | AdvancePastEmptyBuckets(); |
1272 | return *this; |
1273 | } |
1274 | DenseMapIterator operator++(int) { // Postincrement |
1275 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
1276 | DenseMapIterator tmp = *this; ++*this; return tmp; |
1277 | } |
1278 | |
1279 | private: |
1280 | void AdvancePastEmptyBuckets() { |
1281 | assert(Ptr <= End)((void)0); |
1282 | const KeyT Empty = KeyInfoT::getEmptyKey(); |
1283 | const KeyT Tombstone = KeyInfoT::getTombstoneKey(); |
1284 | |
1285 | while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) || |
1286 | KeyInfoT::isEqual(Ptr->getFirst(), Tombstone))) |
1287 | ++Ptr; |
1288 | } |
1289 | |
1290 | void RetreatPastEmptyBuckets() { |
1291 | assert(Ptr >= End)((void)0); |
1292 | const KeyT Empty = KeyInfoT::getEmptyKey(); |
1293 | const KeyT Tombstone = KeyInfoT::getTombstoneKey(); |
1294 | |
1295 | while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) || |
1296 | KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone))) |
1297 | --Ptr; |
1298 | } |
1299 | }; |
1300 | |
1301 | template <typename KeyT, typename ValueT, typename KeyInfoT> |
1302 | inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { |
1303 | return X.getMemorySize(); |
1304 | } |
1305 | |
1306 | } // end namespace llvm |
1307 | |
1308 | #endif // LLVM_ADT_DENSEMAP_H |