Bug Summary

File:build/source/llvm/lib/CodeGen/InlineSpiller.cpp
Warning:line 322, 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/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D _LIBCPP_ENABLE_ASSERTIONS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/CodeGen -I /build/source/llvm/lib/CodeGen -I include -I /build/source/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-17/lib/clang/17/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/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1683717183 -O2 -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/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -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-2023-05-10-133810-16478-1 -x c++ /build/source/llvm/lib/CodeGen/InlineSpiller.cpp

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

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