Bug Summary

File:llvm/lib/CodeGen/InlineSpiller.cpp
Warning:line 1362, 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 -clear-ast-before-backend -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 -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/build-llvm -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 lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/llvm/lib/CodeGen -I include -I /build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/llvm/include -D _FORTIFY_SOURCE=2 -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 -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/= -O3 -Wno-unused-command-line-argument -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~++20220128100846+e1a12767ee62/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -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-2022-01-28-233020-220964-1 -x c++ /build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/llvm/lib/CodeGen/InlineSpiller.cpp

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

/build/llvm-toolchain-snapshot-14~++20220128100846+e1a12767ee62/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 MachineDomTree = DomTreeBase<MachineBasicBlock>;
40using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>;
41
42//===-------------------------------------
43/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
44/// compute a normal dominator tree.
45///
46class MachineDominatorTree : public MachineFunctionPass {
47 /// Helper structure used to hold all the basic blocks
48 /// involved in the split of a critical edge.
49 struct CriticalEdge {
50 MachineBasicBlock *FromBB;
51 MachineBasicBlock *ToBB;
52 MachineBasicBlock *NewBB;
53 };
54
55 /// Pile up all the critical edges to be split.
56 /// The splitting of a critical edge is local and thus, it is possible
57 /// to apply several of those changes at the same time.
58 mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit;
59
60 /// Remember all the basic blocks that are inserted during
61 /// edge splitting.
62 /// Invariant: NewBBs == all the basic blocks contained in the NewBB
63 /// field of all the elements of CriticalEdgesToSplit.
64 /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
65 /// such as BB == elt.NewBB.
66 mutable SmallSet<MachineBasicBlock *, 32> NewBBs;
67
68 /// The DominatorTreeBase that is used to compute a normal dominator tree.
69 std::unique_ptr<MachineDomTree> DT;
70
71 /// Apply all the recorded critical edges to the DT.
72 /// This updates the underlying DT information in a way that uses
73 /// the fast query path of DT as much as possible.
74 ///
75 /// \post CriticalEdgesToSplit.empty().
76 void applySplitCriticalEdges() const;
77
78public:
79 static char ID; // Pass ID, replacement for typeid
80
81 MachineDominatorTree();
82 explicit MachineDominatorTree(MachineFunction &MF) : MachineFunctionPass(ID) {
83 calculate(MF);
84 }
85
86 MachineDomTree &getBase() {
87 if (!DT)
88 DT.reset(new MachineDomTree());
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\""
, "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\""
, "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~++20220128100846+e1a12767ee62/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?\""
, "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!\""
, "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!\""
, "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", "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", "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\""
, "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\""
, "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!\""
, "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!\""
, "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!\""
, "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!\""
, "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\""
, "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\""
, "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\""
, "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\""
, "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\""
, "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 (as long as it is done in a deterministic fashion). The
532 /// batch updater is also able to detect sequences of zero and exactly one
533 /// update -- it's optimized to do less work in these 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 ordered sequence of updates to perform. The current CFG
542 /// 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 ordered sequence of updates to perform. The current CFG
551 /// and the reverse of these updates provides the pre-view of the CFG.
552 /// \param PostViewUpdates An ordered 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", "llvm/include/llvm/Support/GenericDomTree.h", 585, __extension__
__PRETTY_FUNCTION__))
;
586 assert(To)(static_cast <bool> (To) ? void (0) : __assert_fail ("To"
, "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", "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", "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", "llvm/include/llvm/Support/GenericDomTree.h", 603, __extension__
__PRETTY_FUNCTION__))
;
604 assert(To)(static_cast <bool> (To) ? void (0) : __assert_fail ("To"
, "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", "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", "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!\""
, "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!\""
, "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!\""
, "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\""
, "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\""
, "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", "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!\""
, "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.\""
, "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.\""
, "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!\""
, "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!\""
, "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\""
, "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!\""
, "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!\""
, "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!\""
, "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?\""
, "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", "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)", "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)", "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~++20220128100846+e1a12767ee62/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!\""
, "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!\""
, "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!\""
, "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?\""
, "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", "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()"
, "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", "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!\""
, "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!\""
, "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!\""
, "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", "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!\""
, "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!\""
, "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\""
, "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", "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", "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\""
, "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!\""
, "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!\""
, "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\""
, "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!\""
, "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\""
, "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!\""
, "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!\""
, "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!\""
, "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!\""
, "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!\""
, "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\""
, "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!\""
, "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", "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", "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