Bug Summary

File:build/source/llvm/lib/CodeGen/InlineSpiller.cpp
Warning:line 499, column 55
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 -resource-dir /usr/lib/llvm-17/lib/clang/17 -I lib/CodeGen -I /build/source/llvm/lib/CodeGen -I include -I /build/source/llvm/include -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -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=build-llvm -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm=build-llvm -fcoverage-prefix-map=/build/source/= -source-date-epoch 1675721604 -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm -fdebug-prefix-map=/build/source/build-llvm=build-llvm -fdebug-prefix-map=/build/source/= -fdebug-prefix-map=/build/source/build-llvm=build-llvm -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-02-07-030702-17298-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;
169 LiveInterval *StackInt;
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))
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()) {
300 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
301 if (MI->getOpcode() == TargetOpcode::STATEPOINT)
302 --NumValNums;
303 }
304 if (NumValNums > 2)
305 return false;
306
307 MachineInstr *UseMI = nullptr;
308
309 // Check that all uses satisfy our criteria.
310 for (MachineRegisterInfo::reg_instr_nodbg_iterator
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))
318 continue;
319
320 // Allow stack slot loads.
321 int FI;
322 if (SnipLI.reg() == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
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__));
34
←
Assuming 'VNI' is non-null
→
35
←
'?' condition is true
→
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__
));
36
←
Assuming field 'StackInt' is non-null
→
37
←
'?' condition is true
→
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)
38
←
Assuming 'DebugFlag' is false
→
39
←
Loop condition is false. Exiting loop
→
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))
40
←
Taking false branch
→
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);
41
←
Assuming 'DebugFlag' is false
→
42
←
Loop condition is false. Exiting loop
→
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())
43
←
Assuming the condition is false
→
44
←
Taking false branch
→
480 continue;
481 SlotIndex Idx = LIS.getInstructionIndex(MI);
482 if (LI->getVNInfoAt(Idx) != VNI)
45
←
Assuming the condition is false
→
46
←
Taking false branch
→
483 continue;
484
485 // Follow sibling copies down the dominator tree.
486 if (Register DstReg = isFullCopyOf(MI, Reg)) {
47
←
Taking false branch
→
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;
48
←
'FI' declared without an initial value
→
499 if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {
49
←
Calling 'TargetInstrInfo::isStoreToStackSlot'
→
51
←
Returning from 'TargetInstrInfo::isStoreToStackSlot'
→
52
←
The left operand of '==' is a garbage value
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);
19
←
Assuming 'DebugFlag' is false
→
20
←
Loop condition is false. Exiting loop
→
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__
))
21
←
Taking false branch
→
22
←
'?' condition is true
→
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))
23
←
Assuming the condition is false
→
24
←
Taking false branch
→
1096 continue;
1097
1098 // Stack slot accesses may coalesce away.
1099 if (coalesceStackAccess(&MI, Reg))
25
←
Taking false branch
→
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)))
26
←
Assuming 'VNI' is null
→
27
←
Taking false branch
→
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)) {
28
←
Assuming the condition is true
→
29
←
Taking true branch
→
1116 // This may actually be a copy between snippets.
1117 if (isRegToSpill(SibReg)) {
30
←
Taking false branch
→
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) {
31
←
Assuming field 'Writes' is false
→
32
←
Taking false branch
→
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));
33
←
Calling 'InlineSpiller::eliminateRedundantSpills'
→
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) {
9
←
Assuming field 'StackSlot' is not equal to NO_STACK_SLOT
→
10
←
Taking false branch
→
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__
));
11
←
Taking false branch
→
12
←
Assuming the condition is true
→
13
←
'?' condition is true
→
1184 for (Register Reg : RegsToSpill)
14
←
Assuming '__begin1' is equal to '__end1'
→
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);
15
←
Assuming 'DebugFlag' is false
→
16
←
Loop condition is false. Exiting loop
→
1188
1189 // Spill around uses of all RegsToSpill.
1190 for (Register Reg : RegsToSpill)
17
←
Assuming '__begin1' is not equal to '__end1'
→
1191 spillAroundUses(Reg);
18
←
Calling 'InlineSpiller::spillAroundUses'
→
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__
))
1
'?' condition is true
→
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)
2
←
Assuming 'DebugFlag' is 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__
))
3
←
Loop condition is false. Exiting loop
→
4
←
Assuming the condition is true
→
5
←
'?' condition is true
→
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__
));
6
←
'?' condition is true
→
1232
1233 collectRegsToSpill();
1234 reMaterializeAll();
1235
1236 // Remat may handle everything.
1237 if (!RegsToSpill.empty())
7
←
Taking true branch
→
1238 spillAll();
8
←
Calling 'InlineSpiller::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.find(StackSlot) == StackSlotToOrigLI.end()) {
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.find(*RIt) != SpillsToKeep.end() && !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.find(Child) == SpillsInSubTreeMap.end())
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.find(SpillBB) != SpillsToKeep.end() &&
1512 !SpillsToKeep[SpillBB]) {
1513 MachineInstr *SpillToRm = SpillBBToSpill[SpillBB];
1514 SpillsToRm.push_back(SpillToRm);
1515 }
1516 // SpillBB will not contain spill anymore, remove it from SpillsToKeep.
1517 SpillsToKeep.erase(SpillBB);
1518 }
1519 // Current Block is the BB containing the new hoisted spill. Add it to
1520 // SpillsToKeep. LiveReg is the source of the new spill.
1521 SpillsToKeep[*RIt] = LiveReg;
1522 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)
1523 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)
1524 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)
1525 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)
1526 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)
1527 << "\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)
1528 })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);
1529 SpillsInSubTree.clear();
1530 SpillsInSubTree.insert(*RIt);
1531 SubTreeCost = MBFI.getBlockFreq(Block);
1532 }
1533 }
1534 // For spills in SpillsToKeep with LiveReg set (i.e., not original spill),
1535 // save them to SpillsToIns.
1536 for (const auto &Ent : SpillsToKeep) {
1537 if (Ent.second)
1538 SpillsToIns[Ent.first->getBlock()] = Ent.second;
1539 }
1540}
1541
1542/// For spills with equal values, remove redundant spills and hoist those left
1543/// to less hot spots.
1544///
1545/// Spills with equal values will be collected into the same set in
1546/// MergeableSpills when spill is inserted. These equal spills are originated
1547/// from the same defining instruction and are dominated by the instruction.
1548/// Before hoisting all the equal spills, redundant spills inside in the same
1549/// BB are first marked to be deleted. Then starting from the spills left, walk
1550/// up on the dominator tree towards the Root node where the define instruction
1551/// is located, mark the dominated spills to be deleted along the way and
1552/// collect the BB nodes on the path from non-dominated spills to the define
1553/// instruction into a WorkSet. The nodes in WorkSet are the candidate places
1554/// where we are considering to hoist the spills. We iterate the WorkSet in
1555/// bottom-up order, and for each node, we will decide whether to hoist spills
1556/// inside its subtree to that node. In this way, we can get benefit locally
1557/// even if hoisting all the equal spills to one cold place is impossible.
1558void HoistSpillHelper::hoistAllSpills() {
1559 SmallVector<Register, 4> NewVRegs;
1560 LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this);
1561
1562 for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
1563 Register Reg = Register::index2VirtReg(i);
1564 Register Original = VRM.getPreSplitReg(Reg);
1565 if (!MRI.def_empty(Reg))
1566 Virt2SiblingsMap[Original].insert(Reg);
1567 }
1568
1569 // Each entry in MergeableSpills contains a spill set with equal values.
1570 for (auto &Ent : MergeableSpills) {
1571 int Slot = Ent.first.first;
1572 LiveInterval &OrigLI = *StackSlotToOrigLI[Slot];
1573 VNInfo *OrigVNI = Ent.first.second;
1574 SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;
1575 if (Ent.second.empty())
1576 continue;
1577
1578 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)
1579 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)
1580 << "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)
1581 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)
1582 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)
1583 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)
1584 })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);
1585
1586 // SpillsToRm is the spill set to be removed from EqValSpills.
1587 SmallVector<MachineInstr *, 16> SpillsToRm;
1588 // SpillsToIns is the spill set to be newly inserted after hoisting.
1589 DenseMap<MachineBasicBlock *, unsigned> SpillsToIns;
1590
1591 runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
1592
1593 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)
1594 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)
1595 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)
1596 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)
1597 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)
1598 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)
1599 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)
1600 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)
1601 })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);
1602
1603 // Stack live range update.
1604 LiveInterval &StackIntvl = LSS.getInterval(Slot);
1605 if (!SpillsToIns.empty() || !SpillsToRm.empty())
1606 StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI,
1607 StackIntvl.getValNumInfo(0));
1608
1609 // Insert hoisted spills.
1610 for (auto const &Insert : SpillsToIns) {
1611 MachineBasicBlock *BB = Insert.first;
1612 Register LiveReg = Insert.second;
1613 MachineBasicBlock::iterator MII = IPA.getLastInsertPointIter(OrigLI, *BB);
1614 MachineInstrSpan MIS(MII, BB);
1615 TII.storeRegToStackSlot(*BB, MII, LiveReg, false, Slot,
1616 MRI.getRegClass(LiveReg), &TRI, Register());
1617 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MII);
1618 for (const MachineInstr &MI : make_range(MIS.begin(), MII))
1619 getVDefInterval(MI, LIS);
1620 ++NumSpills;
1621 }
1622
1623 // Remove redundant spills or change them to dead instructions.
1624 NumSpills -= SpillsToRm.size();
1625 for (auto *const RMEnt : SpillsToRm) {
1626 RMEnt->setDesc(TII.get(TargetOpcode::KILL));
1627 for (unsigned i = RMEnt->getNumOperands(); i; --i) {
1628 MachineOperand &MO = RMEnt->getOperand(i - 1);
1629 if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead())
1630 RMEnt->removeOperand(i - 1);
1631 }
1632 }
1633 Edit.eliminateDeadDefs(SpillsToRm, std::nullopt);
1634 }
1635}
1636
1637/// For VirtReg clone, the \p New register should have the same physreg or
1638/// stackslot as the \p old register.
1639void HoistSpillHelper::LRE_DidCloneVirtReg(Register New, Register Old) {
1640 if (VRM.hasPhys(Old))
1641 VRM.assignVirt2Phys(New, VRM.getPhys(Old));
1642 else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT)
1643 VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
1644 else
1645 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", 1645);
1646 if (VRM.hasShape(Old))
1647 VRM.assignVirt2Shape(New, VRM.getShape(Old));
1648}
←

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