Bug Summary

File:build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/CodeGen/InlineSpiller.cpp
Warning:line 308, column 63
The left operand of '==' is a garbage value

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name InlineSpiller.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/CodeGen -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/CodeGen -I include -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-10-03-140002-15933-1 -x c++ /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/CodeGen/InlineSpiller.cpp

/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/lib/CodeGen/InlineSpiller.cpp

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

/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/include/llvm/CodeGen/TargetInstrInfo.h

1//===- llvm/CodeGen/TargetInstrInfo.h - Instruction Info --------*- 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 describes the target machine instruction set to the code generator.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CODEGEN_TARGETINSTRINFO_H
14#define LLVM_CODEGEN_TARGETINSTRINFO_H
15
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/DenseMapInfo.h"
19#include "llvm/ADT/None.h"
20#include "llvm/CodeGen/MIRFormatter.h"
21#include "llvm/CodeGen/MachineBasicBlock.h"
22#include "llvm/CodeGen/MachineCombinerPattern.h"
23#include "llvm/CodeGen/MachineFunction.h"
24#include "llvm/CodeGen/MachineInstr.h"
25#include "llvm/CodeGen/MachineInstrBuilder.h"
26#include "llvm/CodeGen/MachineOperand.h"
27#include "llvm/CodeGen/MachineOutliner.h"
28#include "llvm/CodeGen/RegisterClassInfo.h"
29#include "llvm/CodeGen/VirtRegMap.h"
30#include "llvm/MC/MCInstrInfo.h"
31#include "llvm/Support/BranchProbability.h"
32#include "llvm/Support/ErrorHandling.h"
33#include <cassert>
34#include <cstddef>
35#include <cstdint>
36#include <utility>
37#include <vector>
38
39namespace llvm {
40
41class DFAPacketizer;
42class InstrItineraryData;
43class LiveIntervals;
44class LiveVariables;
45class MachineLoop;
46class MachineMemOperand;
47class MachineRegisterInfo;
48class MCAsmInfo;
49class MCInst;
50struct MCSchedModel;
51class Module;
52class ScheduleDAG;
53class ScheduleDAGMI;
54class ScheduleHazardRecognizer;
55class SDNode;
56class SelectionDAG;
57class SMSchedule;
58class SwingSchedulerDAG;
59class RegScavenger;
60class TargetRegisterClass;
61class TargetRegisterInfo;
62class TargetSchedModel;
63class TargetSubtargetInfo;
64
65template <class T> class SmallVectorImpl;
66
67using ParamLoadedValue = std::pair<MachineOperand, DIExpression*>;
68
69struct DestSourcePair {
70 const MachineOperand *Destination;
71 const MachineOperand *Source;
72
73 DestSourcePair(const MachineOperand &Dest, const MachineOperand &Src)
74 : Destination(&Dest), Source(&Src) {}
75};
76
77/// Used to describe a register and immediate addition.
78struct RegImmPair {
79 Register Reg;
80 int64_t Imm;
81
82 RegImmPair(Register Reg, int64_t Imm) : Reg(Reg), Imm(Imm) {}
83};
84
85/// Used to describe addressing mode similar to ExtAddrMode in CodeGenPrepare.
86/// It holds the register values, the scale value and the displacement.
87struct ExtAddrMode {
88 Register BaseReg;
89 Register ScaledReg;
90 int64_t Scale;
91 int64_t Displacement;
92};
93
94//---------------------------------------------------------------------------
95///
96/// TargetInstrInfo - Interface to description of machine instruction set
97///
98class TargetInstrInfo : public MCInstrInfo {
99public:
100 TargetInstrInfo(unsigned CFSetupOpcode = ~0u, unsigned CFDestroyOpcode = ~0u,
101 unsigned CatchRetOpcode = ~0u, unsigned ReturnOpcode = ~0u)
102 : CallFrameSetupOpcode(CFSetupOpcode),
103 CallFrameDestroyOpcode(CFDestroyOpcode), CatchRetOpcode(CatchRetOpcode),
104 ReturnOpcode(ReturnOpcode) {}
105 TargetInstrInfo(const TargetInstrInfo &) = delete;
106 TargetInstrInfo &operator=(const TargetInstrInfo &) = delete;
107 virtual ~TargetInstrInfo();
108
109 static bool isGenericOpcode(unsigned Opc) {
110 return Opc <= TargetOpcode::GENERIC_OP_END;
111 }
112
113 static bool isGenericAtomicRMWOpcode(unsigned Opc) {
114 return Opc >= TargetOpcode::GENERIC_ATOMICRMW_OP_START &&
115 Opc <= TargetOpcode::GENERIC_ATOMICRMW_OP_END;
116 }
117
118 /// Given a machine instruction descriptor, returns the register
119 /// class constraint for OpNum, or NULL.
120 virtual
121 const TargetRegisterClass *getRegClass(const MCInstrDesc &MCID, unsigned OpNum,
122 const TargetRegisterInfo *TRI,
123 const MachineFunction &MF) const;
124
125 /// Return true if the instruction is trivially rematerializable, meaning it
126 /// has no side effects and requires no operands that aren't always available.
127 /// This means the only allowed uses are constants and unallocatable physical
128 /// registers so that the instructions result is independent of the place
129 /// in the function.
130 bool isTriviallyReMaterializable(const MachineInstr &MI) const {
131 return MI.getOpcode() == TargetOpcode::IMPLICIT_DEF ||
132 (MI.getDesc().isRematerializable() &&
133 (isReallyTriviallyReMaterializable(MI) ||
134 isReallyTriviallyReMaterializableGeneric(MI)));
135 }
136
137 /// Given \p MO is a PhysReg use return if it can be ignored for the purpose
138 /// of instruction rematerialization or sinking.
139 virtual bool isIgnorableUse(const MachineOperand &MO) const {
140 return false;
141 }
142
143protected:
144 /// For instructions with opcodes for which the M_REMATERIALIZABLE flag is
145 /// set, this hook lets the target specify whether the instruction is actually
146 /// trivially rematerializable, taking into consideration its operands. This
147 /// predicate must return false if the instruction has any side effects other
148 /// than producing a value, or if it requres any address registers that are
149 /// not always available.
150 /// Requirements must be check as stated in isTriviallyReMaterializable() .
151 virtual bool isReallyTriviallyReMaterializable(const MachineInstr &MI) const {
152 return false;
153 }
154
155 /// This method commutes the operands of the given machine instruction MI.
156 /// The operands to be commuted are specified by their indices OpIdx1 and
157 /// OpIdx2.
158 ///
159 /// If a target has any instructions that are commutable but require
160 /// converting to different instructions or making non-trivial changes
161 /// to commute them, this method can be overloaded to do that.
162 /// The default implementation simply swaps the commutable operands.
163 ///
164 /// If NewMI is false, MI is modified in place and returned; otherwise, a
165 /// new machine instruction is created and returned.
166 ///
167 /// Do not call this method for a non-commutable instruction.
168 /// Even though the instruction is commutable, the method may still
169 /// fail to commute the operands, null pointer is returned in such cases.
170 virtual MachineInstr *commuteInstructionImpl(MachineInstr &MI, bool NewMI,
171 unsigned OpIdx1,
172 unsigned OpIdx2) const;
173
174 /// Assigns the (CommutableOpIdx1, CommutableOpIdx2) pair of commutable
175 /// operand indices to (ResultIdx1, ResultIdx2).
176 /// One or both input values of the pair: (ResultIdx1, ResultIdx2) may be
177 /// predefined to some indices or be undefined (designated by the special
178 /// value 'CommuteAnyOperandIndex').
179 /// The predefined result indices cannot be re-defined.
180 /// The function returns true iff after the result pair redefinition
181 /// the fixed result pair is equal to or equivalent to the source pair of
182 /// indices: (CommutableOpIdx1, CommutableOpIdx2). It is assumed here that
183 /// the pairs (x,y) and (y,x) are equivalent.
184 static bool fixCommutedOpIndices(unsigned &ResultIdx1, unsigned &ResultIdx2,
185 unsigned CommutableOpIdx1,
186 unsigned CommutableOpIdx2);
187
188private:
189 /// For instructions with opcodes for which the M_REMATERIALIZABLE flag is
190 /// set and the target hook isReallyTriviallyReMaterializable returns false,
191 /// this function does target-independent tests to determine if the
192 /// instruction is really trivially rematerializable.
193 bool isReallyTriviallyReMaterializableGeneric(const MachineInstr &MI) const;
194
195public:
196 /// These methods return the opcode of the frame setup/destroy instructions
197 /// if they exist (-1 otherwise). Some targets use pseudo instructions in
198 /// order to abstract away the difference between operating with a frame
199 /// pointer and operating without, through the use of these two instructions.
200 ///
201 unsigned getCallFrameSetupOpcode() const { return CallFrameSetupOpcode; }
202 unsigned getCallFrameDestroyOpcode() const { return CallFrameDestroyOpcode; }
203
204 /// Returns true if the argument is a frame pseudo instruction.
205 bool isFrameInstr(const MachineInstr &I) const {
206 return I.getOpcode() == getCallFrameSetupOpcode() ||
207 I.getOpcode() == getCallFrameDestroyOpcode();
208 }
209
210 /// Returns true if the argument is a frame setup pseudo instruction.
211 bool isFrameSetup(const MachineInstr &I) const {
212 return I.getOpcode() == getCallFrameSetupOpcode();
213 }
214
215 /// Returns size of the frame associated with the given frame instruction.
216 /// For frame setup instruction this is frame that is set up space set up
217 /// after the instruction. For frame destroy instruction this is the frame
218 /// freed by the caller.
219 /// Note, in some cases a call frame (or a part of it) may be prepared prior
220 /// to the frame setup instruction. It occurs in the calls that involve
221 /// inalloca arguments. This function reports only the size of the frame part
222 /// that is set up between the frame setup and destroy pseudo instructions.
223 int64_t getFrameSize(const MachineInstr &I) const {
224 assert(isFrameInstr(I) && "Not a frame instruction")(static_cast <bool> (isFrameInstr(I) && "Not a frame instruction"
) ? void (0) : __assert_fail ("isFrameInstr(I) && \"Not a frame instruction\""
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 224, __extension__
__PRETTY_FUNCTION__))
;
225 assert(I.getOperand(0).getImm() >= 0)(static_cast <bool> (I.getOperand(0).getImm() >= 0) ?
void (0) : __assert_fail ("I.getOperand(0).getImm() >= 0"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 225, __extension__
__PRETTY_FUNCTION__))
;
226 return I.getOperand(0).getImm();
227 }
228
229 /// Returns the total frame size, which is made up of the space set up inside
230 /// the pair of frame start-stop instructions and the space that is set up
231 /// prior to the pair.
232 int64_t getFrameTotalSize(const MachineInstr &I) const {
233 if (isFrameSetup(I)) {
234 assert(I.getOperand(1).getImm() >= 0 &&(static_cast <bool> (I.getOperand(1).getImm() >= 0 &&
"Frame size must not be negative") ? void (0) : __assert_fail
("I.getOperand(1).getImm() >= 0 && \"Frame size must not be negative\""
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 235, __extension__
__PRETTY_FUNCTION__))
235 "Frame size must not be negative")(static_cast <bool> (I.getOperand(1).getImm() >= 0 &&
"Frame size must not be negative") ? void (0) : __assert_fail
("I.getOperand(1).getImm() >= 0 && \"Frame size must not be negative\""
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 235, __extension__
__PRETTY_FUNCTION__))
;
236 return getFrameSize(I) + I.getOperand(1).getImm();
237 }
238 return getFrameSize(I);
239 }
240
241 unsigned getCatchReturnOpcode() const { return CatchRetOpcode; }
242 unsigned getReturnOpcode() const { return ReturnOpcode; }
243
244 /// Returns the actual stack pointer adjustment made by an instruction
245 /// as part of a call sequence. By default, only call frame setup/destroy
246 /// instructions adjust the stack, but targets may want to override this
247 /// to enable more fine-grained adjustment, or adjust by a different value.
248 virtual int getSPAdjust(const MachineInstr &MI) const;
249
250 /// Return true if the instruction is a "coalescable" extension instruction.
251 /// That is, it's like a copy where it's legal for the source to overlap the
252 /// destination. e.g. X86::MOVSX64rr32. If this returns true, then it's
253 /// expected the pre-extension value is available as a subreg of the result
254 /// register. This also returns the sub-register index in SubIdx.
255 virtual bool isCoalescableExtInstr(const MachineInstr &MI, Register &SrcReg,
256 Register &DstReg, unsigned &SubIdx) const {
257 return false;
258 }
259
260 /// If the specified machine instruction is a direct
261 /// load from a stack slot, return the virtual or physical register number of
262 /// the destination along with the FrameIndex of the loaded stack slot. If
263 /// not, return 0. This predicate must return 0 if the instruction has
264 /// any side effects other than loading from the stack slot.
265 virtual unsigned isLoadFromStackSlot(const MachineInstr &MI,
266 int &FrameIndex) const {
267 return 0;
8
Returning without writing to 'FrameIndex'
268 }
269
270 /// Optional extension of isLoadFromStackSlot that returns the number of
271 /// bytes loaded from the stack. This must be implemented if a backend
272 /// supports partial stack slot spills/loads to further disambiguate
273 /// what the load does.
274 virtual unsigned isLoadFromStackSlot(const MachineInstr &MI,
275 int &FrameIndex,
276 unsigned &MemBytes) const {
277 MemBytes = 0;
278 return isLoadFromStackSlot(MI, FrameIndex);
279 }
280
281 /// Check for post-frame ptr elimination stack locations as well.
282 /// This uses a heuristic so it isn't reliable for correctness.
283 virtual unsigned isLoadFromStackSlotPostFE(const MachineInstr &MI,
284 int &FrameIndex) const {
285 return 0;
286 }
287
288 /// If the specified machine instruction has a load from a stack slot,
289 /// return true along with the FrameIndices of the loaded stack slot and the
290 /// machine mem operands containing the reference.
291 /// If not, return false. Unlike isLoadFromStackSlot, this returns true for
292 /// any instructions that loads from the stack. This is just a hint, as some
293 /// cases may be missed.
294 virtual bool hasLoadFromStackSlot(
295 const MachineInstr &MI,
296 SmallVectorImpl<const MachineMemOperand *> &Accesses) const;
297
298 /// If the specified machine instruction is a direct
299 /// store to a stack slot, return the virtual or physical register number of
300 /// the source reg along with the FrameIndex of the loaded stack slot. If
301 /// not, return 0. This predicate must return 0 if the instruction has
302 /// any side effects other than storing to the stack slot.
303 virtual unsigned isStoreToStackSlot(const MachineInstr &MI,
304 int &FrameIndex) const {
305 return 0;
306 }
307
308 /// Optional extension of isStoreToStackSlot that returns the number of
309 /// bytes stored to the stack. This must be implemented if a backend
310 /// supports partial stack slot spills/loads to further disambiguate
311 /// what the store does.
312 virtual unsigned isStoreToStackSlot(const MachineInstr &MI,
313 int &FrameIndex,
314 unsigned &MemBytes) const {
315 MemBytes = 0;
316 return isStoreToStackSlot(MI, FrameIndex);
317 }
318
319 /// Check for post-frame ptr elimination stack locations as well.
320 /// This uses a heuristic, so it isn't reliable for correctness.
321 virtual unsigned isStoreToStackSlotPostFE(const MachineInstr &MI,
322 int &FrameIndex) const {
323 return 0;
324 }
325
326 /// If the specified machine instruction has a store to a stack slot,
327 /// return true along with the FrameIndices of the loaded stack slot and the
328 /// machine mem operands containing the reference.
329 /// If not, return false. Unlike isStoreToStackSlot,
330 /// this returns true for any instructions that stores to the
331 /// stack. This is just a hint, as some cases may be missed.
332 virtual bool hasStoreToStackSlot(
333 const MachineInstr &MI,
334 SmallVectorImpl<const MachineMemOperand *> &Accesses) const;
335
336 /// Return true if the specified machine instruction
337 /// is a copy of one stack slot to another and has no other effect.
338 /// Provide the identity of the two frame indices.
339 virtual bool isStackSlotCopy(const MachineInstr &MI, int &DestFrameIndex,
340 int &SrcFrameIndex) const {
341 return false;
342 }
343
344 /// Compute the size in bytes and offset within a stack slot of a spilled
345 /// register or subregister.
346 ///
347 /// \param [out] Size in bytes of the spilled value.
348 /// \param [out] Offset in bytes within the stack slot.
349 /// \returns true if both Size and Offset are successfully computed.
350 ///
351 /// Not all subregisters have computable spill slots. For example,
352 /// subregisters registers may not be byte-sized, and a pair of discontiguous
353 /// subregisters has no single offset.
354 ///
355 /// Targets with nontrivial bigendian implementations may need to override
356 /// this, particularly to support spilled vector registers.
357 virtual bool getStackSlotRange(const TargetRegisterClass *RC, unsigned SubIdx,
358 unsigned &Size, unsigned &Offset,
359 const MachineFunction &MF) const;
360
361 /// Return true if the given instruction is terminator that is unspillable,
362 /// according to isUnspillableTerminatorImpl.
363 bool isUnspillableTerminator(const MachineInstr *MI) const {
364 return MI->isTerminator() && isUnspillableTerminatorImpl(MI);
365 }
366
367 /// Returns the size in bytes of the specified MachineInstr, or ~0U
368 /// when this function is not implemented by a target.
369 virtual unsigned getInstSizeInBytes(const MachineInstr &MI) const {
370 return ~0U;
371 }
372
373 /// Return true if the instruction is as cheap as a move instruction.
374 ///
375 /// Targets for different archs need to override this, and different
376 /// micro-architectures can also be finely tuned inside.
377 virtual bool isAsCheapAsAMove(const MachineInstr &MI) const {
378 return MI.isAsCheapAsAMove();
379 }
380
381 /// Return true if the instruction should be sunk by MachineSink.
382 ///
383 /// MachineSink determines on its own whether the instruction is safe to sink;
384 /// this gives the target a hook to override the default behavior with regards
385 /// to which instructions should be sunk.
386 virtual bool shouldSink(const MachineInstr &MI) const { return true; }
387
388 /// Return false if the instruction should not be hoisted by MachineLICM.
389 ///
390 /// MachineLICM determines on its own whether the instruction is safe to
391 /// hoist; this gives the target a hook to extend this assessment and prevent
392 /// an instruction being hoisted from a given loop for target specific
393 /// reasons.
394 virtual bool shouldHoist(const MachineInstr &MI,
395 const MachineLoop *FromLoop) const {
396 return true;
397 }
398
399 /// Re-issue the specified 'original' instruction at the
400 /// specific location targeting a new destination register.
401 /// The register in Orig->getOperand(0).getReg() will be substituted by
402 /// DestReg:SubIdx. Any existing subreg index is preserved or composed with
403 /// SubIdx.
404 virtual void reMaterialize(MachineBasicBlock &MBB,
405 MachineBasicBlock::iterator MI, Register DestReg,
406 unsigned SubIdx, const MachineInstr &Orig,
407 const TargetRegisterInfo &TRI) const;
408
409 /// Clones instruction or the whole instruction bundle \p Orig and
410 /// insert into \p MBB before \p InsertBefore. The target may update operands
411 /// that are required to be unique.
412 ///
413 /// \p Orig must not return true for MachineInstr::isNotDuplicable().
414 virtual MachineInstr &duplicate(MachineBasicBlock &MBB,
415 MachineBasicBlock::iterator InsertBefore,
416 const MachineInstr &Orig) const;
417
418 /// This method must be implemented by targets that
419 /// set the M_CONVERTIBLE_TO_3_ADDR flag. When this flag is set, the target
420 /// may be able to convert a two-address instruction into one or more true
421 /// three-address instructions on demand. This allows the X86 target (for
422 /// example) to convert ADD and SHL instructions into LEA instructions if they
423 /// would require register copies due to two-addressness.
424 ///
425 /// This method returns a null pointer if the transformation cannot be
426 /// performed, otherwise it returns the last new instruction.
427 ///
428 /// If \p LIS is not nullptr, the LiveIntervals info should be updated for
429 /// replacing \p MI with new instructions, even though this function does not
430 /// remove MI.
431 virtual MachineInstr *convertToThreeAddress(MachineInstr &MI,
432 LiveVariables *LV,
433 LiveIntervals *LIS) const {
434 return nullptr;
435 }
436
437 // This constant can be used as an input value of operand index passed to
438 // the method findCommutedOpIndices() to tell the method that the
439 // corresponding operand index is not pre-defined and that the method
440 // can pick any commutable operand.
441 static const unsigned CommuteAnyOperandIndex = ~0U;
442
443 /// This method commutes the operands of the given machine instruction MI.
444 ///
445 /// The operands to be commuted are specified by their indices OpIdx1 and
446 /// OpIdx2. OpIdx1 and OpIdx2 arguments may be set to a special value
447 /// 'CommuteAnyOperandIndex', which means that the method is free to choose
448 /// any arbitrarily chosen commutable operand. If both arguments are set to
449 /// 'CommuteAnyOperandIndex' then the method looks for 2 different commutable
450 /// operands; then commutes them if such operands could be found.
451 ///
452 /// If NewMI is false, MI is modified in place and returned; otherwise, a
453 /// new machine instruction is created and returned.
454 ///
455 /// Do not call this method for a non-commutable instruction or
456 /// for non-commuable operands.
457 /// Even though the instruction is commutable, the method may still
458 /// fail to commute the operands, null pointer is returned in such cases.
459 MachineInstr *
460 commuteInstruction(MachineInstr &MI, bool NewMI = false,
461 unsigned OpIdx1 = CommuteAnyOperandIndex,
462 unsigned OpIdx2 = CommuteAnyOperandIndex) const;
463
464 /// Returns true iff the routine could find two commutable operands in the
465 /// given machine instruction.
466 /// The 'SrcOpIdx1' and 'SrcOpIdx2' are INPUT and OUTPUT arguments.
467 /// If any of the INPUT values is set to the special value
468 /// 'CommuteAnyOperandIndex' then the method arbitrarily picks a commutable
469 /// operand, then returns its index in the corresponding argument.
470 /// If both of INPUT values are set to 'CommuteAnyOperandIndex' then method
471 /// looks for 2 commutable operands.
472 /// If INPUT values refer to some operands of MI, then the method simply
473 /// returns true if the corresponding operands are commutable and returns
474 /// false otherwise.
475 ///
476 /// For example, calling this method this way:
477 /// unsigned Op1 = 1, Op2 = CommuteAnyOperandIndex;
478 /// findCommutedOpIndices(MI, Op1, Op2);
479 /// can be interpreted as a query asking to find an operand that would be
480 /// commutable with the operand#1.
481 virtual bool findCommutedOpIndices(const MachineInstr &MI,
482 unsigned &SrcOpIdx1,
483 unsigned &SrcOpIdx2) const;
484
485 /// Returns true if the target has a preference on the operands order of
486 /// the given machine instruction. And specify if \p Commute is required to
487 /// get the desired operands order.
488 virtual bool hasCommutePreference(MachineInstr &MI, bool &Commute) const {
489 return false;
490 }
491
492 /// A pair composed of a register and a sub-register index.
493 /// Used to give some type checking when modeling Reg:SubReg.
494 struct RegSubRegPair {
495 Register Reg;
496 unsigned SubReg;
497
498 RegSubRegPair(Register Reg = Register(), unsigned SubReg = 0)
499 : Reg(Reg), SubReg(SubReg) {}
500
501 bool operator==(const RegSubRegPair& P) const {
502 return Reg == P.Reg && SubReg == P.SubReg;
503 }
504 bool operator!=(const RegSubRegPair& P) const {
505 return !(*this == P);
506 }
507 };
508
509 /// A pair composed of a pair of a register and a sub-register index,
510 /// and another sub-register index.
511 /// Used to give some type checking when modeling Reg:SubReg1, SubReg2.
512 struct RegSubRegPairAndIdx : RegSubRegPair {
513 unsigned SubIdx;
514
515 RegSubRegPairAndIdx(Register Reg = Register(), unsigned SubReg = 0,
516 unsigned SubIdx = 0)
517 : RegSubRegPair(Reg, SubReg), SubIdx(SubIdx) {}
518 };
519
520 /// Build the equivalent inputs of a REG_SEQUENCE for the given \p MI
521 /// and \p DefIdx.
522 /// \p [out] InputRegs of the equivalent REG_SEQUENCE. Each element of
523 /// the list is modeled as <Reg:SubReg, SubIdx>. Operands with the undef
524 /// flag are not added to this list.
525 /// E.g., REG_SEQUENCE %1:sub1, sub0, %2, sub1 would produce
526 /// two elements:
527 /// - %1:sub1, sub0
528 /// - %2<:0>, sub1
529 ///
530 /// \returns true if it is possible to build such an input sequence
531 /// with the pair \p MI, \p DefIdx. False otherwise.
532 ///
533 /// \pre MI.isRegSequence() or MI.isRegSequenceLike().
534 ///
535 /// \note The generic implementation does not provide any support for
536 /// MI.isRegSequenceLike(). In other words, one has to override
537 /// getRegSequenceLikeInputs for target specific instructions.
538 bool
539 getRegSequenceInputs(const MachineInstr &MI, unsigned DefIdx,
540 SmallVectorImpl<RegSubRegPairAndIdx> &InputRegs) const;
541
542 /// Build the equivalent inputs of a EXTRACT_SUBREG for the given \p MI
543 /// and \p DefIdx.
544 /// \p [out] InputReg of the equivalent EXTRACT_SUBREG.
545 /// E.g., EXTRACT_SUBREG %1:sub1, sub0, sub1 would produce:
546 /// - %1:sub1, sub0
547 ///
548 /// \returns true if it is possible to build such an input sequence
549 /// with the pair \p MI, \p DefIdx and the operand has no undef flag set.
550 /// False otherwise.
551 ///
552 /// \pre MI.isExtractSubreg() or MI.isExtractSubregLike().
553 ///
554 /// \note The generic implementation does not provide any support for
555 /// MI.isExtractSubregLike(). In other words, one has to override
556 /// getExtractSubregLikeInputs for target specific instructions.
557 bool getExtractSubregInputs(const MachineInstr &MI, unsigned DefIdx,
558 RegSubRegPairAndIdx &InputReg) const;
559
560 /// Build the equivalent inputs of a INSERT_SUBREG for the given \p MI
561 /// and \p DefIdx.
562 /// \p [out] BaseReg and \p [out] InsertedReg contain
563 /// the equivalent inputs of INSERT_SUBREG.
564 /// E.g., INSERT_SUBREG %0:sub0, %1:sub1, sub3 would produce:
565 /// - BaseReg: %0:sub0
566 /// - InsertedReg: %1:sub1, sub3
567 ///
568 /// \returns true if it is possible to build such an input sequence
569 /// with the pair \p MI, \p DefIdx and the operand has no undef flag set.
570 /// False otherwise.
571 ///
572 /// \pre MI.isInsertSubreg() or MI.isInsertSubregLike().
573 ///
574 /// \note The generic implementation does not provide any support for
575 /// MI.isInsertSubregLike(). In other words, one has to override
576 /// getInsertSubregLikeInputs for target specific instructions.
577 bool getInsertSubregInputs(const MachineInstr &MI, unsigned DefIdx,
578 RegSubRegPair &BaseReg,
579 RegSubRegPairAndIdx &InsertedReg) const;
580
581 /// Return true if two machine instructions would produce identical values.
582 /// By default, this is only true when the two instructions
583 /// are deemed identical except for defs. If this function is called when the
584 /// IR is still in SSA form, the caller can pass the MachineRegisterInfo for
585 /// aggressive checks.
586 virtual bool produceSameValue(const MachineInstr &MI0,
587 const MachineInstr &MI1,
588 const MachineRegisterInfo *MRI = nullptr) const;
589
590 /// \returns true if a branch from an instruction with opcode \p BranchOpc
591 /// bytes is capable of jumping to a position \p BrOffset bytes away.
592 virtual bool isBranchOffsetInRange(unsigned BranchOpc,
593 int64_t BrOffset) const {
594 llvm_unreachable("target did not implement")::llvm::llvm_unreachable_internal("target did not implement",
"llvm/include/llvm/CodeGen/TargetInstrInfo.h", 594)
;
595 }
596
597 /// \returns The block that branch instruction \p MI jumps to.
598 virtual MachineBasicBlock *getBranchDestBlock(const MachineInstr &MI) const {
599 llvm_unreachable("target did not implement")::llvm::llvm_unreachable_internal("target did not implement",
"llvm/include/llvm/CodeGen/TargetInstrInfo.h", 599)
;
600 }
601
602 /// Insert an unconditional indirect branch at the end of \p MBB to \p
603 /// NewDestBB. Optionally, insert the clobbered register restoring in \p
604 /// RestoreBB. \p BrOffset indicates the offset of \p NewDestBB relative to
605 /// the offset of the position to insert the new branch.
606 virtual void insertIndirectBranch(MachineBasicBlock &MBB,
607 MachineBasicBlock &NewDestBB,
608 MachineBasicBlock &RestoreBB,
609 const DebugLoc &DL, int64_t BrOffset = 0,
610 RegScavenger *RS = nullptr) const {
611 llvm_unreachable("target did not implement")::llvm::llvm_unreachable_internal("target did not implement",
"llvm/include/llvm/CodeGen/TargetInstrInfo.h", 611)
;
612 }
613
614 /// Analyze the branching code at the end of MBB, returning
615 /// true if it cannot be understood (e.g. it's a switch dispatch or isn't
616 /// implemented for a target). Upon success, this returns false and returns
617 /// with the following information in various cases:
618 ///
619 /// 1. If this block ends with no branches (it just falls through to its succ)
620 /// just return false, leaving TBB/FBB null.
621 /// 2. If this block ends with only an unconditional branch, it sets TBB to be
622 /// the destination block.
623 /// 3. If this block ends with a conditional branch and it falls through to a
624 /// successor block, it sets TBB to be the branch destination block and a
625 /// list of operands that evaluate the condition. These operands can be
626 /// passed to other TargetInstrInfo methods to create new branches.
627 /// 4. If this block ends with a conditional branch followed by an
628 /// unconditional branch, it returns the 'true' destination in TBB, the
629 /// 'false' destination in FBB, and a list of operands that evaluate the
630 /// condition. These operands can be passed to other TargetInstrInfo
631 /// methods to create new branches.
632 ///
633 /// Note that removeBranch and insertBranch must be implemented to support
634 /// cases where this method returns success.
635 ///
636 /// If AllowModify is true, then this routine is allowed to modify the basic
637 /// block (e.g. delete instructions after the unconditional branch).
638 ///
639 /// The CFG information in MBB.Predecessors and MBB.Successors must be valid
640 /// before calling this function.
641 virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
642 MachineBasicBlock *&FBB,
643 SmallVectorImpl<MachineOperand> &Cond,
644 bool AllowModify = false) const {
645 return true;
646 }
647
648 /// Represents a predicate at the MachineFunction level. The control flow a
649 /// MachineBranchPredicate represents is:
650 ///
651 /// Reg = LHS `Predicate` RHS == ConditionDef
652 /// if Reg then goto TrueDest else goto FalseDest
653 ///
654 struct MachineBranchPredicate {
655 enum ComparePredicate {
656 PRED_EQ, // True if two values are equal
657 PRED_NE, // True if two values are not equal
658 PRED_INVALID // Sentinel value
659 };
660
661 ComparePredicate Predicate = PRED_INVALID;
662 MachineOperand LHS = MachineOperand::CreateImm(0);
663 MachineOperand RHS = MachineOperand::CreateImm(0);
664 MachineBasicBlock *TrueDest = nullptr;
665 MachineBasicBlock *FalseDest = nullptr;
666 MachineInstr *ConditionDef = nullptr;
667
668 /// SingleUseCondition is true if ConditionDef is dead except for the
669 /// branch(es) at the end of the basic block.
670 ///
671 bool SingleUseCondition = false;
672
673 explicit MachineBranchPredicate() = default;
674 };
675
676 /// Analyze the branching code at the end of MBB and parse it into the
677 /// MachineBranchPredicate structure if possible. Returns false on success
678 /// and true on failure.
679 ///
680 /// If AllowModify is true, then this routine is allowed to modify the basic
681 /// block (e.g. delete instructions after the unconditional branch).
682 ///
683 virtual bool analyzeBranchPredicate(MachineBasicBlock &MBB,
684 MachineBranchPredicate &MBP,
685 bool AllowModify = false) const {
686 return true;
687 }
688
689 /// Remove the branching code at the end of the specific MBB.
690 /// This is only invoked in cases where analyzeBranch returns success. It
691 /// returns the number of instructions that were removed.
692 /// If \p BytesRemoved is non-null, report the change in code size from the
693 /// removed instructions.
694 virtual unsigned removeBranch(MachineBasicBlock &MBB,
695 int *BytesRemoved = nullptr) const {
696 llvm_unreachable("Target didn't implement TargetInstrInfo::removeBranch!")::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::removeBranch!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 696)
;
697 }
698
699 /// Insert branch code into the end of the specified MachineBasicBlock. The
700 /// operands to this method are the same as those returned by analyzeBranch.
701 /// This is only invoked in cases where analyzeBranch returns success. It
702 /// returns the number of instructions inserted. If \p BytesAdded is non-null,
703 /// report the change in code size from the added instructions.
704 ///
705 /// It is also invoked by tail merging to add unconditional branches in
706 /// cases where analyzeBranch doesn't apply because there was no original
707 /// branch to analyze. At least this much must be implemented, else tail
708 /// merging needs to be disabled.
709 ///
710 /// The CFG information in MBB.Predecessors and MBB.Successors must be valid
711 /// before calling this function.
712 virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
713 MachineBasicBlock *FBB,
714 ArrayRef<MachineOperand> Cond,
715 const DebugLoc &DL,
716 int *BytesAdded = nullptr) const {
717 llvm_unreachable("Target didn't implement TargetInstrInfo::insertBranch!")::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::insertBranch!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 717)
;
718 }
719
720 unsigned insertUnconditionalBranch(MachineBasicBlock &MBB,
721 MachineBasicBlock *DestBB,
722 const DebugLoc &DL,
723 int *BytesAdded = nullptr) const {
724 return insertBranch(MBB, DestBB, nullptr, ArrayRef<MachineOperand>(), DL,
725 BytesAdded);
726 }
727
728 /// Object returned by analyzeLoopForPipelining. Allows software pipelining
729 /// implementations to query attributes of the loop being pipelined and to
730 /// apply target-specific updates to the loop once pipelining is complete.
731 class PipelinerLoopInfo {
732 public:
733 virtual ~PipelinerLoopInfo();
734 /// Return true if the given instruction should not be pipelined and should
735 /// be ignored. An example could be a loop comparison, or induction variable
736 /// update with no users being pipelined.
737 virtual bool shouldIgnoreForPipelining(const MachineInstr *MI) const = 0;
738
739 /// Return true if the proposed schedule should used. Otherwise return
740 /// false to not pipeline the loop. This function should be used to ensure
741 /// that pipelined loops meet target-specific quality heuristics.
742 virtual bool shouldUseSchedule(SwingSchedulerDAG &SSD, SMSchedule &SMS) {
743 return true;
744 }
745
746 /// Create a condition to determine if the trip count of the loop is greater
747 /// than TC, where TC is always one more than for the previous prologue or
748 /// 0 if this is being called for the outermost prologue.
749 ///
750 /// If the trip count is statically known to be greater than TC, return
751 /// true. If the trip count is statically known to be not greater than TC,
752 /// return false. Otherwise return nullopt and fill out Cond with the test
753 /// condition.
754 ///
755 /// Note: This hook is guaranteed to be called from the innermost to the
756 /// outermost prologue of the loop being software pipelined.
757 virtual Optional<bool>
758 createTripCountGreaterCondition(int TC, MachineBasicBlock &MBB,
759 SmallVectorImpl<MachineOperand> &Cond) = 0;
760
761 /// Modify the loop such that the trip count is
762 /// OriginalTC + TripCountAdjust.
763 virtual void adjustTripCount(int TripCountAdjust) = 0;
764
765 /// Called when the loop's preheader has been modified to NewPreheader.
766 virtual void setPreheader(MachineBasicBlock *NewPreheader) = 0;
767
768 /// Called when the loop is being removed. Any instructions in the preheader
769 /// should be removed.
770 ///
771 /// Once this function is called, no other functions on this object are
772 /// valid; the loop has been removed.
773 virtual void disposed() = 0;
774 };
775
776 /// Analyze loop L, which must be a single-basic-block loop, and if the
777 /// conditions can be understood enough produce a PipelinerLoopInfo object.
778 virtual std::unique_ptr<PipelinerLoopInfo>
779 analyzeLoopForPipelining(MachineBasicBlock *LoopBB) const {
780 return nullptr;
781 }
782
783 /// Analyze the loop code, return true if it cannot be understood. Upon
784 /// success, this function returns false and returns information about the
785 /// induction variable and compare instruction used at the end.
786 virtual bool analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst,
787 MachineInstr *&CmpInst) const {
788 return true;
789 }
790
791 /// Generate code to reduce the loop iteration by one and check if the loop
792 /// is finished. Return the value/register of the new loop count. We need
793 /// this function when peeling off one or more iterations of a loop. This
794 /// function assumes the nth iteration is peeled first.
795 virtual unsigned reduceLoopCount(MachineBasicBlock &MBB,
796 MachineBasicBlock &PreHeader,
797 MachineInstr *IndVar, MachineInstr &Cmp,
798 SmallVectorImpl<MachineOperand> &Cond,
799 SmallVectorImpl<MachineInstr *> &PrevInsts,
800 unsigned Iter, unsigned MaxIter) const {
801 llvm_unreachable("Target didn't implement ReduceLoopCount")::llvm::llvm_unreachable_internal("Target didn't implement ReduceLoopCount"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 801)
;
802 }
803
804 /// Delete the instruction OldInst and everything after it, replacing it with
805 /// an unconditional branch to NewDest. This is used by the tail merging pass.
806 virtual void ReplaceTailWithBranchTo(MachineBasicBlock::iterator Tail,
807 MachineBasicBlock *NewDest) const;
808
809 /// Return true if it's legal to split the given basic
810 /// block at the specified instruction (i.e. instruction would be the start
811 /// of a new basic block).
812 virtual bool isLegalToSplitMBBAt(MachineBasicBlock &MBB,
813 MachineBasicBlock::iterator MBBI) const {
814 return true;
815 }
816
817 /// Return true if it's profitable to predicate
818 /// instructions with accumulated instruction latency of "NumCycles"
819 /// of the specified basic block, where the probability of the instructions
820 /// being executed is given by Probability, and Confidence is a measure
821 /// of our confidence that it will be properly predicted.
822 virtual bool isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumCycles,
823 unsigned ExtraPredCycles,
824 BranchProbability Probability) const {
825 return false;
826 }
827
828 /// Second variant of isProfitableToIfCvt. This one
829 /// checks for the case where two basic blocks from true and false path
830 /// of a if-then-else (diamond) are predicated on mutually exclusive
831 /// predicates, where the probability of the true path being taken is given
832 /// by Probability, and Confidence is a measure of our confidence that it
833 /// will be properly predicted.
834 virtual bool isProfitableToIfCvt(MachineBasicBlock &TMBB, unsigned NumTCycles,
835 unsigned ExtraTCycles,
836 MachineBasicBlock &FMBB, unsigned NumFCycles,
837 unsigned ExtraFCycles,
838 BranchProbability Probability) const {
839 return false;
840 }
841
842 /// Return true if it's profitable for if-converter to duplicate instructions
843 /// of specified accumulated instruction latencies in the specified MBB to
844 /// enable if-conversion.
845 /// The probability of the instructions being executed is given by
846 /// Probability, and Confidence is a measure of our confidence that it
847 /// will be properly predicted.
848 virtual bool isProfitableToDupForIfCvt(MachineBasicBlock &MBB,
849 unsigned NumCycles,
850 BranchProbability Probability) const {
851 return false;
852 }
853
854 /// Return the increase in code size needed to predicate a contiguous run of
855 /// NumInsts instructions.
856 virtual unsigned extraSizeToPredicateInstructions(const MachineFunction &MF,
857 unsigned NumInsts) const {
858 return 0;
859 }
860
861 /// Return an estimate for the code size reduction (in bytes) which will be
862 /// caused by removing the given branch instruction during if-conversion.
863 virtual unsigned predictBranchSizeForIfCvt(MachineInstr &MI) const {
864 return getInstSizeInBytes(MI);
865 }
866
867 /// Return true if it's profitable to unpredicate
868 /// one side of a 'diamond', i.e. two sides of if-else predicated on mutually
869 /// exclusive predicates.
870 /// e.g.
871 /// subeq r0, r1, #1
872 /// addne r0, r1, #1
873 /// =>
874 /// sub r0, r1, #1
875 /// addne r0, r1, #1
876 ///
877 /// This may be profitable is conditional instructions are always executed.
878 virtual bool isProfitableToUnpredicate(MachineBasicBlock &TMBB,
879 MachineBasicBlock &FMBB) const {
880 return false;
881 }
882
883 /// Return true if it is possible to insert a select
884 /// instruction that chooses between TrueReg and FalseReg based on the
885 /// condition code in Cond.
886 ///
887 /// When successful, also return the latency in cycles from TrueReg,
888 /// FalseReg, and Cond to the destination register. In most cases, a select
889 /// instruction will be 1 cycle, so CondCycles = TrueCycles = FalseCycles = 1
890 ///
891 /// Some x86 implementations have 2-cycle cmov instructions.
892 ///
893 /// @param MBB Block where select instruction would be inserted.
894 /// @param Cond Condition returned by analyzeBranch.
895 /// @param DstReg Virtual dest register that the result should write to.
896 /// @param TrueReg Virtual register to select when Cond is true.
897 /// @param FalseReg Virtual register to select when Cond is false.
898 /// @param CondCycles Latency from Cond+Branch to select output.
899 /// @param TrueCycles Latency from TrueReg to select output.
900 /// @param FalseCycles Latency from FalseReg to select output.
901 virtual bool canInsertSelect(const MachineBasicBlock &MBB,
902 ArrayRef<MachineOperand> Cond, Register DstReg,
903 Register TrueReg, Register FalseReg,
904 int &CondCycles, int &TrueCycles,
905 int &FalseCycles) const {
906 return false;
907 }
908
909 /// Insert a select instruction into MBB before I that will copy TrueReg to
910 /// DstReg when Cond is true, and FalseReg to DstReg when Cond is false.
911 ///
912 /// This function can only be called after canInsertSelect() returned true.
913 /// The condition in Cond comes from analyzeBranch, and it can be assumed
914 /// that the same flags or registers required by Cond are available at the
915 /// insertion point.
916 ///
917 /// @param MBB Block where select instruction should be inserted.
918 /// @param I Insertion point.
919 /// @param DL Source location for debugging.
920 /// @param DstReg Virtual register to be defined by select instruction.
921 /// @param Cond Condition as computed by analyzeBranch.
922 /// @param TrueReg Virtual register to copy when Cond is true.
923 /// @param FalseReg Virtual register to copy when Cons is false.
924 virtual void insertSelect(MachineBasicBlock &MBB,
925 MachineBasicBlock::iterator I, const DebugLoc &DL,
926 Register DstReg, ArrayRef<MachineOperand> Cond,
927 Register TrueReg, Register FalseReg) const {
928 llvm_unreachable("Target didn't implement TargetInstrInfo::insertSelect!")::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::insertSelect!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 928)
;
929 }
930
931 /// Analyze the given select instruction, returning true if
932 /// it cannot be understood. It is assumed that MI->isSelect() is true.
933 ///
934 /// When successful, return the controlling condition and the operands that
935 /// determine the true and false result values.
936 ///
937 /// Result = SELECT Cond, TrueOp, FalseOp
938 ///
939 /// Some targets can optimize select instructions, for example by predicating
940 /// the instruction defining one of the operands. Such targets should set
941 /// Optimizable.
942 ///
943 /// @param MI Select instruction to analyze.
944 /// @param Cond Condition controlling the select.
945 /// @param TrueOp Operand number of the value selected when Cond is true.
946 /// @param FalseOp Operand number of the value selected when Cond is false.
947 /// @param Optimizable Returned as true if MI is optimizable.
948 /// @returns False on success.
949 virtual bool analyzeSelect(const MachineInstr &MI,
950 SmallVectorImpl<MachineOperand> &Cond,
951 unsigned &TrueOp, unsigned &FalseOp,
952 bool &Optimizable) const {
953 assert(MI.getDesc().isSelect() && "MI must be a select instruction")(static_cast <bool> (MI.getDesc().isSelect() &&
"MI must be a select instruction") ? void (0) : __assert_fail
("MI.getDesc().isSelect() && \"MI must be a select instruction\""
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 953, __extension__
__PRETTY_FUNCTION__))
;
954 return true;
955 }
956
957 /// Given a select instruction that was understood by
958 /// analyzeSelect and returned Optimizable = true, attempt to optimize MI by
959 /// merging it with one of its operands. Returns NULL on failure.
960 ///
961 /// When successful, returns the new select instruction. The client is
962 /// responsible for deleting MI.
963 ///
964 /// If both sides of the select can be optimized, PreferFalse is used to pick
965 /// a side.
966 ///
967 /// @param MI Optimizable select instruction.
968 /// @param NewMIs Set that record all MIs in the basic block up to \p
969 /// MI. Has to be updated with any newly created MI or deleted ones.
970 /// @param PreferFalse Try to optimize FalseOp instead of TrueOp.
971 /// @returns Optimized instruction or NULL.
972 virtual MachineInstr *optimizeSelect(MachineInstr &MI,
973 SmallPtrSetImpl<MachineInstr *> &NewMIs,
974 bool PreferFalse = false) const {
975 // This function must be implemented if Optimizable is ever set.
976 llvm_unreachable("Target must implement TargetInstrInfo::optimizeSelect!")::llvm::llvm_unreachable_internal("Target must implement TargetInstrInfo::optimizeSelect!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 976)
;
977 }
978
979 /// Emit instructions to copy a pair of physical registers.
980 ///
981 /// This function should support copies within any legal register class as
982 /// well as any cross-class copies created during instruction selection.
983 ///
984 /// The source and destination registers may overlap, which may require a
985 /// careful implementation when multiple copy instructions are required for
986 /// large registers. See for example the ARM target.
987 virtual void copyPhysReg(MachineBasicBlock &MBB,
988 MachineBasicBlock::iterator MI, const DebugLoc &DL,
989 MCRegister DestReg, MCRegister SrcReg,
990 bool KillSrc) const {
991 llvm_unreachable("Target didn't implement TargetInstrInfo::copyPhysReg!")::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::copyPhysReg!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 991)
;
992 }
993
994 /// Allow targets to tell MachineVerifier whether a specific register
995 /// MachineOperand can be used as part of PC-relative addressing.
996 /// PC-relative addressing modes in many CISC architectures contain
997 /// (non-PC) registers as offsets or scaling values, which inherently
998 /// tags the corresponding MachineOperand with OPERAND_PCREL.
999 ///
1000 /// @param MO The MachineOperand in question. MO.isReg() should always
1001 /// be true.
1002 /// @return Whether this operand is allowed to be used PC-relatively.
1003 virtual bool isPCRelRegisterOperandLegal(const MachineOperand &MO) const {
1004 return false;
1005 }
1006
1007protected:
1008 /// Target-dependent implementation for IsCopyInstr.
1009 /// If the specific machine instruction is a instruction that moves/copies
1010 /// value from one register to another register return destination and source
1011 /// registers as machine operands.
1012 virtual Optional<DestSourcePair>
1013 isCopyInstrImpl(const MachineInstr &MI) const {
1014 return None;
1015 }
1016
1017 /// Return true if the given terminator MI is not expected to spill. This
1018 /// sets the live interval as not spillable and adjusts phi node lowering to
1019 /// not introduce copies after the terminator. Use with care, these are
1020 /// currently used for hardware loop intrinsics in very controlled situations,
1021 /// created prior to registry allocation in loops that only have single phi
1022 /// users for the terminators value. They may run out of registers if not used
1023 /// carefully.
1024 virtual bool isUnspillableTerminatorImpl(const MachineInstr *MI) const {
1025 return false;
1026 }
1027
1028public:
1029 /// If the specific machine instruction is a instruction that moves/copies
1030 /// value from one register to another register return destination and source
1031 /// registers as machine operands.
1032 /// For COPY-instruction the method naturally returns destination and source
1033 /// registers as machine operands, for all other instructions the method calls
1034 /// target-dependent implementation.
1035 Optional<DestSourcePair> isCopyInstr(const MachineInstr &MI) const {
1036 if (MI.isCopy()) {
1037 return DestSourcePair{MI.getOperand(0), MI.getOperand(1)};
1038 }
1039 return isCopyInstrImpl(MI);
1040 }
1041
1042 /// If the specific machine instruction is an instruction that adds an
1043 /// immediate value and a physical register, and stores the result in
1044 /// the given physical register \c Reg, return a pair of the source
1045 /// register and the offset which has been added.
1046 virtual Optional<RegImmPair> isAddImmediate(const MachineInstr &MI,
1047 Register Reg) const {
1048 return None;
1049 }
1050
1051 /// Returns true if MI is an instruction that defines Reg to have a constant
1052 /// value and the value is recorded in ImmVal. The ImmVal is a result that
1053 /// should be interpreted as modulo size of Reg.
1054 virtual bool getConstValDefinedInReg(const MachineInstr &MI,
1055 const Register Reg,
1056 int64_t &ImmVal) const {
1057 return false;
1058 }
1059
1060 /// Store the specified register of the given register class to the specified
1061 /// stack frame index. The store instruction is to be added to the given
1062 /// machine basic block before the specified machine instruction. If isKill
1063 /// is true, the register operand is the last use and must be marked kill.
1064 virtual void storeRegToStackSlot(MachineBasicBlock &MBB,
1065 MachineBasicBlock::iterator MI,
1066 Register SrcReg, bool isKill, int FrameIndex,
1067 const TargetRegisterClass *RC,
1068 const TargetRegisterInfo *TRI) const {
1069 llvm_unreachable("Target didn't implement "::llvm::llvm_unreachable_internal("Target didn't implement " "TargetInstrInfo::storeRegToStackSlot!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1070)
1070 "TargetInstrInfo::storeRegToStackSlot!")::llvm::llvm_unreachable_internal("Target didn't implement " "TargetInstrInfo::storeRegToStackSlot!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1070)
;
1071 }
1072
1073 /// Load the specified register of the given register class from the specified
1074 /// stack frame index. The load instruction is to be added to the given
1075 /// machine basic block before the specified machine instruction.
1076 virtual void loadRegFromStackSlot(MachineBasicBlock &MBB,
1077 MachineBasicBlock::iterator MI,
1078 Register DestReg, int FrameIndex,
1079 const TargetRegisterClass *RC,
1080 const TargetRegisterInfo *TRI) const {
1081 llvm_unreachable("Target didn't implement "::llvm::llvm_unreachable_internal("Target didn't implement " "TargetInstrInfo::loadRegFromStackSlot!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1082)
1082 "TargetInstrInfo::loadRegFromStackSlot!")::llvm::llvm_unreachable_internal("Target didn't implement " "TargetInstrInfo::loadRegFromStackSlot!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1082)
;
1083 }
1084
1085 /// This function is called for all pseudo instructions
1086 /// that remain after register allocation. Many pseudo instructions are
1087 /// created to help register allocation. This is the place to convert them
1088 /// into real instructions. The target can edit MI in place, or it can insert
1089 /// new instructions and erase MI. The function should return true if
1090 /// anything was changed.
1091 virtual bool expandPostRAPseudo(MachineInstr &MI) const { return false; }
1092
1093 /// Check whether the target can fold a load that feeds a subreg operand
1094 /// (or a subreg operand that feeds a store).
1095 /// For example, X86 may want to return true if it can fold
1096 /// movl (%esp), %eax
1097 /// subb, %al, ...
1098 /// Into:
1099 /// subb (%esp), ...
1100 ///
1101 /// Ideally, we'd like the target implementation of foldMemoryOperand() to
1102 /// reject subregs - but since this behavior used to be enforced in the
1103 /// target-independent code, moving this responsibility to the targets
1104 /// has the potential of causing nasty silent breakage in out-of-tree targets.
1105 virtual bool isSubregFoldable() const { return false; }
1106
1107 /// For a patchpoint, stackmap, or statepoint intrinsic, return the range of
1108 /// operands which can't be folded into stack references. Operands outside
1109 /// of the range are most likely foldable but it is not guaranteed.
1110 /// These instructions are unique in that stack references for some operands
1111 /// have the same execution cost (e.g. none) as the unfolded register forms.
1112 /// The ranged return is guaranteed to include all operands which can't be
1113 /// folded at zero cost.
1114 virtual std::pair<unsigned, unsigned>
1115 getPatchpointUnfoldableRange(const MachineInstr &MI) const;
1116
1117 /// Attempt to fold a load or store of the specified stack
1118 /// slot into the specified machine instruction for the specified operand(s).
1119 /// If this is possible, a new instruction is returned with the specified
1120 /// operand folded, otherwise NULL is returned.
1121 /// The new instruction is inserted before MI, and the client is responsible
1122 /// for removing the old instruction.
1123 /// If VRM is passed, the assigned physregs can be inspected by target to
1124 /// decide on using an opcode (note that those assignments can still change).
1125 MachineInstr *foldMemoryOperand(MachineInstr &MI, ArrayRef<unsigned> Ops,
1126 int FI,
1127 LiveIntervals *LIS = nullptr,
1128 VirtRegMap *VRM = nullptr) const;
1129
1130 /// Same as the previous version except it allows folding of any load and
1131 /// store from / to any address, not just from a specific stack slot.
1132 MachineInstr *foldMemoryOperand(MachineInstr &MI, ArrayRef<unsigned> Ops,
1133 MachineInstr &LoadMI,
1134 LiveIntervals *LIS = nullptr) const;
1135
1136 /// Return true when there is potentially a faster code sequence
1137 /// for an instruction chain ending in \p Root. All potential patterns are
1138 /// returned in the \p Pattern vector. Pattern should be sorted in priority
1139 /// order since the pattern evaluator stops checking as soon as it finds a
1140 /// faster sequence.
1141 /// \param Root - Instruction that could be combined with one of its operands
1142 /// \param Patterns - Vector of possible combination patterns
1143 virtual bool
1144 getMachineCombinerPatterns(MachineInstr &Root,
1145 SmallVectorImpl<MachineCombinerPattern> &Patterns,
1146 bool DoRegPressureReduce) const;
1147
1148 /// Return true if target supports reassociation of instructions in machine
1149 /// combiner pass to reduce register pressure for a given BB.
1150 virtual bool
1151 shouldReduceRegisterPressure(MachineBasicBlock *MBB,
1152 RegisterClassInfo *RegClassInfo) const {
1153 return false;
1154 }
1155
1156 /// Fix up the placeholder we may add in genAlternativeCodeSequence().
1157 virtual void
1158 finalizeInsInstrs(MachineInstr &Root, MachineCombinerPattern &P,
1159 SmallVectorImpl<MachineInstr *> &InsInstrs) const {}
1160
1161 /// Return true when a code sequence can improve throughput. It
1162 /// should be called only for instructions in loops.
1163 /// \param Pattern - combiner pattern
1164 virtual bool isThroughputPattern(MachineCombinerPattern Pattern) const;
1165
1166 /// Return true if the input \P Inst is part of a chain of dependent ops
1167 /// that are suitable for reassociation, otherwise return false.
1168 /// If the instruction's operands must be commuted to have a previous
1169 /// instruction of the same type define the first source operand, \P Commuted
1170 /// will be set to true.
1171 bool isReassociationCandidate(const MachineInstr &Inst, bool &Commuted) const;
1172
1173 /// Return true when \P Inst is both associative and commutative.
1174 virtual bool isAssociativeAndCommutative(const MachineInstr &Inst) const {
1175 return false;
1176 }
1177
1178 /// Return true when \P Inst has reassociable operands in the same \P MBB.
1179 virtual bool hasReassociableOperands(const MachineInstr &Inst,
1180 const MachineBasicBlock *MBB) const;
1181
1182 /// Return true when \P Inst has reassociable sibling.
1183 bool hasReassociableSibling(const MachineInstr &Inst, bool &Commuted) const;
1184
1185 /// When getMachineCombinerPatterns() finds patterns, this function generates
1186 /// the instructions that could replace the original code sequence. The client
1187 /// has to decide whether the actual replacement is beneficial or not.
1188 /// \param Root - Instruction that could be combined with one of its operands
1189 /// \param Pattern - Combination pattern for Root
1190 /// \param InsInstrs - Vector of new instructions that implement P
1191 /// \param DelInstrs - Old instructions, including Root, that could be
1192 /// replaced by InsInstr
1193 /// \param InstIdxForVirtReg - map of virtual register to instruction in
1194 /// InsInstr that defines it
1195 virtual void genAlternativeCodeSequence(
1196 MachineInstr &Root, MachineCombinerPattern Pattern,
1197 SmallVectorImpl<MachineInstr *> &InsInstrs,
1198 SmallVectorImpl<MachineInstr *> &DelInstrs,
1199 DenseMap<unsigned, unsigned> &InstIdxForVirtReg) const;
1200
1201 /// Attempt to reassociate \P Root and \P Prev according to \P Pattern to
1202 /// reduce critical path length.
1203 void reassociateOps(MachineInstr &Root, MachineInstr &Prev,
1204 MachineCombinerPattern Pattern,
1205 SmallVectorImpl<MachineInstr *> &InsInstrs,
1206 SmallVectorImpl<MachineInstr *> &DelInstrs,
1207 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg) const;
1208
1209 /// The limit on resource length extension we accept in MachineCombiner Pass.
1210 virtual int getExtendResourceLenLimit() const { return 0; }
1211
1212 /// This is an architecture-specific helper function of reassociateOps.
1213 /// Set special operand attributes for new instructions after reassociation.
1214 virtual void setSpecialOperandAttr(MachineInstr &OldMI1, MachineInstr &OldMI2,
1215 MachineInstr &NewMI1,
1216 MachineInstr &NewMI2) const {}
1217
1218 /// Return true when a target supports MachineCombiner.
1219 virtual bool useMachineCombiner() const { return false; }
1220
1221 /// Return true if the given SDNode can be copied during scheduling
1222 /// even if it has glue.
1223 virtual bool canCopyGluedNodeDuringSchedule(SDNode *N) const { return false; }
1224
1225protected:
1226 /// Target-dependent implementation for foldMemoryOperand.
1227 /// Target-independent code in foldMemoryOperand will
1228 /// take care of adding a MachineMemOperand to the newly created instruction.
1229 /// The instruction and any auxiliary instructions necessary will be inserted
1230 /// at InsertPt.
1231 virtual MachineInstr *
1232 foldMemoryOperandImpl(MachineFunction &MF, MachineInstr &MI,
1233 ArrayRef<unsigned> Ops,
1234 MachineBasicBlock::iterator InsertPt, int FrameIndex,
1235 LiveIntervals *LIS = nullptr,
1236 VirtRegMap *VRM = nullptr) const {
1237 return nullptr;
1238 }
1239
1240 /// Target-dependent implementation for foldMemoryOperand.
1241 /// Target-independent code in foldMemoryOperand will
1242 /// take care of adding a MachineMemOperand to the newly created instruction.
1243 /// The instruction and any auxiliary instructions necessary will be inserted
1244 /// at InsertPt.
1245 virtual MachineInstr *foldMemoryOperandImpl(
1246 MachineFunction &MF, MachineInstr &MI, ArrayRef<unsigned> Ops,
1247 MachineBasicBlock::iterator InsertPt, MachineInstr &LoadMI,
1248 LiveIntervals *LIS = nullptr) const {
1249 return nullptr;
1250 }
1251
1252 /// Target-dependent implementation of getRegSequenceInputs.
1253 ///
1254 /// \returns true if it is possible to build the equivalent
1255 /// REG_SEQUENCE inputs with the pair \p MI, \p DefIdx. False otherwise.
1256 ///
1257 /// \pre MI.isRegSequenceLike().
1258 ///
1259 /// \see TargetInstrInfo::getRegSequenceInputs.
1260 virtual bool getRegSequenceLikeInputs(
1261 const MachineInstr &MI, unsigned DefIdx,
1262 SmallVectorImpl<RegSubRegPairAndIdx> &InputRegs) const {
1263 return false;
1264 }
1265
1266 /// Target-dependent implementation of getExtractSubregInputs.
1267 ///
1268 /// \returns true if it is possible to build the equivalent
1269 /// EXTRACT_SUBREG inputs with the pair \p MI, \p DefIdx. False otherwise.
1270 ///
1271 /// \pre MI.isExtractSubregLike().
1272 ///
1273 /// \see TargetInstrInfo::getExtractSubregInputs.
1274 virtual bool getExtractSubregLikeInputs(const MachineInstr &MI,
1275 unsigned DefIdx,
1276 RegSubRegPairAndIdx &InputReg) const {
1277 return false;
1278 }
1279
1280 /// Target-dependent implementation of getInsertSubregInputs.
1281 ///
1282 /// \returns true if it is possible to build the equivalent
1283 /// INSERT_SUBREG inputs with the pair \p MI, \p DefIdx. False otherwise.
1284 ///
1285 /// \pre MI.isInsertSubregLike().
1286 ///
1287 /// \see TargetInstrInfo::getInsertSubregInputs.
1288 virtual bool
1289 getInsertSubregLikeInputs(const MachineInstr &MI, unsigned DefIdx,
1290 RegSubRegPair &BaseReg,
1291 RegSubRegPairAndIdx &InsertedReg) const {
1292 return false;
1293 }
1294
1295public:
1296 /// unfoldMemoryOperand - Separate a single instruction which folded a load or
1297 /// a store or a load and a store into two or more instruction. If this is
1298 /// possible, returns true as well as the new instructions by reference.
1299 virtual bool
1300 unfoldMemoryOperand(MachineFunction &MF, MachineInstr &MI, unsigned Reg,
1301 bool UnfoldLoad, bool UnfoldStore,
1302 SmallVectorImpl<MachineInstr *> &NewMIs) const {
1303 return false;
1304 }
1305
1306 virtual bool unfoldMemoryOperand(SelectionDAG &DAG, SDNode *N,
1307 SmallVectorImpl<SDNode *> &NewNodes) const {
1308 return false;
1309 }
1310
1311 /// Returns the opcode of the would be new
1312 /// instruction after load / store are unfolded from an instruction of the
1313 /// specified opcode. It returns zero if the specified unfolding is not
1314 /// possible. If LoadRegIndex is non-null, it is filled in with the operand
1315 /// index of the operand which will hold the register holding the loaded
1316 /// value.
1317 virtual unsigned
1318 getOpcodeAfterMemoryUnfold(unsigned Opc, bool UnfoldLoad, bool UnfoldStore,
1319 unsigned *LoadRegIndex = nullptr) const {
1320 return 0;
1321 }
1322
1323 /// This is used by the pre-regalloc scheduler to determine if two loads are
1324 /// loading from the same base address. It should only return true if the base
1325 /// pointers are the same and the only differences between the two addresses
1326 /// are the offset. It also returns the offsets by reference.
1327 virtual bool areLoadsFromSameBasePtr(SDNode *Load1, SDNode *Load2,
1328 int64_t &Offset1,
1329 int64_t &Offset2) const {
1330 return false;
1331 }
1332
1333 /// This is a used by the pre-regalloc scheduler to determine (in conjunction
1334 /// with areLoadsFromSameBasePtr) if two loads should be scheduled together.
1335 /// On some targets if two loads are loading from
1336 /// addresses in the same cache line, it's better if they are scheduled
1337 /// together. This function takes two integers that represent the load offsets
1338 /// from the common base address. It returns true if it decides it's desirable
1339 /// to schedule the two loads together. "NumLoads" is the number of loads that
1340 /// have already been scheduled after Load1.
1341 virtual bool shouldScheduleLoadsNear(SDNode *Load1, SDNode *Load2,
1342 int64_t Offset1, int64_t Offset2,
1343 unsigned NumLoads) const {
1344 return false;
1345 }
1346
1347 /// Get the base operand and byte offset of an instruction that reads/writes
1348 /// memory. This is a convenience function for callers that are only prepared
1349 /// to handle a single base operand.
1350 bool getMemOperandWithOffset(const MachineInstr &MI,
1351 const MachineOperand *&BaseOp, int64_t &Offset,
1352 bool &OffsetIsScalable,
1353 const TargetRegisterInfo *TRI) const;
1354
1355 /// Get zero or more base operands and the byte offset of an instruction that
1356 /// reads/writes memory. Note that there may be zero base operands if the
1357 /// instruction accesses a constant address.
1358 /// It returns false if MI does not read/write memory.
1359 /// It returns false if base operands and offset could not be determined.
1360 /// It is not guaranteed to always recognize base operands and offsets in all
1361 /// cases.
1362 virtual bool getMemOperandsWithOffsetWidth(
1363 const MachineInstr &MI, SmallVectorImpl<const MachineOperand *> &BaseOps,
1364 int64_t &Offset, bool &OffsetIsScalable, unsigned &Width,
1365 const TargetRegisterInfo *TRI) const {
1366 return false;
1367 }
1368
1369 /// Return true if the instruction contains a base register and offset. If
1370 /// true, the function also sets the operand position in the instruction
1371 /// for the base register and offset.
1372 virtual bool getBaseAndOffsetPosition(const MachineInstr &MI,
1373 unsigned &BasePos,
1374 unsigned &OffsetPos) const {
1375 return false;
1376 }
1377
1378 /// Target dependent implementation to get the values constituting the address
1379 /// MachineInstr that is accessing memory. These values are returned as a
1380 /// struct ExtAddrMode which contains all relevant information to make up the
1381 /// address.
1382 virtual Optional<ExtAddrMode>
1383 getAddrModeFromMemoryOp(const MachineInstr &MemI,
1384 const TargetRegisterInfo *TRI) const {
1385 return None;
1386 }
1387
1388 /// Returns true if MI's Def is NullValueReg, and the MI
1389 /// does not change the Zero value. i.e. cases such as rax = shr rax, X where
1390 /// NullValueReg = rax. Note that if the NullValueReg is non-zero, this
1391 /// function can return true even if becomes zero. Specifically cases such as
1392 /// NullValueReg = shl NullValueReg, 63.
1393 virtual bool preservesZeroValueInReg(const MachineInstr *MI,
1394 const Register NullValueReg,
1395 const TargetRegisterInfo *TRI) const {
1396 return false;
1397 }
1398
1399 /// If the instruction is an increment of a constant value, return the amount.
1400 virtual bool getIncrementValue(const MachineInstr &MI, int &Value) const {
1401 return false;
1402 }
1403
1404 /// Returns true if the two given memory operations should be scheduled
1405 /// adjacent. Note that you have to add:
1406 /// DAG->addMutation(createLoadClusterDAGMutation(DAG->TII, DAG->TRI));
1407 /// or
1408 /// DAG->addMutation(createStoreClusterDAGMutation(DAG->TII, DAG->TRI));
1409 /// to TargetPassConfig::createMachineScheduler() to have an effect.
1410 ///
1411 /// \p BaseOps1 and \p BaseOps2 are memory operands of two memory operations.
1412 /// \p NumLoads is the number of loads that will be in the cluster if this
1413 /// hook returns true.
1414 /// \p NumBytes is the number of bytes that will be loaded from all the
1415 /// clustered loads if this hook returns true.
1416 virtual bool shouldClusterMemOps(ArrayRef<const MachineOperand *> BaseOps1,
1417 ArrayRef<const MachineOperand *> BaseOps2,
1418 unsigned NumLoads, unsigned NumBytes) const {
1419 llvm_unreachable("target did not implement shouldClusterMemOps()")::llvm::llvm_unreachable_internal("target did not implement shouldClusterMemOps()"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1419)
;
1420 }
1421
1422 /// Reverses the branch condition of the specified condition list,
1423 /// returning false on success and true if it cannot be reversed.
1424 virtual bool
1425 reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const {
1426 return true;
1427 }
1428
1429 /// Insert a noop into the instruction stream at the specified point.
1430 virtual void insertNoop(MachineBasicBlock &MBB,
1431 MachineBasicBlock::iterator MI) const;
1432
1433 /// Insert noops into the instruction stream at the specified point.
1434 virtual void insertNoops(MachineBasicBlock &MBB,
1435 MachineBasicBlock::iterator MI,
1436 unsigned Quantity) const;
1437
1438 /// Return the noop instruction to use for a noop.
1439 virtual MCInst getNop() const;
1440
1441 /// Return true for post-incremented instructions.
1442 virtual bool isPostIncrement(const MachineInstr &MI) const { return false; }
1443
1444 /// Returns true if the instruction is already predicated.
1445 virtual bool isPredicated(const MachineInstr &MI) const { return false; }
1446
1447 // Returns a MIRPrinter comment for this machine operand.
1448 virtual std::string
1449 createMIROperandComment(const MachineInstr &MI, const MachineOperand &Op,
1450 unsigned OpIdx, const TargetRegisterInfo *TRI) const;
1451
1452 /// Returns true if the instruction is a
1453 /// terminator instruction that has not been predicated.
1454 bool isUnpredicatedTerminator(const MachineInstr &MI) const;
1455
1456 /// Returns true if MI is an unconditional tail call.
1457 virtual bool isUnconditionalTailCall(const MachineInstr &MI) const {
1458 return false;
1459 }
1460
1461 /// Returns true if the tail call can be made conditional on BranchCond.
1462 virtual bool canMakeTailCallConditional(SmallVectorImpl<MachineOperand> &Cond,
1463 const MachineInstr &TailCall) const {
1464 return false;
1465 }
1466
1467 /// Replace the conditional branch in MBB with a conditional tail call.
1468 virtual void replaceBranchWithTailCall(MachineBasicBlock &MBB,
1469 SmallVectorImpl<MachineOperand> &Cond,
1470 const MachineInstr &TailCall) const {
1471 llvm_unreachable("Target didn't implement replaceBranchWithTailCall!")::llvm::llvm_unreachable_internal("Target didn't implement replaceBranchWithTailCall!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1471)
;
1472 }
1473
1474 /// Convert the instruction into a predicated instruction.
1475 /// It returns true if the operation was successful.
1476 virtual bool PredicateInstruction(MachineInstr &MI,
1477 ArrayRef<MachineOperand> Pred) const;
1478
1479 /// Returns true if the first specified predicate
1480 /// subsumes the second, e.g. GE subsumes GT.
1481 virtual bool SubsumesPredicate(ArrayRef<MachineOperand> Pred1,
1482 ArrayRef<MachineOperand> Pred2) const {
1483 return false;
1484 }
1485
1486 /// If the specified instruction defines any predicate
1487 /// or condition code register(s) used for predication, returns true as well
1488 /// as the definition predicate(s) by reference.
1489 /// SkipDead should be set to false at any point that dead
1490 /// predicate instructions should be considered as being defined.
1491 /// A dead predicate instruction is one that is guaranteed to be removed
1492 /// after a call to PredicateInstruction.
1493 virtual bool ClobbersPredicate(MachineInstr &MI,
1494 std::vector<MachineOperand> &Pred,
1495 bool SkipDead) const {
1496 return false;
1497 }
1498
1499 /// Return true if the specified instruction can be predicated.
1500 /// By default, this returns true for every instruction with a
1501 /// PredicateOperand.
1502 virtual bool isPredicable(const MachineInstr &MI) const {
1503 return MI.getDesc().isPredicable();
1504 }
1505
1506 /// Return true if it's safe to move a machine
1507 /// instruction that defines the specified register class.
1508 virtual bool isSafeToMoveRegClassDefs(const TargetRegisterClass *RC) const {
1509 return true;
1510 }
1511
1512 /// Test if the given instruction should be considered a scheduling boundary.
1513 /// This primarily includes labels and terminators.
1514 virtual bool isSchedulingBoundary(const MachineInstr &MI,
1515 const MachineBasicBlock *MBB,
1516 const MachineFunction &MF) const;
1517
1518 /// Measure the specified inline asm to determine an approximation of its
1519 /// length.
1520 virtual unsigned getInlineAsmLength(
1521 const char *Str, const MCAsmInfo &MAI,
1522 const TargetSubtargetInfo *STI = nullptr) const;
1523
1524 /// Allocate and return a hazard recognizer to use for this target when
1525 /// scheduling the machine instructions before register allocation.
1526 virtual ScheduleHazardRecognizer *
1527 CreateTargetHazardRecognizer(const TargetSubtargetInfo *STI,
1528 const ScheduleDAG *DAG) const;
1529
1530 /// Allocate and return a hazard recognizer to use for this target when
1531 /// scheduling the machine instructions before register allocation.
1532 virtual ScheduleHazardRecognizer *
1533 CreateTargetMIHazardRecognizer(const InstrItineraryData *,
1534 const ScheduleDAGMI *DAG) const;
1535
1536 /// Allocate and return a hazard recognizer to use for this target when
1537 /// scheduling the machine instructions after register allocation.
1538 virtual ScheduleHazardRecognizer *
1539 CreateTargetPostRAHazardRecognizer(const InstrItineraryData *,
1540 const ScheduleDAG *DAG) const;
1541
1542 /// Allocate and return a hazard recognizer to use for by non-scheduling
1543 /// passes.
1544 virtual ScheduleHazardRecognizer *
1545 CreateTargetPostRAHazardRecognizer(const MachineFunction &MF) const {
1546 return nullptr;
1547 }
1548
1549 /// Provide a global flag for disabling the PreRA hazard recognizer that
1550 /// targets may choose to honor.
1551 bool usePreRAHazardRecognizer() const;
1552
1553 /// For a comparison instruction, return the source registers
1554 /// in SrcReg and SrcReg2 if having two register operands, and the value it
1555 /// compares against in CmpValue. Return true if the comparison instruction
1556 /// can be analyzed.
1557 virtual bool analyzeCompare(const MachineInstr &MI, Register &SrcReg,
1558 Register &SrcReg2, int64_t &Mask,
1559 int64_t &Value) const {
1560 return false;
1561 }
1562
1563 /// See if the comparison instruction can be converted
1564 /// into something more efficient. E.g., on ARM most instructions can set the
1565 /// flags register, obviating the need for a separate CMP.
1566 virtual bool optimizeCompareInstr(MachineInstr &CmpInstr, Register SrcReg,
1567 Register SrcReg2, int64_t Mask,
1568 int64_t Value,
1569 const MachineRegisterInfo *MRI) const {
1570 return false;
1571 }
1572 virtual bool optimizeCondBranch(MachineInstr &MI) const { return false; }
1573
1574 /// Try to remove the load by folding it to a register operand at the use.
1575 /// We fold the load instructions if and only if the
1576 /// def and use are in the same BB. We only look at one load and see
1577 /// whether it can be folded into MI. FoldAsLoadDefReg is the virtual register
1578 /// defined by the load we are trying to fold. DefMI returns the machine
1579 /// instruction that defines FoldAsLoadDefReg, and the function returns
1580 /// the machine instruction generated due to folding.
1581 virtual MachineInstr *optimizeLoadInstr(MachineInstr &MI,
1582 const MachineRegisterInfo *MRI,
1583 Register &FoldAsLoadDefReg,
1584 MachineInstr *&DefMI) const {
1585 return nullptr;
1586 }
1587
1588 /// 'Reg' is known to be defined by a move immediate instruction,
1589 /// try to fold the immediate into the use instruction.
1590 /// If MRI->hasOneNonDBGUse(Reg) is true, and this function returns true,
1591 /// then the caller may assume that DefMI has been erased from its parent
1592 /// block. The caller may assume that it will not be erased by this
1593 /// function otherwise.
1594 virtual bool FoldImmediate(MachineInstr &UseMI, MachineInstr &DefMI,
1595 Register Reg, MachineRegisterInfo *MRI) const {
1596 return false;
1597 }
1598
1599 /// Return the number of u-operations the given machine
1600 /// instruction will be decoded to on the target cpu. The itinerary's
1601 /// IssueWidth is the number of microops that can be dispatched each
1602 /// cycle. An instruction with zero microops takes no dispatch resources.
1603 virtual unsigned getNumMicroOps(const InstrItineraryData *ItinData,
1604 const MachineInstr &MI) const;
1605
1606 /// Return true for pseudo instructions that don't consume any
1607 /// machine resources in their current form. These are common cases that the
1608 /// scheduler should consider free, rather than conservatively handling them
1609 /// as instructions with no itinerary.
1610 bool isZeroCost(unsigned Opcode) const {
1611 return Opcode <= TargetOpcode::COPY;
1612 }
1613
1614 virtual int getOperandLatency(const InstrItineraryData *ItinData,
1615 SDNode *DefNode, unsigned DefIdx,
1616 SDNode *UseNode, unsigned UseIdx) const;
1617
1618 /// Compute and return the use operand latency of a given pair of def and use.
1619 /// In most cases, the static scheduling itinerary was enough to determine the
1620 /// operand latency. But it may not be possible for instructions with variable
1621 /// number of defs / uses.
1622 ///
1623 /// This is a raw interface to the itinerary that may be directly overridden
1624 /// by a target. Use computeOperandLatency to get the best estimate of
1625 /// latency.
1626 virtual int getOperandLatency(const InstrItineraryData *ItinData,
1627 const MachineInstr &DefMI, unsigned DefIdx,
1628 const MachineInstr &UseMI,
1629 unsigned UseIdx) const;
1630
1631 /// Compute the instruction latency of a given instruction.
1632 /// If the instruction has higher cost when predicated, it's returned via
1633 /// PredCost.
1634 virtual unsigned getInstrLatency(const InstrItineraryData *ItinData,
1635 const MachineInstr &MI,
1636 unsigned *PredCost = nullptr) const;
1637
1638 virtual unsigned getPredicationCost(const MachineInstr &MI) const;
1639
1640 virtual int getInstrLatency(const InstrItineraryData *ItinData,
1641 SDNode *Node) const;
1642
1643 /// Return the default expected latency for a def based on its opcode.
1644 unsigned defaultDefLatency(const MCSchedModel &SchedModel,
1645 const MachineInstr &DefMI) const;
1646
1647 /// Return true if this opcode has high latency to its result.
1648 virtual bool isHighLatencyDef(int opc) const { return false; }
1649
1650 /// Compute operand latency between a def of 'Reg'
1651 /// and a use in the current loop. Return true if the target considered
1652 /// it 'high'. This is used by optimization passes such as machine LICM to
1653 /// determine whether it makes sense to hoist an instruction out even in a
1654 /// high register pressure situation.
1655 virtual bool hasHighOperandLatency(const TargetSchedModel &SchedModel,
1656 const MachineRegisterInfo *MRI,
1657 const MachineInstr &DefMI, unsigned DefIdx,
1658 const MachineInstr &UseMI,
1659 unsigned UseIdx) const {
1660 return false;
1661 }
1662
1663 /// Compute operand latency of a def of 'Reg'. Return true
1664 /// if the target considered it 'low'.
1665 virtual bool hasLowDefLatency(const TargetSchedModel &SchedModel,
1666 const MachineInstr &DefMI,
1667 unsigned DefIdx) const;
1668
1669 /// Perform target-specific instruction verification.
1670 virtual bool verifyInstruction(const MachineInstr &MI,
1671 StringRef &ErrInfo) const {
1672 return true;
1673 }
1674
1675 /// Return the current execution domain and bit mask of
1676 /// possible domains for instruction.
1677 ///
1678 /// Some micro-architectures have multiple execution domains, and multiple
1679 /// opcodes that perform the same operation in different domains. For
1680 /// example, the x86 architecture provides the por, orps, and orpd
1681 /// instructions that all do the same thing. There is a latency penalty if a
1682 /// register is written in one domain and read in another.
1683 ///
1684 /// This function returns a pair (domain, mask) containing the execution
1685 /// domain of MI, and a bit mask of possible domains. The setExecutionDomain
1686 /// function can be used to change the opcode to one of the domains in the
1687 /// bit mask. Instructions whose execution domain can't be changed should
1688 /// return a 0 mask.
1689 ///
1690 /// The execution domain numbers don't have any special meaning except domain
1691 /// 0 is used for instructions that are not associated with any interesting
1692 /// execution domain.
1693 ///
1694 virtual std::pair<uint16_t, uint16_t>
1695 getExecutionDomain(const MachineInstr &MI) const {
1696 return std::make_pair(0, 0);
1697 }
1698
1699 /// Change the opcode of MI to execute in Domain.
1700 ///
1701 /// The bit (1 << Domain) must be set in the mask returned from
1702 /// getExecutionDomain(MI).
1703 virtual void setExecutionDomain(MachineInstr &MI, unsigned Domain) const {}
1704
1705 /// Returns the preferred minimum clearance
1706 /// before an instruction with an unwanted partial register update.
1707 ///
1708 /// Some instructions only write part of a register, and implicitly need to
1709 /// read the other parts of the register. This may cause unwanted stalls
1710 /// preventing otherwise unrelated instructions from executing in parallel in
1711 /// an out-of-order CPU.
1712 ///
1713 /// For example, the x86 instruction cvtsi2ss writes its result to bits
1714 /// [31:0] of the destination xmm register. Bits [127:32] are unaffected, so
1715 /// the instruction needs to wait for the old value of the register to become
1716 /// available:
1717 ///
1718 /// addps %xmm1, %xmm0
1719 /// movaps %xmm0, (%rax)
1720 /// cvtsi2ss %rbx, %xmm0
1721 ///
1722 /// In the code above, the cvtsi2ss instruction needs to wait for the addps
1723 /// instruction before it can issue, even though the high bits of %xmm0
1724 /// probably aren't needed.
1725 ///
1726 /// This hook returns the preferred clearance before MI, measured in
1727 /// instructions. Other defs of MI's operand OpNum are avoided in the last N
1728 /// instructions before MI. It should only return a positive value for
1729 /// unwanted dependencies. If the old bits of the defined register have
1730 /// useful values, or if MI is determined to otherwise read the dependency,
1731 /// the hook should return 0.
1732 ///
1733 /// The unwanted dependency may be handled by:
1734 ///
1735 /// 1. Allocating the same register for an MI def and use. That makes the
1736 /// unwanted dependency identical to a required dependency.
1737 ///
1738 /// 2. Allocating a register for the def that has no defs in the previous N
1739 /// instructions.
1740 ///
1741 /// 3. Calling breakPartialRegDependency() with the same arguments. This
1742 /// allows the target to insert a dependency breaking instruction.
1743 ///
1744 virtual unsigned
1745 getPartialRegUpdateClearance(const MachineInstr &MI, unsigned OpNum,
1746 const TargetRegisterInfo *TRI) const {
1747 // The default implementation returns 0 for no partial register dependency.
1748 return 0;
1749 }
1750
1751 /// Return the minimum clearance before an instruction that reads an
1752 /// unused register.
1753 ///
1754 /// For example, AVX instructions may copy part of a register operand into
1755 /// the unused high bits of the destination register.
1756 ///
1757 /// vcvtsi2sdq %rax, undef %xmm0, %xmm14
1758 ///
1759 /// In the code above, vcvtsi2sdq copies %xmm0[127:64] into %xmm14 creating a
1760 /// false dependence on any previous write to %xmm0.
1761 ///
1762 /// This hook works similarly to getPartialRegUpdateClearance, except that it
1763 /// does not take an operand index. Instead sets \p OpNum to the index of the
1764 /// unused register.
1765 virtual unsigned getUndefRegClearance(const MachineInstr &MI, unsigned OpNum,
1766 const TargetRegisterInfo *TRI) const {
1767 // The default implementation returns 0 for no undef register dependency.
1768 return 0;
1769 }
1770
1771 /// Insert a dependency-breaking instruction
1772 /// before MI to eliminate an unwanted dependency on OpNum.
1773 ///
1774 /// If it wasn't possible to avoid a def in the last N instructions before MI
1775 /// (see getPartialRegUpdateClearance), this hook will be called to break the
1776 /// unwanted dependency.
1777 ///
1778 /// On x86, an xorps instruction can be used as a dependency breaker:
1779 ///
1780 /// addps %xmm1, %xmm0
1781 /// movaps %xmm0, (%rax)
1782 /// xorps %xmm0, %xmm0
1783 /// cvtsi2ss %rbx, %xmm0
1784 ///
1785 /// An <imp-kill> operand should be added to MI if an instruction was
1786 /// inserted. This ties the instructions together in the post-ra scheduler.
1787 ///
1788 virtual void breakPartialRegDependency(MachineInstr &MI, unsigned OpNum,
1789 const TargetRegisterInfo *TRI) const {}
1790
1791 /// Create machine specific model for scheduling.
1792 virtual DFAPacketizer *
1793 CreateTargetScheduleState(const TargetSubtargetInfo &) const {
1794 return nullptr;
1795 }
1796
1797 /// Sometimes, it is possible for the target
1798 /// to tell, even without aliasing information, that two MIs access different
1799 /// memory addresses. This function returns true if two MIs access different
1800 /// memory addresses and false otherwise.
1801 ///
1802 /// Assumes any physical registers used to compute addresses have the same
1803 /// value for both instructions. (This is the most useful assumption for
1804 /// post-RA scheduling.)
1805 ///
1806 /// See also MachineInstr::mayAlias, which is implemented on top of this
1807 /// function.
1808 virtual bool
1809 areMemAccessesTriviallyDisjoint(const MachineInstr &MIa,
1810 const MachineInstr &MIb) const {
1811 assert(MIa.mayLoadOrStore() &&(static_cast <bool> (MIa.mayLoadOrStore() && "MIa must load from or modify a memory location"
) ? void (0) : __assert_fail ("MIa.mayLoadOrStore() && \"MIa must load from or modify a memory location\""
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1812, __extension__
__PRETTY_FUNCTION__))
1812 "MIa must load from or modify a memory location")(static_cast <bool> (MIa.mayLoadOrStore() && "MIa must load from or modify a memory location"
) ? void (0) : __assert_fail ("MIa.mayLoadOrStore() && \"MIa must load from or modify a memory location\""
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1812, __extension__
__PRETTY_FUNCTION__))
;
1813 assert(MIb.mayLoadOrStore() &&(static_cast <bool> (MIb.mayLoadOrStore() && "MIb must load from or modify a memory location"
) ? void (0) : __assert_fail ("MIb.mayLoadOrStore() && \"MIb must load from or modify a memory location\""
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1814, __extension__
__PRETTY_FUNCTION__))
1814 "MIb must load from or modify a memory location")(static_cast <bool> (MIb.mayLoadOrStore() && "MIb must load from or modify a memory location"
) ? void (0) : __assert_fail ("MIb.mayLoadOrStore() && \"MIb must load from or modify a memory location\""
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1814, __extension__
__PRETTY_FUNCTION__))
;
1815 return false;
1816 }
1817
1818 /// Return the value to use for the MachineCSE's LookAheadLimit,
1819 /// which is a heuristic used for CSE'ing phys reg defs.
1820 virtual unsigned getMachineCSELookAheadLimit() const {
1821 // The default lookahead is small to prevent unprofitable quadratic
1822 // behavior.
1823 return 5;
1824 }
1825
1826 /// Return the maximal number of alias checks on memory operands. For
1827 /// instructions with more than one memory operands, the alias check on a
1828 /// single MachineInstr pair has quadratic overhead and results in
1829 /// unacceptable performance in the worst case. The limit here is to clamp
1830 /// that maximal checks performed. Usually, that's the product of memory
1831 /// operand numbers from that pair of MachineInstr to be checked. For
1832 /// instance, with two MachineInstrs with 4 and 5 memory operands
1833 /// correspondingly, a total of 20 checks are required. With this limit set to
1834 /// 16, their alias check is skipped. We choose to limit the product instead
1835 /// of the individual instruction as targets may have special MachineInstrs
1836 /// with a considerably high number of memory operands, such as `ldm` in ARM.
1837 /// Setting this limit per MachineInstr would result in either too high
1838 /// overhead or too rigid restriction.
1839 virtual unsigned getMemOperandAACheckLimit() const { return 16; }
1840
1841 /// Return an array that contains the ids of the target indices (used for the
1842 /// TargetIndex machine operand) and their names.
1843 ///
1844 /// MIR Serialization is able to serialize only the target indices that are
1845 /// defined by this method.
1846 virtual ArrayRef<std::pair<int, const char *>>
1847 getSerializableTargetIndices() const {
1848 return None;
1849 }
1850
1851 /// Decompose the machine operand's target flags into two values - the direct
1852 /// target flag value and any of bit flags that are applied.
1853 virtual std::pair<unsigned, unsigned>
1854 decomposeMachineOperandsTargetFlags(unsigned /*TF*/) const {
1855 return std::make_pair(0u, 0u);
1856 }
1857
1858 /// Return an array that contains the direct target flag values and their
1859 /// names.
1860 ///
1861 /// MIR Serialization is able to serialize only the target flags that are
1862 /// defined by this method.
1863 virtual ArrayRef<std::pair<unsigned, const char *>>
1864 getSerializableDirectMachineOperandTargetFlags() const {
1865 return None;
1866 }
1867
1868 /// Return an array that contains the bitmask target flag values and their
1869 /// names.
1870 ///
1871 /// MIR Serialization is able to serialize only the target flags that are
1872 /// defined by this method.
1873 virtual ArrayRef<std::pair<unsigned, const char *>>
1874 getSerializableBitmaskMachineOperandTargetFlags() const {
1875 return None;
1876 }
1877
1878 /// Return an array that contains the MMO target flag values and their
1879 /// names.
1880 ///
1881 /// MIR Serialization is able to serialize only the MMO target flags that are
1882 /// defined by this method.
1883 virtual ArrayRef<std::pair<MachineMemOperand::Flags, const char *>>
1884 getSerializableMachineMemOperandTargetFlags() const {
1885 return None;
1886 }
1887
1888 /// Determines whether \p Inst is a tail call instruction. Override this
1889 /// method on targets that do not properly set MCID::Return and MCID::Call on
1890 /// tail call instructions."
1891 virtual bool isTailCall(const MachineInstr &Inst) const {
1892 return Inst.isReturn() && Inst.isCall();
1893 }
1894
1895 /// True if the instruction is bound to the top of its basic block and no
1896 /// other instructions shall be inserted before it. This can be implemented
1897 /// to prevent register allocator to insert spills before such instructions.
1898 virtual bool isBasicBlockPrologue(const MachineInstr &MI) const {
1899 return false;
1900 }
1901
1902 /// During PHI eleimination lets target to make necessary checks and
1903 /// insert the copy to the PHI destination register in a target specific
1904 /// manner.
1905 virtual MachineInstr *createPHIDestinationCopy(
1906 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsPt,
1907 const DebugLoc &DL, Register Src, Register Dst) const {
1908 return BuildMI(MBB, InsPt, DL, get(TargetOpcode::COPY), Dst)
1909 .addReg(Src);
1910 }
1911
1912 /// During PHI eleimination lets target to make necessary checks and
1913 /// insert the copy to the PHI destination register in a target specific
1914 /// manner.
1915 virtual MachineInstr *createPHISourceCopy(MachineBasicBlock &MBB,
1916 MachineBasicBlock::iterator InsPt,
1917 const DebugLoc &DL, Register Src,
1918 unsigned SrcSubReg,
1919 Register Dst) const {
1920 return BuildMI(MBB, InsPt, DL, get(TargetOpcode::COPY), Dst)
1921 .addReg(Src, 0, SrcSubReg);
1922 }
1923
1924 /// Returns a \p outliner::OutlinedFunction struct containing target-specific
1925 /// information for a set of outlining candidates.
1926 virtual outliner::OutlinedFunction getOutliningCandidateInfo(
1927 std::vector<outliner::Candidate> &RepeatedSequenceLocs) const {
1928 llvm_unreachable(::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::getOutliningCandidateInfo!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1929)
1929 "Target didn't implement TargetInstrInfo::getOutliningCandidateInfo!")::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::getOutliningCandidateInfo!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1929)
;
1930 }
1931
1932 /// Optional target hook to create the LLVM IR attributes for the outlined
1933 /// function. If overridden, the overriding function must call the default
1934 /// implementation.
1935 virtual void mergeOutliningCandidateAttributes(
1936 Function &F, std::vector<outliner::Candidate> &Candidates) const;
1937
1938 /// Returns how or if \p MI should be outlined.
1939 virtual outliner::InstrType
1940 getOutliningType(MachineBasicBlock::iterator &MIT, unsigned Flags) const {
1941 llvm_unreachable(::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::getOutliningType!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1942)
1942 "Target didn't implement TargetInstrInfo::getOutliningType!")::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::getOutliningType!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1942)
;
1943 }
1944
1945 /// Optional target hook that returns true if \p MBB is safe to outline from,
1946 /// and returns any target-specific information in \p Flags.
1947 virtual bool isMBBSafeToOutlineFrom(MachineBasicBlock &MBB,
1948 unsigned &Flags) const;
1949
1950 /// Insert a custom frame for outlined functions.
1951 virtual void buildOutlinedFrame(MachineBasicBlock &MBB, MachineFunction &MF,
1952 const outliner::OutlinedFunction &OF) const {
1953 llvm_unreachable(::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::buildOutlinedFrame!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1954)
1954 "Target didn't implement TargetInstrInfo::buildOutlinedFrame!")::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::buildOutlinedFrame!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1954)
;
1955 }
1956
1957 /// Insert a call to an outlined function into the program.
1958 /// Returns an iterator to the spot where we inserted the call. This must be
1959 /// implemented by the target.
1960 virtual MachineBasicBlock::iterator
1961 insertOutlinedCall(Module &M, MachineBasicBlock &MBB,
1962 MachineBasicBlock::iterator &It, MachineFunction &MF,
1963 outliner::Candidate &C) const {
1964 llvm_unreachable(::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::insertOutlinedCall!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1965)
1965 "Target didn't implement TargetInstrInfo::insertOutlinedCall!")::llvm::llvm_unreachable_internal("Target didn't implement TargetInstrInfo::insertOutlinedCall!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1965)
;
1966 }
1967
1968 /// Return true if the function can safely be outlined from.
1969 /// A function \p MF is considered safe for outlining if an outlined function
1970 /// produced from instructions in F will produce a program which produces the
1971 /// same output for any set of given inputs.
1972 virtual bool isFunctionSafeToOutlineFrom(MachineFunction &MF,
1973 bool OutlineFromLinkOnceODRs) const {
1974 llvm_unreachable("Target didn't implement "::llvm::llvm_unreachable_internal("Target didn't implement " "TargetInstrInfo::isFunctionSafeToOutlineFrom!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1975)
1975 "TargetInstrInfo::isFunctionSafeToOutlineFrom!")::llvm::llvm_unreachable_internal("Target didn't implement " "TargetInstrInfo::isFunctionSafeToOutlineFrom!"
, "llvm/include/llvm/CodeGen/TargetInstrInfo.h", 1975)
;
1976 }
1977
1978 /// Return true if the function should be outlined from by default.
1979 virtual bool shouldOutlineFromFunctionByDefault(MachineFunction &MF) const {
1980 return false;
1981 }
1982
1983 /// Produce the expression describing the \p MI loading a value into
1984 /// the physical register \p Reg. This hook should only be used with
1985 /// \p MIs belonging to VReg-less functions.
1986 virtual Optional<ParamLoadedValue> describeLoadedValue(const MachineInstr &MI,
1987 Register Reg) const;
1988
1989 /// Given the generic extension instruction \p ExtMI, returns true if this
1990 /// extension is a likely candidate for being folded into an another
1991 /// instruction.
1992 virtual bool isExtendLikelyToBeFolded(MachineInstr &ExtMI,
1993 MachineRegisterInfo &MRI) const {
1994 return false;
1995 }
1996
1997 /// Return MIR formatter to format/parse MIR operands. Target can override
1998 /// this virtual function and return target specific MIR formatter.
1999 virtual const MIRFormatter *getMIRFormatter() const {
2000 if (!Formatter.get())
2001 Formatter = std::make_unique<MIRFormatter>();
2002 return Formatter.get();
2003 }
2004
2005 /// Returns the target-specific default value for tail duplication.
2006 /// This value will be used if the tail-dup-placement-threshold argument is
2007 /// not provided.
2008 virtual unsigned getTailDuplicateSize(CodeGenOpt::Level OptLevel) const {
2009 return OptLevel >= CodeGenOpt::Aggressive ? 4 : 2;
2010 }
2011
2012 /// Returns the callee operand from the given \p MI.
2013 virtual const MachineOperand &getCalleeOperand(const MachineInstr &MI) const {
2014 return MI.getOperand(0);
2015 }
2016
2017private:
2018 mutable std::unique_ptr<MIRFormatter> Formatter;
2019 unsigned CallFrameSetupOpcode, CallFrameDestroyOpcode;
2020 unsigned CatchRetOpcode;
2021 unsigned ReturnOpcode;
2022};
2023
2024/// Provide DenseMapInfo for TargetInstrInfo::RegSubRegPair.
2025template <> struct DenseMapInfo<TargetInstrInfo::RegSubRegPair> {
2026 using RegInfo = DenseMapInfo<unsigned>;
2027
2028 static inline TargetInstrInfo::RegSubRegPair getEmptyKey() {
2029 return TargetInstrInfo::RegSubRegPair(RegInfo::getEmptyKey(),
2030 RegInfo::getEmptyKey());
2031 }
2032
2033 static inline TargetInstrInfo::RegSubRegPair getTombstoneKey() {
2034 return TargetInstrInfo::RegSubRegPair(RegInfo::getTombstoneKey(),
2035 RegInfo::getTombstoneKey());
2036 }
2037
2038 /// Reuse getHashValue implementation from
2039 /// std::pair<unsigned, unsigned>.
2040 static unsigned getHashValue(const TargetInstrInfo::RegSubRegPair &Val) {
2041 std::pair<unsigned, unsigned> PairVal = std::make_pair(Val.Reg, Val.SubReg);
2042 return DenseMapInfo<std::pair<unsigned, unsigned>>::getHashValue(PairVal);
2043 }
2044
2045 static bool isEqual(const TargetInstrInfo::RegSubRegPair &LHS,
2046 const TargetInstrInfo::RegSubRegPair &RHS) {
2047 return RegInfo::isEqual(LHS.Reg, RHS.Reg) &&
2048 RegInfo::isEqual(LHS.SubReg, RHS.SubReg);
2049 }
2050};
2051
2052} // end namespace llvm
2053
2054#endif // LLVM_CODEGEN_TARGETINSTRINFO_H