Bug Summary

File:llvm/lib/CodeGen/InlineSpiller.cpp
Warning:line 1348, column 14
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name InlineSpiller.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/lib/CodeGen -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-08-28-193554-24367-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp

→
1//===- InlineSpiller.cpp - Insert spills and restores inline --------------===//
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// The inline spiller modifies the machine function directly instead of
10// inserting spills and restores in VirtRegMap.
11//
12//===----------------------------------------------------------------------===//
13
14#include "SplitKit.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/MapVector.h"
18#include "llvm/ADT/None.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SetVector.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/AliasAnalysis.h"
25#include "llvm/CodeGen/LiveInterval.h"
26#include "llvm/CodeGen/LiveIntervalCalc.h"
27#include "llvm/CodeGen/LiveIntervals.h"
28#include "llvm/CodeGen/LiveRangeEdit.h"
29#include "llvm/CodeGen/LiveStacks.h"
30#include "llvm/CodeGen/MachineBasicBlock.h"
31#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
32#include "llvm/CodeGen/MachineDominators.h"
33#include "llvm/CodeGen/MachineFunction.h"
34#include "llvm/CodeGen/MachineFunctionPass.h"
35#include "llvm/CodeGen/MachineInstr.h"
36#include "llvm/CodeGen/MachineInstrBuilder.h"
37#include "llvm/CodeGen/MachineInstrBundle.h"
38#include "llvm/CodeGen/MachineLoopInfo.h"
39#include "llvm/CodeGen/MachineOperand.h"
40#include "llvm/CodeGen/MachineRegisterInfo.h"
41#include "llvm/CodeGen/SlotIndexes.h"
42#include "llvm/CodeGen/Spiller.h"
43#include "llvm/CodeGen/StackMaps.h"
44#include "llvm/CodeGen/TargetInstrInfo.h"
45#include "llvm/CodeGen/TargetOpcodes.h"
46#include "llvm/CodeGen/TargetRegisterInfo.h"
47#include "llvm/CodeGen/TargetSubtargetInfo.h"
48#include "llvm/CodeGen/VirtRegMap.h"
49#include "llvm/Config/llvm-config.h"
50#include "llvm/Support/BlockFrequency.h"
51#include "llvm/Support/BranchProbability.h"
52#include "llvm/Support/CommandLine.h"
53#include "llvm/Support/Compiler.h"
54#include "llvm/Support/Debug.h"
55#include "llvm/Support/ErrorHandling.h"
56#include "llvm/Support/raw_ostream.h"
57#include <cassert>
58#include <iterator>
59#include <tuple>
60#include <utility>
61#include <vector>
62
63using namespace llvm;
64
65#define DEBUG_TYPE"regalloc" "regalloc"
66
67STATISTIC(NumSpilledRanges, "Number of spilled live ranges")static llvm::Statistic NumSpilledRanges = {"regalloc", "NumSpilledRanges"
, "Number of spilled live ranges"};
68STATISTIC(NumSnippets, "Number of spilled snippets")static llvm::Statistic NumSnippets = {"regalloc", "NumSnippets"
, "Number of spilled snippets"};
69STATISTIC(NumSpills, "Number of spills inserted")static llvm::Statistic NumSpills = {"regalloc", "NumSpills", "Number of spills inserted"
};
70STATISTIC(NumSpillsRemoved, "Number of spills removed")static llvm::Statistic NumSpillsRemoved = {"regalloc", "NumSpillsRemoved"
, "Number of spills removed"};
71STATISTIC(NumReloads, "Number of reloads inserted")static llvm::Statistic NumReloads = {"regalloc", "NumReloads"
, "Number of reloads inserted"};
72STATISTIC(NumReloadsRemoved, "Number of reloads removed")static llvm::Statistic NumReloadsRemoved = {"regalloc", "NumReloadsRemoved"
, "Number of reloads removed"};
73STATISTIC(NumFolded, "Number of folded stack accesses")static llvm::Statistic NumFolded = {"regalloc", "NumFolded", "Number of folded stack accesses"
};
74STATISTIC(NumFoldedLoads, "Number of folded loads")static llvm::Statistic NumFoldedLoads = {"regalloc", "NumFoldedLoads"
, "Number of folded loads"};
75STATISTIC(NumRemats, "Number of rematerialized defs for spilling")static llvm::Statistic NumRemats = {"regalloc", "NumRemats", "Number of rematerialized defs for spilling"
};
76
77static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden,
78 cl::desc("Disable inline spill hoisting"));
79static cl::opt<bool>
80RestrictStatepointRemat("restrict-statepoint-remat",
81 cl::init(false), cl::Hidden,
82 cl::desc("Restrict remat for statepoint operands"));
83
84namespace {
85
86class HoistSpillHelper : private LiveRangeEdit::Delegate {
87 MachineFunction &MF;
88 LiveIntervals &LIS;
89 LiveStacks &LSS;
90 AliasAnalysis *AA;
91 MachineDominatorTree &MDT;
92 MachineLoopInfo &Loops;
93 VirtRegMap &VRM;
94 MachineRegisterInfo &MRI;
95 const TargetInstrInfo &TII;
96 const TargetRegisterInfo &TRI;
97 const MachineBlockFrequencyInfo &MBFI;
98
99 InsertPointAnalysis IPA;
100
101 // Map from StackSlot to the LiveInterval of the original register.
102 // Note the LiveInterval of the original register may have been deleted
103 // after it is spilled. We keep a copy here to track the range where
104 // spills can be moved.
105 DenseMap<int, std::unique_ptr<LiveInterval>> StackSlotToOrigLI;
106
107 // Map from pair of (StackSlot and Original VNI) to a set of spills which
108 // have the same stackslot and have equal values defined by Original VNI.
109 // These spills are mergeable and are hoist candiates.
110 using MergeableSpillsMap =
111 MapVector<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>;
112 MergeableSpillsMap MergeableSpills;
113
114 /// This is the map from original register to a set containing all its
115 /// siblings. To hoist a spill to another BB, we need to find out a live
116 /// sibling there and use it as the source of the new spill.
117 DenseMap<Register, SmallSetVector<Register, 16>> Virt2SiblingsMap;
118
119 bool isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
120 MachineBasicBlock &BB, Register &LiveReg);
121
122 void rmRedundantSpills(
123 SmallPtrSet<MachineInstr *, 16> &Spills,
124 SmallVectorImpl<MachineInstr *> &SpillsToRm,
125 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);
126
127 void getVisitOrders(
128 MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
129 SmallVectorImpl<MachineDomTreeNode *> &Orders,
130 SmallVectorImpl<MachineInstr *> &SpillsToRm,
131 DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep,
132 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);
133
134 void runHoistSpills(LiveInterval &OrigLI, VNInfo &OrigVNI,
135 SmallPtrSet<MachineInstr *, 16> &Spills,
136 SmallVectorImpl<MachineInstr *> &SpillsToRm,
137 DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns);
138
139public:
140 HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf,
141 VirtRegMap &vrm)
142 : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
143 LSS(pass.getAnalysis<LiveStacks>()),
144 AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
145 MDT(pass.getAnalysis<MachineDominatorTree>()),
146 Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
147 MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()),
148 TRI(*mf.getSubtarget().getRegisterInfo()),
149 MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()),
150 IPA(LIS, mf.getNumBlockIDs()) {}
151
152 void addToMergeableSpills(MachineInstr &Spill, int StackSlot,
153 unsigned Original);
154 bool rmFromMergeableSpills(MachineInstr &Spill, int StackSlot);
155 void hoistAllSpills();
156 void LRE_DidCloneVirtReg(Register, Register) override;
157};
158
159class InlineSpiller : public Spiller {
160 MachineFunction &MF;
161 LiveIntervals &LIS;
162 LiveStacks &LSS;
163 AliasAnalysis *AA;
164 MachineDominatorTree &MDT;
165 MachineLoopInfo &Loops;
166 VirtRegMap &VRM;
167 MachineRegisterInfo &MRI;
168 const TargetInstrInfo &TII;
169 const TargetRegisterInfo &TRI;
170 const MachineBlockFrequencyInfo &MBFI;
171
172 // Variables that are valid during spill(), but used by multiple methods.
173 LiveRangeEdit *Edit;
174 LiveInterval *StackInt;
175 int StackSlot;
176 Register Original;
177
178 // All registers to spill to StackSlot, including the main register.
179 SmallVector<Register, 8> RegsToSpill;
180
181 // All COPY instructions to/from snippets.
182 // They are ignored since both operands refer to the same stack slot.
183 SmallPtrSet<MachineInstr*, 8> SnippetCopies;
184
185 // Values that failed to remat at some point.
186 SmallPtrSet<VNInfo*, 8> UsedValues;
187
188 // Dead defs generated during spilling.
189 SmallVector<MachineInstr*, 8> DeadDefs;
190
191 // Object records spills information and does the hoisting.
192 HoistSpillHelper HSpiller;
193
194 // Live range weight calculator.
195 VirtRegAuxInfo &VRAI;
196
197 ~InlineSpiller() override = default;
198
199public:
200 InlineSpiller(MachineFunctionPass &Pass, MachineFunction &MF, VirtRegMap &VRM,
201 VirtRegAuxInfo &VRAI)
202 : MF(MF), LIS(Pass.getAnalysis<LiveIntervals>()),
203 LSS(Pass.getAnalysis<LiveStacks>()),
204 AA(&Pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
205 MDT(Pass.getAnalysis<MachineDominatorTree>()),
206 Loops(Pass.getAnalysis<MachineLoopInfo>()), VRM(VRM),
207 MRI(MF.getRegInfo()), TII(*MF.getSubtarget().getInstrInfo()),
208 TRI(*MF.getSubtarget().getRegisterInfo()),
209 MBFI(Pass.getAnalysis<MachineBlockFrequencyInfo>()),
210 HSpiller(Pass, MF, VRM), VRAI(VRAI) {}
211
212 void spill(LiveRangeEdit &) override;
213 void postOptimization() override;
214
215private:
216 bool isSnippet(const LiveInterval &SnipLI);
217 void collectRegsToSpill();
218
219 bool isRegToSpill(Register Reg) { return is_contained(RegsToSpill, Reg); }
220
221 bool isSibling(Register Reg);
222 bool hoistSpillInsideBB(LiveInterval &SpillLI, MachineInstr &CopyMI);
223 void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);
224
225 void markValueUsed(LiveInterval*, VNInfo*);
226 bool canGuaranteeAssignmentAfterRemat(Register VReg, MachineInstr &MI);
227 bool reMaterializeFor(LiveInterval &, MachineInstr &MI);
228 void reMaterializeAll();
229
230 bool coalesceStackAccess(MachineInstr *MI, Register Reg);
231 bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>>,
232 MachineInstr *LoadMI = nullptr);
233 void insertReload(Register VReg, SlotIndex, MachineBasicBlock::iterator MI);
234 void insertSpill(Register VReg, bool isKill, MachineBasicBlock::iterator MI);
235
236 void spillAroundUses(Register Reg);
237 void spillAll();
238};
239
240} // end anonymous namespace
241
242Spiller::~Spiller() = default;
243
244void Spiller::anchor() {}
245
246Spiller *llvm::createInlineSpiller(MachineFunctionPass &Pass,
247 MachineFunction &MF, VirtRegMap &VRM,
248 VirtRegAuxInfo &VRAI) {
249 return new InlineSpiller(Pass, MF, VRM, VRAI);
250}
251
252//===----------------------------------------------------------------------===//
253// Snippets
254//===----------------------------------------------------------------------===//
255
256// When spilling a virtual register, we also spill any snippets it is connected
257// to. The snippets are small live ranges that only have a single real use,
258// leftovers from live range splitting. Spilling them enables memory operand
259// folding or tightens the live range around the single use.
260//
261// This minimizes register pressure and maximizes the store-to-load distance for
262// spill slots which can be important in tight loops.
263
264/// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,
265/// otherwise return 0.
266static Register isFullCopyOf(const MachineInstr &MI, Register Reg) {
267 if (!MI.isFullCopy())
268 return Register();
269 if (MI.getOperand(0).getReg() == Reg)
270 return MI.getOperand(1).getReg();
271 if (MI.getOperand(1).getReg() == Reg)
272 return MI.getOperand(0).getReg();
273 return Register();
274}
275
276static void getVDefInterval(const MachineInstr &MI, LiveIntervals &LIS) {
277 for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
278 const MachineOperand &MO = MI.getOperand(I);
279 if (MO.isReg() && MO.isDef() && Register::isVirtualRegister(MO.getReg()))
280 LIS.getInterval(MO.getReg());
281 }
282}
283
284/// isSnippet - Identify if a live interval is a snippet that should be spilled.
285/// It is assumed that SnipLI is a virtual register with the same original as
286/// Edit->getReg().
287bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {
288 Register Reg = Edit->getReg();
289
290 // A snippet is a tiny live range with only a single instruction using it
291 // besides copies to/from Reg or spills/fills. We accept:
292 //
293 // %snip = COPY %Reg / FILL fi#
294 // %snip = USE %snip
295 // %Reg = COPY %snip / SPILL %snip, fi#
296 //
297 if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI))
298 return false;
299
300 MachineInstr *UseMI = nullptr;
301
302 // Check that all uses satisfy our criteria.
303 for (MachineRegisterInfo::reg_instr_nodbg_iterator
304 RI = MRI.reg_instr_nodbg_begin(SnipLI.reg()),
305 E = MRI.reg_instr_nodbg_end();
306 RI != E;) {
307 MachineInstr &MI = *RI++;
308
309 // Allow copies to/from Reg.
310 if (isFullCopyOf(MI, Reg))
311 continue;
312
313 // Allow stack slot loads.
314 int FI;
315 if (SnipLI.reg() == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
316 continue;
317
318 // Allow stack slot stores.
319 if (SnipLI.reg() == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)
320 continue;
321
322 // Allow a single additional instruction.
323 if (UseMI && &MI != UseMI)
324 return false;
325 UseMI = &MI;
326 }
327 return true;
328}
329
330/// collectRegsToSpill - Collect live range snippets that only have a single
331/// real use.
332void InlineSpiller::collectRegsToSpill() {
333 Register Reg = Edit->getReg();
334
335 // Main register always spills.
336 RegsToSpill.assign(1, Reg);
337 SnippetCopies.clear();
338
339 // Snippets all have the same original, so there can't be any for an original
340 // register.
341 if (Original == Reg)
342 return;
343
344 for (MachineRegisterInfo::reg_instr_iterator
345 RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); RI != E; ) {
346 MachineInstr &MI = *RI++;
347 Register SnipReg = isFullCopyOf(MI, Reg);
348 if (!isSibling(SnipReg))
349 continue;
350 LiveInterval &SnipLI = LIS.getInterval(SnipReg);
351 if (!isSnippet(SnipLI))
352 continue;
353 SnippetCopies.insert(&MI);
354 if (isRegToSpill(SnipReg))
355 continue;
356 RegsToSpill.push_back(SnipReg);
357 LLVM_DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\talso spill snippet " <<
SnipLI << '\n'; } } while (false);
358 ++NumSnippets;
359 }
360}
361
362bool InlineSpiller::isSibling(Register Reg) {
363 return Reg.isVirtual() && VRM.getOriginal(Reg) == Original;
364}
365
366/// It is beneficial to spill to earlier place in the same BB in case
367/// as follows:
368/// There is an alternative def earlier in the same MBB.
369/// Hoist the spill as far as possible in SpillMBB. This can ease
370/// register pressure:
371///
372/// x = def
373/// y = use x
374/// s = copy x
375///
376/// Hoisting the spill of s to immediately after the def removes the
377/// interference between x and y:
378///
379/// x = def
380/// spill x
381/// y = use killed x
382///
383/// This hoist only helps when the copy kills its source.
384///
385bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI,
386 MachineInstr &CopyMI) {
387 SlotIndex Idx = LIS.getInstructionIndex(CopyMI);
388#ifndef NDEBUG
389 VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot());
390 assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy")(static_cast <bool> (VNI && VNI->def == Idx.
getRegSlot() && "Not defined by copy") ? void (0) : __assert_fail
("VNI && VNI->def == Idx.getRegSlot() && \"Not defined by copy\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 390, __extension__ __PRETTY_FUNCTION__));
391#endif
392
393 Register SrcReg = CopyMI.getOperand(1).getReg();
394 LiveInterval &SrcLI = LIS.getInterval(SrcReg);
395 VNInfo *SrcVNI = SrcLI.getVNInfoAt(Idx);
396 LiveQueryResult SrcQ = SrcLI.Query(Idx);
397 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(SrcVNI->def);
398 if (DefMBB != CopyMI.getParent() || !SrcQ.isKill())
399 return false;
400
401 // Conservatively extend the stack slot range to the range of the original
402 // value. We may be able to do better with stack slot coloring by being more
403 // careful here.
404 assert(StackInt && "No stack slot assigned yet.")(static_cast <bool> (StackInt && "No stack slot assigned yet."
) ? void (0) : __assert_fail ("StackInt && \"No stack slot assigned yet.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 404, __extension__ __PRETTY_FUNCTION__));
405 LiveInterval &OrigLI = LIS.getInterval(Original);
406 VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
407 StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));
408 LLVM_DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tmerged orig valno " <<
OrigVNI->id << ": " << *StackInt << '\n'
; } } while (false)
409 << *StackInt << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tmerged orig valno " <<
OrigVNI->id << ": " << *StackInt << '\n'
; } } while (false);
410
411 // We are going to spill SrcVNI immediately after its def, so clear out
412 // any later spills of the same value.
413 eliminateRedundantSpills(SrcLI, SrcVNI);
414
415 MachineBasicBlock *MBB = LIS.getMBBFromIndex(SrcVNI->def);
416 MachineBasicBlock::iterator MII;
417 if (SrcVNI->isPHIDef())
418 MII = MBB->SkipPHIsLabelsAndDebug(MBB->begin());
419 else {
420 MachineInstr *DefMI = LIS.getInstructionFromIndex(SrcVNI->def);
421 assert(DefMI && "Defining instruction disappeared")(static_cast <bool> (DefMI && "Defining instruction disappeared"
) ? void (0) : __assert_fail ("DefMI && \"Defining instruction disappeared\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 421, __extension__ __PRETTY_FUNCTION__));
422 MII = DefMI;
423 ++MII;
424 }
425 MachineInstrSpan MIS(MII, MBB);
426 // Insert spill without kill flag immediately after def.
427 TII.storeRegToStackSlot(*MBB, MII, SrcReg, false, StackSlot,
428 MRI.getRegClass(SrcReg), &TRI);
429 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MII);
430 for (const MachineInstr &MI : make_range(MIS.begin(), MII))
431 getVDefInterval(MI, LIS);
432 --MII; // Point to store instruction.
433 LLVM_DEBUG(dbgs() << "\thoisted: " << SrcVNI->def << '\t' << *MII)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\thoisted: " << SrcVNI
->def << '\t' << *MII; } } while (false);
434
435 // If there is only 1 store instruction is required for spill, add it
436 // to mergeable list. In X86 AMX, 2 intructions are required to store.
437 // We disable the merge for this case.
438 if (MIS.begin() == MII)
439 HSpiller.addToMergeableSpills(*MII, StackSlot, Original);
440 ++NumSpills;
441 return true;
442}
443
444/// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any
445/// redundant spills of this value in SLI.reg and sibling copies.
446void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
447 assert(VNI && "Missing value")(static_cast <bool> (VNI && "Missing value") ? void
(0) : __assert_fail ("VNI && \"Missing value\"", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 447, __extension__ __PRETTY_FUNCTION__));
448 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
449 WorkList.push_back(std::make_pair(&SLI, VNI));
450 assert(StackInt && "No stack slot assigned yet.")(static_cast <bool> (StackInt && "No stack slot assigned yet."
) ? void (0) : __assert_fail ("StackInt && \"No stack slot assigned yet.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 450, __extension__ __PRETTY_FUNCTION__));
451
452 do {
453 LiveInterval *LI;
454 std::tie(LI, VNI) = WorkList.pop_back_val();
455 Register Reg = LI->reg();
456 LLVM_DEBUG(dbgs() << "Checking redundant spills for " << VNI->id << '@'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Checking redundant spills for "
<< VNI->id << '@' << VNI->def <<
" in " << *LI << '\n'; } } while (false)
457 << VNI->def << " in " << *LI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Checking redundant spills for "
<< VNI->id << '@' << VNI->def <<
" in " << *LI << '\n'; } } while (false);
458
459 // Regs to spill are taken care of.
460 if (isRegToSpill(Reg))
461 continue;
462
463 // Add all of VNI's live range to StackInt.
464 StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));
465 LLVM_DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Merged to stack int: " <<
*StackInt << '\n'; } } while (false);
466
467 // Find all spills and copies of VNI.
468 for (MachineRegisterInfo::use_instr_nodbg_iterator
469 UI = MRI.use_instr_nodbg_begin(Reg), E = MRI.use_instr_nodbg_end();
470 UI != E; ) {
471 MachineInstr &MI = *UI++;
472 if (!MI.isCopy() && !MI.mayStore())
473 continue;
474 SlotIndex Idx = LIS.getInstructionIndex(MI);
475 if (LI->getVNInfoAt(Idx) != VNI)
476 continue;
477
478 // Follow sibling copies down the dominator tree.
479 if (Register DstReg = isFullCopyOf(MI, Reg)) {
480 if (isSibling(DstReg)) {
481 LiveInterval &DstLI = LIS.getInterval(DstReg);
482 VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot());
483 assert(DstVNI && "Missing defined value")(static_cast <bool> (DstVNI && "Missing defined value"
) ? void (0) : __assert_fail ("DstVNI && \"Missing defined value\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 483, __extension__ __PRETTY_FUNCTION__));
484 assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot")(static_cast <bool> (DstVNI->def == Idx.getRegSlot()
&& "Wrong copy def slot") ? void (0) : __assert_fail
("DstVNI->def == Idx.getRegSlot() && \"Wrong copy def slot\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 484, __extension__ __PRETTY_FUNCTION__));
485 WorkList.push_back(std::make_pair(&DstLI, DstVNI));
486 }
487 continue;
488 }
489
490 // Erase spills.
491 int FI;
492 if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {
493 LLVM_DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Redundant spill " << Idx
<< '\t' << MI; } } while (false);
494 // eliminateDeadDefs won't normally remove stores, so switch opcode.
495 MI.setDesc(TII.get(TargetOpcode::KILL));
496 DeadDefs.push_back(&MI);
497 ++NumSpillsRemoved;
498 if (HSpiller.rmFromMergeableSpills(MI, StackSlot))
499 --NumSpills;
500 }
501 }
502 } while (!WorkList.empty());
503}
504
505//===----------------------------------------------------------------------===//
506// Rematerialization
507//===----------------------------------------------------------------------===//
508
509/// markValueUsed - Remember that VNI failed to rematerialize, so its defining
510/// instruction cannot be eliminated. See through snippet copies
511void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) {
512 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
513 WorkList.push_back(std::make_pair(LI, VNI));
514 do {
515 std::tie(LI, VNI) = WorkList.pop_back_val();
516 if (!UsedValues.insert(VNI).second)
517 continue;
518
519 if (VNI->isPHIDef()) {
520 MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
521 for (MachineBasicBlock *P : MBB->predecessors()) {
522 VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(P));
523 if (PVNI)
524 WorkList.push_back(std::make_pair(LI, PVNI));
525 }
526 continue;
527 }
528
529 // Follow snippet copies.
530 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
531 if (!SnippetCopies.count(MI))
532 continue;
533 LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg());
534 assert(isRegToSpill(SnipLI.reg()) && "Unexpected register in copy")(static_cast <bool> (isRegToSpill(SnipLI.reg()) &&
"Unexpected register in copy") ? void (0) : __assert_fail ("isRegToSpill(SnipLI.reg()) && \"Unexpected register in copy\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 534, __extension__ __PRETTY_FUNCTION__));
535 VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true));
536 assert(SnipVNI && "Snippet undefined before copy")(static_cast <bool> (SnipVNI && "Snippet undefined before copy"
) ? void (0) : __assert_fail ("SnipVNI && \"Snippet undefined before copy\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 536, __extension__ __PRETTY_FUNCTION__));
537 WorkList.push_back(std::make_pair(&SnipLI, SnipVNI));
538 } while (!WorkList.empty());
539}
540
541bool InlineSpiller::canGuaranteeAssignmentAfterRemat(Register VReg,
542 MachineInstr &MI) {
543 if (!RestrictStatepointRemat)
544 return true;
545 // Here's a quick explanation of the problem we're trying to handle here:
546 // * There are some pseudo instructions with more vreg uses than there are
547 // physical registers on the machine.
548 // * This is normally handled by spilling the vreg, and folding the reload
549 // into the user instruction. (Thus decreasing the number of used vregs
550 // until the remainder can be assigned to physregs.)
551 // * However, since we may try to spill vregs in any order, we can end up
552 // trying to spill each operand to the instruction, and then rematting it
553 // instead. When that happens, the new live intervals (for the remats) are
554 // expected to be trivially assignable (i.e. RS_Done). However, since we
555 // may have more remats than physregs, we're guaranteed to fail to assign
556 // one.
557 // At the moment, we only handle this for STATEPOINTs since they're the only
558 // pseudo op where we've seen this. If we start seeing other instructions
559 // with the same problem, we need to revisit this.
560 if (MI.getOpcode() != TargetOpcode::STATEPOINT)
561 return true;
562 // For STATEPOINTs we allow re-materialization for fixed arguments only hoping
563 // that number of physical registers is enough to cover all fixed arguments.
564 // If it is not true we need to revisit it.
565 for (unsigned Idx = StatepointOpers(&MI).getVarIdx(),
566 EndIdx = MI.getNumOperands();
567 Idx < EndIdx; ++Idx) {
568 MachineOperand &MO = MI.getOperand(Idx);
569 if (MO.isReg() && MO.getReg() == VReg)
570 return false;
571 }
572 return true;
573}
574
575/// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
576bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) {
577 // Analyze instruction
578 SmallVector<std::pair<MachineInstr *, unsigned>, 8> Ops;
579 VirtRegInfo RI = AnalyzeVirtRegInBundle(MI, VirtReg.reg(), &Ops);
580
581 if (!RI.Reads)
582 return false;
583
584 SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);
585 VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex());
586
587 if (!ParentVNI) {
588 LLVM_DEBUG(dbgs() << "\tadding <undef> flags: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tadding <undef> flags: "
; } } while (false);
589 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
590 MachineOperand &MO = MI.getOperand(i);
591 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg())
592 MO.setIsUndef();
593 }
594 LLVM_DEBUG(dbgs() << UseIdx << '\t' << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << UseIdx << '\t' <<
MI; } } while (false);
595 return true;
596 }
597
598 if (SnippetCopies.count(&MI))
599 return false;
600
601 LiveInterval &OrigLI = LIS.getInterval(Original);
602 VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
603 LiveRangeEdit::Remat RM(ParentVNI);
604 RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
605
606 if (!Edit->canRematerializeAt(RM, OrigVNI, UseIdx, false)) {
607 markValueUsed(&VirtReg, ParentVNI);
608 LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tcannot remat for " <<
UseIdx << '\t' << MI; } } while (false);
609 return false;
610 }
611
612 // If the instruction also writes VirtReg.reg, it had better not require the
613 // same register for uses and defs.
614 if (RI.Tied) {
615 markValueUsed(&VirtReg, ParentVNI);
616 LLVM_DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tcannot remat tied reg: " <<
UseIdx << '\t' << MI; } } while (false);
617 return false;
618 }
619
620 // Before rematerializing into a register for a single instruction, try to
621 // fold a load into the instruction. That avoids allocating a new register.
622 if (RM.OrigMI->canFoldAsLoad() &&
623 foldMemoryOperand(Ops, RM.OrigMI)) {
624 Edit->markRematerialized(RM.ParentVNI);
625 ++NumFoldedLoads;
626 return true;
627 }
628
629 // If we can't guarantee that we'll be able to actually assign the new vreg,
630 // we can't remat.
631 if (!canGuaranteeAssignmentAfterRemat(VirtReg.reg(), MI)) {
632 markValueUsed(&VirtReg, ParentVNI);
633 LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tcannot remat for " <<
UseIdx << '\t' << MI; } } while (false);
634 return false;
635 }
636
637 // Allocate a new register for the remat.
638 Register NewVReg = Edit->createFrom(Original);
639
640 // Finally we can rematerialize OrigMI before MI.
641 SlotIndex DefIdx =
642 Edit->rematerializeAt(*MI.getParent(), MI, NewVReg, RM, TRI);
643
644 // We take the DebugLoc from MI, since OrigMI may be attributed to a
645 // different source location.
646 auto *NewMI = LIS.getInstructionFromIndex(DefIdx);
647 NewMI->setDebugLoc(MI.getDebugLoc());
648
649 (void)DefIdx;
650 LLVM_DEBUG(dbgs() << "\tremat: " << DefIdx << '\t'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tremat: " << DefIdx <<
'\t' << *LIS.getInstructionFromIndex(DefIdx); } } while
(false)
651 << *LIS.getInstructionFromIndex(DefIdx))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tremat: " << DefIdx <<
'\t' << *LIS.getInstructionFromIndex(DefIdx); } } while
(false);
652
653 // Replace operands
654 for (const auto &OpPair : Ops) {
655 MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
656 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg()) {
657 MO.setReg(NewVReg);
658 MO.setIsKill();
659 }
660 }
661 LLVM_DEBUG(dbgs() << "\t " << UseIdx << '\t' << MI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t " << UseIdx <<
'\t' << MI << '\n'; } } while (false);
662
663 ++NumRemats;
664 return true;
665}
666
667/// reMaterializeAll - Try to rematerialize as many uses as possible,
668/// and trim the live ranges after.
669void InlineSpiller::reMaterializeAll() {
670 if (!Edit->anyRematerializable(AA))
671 return;
672
673 UsedValues.clear();
674
675 // Try to remat before all uses of snippets.
676 bool anyRemat = false;
677 for (Register Reg : RegsToSpill) {
678 LiveInterval &LI = LIS.getInterval(Reg);
679 for (MachineRegisterInfo::reg_bundle_iterator
680 RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
681 RegI != E; ) {
682 MachineInstr &MI = *RegI++;
683
684 // Debug values are not allowed to affect codegen.
685 if (MI.isDebugValue())
686 continue;
687
688 assert(!MI.isDebugInstr() && "Did not expect to find a use in debug "(static_cast <bool> (!MI.isDebugInstr() && "Did not expect to find a use in debug "
"instruction that isn't a DBG_VALUE") ? void (0) : __assert_fail
("!MI.isDebugInstr() && \"Did not expect to find a use in debug \" \"instruction that isn't a DBG_VALUE\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 689, __extension__ __PRETTY_FUNCTION__))
689 "instruction that isn't a DBG_VALUE")(static_cast <bool> (!MI.isDebugInstr() && "Did not expect to find a use in debug "
"instruction that isn't a DBG_VALUE") ? void (0) : __assert_fail
("!MI.isDebugInstr() && \"Did not expect to find a use in debug \" \"instruction that isn't a DBG_VALUE\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 689, __extension__ __PRETTY_FUNCTION__));
690
691 anyRemat |= reMaterializeFor(LI, MI);
692 }
693 }
694 if (!anyRemat)
695 return;
696
697 // Remove any values that were completely rematted.
698 for (Register Reg : RegsToSpill) {
699 LiveInterval &LI = LIS.getInterval(Reg);
700 for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end();
701 I != E; ++I) {
702 VNInfo *VNI = *I;
703 if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI))
704 continue;
705 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
706 MI->addRegisterDead(Reg, &TRI);
707 if (!MI->allDefsAreDead())
708 continue;
709 LLVM_DEBUG(dbgs() << "All defs dead: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "All defs dead: " << *MI
; } } while (false);
710 DeadDefs.push_back(MI);
711 }
712 }
713
714 // Eliminate dead code after remat. Note that some snippet copies may be
715 // deleted here.
716 if (DeadDefs.empty())
717 return;
718 LLVM_DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Remat created " << DeadDefs
.size() << " dead defs.\n"; } } while (false);
719 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
720
721 // LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions
722 // after rematerialization. To remove a VNI for a vreg from its LiveInterval,
723 // LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all
724 // removed, PHI VNI are still left in the LiveInterval.
725 // So to get rid of unused reg, we need to check whether it has non-dbg
726 // reference instead of whether it has non-empty interval.
727 unsigned ResultPos = 0;
728 for (Register Reg : RegsToSpill) {
729 if (MRI.reg_nodbg_empty(Reg)) {
730 Edit->eraseVirtReg(Reg);
731 continue;
732 }
733
734 assert(LIS.hasInterval(Reg) &&(static_cast <bool> (LIS.hasInterval(Reg) && (!
LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) &&
"Empty and not used live-range?!") ? void (0) : __assert_fail
("LIS.hasInterval(Reg) && (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) && \"Empty and not used live-range?!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 736, __extension__ __PRETTY_FUNCTION__))
735 (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) &&(static_cast <bool> (LIS.hasInterval(Reg) && (!
LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) &&
"Empty and not used live-range?!") ? void (0) : __assert_fail
("LIS.hasInterval(Reg) && (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) && \"Empty and not used live-range?!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 736, __extension__ __PRETTY_FUNCTION__))
736 "Empty and not used live-range?!")(static_cast <bool> (LIS.hasInterval(Reg) && (!
LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) &&
"Empty and not used live-range?!") ? void (0) : __assert_fail
("LIS.hasInterval(Reg) && (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) && \"Empty and not used live-range?!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 736, __extension__ __PRETTY_FUNCTION__));
737
738 RegsToSpill[ResultPos++] = Reg;
739 }
740 RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end());
741 LLVM_DEBUG(dbgs() << RegsToSpill.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << RegsToSpill.size() << " registers to spill after remat.\n"
; } } while (false)
742 << " registers to spill after remat.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << RegsToSpill.size() << " registers to spill after remat.\n"
; } } while (false);
743}
744
745//===----------------------------------------------------------------------===//
746// Spilling
747//===----------------------------------------------------------------------===//
748
749/// If MI is a load or store of StackSlot, it can be removed.
750bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, Register Reg) {
751 int FI = 0;
752 Register InstrReg = TII.isLoadFromStackSlot(*MI, FI);
753 bool IsLoad = InstrReg;
754 if (!IsLoad)
755 InstrReg = TII.isStoreToStackSlot(*MI, FI);
756
757 // We have a stack access. Is it the right register and slot?
758 if (InstrReg != Reg || FI != StackSlot)
759 return false;
760
761 if (!IsLoad)
762 HSpiller.rmFromMergeableSpills(*MI, StackSlot);
763
764 LLVM_DEBUG(dbgs() << "Coalescing stack access: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Coalescing stack access: " <<
*MI; } } while (false);
765 LIS.RemoveMachineInstrFromMaps(*MI);
766 MI->eraseFromParent();
767
768 if (IsLoad) {
769 ++NumReloadsRemoved;
770 --NumReloads;
771 } else {
772 ++NumSpillsRemoved;
773 --NumSpills;
774 }
775
776 return true;
777}
778
779#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
780LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__))
781// Dump the range of instructions from B to E with their slot indexes.
782static void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B,
783 MachineBasicBlock::iterator E,
784 LiveIntervals const &LIS,
785 const char *const header,
786 Register VReg = Register()) {
787 char NextLine = '\n';
788 char SlotIndent = '\t';
789
790 if (std::next(B) == E) {
791 NextLine = ' ';
792 SlotIndent = ' ';
793 }
794
795 dbgs() << '\t' << header << ": " << NextLine;
796
797 for (MachineBasicBlock::iterator I = B; I != E; ++I) {
798 SlotIndex Idx = LIS.getInstructionIndex(*I).getRegSlot();
799
800 // If a register was passed in and this instruction has it as a
801 // destination that is marked as an early clobber, print the
802 // early-clobber slot index.
803 if (VReg) {
804 MachineOperand *MO = I->findRegisterDefOperand(VReg);
805 if (MO && MO->isEarlyClobber())
806 Idx = Idx.getRegSlot(true);
807 }
808
809 dbgs() << SlotIndent << Idx << '\t' << *I;
810 }
811}
812#endif
813
814/// foldMemoryOperand - Try folding stack slot references in Ops into their
815/// instructions.
816///
817/// @param Ops Operand indices from AnalyzeVirtRegInBundle().
818/// @param LoadMI Load instruction to use instead of stack slot when non-null.
819/// @return True on success.
820bool InlineSpiller::
821foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>> Ops,
822 MachineInstr *LoadMI) {
823 if (Ops.empty())
824 return false;
825 // Don't attempt folding in bundles.
826 MachineInstr *MI = Ops.front().first;
827 if (Ops.back().first != MI || MI->isBundled())
828 return false;
829
830 bool WasCopy = MI->isCopy();
831 Register ImpReg;
832
833 // TII::foldMemoryOperand will do what we need here for statepoint
834 // (fold load into use and remove corresponding def). We will replace
835 // uses of removed def with loads (spillAroundUses).
836 // For that to work we need to untie def and use to pass it through
837 // foldMemoryOperand and signal foldPatchpoint that it is allowed to
838 // fold them.
839 bool UntieRegs = MI->getOpcode() == TargetOpcode::STATEPOINT;
840
841 // Spill subregs if the target allows it.
842 // We always want to spill subregs for stackmap/patchpoint pseudos.
843 bool SpillSubRegs = TII.isSubregFoldable() ||
844 MI->getOpcode() == TargetOpcode::STATEPOINT ||
845 MI->getOpcode() == TargetOpcode::PATCHPOINT ||
846 MI->getOpcode() == TargetOpcode::STACKMAP;
847
848 // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
849 // operands.
850 SmallVector<unsigned, 8> FoldOps;
851 for (const auto &OpPair : Ops) {
852 unsigned Idx = OpPair.second;
853 assert(MI == OpPair.first && "Instruction conflict during operand folding")(static_cast <bool> (MI == OpPair.first && "Instruction conflict during operand folding"
) ? void (0) : __assert_fail ("MI == OpPair.first && \"Instruction conflict during operand folding\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 853, __extension__ __PRETTY_FUNCTION__));
854 MachineOperand &MO = MI->getOperand(Idx);
855 if (MO.isImplicit()) {
856 ImpReg = MO.getReg();
857 continue;
858 }
859
860 if (!SpillSubRegs && MO.getSubReg())
861 return false;
862 // We cannot fold a load instruction into a def.
863 if (LoadMI && MO.isDef())
864 return false;
865 // Tied use operands should not be passed to foldMemoryOperand.
866 if (UntieRegs || !MI->isRegTiedToDefOperand(Idx))
867 FoldOps.push_back(Idx);
868 }
869
870 // If we only have implicit uses, we won't be able to fold that.
871 // Moreover, TargetInstrInfo::foldMemoryOperand will assert if we try!
872 if (FoldOps.empty())
873 return false;
874
875 MachineInstrSpan MIS(MI, MI->getParent());
876
877 SmallVector<std::pair<unsigned, unsigned> > TiedOps;
878 if (UntieRegs)
879 for (unsigned Idx : FoldOps) {
880 MachineOperand &MO = MI->getOperand(Idx);
881 if (!MO.isTied())
882 continue;
883 unsigned Tied = MI->findTiedOperandIdx(Idx);
884 if (MO.isUse())
885 TiedOps.emplace_back(Tied, Idx);
886 else {
887 assert(MO.isDef() && "Tied to not use and def?")(static_cast <bool> (MO.isDef() && "Tied to not use and def?"
) ? void (0) : __assert_fail ("MO.isDef() && \"Tied to not use and def?\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 887, __extension__ __PRETTY_FUNCTION__));
888 TiedOps.emplace_back(Idx, Tied);
889 }
890 MI->untieRegOperand(Idx);
891 }
892
893 MachineInstr *FoldMI =
894 LoadMI ? TII.foldMemoryOperand(*MI, FoldOps, *LoadMI, &LIS)
895 : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS, &VRM);
896 if (!FoldMI) {
897 // Re-tie operands.
898 for (auto Tied : TiedOps)
899 MI->tieOperands(Tied.first, Tied.second);
900 return false;
901 }
902
903 // Remove LIS for any dead defs in the original MI not in FoldMI.
904 for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) {
905 if (!MO->isReg())
906 continue;
907 Register Reg = MO->getReg();
908 if (!Reg || Register::isVirtualRegister(Reg) || MRI.isReserved(Reg)) {
909 continue;
910 }
911 // Skip non-Defs, including undef uses and internal reads.
912 if (MO->isUse())
913 continue;
914 PhysRegInfo RI = AnalyzePhysRegInBundle(*FoldMI, Reg, &TRI);
915 if (RI.FullyDefined)
916 continue;
917 // FoldMI does not define this physreg. Remove the LI segment.
918 assert(MO->isDead() && "Cannot fold physreg def")(static_cast <bool> (MO->isDead() && "Cannot fold physreg def"
) ? void (0) : __assert_fail ("MO->isDead() && \"Cannot fold physreg def\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 918, __extension__ __PRETTY_FUNCTION__));
919 SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
920 LIS.removePhysRegDefAt(Reg.asMCReg(), Idx);
921 }
922
923 int FI;
924 if (TII.isStoreToStackSlot(*MI, FI) &&
925 HSpiller.rmFromMergeableSpills(*MI, FI))
926 --NumSpills;
927 LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI);
928 // Update the call site info.
929 if (MI->isCandidateForCallSiteEntry())
930 MI->getMF()->moveCallSiteInfo(MI, FoldMI);
931 MI->eraseFromParent();
932
933 // Insert any new instructions other than FoldMI into the LIS maps.
934 assert(!MIS.empty() && "Unexpected empty span of instructions!")(static_cast <bool> (!MIS.empty() && "Unexpected empty span of instructions!"
) ? void (0) : __assert_fail ("!MIS.empty() && \"Unexpected empty span of instructions!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 934, __extension__ __PRETTY_FUNCTION__));
935 for (MachineInstr &MI : MIS)
936 if (&MI != FoldMI)
937 LIS.InsertMachineInstrInMaps(MI);
938
939 // TII.foldMemoryOperand may have left some implicit operands on the
940 // instruction. Strip them.
941 if (ImpReg)
942 for (unsigned i = FoldMI->getNumOperands(); i; --i) {
943 MachineOperand &MO = FoldMI->getOperand(i - 1);
944 if (!MO.isReg() || !MO.isImplicit())
945 break;
946 if (MO.getReg() == ImpReg)
947 FoldMI->RemoveOperand(i - 1);
948 }
949
950 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS,do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dumpMachineInstrRangeWithSlotIndex(MIS.begin(
), MIS.end(), LIS, "folded"); } } while (false)
951 "folded"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dumpMachineInstrRangeWithSlotIndex(MIS.begin(
), MIS.end(), LIS, "folded"); } } while (false);
952
953 if (!WasCopy)
954 ++NumFolded;
955 else if (Ops.front().second == 0) {
956 ++NumSpills;
957 // If there is only 1 store instruction is required for spill, add it
958 // to mergeable list. In X86 AMX, 2 intructions are required to store.
959 // We disable the merge for this case.
960 if (std::distance(MIS.begin(), MIS.end()) <= 1)
961 HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original);
962 } else
963 ++NumReloads;
964 return true;
965}
966
967void InlineSpiller::insertReload(Register NewVReg,
968 SlotIndex Idx,
969 MachineBasicBlock::iterator MI) {
970 MachineBasicBlock &MBB = *MI->getParent();
971
972 MachineInstrSpan MIS(MI, &MBB);
973 TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot,
974 MRI.getRegClass(NewVReg), &TRI);
975
976 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI);
977
978 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload",do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dumpMachineInstrRangeWithSlotIndex(MIS.begin(
), MI, LIS, "reload", NewVReg); } } while (false)
979 NewVReg))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dumpMachineInstrRangeWithSlotIndex(MIS.begin(
), MI, LIS, "reload", NewVReg); } } while (false);
980 ++NumReloads;
981}
982
983/// Check if \p Def fully defines a VReg with an undefined value.
984/// If that's the case, that means the value of VReg is actually
985/// not relevant.
986static bool isRealSpill(const MachineInstr &Def) {
987 if (!Def.isImplicitDef())
988 return true;
989 assert(Def.getNumOperands() == 1 &&(static_cast <bool> (Def.getNumOperands() == 1 &&
"Implicit def with more than one definition") ? void (0) : __assert_fail
("Def.getNumOperands() == 1 && \"Implicit def with more than one definition\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 990, __extension__ __PRETTY_FUNCTION__))
990 "Implicit def with more than one definition")(static_cast <bool> (Def.getNumOperands() == 1 &&
"Implicit def with more than one definition") ? void (0) : __assert_fail
("Def.getNumOperands() == 1 && \"Implicit def with more than one definition\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 990, __extension__ __PRETTY_FUNCTION__));
991 // We can say that the VReg defined by Def is undef, only if it is
992 // fully defined by Def. Otherwise, some of the lanes may not be
993 // undef and the value of the VReg matters.
994 return Def.getOperand(0).getSubReg();
995}
996
997/// insertSpill - Insert a spill of NewVReg after MI.
998void InlineSpiller::insertSpill(Register NewVReg, bool isKill,
999 MachineBasicBlock::iterator MI) {
1000 // Spill are not terminators, so inserting spills after terminators will
1001 // violate invariants in MachineVerifier.
1002 assert(!MI->isTerminator() && "Inserting a spill after a terminator")(static_cast <bool> (!MI->isTerminator() && "Inserting a spill after a terminator"
) ? void (0) : __assert_fail ("!MI->isTerminator() && \"Inserting a spill after a terminator\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1002, __extension__ __PRETTY_FUNCTION__));
1003 MachineBasicBlock &MBB = *MI->getParent();
1004
1005 MachineInstrSpan MIS(MI, &MBB);
1006 MachineBasicBlock::iterator SpillBefore = std::next(MI);
1007 bool IsRealSpill = isRealSpill(*MI);
1008
1009 if (IsRealSpill)
1010 TII.storeRegToStackSlot(MBB, SpillBefore, NewVReg, isKill, StackSlot,
1011 MRI.getRegClass(NewVReg), &TRI);
1012 else
1013 // Don't spill undef value.
1014 // Anything works for undef, in particular keeping the memory
1015 // uninitialized is a viable option and it saves code size and
1016 // run time.
1017 BuildMI(MBB, SpillBefore, MI->getDebugLoc(), TII.get(TargetOpcode::KILL))
1018 .addReg(NewVReg, getKillRegState(isKill));
1019
1020 MachineBasicBlock::iterator Spill = std::next(MI);
1021 LIS.InsertMachineInstrRangeInMaps(Spill, MIS.end());
1022 for (const MachineInstr &MI : make_range(Spill, MIS.end()))
1023 getVDefInterval(MI, LIS);
1024
1025 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dumpMachineInstrRangeWithSlotIndex(Spill, MIS
.end(), LIS, "spill"); } } while (false)
1026 dumpMachineInstrRangeWithSlotIndex(Spill, MIS.end(), LIS, "spill"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dumpMachineInstrRangeWithSlotIndex(Spill, MIS
.end(), LIS, "spill"); } } while (false);
1027 ++NumSpills;
1028 // If there is only 1 store instruction is required for spill, add it
1029 // to mergeable list. In X86 AMX, 2 intructions are required to store.
1030 // We disable the merge for this case.
1031 if (IsRealSpill && std::distance(Spill, MIS.end()) <= 1)
1032 HSpiller.addToMergeableSpills(*Spill, StackSlot, Original);
1033}
1034
1035/// spillAroundUses - insert spill code around each use of Reg.
1036void InlineSpiller::spillAroundUses(Register Reg) {
1037 LLVM_DEBUG(dbgs() << "spillAroundUses " << printReg(Reg) << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "spillAroundUses " << printReg
(Reg) << '\n'; } } while (false);
1038 LiveInterval &OldLI = LIS.getInterval(Reg);
1039
1040 // Iterate over instructions using Reg.
1041 for (MachineRegisterInfo::reg_bundle_iterator
1042 RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
1043 RegI != E; ) {
1044 MachineInstr *MI = &*(RegI++);
1045
1046 // Debug values are not allowed to affect codegen.
1047 if (MI->isDebugValue()) {
1048 // Modify DBG_VALUE now that the value is in a spill slot.
1049 MachineBasicBlock *MBB = MI->getParent();
1050 LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:\t" << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Modifying debug info due to spill:\t"
<< *MI; } } while (false);
1051 buildDbgValueForSpill(*MBB, MI, *MI, StackSlot, Reg);
1052 MBB->erase(MI);
1053 continue;
1054 }
1055
1056 assert(!MI->isDebugInstr() && "Did not expect to find a use in debug "(static_cast <bool> (!MI->isDebugInstr() && "Did not expect to find a use in debug "
"instruction that isn't a DBG_VALUE") ? void (0) : __assert_fail
("!MI->isDebugInstr() && \"Did not expect to find a use in debug \" \"instruction that isn't a DBG_VALUE\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1057, __extension__ __PRETTY_FUNCTION__))
1057 "instruction that isn't a DBG_VALUE")(static_cast <bool> (!MI->isDebugInstr() && "Did not expect to find a use in debug "
"instruction that isn't a DBG_VALUE") ? void (0) : __assert_fail
("!MI->isDebugInstr() && \"Did not expect to find a use in debug \" \"instruction that isn't a DBG_VALUE\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1057, __extension__ __PRETTY_FUNCTION__));
1058
1059 // Ignore copies to/from snippets. We'll delete them.
1060 if (SnippetCopies.count(MI))
1061 continue;
1062
1063 // Stack slot accesses may coalesce away.
1064 if (coalesceStackAccess(MI, Reg))
1065 continue;
1066
1067 // Analyze instruction.
1068 SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops;
1069 VirtRegInfo RI = AnalyzeVirtRegInBundle(*MI, Reg, &Ops);
1070
1071 // Find the slot index where this instruction reads and writes OldLI.
1072 // This is usually the def slot, except for tied early clobbers.
1073 SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
1074 if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true)))
1075 if (SlotIndex::isSameInstr(Idx, VNI->def))
1076 Idx = VNI->def;
1077
1078 // Check for a sibling copy.
1079 Register SibReg = isFullCopyOf(*MI, Reg);
1080 if (SibReg && isSibling(SibReg)) {
1081 // This may actually be a copy between snippets.
1082 if (isRegToSpill(SibReg)) {
1083 LLVM_DEBUG(dbgs() << "Found new snippet copy: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Found new snippet copy: " <<
*MI; } } while (false);
1084 SnippetCopies.insert(MI);
1085 continue;
1086 }
1087 if (RI.Writes) {
1088 if (hoistSpillInsideBB(OldLI, *MI)) {
1089 // This COPY is now dead, the value is already in the stack slot.
1090 MI->getOperand(0).setIsDead();
1091 DeadDefs.push_back(MI);
1092 continue;
1093 }
1094 } else {
1095 // This is a reload for a sib-reg copy. Drop spills downstream.
1096 LiveInterval &SibLI = LIS.getInterval(SibReg);
1097 eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx));
1098 // The COPY will fold to a reload below.
1099 }
1100 }
1101
1102 // Attempt to fold memory ops.
1103 if (foldMemoryOperand(Ops))
1104 continue;
1105
1106 // Create a new virtual register for spill/fill.
1107 // FIXME: Infer regclass from instruction alone.
1108 Register NewVReg = Edit->createFrom(Reg);
1109
1110 if (RI.Reads)
1111 insertReload(NewVReg, Idx, MI);
1112
1113 // Rewrite instruction operands.
1114 bool hasLiveDef = false;
1115 for (const auto &OpPair : Ops) {
1116 MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
1117 MO.setReg(NewVReg);
1118 if (MO.isUse()) {
1119 if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
1120 MO.setIsKill();
1121 } else {
1122 if (!MO.isDead())
1123 hasLiveDef = true;
1124 }
1125 }
1126 LLVM_DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\trewrite: " << Idx <<
'\t' << *MI << '\n'; } } while (false);
1127
1128 // FIXME: Use a second vreg if instruction has no tied ops.
1129 if (RI.Writes)
1130 if (hasLiveDef)
1131 insertSpill(NewVReg, true, MI);
1132 }
1133}
1134
1135/// spillAll - Spill all registers remaining after rematerialization.
1136void InlineSpiller::spillAll() {
1137 // Update LiveStacks now that we are committed to spilling.
1138 if (StackSlot == VirtRegMap::NO_STACK_SLOT) {
1139 StackSlot = VRM.assignVirt2StackSlot(Original);
1140 StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original));
1141 StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator());
1142 } else
1143 StackInt = &LSS.getInterval(StackSlot);
1144
1145 if (Original != Edit->getReg())
1146 VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);
1147
1148 assert(StackInt->getNumValNums() == 1 && "Bad stack interval values")(static_cast <bool> (StackInt->getNumValNums() == 1 &&
"Bad stack interval values") ? void (0) : __assert_fail ("StackInt->getNumValNums() == 1 && \"Bad stack interval values\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1148, __extension__ __PRETTY_FUNCTION__));
1149 for (Register Reg : RegsToSpill)
1150 StackInt->MergeSegmentsInAsValue(LIS.getInterval(Reg),
1151 StackInt->getValNumInfo(0));
1152 LLVM_DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Merged spilled regs: " <<
*StackInt << '\n'; } } while (false);
1153
1154 // Spill around uses of all RegsToSpill.
1155 for (Register Reg : RegsToSpill)
1156 spillAroundUses(Reg);
1157
1158 // Hoisted spills may cause dead code.
1159 if (!DeadDefs.empty()) {
1160 LLVM_DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Eliminating " << DeadDefs
.size() << " dead defs\n"; } } while (false);
1161 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
1162 }
1163
1164 // Finally delete the SnippetCopies.
1165 for (Register Reg : RegsToSpill) {
1166 for (MachineRegisterInfo::reg_instr_iterator
1167 RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end();
1168 RI != E; ) {
1169 MachineInstr &MI = *(RI++);
1170 assert(SnippetCopies.count(&MI) && "Remaining use wasn't a snippet copy")(static_cast <bool> (SnippetCopies.count(&MI) &&
"Remaining use wasn't a snippet copy") ? void (0) : __assert_fail
("SnippetCopies.count(&MI) && \"Remaining use wasn't a snippet copy\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1170, __extension__ __PRETTY_FUNCTION__));
1171 // FIXME: Do this with a LiveRangeEdit callback.
1172 LIS.RemoveMachineInstrFromMaps(MI);
1173 MI.eraseFromParent();
1174 }
1175 }
1176
1177 // Delete all spilled registers.
1178 for (Register Reg : RegsToSpill)
1179 Edit->eraseVirtReg(Reg);
1180}
1181
1182void InlineSpiller::spill(LiveRangeEdit &edit) {
1183 ++NumSpilledRanges;
1184 Edit = &edit;
1185 assert(!Register::isStackSlot(edit.getReg()) &&(static_cast <bool> (!Register::isStackSlot(edit.getReg
()) && "Trying to spill a stack slot.") ? void (0) : __assert_fail
("!Register::isStackSlot(edit.getReg()) && \"Trying to spill a stack slot.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1186, __extension__ __PRETTY_FUNCTION__))
1186 "Trying to spill a stack slot.")(static_cast <bool> (!Register::isStackSlot(edit.getReg
()) && "Trying to spill a stack slot.") ? void (0) : __assert_fail
("!Register::isStackSlot(edit.getReg()) && \"Trying to spill a stack slot.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1186, __extension__ __PRETTY_FUNCTION__));
1187 // Share a stack slot among all descendants of Original.
1188 Original = VRM.getOriginal(edit.getReg());
1189 StackSlot = VRM.getStackSlot(Original);
1190 StackInt = nullptr;
1191
1192 LLVM_DEBUG(dbgs() << "Inline spilling "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Inline spilling " << TRI
.getRegClassName(MRI.getRegClass(edit.getReg())) << ':'
<< edit.getParent() << "\nFrom original " <<
printReg(Original) << '\n'; } } while (false)
1193 << TRI.getRegClassName(MRI.getRegClass(edit.getReg()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Inline spilling " << TRI
.getRegClassName(MRI.getRegClass(edit.getReg())) << ':'
<< edit.getParent() << "\nFrom original " <<
printReg(Original) << '\n'; } } while (false)
1194 << ':' << edit.getParent() << "\nFrom original "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Inline spilling " << TRI
.getRegClassName(MRI.getRegClass(edit.getReg())) << ':'
<< edit.getParent() << "\nFrom original " <<
printReg(Original) << '\n'; } } while (false)
1195 << printReg(Original) << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Inline spilling " << TRI
.getRegClassName(MRI.getRegClass(edit.getReg())) << ':'
<< edit.getParent() << "\nFrom original " <<
printReg(Original) << '\n'; } } while (false);
1196 assert(edit.getParent().isSpillable() &&(static_cast <bool> (edit.getParent().isSpillable() &&
"Attempting to spill already spilled value.") ? void (0) : __assert_fail
("edit.getParent().isSpillable() && \"Attempting to spill already spilled value.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1197, __extension__ __PRETTY_FUNCTION__))
1197 "Attempting to spill already spilled value.")(static_cast <bool> (edit.getParent().isSpillable() &&
"Attempting to spill already spilled value.") ? void (0) : __assert_fail
("edit.getParent().isSpillable() && \"Attempting to spill already spilled value.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1197, __extension__ __PRETTY_FUNCTION__));
1198 assert(DeadDefs.empty() && "Previous spill didn't remove dead defs")(static_cast <bool> (DeadDefs.empty() && "Previous spill didn't remove dead defs"
) ? void (0) : __assert_fail ("DeadDefs.empty() && \"Previous spill didn't remove dead defs\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1198, __extension__ __PRETTY_FUNCTION__));
1199
1200 collectRegsToSpill();
1201 reMaterializeAll();
1202
1203 // Remat may handle everything.
1204 if (!RegsToSpill.empty())
1205 spillAll();
1206
1207 Edit->calculateRegClassAndHint(MF, VRAI);
1208}
1209
1210/// Optimizations after all the reg selections and spills are done.
1211void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); }
1
Calling 'HoistSpillHelper::hoistAllSpills'
→
1212
1213/// When a spill is inserted, add the spill to MergeableSpills map.
1214void HoistSpillHelper::addToMergeableSpills(MachineInstr &Spill, int StackSlot,
1215 unsigned Original) {
1216 BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
1217 LiveInterval &OrigLI = LIS.getInterval(Original);
1218 // save a copy of LiveInterval in StackSlotToOrigLI because the original
1219 // LiveInterval may be cleared after all its references are spilled.
1220 if (StackSlotToOrigLI.find(StackSlot) == StackSlotToOrigLI.end()) {
1221 auto LI = std::make_unique<LiveInterval>(OrigLI.reg(), OrigLI.weight());
1222 LI->assign(OrigLI, Allocator);
1223 StackSlotToOrigLI[StackSlot] = std::move(LI);
1224 }
1225 SlotIndex Idx = LIS.getInstructionIndex(Spill);
1226 VNInfo *OrigVNI = StackSlotToOrigLI[StackSlot]->getVNInfoAt(Idx.getRegSlot());
1227 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1228 MergeableSpills[MIdx].insert(&Spill);
1229}
1230
1231/// When a spill is removed, remove the spill from MergeableSpills map.
1232/// Return true if the spill is removed successfully.
1233bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr &Spill,
1234 int StackSlot) {
1235 auto It = StackSlotToOrigLI.find(StackSlot);
1236 if (It == StackSlotToOrigLI.end())
1237 return false;
1238 SlotIndex Idx = LIS.getInstructionIndex(Spill);
1239 VNInfo *OrigVNI = It->second->getVNInfoAt(Idx.getRegSlot());
1240 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
1241 return MergeableSpills[MIdx].erase(&Spill);
1242}
1243
1244/// Check BB to see if it is a possible target BB to place a hoisted spill,
1245/// i.e., there should be a living sibling of OrigReg at the insert point.
1246bool HoistSpillHelper::isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
1247 MachineBasicBlock &BB, Register &LiveReg) {
1248 SlotIndex Idx = IPA.getLastInsertPoint(OrigLI, BB);
1249 // The original def could be after the last insert point in the root block,
1250 // we can't hoist to here.
1251 if (Idx < OrigVNI.def) {
1252 // TODO: We could be better here. If LI is not alive in landing pad
1253 // we could hoist spill after LIP.
1254 LLVM_DEBUG(dbgs() << "can't spill in root block - def after LIP\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "can't spill in root block - def after LIP\n"
; } } while (false);
1255 return false;
1256 }
1257 Register OrigReg = OrigLI.reg();
1258 SmallSetVector<Register, 16> &Siblings = Virt2SiblingsMap[OrigReg];
1259 assert(OrigLI.getVNInfoAt(Idx) == &OrigVNI && "Unexpected VNI")(static_cast <bool> (OrigLI.getVNInfoAt(Idx) == &OrigVNI
&& "Unexpected VNI") ? void (0) : __assert_fail ("OrigLI.getVNInfoAt(Idx) == &OrigVNI && \"Unexpected VNI\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1259, __extension__ __PRETTY_FUNCTION__));
1260
1261 for (const Register &SibReg : Siblings) {
1262 LiveInterval &LI = LIS.getInterval(SibReg);
1263 VNInfo *VNI = LI.getVNInfoAt(Idx);
1264 if (VNI) {
1265 LiveReg = SibReg;
1266 return true;
1267 }
1268 }
1269 return false;
1270}
1271
1272/// Remove redundant spills in the same BB. Save those redundant spills in
1273/// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map.
1274void HoistSpillHelper::rmRedundantSpills(
1275 SmallPtrSet<MachineInstr *, 16> &Spills,
1276 SmallVectorImpl<MachineInstr *> &SpillsToRm,
1277 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
1278 // For each spill saw, check SpillBBToSpill[] and see if its BB already has
1279 // another spill inside. If a BB contains more than one spill, only keep the
1280 // earlier spill with smaller SlotIndex.
1281 for (const auto CurrentSpill : Spills) {
1282 MachineBasicBlock *Block = CurrentSpill->getParent();
1283 MachineDomTreeNode *Node = MDT.getBase().getNode(Block);
1284 MachineInstr *PrevSpill = SpillBBToSpill[Node];
1285 if (PrevSpill) {
1286 SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill);
1287 SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill);
1288 MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;
1289 MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;
1290 SpillsToRm.push_back(SpillToRm);
1291 SpillBBToSpill[MDT.getBase().getNode(Block)] = SpillToKeep;
1292 } else {
1293 SpillBBToSpill[MDT.getBase().getNode(Block)] = CurrentSpill;
1294 }
1295 }
1296 for (const auto SpillToRm : SpillsToRm)
1297 Spills.erase(SpillToRm);
1298}
1299
1300/// Starting from \p Root find a top-down traversal order of the dominator
1301/// tree to visit all basic blocks containing the elements of \p Spills.
1302/// Redundant spills will be found and put into \p SpillsToRm at the same
1303/// time. \p SpillBBToSpill will be populated as part of the process and
1304/// maps a basic block to the first store occurring in the basic block.
1305/// \post SpillsToRm.union(Spills\@post) == Spills\@pre
1306void HoistSpillHelper::getVisitOrders(
1307 MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
1308 SmallVectorImpl<MachineDomTreeNode *> &Orders,
1309 SmallVectorImpl<MachineInstr *> &SpillsToRm,
1310 DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep,
1311 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
1312 // The set contains all the possible BB nodes to which we may hoist
1313 // original spills.
1314 SmallPtrSet<MachineDomTreeNode *, 8> WorkSet;
1315 // Save the BB nodes on the path from the first BB node containing
1316 // non-redundant spill to the Root node.
1317 SmallPtrSet<MachineDomTreeNode *, 8> NodesOnPath;
1318 // All the spills to be hoisted must originate from a single def instruction
1319 // to the OrigReg. It means the def instruction should dominate all the spills
1320 // to be hoisted. We choose the BB where the def instruction is located as
1321 // the Root.
1322 MachineDomTreeNode *RootIDomNode = MDT[Root]->getIDom();
1323 // For every node on the dominator tree with spill, walk up on the dominator
1324 // tree towards the Root node until it is reached. If there is other node
1325 // containing spill in the middle of the path, the previous spill saw will
1326 // be redundant and the node containing it will be removed. All the nodes on
1327 // the path starting from the first node with non-redundant spill to the Root
1328 // node will be added to the WorkSet, which will contain all the possible
1329 // locations where spills may be hoisted to after the loop below is done.
1330 for (const auto Spill : Spills) {
1331 MachineBasicBlock *Block = Spill->getParent();
1332 MachineDomTreeNode *Node = MDT[Block];
9
←
Calling 'MachineDominatorTree::operator[]'
→
27
←
Returning from 'MachineDominatorTree::operator[]'
→
28
←
'Node' initialized here
→
1333 MachineInstr *SpillToRm = nullptr;
1334 while (Node != RootIDomNode) {
29
←
Assuming 'Node' is not equal to 'RootIDomNode'
→
1335 // If Node dominates Block, and it already contains a spill, the spill in
1336 // Block will be redundant.
1337 if (Node != MDT[Block] && SpillBBToSpill[Node]) {
30
←
Assuming the condition is false
→
31
←
Assuming pointer value is null
→
1338 SpillToRm = SpillBBToSpill[MDT[Block]];
1339 break;
1340 /// If we see the Node already in WorkSet, the path from the Node to
1341 /// the Root node must already be traversed by another spill.
1342 /// Then no need to repeat.
1343 } else if (WorkSet.count(Node)) {
32
←
Assuming the condition is false
→
33
←
Taking false branch
→
1344 break;
1345 } else {
1346 NodesOnPath.insert(Node);
1347 }
1348 Node = Node->getIDom();
34
←
Called C++ object pointer is null
1349 }
1350 if (SpillToRm) {
1351 SpillsToRm.push_back(SpillToRm);
1352 } else {
1353 // Add a BB containing the original spills to SpillsToKeep -- i.e.,
1354 // set the initial status before hoisting start. The value of BBs
1355 // containing original spills is set to 0, in order to descriminate
1356 // with BBs containing hoisted spills which will be inserted to
1357 // SpillsToKeep later during hoisting.
1358 SpillsToKeep[MDT[Block]] = 0;
1359 WorkSet.insert(NodesOnPath.begin(), NodesOnPath.end());
1360 }
1361 NodesOnPath.clear();
1362 }
1363
1364 // Sort the nodes in WorkSet in top-down order and save the nodes
1365 // in Orders. Orders will be used for hoisting in runHoistSpills.
1366 unsigned idx = 0;
1367 Orders.push_back(MDT.getBase().getNode(Root));
1368 do {
1369 MachineDomTreeNode *Node = Orders[idx++];
1370 for (MachineDomTreeNode *Child : Node->children()) {
1371 if (WorkSet.count(Child))
1372 Orders.push_back(Child);
1373 }
1374 } while (idx != Orders.size());
1375 assert(Orders.size() == WorkSet.size() &&(static_cast <bool> (Orders.size() == WorkSet.size() &&
"Orders have different size with WorkSet") ? void (0) : __assert_fail
("Orders.size() == WorkSet.size() && \"Orders have different size with WorkSet\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1376, __extension__ __PRETTY_FUNCTION__))
1376 "Orders have different size with WorkSet")(static_cast <bool> (Orders.size() == WorkSet.size() &&
"Orders have different size with WorkSet") ? void (0) : __assert_fail
("Orders.size() == WorkSet.size() && \"Orders have different size with WorkSet\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1376, __extension__ __PRETTY_FUNCTION__));
1377
1378#ifndef NDEBUG
1379 LLVM_DEBUG(dbgs() << "Orders size is " << Orders.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Orders size is " << Orders
.size() << "\n"; } } while (false);
1380 SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();
1381 for (; RIt != Orders.rend(); RIt++)
1382 LLVM_DEBUG(dbgs() << "BB" << (*RIt)->getBlock()->getNumber() << ",")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "BB" << (*RIt)->getBlock
()->getNumber() << ","; } } while (false);
1383 LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\n"; } } while (false);
1384#endif
1385}
1386
1387/// Try to hoist spills according to BB hotness. The spills to removed will
1388/// be saved in \p SpillsToRm. The spills to be inserted will be saved in
1389/// \p SpillsToIns.
1390void HoistSpillHelper::runHoistSpills(
1391 LiveInterval &OrigLI, VNInfo &OrigVNI,
1392 SmallPtrSet<MachineInstr *, 16> &Spills,
1393 SmallVectorImpl<MachineInstr *> &SpillsToRm,
1394 DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns) {
1395 // Visit order of dominator tree nodes.
1396 SmallVector<MachineDomTreeNode *, 32> Orders;
1397 // SpillsToKeep contains all the nodes where spills are to be inserted
1398 // during hoisting. If the spill to be inserted is an original spill
1399 // (not a hoisted one), the value of the map entry is 0. If the spill
1400 // is a hoisted spill, the value of the map entry is the VReg to be used
1401 // as the source of the spill.
1402 DenseMap<MachineDomTreeNode *, unsigned> SpillsToKeep;
1403 // Map from BB to the first spill inside of it.
1404 DenseMap<MachineDomTreeNode *, MachineInstr *> SpillBBToSpill;
1405
1406 rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill);
1407
1408 MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI.def);
1409 getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep,
8
←
Calling 'HoistSpillHelper::getVisitOrders'
→
1410 SpillBBToSpill);
1411
1412 // SpillsInSubTreeMap keeps the map from a dom tree node to a pair of
1413 // nodes set and the cost of all the spills inside those nodes.
1414 // The nodes set are the locations where spills are to be inserted
1415 // in the subtree of current node.
1416 using NodesCostPair =
1417 std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency>;
1418 DenseMap<MachineDomTreeNode *, NodesCostPair> SpillsInSubTreeMap;
1419
1420 // Iterate Orders set in reverse order, which will be a bottom-up order
1421 // in the dominator tree. Once we visit a dom tree node, we know its
1422 // children have already been visited and the spill locations in the
1423 // subtrees of all the children have been determined.
1424 SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();
1425 for (; RIt != Orders.rend(); RIt++) {
1426 MachineBasicBlock *Block = (*RIt)->getBlock();
1427
1428 // If Block contains an original spill, simply continue.
1429 if (SpillsToKeep.find(*RIt) != SpillsToKeep.end() && !SpillsToKeep[*RIt]) {
1430 SpillsInSubTreeMap[*RIt].first.insert(*RIt);
1431 // SpillsInSubTreeMap[*RIt].second contains the cost of spill.
1432 SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block);
1433 continue;
1434 }
1435
1436 // Collect spills in subtree of current node (*RIt) to
1437 // SpillsInSubTreeMap[*RIt].first.
1438 for (MachineDomTreeNode *Child : (*RIt)->children()) {
1439 if (SpillsInSubTreeMap.find(Child) == SpillsInSubTreeMap.end())
1440 continue;
1441 // The stmt "SpillsInSubTree = SpillsInSubTreeMap[*RIt].first" below
1442 // should be placed before getting the begin and end iterators of
1443 // SpillsInSubTreeMap[Child].first, or else the iterators may be
1444 // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time
1445 // and the map grows and then the original buckets in the map are moved.
1446 SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
1447 SpillsInSubTreeMap[*RIt].first;
1448 BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
1449 SubTreeCost += SpillsInSubTreeMap[Child].second;
1450 auto BI = SpillsInSubTreeMap[Child].first.begin();
1451 auto EI = SpillsInSubTreeMap[Child].first.end();
1452 SpillsInSubTree.insert(BI, EI);
1453 SpillsInSubTreeMap.erase(Child);
1454 }
1455
1456 SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
1457 SpillsInSubTreeMap[*RIt].first;
1458 BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
1459 // No spills in subtree, simply continue.
1460 if (SpillsInSubTree.empty())
1461 continue;
1462
1463 // Check whether Block is a possible candidate to insert spill.
1464 Register LiveReg;
1465 if (!isSpillCandBB(OrigLI, OrigVNI, *Block, LiveReg))
1466 continue;
1467
1468 // If there are multiple spills that could be merged, bias a little
1469 // to hoist the spill.
1470 BranchProbability MarginProb = (SpillsInSubTree.size() > 1)
1471 ? BranchProbability(9, 10)
1472 : BranchProbability(1, 1);
1473 if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) {
1474 // Hoist: Move spills to current Block.
1475 for (const auto SpillBB : SpillsInSubTree) {
1476 // When SpillBB is a BB contains original spill, insert the spill
1477 // to SpillsToRm.
1478 if (SpillsToKeep.find(SpillBB) != SpillsToKeep.end() &&
1479 !SpillsToKeep[SpillBB]) {
1480 MachineInstr *SpillToRm = SpillBBToSpill[SpillBB];
1481 SpillsToRm.push_back(SpillToRm);
1482 }
1483 // SpillBB will not contain spill anymore, remove it from SpillsToKeep.
1484 SpillsToKeep.erase(SpillBB);
1485 }
1486 // Current Block is the BB containing the new hoisted spill. Add it to
1487 // SpillsToKeep. LiveReg is the source of the new spill.
1488 SpillsToKeep[*RIt] = LiveReg;
1489 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "spills in BB: "; for (const
auto Rspill : SpillsInSubTree) dbgs() << Rspill->getBlock
()->getNumber() << " "; dbgs() << "were promoted to BB"
<< (*RIt)->getBlock()->getNumber() << "\n"
; }; } } while (false)
1490 dbgs() << "spills in BB: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "spills in BB: "; for (const
auto Rspill : SpillsInSubTree) dbgs() << Rspill->getBlock
()->getNumber() << " "; dbgs() << "were promoted to BB"
<< (*RIt)->getBlock()->getNumber() << "\n"
; }; } } while (false)
1491 for (const auto Rspill : SpillsInSubTree)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "spills in BB: "; for (const
auto Rspill : SpillsInSubTree) dbgs() << Rspill->getBlock
()->getNumber() << " "; dbgs() << "were promoted to BB"
<< (*RIt)->getBlock()->getNumber() << "\n"
; }; } } while (false)
1492 dbgs() << Rspill->getBlock()->getNumber() << " ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "spills in BB: "; for (const
auto Rspill : SpillsInSubTree) dbgs() << Rspill->getBlock
()->getNumber() << " "; dbgs() << "were promoted to BB"
<< (*RIt)->getBlock()->getNumber() << "\n"
; }; } } while (false)
1493 dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "spills in BB: "; for (const
auto Rspill : SpillsInSubTree) dbgs() << Rspill->getBlock
()->getNumber() << " "; dbgs() << "were promoted to BB"
<< (*RIt)->getBlock()->getNumber() << "\n"
; }; } } while (false)
1494 << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "spills in BB: "; for (const
auto Rspill : SpillsInSubTree) dbgs() << Rspill->getBlock
()->getNumber() << " "; dbgs() << "were promoted to BB"
<< (*RIt)->getBlock()->getNumber() << "\n"
; }; } } while (false)
1495 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "spills in BB: "; for (const
auto Rspill : SpillsInSubTree) dbgs() << Rspill->getBlock
()->getNumber() << " "; dbgs() << "were promoted to BB"
<< (*RIt)->getBlock()->getNumber() << "\n"
; }; } } while (false);
1496 SpillsInSubTree.clear();
1497 SpillsInSubTree.insert(*RIt);
1498 SubTreeCost = MBFI.getBlockFreq(Block);
1499 }
1500 }
1501 // For spills in SpillsToKeep with LiveReg set (i.e., not original spill),
1502 // save them to SpillsToIns.
1503 for (const auto &Ent : SpillsToKeep) {
1504 if (Ent.second)
1505 SpillsToIns[Ent.first->getBlock()] = Ent.second;
1506 }
1507}
1508
1509/// For spills with equal values, remove redundant spills and hoist those left
1510/// to less hot spots.
1511///
1512/// Spills with equal values will be collected into the same set in
1513/// MergeableSpills when spill is inserted. These equal spills are originated
1514/// from the same defining instruction and are dominated by the instruction.
1515/// Before hoisting all the equal spills, redundant spills inside in the same
1516/// BB are first marked to be deleted. Then starting from the spills left, walk
1517/// up on the dominator tree towards the Root node where the define instruction
1518/// is located, mark the dominated spills to be deleted along the way and
1519/// collect the BB nodes on the path from non-dominated spills to the define
1520/// instruction into a WorkSet. The nodes in WorkSet are the candidate places
1521/// where we are considering to hoist the spills. We iterate the WorkSet in
1522/// bottom-up order, and for each node, we will decide whether to hoist spills
1523/// inside its subtree to that node. In this way, we can get benefit locally
1524/// even if hoisting all the equal spills to one cold place is impossible.
1525void HoistSpillHelper::hoistAllSpills() {
1526 SmallVector<Register, 4> NewVRegs;
1527 LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this);
1528
1529 for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
2
←
Assuming 'i' is equal to 'e'
→
3
←
Loop condition is false. Execution continues on line 1537
→
1530 Register Reg = Register::index2VirtReg(i);
1531 Register Original = VRM.getPreSplitReg(Reg);
1532 if (!MRI.def_empty(Reg))
1533 Virt2SiblingsMap[Original].insert(Reg);
1534 }
1535
1536 // Each entry in MergeableSpills contains a spill set with equal values.
1537 for (auto &Ent : MergeableSpills) {
1538 int Slot = Ent.first.first;
1539 LiveInterval &OrigLI = *StackSlotToOrigLI[Slot];
1540 VNInfo *OrigVNI = Ent.first.second;
1541 SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;
1542 if (Ent.second.empty())
1543 continue;
1544
1545 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\nFor Slot" << Slot <<
" and VN" << OrigVNI->id << ":\n" << "Equal spills in BB: "
; for (const auto spill : EqValSpills) dbgs() << spill->
getParent()->getNumber() << " "; dbgs() << "\n"
; }; } } while (false)
4
←
Taking false branch
→
5
←
Assuming 'DebugFlag' is false
→
6
←
Loop condition is false. Exiting loop
→
1546 dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\nFor Slot" << Slot <<
" and VN" << OrigVNI->id << ":\n" << "Equal spills in BB: "
; for (const auto spill : EqValSpills) dbgs() << spill->
getParent()->getNumber() << " "; dbgs() << "\n"
; }; } } while (false)
1547 << "Equal spills in BB: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\nFor Slot" << Slot <<
" and VN" << OrigVNI->id << ":\n" << "Equal spills in BB: "
; for (const auto spill : EqValSpills) dbgs() << spill->
getParent()->getNumber() << " "; dbgs() << "\n"
; }; } } while (false)
1548 for (const auto spill : EqValSpills)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\nFor Slot" << Slot <<
" and VN" << OrigVNI->id << ":\n" << "Equal spills in BB: "
; for (const auto spill : EqValSpills) dbgs() << spill->
getParent()->getNumber() << " "; dbgs() << "\n"
; }; } } while (false)
1549 dbgs() << spill->getParent()->getNumber() << " ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\nFor Slot" << Slot <<
" and VN" << OrigVNI->id << ":\n" << "Equal spills in BB: "
; for (const auto spill : EqValSpills) dbgs() << spill->
getParent()->getNumber() << " "; dbgs() << "\n"
; }; } } while (false)
1550 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\nFor Slot" << Slot <<
" and VN" << OrigVNI->id << ":\n" << "Equal spills in BB: "
; for (const auto spill : EqValSpills) dbgs() << spill->
getParent()->getNumber() << " "; dbgs() << "\n"
; }; } } while (false)
1551 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\nFor Slot" << Slot <<
" and VN" << OrigVNI->id << ":\n" << "Equal spills in BB: "
; for (const auto spill : EqValSpills) dbgs() << spill->
getParent()->getNumber() << " "; dbgs() << "\n"
; }; } } while (false);
1552
1553 // SpillsToRm is the spill set to be removed from EqValSpills.
1554 SmallVector<MachineInstr *, 16> SpillsToRm;
1555 // SpillsToIns is the spill set to be newly inserted after hoisting.
1556 DenseMap<MachineBasicBlock *, unsigned> SpillsToIns;
1557
1558 runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
7
←
Calling 'HoistSpillHelper::runHoistSpills'
→
1559
1560 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "Finally inserted spills in BB: "
; for (const auto &Ispill : SpillsToIns) dbgs() << Ispill
.first->getNumber() << " "; dbgs() << "\nFinally removed spills in BB: "
; for (const auto Rspill : SpillsToRm) dbgs() << Rspill
->getParent()->getNumber() << " "; dbgs() <<
"\n"; }; } } while (false)
1561 dbgs() << "Finally inserted spills in BB: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "Finally inserted spills in BB: "
; for (const auto &Ispill : SpillsToIns) dbgs() << Ispill
.first->getNumber() << " "; dbgs() << "\nFinally removed spills in BB: "
; for (const auto Rspill : SpillsToRm) dbgs() << Rspill
->getParent()->getNumber() << " "; dbgs() <<
"\n"; }; } } while (false)
1562 for (const auto &Ispill : SpillsToIns)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "Finally inserted spills in BB: "
; for (const auto &Ispill : SpillsToIns) dbgs() << Ispill
.first->getNumber() << " "; dbgs() << "\nFinally removed spills in BB: "
; for (const auto Rspill : SpillsToRm) dbgs() << Rspill
->getParent()->getNumber() << " "; dbgs() <<
"\n"; }; } } while (false)
1563 dbgs() << Ispill.first->getNumber() << " ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "Finally inserted spills in BB: "
; for (const auto &Ispill : SpillsToIns) dbgs() << Ispill
.first->getNumber() << " "; dbgs() << "\nFinally removed spills in BB: "
; for (const auto Rspill : SpillsToRm) dbgs() << Rspill
->getParent()->getNumber() << " "; dbgs() <<
"\n"; }; } } while (false)
1564 dbgs() << "\nFinally removed spills in BB: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "Finally inserted spills in BB: "
; for (const auto &Ispill : SpillsToIns) dbgs() << Ispill
.first->getNumber() << " "; dbgs() << "\nFinally removed spills in BB: "
; for (const auto Rspill : SpillsToRm) dbgs() << Rspill
->getParent()->getNumber() << " "; dbgs() <<
"\n"; }; } } while (false)
1565 for (const auto Rspill : SpillsToRm)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "Finally inserted spills in BB: "
; for (const auto &Ispill : SpillsToIns) dbgs() << Ispill
.first->getNumber() << " "; dbgs() << "\nFinally removed spills in BB: "
; for (const auto Rspill : SpillsToRm) dbgs() << Rspill
->getParent()->getNumber() << " "; dbgs() <<
"\n"; }; } } while (false)
1566 dbgs() << Rspill->getParent()->getNumber() << " ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "Finally inserted spills in BB: "
; for (const auto &Ispill : SpillsToIns) dbgs() << Ispill
.first->getNumber() << " "; dbgs() << "\nFinally removed spills in BB: "
; for (const auto Rspill : SpillsToRm) dbgs() << Rspill
->getParent()->getNumber() << " "; dbgs() <<
"\n"; }; } } while (false)
1567 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "Finally inserted spills in BB: "
; for (const auto &Ispill : SpillsToIns) dbgs() << Ispill
.first->getNumber() << " "; dbgs() << "\nFinally removed spills in BB: "
; for (const auto Rspill : SpillsToRm) dbgs() << Rspill
->getParent()->getNumber() << " "; dbgs() <<
"\n"; }; } } while (false)
1568 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "Finally inserted spills in BB: "
; for (const auto &Ispill : SpillsToIns) dbgs() << Ispill
.first->getNumber() << " "; dbgs() << "\nFinally removed spills in BB: "
; for (const auto Rspill : SpillsToRm) dbgs() << Rspill
->getParent()->getNumber() << " "; dbgs() <<
"\n"; }; } } while (false);
1569
1570 // Stack live range update.
1571 LiveInterval &StackIntvl = LSS.getInterval(Slot);
1572 if (!SpillsToIns.empty() || !SpillsToRm.empty())
1573 StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI,
1574 StackIntvl.getValNumInfo(0));
1575
1576 // Insert hoisted spills.
1577 for (auto const &Insert : SpillsToIns) {
1578 MachineBasicBlock *BB = Insert.first;
1579 Register LiveReg = Insert.second;
1580 MachineBasicBlock::iterator MII = IPA.getLastInsertPointIter(OrigLI, *BB);
1581 MachineInstrSpan MIS(MII, BB);
1582 TII.storeRegToStackSlot(*BB, MII, LiveReg, false, Slot,
1583 MRI.getRegClass(LiveReg), &TRI);
1584 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MII);
1585 for (const MachineInstr &MI : make_range(MIS.begin(), MII))
1586 getVDefInterval(MI, LIS);
1587 ++NumSpills;
1588 }
1589
1590 // Remove redundant spills or change them to dead instructions.
1591 NumSpills -= SpillsToRm.size();
1592 for (auto const RMEnt : SpillsToRm) {
1593 RMEnt->setDesc(TII.get(TargetOpcode::KILL));
1594 for (unsigned i = RMEnt->getNumOperands(); i; --i) {
1595 MachineOperand &MO = RMEnt->getOperand(i - 1);
1596 if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead())
1597 RMEnt->RemoveOperand(i - 1);
1598 }
1599 }
1600 Edit.eliminateDeadDefs(SpillsToRm, None, AA);
1601 }
1602}
1603
1604/// For VirtReg clone, the \p New register should have the same physreg or
1605/// stackslot as the \p old register.
1606void HoistSpillHelper::LRE_DidCloneVirtReg(Register New, Register Old) {
1607 if (VRM.hasPhys(Old))
1608 VRM.assignVirt2Phys(New, VRM.getPhys(Old));
1609 else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT)
1610 VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
1611 else
1612 llvm_unreachable("VReg should be assigned either physreg or stackslot")::llvm::llvm_unreachable_internal("VReg should be assigned either physreg or stackslot"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/CodeGen/InlineSpiller.cpp"
, 1612);
1613 if (VRM.hasShape(Old))
1614 VRM.assignVirt2Shape(New, VRM.getShape(Old));
1615}
←

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/MachineDominators.h

→
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
27namespace llvm {
28
29template <>
30inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot(
31 MachineBasicBlock *MBB) {
32 this->Roots.push_back(MBB);
33}
34
35extern template class DomTreeNodeBase<MachineBasicBlock>;
36extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree
37extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree
38
39using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>;
40
41//===-------------------------------------
42/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
43/// compute a normal dominator tree.
44///
45class 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
79public:
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 void getDescendants(MachineBasicBlock *A,
116 SmallVectorImpl<MachineBasicBlock *> &Result) {
117 applySplitCriticalEdges();
118 DT->getDescendants(A, Result);
119 }
120
121 bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const {
122 applySplitCriticalEdges();
123 return DT->dominates(A, B);
124 }
125
126 // dominates - Return true if A dominates B. This performs the
127 // special checks necessary if A and B are in the same basic block.
128 bool dominates(const MachineInstr *A, const MachineInstr *B) const {
129 applySplitCriticalEdges();
130 const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
131 if (BBA != BBB) return DT->dominates(BBA, BBB);
132
133 // Loop through the basic block until we find A or B.
134 MachineBasicBlock::const_iterator I = BBA->begin();
135 for (; &*I != A && &*I != B; ++I)
136 /*empty*/ ;
137
138 return &*I == A;
139 }
140
141 bool properlyDominates(const MachineDomTreeNode *A,
142 const MachineDomTreeNode *B) const {
143 applySplitCriticalEdges();
144 return DT->properlyDominates(A, B);
145 }
146
147 bool properlyDominates(const MachineBasicBlock *A,
148 const MachineBasicBlock *B) const {
149 applySplitCriticalEdges();
150 return DT->properlyDominates(A, B);
151 }
152
153 /// findNearestCommonDominator - Find nearest common dominator basic block
154 /// for basic block A and B. If there is no such block then return NULL.
155 MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A,
156 MachineBasicBlock *B) {
157 applySplitCriticalEdges();
158 return DT->findNearestCommonDominator(A, B);
159 }
160
161 MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
162 applySplitCriticalEdges();
163 return DT->getNode(BB);
10
←
Calling 'DominatorTreeBase::getNode'
→
25
←
Returning from 'DominatorTreeBase::getNode'
→
26
←
Returning pointer
→
164 }
165
166 /// getNode - return the (Post)DominatorTree node for the specified basic
167 /// block. This is the same as using operator[] on this class.
168 ///
169 MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
170 applySplitCriticalEdges();
171 return DT->getNode(BB);
172 }
173
174 /// addNewBlock - Add a new node to the dominator tree information. This
175 /// creates a new node as a child of DomBB dominator node,linking it into
176 /// the children list of the immediate dominator.
177 MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB,
178 MachineBasicBlock *DomBB) {
179 applySplitCriticalEdges();
180 return DT->addNewBlock(BB, DomBB);
181 }
182
183 /// changeImmediateDominator - This method is used to update the dominator
184 /// tree information when a node's immediate dominator changes.
185 ///
186 void changeImmediateDominator(MachineBasicBlock *N,
187 MachineBasicBlock *NewIDom) {
188 applySplitCriticalEdges();
189 DT->changeImmediateDominator(N, NewIDom);
190 }
191
192 void changeImmediateDominator(MachineDomTreeNode *N,
193 MachineDomTreeNode *NewIDom) {
194 applySplitCriticalEdges();
195 DT->changeImmediateDominator(N, NewIDom);
196 }
197
198 /// eraseNode - Removes a node from the dominator tree. Block must not
199 /// dominate any other blocks. Removes node from its immediate dominator's
200 /// children list. Deletes dominator node associated with basic block BB.
201 void eraseNode(MachineBasicBlock *BB) {
202 applySplitCriticalEdges();
203 DT->eraseNode(BB);
204 }
205
206 /// splitBlock - BB is split and now it has one successor. Update dominator
207 /// tree to reflect this change.
208 void splitBlock(MachineBasicBlock* NewBB) {
209 applySplitCriticalEdges();
210 DT->splitBlock(NewBB);
211 }
212
213 /// isReachableFromEntry - Return true if A is dominated by the entry
214 /// block of the function containing it.
215 bool isReachableFromEntry(const MachineBasicBlock *A) {
216 applySplitCriticalEdges();
217 return DT->isReachableFromEntry(A);
218 }
219
220 void releaseMemory() override;
221
222 void verifyAnalysis() const override;
223
224 void print(raw_ostream &OS, const Module*) const override;
225
226 /// Record that the critical edge (FromBB, ToBB) has been
227 /// split with NewBB.
228 /// This is best to use this method instead of directly update the
229 /// underlying information, because this helps mitigating the
230 /// number of time the DT information is invalidated.
231 ///
232 /// \note Do not use this method with regular edges.
233 ///
234 /// \note To benefit from the compile time improvement incurred by this
235 /// method, the users of this method have to limit the queries to the DT
236 /// interface between two edges splitting. In other words, they have to
237 /// pack the splitting of critical edges as much as possible.
238 void recordSplitCriticalEdge(MachineBasicBlock *FromBB,
239 MachineBasicBlock *ToBB,
240 MachineBasicBlock *NewBB) {
241 bool Inserted = NewBBs.insert(NewBB).second;
242 (void)Inserted;
243 assert(Inserted &&(static_cast <bool> (Inserted && "A basic block inserted via edge splitting cannot appear twice"
) ? void (0) : __assert_fail ("Inserted && \"A basic block inserted via edge splitting cannot appear twice\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/MachineDominators.h"
, 244, __extension__ __PRETTY_FUNCTION__))
244 "A basic block inserted via edge splitting cannot appear twice")(static_cast <bool> (Inserted && "A basic block inserted via edge splitting cannot appear twice"
) ? void (0) : __assert_fail ("Inserted && \"A basic block inserted via edge splitting cannot appear twice\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/CodeGen/MachineDominators.h"
, 244, __extension__ __PRETTY_FUNCTION__));
245 CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
246 }
247};
248
249//===-------------------------------------
250/// DominatorTree GraphTraits specialization so the DominatorTree can be
251/// iterable by generic graph iterators.
252///
253
254template <class Node, class ChildIterator>
255struct MachineDomTreeGraphTraitsBase {
256 using NodeRef = Node *;
257 using ChildIteratorType = ChildIterator;
258
259 static NodeRef getEntryNode(NodeRef N) { return N; }
260 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
261 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
262};
263
264template <class T> struct GraphTraits;
265
266template <>
267struct GraphTraits<MachineDomTreeNode *>
268 : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode,
269 MachineDomTreeNode::const_iterator> {
270};
271
272template <>
273struct GraphTraits<const MachineDomTreeNode *>
274 : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode,
275 MachineDomTreeNode::const_iterator> {
276};
277
278template <> struct GraphTraits<MachineDominatorTree*>
279 : public GraphTraits<MachineDomTreeNode *> {
280 static NodeRef getEntryNode(MachineDominatorTree *DT) {
281 return DT->getRootNode();
282 }
283};
284
285} // end namespace llvm
286
287#endif // LLVM_CODEGEN_MACHINEDOMINATORS_H
←

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.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
42namespace llvm {
43
44template <typename NodeT, bool IsPostDom>
45class DominatorTreeBase;
46
47namespace DomTreeBuilder {
48template <typename DomTreeT>
49struct SemiNCAInfo;
50} // namespace DomTreeBuilder
51
52/// Base class for the actual dominator tree node.
53template <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?")(static_cast <bool> (IDom && "No immediate dominator?"
) ? void (0) : __assert_fail ("IDom && \"No immediate dominator?\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 124, __extension__ __PRETTY_FUNCTION__));
125 if (IDom == NewIDom) return;
126
127 auto I = find(IDom->Children, this);
128 assert(I != IDom->Children.end() &&(static_cast <bool> (I != IDom->Children.end() &&
"Not in immediate dominator children set!") ? void (0) : __assert_fail
("I != IDom->Children.end() && \"Not in immediate dominator children set!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 129, __extension__ __PRETTY_FUNCTION__))
129 "Not in immediate dominator children set!")(static_cast <bool> (I != IDom->Children.end() &&
"Not in immediate dominator children set!") ? void (0) : __assert_fail
("I != IDom->Children.end() && \"Not in immediate dominator children set!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 129, __extension__ __PRETTY_FUNCTION__));
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
146private:
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)(static_cast <bool> (IDom) ? void (0) : __assert_fail (
"IDom", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 155, __extension__ __PRETTY_FUNCTION__));
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)(static_cast <bool> (C->IDom) ? void (0) : __assert_fail
("C->IDom", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 165, __extension__ __PRETTY_FUNCTION__));
166 if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
167 }
168 }
169 }
170};
171
172template <class NodeT>
173raw_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
185template <class NodeT>
186void 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
195namespace DomTreeBuilder {
196// The routines below are provided in a separate header but referenced here.
197template <typename DomTreeT>
198void Calculate(DomTreeT &DT);
199
200template <typename DomTreeT>
201void CalculateWithUpdates(DomTreeT &DT,
202 ArrayRef<typename DomTreeT::UpdateType> Updates);
203
204template <typename DomTreeT>
205void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
206 typename DomTreeT::NodePtr To);
207
208template <typename DomTreeT>
209void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
210 typename DomTreeT::NodePtr To);
211
212template <typename DomTreeT>
213void ApplyUpdates(DomTreeT &DT,
214 GraphDiff<typename DomTreeT::NodePtr,
215 DomTreeT::IsPostDominator> &PreViewCFG,
216 GraphDiff<typename DomTreeT::NodePtr,
217 DomTreeT::IsPostDominator> *PostViewCFG);
218
219template <typename DomTreeT>
220bool 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.
227template <typename NodeT, bool IsPostDom>
228class 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
247protected:
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())
11
←
Calling 'operator!='
→
22
←
Returning from 'operator!='
→
23
←
Taking true branch
→
354 return I->second.get();
24
←
Returning pointer
→
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() &&(static_cast <bool> (!this->isPostDominator() &&
"This is not implemented for post dominators") ? void (0) : __assert_fail
("!this->isPostDominator() && \"This is not implemented for post dominators\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 407, __extension__ __PRETTY_FUNCTION__))
407 "This is not implemented for post dominators")(static_cast <bool> (!this->isPostDominator() &&
"This is not implemented for post dominators") ? void (0) : __assert_fail
("!this->isPostDominator() && \"This is not implemented for post dominators\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 407, __extension__ __PRETTY_FUNCTION__));
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 ||(static_cast <bool> ((!DFSInfoValid || (dominatedBySlowTreeWalk
(A, B) == B->DominatedBy(A))) && "Tree walk disagrees with dfs numbers!"
) ? void (0) : __assert_fail ("(!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && \"Tree walk disagrees with dfs numbers!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 442, __extension__ __PRETTY_FUNCTION__))
441 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&(static_cast <bool> ((!DFSInfoValid || (dominatedBySlowTreeWalk
(A, B) == B->DominatedBy(A))) && "Tree walk disagrees with dfs numbers!"
) ? void (0) : __assert_fail ("(!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && \"Tree walk disagrees with dfs numbers!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 442, __extension__ __PRETTY_FUNCTION__))
442 "Tree walk disagrees with dfs numbers!")(static_cast <bool> ((!DFSInfoValid || (dominatedBySlowTreeWalk
(A, B) == B->DominatedBy(A))) && "Tree walk disagrees with dfs numbers!"
) ? void (0) : __assert_fail ("(!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && \"Tree walk disagrees with dfs numbers!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 442, __extension__ __PRETTY_FUNCTION__));
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!")(static_cast <bool> (this->Roots.size() == 1 &&
"Should always have entry node!") ? void (0) : __assert_fail
("this->Roots.size() == 1 && \"Should always have entry node!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 462, __extension__ __PRETTY_FUNCTION__));
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")(static_cast <bool> (A && B && "Pointers are not valid"
) ? void (0) : __assert_fail ("A && B && \"Pointers are not valid\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 469, __extension__ __PRETTY_FUNCTION__));
470 assert(A->getParent() == B->getParent() &&(static_cast <bool> (A->getParent() == B->getParent
() && "Two blocks are not in same function") ? void (
0) : __assert_fail ("A->getParent() == B->getParent() && \"Two blocks are not in same function\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 471, __extension__ __PRETTY_FUNCTION__))
471 "Two blocks are not in same function")(static_cast <bool> (A->getParent() == B->getParent
() && "Two blocks are not in same function") ? void (
0) : __assert_fail ("A->getParent() == B->getParent() && \"Two blocks are not in same function\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 471, __extension__ __PRETTY_FUNCTION__));
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")(static_cast <bool> (NodeA && "A must be in the tree"
) ? void (0) : __assert_fail ("NodeA && \"A must be in the tree\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 483, __extension__ __PRETTY_FUNCTION__));
484 assert(NodeB && "B must be in the tree")(static_cast <bool> (NodeB && "B must be in the tree"
) ? void (0) : __assert_fail ("NodeB && \"B must be in the tree\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 484, __extension__ __PRETTY_FUNCTION__));
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)(static_cast <bool> (From) ? void (0) : __assert_fail (
"From", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 585, __extension__ __PRETTY_FUNCTION__));
586 assert(To)(static_cast <bool> (To) ? void (0) : __assert_fail ("To"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 586, __extension__ __PRETTY_FUNCTION__));
587 assert(From->getParent() == Parent)(static_cast <bool> (From->getParent() == Parent) ? void
(0) : __assert_fail ("From->getParent() == Parent", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 587, __extension__ __PRETTY_FUNCTION__));
588 assert(To->getParent() == Parent)(static_cast <bool> (To->getParent() == Parent) ? void
(0) : __assert_fail ("To->getParent() == Parent", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 588, __extension__ __PRETTY_FUNCTION__));
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)(static_cast <bool> (From) ? void (0) : __assert_fail (
"From", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 603, __extension__ __PRETTY_FUNCTION__));
604 assert(To)(static_cast <bool> (To) ? void (0) : __assert_fail ("To"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 604, __extension__ __PRETTY_FUNCTION__));
605 assert(From->getParent() == Parent)(static_cast <bool> (From->getParent() == Parent) ? void
(0) : __assert_fail ("From->getParent() == Parent", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 605, __extension__ __PRETTY_FUNCTION__));
606 assert(To->getParent() == Parent)(static_cast <bool> (To->getParent() == Parent) ? void
(0) : __assert_fail ("To->getParent() == Parent", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 606, __extension__ __PRETTY_FUNCTION__));
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!")(static_cast <bool> (getNode(BB) == nullptr && "Block already in dominator tree!"
) ? void (0) : __assert_fail ("getNode(BB) == nullptr && \"Block already in dominator tree!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 620, __extension__ __PRETTY_FUNCTION__));
621 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
622 assert(IDomNode && "Not immediate dominator specified for block!")(static_cast <bool> (IDomNode && "Not immediate dominator specified for block!"
) ? void (0) : __assert_fail ("IDomNode && \"Not immediate dominator specified for block!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 622, __extension__ __PRETTY_FUNCTION__));
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!")(static_cast <bool> (getNode(BB) == nullptr && "Block already in dominator tree!"
) ? void (0) : __assert_fail ("getNode(BB) == nullptr && \"Block already in dominator tree!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 633, __extension__ __PRETTY_FUNCTION__));
634 assert(!this->isPostDominator() &&(static_cast <bool> (!this->isPostDominator() &&
"Cannot change root of post-dominator tree") ? void (0) : __assert_fail
("!this->isPostDominator() && \"Cannot change root of post-dominator tree\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 635, __extension__ __PRETTY_FUNCTION__))
635 "Cannot change root of post-dominator tree")(static_cast <bool> (!this->isPostDominator() &&
"Cannot change root of post-dominator tree") ? void (0) : __assert_fail
("!this->isPostDominator() && \"Cannot change root of post-dominator tree\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 635, __extension__ __PRETTY_FUNCTION__));
636 DFSInfoValid = false;
637 DomTreeNodeBase<NodeT> *NewNode = createNode(BB);
638 if (Roots.empty()) {
639 addRoot(BB);
640 } else {
641 assert(Roots.size() == 1)(static_cast <bool> (Roots.size() == 1) ? void (0) : __assert_fail
("Roots.size() == 1", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 641, __extension__ __PRETTY_FUNCTION__));
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!")(static_cast <bool> (N && NewIDom && "Cannot change null node pointers!"
) ? void (0) : __assert_fail ("N && NewIDom && \"Cannot change null node pointers!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 657, __extension__ __PRETTY_FUNCTION__));
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.")(static_cast <bool> (Node && "Removing node that isn't in dominator tree."
) ? void (0) : __assert_fail ("Node && \"Removing node that isn't in dominator tree.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 671, __extension__ __PRETTY_FUNCTION__));
672 assert(Node->isLeaf() && "Node is not a leaf node.")(static_cast <bool> (Node->isLeaf() && "Node is not a leaf node."
) ? void (0) : __assert_fail ("Node->isLeaf() && \"Node is not a leaf node.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 672, __extension__ __PRETTY_FUNCTION__));
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() &&(static_cast <bool> (I != IDom->Children.end() &&
"Not in immediate dominator children set!") ? void (0) : __assert_fail
("I != IDom->Children.end() && \"Not in immediate dominator children set!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 681, __extension__ __PRETTY_FUNCTION__))
681 "Not in immediate dominator children set!")(static_cast <bool> (I != IDom->Children.end() &&
"Not in immediate dominator children set!") ? void (0) : __assert_fail
("I != IDom->Children.end() && \"Not in immediate dominator children set!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 681, __extension__ __PRETTY_FUNCTION__));
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
729public:
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")(static_cast <bool> ((!Parent || ThisRoot) && "Empty constructed DomTree"
) ? void (0) : __assert_fail ("(!Parent || ThisRoot) && \"Empty constructed DomTree\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 743, __extension__ __PRETTY_FUNCTION__));
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
815protected:
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),(static_cast <bool> (std::distance(GraphT::child_begin(
NewBB), GraphT::child_end(NewBB)) == 1 && "NewBB should have a single successor!"
) ? void (0) : __assert_fail ("std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1 && \"NewBB should have a single successor!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 838, __extension__ __PRETTY_FUNCTION__))
837 GraphT::child_end(NewBB)) == 1 &&(static_cast <bool> (std::distance(GraphT::child_begin(
NewBB), GraphT::child_end(NewBB)) == 1 && "NewBB should have a single successor!"
) ? void (0) : __assert_fail ("std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1 && \"NewBB should have a single successor!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 838, __extension__ __PRETTY_FUNCTION__))
838 "NewBB should have a single successor!")(static_cast <bool> (std::distance(GraphT::child_begin(
NewBB), GraphT::child_end(NewBB)) == 1 && "NewBB should have a single successor!"
) ? void (0) : __assert_fail ("std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1 && \"NewBB should have a single successor!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 838, __extension__ __PRETTY_FUNCTION__));
839 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
840
841 SmallVector<NodeRef, 4> PredBlocks(children<Inverse<N>>(NewBB));
842
843 assert(!PredBlocks.empty() && "No predblocks?")(static_cast <bool> (!PredBlocks.empty() && "No predblocks?"
) ? void (0) : __assert_fail ("!PredBlocks.empty() && \"No predblocks?\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 843, __extension__ __PRETTY_FUNCTION__));
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)(static_cast <bool> (A != B) ? void (0) : __assert_fail
("A != B", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 888, __extension__ __PRETTY_FUNCTION__));
889 assert(isReachableFromEntry(B))(static_cast <bool> (isReachableFromEntry(B)) ? void (0
) : __assert_fail ("isReachableFromEntry(B)", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 889, __extension__ __PRETTY_FUNCTION__));
890 assert(isReachableFromEntry(A))(static_cast <bool> (isReachableFromEntry(A)) ? void (0
) : __assert_fail ("isReachableFromEntry(A)", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/Support/GenericDomTree.h"
, 890, __extension__ __PRETTY_FUNCTION__));
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
914template <typename T>
915using DomTreeBase = DominatorTreeBase<T, false>;
916
917template <typename T>
918using 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.
922template <typename NodeT, bool IsPostDom>
923bool 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}
934template <typename NodeT, bool IsPostDom>
935bool 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
←

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.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
34namespace llvm {
35
36namespace detail {
37
38// We extend a pair to allow users to override the bucket type with their own
39// implementation without requiring two members.
40template <typename KeyT, typename ValueT>
41struct 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
52template <typename KeyT, typename ValueT,
53 typename KeyInfoT = DenseMapInfo<KeyT>,
54 typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>,
55 bool IsConst = false>
56class DenseMapIterator;
57
58template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
59 typename BucketT>
60class DenseMapBase : public DebugEpochBase {
61 template <typename T>
62 using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
63
64public:
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!")(static_cast <bool> (NumEntries == 0 && "Node count imbalance!"
) ? void (0) : __assert_fail ("NumEntries == 0 && \"Node count imbalance!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 138, __extension__ __PRETTY_FUNCTION__));
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
357protected:
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 &&(static_cast <bool> ((getNumBuckets() & (getNumBuckets
()-1)) == 0 && "# initial buckets must be a power of two!"
) ? void (0) : __assert_fail ("(getNumBuckets() & (getNumBuckets()-1)) == 0 && \"# initial buckets must be a power of two!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 378, __extension__ __PRETTY_FUNCTION__))
378 "# initial buckets must be a power of two!")(static_cast <bool> ((getNumBuckets() & (getNumBuckets
()-1)) == 0 && "# initial buckets must be a power of two!"
) ? void (0) : __assert_fail ("(getNumBuckets() & (getNumBuckets()-1)) == 0 && \"# initial buckets must be a power of two!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 378, __extension__ __PRETTY_FUNCTION__));
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?")(static_cast <bool> (!FoundVal && "Key already in new map?"
) ? void (0) : __assert_fail ("!FoundVal && \"Key already in new map?\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 408, __extension__ __PRETTY_FUNCTION__));
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)(static_cast <bool> (&other != this) ? void (0) : __assert_fail
("&other != this", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 423, __extension__ __PRETTY_FUNCTION__));
424 assert(getNumBuckets() == other.getNumBuckets())(static_cast <bool> (getNumBuckets() == other.getNumBuckets
()) ? void (0) : __assert_fail ("getNumBuckets() == other.getNumBuckets()"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 424, __extension__ __PRETTY_FUNCTION__));
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
463private:
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)(static_cast <bool> (TheBucket) ? void (0) : __assert_fail
("TheBucket", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 589, __extension__ __PRETTY_FUNCTION__));
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) &&(static_cast <bool> (!KeyInfoT::isEqual(Val, EmptyKey) &&
!KeyInfoT::isEqual(Val, TombstoneKey) && "Empty/Tombstone value shouldn't be inserted into map!"
) ? void (0) : __assert_fail ("!KeyInfoT::isEqual(Val, EmptyKey) && !KeyInfoT::isEqual(Val, TombstoneKey) && \"Empty/Tombstone value shouldn't be inserted into map!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 624, __extension__ __PRETTY_FUNCTION__))
623 !KeyInfoT::isEqual(Val, TombstoneKey) &&(static_cast <bool> (!KeyInfoT::isEqual(Val, EmptyKey) &&
!KeyInfoT::isEqual(Val, TombstoneKey) && "Empty/Tombstone value shouldn't be inserted into map!"
) ? void (0) : __assert_fail ("!KeyInfoT::isEqual(Val, EmptyKey) && !KeyInfoT::isEqual(Val, TombstoneKey) && \"Empty/Tombstone value shouldn't be inserted into map!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 624, __extension__ __PRETTY_FUNCTION__))
624 "Empty/Tombstone value shouldn't be inserted into map!")(static_cast <bool> (!KeyInfoT::isEqual(Val, EmptyKey) &&
!KeyInfoT::isEqual(Val, TombstoneKey) && "Empty/Tombstone value shouldn't be inserted into map!"
) ? void (0) : __assert_fail ("!KeyInfoT::isEqual(Val, EmptyKey) && !KeyInfoT::isEqual(Val, TombstoneKey) && \"Empty/Tombstone value shouldn't be inserted into map!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 624, __extension__ __PRETTY_FUNCTION__));
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
667public:
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).
683template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
684 typename BucketT>
685bool 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.
703template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
704 typename BucketT>
705bool 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
711template <typename KeyT, typename ValueT,
712 typename KeyInfoT = DenseMapInfo<KeyT>,
713 typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
714class 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
727public:
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)(static_cast <bool> (Buckets) ? void (0) : __assert_fail
("Buckets", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 807, __extension__ __PRETTY_FUNCTION__));
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
839private:
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
877template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,
878 typename KeyInfoT = DenseMapInfo<KeyT>,
879 typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>
880class 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
906public:
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 &&(static_cast <bool> (size_t(TmpEnd - TmpBegin) < InlineBuckets
&& "Too many inline buckets!") ? void (0) : __assert_fail
("size_t(TmpEnd - TmpBegin) < InlineBuckets && \"Too many inline buckets!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1059, __extension__ __PRETTY_FUNCTION__))
1059 "Too many inline buckets!")(static_cast <bool> (size_t(TmpEnd - TmpBegin) < InlineBuckets
&& "Too many inline buckets!") ? void (0) : __assert_fail
("size_t(TmpEnd - TmpBegin) < InlineBuckets && \"Too many inline buckets!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1059, __extension__ __PRETTY_FUNCTION__));
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
1115private:
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")(static_cast <bool> (Num < (1U << 31) &&
"Cannot support more than 1<<31 entries") ? void (0) :
__assert_fail ("Num < (1U << 31) && \"Cannot support more than 1<<31 entries\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1122, __extension__ __PRETTY_FUNCTION__));
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)(static_cast <bool> (Small) ? void (0) : __assert_fail (
"Small", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1135, __extension__ __PRETTY_FUNCTION__));
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)(static_cast <bool> (!Small) ? void (0) : __assert_fail
("!Small", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1148, __extension__ __PRETTY_FUNCTION__));
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")(static_cast <bool> (Num > InlineBuckets && "Must allocate more buckets than are inline"
) ? void (0) : __assert_fail ("Num > InlineBuckets && \"Must allocate more buckets than are inline\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1182, __extension__ __PRETTY_FUNCTION__));
1183 LargeRep Rep = {static_cast<BucketT *>(allocate_buffer(
1184 sizeof(BucketT) * Num, alignof(BucketT))),
1185 Num};
1186 return Rep;
1187 }
1188};
1189
1190template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
1191 bool IsConst>
1192class DenseMapIterator : DebugEpochBase::HandleBase {
1193 friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
1194 friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;
1195
1196public:
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
1204private:
1205 pointer Ptr = nullptr;
1206 pointer End = nullptr;
1207
1208public:
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!")(static_cast <bool> (isHandleInSync() && "invalid construction!"
) ? void (0) : __assert_fail ("isHandleInSync() && \"invalid construction!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1214, __extension__ __PRETTY_FUNCTION__));
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!")(static_cast <bool> (isHandleInSync() && "invalid iterator access!"
) ? void (0) : __assert_fail ("isHandleInSync() && \"invalid iterator access!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1234, __extension__ __PRETTY_FUNCTION__));
1235 assert(Ptr != End && "dereferencing end() iterator")(static_cast <bool> (Ptr != End && "dereferencing end() iterator"
) ? void (0) : __assert_fail ("Ptr != End && \"dereferencing end() iterator\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1235, __extension__ __PRETTY_FUNCTION__));
1236 if (shouldReverseIterate<KeyT>())
1237 return Ptr[-1];
1238 return *Ptr;
1239 }
1240 pointer operator->() const {
1241 assert(isHandleInSync() && "invalid iterator access!")(static_cast <bool> (isHandleInSync() && "invalid iterator access!"
) ? void (0) : __assert_fail ("isHandleInSync() && \"invalid iterator access!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1241, __extension__ __PRETTY_FUNCTION__));
1242 assert(Ptr != End && "dereferencing end() iterator")(static_cast <bool> (Ptr != End && "dereferencing end() iterator"
) ? void (0) : __assert_fail ("Ptr != End && \"dereferencing end() iterator\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1242, __extension__ __PRETTY_FUNCTION__));
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!")(static_cast <bool> ((!LHS.Ptr || LHS.isHandleInSync())
&& "handle not in sync!") ? void (0) : __assert_fail
("(!LHS.Ptr || LHS.isHandleInSync()) && \"handle not in sync!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1250, __extension__ __PRETTY_FUNCTION__));
13
←
Assuming field 'Ptr' is non-null
→
14
←
'?' condition is true
→
1251 assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!")(static_cast <bool> ((!RHS.Ptr || RHS.isHandleInSync())
&& "handle not in sync!") ? void (0) : __assert_fail
("(!RHS.Ptr || RHS.isHandleInSync()) && \"handle not in sync!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1251, __extension__ __PRETTY_FUNCTION__));
15
←
Assuming field 'Ptr' is null
→
16
←
'?' condition is true
→
1252 assert(LHS.getEpochAddress() == RHS.getEpochAddress() &&(static_cast <bool> (LHS.getEpochAddress() == RHS.getEpochAddress
() && "comparing incomparable iterators!") ? void (0)
: __assert_fail ("LHS.getEpochAddress() == RHS.getEpochAddress() && \"comparing incomparable iterators!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1253, __extension__ __PRETTY_FUNCTION__))
17
←
Assuming the condition is true
→
18
←
'?' condition is true
→
1253 "comparing incomparable iterators!")(static_cast <bool> (LHS.getEpochAddress() == RHS.getEpochAddress
() && "comparing incomparable iterators!") ? void (0)
: __assert_fail ("LHS.getEpochAddress() == RHS.getEpochAddress() && \"comparing incomparable iterators!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1253, __extension__ __PRETTY_FUNCTION__));
1254 return LHS.Ptr
18.1
'LHS.Ptr' is not equal to 'RHS.Ptr'
18.1
'LHS.Ptr' is not equal to 'RHS.Ptr'
18.1
'LHS.Ptr' is not equal to 'RHS.Ptr'
18.1
'LHS.Ptr' is not equal to 'RHS.Ptr'
 == RHS.Ptr;
19
←
Returning zero, which participates in a condition later
→
1255 }
1256
1257 friend bool operator!=(const DenseMapIterator &LHS,
1258 const DenseMapIterator &RHS) {
1259 return !(LHS == RHS);
12
←
Calling 'operator=='
→
20
←
Returning from 'operator=='
→
21
←
Returning the value 1, which participates in a condition later
→
1260 }
1261
1262 inline DenseMapIterator& operator++() { // Preincrement
1263 assert(isHandleInSync() && "invalid iterator access!")(static_cast <bool> (isHandleInSync() && "invalid iterator access!"
) ? void (0) : __assert_fail ("isHandleInSync() && \"invalid iterator access!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1263, __extension__ __PRETTY_FUNCTION__));
1264 assert(Ptr != End && "incrementing end() iterator")(static_cast <bool> (Ptr != End && "incrementing end() iterator"
) ? void (0) : __assert_fail ("Ptr != End && \"incrementing end() iterator\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1264, __extension__ __PRETTY_FUNCTION__));
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!")(static_cast <bool> (isHandleInSync() && "invalid iterator access!"
) ? void (0) : __assert_fail ("isHandleInSync() && \"invalid iterator access!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1275, __extension__ __PRETTY_FUNCTION__));
1276 DenseMapIterator tmp = *this; ++*this; return tmp;
1277 }
1278
1279private:
1280 void AdvancePastEmptyBuckets() {
1281 assert(Ptr <= End)(static_cast <bool> (Ptr <= End) ? void (0) : __assert_fail
("Ptr <= End", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1281, __extension__ __PRETTY_FUNCTION__));
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)(static_cast <bool> (Ptr >= End) ? void (0) : __assert_fail
("Ptr >= End", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/DenseMap.h"
, 1291, __extension__ __PRETTY_FUNCTION__));
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
1301template <typename KeyT, typename ValueT, typename KeyInfoT>
1302inline 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