Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name InlineSpiller.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-10~svn374877/lib/CodeGen -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn374877/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn374877=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-10-15-233810-7101-1 -x c++ /build/llvm-toolchain-snapshot-10~svn374877/lib/CodeGen/InlineSpiller.cpp

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

/build/llvm-toolchain-snapshot-10~svn374877/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#include <vector>
27
28namespace llvm {
29
30template <>
31inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot(
32 MachineBasicBlock *MBB) {
33 this->Roots.push_back(MBB);
34}
35
36extern template class DomTreeNodeBase<MachineBasicBlock>;
37extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree
38extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree
39
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 using DomTreeT = DomTreeBase<MachineBasicBlock>;
48
49 /// Helper structure used to hold all the basic blocks
50 /// involved in the split of a critical edge.
51 struct CriticalEdge {
52 MachineBasicBlock *FromBB;
53 MachineBasicBlock *ToBB;
54 MachineBasicBlock *NewBB;
55 };
56
57 /// Pile up all the critical edges to be split.
58 /// The splitting of a critical edge is local and thus, it is possible
59 /// to apply several of those changes at the same time.
60 mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit;
61
62 /// Remember all the basic blocks that are inserted during
63 /// edge splitting.
64 /// Invariant: NewBBs == all the basic blocks contained in the NewBB
65 /// field of all the elements of CriticalEdgesToSplit.
66 /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
67 /// such as BB == elt.NewBB.
68 mutable SmallSet<MachineBasicBlock *, 32> NewBBs;
69
70 /// The DominatorTreeBase that is used to compute a normal dominator tree.
71 std::unique_ptr<DomTreeT> DT;
72
73 /// Apply all the recorded critical edges to the DT.
74 /// This updates the underlying DT information in a way that uses
75 /// the fast query path of DT as much as possible.
76 ///
77 /// \post CriticalEdgesToSplit.empty().
78 void applySplitCriticalEdges() const;
79
80public:
81 static char ID; // Pass ID, replacement for typeid
82
83 MachineDominatorTree();
84
85 DomTreeT &getBase() {
86 if (!DT) DT.reset(new DomTreeT());
87 applySplitCriticalEdges();
88 return *DT;
89 }
90
91 void getAnalysisUsage(AnalysisUsage &AU) const override;
92
93 /// getRoots - Return the root blocks of the current CFG. This may include
94 /// multiple blocks if we are computing post dominators. For forward
95 /// dominators, this will always be a single block (the entry node).
96 ///
97 const SmallVectorImpl<MachineBasicBlock*> &getRoots() const {
98 applySplitCriticalEdges();
99 return DT->getRoots();
100 }
101
102 MachineBasicBlock *getRoot() const {
103 applySplitCriticalEdges();
104 return DT->getRoot();
105 }
106
107 MachineDomTreeNode *getRootNode() const {
108 applySplitCriticalEdges();
109 return DT->getRootNode();
110 }
111
112 bool runOnMachineFunction(MachineFunction &F) override;
113
114 bool dominates(const MachineDomTreeNode *A,
115 const MachineDomTreeNode *B) const {
116 applySplitCriticalEdges();
117 return DT->dominates(A, B);
118 }
119
120 bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const {
121 applySplitCriticalEdges();
122 return DT->dominates(A, B);
123 }
124
125 // dominates - Return true if A dominates B. This performs the
126 // special checks necessary if A and B are in the same basic block.
127 bool dominates(const MachineInstr *A, const MachineInstr *B) const {
128 applySplitCriticalEdges();
129 const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
130 if (BBA != BBB) return DT->dominates(BBA, BBB);
131
132 // Loop through the basic block until we find A or B.
133 MachineBasicBlock::const_iterator I = BBA->begin();
134 for (; &*I != A && &*I != B; ++I)
135 /*empty*/ ;
136
137 return &*I == A;
138 }
139
140 bool properlyDominates(const MachineDomTreeNode *A,
141 const MachineDomTreeNode *B) const {
142 applySplitCriticalEdges();
143 return DT->properlyDominates(A, B);
144 }
145
146 bool properlyDominates(const MachineBasicBlock *A,
147 const MachineBasicBlock *B) const {
148 applySplitCriticalEdges();
149 return DT->properlyDominates(A, B);
150 }
151
152 /// findNearestCommonDominator - Find nearest common dominator basic block
153 /// for basic block A and B. If there is no such block then return NULL.
154 MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A,
155 MachineBasicBlock *B) {
156 applySplitCriticalEdges();
157 return DT->findNearestCommonDominator(A, B);
158 }
159
160 MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
161 applySplitCriticalEdges();
162 return DT->getNode(BB);
10
Calling 'DominatorTreeBase::getNode'
14
Returning from 'DominatorTreeBase::getNode'
15
Returning pointer
163 }
164
165 /// getNode - return the (Post)DominatorTree node for the specified basic
166 /// block. This is the same as using operator[] on this class.
167 ///
168 MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
169 applySplitCriticalEdges();
170 return DT->getNode(BB);
171 }
172
173 /// addNewBlock - Add a new node to the dominator tree information. This
174 /// creates a new node as a child of DomBB dominator node,linking it into
175 /// the children list of the immediate dominator.
176 MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB,
177 MachineBasicBlock *DomBB) {
178 applySplitCriticalEdges();
179 return DT->addNewBlock(BB, DomBB);
180 }
181
182 /// changeImmediateDominator - This method is used to update the dominator
183 /// tree information when a node's immediate dominator changes.
184 ///
185 void changeImmediateDominator(MachineBasicBlock *N,
186 MachineBasicBlock *NewIDom) {
187 applySplitCriticalEdges();
188 DT->changeImmediateDominator(N, NewIDom);
189 }
190
191 void changeImmediateDominator(MachineDomTreeNode *N,
192 MachineDomTreeNode *NewIDom) {
193 applySplitCriticalEdges();
194 DT->changeImmediateDominator(N, NewIDom);
195 }
196
197 /// eraseNode - Removes a node from the dominator tree. Block must not
198 /// dominate any other blocks. Removes node from its immediate dominator's
199 /// children list. Deletes dominator node associated with basic block BB.
200 void eraseNode(MachineBasicBlock *BB) {
201 applySplitCriticalEdges();
202 DT->eraseNode(BB);
203 }
204
205 /// splitBlock - BB is split and now it has one successor. Update dominator
206 /// tree to reflect this change.
207 void splitBlock(MachineBasicBlock* NewBB) {
208 applySplitCriticalEdges();
209 DT->splitBlock(NewBB);
210 }
211
212 /// isReachableFromEntry - Return true if A is dominated by the entry
213 /// block of the function containing it.
214 bool isReachableFromEntry(const MachineBasicBlock *A) {
215 applySplitCriticalEdges();
216 return DT->isReachableFromEntry(A);
217 }
218
219 void releaseMemory() override;
220
221 void verifyAnalysis() const override;
222
223 void print(raw_ostream &OS, const Module*) const override;
224
225 /// Record that the critical edge (FromBB, ToBB) has been
226 /// split with NewBB.
227 /// This is best to use this method instead of directly update the
228 /// underlying information, because this helps mitigating the
229 /// number of time the DT information is invalidated.
230 ///
231 /// \note Do not use this method with regular edges.
232 ///
233 /// \note To benefit from the compile time improvement incurred by this
234 /// method, the users of this method have to limit the queries to the DT
235 /// interface between two edges splitting. In other words, they have to
236 /// pack the splitting of critical edges as much as possible.
237 void recordSplitCriticalEdge(MachineBasicBlock *FromBB,
238 MachineBasicBlock *ToBB,
239 MachineBasicBlock *NewBB) {
240 bool Inserted = NewBBs.insert(NewBB).second;
241 (void)Inserted;
242 assert(Inserted &&((Inserted && "A basic block inserted via edge splitting cannot appear twice"
) ? static_cast<void> (0) : __assert_fail ("Inserted && \"A basic block inserted via edge splitting cannot appear twice\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/CodeGen/MachineDominators.h"
, 243, __PRETTY_FUNCTION__))
243 "A basic block inserted via edge splitting cannot appear twice")((Inserted && "A basic block inserted via edge splitting cannot appear twice"
) ? static_cast<void> (0) : __assert_fail ("Inserted && \"A basic block inserted via edge splitting cannot appear twice\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/CodeGen/MachineDominators.h"
, 243, __PRETTY_FUNCTION__))
;
244 CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
245 }
246};
247
248//===-------------------------------------
249/// DominatorTree GraphTraits specialization so the DominatorTree can be
250/// iterable by generic graph iterators.
251///
252
253template <class Node, class ChildIterator>
254struct MachineDomTreeGraphTraitsBase {
255 using NodeRef = Node *;
256 using ChildIteratorType = ChildIterator;
257
258 static NodeRef getEntryNode(NodeRef N) { return N; }
259 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
260 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
261};
262
263template <class T> struct GraphTraits;
264
265template <>
266struct GraphTraits<MachineDomTreeNode *>
267 : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode,
268 MachineDomTreeNode::iterator> {};
269
270template <>
271struct GraphTraits<const MachineDomTreeNode *>
272 : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode,
273 MachineDomTreeNode::const_iterator> {
274};
275
276template <> struct GraphTraits<MachineDominatorTree*>
277 : public GraphTraits<MachineDomTreeNode *> {
278 static NodeRef getEntryNode(MachineDominatorTree *DT) {
279 return DT->getRootNode();
280 }
281};
282
283} // end namespace llvm
284
285#endif // LLVM_CODEGEN_MACHINEDOMINATORS_H

/build/llvm-toolchain-snapshot-10~svn374877/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/PointerIntPair.h"
29#include "llvm/ADT/STLExtras.h"
30#include "llvm/ADT/SmallPtrSet.h"
31#include "llvm/ADT/SmallVector.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#include <vector>
42
43namespace llvm {
44
45template <typename NodeT, bool IsPostDom>
46class DominatorTreeBase;
47
48namespace DomTreeBuilder {
49template <typename DomTreeT>
50struct SemiNCAInfo;
51} // namespace DomTreeBuilder
52
53/// Base class for the actual dominator tree node.
54template <class NodeT> class DomTreeNodeBase {
55 friend class PostDominatorTree;
56 friend class DominatorTreeBase<NodeT, false>;
57 friend class DominatorTreeBase<NodeT, true>;
58 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
59 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;
60
61 NodeT *TheBB;
62 DomTreeNodeBase *IDom;
63 unsigned Level;
64 std::vector<DomTreeNodeBase *> Children;
65 mutable unsigned DFSNumIn = ~0;
66 mutable unsigned DFSNumOut = ~0;
67
68 public:
69 DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
70 : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
71
72 using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
73 using const_iterator =
74 typename std::vector<DomTreeNodeBase *>::const_iterator;
75
76 iterator begin() { return Children.begin(); }
77 iterator end() { return Children.end(); }
78 const_iterator begin() const { return Children.begin(); }
79 const_iterator end() const { return Children.end(); }
80
81 NodeT *getBlock() const { return TheBB; }
82 DomTreeNodeBase *getIDom() const { return IDom; }
83 unsigned getLevel() const { return Level; }
84
85 const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
86
87 std::unique_ptr<DomTreeNodeBase> addChild(
88 std::unique_ptr<DomTreeNodeBase> C) {
89 Children.push_back(C.get());
90 return C;
91 }
92
93 size_t getNumChildren() const { return Children.size(); }
94
95 void clearAllChildren() { Children.clear(); }
96
97 bool compare(const DomTreeNodeBase *Other) const {
98 if (getNumChildren() != Other->getNumChildren())
99 return true;
100
101 if (Level != Other->Level) return true;
102
103 SmallPtrSet<const NodeT *, 4> OtherChildren;
104 for (const DomTreeNodeBase *I : *Other) {
105 const NodeT *Nd = I->getBlock();
106 OtherChildren.insert(Nd);
107 }
108
109 for (const DomTreeNodeBase *I : *this) {
110 const NodeT *N = I->getBlock();
111 if (OtherChildren.count(N) == 0)
112 return true;
113 }
114 return false;
115 }
116
117 void setIDom(DomTreeNodeBase *NewIDom) {
118 assert(IDom && "No immediate dominator?")((IDom && "No immediate dominator?") ? static_cast<
void> (0) : __assert_fail ("IDom && \"No immediate dominator?\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 118, __PRETTY_FUNCTION__))
;
119 if (IDom == NewIDom) return;
120
121 auto I = find(IDom->Children, this);
122 assert(I != IDom->Children.end() &&((I != IDom->Children.end() && "Not in immediate dominator children set!"
) ? static_cast<void> (0) : __assert_fail ("I != IDom->Children.end() && \"Not in immediate dominator children set!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 123, __PRETTY_FUNCTION__))
123 "Not in immediate dominator children set!")((I != IDom->Children.end() && "Not in immediate dominator children set!"
) ? static_cast<void> (0) : __assert_fail ("I != IDom->Children.end() && \"Not in immediate dominator children set!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 123, __PRETTY_FUNCTION__))
;
124 // I am no longer your child...
125 IDom->Children.erase(I);
126
127 // Switch to new dominator
128 IDom = NewIDom;
129 IDom->Children.push_back(this);
130
131 UpdateLevel();
132 }
133
134 /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
135 /// in the dominator tree. They are only guaranteed valid if
136 /// updateDFSNumbers() has been called.
137 unsigned getDFSNumIn() const { return DFSNumIn; }
138 unsigned getDFSNumOut() const { return DFSNumOut; }
139
140private:
141 // Return true if this node is dominated by other. Use this only if DFS info
142 // is valid.
143 bool DominatedBy(const DomTreeNodeBase *other) const {
144 return this->DFSNumIn >= other->DFSNumIn &&
145 this->DFSNumOut <= other->DFSNumOut;
146 }
147
148 void UpdateLevel() {
149 assert(IDom)((IDom) ? static_cast<void> (0) : __assert_fail ("IDom"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 149, __PRETTY_FUNCTION__))
;
150 if (Level == IDom->Level + 1) return;
151
152 SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
153
154 while (!WorkStack.empty()) {
155 DomTreeNodeBase *Current = WorkStack.pop_back_val();
156 Current->Level = Current->IDom->Level + 1;
157
158 for (DomTreeNodeBase *C : *Current) {
159 assert(C->IDom)((C->IDom) ? static_cast<void> (0) : __assert_fail (
"C->IDom", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 159, __PRETTY_FUNCTION__))
;
160 if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
161 }
162 }
163 }
164};
165
166template <class NodeT>
167raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
168 if (Node->getBlock())
169 Node->getBlock()->printAsOperand(O, false);
170 else
171 O << " <<exit node>>";
172
173 O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
174 << Node->getLevel() << "]\n";
175
176 return O;
177}
178
179template <class NodeT>
180void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
181 unsigned Lev) {
182 O.indent(2 * Lev) << "[" << Lev << "] " << N;
183 for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
184 E = N->end();
185 I != E; ++I)
186 PrintDomTree<NodeT>(*I, O, Lev + 1);
187}
188
189namespace DomTreeBuilder {
190// The routines below are provided in a separate header but referenced here.
191template <typename DomTreeT>
192void Calculate(DomTreeT &DT);
193
194template <typename DomTreeT>
195void CalculateWithUpdates(DomTreeT &DT,
196 ArrayRef<typename DomTreeT::UpdateType> Updates);
197
198template <typename DomTreeT>
199void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
200 typename DomTreeT::NodePtr To);
201
202template <typename DomTreeT>
203void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
204 typename DomTreeT::NodePtr To);
205
206template <typename DomTreeT>
207void ApplyUpdates(DomTreeT &DT,
208 ArrayRef<typename DomTreeT::UpdateType> Updates);
209
210template <typename DomTreeT>
211bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
212} // namespace DomTreeBuilder
213
214/// Core dominator tree base class.
215///
216/// This class is a generic template over graph nodes. It is instantiated for
217/// various graphs in the LLVM IR or in the code generator.
218template <typename NodeT, bool IsPostDom>
219class DominatorTreeBase {
220 public:
221 static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
222 "Currently DominatorTreeBase supports only pointer nodes");
223 using NodeType = NodeT;
224 using NodePtr = NodeT *;
225 using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
226 static_assert(std::is_pointer<ParentPtr>::value,
227 "Currently NodeT's parent must be a pointer type");
228 using ParentType = typename std::remove_pointer<ParentPtr>::type;
229 static constexpr bool IsPostDominator = IsPostDom;
230
231 using UpdateType = cfg::Update<NodePtr>;
232 using UpdateKind = cfg::UpdateKind;
233 static constexpr UpdateKind Insert = UpdateKind::Insert;
234 static constexpr UpdateKind Delete = UpdateKind::Delete;
235
236 enum class VerificationLevel { Fast, Basic, Full };
237
238protected:
239 // Dominators always have a single root, postdominators can have more.
240 SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
241
242 using DomTreeNodeMapType =
243 DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
244 DomTreeNodeMapType DomTreeNodes;
245 DomTreeNodeBase<NodeT> *RootNode = nullptr;
246 ParentPtr Parent = nullptr;
247
248 mutable bool DFSInfoValid = false;
249 mutable unsigned int SlowQueries = 0;
250
251 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
252
253 public:
254 DominatorTreeBase() {}
255
256 DominatorTreeBase(DominatorTreeBase &&Arg)
257 : Roots(std::move(Arg.Roots)),
258 DomTreeNodes(std::move(Arg.DomTreeNodes)),
259 RootNode(Arg.RootNode),
260 Parent(Arg.Parent),
261 DFSInfoValid(Arg.DFSInfoValid),
262 SlowQueries(Arg.SlowQueries) {
263 Arg.wipe();
264 }
265
266 DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
267 Roots = std::move(RHS.Roots);
268 DomTreeNodes = std::move(RHS.DomTreeNodes);
269 RootNode = RHS.RootNode;
270 Parent = RHS.Parent;
271 DFSInfoValid = RHS.DFSInfoValid;
272 SlowQueries = RHS.SlowQueries;
273 RHS.wipe();
274 return *this;
275 }
276
277 DominatorTreeBase(const DominatorTreeBase &) = delete;
278 DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
279
280 /// getRoots - Return the root blocks of the current CFG. This may include
281 /// multiple blocks if we are computing post dominators. For forward
282 /// dominators, this will always be a single block (the entry node).
283 ///
284 const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
285
286 /// isPostDominator - Returns true if analysis based of postdoms
287 ///
288 bool isPostDominator() const { return IsPostDominator; }
289
290 /// compare - Return false if the other dominator tree base matches this
291 /// dominator tree base. Otherwise return true.
292 bool compare(const DominatorTreeBase &Other) const {
293 if (Parent != Other.Parent) return true;
294
295 if (Roots.size() != Other.Roots.size())
296 return true;
297
298 if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
299 return true;
300
301 const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
302 if (DomTreeNodes.size() != OtherDomTreeNodes.size())
303 return true;
304
305 for (const auto &DomTreeNode : DomTreeNodes) {
306 NodeT *BB = DomTreeNode.first;
307 typename DomTreeNodeMapType::const_iterator OI =
308 OtherDomTreeNodes.find(BB);
309 if (OI == OtherDomTreeNodes.end())
310 return true;
311
312 DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
313 DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
314
315 if (MyNd.compare(&OtherNd))
316 return true;
317 }
318
319 return false;
320 }
321
322 void releaseMemory() { reset(); }
323
324 /// getNode - return the (Post)DominatorTree node for the specified basic
325 /// block. This is the same as using operator[] on this class. The result
326 /// may (but is not required to) be null for a forward (backwards)
327 /// statically unreachable block.
328 DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
329 auto I = DomTreeNodes.find(BB);
330 if (I != DomTreeNodes.end())
11
Assuming the condition is true
12
Taking true branch
331 return I->second.get();
13
Returning pointer
332 return nullptr;
333 }
334
335 /// See getNode.
336 DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
337 return getNode(BB);
338 }
339
340 /// getRootNode - This returns the entry node for the CFG of the function. If
341 /// this tree represents the post-dominance relations for a function, however,
342 /// this root may be a node with the block == NULL. This is the case when
343 /// there are multiple exit nodes from a particular function. Consumers of
344 /// post-dominance information must be capable of dealing with this
345 /// possibility.
346 ///
347 DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
348 const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
349
350 /// Get all nodes dominated by R, including R itself.
351 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
352 Result.clear();
353 const DomTreeNodeBase<NodeT> *RN = getNode(R);
354 if (!RN)
355 return; // If R is unreachable, it will not be present in the DOM tree.
356 SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
357 WL.push_back(RN);
358
359 while (!WL.empty()) {
360 const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
361 Result.push_back(N->getBlock());
362 WL.append(N->begin(), N->end());
363 }
364 }
365
366 /// properlyDominates - Returns true iff A dominates B and A != B.
367 /// Note that this is not a constant time operation!
368 ///
369 bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
370 const DomTreeNodeBase<NodeT> *B) const {
371 if (!A || !B)
372 return false;
373 if (A == B)
374 return false;
375 return dominates(A, B);
376 }
377
378 bool properlyDominates(const NodeT *A, const NodeT *B) const;
379
380 /// isReachableFromEntry - Return true if A is dominated by the entry
381 /// block of the function containing it.
382 bool isReachableFromEntry(const NodeT *A) const {
383 assert(!this->isPostDominator() &&((!this->isPostDominator() && "This is not implemented for post dominators"
) ? static_cast<void> (0) : __assert_fail ("!this->isPostDominator() && \"This is not implemented for post dominators\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 384, __PRETTY_FUNCTION__))
384 "This is not implemented for post dominators")((!this->isPostDominator() && "This is not implemented for post dominators"
) ? static_cast<void> (0) : __assert_fail ("!this->isPostDominator() && \"This is not implemented for post dominators\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 384, __PRETTY_FUNCTION__))
;
385 return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
386 }
387
388 bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
389
390 /// dominates - Returns true iff A dominates B. Note that this is not a
391 /// constant time operation!
392 ///
393 bool dominates(const DomTreeNodeBase<NodeT> *A,
394 const DomTreeNodeBase<NodeT> *B) const {
395 // A node trivially dominates itself.
396 if (B == A)
397 return true;
398
399 // An unreachable node is dominated by anything.
400 if (!isReachableFromEntry(B))
401 return true;
402
403 // And dominates nothing.
404 if (!isReachableFromEntry(A))
405 return false;
406
407 if (B->getIDom() == A) return true;
408
409 if (A->getIDom() == B) return false;
410
411 // A can only dominate B if it is higher in the tree.
412 if (A->getLevel() >= B->getLevel()) return false;
413
414 // Compare the result of the tree walk and the dfs numbers, if expensive
415 // checks are enabled.
416#ifdef EXPENSIVE_CHECKS
417 assert((!DFSInfoValid ||(((!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy
(A))) && "Tree walk disagrees with dfs numbers!") ? static_cast
<void> (0) : __assert_fail ("(!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && \"Tree walk disagrees with dfs numbers!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 419, __PRETTY_FUNCTION__))
418 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&(((!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy
(A))) && "Tree walk disagrees with dfs numbers!") ? static_cast
<void> (0) : __assert_fail ("(!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && \"Tree walk disagrees with dfs numbers!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 419, __PRETTY_FUNCTION__))
419 "Tree walk disagrees with dfs numbers!")(((!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy
(A))) && "Tree walk disagrees with dfs numbers!") ? static_cast
<void> (0) : __assert_fail ("(!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && \"Tree walk disagrees with dfs numbers!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 419, __PRETTY_FUNCTION__))
;
420#endif
421
422 if (DFSInfoValid)
423 return B->DominatedBy(A);
424
425 // If we end up with too many slow queries, just update the
426 // DFS numbers on the theory that we are going to keep querying.
427 SlowQueries++;
428 if (SlowQueries > 32) {
429 updateDFSNumbers();
430 return B->DominatedBy(A);
431 }
432
433 return dominatedBySlowTreeWalk(A, B);
434 }
435
436 bool dominates(const NodeT *A, const NodeT *B) const;
437
438 NodeT *getRoot() const {
439 assert(this->Roots.size() == 1 && "Should always have entry node!")((this->Roots.size() == 1 && "Should always have entry node!"
) ? static_cast<void> (0) : __assert_fail ("this->Roots.size() == 1 && \"Should always have entry node!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 439, __PRETTY_FUNCTION__))
;
440 return this->Roots[0];
441 }
442
443 /// findNearestCommonDominator - Find nearest common dominator basic block
444 /// for basic block A and B. If there is no such block then return nullptr.
445 NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
446 assert(A && B && "Pointers are not valid")((A && B && "Pointers are not valid") ? static_cast
<void> (0) : __assert_fail ("A && B && \"Pointers are not valid\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 446, __PRETTY_FUNCTION__))
;
447 assert(A->getParent() == B->getParent() &&((A->getParent() == B->getParent() && "Two blocks are not in same function"
) ? static_cast<void> (0) : __assert_fail ("A->getParent() == B->getParent() && \"Two blocks are not in same function\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 448, __PRETTY_FUNCTION__))
448 "Two blocks are not in same function")((A->getParent() == B->getParent() && "Two blocks are not in same function"
) ? static_cast<void> (0) : __assert_fail ("A->getParent() == B->getParent() && \"Two blocks are not in same function\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 448, __PRETTY_FUNCTION__))
;
449
450 // If either A or B is a entry block then it is nearest common dominator
451 // (for forward-dominators).
452 if (!isPostDominator()) {
453 NodeT &Entry = A->getParent()->front();
454 if (A == &Entry || B == &Entry)
455 return &Entry;
456 }
457
458 DomTreeNodeBase<NodeT> *NodeA = getNode(A);
459 DomTreeNodeBase<NodeT> *NodeB = getNode(B);
460
461 if (!NodeA || !NodeB) return nullptr;
462
463 // Use level information to go up the tree until the levels match. Then
464 // continue going up til we arrive at the same node.
465 while (NodeA && NodeA != NodeB) {
466 if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
467
468 NodeA = NodeA->IDom;
469 }
470
471 return NodeA ? NodeA->getBlock() : nullptr;
472 }
473
474 const NodeT *findNearestCommonDominator(const NodeT *A,
475 const NodeT *B) const {
476 // Cast away the const qualifiers here. This is ok since
477 // const is re-introduced on the return type.
478 return findNearestCommonDominator(const_cast<NodeT *>(A),
479 const_cast<NodeT *>(B));
480 }
481
482 bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
483 return isPostDominator() && !A->getBlock();
484 }
485
486 //===--------------------------------------------------------------------===//
487 // API to update (Post)DominatorTree information based on modifications to
488 // the CFG...
489
490 /// Inform the dominator tree about a sequence of CFG edge insertions and
491 /// deletions and perform a batch update on the tree.
492 ///
493 /// This function should be used when there were multiple CFG updates after
494 /// the last dominator tree update. It takes care of performing the updates
495 /// in sync with the CFG and optimizes away the redundant operations that
496 /// cancel each other.
497 /// The functions expects the sequence of updates to be balanced. Eg.:
498 /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
499 /// logically it results in a single insertions.
500 /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
501 /// sense to insert the same edge twice.
502 ///
503 /// What's more, the functions assumes that it's safe to ask every node in the
504 /// CFG about its children and inverse children. This implies that deletions
505 /// of CFG edges must not delete the CFG nodes before calling this function.
506 ///
507 /// The applyUpdates function can reorder the updates and remove redundant
508 /// ones internally. The batch updater is also able to detect sequences of
509 /// zero and exactly one update -- it's optimized to do less work in these
510 /// cases.
511 ///
512 /// Note that for postdominators it automatically takes care of applying
513 /// updates on reverse edges internally (so there's no need to swap the
514 /// From and To pointers when constructing DominatorTree::UpdateType).
515 /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
516 /// with the same template parameter T.
517 ///
518 /// \param Updates An unordered sequence of updates to perform.
519 ///
520 void applyUpdates(ArrayRef<UpdateType> Updates) {
521 DomTreeBuilder::ApplyUpdates(*this, Updates);
522 }
523
524 /// Inform the dominator tree about a CFG edge insertion and update the tree.
525 ///
526 /// This function has to be called just before or just after making the update
527 /// on the actual CFG. There cannot be any other updates that the dominator
528 /// tree doesn't know about.
529 ///
530 /// Note that for postdominators it automatically takes care of inserting
531 /// a reverse edge internally (so there's no need to swap the parameters).
532 ///
533 void insertEdge(NodeT *From, NodeT *To) {
534 assert(From)((From) ? static_cast<void> (0) : __assert_fail ("From"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 534, __PRETTY_FUNCTION__))
;
535 assert(To)((To) ? static_cast<void> (0) : __assert_fail ("To", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 535, __PRETTY_FUNCTION__))
;
536 assert(From->getParent() == Parent)((From->getParent() == Parent) ? static_cast<void> (
0) : __assert_fail ("From->getParent() == Parent", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 536, __PRETTY_FUNCTION__))
;
537 assert(To->getParent() == Parent)((To->getParent() == Parent) ? static_cast<void> (0)
: __assert_fail ("To->getParent() == Parent", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 537, __PRETTY_FUNCTION__))
;
538 DomTreeBuilder::InsertEdge(*this, From, To);
539 }
540
541 /// Inform the dominator tree about a CFG edge deletion and update the tree.
542 ///
543 /// This function has to be called just after making the update on the actual
544 /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
545 /// DEBUG mode. There cannot be any other updates that the
546 /// dominator tree doesn't know about.
547 ///
548 /// Note that for postdominators it automatically takes care of deleting
549 /// a reverse edge internally (so there's no need to swap the parameters).
550 ///
551 void deleteEdge(NodeT *From, NodeT *To) {
552 assert(From)((From) ? static_cast<void> (0) : __assert_fail ("From"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 552, __PRETTY_FUNCTION__))
;
553 assert(To)((To) ? static_cast<void> (0) : __assert_fail ("To", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 553, __PRETTY_FUNCTION__))
;
554 assert(From->getParent() == Parent)((From->getParent() == Parent) ? static_cast<void> (
0) : __assert_fail ("From->getParent() == Parent", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 554, __PRETTY_FUNCTION__))
;
555 assert(To->getParent() == Parent)((To->getParent() == Parent) ? static_cast<void> (0)
: __assert_fail ("To->getParent() == Parent", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 555, __PRETTY_FUNCTION__))
;
556 DomTreeBuilder::DeleteEdge(*this, From, To);
557 }
558
559 /// Add a new node to the dominator tree information.
560 ///
561 /// This creates a new node as a child of DomBB dominator node, linking it
562 /// into the children list of the immediate dominator.
563 ///
564 /// \param BB New node in CFG.
565 /// \param DomBB CFG node that is dominator for BB.
566 /// \returns New dominator tree node that represents new CFG node.
567 ///
568 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
569 assert(getNode(BB) == nullptr && "Block already in dominator tree!")((getNode(BB) == nullptr && "Block already in dominator tree!"
) ? static_cast<void> (0) : __assert_fail ("getNode(BB) == nullptr && \"Block already in dominator tree!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 569, __PRETTY_FUNCTION__))
;
570 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
571 assert(IDomNode && "Not immediate dominator specified for block!")((IDomNode && "Not immediate dominator specified for block!"
) ? static_cast<void> (0) : __assert_fail ("IDomNode && \"Not immediate dominator specified for block!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 571, __PRETTY_FUNCTION__))
;
572 DFSInfoValid = false;
573 return (DomTreeNodes[BB] = IDomNode->addChild(
574 std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
575 }
576
577 /// Add a new node to the forward dominator tree and make it a new root.
578 ///
579 /// \param BB New node in CFG.
580 /// \returns New dominator tree node that represents new CFG node.
581 ///
582 DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
583 assert(getNode(BB) == nullptr && "Block already in dominator tree!")((getNode(BB) == nullptr && "Block already in dominator tree!"
) ? static_cast<void> (0) : __assert_fail ("getNode(BB) == nullptr && \"Block already in dominator tree!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 583, __PRETTY_FUNCTION__))
;
584 assert(!this->isPostDominator() &&((!this->isPostDominator() && "Cannot change root of post-dominator tree"
) ? static_cast<void> (0) : __assert_fail ("!this->isPostDominator() && \"Cannot change root of post-dominator tree\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 585, __PRETTY_FUNCTION__))
585 "Cannot change root of post-dominator tree")((!this->isPostDominator() && "Cannot change root of post-dominator tree"
) ? static_cast<void> (0) : __assert_fail ("!this->isPostDominator() && \"Cannot change root of post-dominator tree\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 585, __PRETTY_FUNCTION__))
;
586 DFSInfoValid = false;
587 DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
588 std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
589 if (Roots.empty()) {
590 addRoot(BB);
591 } else {
592 assert(Roots.size() == 1)((Roots.size() == 1) ? static_cast<void> (0) : __assert_fail
("Roots.size() == 1", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 592, __PRETTY_FUNCTION__))
;
593 NodeT *OldRoot = Roots.front();
594 auto &OldNode = DomTreeNodes[OldRoot];
595 OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
596 OldNode->IDom = NewNode;
597 OldNode->UpdateLevel();
598 Roots[0] = BB;
599 }
600 return RootNode = NewNode;
601 }
602
603 /// changeImmediateDominator - This method is used to update the dominator
604 /// tree information when a node's immediate dominator changes.
605 ///
606 void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
607 DomTreeNodeBase<NodeT> *NewIDom) {
608 assert(N && NewIDom && "Cannot change null node pointers!")((N && NewIDom && "Cannot change null node pointers!"
) ? static_cast<void> (0) : __assert_fail ("N && NewIDom && \"Cannot change null node pointers!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 608, __PRETTY_FUNCTION__))
;
609 DFSInfoValid = false;
610 N->setIDom(NewIDom);
611 }
612
613 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
614 changeImmediateDominator(getNode(BB), getNode(NewBB));
615 }
616
617 /// eraseNode - Removes a node from the dominator tree. Block must not
618 /// dominate any other blocks. Removes node from its immediate dominator's
619 /// children list. Deletes dominator node associated with basic block BB.
620 void eraseNode(NodeT *BB) {
621 DomTreeNodeBase<NodeT> *Node = getNode(BB);
622 assert(Node && "Removing node that isn't in dominator tree.")((Node && "Removing node that isn't in dominator tree."
) ? static_cast<void> (0) : __assert_fail ("Node && \"Removing node that isn't in dominator tree.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 622, __PRETTY_FUNCTION__))
;
623 assert(Node->getChildren().empty() && "Node is not a leaf node.")((Node->getChildren().empty() && "Node is not a leaf node."
) ? static_cast<void> (0) : __assert_fail ("Node->getChildren().empty() && \"Node is not a leaf node.\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 623, __PRETTY_FUNCTION__))
;
624
625 DFSInfoValid = false;
626
627 // Remove node from immediate dominator's children list.
628 DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
629 if (IDom) {
630 const auto I = find(IDom->Children, Node);
631 assert(I != IDom->Children.end() &&((I != IDom->Children.end() && "Not in immediate dominator children set!"
) ? static_cast<void> (0) : __assert_fail ("I != IDom->Children.end() && \"Not in immediate dominator children set!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 632, __PRETTY_FUNCTION__))
632 "Not in immediate dominator children set!")((I != IDom->Children.end() && "Not in immediate dominator children set!"
) ? static_cast<void> (0) : __assert_fail ("I != IDom->Children.end() && \"Not in immediate dominator children set!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 632, __PRETTY_FUNCTION__))
;
633 // I am no longer your child...
634 IDom->Children.erase(I);
635 }
636
637 DomTreeNodes.erase(BB);
638
639 if (!IsPostDom) return;
640
641 // Remember to update PostDominatorTree roots.
642 auto RIt = llvm::find(Roots, BB);
643 if (RIt != Roots.end()) {
644 std::swap(*RIt, Roots.back());
645 Roots.pop_back();
646 }
647 }
648
649 /// splitBlock - BB is split and now it has one successor. Update dominator
650 /// tree to reflect this change.
651 void splitBlock(NodeT *NewBB) {
652 if (IsPostDominator)
653 Split<Inverse<NodeT *>>(NewBB);
654 else
655 Split<NodeT *>(NewBB);
656 }
657
658 /// print - Convert to human readable form
659 ///
660 void print(raw_ostream &O) const {
661 O << "=============================--------------------------------\n";
662 if (IsPostDominator)
663 O << "Inorder PostDominator Tree: ";
664 else
665 O << "Inorder Dominator Tree: ";
666 if (!DFSInfoValid)
667 O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
668 O << "\n";
669
670 // The postdom tree can have a null root if there are no returns.
671 if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
672 O << "Roots: ";
673 for (const NodePtr Block : Roots) {
674 Block->printAsOperand(O, false);
675 O << " ";
676 }
677 O << "\n";
678 }
679
680public:
681 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
682 /// dominator tree in dfs order.
683 void updateDFSNumbers() const {
684 if (DFSInfoValid) {
685 SlowQueries = 0;
686 return;
687 }
688
689 SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
690 typename DomTreeNodeBase<NodeT>::const_iterator>,
691 32> WorkStack;
692
693 const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
694 assert((!Parent || ThisRoot) && "Empty constructed DomTree")(((!Parent || ThisRoot) && "Empty constructed DomTree"
) ? static_cast<void> (0) : __assert_fail ("(!Parent || ThisRoot) && \"Empty constructed DomTree\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 694, __PRETTY_FUNCTION__))
;
695 if (!ThisRoot)
696 return;
697
698 // Both dominators and postdominators have a single root node. In the case
699 // case of PostDominatorTree, this node is a virtual root.
700 WorkStack.push_back({ThisRoot, ThisRoot->begin()});
701
702 unsigned DFSNum = 0;
703 ThisRoot->DFSNumIn = DFSNum++;
704
705 while (!WorkStack.empty()) {
706 const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
707 const auto ChildIt = WorkStack.back().second;
708
709 // If we visited all of the children of this node, "recurse" back up the
710 // stack setting the DFOutNum.
711 if (ChildIt == Node->end()) {
712 Node->DFSNumOut = DFSNum++;
713 WorkStack.pop_back();
714 } else {
715 // Otherwise, recursively visit this child.
716 const DomTreeNodeBase<NodeT> *Child = *ChildIt;
717 ++WorkStack.back().second;
718
719 WorkStack.push_back({Child, Child->begin()});
720 Child->DFSNumIn = DFSNum++;
721 }
722 }
723
724 SlowQueries = 0;
725 DFSInfoValid = true;
726 }
727
728 /// recalculate - compute a dominator tree for the given function
729 void recalculate(ParentType &Func) {
730 Parent = &Func;
731 DomTreeBuilder::Calculate(*this);
732 }
733
734 void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) {
735 Parent = &Func;
736 DomTreeBuilder::CalculateWithUpdates(*this, Updates);
737 }
738
739 /// verify - checks if the tree is correct. There are 3 level of verification:
740 /// - Full -- verifies if the tree is correct by making sure all the
741 /// properties (including the parent and the sibling property)
742 /// hold.
743 /// Takes O(N^3) time.
744 ///
745 /// - Basic -- checks if the tree is correct, but compares it to a freshly
746 /// constructed tree instead of checking the sibling property.
747 /// Takes O(N^2) time.
748 ///
749 /// - Fast -- checks basic tree structure and compares it with a freshly
750 /// constructed tree.
751 /// Takes O(N^2) time worst case, but is faster in practise (same
752 /// as tree construction).
753 bool verify(VerificationLevel VL = VerificationLevel::Full) const {
754 return DomTreeBuilder::Verify(*this, VL);
755 }
756
757protected:
758 void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
759
760 void reset() {
761 DomTreeNodes.clear();
762 Roots.clear();
763 RootNode = nullptr;
764 Parent = nullptr;
765 DFSInfoValid = false;
766 SlowQueries = 0;
767 }
768
769 // NewBB is split and now it has one successor. Update dominator tree to
770 // reflect this change.
771 template <class N>
772 void Split(typename GraphTraits<N>::NodeRef NewBB) {
773 using GraphT = GraphTraits<N>;
774 using NodeRef = typename GraphT::NodeRef;
775 assert(std::distance(GraphT::child_begin(NewBB),((std::distance(GraphT::child_begin(NewBB), GraphT::child_end
(NewBB)) == 1 && "NewBB should have a single successor!"
) ? static_cast<void> (0) : __assert_fail ("std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1 && \"NewBB should have a single successor!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 777, __PRETTY_FUNCTION__))
776 GraphT::child_end(NewBB)) == 1 &&((std::distance(GraphT::child_begin(NewBB), GraphT::child_end
(NewBB)) == 1 && "NewBB should have a single successor!"
) ? static_cast<void> (0) : __assert_fail ("std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1 && \"NewBB should have a single successor!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 777, __PRETTY_FUNCTION__))
777 "NewBB should have a single successor!")((std::distance(GraphT::child_begin(NewBB), GraphT::child_end
(NewBB)) == 1 && "NewBB should have a single successor!"
) ? static_cast<void> (0) : __assert_fail ("std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1 && \"NewBB should have a single successor!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 777, __PRETTY_FUNCTION__))
;
778 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
779
780 std::vector<NodeRef> PredBlocks;
781 for (const auto &Pred : children<Inverse<N>>(NewBB))
782 PredBlocks.push_back(Pred);
783
784 assert(!PredBlocks.empty() && "No predblocks?")((!PredBlocks.empty() && "No predblocks?") ? static_cast
<void> (0) : __assert_fail ("!PredBlocks.empty() && \"No predblocks?\""
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 784, __PRETTY_FUNCTION__))
;
785
786 bool NewBBDominatesNewBBSucc = true;
787 for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
788 if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
789 isReachableFromEntry(Pred)) {
790 NewBBDominatesNewBBSucc = false;
791 break;
792 }
793 }
794
795 // Find NewBB's immediate dominator and create new dominator tree node for
796 // NewBB.
797 NodeT *NewBBIDom = nullptr;
798 unsigned i = 0;
799 for (i = 0; i < PredBlocks.size(); ++i)
800 if (isReachableFromEntry(PredBlocks[i])) {
801 NewBBIDom = PredBlocks[i];
802 break;
803 }
804
805 // It's possible that none of the predecessors of NewBB are reachable;
806 // in that case, NewBB itself is unreachable, so nothing needs to be
807 // changed.
808 if (!NewBBIDom) return;
809
810 for (i = i + 1; i < PredBlocks.size(); ++i) {
811 if (isReachableFromEntry(PredBlocks[i]))
812 NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
813 }
814
815 // Create the new dominator tree node... and set the idom of NewBB.
816 DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
817
818 // If NewBB strictly dominates other blocks, then it is now the immediate
819 // dominator of NewBBSucc. Update the dominator tree as appropriate.
820 if (NewBBDominatesNewBBSucc) {
821 DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
822 changeImmediateDominator(NewBBSuccNode, NewBBNode);
823 }
824 }
825
826 private:
827 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
828 const DomTreeNodeBase<NodeT> *B) const {
829 assert(A != B)((A != B) ? static_cast<void> (0) : __assert_fail ("A != B"
, "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 829, __PRETTY_FUNCTION__))
;
830 assert(isReachableFromEntry(B))((isReachableFromEntry(B)) ? static_cast<void> (0) : __assert_fail
("isReachableFromEntry(B)", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 830, __PRETTY_FUNCTION__))
;
831 assert(isReachableFromEntry(A))((isReachableFromEntry(A)) ? static_cast<void> (0) : __assert_fail
("isReachableFromEntry(A)", "/build/llvm-toolchain-snapshot-10~svn374877/include/llvm/Support/GenericDomTree.h"
, 831, __PRETTY_FUNCTION__))
;
832
833 const unsigned ALevel = A->getLevel();
834 const DomTreeNodeBase<NodeT> *IDom;
835
836 // Don't walk nodes above A's subtree. When we reach A's level, we must
837 // either find A or be in some other subtree not dominated by A.
838 while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
839 B = IDom; // Walk up the tree
840
841 return B == A;
842 }
843
844 /// Wipe this tree's state without releasing any resources.
845 ///
846 /// This is essentially a post-move helper only. It leaves the object in an
847 /// assignable and destroyable state, but otherwise invalid.
848 void wipe() {
849 DomTreeNodes.clear();
850 RootNode = nullptr;
851 Parent = nullptr;
852 }
853};
854
855template <typename T>
856using DomTreeBase = DominatorTreeBase<T, false>;
857
858template <typename T>
859using PostDomTreeBase = DominatorTreeBase<T, true>;
860
861// These two functions are declared out of line as a workaround for building
862// with old (< r147295) versions of clang because of pr11642.
863template <typename NodeT, bool IsPostDom>
864bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
865 const NodeT *B) const {
866 if (A == B)
867 return true;
868
869 // Cast away the const qualifiers here. This is ok since
870 // this function doesn't actually return the values returned
871 // from getNode.
872 return dominates(getNode(const_cast<NodeT *>(A)),
873 getNode(const_cast<NodeT *>(B)));
874}
875template <typename NodeT, bool IsPostDom>
876bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
877 const NodeT *A, const NodeT *B) const {
878 if (A == B)
879 return false;
880
881 // Cast away the const qualifiers here. This is ok since
882 // this function doesn't actually return the values returned
883 // from getNode.
884 return dominates(getNode(const_cast<NodeT *>(A)),
885 getNode(const_cast<NodeT *>(B)));
886}
887
888} // end namespace llvm
889
890#endif // LLVM_SUPPORT_GENERICDOMTREE_H