Bug Summary

File:build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/CodeGen/InlineSpiller.cpp
Warning:line 316, 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-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm -resource-dir /usr/lib/llvm-15/lib/clang/15.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/CodeGen -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/CodeGen -I include -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-15/lib/clang/15.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -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 -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-04-20-140412-16051-1 -x c++ /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/CodeGen/InlineSpiller.cpp

/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/CodeGen/InlineSpiller.cpp

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

/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include/llvm/CodeGen/TargetInstrInfo.h

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