Bug Summary

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

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