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