Bug Summary

File:lib/CodeGen/InlineSpiller.cpp
Warning:line 297, column 61
The left operand of '==' is a garbage value

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -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 -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-8~svn345461/lib/CodeGen -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn345461/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/lib/CodeGen -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-10-27-211344-32123-1 -x c++ /build/llvm-toolchain-snapshot-8~svn345461/lib/CodeGen/InlineSpiller.cpp -faddrsig

/build/llvm-toolchain-snapshot-8~svn345461/lib/CodeGen/InlineSpiller.cpp

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

/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/CodeGen/TargetInstrInfo.h

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