File: | build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/CodeGen/PeepholeOptimizer.cpp |
Warning: | line 545, column 30 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- PeepholeOptimizer.cpp - Peephole Optimizations ---------------------===// | |||
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 | // Perform peephole optimizations on the machine code: | |||
10 | // | |||
11 | // - Optimize Extensions | |||
12 | // | |||
13 | // Optimization of sign / zero extension instructions. It may be extended to | |||
14 | // handle other instructions with similar properties. | |||
15 | // | |||
16 | // On some targets, some instructions, e.g. X86 sign / zero extension, may | |||
17 | // leave the source value in the lower part of the result. This optimization | |||
18 | // will replace some uses of the pre-extension value with uses of the | |||
19 | // sub-register of the results. | |||
20 | // | |||
21 | // - Optimize Comparisons | |||
22 | // | |||
23 | // Optimization of comparison instructions. For instance, in this code: | |||
24 | // | |||
25 | // sub r1, 1 | |||
26 | // cmp r1, 0 | |||
27 | // bz L1 | |||
28 | // | |||
29 | // If the "sub" instruction all ready sets (or could be modified to set) the | |||
30 | // same flag that the "cmp" instruction sets and that "bz" uses, then we can | |||
31 | // eliminate the "cmp" instruction. | |||
32 | // | |||
33 | // Another instance, in this code: | |||
34 | // | |||
35 | // sub r1, r3 | sub r1, imm | |||
36 | // cmp r3, r1 or cmp r1, r3 | cmp r1, imm | |||
37 | // bge L1 | |||
38 | // | |||
39 | // If the branch instruction can use flag from "sub", then we can replace | |||
40 | // "sub" with "subs" and eliminate the "cmp" instruction. | |||
41 | // | |||
42 | // - Optimize Loads: | |||
43 | // | |||
44 | // Loads that can be folded into a later instruction. A load is foldable | |||
45 | // if it loads to virtual registers and the virtual register defined has | |||
46 | // a single use. | |||
47 | // | |||
48 | // - Optimize Copies and Bitcast (more generally, target specific copies): | |||
49 | // | |||
50 | // Rewrite copies and bitcasts to avoid cross register bank copies | |||
51 | // when possible. | |||
52 | // E.g., Consider the following example, where capital and lower | |||
53 | // letters denote different register file: | |||
54 | // b = copy A <-- cross-bank copy | |||
55 | // C = copy b <-- cross-bank copy | |||
56 | // => | |||
57 | // b = copy A <-- cross-bank copy | |||
58 | // C = copy A <-- same-bank copy | |||
59 | // | |||
60 | // E.g., for bitcast: | |||
61 | // b = bitcast A <-- cross-bank copy | |||
62 | // C = bitcast b <-- cross-bank copy | |||
63 | // => | |||
64 | // b = bitcast A <-- cross-bank copy | |||
65 | // C = copy A <-- same-bank copy | |||
66 | //===----------------------------------------------------------------------===// | |||
67 | ||||
68 | #include "llvm/ADT/DenseMap.h" | |||
69 | #include "llvm/ADT/Optional.h" | |||
70 | #include "llvm/ADT/SmallPtrSet.h" | |||
71 | #include "llvm/ADT/SmallSet.h" | |||
72 | #include "llvm/ADT/SmallVector.h" | |||
73 | #include "llvm/ADT/Statistic.h" | |||
74 | #include "llvm/CodeGen/MachineBasicBlock.h" | |||
75 | #include "llvm/CodeGen/MachineDominators.h" | |||
76 | #include "llvm/CodeGen/MachineFunction.h" | |||
77 | #include "llvm/CodeGen/MachineFunctionPass.h" | |||
78 | #include "llvm/CodeGen/MachineInstr.h" | |||
79 | #include "llvm/CodeGen/MachineInstrBuilder.h" | |||
80 | #include "llvm/CodeGen/MachineLoopInfo.h" | |||
81 | #include "llvm/CodeGen/MachineOperand.h" | |||
82 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |||
83 | #include "llvm/CodeGen/TargetInstrInfo.h" | |||
84 | #include "llvm/CodeGen/TargetOpcodes.h" | |||
85 | #include "llvm/CodeGen/TargetRegisterInfo.h" | |||
86 | #include "llvm/CodeGen/TargetSubtargetInfo.h" | |||
87 | #include "llvm/InitializePasses.h" | |||
88 | #include "llvm/MC/LaneBitmask.h" | |||
89 | #include "llvm/MC/MCInstrDesc.h" | |||
90 | #include "llvm/Pass.h" | |||
91 | #include "llvm/Support/CommandLine.h" | |||
92 | #include "llvm/Support/Debug.h" | |||
93 | #include "llvm/Support/raw_ostream.h" | |||
94 | #include <cassert> | |||
95 | #include <cstdint> | |||
96 | #include <memory> | |||
97 | #include <utility> | |||
98 | ||||
99 | using namespace llvm; | |||
100 | using RegSubRegPair = TargetInstrInfo::RegSubRegPair; | |||
101 | using RegSubRegPairAndIdx = TargetInstrInfo::RegSubRegPairAndIdx; | |||
102 | ||||
103 | #define DEBUG_TYPE"peephole-opt" "peephole-opt" | |||
104 | ||||
105 | // Optimize Extensions | |||
106 | static cl::opt<bool> | |||
107 | Aggressive("aggressive-ext-opt", cl::Hidden, | |||
108 | cl::desc("Aggressive extension optimization")); | |||
109 | ||||
110 | static cl::opt<bool> | |||
111 | DisablePeephole("disable-peephole", cl::Hidden, cl::init(false), | |||
112 | cl::desc("Disable the peephole optimizer")); | |||
113 | ||||
114 | /// Specifiy whether or not the value tracking looks through | |||
115 | /// complex instructions. When this is true, the value tracker | |||
116 | /// bails on everything that is not a copy or a bitcast. | |||
117 | static cl::opt<bool> | |||
118 | DisableAdvCopyOpt("disable-adv-copy-opt", cl::Hidden, cl::init(false), | |||
119 | cl::desc("Disable advanced copy optimization")); | |||
120 | ||||
121 | static cl::opt<bool> DisableNAPhysCopyOpt( | |||
122 | "disable-non-allocatable-phys-copy-opt", cl::Hidden, cl::init(false), | |||
123 | cl::desc("Disable non-allocatable physical register copy optimization")); | |||
124 | ||||
125 | // Limit the number of PHI instructions to process | |||
126 | // in PeepholeOptimizer::getNextSource. | |||
127 | static cl::opt<unsigned> RewritePHILimit( | |||
128 | "rewrite-phi-limit", cl::Hidden, cl::init(10), | |||
129 | cl::desc("Limit the length of PHI chains to lookup")); | |||
130 | ||||
131 | // Limit the length of recurrence chain when evaluating the benefit of | |||
132 | // commuting operands. | |||
133 | static cl::opt<unsigned> MaxRecurrenceChain( | |||
134 | "recurrence-chain-limit", cl::Hidden, cl::init(3), | |||
135 | cl::desc("Maximum length of recurrence chain when evaluating the benefit " | |||
136 | "of commuting operands")); | |||
137 | ||||
138 | ||||
139 | STATISTIC(NumReuse, "Number of extension results reused")static llvm::Statistic NumReuse = {"peephole-opt", "NumReuse" , "Number of extension results reused"}; | |||
140 | STATISTIC(NumCmps, "Number of compares eliminated")static llvm::Statistic NumCmps = {"peephole-opt", "NumCmps", "Number of compares eliminated" }; | |||
141 | STATISTIC(NumImmFold, "Number of move immediate folded")static llvm::Statistic NumImmFold = {"peephole-opt", "NumImmFold" , "Number of move immediate folded"}; | |||
142 | STATISTIC(NumLoadFold, "Number of loads folded")static llvm::Statistic NumLoadFold = {"peephole-opt", "NumLoadFold" , "Number of loads folded"}; | |||
143 | STATISTIC(NumSelects, "Number of selects optimized")static llvm::Statistic NumSelects = {"peephole-opt", "NumSelects" , "Number of selects optimized"}; | |||
144 | STATISTIC(NumUncoalescableCopies, "Number of uncoalescable copies optimized")static llvm::Statistic NumUncoalescableCopies = {"peephole-opt" , "NumUncoalescableCopies", "Number of uncoalescable copies optimized" }; | |||
145 | STATISTIC(NumRewrittenCopies, "Number of copies rewritten")static llvm::Statistic NumRewrittenCopies = {"peephole-opt", "NumRewrittenCopies" , "Number of copies rewritten"}; | |||
146 | STATISTIC(NumNAPhysCopies, "Number of non-allocatable physical copies removed")static llvm::Statistic NumNAPhysCopies = {"peephole-opt", "NumNAPhysCopies" , "Number of non-allocatable physical copies removed"}; | |||
147 | ||||
148 | namespace { | |||
149 | ||||
150 | class ValueTrackerResult; | |||
151 | class RecurrenceInstr; | |||
152 | ||||
153 | class PeepholeOptimizer : public MachineFunctionPass { | |||
154 | const TargetInstrInfo *TII; | |||
155 | const TargetRegisterInfo *TRI; | |||
156 | MachineRegisterInfo *MRI; | |||
157 | MachineDominatorTree *DT; // Machine dominator tree | |||
158 | MachineLoopInfo *MLI; | |||
159 | ||||
160 | public: | |||
161 | static char ID; // Pass identification | |||
162 | ||||
163 | PeepholeOptimizer() : MachineFunctionPass(ID) { | |||
164 | initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry()); | |||
165 | } | |||
166 | ||||
167 | bool runOnMachineFunction(MachineFunction &MF) override; | |||
168 | ||||
169 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
170 | AU.setPreservesCFG(); | |||
171 | MachineFunctionPass::getAnalysisUsage(AU); | |||
172 | AU.addRequired<MachineLoopInfo>(); | |||
173 | AU.addPreserved<MachineLoopInfo>(); | |||
174 | if (Aggressive) { | |||
175 | AU.addRequired<MachineDominatorTree>(); | |||
176 | AU.addPreserved<MachineDominatorTree>(); | |||
177 | } | |||
178 | } | |||
179 | ||||
180 | MachineFunctionProperties getRequiredProperties() const override { | |||
181 | return MachineFunctionProperties() | |||
182 | .set(MachineFunctionProperties::Property::IsSSA); | |||
183 | } | |||
184 | ||||
185 | /// Track Def -> Use info used for rewriting copies. | |||
186 | using RewriteMapTy = SmallDenseMap<RegSubRegPair, ValueTrackerResult>; | |||
187 | ||||
188 | /// Sequence of instructions that formulate recurrence cycle. | |||
189 | using RecurrenceCycle = SmallVector<RecurrenceInstr, 4>; | |||
190 | ||||
191 | private: | |||
192 | bool optimizeCmpInstr(MachineInstr &MI); | |||
193 | bool optimizeExtInstr(MachineInstr &MI, MachineBasicBlock &MBB, | |||
194 | SmallPtrSetImpl<MachineInstr*> &LocalMIs); | |||
195 | bool optimizeSelect(MachineInstr &MI, | |||
196 | SmallPtrSetImpl<MachineInstr *> &LocalMIs); | |||
197 | bool optimizeCondBranch(MachineInstr &MI); | |||
198 | bool optimizeCoalescableCopy(MachineInstr &MI); | |||
199 | bool optimizeUncoalescableCopy(MachineInstr &MI, | |||
200 | SmallPtrSetImpl<MachineInstr *> &LocalMIs); | |||
201 | bool optimizeRecurrence(MachineInstr &PHI); | |||
202 | bool findNextSource(RegSubRegPair RegSubReg, RewriteMapTy &RewriteMap); | |||
203 | bool isMoveImmediate(MachineInstr &MI, SmallSet<Register, 4> &ImmDefRegs, | |||
204 | DenseMap<Register, MachineInstr *> &ImmDefMIs); | |||
205 | bool foldImmediate(MachineInstr &MI, SmallSet<Register, 4> &ImmDefRegs, | |||
206 | DenseMap<Register, MachineInstr *> &ImmDefMIs); | |||
207 | ||||
208 | /// Finds recurrence cycles, but only ones that formulated around | |||
209 | /// a def operand and a use operand that are tied. If there is a use | |||
210 | /// operand commutable with the tied use operand, find recurrence cycle | |||
211 | /// along that operand as well. | |||
212 | bool findTargetRecurrence(Register Reg, | |||
213 | const SmallSet<Register, 2> &TargetReg, | |||
214 | RecurrenceCycle &RC); | |||
215 | ||||
216 | /// If copy instruction \p MI is a virtual register copy, track it in | |||
217 | /// the set \p CopyMIs. If this virtual register was previously seen as a | |||
218 | /// copy, replace the uses of this copy with the previously seen copy's | |||
219 | /// destination register. | |||
220 | bool foldRedundantCopy(MachineInstr &MI, | |||
221 | DenseMap<RegSubRegPair, MachineInstr *> &CopyMIs); | |||
222 | ||||
223 | /// Is the register \p Reg a non-allocatable physical register? | |||
224 | bool isNAPhysCopy(Register Reg); | |||
225 | ||||
226 | /// If copy instruction \p MI is a non-allocatable virtual<->physical | |||
227 | /// register copy, track it in the \p NAPhysToVirtMIs map. If this | |||
228 | /// non-allocatable physical register was previously copied to a virtual | |||
229 | /// registered and hasn't been clobbered, the virt->phys copy can be | |||
230 | /// deleted. | |||
231 | bool foldRedundantNAPhysCopy( | |||
232 | MachineInstr &MI, DenseMap<Register, MachineInstr *> &NAPhysToVirtMIs); | |||
233 | ||||
234 | bool isLoadFoldable(MachineInstr &MI, | |||
235 | SmallSet<Register, 16> &FoldAsLoadDefCandidates); | |||
236 | ||||
237 | /// Check whether \p MI is understood by the register coalescer | |||
238 | /// but may require some rewriting. | |||
239 | bool isCoalescableCopy(const MachineInstr &MI) { | |||
240 | // SubregToRegs are not interesting, because they are already register | |||
241 | // coalescer friendly. | |||
242 | return MI.isCopy() || (!DisableAdvCopyOpt && | |||
243 | (MI.isRegSequence() || MI.isInsertSubreg() || | |||
244 | MI.isExtractSubreg())); | |||
245 | } | |||
246 | ||||
247 | /// Check whether \p MI is a copy like instruction that is | |||
248 | /// not recognized by the register coalescer. | |||
249 | bool isUncoalescableCopy(const MachineInstr &MI) { | |||
250 | return MI.isBitcast() || | |||
251 | (!DisableAdvCopyOpt && | |||
252 | (MI.isRegSequenceLike() || MI.isInsertSubregLike() || | |||
253 | MI.isExtractSubregLike())); | |||
254 | } | |||
255 | ||||
256 | MachineInstr &rewriteSource(MachineInstr &CopyLike, | |||
257 | RegSubRegPair Def, RewriteMapTy &RewriteMap); | |||
258 | }; | |||
259 | ||||
260 | /// Helper class to hold instructions that are inside recurrence cycles. | |||
261 | /// The recurrence cycle is formulated around 1) a def operand and its | |||
262 | /// tied use operand, or 2) a def operand and a use operand that is commutable | |||
263 | /// with another use operand which is tied to the def operand. In the latter | |||
264 | /// case, index of the tied use operand and the commutable use operand are | |||
265 | /// maintained with CommutePair. | |||
266 | class RecurrenceInstr { | |||
267 | public: | |||
268 | using IndexPair = std::pair<unsigned, unsigned>; | |||
269 | ||||
270 | RecurrenceInstr(MachineInstr *MI) : MI(MI) {} | |||
271 | RecurrenceInstr(MachineInstr *MI, unsigned Idx1, unsigned Idx2) | |||
272 | : MI(MI), CommutePair(std::make_pair(Idx1, Idx2)) {} | |||
273 | ||||
274 | MachineInstr *getMI() const { return MI; } | |||
275 | Optional<IndexPair> getCommutePair() const { return CommutePair; } | |||
276 | ||||
277 | private: | |||
278 | MachineInstr *MI; | |||
279 | Optional<IndexPair> CommutePair; | |||
280 | }; | |||
281 | ||||
282 | /// Helper class to hold a reply for ValueTracker queries. | |||
283 | /// Contains the returned sources for a given search and the instructions | |||
284 | /// where the sources were tracked from. | |||
285 | class ValueTrackerResult { | |||
286 | private: | |||
287 | /// Track all sources found by one ValueTracker query. | |||
288 | SmallVector<RegSubRegPair, 2> RegSrcs; | |||
289 | ||||
290 | /// Instruction using the sources in 'RegSrcs'. | |||
291 | const MachineInstr *Inst = nullptr; | |||
292 | ||||
293 | public: | |||
294 | ValueTrackerResult() = default; | |||
295 | ||||
296 | ValueTrackerResult(Register Reg, unsigned SubReg) { | |||
297 | addSource(Reg, SubReg); | |||
298 | } | |||
299 | ||||
300 | bool isValid() const { return getNumSources() > 0; } | |||
301 | ||||
302 | void setInst(const MachineInstr *I) { Inst = I; } | |||
303 | const MachineInstr *getInst() const { return Inst; } | |||
304 | ||||
305 | void clear() { | |||
306 | RegSrcs.clear(); | |||
307 | Inst = nullptr; | |||
308 | } | |||
309 | ||||
310 | void addSource(Register SrcReg, unsigned SrcSubReg) { | |||
311 | RegSrcs.push_back(RegSubRegPair(SrcReg, SrcSubReg)); | |||
312 | } | |||
313 | ||||
314 | void setSource(int Idx, Register SrcReg, unsigned SrcSubReg) { | |||
315 | assert(Idx < getNumSources() && "Reg pair source out of index")(static_cast <bool> (Idx < getNumSources() && "Reg pair source out of index") ? void (0) : __assert_fail ( "Idx < getNumSources() && \"Reg pair source out of index\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 315, __extension__ __PRETTY_FUNCTION__)); | |||
316 | RegSrcs[Idx] = RegSubRegPair(SrcReg, SrcSubReg); | |||
317 | } | |||
318 | ||||
319 | int getNumSources() const { return RegSrcs.size(); } | |||
320 | ||||
321 | RegSubRegPair getSrc(int Idx) const { | |||
322 | return RegSrcs[Idx]; | |||
323 | } | |||
324 | ||||
325 | Register getSrcReg(int Idx) const { | |||
326 | assert(Idx < getNumSources() && "Reg source out of index")(static_cast <bool> (Idx < getNumSources() && "Reg source out of index") ? void (0) : __assert_fail ("Idx < getNumSources() && \"Reg source out of index\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 326, __extension__ __PRETTY_FUNCTION__)); | |||
327 | return RegSrcs[Idx].Reg; | |||
328 | } | |||
329 | ||||
330 | unsigned getSrcSubReg(int Idx) const { | |||
331 | assert(Idx < getNumSources() && "SubReg source out of index")(static_cast <bool> (Idx < getNumSources() && "SubReg source out of index") ? void (0) : __assert_fail ("Idx < getNumSources() && \"SubReg source out of index\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 331, __extension__ __PRETTY_FUNCTION__)); | |||
332 | return RegSrcs[Idx].SubReg; | |||
333 | } | |||
334 | ||||
335 | bool operator==(const ValueTrackerResult &Other) const { | |||
336 | if (Other.getInst() != getInst()) | |||
337 | return false; | |||
338 | ||||
339 | if (Other.getNumSources() != getNumSources()) | |||
340 | return false; | |||
341 | ||||
342 | for (int i = 0, e = Other.getNumSources(); i != e; ++i) | |||
343 | if (Other.getSrcReg(i) != getSrcReg(i) || | |||
344 | Other.getSrcSubReg(i) != getSrcSubReg(i)) | |||
345 | return false; | |||
346 | return true; | |||
347 | } | |||
348 | }; | |||
349 | ||||
350 | /// Helper class to track the possible sources of a value defined by | |||
351 | /// a (chain of) copy related instructions. | |||
352 | /// Given a definition (instruction and definition index), this class | |||
353 | /// follows the use-def chain to find successive suitable sources. | |||
354 | /// The given source can be used to rewrite the definition into | |||
355 | /// def = COPY src. | |||
356 | /// | |||
357 | /// For instance, let us consider the following snippet: | |||
358 | /// v0 = | |||
359 | /// v2 = INSERT_SUBREG v1, v0, sub0 | |||
360 | /// def = COPY v2.sub0 | |||
361 | /// | |||
362 | /// Using a ValueTracker for def = COPY v2.sub0 will give the following | |||
363 | /// suitable sources: | |||
364 | /// v2.sub0 and v0. | |||
365 | /// Then, def can be rewritten into def = COPY v0. | |||
366 | class ValueTracker { | |||
367 | private: | |||
368 | /// The current point into the use-def chain. | |||
369 | const MachineInstr *Def = nullptr; | |||
370 | ||||
371 | /// The index of the definition in Def. | |||
372 | unsigned DefIdx = 0; | |||
373 | ||||
374 | /// The sub register index of the definition. | |||
375 | unsigned DefSubReg; | |||
376 | ||||
377 | /// The register where the value can be found. | |||
378 | Register Reg; | |||
379 | ||||
380 | /// MachineRegisterInfo used to perform tracking. | |||
381 | const MachineRegisterInfo &MRI; | |||
382 | ||||
383 | /// Optional TargetInstrInfo used to perform some complex tracking. | |||
384 | const TargetInstrInfo *TII; | |||
385 | ||||
386 | /// Dispatcher to the right underlying implementation of getNextSource. | |||
387 | ValueTrackerResult getNextSourceImpl(); | |||
388 | ||||
389 | /// Specialized version of getNextSource for Copy instructions. | |||
390 | ValueTrackerResult getNextSourceFromCopy(); | |||
391 | ||||
392 | /// Specialized version of getNextSource for Bitcast instructions. | |||
393 | ValueTrackerResult getNextSourceFromBitcast(); | |||
394 | ||||
395 | /// Specialized version of getNextSource for RegSequence instructions. | |||
396 | ValueTrackerResult getNextSourceFromRegSequence(); | |||
397 | ||||
398 | /// Specialized version of getNextSource for InsertSubreg instructions. | |||
399 | ValueTrackerResult getNextSourceFromInsertSubreg(); | |||
400 | ||||
401 | /// Specialized version of getNextSource for ExtractSubreg instructions. | |||
402 | ValueTrackerResult getNextSourceFromExtractSubreg(); | |||
403 | ||||
404 | /// Specialized version of getNextSource for SubregToReg instructions. | |||
405 | ValueTrackerResult getNextSourceFromSubregToReg(); | |||
406 | ||||
407 | /// Specialized version of getNextSource for PHI instructions. | |||
408 | ValueTrackerResult getNextSourceFromPHI(); | |||
409 | ||||
410 | public: | |||
411 | /// Create a ValueTracker instance for the value defined by \p Reg. | |||
412 | /// \p DefSubReg represents the sub register index the value tracker will | |||
413 | /// track. It does not need to match the sub register index used in the | |||
414 | /// definition of \p Reg. | |||
415 | /// If \p Reg is a physical register, a value tracker constructed with | |||
416 | /// this constructor will not find any alternative source. | |||
417 | /// Indeed, when \p Reg is a physical register that constructor does not | |||
418 | /// know which definition of \p Reg it should track. | |||
419 | /// Use the next constructor to track a physical register. | |||
420 | ValueTracker(Register Reg, unsigned DefSubReg, | |||
421 | const MachineRegisterInfo &MRI, | |||
422 | const TargetInstrInfo *TII = nullptr) | |||
423 | : DefSubReg(DefSubReg), Reg(Reg), MRI(MRI), TII(TII) { | |||
424 | if (!Reg.isPhysical()) { | |||
425 | Def = MRI.getVRegDef(Reg); | |||
426 | DefIdx = MRI.def_begin(Reg).getOperandNo(); | |||
427 | } | |||
428 | } | |||
429 | ||||
430 | /// Following the use-def chain, get the next available source | |||
431 | /// for the tracked value. | |||
432 | /// \return A ValueTrackerResult containing a set of registers | |||
433 | /// and sub registers with tracked values. A ValueTrackerResult with | |||
434 | /// an empty set of registers means no source was found. | |||
435 | ValueTrackerResult getNextSource(); | |||
436 | }; | |||
437 | ||||
438 | } // end anonymous namespace | |||
439 | ||||
440 | char PeepholeOptimizer::ID = 0; | |||
441 | ||||
442 | char &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID; | |||
443 | ||||
444 | INITIALIZE_PASS_BEGIN(PeepholeOptimizer, DEBUG_TYPE,static void *initializePeepholeOptimizerPassOnce(PassRegistry &Registry) { | |||
445 | "Peephole Optimizations", false, false)static void *initializePeepholeOptimizerPassOnce(PassRegistry &Registry) { | |||
446 | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)initializeMachineDominatorTreePass(Registry); | |||
447 | INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)initializeMachineLoopInfoPass(Registry); | |||
448 | INITIALIZE_PASS_END(PeepholeOptimizer, DEBUG_TYPE,PassInfo *PI = new PassInfo( "Peephole Optimizations", "peephole-opt" , &PeepholeOptimizer::ID, PassInfo::NormalCtor_t(callDefaultCtor <PeepholeOptimizer>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializePeepholeOptimizerPassFlag ; void llvm::initializePeepholeOptimizerPass(PassRegistry & Registry) { llvm::call_once(InitializePeepholeOptimizerPassFlag , initializePeepholeOptimizerPassOnce, std::ref(Registry)); } | |||
449 | "Peephole Optimizations", false, false)PassInfo *PI = new PassInfo( "Peephole Optimizations", "peephole-opt" , &PeepholeOptimizer::ID, PassInfo::NormalCtor_t(callDefaultCtor <PeepholeOptimizer>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializePeepholeOptimizerPassFlag ; void llvm::initializePeepholeOptimizerPass(PassRegistry & Registry) { llvm::call_once(InitializePeepholeOptimizerPassFlag , initializePeepholeOptimizerPassOnce, std::ref(Registry)); } | |||
450 | ||||
451 | /// If instruction is a copy-like instruction, i.e. it reads a single register | |||
452 | /// and writes a single register and it does not modify the source, and if the | |||
453 | /// source value is preserved as a sub-register of the result, then replace all | |||
454 | /// reachable uses of the source with the subreg of the result. | |||
455 | /// | |||
456 | /// Do not generate an EXTRACT that is used only in a debug use, as this changes | |||
457 | /// the code. Since this code does not currently share EXTRACTs, just ignore all | |||
458 | /// debug uses. | |||
459 | bool PeepholeOptimizer:: | |||
460 | optimizeExtInstr(MachineInstr &MI, MachineBasicBlock &MBB, | |||
461 | SmallPtrSetImpl<MachineInstr*> &LocalMIs) { | |||
462 | Register SrcReg, DstReg; | |||
463 | unsigned SubIdx; | |||
464 | if (!TII->isCoalescableExtInstr(MI, SrcReg, DstReg, SubIdx)) | |||
465 | return false; | |||
466 | ||||
467 | if (DstReg.isPhysical() || SrcReg.isPhysical()) | |||
468 | return false; | |||
469 | ||||
470 | if (MRI->hasOneNonDBGUse(SrcReg)) | |||
471 | // No other uses. | |||
472 | return false; | |||
473 | ||||
474 | // Ensure DstReg can get a register class that actually supports | |||
475 | // sub-registers. Don't change the class until we commit. | |||
476 | const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg); | |||
477 | DstRC = TRI->getSubClassWithSubReg(DstRC, SubIdx); | |||
478 | if (!DstRC) | |||
479 | return false; | |||
480 | ||||
481 | // The ext instr may be operating on a sub-register of SrcReg as well. | |||
482 | // PPC::EXTSW is a 32 -> 64-bit sign extension, but it reads a 64-bit | |||
483 | // register. | |||
484 | // If UseSrcSubIdx is Set, SubIdx also applies to SrcReg, and only uses of | |||
485 | // SrcReg:SubIdx should be replaced. | |||
486 | bool UseSrcSubIdx = | |||
487 | TRI->getSubClassWithSubReg(MRI->getRegClass(SrcReg), SubIdx) != nullptr; | |||
488 | ||||
489 | // The source has other uses. See if we can replace the other uses with use of | |||
490 | // the result of the extension. | |||
491 | SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs; | |||
492 | for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg)) | |||
493 | ReachedBBs.insert(UI.getParent()); | |||
494 | ||||
495 | // Uses that are in the same BB of uses of the result of the instruction. | |||
496 | SmallVector<MachineOperand*, 8> Uses; | |||
497 | ||||
498 | // Uses that the result of the instruction can reach. | |||
499 | SmallVector<MachineOperand*, 8> ExtendedUses; | |||
500 | ||||
501 | bool ExtendLife = true; | |||
502 | for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) { | |||
503 | MachineInstr *UseMI = UseMO.getParent(); | |||
504 | if (UseMI == &MI) | |||
505 | continue; | |||
506 | ||||
507 | if (UseMI->isPHI()) { | |||
508 | ExtendLife = false; | |||
509 | continue; | |||
510 | } | |||
511 | ||||
512 | // Only accept uses of SrcReg:SubIdx. | |||
513 | if (UseSrcSubIdx
| |||
514 | continue; | |||
515 | ||||
516 | // It's an error to translate this: | |||
517 | // | |||
518 | // %reg1025 = <sext> %reg1024 | |||
519 | // ... | |||
520 | // %reg1026 = SUBREG_TO_REG 0, %reg1024, 4 | |||
521 | // | |||
522 | // into this: | |||
523 | // | |||
524 | // %reg1025 = <sext> %reg1024 | |||
525 | // ... | |||
526 | // %reg1027 = COPY %reg1025:4 | |||
527 | // %reg1026 = SUBREG_TO_REG 0, %reg1027, 4 | |||
528 | // | |||
529 | // The problem here is that SUBREG_TO_REG is there to assert that an | |||
530 | // implicit zext occurs. It doesn't insert a zext instruction. If we allow | |||
531 | // the COPY here, it will give us the value after the <sext>, not the | |||
532 | // original value of %reg1024 before <sext>. | |||
533 | if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG) | |||
534 | continue; | |||
535 | ||||
536 | MachineBasicBlock *UseMBB = UseMI->getParent(); | |||
537 | if (UseMBB == &MBB) { | |||
538 | // Local uses that come after the extension. | |||
539 | if (!LocalMIs.count(UseMI)) | |||
540 | Uses.push_back(&UseMO); | |||
541 | } else if (ReachedBBs.count(UseMBB)) { | |||
542 | // Non-local uses where the result of the extension is used. Always | |||
543 | // replace these unless it's a PHI. | |||
544 | Uses.push_back(&UseMO); | |||
545 | } else if (Aggressive && DT->dominates(&MBB, UseMBB)) { | |||
| ||||
546 | // We may want to extend the live range of the extension result in order | |||
547 | // to replace these uses. | |||
548 | ExtendedUses.push_back(&UseMO); | |||
549 | } else { | |||
550 | // Both will be live out of the def MBB anyway. Don't extend live range of | |||
551 | // the extension result. | |||
552 | ExtendLife = false; | |||
553 | break; | |||
554 | } | |||
555 | } | |||
556 | ||||
557 | if (ExtendLife && !ExtendedUses.empty()) | |||
558 | // Extend the liveness of the extension result. | |||
559 | Uses.append(ExtendedUses.begin(), ExtendedUses.end()); | |||
560 | ||||
561 | // Now replace all uses. | |||
562 | bool Changed = false; | |||
563 | if (!Uses.empty()) { | |||
564 | SmallPtrSet<MachineBasicBlock*, 4> PHIBBs; | |||
565 | ||||
566 | // Look for PHI uses of the extended result, we don't want to extend the | |||
567 | // liveness of a PHI input. It breaks all kinds of assumptions down | |||
568 | // stream. A PHI use is expected to be the kill of its source values. | |||
569 | for (MachineInstr &UI : MRI->use_nodbg_instructions(DstReg)) | |||
570 | if (UI.isPHI()) | |||
571 | PHIBBs.insert(UI.getParent()); | |||
572 | ||||
573 | const TargetRegisterClass *RC = MRI->getRegClass(SrcReg); | |||
574 | for (unsigned i = 0, e = Uses.size(); i != e; ++i) { | |||
575 | MachineOperand *UseMO = Uses[i]; | |||
576 | MachineInstr *UseMI = UseMO->getParent(); | |||
577 | MachineBasicBlock *UseMBB = UseMI->getParent(); | |||
578 | if (PHIBBs.count(UseMBB)) | |||
579 | continue; | |||
580 | ||||
581 | // About to add uses of DstReg, clear DstReg's kill flags. | |||
582 | if (!Changed) { | |||
583 | MRI->clearKillFlags(DstReg); | |||
584 | MRI->constrainRegClass(DstReg, DstRC); | |||
585 | } | |||
586 | ||||
587 | // SubReg defs are illegal in machine SSA phase, | |||
588 | // we should not generate SubReg defs. | |||
589 | // | |||
590 | // For example, for the instructions: | |||
591 | // | |||
592 | // %1:g8rc_and_g8rc_nox0 = EXTSW %0:g8rc | |||
593 | // %3:gprc_and_gprc_nor0 = COPY %0.sub_32:g8rc | |||
594 | // | |||
595 | // We should generate: | |||
596 | // | |||
597 | // %1:g8rc_and_g8rc_nox0 = EXTSW %0:g8rc | |||
598 | // %6:gprc_and_gprc_nor0 = COPY %1.sub_32:g8rc_and_g8rc_nox0 | |||
599 | // %3:gprc_and_gprc_nor0 = COPY %6:gprc_and_gprc_nor0 | |||
600 | // | |||
601 | if (UseSrcSubIdx) | |||
602 | RC = MRI->getRegClass(UseMI->getOperand(0).getReg()); | |||
603 | ||||
604 | Register NewVR = MRI->createVirtualRegister(RC); | |||
605 | BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(), | |||
606 | TII->get(TargetOpcode::COPY), NewVR) | |||
607 | .addReg(DstReg, 0, SubIdx); | |||
608 | if (UseSrcSubIdx) | |||
609 | UseMO->setSubReg(0); | |||
610 | ||||
611 | UseMO->setReg(NewVR); | |||
612 | ++NumReuse; | |||
613 | Changed = true; | |||
614 | } | |||
615 | } | |||
616 | ||||
617 | return Changed; | |||
618 | } | |||
619 | ||||
620 | /// If the instruction is a compare and the previous instruction it's comparing | |||
621 | /// against already sets (or could be modified to set) the same flag as the | |||
622 | /// compare, then we can remove the comparison and use the flag from the | |||
623 | /// previous instruction. | |||
624 | bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr &MI) { | |||
625 | // If this instruction is a comparison against zero and isn't comparing a | |||
626 | // physical register, we can try to optimize it. | |||
627 | Register SrcReg, SrcReg2; | |||
628 | int64_t CmpMask, CmpValue; | |||
629 | if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) || | |||
630 | SrcReg.isPhysical() || SrcReg2.isPhysical()) | |||
631 | return false; | |||
632 | ||||
633 | // Attempt to optimize the comparison instruction. | |||
634 | LLVM_DEBUG(dbgs() << "Attempting to optimize compare: " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "Attempting to optimize compare: " << MI; } } while (false); | |||
635 | if (TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) { | |||
636 | LLVM_DEBUG(dbgs() << " -> Successfully optimized compare!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << " -> Successfully optimized compare!\n" ; } } while (false); | |||
637 | ++NumCmps; | |||
638 | return true; | |||
639 | } | |||
640 | ||||
641 | return false; | |||
642 | } | |||
643 | ||||
644 | /// Optimize a select instruction. | |||
645 | bool PeepholeOptimizer::optimizeSelect(MachineInstr &MI, | |||
646 | SmallPtrSetImpl<MachineInstr *> &LocalMIs) { | |||
647 | unsigned TrueOp = 0; | |||
648 | unsigned FalseOp = 0; | |||
649 | bool Optimizable = false; | |||
650 | SmallVector<MachineOperand, 4> Cond; | |||
651 | if (TII->analyzeSelect(MI, Cond, TrueOp, FalseOp, Optimizable)) | |||
652 | return false; | |||
653 | if (!Optimizable) | |||
654 | return false; | |||
655 | if (!TII->optimizeSelect(MI, LocalMIs)) | |||
656 | return false; | |||
657 | LLVM_DEBUG(dbgs() << "Deleting select: " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "Deleting select: " << MI; } } while (false); | |||
658 | MI.eraseFromParent(); | |||
659 | ++NumSelects; | |||
660 | return true; | |||
661 | } | |||
662 | ||||
663 | /// Check if a simpler conditional branch can be generated. | |||
664 | bool PeepholeOptimizer::optimizeCondBranch(MachineInstr &MI) { | |||
665 | return TII->optimizeCondBranch(MI); | |||
666 | } | |||
667 | ||||
668 | /// Try to find the next source that share the same register file | |||
669 | /// for the value defined by \p Reg and \p SubReg. | |||
670 | /// When true is returned, the \p RewriteMap can be used by the client to | |||
671 | /// retrieve all Def -> Use along the way up to the next source. Any found | |||
672 | /// Use that is not itself a key for another entry, is the next source to | |||
673 | /// use. During the search for the next source, multiple sources can be found | |||
674 | /// given multiple incoming sources of a PHI instruction. In this case, we | |||
675 | /// look in each PHI source for the next source; all found next sources must | |||
676 | /// share the same register file as \p Reg and \p SubReg. The client should | |||
677 | /// then be capable to rewrite all intermediate PHIs to get the next source. | |||
678 | /// \return False if no alternative sources are available. True otherwise. | |||
679 | bool PeepholeOptimizer::findNextSource(RegSubRegPair RegSubReg, | |||
680 | RewriteMapTy &RewriteMap) { | |||
681 | // Do not try to find a new source for a physical register. | |||
682 | // So far we do not have any motivating example for doing that. | |||
683 | // Thus, instead of maintaining untested code, we will revisit that if | |||
684 | // that changes at some point. | |||
685 | Register Reg = RegSubReg.Reg; | |||
686 | if (Reg.isPhysical()) | |||
687 | return false; | |||
688 | const TargetRegisterClass *DefRC = MRI->getRegClass(Reg); | |||
689 | ||||
690 | SmallVector<RegSubRegPair, 4> SrcToLook; | |||
691 | RegSubRegPair CurSrcPair = RegSubReg; | |||
692 | SrcToLook.push_back(CurSrcPair); | |||
693 | ||||
694 | unsigned PHICount = 0; | |||
695 | do { | |||
696 | CurSrcPair = SrcToLook.pop_back_val(); | |||
697 | // As explained above, do not handle physical registers | |||
698 | if (Register::isPhysicalRegister(CurSrcPair.Reg)) | |||
699 | return false; | |||
700 | ||||
701 | ValueTracker ValTracker(CurSrcPair.Reg, CurSrcPair.SubReg, *MRI, TII); | |||
702 | ||||
703 | // Follow the chain of copies until we find a more suitable source, a phi | |||
704 | // or have to abort. | |||
705 | while (true) { | |||
706 | ValueTrackerResult Res = ValTracker.getNextSource(); | |||
707 | // Abort at the end of a chain (without finding a suitable source). | |||
708 | if (!Res.isValid()) | |||
709 | return false; | |||
710 | ||||
711 | // Insert the Def -> Use entry for the recently found source. | |||
712 | ValueTrackerResult CurSrcRes = RewriteMap.lookup(CurSrcPair); | |||
713 | if (CurSrcRes.isValid()) { | |||
714 | assert(CurSrcRes == Res && "ValueTrackerResult found must match")(static_cast <bool> (CurSrcRes == Res && "ValueTrackerResult found must match" ) ? void (0) : __assert_fail ("CurSrcRes == Res && \"ValueTrackerResult found must match\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 714, __extension__ __PRETTY_FUNCTION__)); | |||
715 | // An existent entry with multiple sources is a PHI cycle we must avoid. | |||
716 | // Otherwise it's an entry with a valid next source we already found. | |||
717 | if (CurSrcRes.getNumSources() > 1) { | |||
718 | LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "findNextSource: found PHI cycle, aborting...\n" ; } } while (false) | |||
719 | << "findNextSource: found PHI cycle, aborting...\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "findNextSource: found PHI cycle, aborting...\n" ; } } while (false); | |||
720 | return false; | |||
721 | } | |||
722 | break; | |||
723 | } | |||
724 | RewriteMap.insert(std::make_pair(CurSrcPair, Res)); | |||
725 | ||||
726 | // ValueTrackerResult usually have one source unless it's the result from | |||
727 | // a PHI instruction. Add the found PHI edges to be looked up further. | |||
728 | unsigned NumSrcs = Res.getNumSources(); | |||
729 | if (NumSrcs > 1) { | |||
730 | PHICount++; | |||
731 | if (PHICount >= RewritePHILimit) { | |||
732 | LLVM_DEBUG(dbgs() << "findNextSource: PHI limit reached\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "findNextSource: PHI limit reached\n" ; } } while (false); | |||
733 | return false; | |||
734 | } | |||
735 | ||||
736 | for (unsigned i = 0; i < NumSrcs; ++i) | |||
737 | SrcToLook.push_back(Res.getSrc(i)); | |||
738 | break; | |||
739 | } | |||
740 | ||||
741 | CurSrcPair = Res.getSrc(0); | |||
742 | // Do not extend the live-ranges of physical registers as they add | |||
743 | // constraints to the register allocator. Moreover, if we want to extend | |||
744 | // the live-range of a physical register, unlike SSA virtual register, | |||
745 | // we will have to check that they aren't redefine before the related use. | |||
746 | if (Register::isPhysicalRegister(CurSrcPair.Reg)) | |||
747 | return false; | |||
748 | ||||
749 | // Keep following the chain if the value isn't any better yet. | |||
750 | const TargetRegisterClass *SrcRC = MRI->getRegClass(CurSrcPair.Reg); | |||
751 | if (!TRI->shouldRewriteCopySrc(DefRC, RegSubReg.SubReg, SrcRC, | |||
752 | CurSrcPair.SubReg)) | |||
753 | continue; | |||
754 | ||||
755 | // We currently cannot deal with subreg operands on PHI instructions | |||
756 | // (see insertPHI()). | |||
757 | if (PHICount > 0 && CurSrcPair.SubReg != 0) | |||
758 | continue; | |||
759 | ||||
760 | // We found a suitable source, and are done with this chain. | |||
761 | break; | |||
762 | } | |||
763 | } while (!SrcToLook.empty()); | |||
764 | ||||
765 | // If we did not find a more suitable source, there is nothing to optimize. | |||
766 | return CurSrcPair.Reg != Reg; | |||
767 | } | |||
768 | ||||
769 | /// Insert a PHI instruction with incoming edges \p SrcRegs that are | |||
770 | /// guaranteed to have the same register class. This is necessary whenever we | |||
771 | /// successfully traverse a PHI instruction and find suitable sources coming | |||
772 | /// from its edges. By inserting a new PHI, we provide a rewritten PHI def | |||
773 | /// suitable to be used in a new COPY instruction. | |||
774 | static MachineInstr & | |||
775 | insertPHI(MachineRegisterInfo &MRI, const TargetInstrInfo &TII, | |||
776 | const SmallVectorImpl<RegSubRegPair> &SrcRegs, | |||
777 | MachineInstr &OrigPHI) { | |||
778 | assert(!SrcRegs.empty() && "No sources to create a PHI instruction?")(static_cast <bool> (!SrcRegs.empty() && "No sources to create a PHI instruction?" ) ? void (0) : __assert_fail ("!SrcRegs.empty() && \"No sources to create a PHI instruction?\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 778, __extension__ __PRETTY_FUNCTION__)); | |||
779 | ||||
780 | const TargetRegisterClass *NewRC = MRI.getRegClass(SrcRegs[0].Reg); | |||
781 | // NewRC is only correct if no subregisters are involved. findNextSource() | |||
782 | // should have rejected those cases already. | |||
783 | assert(SrcRegs[0].SubReg == 0 && "should not have subreg operand")(static_cast <bool> (SrcRegs[0].SubReg == 0 && "should not have subreg operand" ) ? void (0) : __assert_fail ("SrcRegs[0].SubReg == 0 && \"should not have subreg operand\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 783, __extension__ __PRETTY_FUNCTION__)); | |||
784 | Register NewVR = MRI.createVirtualRegister(NewRC); | |||
785 | MachineBasicBlock *MBB = OrigPHI.getParent(); | |||
786 | MachineInstrBuilder MIB = BuildMI(*MBB, &OrigPHI, OrigPHI.getDebugLoc(), | |||
787 | TII.get(TargetOpcode::PHI), NewVR); | |||
788 | ||||
789 | unsigned MBBOpIdx = 2; | |||
790 | for (const RegSubRegPair &RegPair : SrcRegs) { | |||
791 | MIB.addReg(RegPair.Reg, 0, RegPair.SubReg); | |||
792 | MIB.addMBB(OrigPHI.getOperand(MBBOpIdx).getMBB()); | |||
793 | // Since we're extended the lifetime of RegPair.Reg, clear the | |||
794 | // kill flags to account for that and make RegPair.Reg reaches | |||
795 | // the new PHI. | |||
796 | MRI.clearKillFlags(RegPair.Reg); | |||
797 | MBBOpIdx += 2; | |||
798 | } | |||
799 | ||||
800 | return *MIB; | |||
801 | } | |||
802 | ||||
803 | namespace { | |||
804 | ||||
805 | /// Interface to query instructions amenable to copy rewriting. | |||
806 | class Rewriter { | |||
807 | protected: | |||
808 | MachineInstr &CopyLike; | |||
809 | unsigned CurrentSrcIdx = 0; ///< The index of the source being rewritten. | |||
810 | public: | |||
811 | Rewriter(MachineInstr &CopyLike) : CopyLike(CopyLike) {} | |||
812 | virtual ~Rewriter() = default; | |||
813 | ||||
814 | /// Get the next rewritable source (SrcReg, SrcSubReg) and | |||
815 | /// the related value that it affects (DstReg, DstSubReg). | |||
816 | /// A source is considered rewritable if its register class and the | |||
817 | /// register class of the related DstReg may not be register | |||
818 | /// coalescer friendly. In other words, given a copy-like instruction | |||
819 | /// not all the arguments may be returned at rewritable source, since | |||
820 | /// some arguments are none to be register coalescer friendly. | |||
821 | /// | |||
822 | /// Each call of this method moves the current source to the next | |||
823 | /// rewritable source. | |||
824 | /// For instance, let CopyLike be the instruction to rewrite. | |||
825 | /// CopyLike has one definition and one source: | |||
826 | /// dst.dstSubIdx = CopyLike src.srcSubIdx. | |||
827 | /// | |||
828 | /// The first call will give the first rewritable source, i.e., | |||
829 | /// the only source this instruction has: | |||
830 | /// (SrcReg, SrcSubReg) = (src, srcSubIdx). | |||
831 | /// This source defines the whole definition, i.e., | |||
832 | /// (DstReg, DstSubReg) = (dst, dstSubIdx). | |||
833 | /// | |||
834 | /// The second and subsequent calls will return false, as there is only one | |||
835 | /// rewritable source. | |||
836 | /// | |||
837 | /// \return True if a rewritable source has been found, false otherwise. | |||
838 | /// The output arguments are valid if and only if true is returned. | |||
839 | virtual bool getNextRewritableSource(RegSubRegPair &Src, | |||
840 | RegSubRegPair &Dst) = 0; | |||
841 | ||||
842 | /// Rewrite the current source with \p NewReg and \p NewSubReg if possible. | |||
843 | /// \return True if the rewriting was possible, false otherwise. | |||
844 | virtual bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) = 0; | |||
845 | }; | |||
846 | ||||
847 | /// Rewriter for COPY instructions. | |||
848 | class CopyRewriter : public Rewriter { | |||
849 | public: | |||
850 | CopyRewriter(MachineInstr &MI) : Rewriter(MI) { | |||
851 | assert(MI.isCopy() && "Expected copy instruction")(static_cast <bool> (MI.isCopy() && "Expected copy instruction" ) ? void (0) : __assert_fail ("MI.isCopy() && \"Expected copy instruction\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 851, __extension__ __PRETTY_FUNCTION__)); | |||
852 | } | |||
853 | virtual ~CopyRewriter() = default; | |||
854 | ||||
855 | bool getNextRewritableSource(RegSubRegPair &Src, | |||
856 | RegSubRegPair &Dst) override { | |||
857 | // CurrentSrcIdx > 0 means this function has already been called. | |||
858 | if (CurrentSrcIdx > 0) | |||
859 | return false; | |||
860 | // This is the first call to getNextRewritableSource. | |||
861 | // Move the CurrentSrcIdx to remember that we made that call. | |||
862 | CurrentSrcIdx = 1; | |||
863 | // The rewritable source is the argument. | |||
864 | const MachineOperand &MOSrc = CopyLike.getOperand(1); | |||
865 | Src = RegSubRegPair(MOSrc.getReg(), MOSrc.getSubReg()); | |||
866 | // What we track are the alternative sources of the definition. | |||
867 | const MachineOperand &MODef = CopyLike.getOperand(0); | |||
868 | Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg()); | |||
869 | return true; | |||
870 | } | |||
871 | ||||
872 | bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override { | |||
873 | if (CurrentSrcIdx != 1) | |||
874 | return false; | |||
875 | MachineOperand &MOSrc = CopyLike.getOperand(CurrentSrcIdx); | |||
876 | MOSrc.setReg(NewReg); | |||
877 | MOSrc.setSubReg(NewSubReg); | |||
878 | return true; | |||
879 | } | |||
880 | }; | |||
881 | ||||
882 | /// Helper class to rewrite uncoalescable copy like instructions | |||
883 | /// into new COPY (coalescable friendly) instructions. | |||
884 | class UncoalescableRewriter : public Rewriter { | |||
885 | unsigned NumDefs; ///< Number of defs in the bitcast. | |||
886 | ||||
887 | public: | |||
888 | UncoalescableRewriter(MachineInstr &MI) : Rewriter(MI) { | |||
889 | NumDefs = MI.getDesc().getNumDefs(); | |||
890 | } | |||
891 | ||||
892 | /// \see See Rewriter::getNextRewritableSource() | |||
893 | /// All such sources need to be considered rewritable in order to | |||
894 | /// rewrite a uncoalescable copy-like instruction. This method return | |||
895 | /// each definition that must be checked if rewritable. | |||
896 | bool getNextRewritableSource(RegSubRegPair &Src, | |||
897 | RegSubRegPair &Dst) override { | |||
898 | // Find the next non-dead definition and continue from there. | |||
899 | if (CurrentSrcIdx == NumDefs) | |||
900 | return false; | |||
901 | ||||
902 | while (CopyLike.getOperand(CurrentSrcIdx).isDead()) { | |||
903 | ++CurrentSrcIdx; | |||
904 | if (CurrentSrcIdx == NumDefs) | |||
905 | return false; | |||
906 | } | |||
907 | ||||
908 | // What we track are the alternative sources of the definition. | |||
909 | Src = RegSubRegPair(0, 0); | |||
910 | const MachineOperand &MODef = CopyLike.getOperand(CurrentSrcIdx); | |||
911 | Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg()); | |||
912 | ||||
913 | CurrentSrcIdx++; | |||
914 | return true; | |||
915 | } | |||
916 | ||||
917 | bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override { | |||
918 | return false; | |||
919 | } | |||
920 | }; | |||
921 | ||||
922 | /// Specialized rewriter for INSERT_SUBREG instruction. | |||
923 | class InsertSubregRewriter : public Rewriter { | |||
924 | public: | |||
925 | InsertSubregRewriter(MachineInstr &MI) : Rewriter(MI) { | |||
926 | assert(MI.isInsertSubreg() && "Invalid instruction")(static_cast <bool> (MI.isInsertSubreg() && "Invalid instruction" ) ? void (0) : __assert_fail ("MI.isInsertSubreg() && \"Invalid instruction\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 926, __extension__ __PRETTY_FUNCTION__)); | |||
927 | } | |||
928 | ||||
929 | /// \see See Rewriter::getNextRewritableSource() | |||
930 | /// Here CopyLike has the following form: | |||
931 | /// dst = INSERT_SUBREG Src1, Src2.src2SubIdx, subIdx. | |||
932 | /// Src1 has the same register class has dst, hence, there is | |||
933 | /// nothing to rewrite. | |||
934 | /// Src2.src2SubIdx, may not be register coalescer friendly. | |||
935 | /// Therefore, the first call to this method returns: | |||
936 | /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx). | |||
937 | /// (DstReg, DstSubReg) = (dst, subIdx). | |||
938 | /// | |||
939 | /// Subsequence calls will return false. | |||
940 | bool getNextRewritableSource(RegSubRegPair &Src, | |||
941 | RegSubRegPair &Dst) override { | |||
942 | // If we already get the only source we can rewrite, return false. | |||
943 | if (CurrentSrcIdx == 2) | |||
944 | return false; | |||
945 | // We are looking at v2 = INSERT_SUBREG v0, v1, sub0. | |||
946 | CurrentSrcIdx = 2; | |||
947 | const MachineOperand &MOInsertedReg = CopyLike.getOperand(2); | |||
948 | Src = RegSubRegPair(MOInsertedReg.getReg(), MOInsertedReg.getSubReg()); | |||
949 | const MachineOperand &MODef = CopyLike.getOperand(0); | |||
950 | ||||
951 | // We want to track something that is compatible with the | |||
952 | // partial definition. | |||
953 | if (MODef.getSubReg()) | |||
954 | // Bail if we have to compose sub-register indices. | |||
955 | return false; | |||
956 | Dst = RegSubRegPair(MODef.getReg(), | |||
957 | (unsigned)CopyLike.getOperand(3).getImm()); | |||
958 | return true; | |||
959 | } | |||
960 | ||||
961 | bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override { | |||
962 | if (CurrentSrcIdx != 2) | |||
963 | return false; | |||
964 | // We are rewriting the inserted reg. | |||
965 | MachineOperand &MO = CopyLike.getOperand(CurrentSrcIdx); | |||
966 | MO.setReg(NewReg); | |||
967 | MO.setSubReg(NewSubReg); | |||
968 | return true; | |||
969 | } | |||
970 | }; | |||
971 | ||||
972 | /// Specialized rewriter for EXTRACT_SUBREG instruction. | |||
973 | class ExtractSubregRewriter : public Rewriter { | |||
974 | const TargetInstrInfo &TII; | |||
975 | ||||
976 | public: | |||
977 | ExtractSubregRewriter(MachineInstr &MI, const TargetInstrInfo &TII) | |||
978 | : Rewriter(MI), TII(TII) { | |||
979 | assert(MI.isExtractSubreg() && "Invalid instruction")(static_cast <bool> (MI.isExtractSubreg() && "Invalid instruction" ) ? void (0) : __assert_fail ("MI.isExtractSubreg() && \"Invalid instruction\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 979, __extension__ __PRETTY_FUNCTION__)); | |||
980 | } | |||
981 | ||||
982 | /// \see Rewriter::getNextRewritableSource() | |||
983 | /// Here CopyLike has the following form: | |||
984 | /// dst.dstSubIdx = EXTRACT_SUBREG Src, subIdx. | |||
985 | /// There is only one rewritable source: Src.subIdx, | |||
986 | /// which defines dst.dstSubIdx. | |||
987 | bool getNextRewritableSource(RegSubRegPair &Src, | |||
988 | RegSubRegPair &Dst) override { | |||
989 | // If we already get the only source we can rewrite, return false. | |||
990 | if (CurrentSrcIdx == 1) | |||
991 | return false; | |||
992 | // We are looking at v1 = EXTRACT_SUBREG v0, sub0. | |||
993 | CurrentSrcIdx = 1; | |||
994 | const MachineOperand &MOExtractedReg = CopyLike.getOperand(1); | |||
995 | // If we have to compose sub-register indices, bail out. | |||
996 | if (MOExtractedReg.getSubReg()) | |||
997 | return false; | |||
998 | ||||
999 | Src = RegSubRegPair(MOExtractedReg.getReg(), | |||
1000 | CopyLike.getOperand(2).getImm()); | |||
1001 | ||||
1002 | // We want to track something that is compatible with the definition. | |||
1003 | const MachineOperand &MODef = CopyLike.getOperand(0); | |||
1004 | Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg()); | |||
1005 | return true; | |||
1006 | } | |||
1007 | ||||
1008 | bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override { | |||
1009 | // The only source we can rewrite is the input register. | |||
1010 | if (CurrentSrcIdx != 1) | |||
1011 | return false; | |||
1012 | ||||
1013 | CopyLike.getOperand(CurrentSrcIdx).setReg(NewReg); | |||
1014 | ||||
1015 | // If we find a source that does not require to extract something, | |||
1016 | // rewrite the operation with a copy. | |||
1017 | if (!NewSubReg) { | |||
1018 | // Move the current index to an invalid position. | |||
1019 | // We do not want another call to this method to be able | |||
1020 | // to do any change. | |||
1021 | CurrentSrcIdx = -1; | |||
1022 | // Rewrite the operation as a COPY. | |||
1023 | // Get rid of the sub-register index. | |||
1024 | CopyLike.removeOperand(2); | |||
1025 | // Morph the operation into a COPY. | |||
1026 | CopyLike.setDesc(TII.get(TargetOpcode::COPY)); | |||
1027 | return true; | |||
1028 | } | |||
1029 | CopyLike.getOperand(CurrentSrcIdx + 1).setImm(NewSubReg); | |||
1030 | return true; | |||
1031 | } | |||
1032 | }; | |||
1033 | ||||
1034 | /// Specialized rewriter for REG_SEQUENCE instruction. | |||
1035 | class RegSequenceRewriter : public Rewriter { | |||
1036 | public: | |||
1037 | RegSequenceRewriter(MachineInstr &MI) : Rewriter(MI) { | |||
1038 | assert(MI.isRegSequence() && "Invalid instruction")(static_cast <bool> (MI.isRegSequence() && "Invalid instruction" ) ? void (0) : __assert_fail ("MI.isRegSequence() && \"Invalid instruction\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1038, __extension__ __PRETTY_FUNCTION__)); | |||
1039 | } | |||
1040 | ||||
1041 | /// \see Rewriter::getNextRewritableSource() | |||
1042 | /// Here CopyLike has the following form: | |||
1043 | /// dst = REG_SEQUENCE Src1.src1SubIdx, subIdx1, Src2.src2SubIdx, subIdx2. | |||
1044 | /// Each call will return a different source, walking all the available | |||
1045 | /// source. | |||
1046 | /// | |||
1047 | /// The first call returns: | |||
1048 | /// (SrcReg, SrcSubReg) = (Src1, src1SubIdx). | |||
1049 | /// (DstReg, DstSubReg) = (dst, subIdx1). | |||
1050 | /// | |||
1051 | /// The second call returns: | |||
1052 | /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx). | |||
1053 | /// (DstReg, DstSubReg) = (dst, subIdx2). | |||
1054 | /// | |||
1055 | /// And so on, until all the sources have been traversed, then | |||
1056 | /// it returns false. | |||
1057 | bool getNextRewritableSource(RegSubRegPair &Src, | |||
1058 | RegSubRegPair &Dst) override { | |||
1059 | // We are looking at v0 = REG_SEQUENCE v1, sub1, v2, sub2, etc. | |||
1060 | ||||
1061 | // If this is the first call, move to the first argument. | |||
1062 | if (CurrentSrcIdx == 0) { | |||
1063 | CurrentSrcIdx = 1; | |||
1064 | } else { | |||
1065 | // Otherwise, move to the next argument and check that it is valid. | |||
1066 | CurrentSrcIdx += 2; | |||
1067 | if (CurrentSrcIdx >= CopyLike.getNumOperands()) | |||
1068 | return false; | |||
1069 | } | |||
1070 | const MachineOperand &MOInsertedReg = CopyLike.getOperand(CurrentSrcIdx); | |||
1071 | Src.Reg = MOInsertedReg.getReg(); | |||
1072 | // If we have to compose sub-register indices, bail out. | |||
1073 | if ((Src.SubReg = MOInsertedReg.getSubReg())) | |||
1074 | return false; | |||
1075 | ||||
1076 | // We want to track something that is compatible with the related | |||
1077 | // partial definition. | |||
1078 | Dst.SubReg = CopyLike.getOperand(CurrentSrcIdx + 1).getImm(); | |||
1079 | ||||
1080 | const MachineOperand &MODef = CopyLike.getOperand(0); | |||
1081 | Dst.Reg = MODef.getReg(); | |||
1082 | // If we have to compose sub-registers, bail. | |||
1083 | return MODef.getSubReg() == 0; | |||
1084 | } | |||
1085 | ||||
1086 | bool RewriteCurrentSource(Register NewReg, unsigned NewSubReg) override { | |||
1087 | // We cannot rewrite out of bound operands. | |||
1088 | // Moreover, rewritable sources are at odd positions. | |||
1089 | if ((CurrentSrcIdx & 1) != 1 || CurrentSrcIdx > CopyLike.getNumOperands()) | |||
1090 | return false; | |||
1091 | ||||
1092 | MachineOperand &MO = CopyLike.getOperand(CurrentSrcIdx); | |||
1093 | MO.setReg(NewReg); | |||
1094 | MO.setSubReg(NewSubReg); | |||
1095 | return true; | |||
1096 | } | |||
1097 | }; | |||
1098 | ||||
1099 | } // end anonymous namespace | |||
1100 | ||||
1101 | /// Get the appropriated Rewriter for \p MI. | |||
1102 | /// \return A pointer to a dynamically allocated Rewriter or nullptr if no | |||
1103 | /// rewriter works for \p MI. | |||
1104 | static Rewriter *getCopyRewriter(MachineInstr &MI, const TargetInstrInfo &TII) { | |||
1105 | // Handle uncoalescable copy-like instructions. | |||
1106 | if (MI.isBitcast() || MI.isRegSequenceLike() || MI.isInsertSubregLike() || | |||
1107 | MI.isExtractSubregLike()) | |||
1108 | return new UncoalescableRewriter(MI); | |||
1109 | ||||
1110 | switch (MI.getOpcode()) { | |||
1111 | default: | |||
1112 | return nullptr; | |||
1113 | case TargetOpcode::COPY: | |||
1114 | return new CopyRewriter(MI); | |||
1115 | case TargetOpcode::INSERT_SUBREG: | |||
1116 | return new InsertSubregRewriter(MI); | |||
1117 | case TargetOpcode::EXTRACT_SUBREG: | |||
1118 | return new ExtractSubregRewriter(MI, TII); | |||
1119 | case TargetOpcode::REG_SEQUENCE: | |||
1120 | return new RegSequenceRewriter(MI); | |||
1121 | } | |||
1122 | } | |||
1123 | ||||
1124 | /// Given a \p Def.Reg and Def.SubReg pair, use \p RewriteMap to find | |||
1125 | /// the new source to use for rewrite. If \p HandleMultipleSources is true and | |||
1126 | /// multiple sources for a given \p Def are found along the way, we found a | |||
1127 | /// PHI instructions that needs to be rewritten. | |||
1128 | /// TODO: HandleMultipleSources should be removed once we test PHI handling | |||
1129 | /// with coalescable copies. | |||
1130 | static RegSubRegPair | |||
1131 | getNewSource(MachineRegisterInfo *MRI, const TargetInstrInfo *TII, | |||
1132 | RegSubRegPair Def, | |||
1133 | const PeepholeOptimizer::RewriteMapTy &RewriteMap, | |||
1134 | bool HandleMultipleSources = true) { | |||
1135 | RegSubRegPair LookupSrc(Def.Reg, Def.SubReg); | |||
1136 | while (true) { | |||
1137 | ValueTrackerResult Res = RewriteMap.lookup(LookupSrc); | |||
1138 | // If there are no entries on the map, LookupSrc is the new source. | |||
1139 | if (!Res.isValid()) | |||
1140 | return LookupSrc; | |||
1141 | ||||
1142 | // There's only one source for this definition, keep searching... | |||
1143 | unsigned NumSrcs = Res.getNumSources(); | |||
1144 | if (NumSrcs == 1) { | |||
1145 | LookupSrc.Reg = Res.getSrcReg(0); | |||
1146 | LookupSrc.SubReg = Res.getSrcSubReg(0); | |||
1147 | continue; | |||
1148 | } | |||
1149 | ||||
1150 | // TODO: Remove once multiple srcs w/ coalescable copies are supported. | |||
1151 | if (!HandleMultipleSources) | |||
1152 | break; | |||
1153 | ||||
1154 | // Multiple sources, recurse into each source to find a new source | |||
1155 | // for it. Then, rewrite the PHI accordingly to its new edges. | |||
1156 | SmallVector<RegSubRegPair, 4> NewPHISrcs; | |||
1157 | for (unsigned i = 0; i < NumSrcs; ++i) { | |||
1158 | RegSubRegPair PHISrc(Res.getSrcReg(i), Res.getSrcSubReg(i)); | |||
1159 | NewPHISrcs.push_back( | |||
1160 | getNewSource(MRI, TII, PHISrc, RewriteMap, HandleMultipleSources)); | |||
1161 | } | |||
1162 | ||||
1163 | // Build the new PHI node and return its def register as the new source. | |||
1164 | MachineInstr &OrigPHI = const_cast<MachineInstr &>(*Res.getInst()); | |||
1165 | MachineInstr &NewPHI = insertPHI(*MRI, *TII, NewPHISrcs, OrigPHI); | |||
1166 | LLVM_DEBUG(dbgs() << "-- getNewSource\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "-- getNewSource\n"; } } while (false); | |||
1167 | LLVM_DEBUG(dbgs() << " Replacing: " << OrigPHI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << " Replacing: " << OrigPHI; } } while (false); | |||
1168 | LLVM_DEBUG(dbgs() << " With: " << NewPHI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << " With: " << NewPHI; } } while (false); | |||
1169 | const MachineOperand &MODef = NewPHI.getOperand(0); | |||
1170 | return RegSubRegPair(MODef.getReg(), MODef.getSubReg()); | |||
1171 | } | |||
1172 | ||||
1173 | return RegSubRegPair(0, 0); | |||
1174 | } | |||
1175 | ||||
1176 | /// Optimize generic copy instructions to avoid cross register bank copy. | |||
1177 | /// The optimization looks through a chain of copies and tries to find a source | |||
1178 | /// that has a compatible register class. | |||
1179 | /// Two register classes are considered to be compatible if they share the same | |||
1180 | /// register bank. | |||
1181 | /// New copies issued by this optimization are register allocator | |||
1182 | /// friendly. This optimization does not remove any copy as it may | |||
1183 | /// overconstrain the register allocator, but replaces some operands | |||
1184 | /// when possible. | |||
1185 | /// \pre isCoalescableCopy(*MI) is true. | |||
1186 | /// \return True, when \p MI has been rewritten. False otherwise. | |||
1187 | bool PeepholeOptimizer::optimizeCoalescableCopy(MachineInstr &MI) { | |||
1188 | assert(isCoalescableCopy(MI) && "Invalid argument")(static_cast <bool> (isCoalescableCopy(MI) && "Invalid argument" ) ? void (0) : __assert_fail ("isCoalescableCopy(MI) && \"Invalid argument\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1188, __extension__ __PRETTY_FUNCTION__)); | |||
1189 | assert(MI.getDesc().getNumDefs() == 1 &&(static_cast <bool> (MI.getDesc().getNumDefs() == 1 && "Coalescer can understand multiple defs?!") ? void (0) : __assert_fail ("MI.getDesc().getNumDefs() == 1 && \"Coalescer can understand multiple defs?!\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1190, __extension__ __PRETTY_FUNCTION__)) | |||
1190 | "Coalescer can understand multiple defs?!")(static_cast <bool> (MI.getDesc().getNumDefs() == 1 && "Coalescer can understand multiple defs?!") ? void (0) : __assert_fail ("MI.getDesc().getNumDefs() == 1 && \"Coalescer can understand multiple defs?!\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1190, __extension__ __PRETTY_FUNCTION__)); | |||
1191 | const MachineOperand &MODef = MI.getOperand(0); | |||
1192 | // Do not rewrite physical definitions. | |||
1193 | if (Register::isPhysicalRegister(MODef.getReg())) | |||
1194 | return false; | |||
1195 | ||||
1196 | bool Changed = false; | |||
1197 | // Get the right rewriter for the current copy. | |||
1198 | std::unique_ptr<Rewriter> CpyRewriter(getCopyRewriter(MI, *TII)); | |||
1199 | // If none exists, bail out. | |||
1200 | if (!CpyRewriter) | |||
1201 | return false; | |||
1202 | // Rewrite each rewritable source. | |||
1203 | RegSubRegPair Src; | |||
1204 | RegSubRegPair TrackPair; | |||
1205 | while (CpyRewriter->getNextRewritableSource(Src, TrackPair)) { | |||
1206 | // Keep track of PHI nodes and its incoming edges when looking for sources. | |||
1207 | RewriteMapTy RewriteMap; | |||
1208 | // Try to find a more suitable source. If we failed to do so, or get the | |||
1209 | // actual source, move to the next source. | |||
1210 | if (!findNextSource(TrackPair, RewriteMap)) | |||
1211 | continue; | |||
1212 | ||||
1213 | // Get the new source to rewrite. TODO: Only enable handling of multiple | |||
1214 | // sources (PHIs) once we have a motivating example and testcases for it. | |||
1215 | RegSubRegPair NewSrc = getNewSource(MRI, TII, TrackPair, RewriteMap, | |||
1216 | /*HandleMultipleSources=*/false); | |||
1217 | if (Src.Reg == NewSrc.Reg || NewSrc.Reg == 0) | |||
1218 | continue; | |||
1219 | ||||
1220 | // Rewrite source. | |||
1221 | if (CpyRewriter->RewriteCurrentSource(NewSrc.Reg, NewSrc.SubReg)) { | |||
1222 | // We may have extended the live-range of NewSrc, account for that. | |||
1223 | MRI->clearKillFlags(NewSrc.Reg); | |||
1224 | Changed = true; | |||
1225 | } | |||
1226 | } | |||
1227 | // TODO: We could have a clean-up method to tidy the instruction. | |||
1228 | // E.g., v0 = INSERT_SUBREG v1, v1.sub0, sub0 | |||
1229 | // => v0 = COPY v1 | |||
1230 | // Currently we haven't seen motivating example for that and we | |||
1231 | // want to avoid untested code. | |||
1232 | NumRewrittenCopies += Changed; | |||
1233 | return Changed; | |||
1234 | } | |||
1235 | ||||
1236 | /// Rewrite the source found through \p Def, by using the \p RewriteMap | |||
1237 | /// and create a new COPY instruction. More info about RewriteMap in | |||
1238 | /// PeepholeOptimizer::findNextSource. Right now this is only used to handle | |||
1239 | /// Uncoalescable copies, since they are copy like instructions that aren't | |||
1240 | /// recognized by the register allocator. | |||
1241 | MachineInstr & | |||
1242 | PeepholeOptimizer::rewriteSource(MachineInstr &CopyLike, | |||
1243 | RegSubRegPair Def, RewriteMapTy &RewriteMap) { | |||
1244 | assert(!Register::isPhysicalRegister(Def.Reg) &&(static_cast <bool> (!Register::isPhysicalRegister(Def. Reg) && "We do not rewrite physical registers") ? void (0) : __assert_fail ("!Register::isPhysicalRegister(Def.Reg) && \"We do not rewrite physical registers\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1245, __extension__ __PRETTY_FUNCTION__)) | |||
1245 | "We do not rewrite physical registers")(static_cast <bool> (!Register::isPhysicalRegister(Def. Reg) && "We do not rewrite physical registers") ? void (0) : __assert_fail ("!Register::isPhysicalRegister(Def.Reg) && \"We do not rewrite physical registers\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1245, __extension__ __PRETTY_FUNCTION__)); | |||
1246 | ||||
1247 | // Find the new source to use in the COPY rewrite. | |||
1248 | RegSubRegPair NewSrc = getNewSource(MRI, TII, Def, RewriteMap); | |||
1249 | ||||
1250 | // Insert the COPY. | |||
1251 | const TargetRegisterClass *DefRC = MRI->getRegClass(Def.Reg); | |||
1252 | Register NewVReg = MRI->createVirtualRegister(DefRC); | |||
1253 | ||||
1254 | MachineInstr *NewCopy = | |||
1255 | BuildMI(*CopyLike.getParent(), &CopyLike, CopyLike.getDebugLoc(), | |||
1256 | TII->get(TargetOpcode::COPY), NewVReg) | |||
1257 | .addReg(NewSrc.Reg, 0, NewSrc.SubReg); | |||
1258 | ||||
1259 | if (Def.SubReg) { | |||
1260 | NewCopy->getOperand(0).setSubReg(Def.SubReg); | |||
1261 | NewCopy->getOperand(0).setIsUndef(); | |||
1262 | } | |||
1263 | ||||
1264 | LLVM_DEBUG(dbgs() << "-- RewriteSource\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "-- RewriteSource\n"; } } while (false); | |||
1265 | LLVM_DEBUG(dbgs() << " Replacing: " << CopyLike)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << " Replacing: " << CopyLike; } } while (false); | |||
1266 | LLVM_DEBUG(dbgs() << " With: " << *NewCopy)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << " With: " << *NewCopy; } } while (false); | |||
1267 | MRI->replaceRegWith(Def.Reg, NewVReg); | |||
1268 | MRI->clearKillFlags(NewVReg); | |||
1269 | ||||
1270 | // We extended the lifetime of NewSrc.Reg, clear the kill flags to | |||
1271 | // account for that. | |||
1272 | MRI->clearKillFlags(NewSrc.Reg); | |||
1273 | ||||
1274 | return *NewCopy; | |||
1275 | } | |||
1276 | ||||
1277 | /// Optimize copy-like instructions to create | |||
1278 | /// register coalescer friendly instruction. | |||
1279 | /// The optimization tries to kill-off the \p MI by looking | |||
1280 | /// through a chain of copies to find a source that has a compatible | |||
1281 | /// register class. | |||
1282 | /// If such a source is found, it replace \p MI by a generic COPY | |||
1283 | /// operation. | |||
1284 | /// \pre isUncoalescableCopy(*MI) is true. | |||
1285 | /// \return True, when \p MI has been optimized. In that case, \p MI has | |||
1286 | /// been removed from its parent. | |||
1287 | /// All COPY instructions created, are inserted in \p LocalMIs. | |||
1288 | bool PeepholeOptimizer::optimizeUncoalescableCopy( | |||
1289 | MachineInstr &MI, SmallPtrSetImpl<MachineInstr *> &LocalMIs) { | |||
1290 | assert(isUncoalescableCopy(MI) && "Invalid argument")(static_cast <bool> (isUncoalescableCopy(MI) && "Invalid argument") ? void (0) : __assert_fail ("isUncoalescableCopy(MI) && \"Invalid argument\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1290, __extension__ __PRETTY_FUNCTION__)); | |||
1291 | UncoalescableRewriter CpyRewriter(MI); | |||
1292 | ||||
1293 | // Rewrite each rewritable source by generating new COPYs. This works | |||
1294 | // differently from optimizeCoalescableCopy since it first makes sure that all | |||
1295 | // definitions can be rewritten. | |||
1296 | RewriteMapTy RewriteMap; | |||
1297 | RegSubRegPair Src; | |||
1298 | RegSubRegPair Def; | |||
1299 | SmallVector<RegSubRegPair, 4> RewritePairs; | |||
1300 | while (CpyRewriter.getNextRewritableSource(Src, Def)) { | |||
1301 | // If a physical register is here, this is probably for a good reason. | |||
1302 | // Do not rewrite that. | |||
1303 | if (Register::isPhysicalRegister(Def.Reg)) | |||
1304 | return false; | |||
1305 | ||||
1306 | // If we do not know how to rewrite this definition, there is no point | |||
1307 | // in trying to kill this instruction. | |||
1308 | if (!findNextSource(Def, RewriteMap)) | |||
1309 | return false; | |||
1310 | ||||
1311 | RewritePairs.push_back(Def); | |||
1312 | } | |||
1313 | ||||
1314 | // The change is possible for all defs, do it. | |||
1315 | for (const RegSubRegPair &Def : RewritePairs) { | |||
1316 | // Rewrite the "copy" in a way the register coalescer understands. | |||
1317 | MachineInstr &NewCopy = rewriteSource(MI, Def, RewriteMap); | |||
1318 | LocalMIs.insert(&NewCopy); | |||
1319 | } | |||
1320 | ||||
1321 | // MI is now dead. | |||
1322 | LLVM_DEBUG(dbgs() << "Deleting uncoalescable copy: " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "Deleting uncoalescable copy: " << MI; } } while (false); | |||
1323 | MI.eraseFromParent(); | |||
1324 | ++NumUncoalescableCopies; | |||
1325 | return true; | |||
1326 | } | |||
1327 | ||||
1328 | /// Check whether MI is a candidate for folding into a later instruction. | |||
1329 | /// We only fold loads to virtual registers and the virtual register defined | |||
1330 | /// has a single user. | |||
1331 | bool PeepholeOptimizer::isLoadFoldable( | |||
1332 | MachineInstr &MI, SmallSet<Register, 16> &FoldAsLoadDefCandidates) { | |||
1333 | if (!MI.canFoldAsLoad() || !MI.mayLoad()) | |||
1334 | return false; | |||
1335 | const MCInstrDesc &MCID = MI.getDesc(); | |||
1336 | if (MCID.getNumDefs() != 1) | |||
1337 | return false; | |||
1338 | ||||
1339 | Register Reg = MI.getOperand(0).getReg(); | |||
1340 | // To reduce compilation time, we check MRI->hasOneNonDBGUser when inserting | |||
1341 | // loads. It should be checked when processing uses of the load, since | |||
1342 | // uses can be removed during peephole. | |||
1343 | if (Reg.isVirtual() && !MI.getOperand(0).getSubReg() && | |||
1344 | MRI->hasOneNonDBGUser(Reg)) { | |||
1345 | FoldAsLoadDefCandidates.insert(Reg); | |||
1346 | return true; | |||
1347 | } | |||
1348 | return false; | |||
1349 | } | |||
1350 | ||||
1351 | bool PeepholeOptimizer::isMoveImmediate( | |||
1352 | MachineInstr &MI, SmallSet<Register, 4> &ImmDefRegs, | |||
1353 | DenseMap<Register, MachineInstr *> &ImmDefMIs) { | |||
1354 | const MCInstrDesc &MCID = MI.getDesc(); | |||
1355 | if (!MI.isMoveImmediate()) | |||
1356 | return false; | |||
1357 | if (MCID.getNumDefs() != 1) | |||
1358 | return false; | |||
1359 | Register Reg = MI.getOperand(0).getReg(); | |||
1360 | if (Reg.isVirtual()) { | |||
1361 | ImmDefMIs.insert(std::make_pair(Reg, &MI)); | |||
1362 | ImmDefRegs.insert(Reg); | |||
1363 | return true; | |||
1364 | } | |||
1365 | ||||
1366 | return false; | |||
1367 | } | |||
1368 | ||||
1369 | /// Try folding register operands that are defined by move immediate | |||
1370 | /// instructions, i.e. a trivial constant folding optimization, if | |||
1371 | /// and only if the def and use are in the same BB. | |||
1372 | bool PeepholeOptimizer::foldImmediate( | |||
1373 | MachineInstr &MI, SmallSet<Register, 4> &ImmDefRegs, | |||
1374 | DenseMap<Register, MachineInstr *> &ImmDefMIs) { | |||
1375 | for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) { | |||
1376 | MachineOperand &MO = MI.getOperand(i); | |||
1377 | if (!MO.isReg() || MO.isDef()) | |||
1378 | continue; | |||
1379 | Register Reg = MO.getReg(); | |||
1380 | if (!Reg.isVirtual()) | |||
1381 | continue; | |||
1382 | if (ImmDefRegs.count(Reg) == 0) | |||
1383 | continue; | |||
1384 | DenseMap<Register, MachineInstr *>::iterator II = ImmDefMIs.find(Reg); | |||
1385 | assert(II != ImmDefMIs.end() && "couldn't find immediate definition")(static_cast <bool> (II != ImmDefMIs.end() && "couldn't find immediate definition" ) ? void (0) : __assert_fail ("II != ImmDefMIs.end() && \"couldn't find immediate definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1385, __extension__ __PRETTY_FUNCTION__)); | |||
1386 | if (TII->FoldImmediate(MI, *II->second, Reg, MRI)) { | |||
1387 | ++NumImmFold; | |||
1388 | return true; | |||
1389 | } | |||
1390 | } | |||
1391 | return false; | |||
1392 | } | |||
1393 | ||||
1394 | // FIXME: This is very simple and misses some cases which should be handled when | |||
1395 | // motivating examples are found. | |||
1396 | // | |||
1397 | // The copy rewriting logic should look at uses as well as defs and be able to | |||
1398 | // eliminate copies across blocks. | |||
1399 | // | |||
1400 | // Later copies that are subregister extracts will also not be eliminated since | |||
1401 | // only the first copy is considered. | |||
1402 | // | |||
1403 | // e.g. | |||
1404 | // %1 = COPY %0 | |||
1405 | // %2 = COPY %0:sub1 | |||
1406 | // | |||
1407 | // Should replace %2 uses with %1:sub1 | |||
1408 | bool PeepholeOptimizer::foldRedundantCopy( | |||
1409 | MachineInstr &MI, DenseMap<RegSubRegPair, MachineInstr *> &CopyMIs) { | |||
1410 | assert(MI.isCopy() && "expected a COPY machine instruction")(static_cast <bool> (MI.isCopy() && "expected a COPY machine instruction" ) ? void (0) : __assert_fail ("MI.isCopy() && \"expected a COPY machine instruction\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1410, __extension__ __PRETTY_FUNCTION__)); | |||
1411 | ||||
1412 | Register SrcReg = MI.getOperand(1).getReg(); | |||
1413 | unsigned SrcSubReg = MI.getOperand(1).getSubReg(); | |||
1414 | if (!SrcReg.isVirtual()) | |||
1415 | return false; | |||
1416 | ||||
1417 | Register DstReg = MI.getOperand(0).getReg(); | |||
1418 | if (!DstReg.isVirtual()) | |||
1419 | return false; | |||
1420 | ||||
1421 | RegSubRegPair SrcPair(SrcReg, SrcSubReg); | |||
1422 | ||||
1423 | if (CopyMIs.insert(std::make_pair(SrcPair, &MI)).second) { | |||
1424 | // First copy of this reg seen. | |||
1425 | return false; | |||
1426 | } | |||
1427 | ||||
1428 | MachineInstr *PrevCopy = CopyMIs.find(SrcPair)->second; | |||
1429 | ||||
1430 | assert(SrcSubReg == PrevCopy->getOperand(1).getSubReg() &&(static_cast <bool> (SrcSubReg == PrevCopy->getOperand (1).getSubReg() && "Unexpected mismatching subreg!") ? void (0) : __assert_fail ("SrcSubReg == PrevCopy->getOperand(1).getSubReg() && \"Unexpected mismatching subreg!\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1431, __extension__ __PRETTY_FUNCTION__)) | |||
1431 | "Unexpected mismatching subreg!")(static_cast <bool> (SrcSubReg == PrevCopy->getOperand (1).getSubReg() && "Unexpected mismatching subreg!") ? void (0) : __assert_fail ("SrcSubReg == PrevCopy->getOperand(1).getSubReg() && \"Unexpected mismatching subreg!\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1431, __extension__ __PRETTY_FUNCTION__)); | |||
1432 | ||||
1433 | Register PrevDstReg = PrevCopy->getOperand(0).getReg(); | |||
1434 | ||||
1435 | // Only replace if the copy register class is the same. | |||
1436 | // | |||
1437 | // TODO: If we have multiple copies to different register classes, we may want | |||
1438 | // to track multiple copies of the same source register. | |||
1439 | if (MRI->getRegClass(DstReg) != MRI->getRegClass(PrevDstReg)) | |||
1440 | return false; | |||
1441 | ||||
1442 | MRI->replaceRegWith(DstReg, PrevDstReg); | |||
1443 | ||||
1444 | // Lifetime of the previous copy has been extended. | |||
1445 | MRI->clearKillFlags(PrevDstReg); | |||
1446 | return true; | |||
1447 | } | |||
1448 | ||||
1449 | bool PeepholeOptimizer::isNAPhysCopy(Register Reg) { | |||
1450 | return Reg.isPhysical() && !MRI->isAllocatable(Reg); | |||
1451 | } | |||
1452 | ||||
1453 | bool PeepholeOptimizer::foldRedundantNAPhysCopy( | |||
1454 | MachineInstr &MI, DenseMap<Register, MachineInstr *> &NAPhysToVirtMIs) { | |||
1455 | assert(MI.isCopy() && "expected a COPY machine instruction")(static_cast <bool> (MI.isCopy() && "expected a COPY machine instruction" ) ? void (0) : __assert_fail ("MI.isCopy() && \"expected a COPY machine instruction\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1455, __extension__ __PRETTY_FUNCTION__)); | |||
1456 | ||||
1457 | if (DisableNAPhysCopyOpt) | |||
1458 | return false; | |||
1459 | ||||
1460 | Register DstReg = MI.getOperand(0).getReg(); | |||
1461 | Register SrcReg = MI.getOperand(1).getReg(); | |||
1462 | if (isNAPhysCopy(SrcReg) && Register::isVirtualRegister(DstReg)) { | |||
1463 | // %vreg = COPY $physreg | |||
1464 | // Avoid using a datastructure which can track multiple live non-allocatable | |||
1465 | // phys->virt copies since LLVM doesn't seem to do this. | |||
1466 | NAPhysToVirtMIs.insert({SrcReg, &MI}); | |||
1467 | return false; | |||
1468 | } | |||
1469 | ||||
1470 | if (!(SrcReg.isVirtual() && isNAPhysCopy(DstReg))) | |||
1471 | return false; | |||
1472 | ||||
1473 | // $physreg = COPY %vreg | |||
1474 | auto PrevCopy = NAPhysToVirtMIs.find(DstReg); | |||
1475 | if (PrevCopy == NAPhysToVirtMIs.end()) { | |||
1476 | // We can't remove the copy: there was an intervening clobber of the | |||
1477 | // non-allocatable physical register after the copy to virtual. | |||
1478 | LLVM_DEBUG(dbgs() << "NAPhysCopy: intervening clobber forbids erasing "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "NAPhysCopy: intervening clobber forbids erasing " << MI; } } while (false) | |||
1479 | << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "NAPhysCopy: intervening clobber forbids erasing " << MI; } } while (false); | |||
1480 | return false; | |||
1481 | } | |||
1482 | ||||
1483 | Register PrevDstReg = PrevCopy->second->getOperand(0).getReg(); | |||
1484 | if (PrevDstReg == SrcReg) { | |||
1485 | // Remove the virt->phys copy: we saw the virtual register definition, and | |||
1486 | // the non-allocatable physical register's state hasn't changed since then. | |||
1487 | LLVM_DEBUG(dbgs() << "NAPhysCopy: erasing " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "NAPhysCopy: erasing " << MI; } } while (false); | |||
1488 | ++NumNAPhysCopies; | |||
1489 | return true; | |||
1490 | } | |||
1491 | ||||
1492 | // Potential missed optimization opportunity: we saw a different virtual | |||
1493 | // register get a copy of the non-allocatable physical register, and we only | |||
1494 | // track one such copy. Avoid getting confused by this new non-allocatable | |||
1495 | // physical register definition, and remove it from the tracked copies. | |||
1496 | LLVM_DEBUG(dbgs() << "NAPhysCopy: missed opportunity " << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "NAPhysCopy: missed opportunity " << MI; } } while (false); | |||
1497 | NAPhysToVirtMIs.erase(PrevCopy); | |||
1498 | return false; | |||
1499 | } | |||
1500 | ||||
1501 | /// \bried Returns true if \p MO is a virtual register operand. | |||
1502 | static bool isVirtualRegisterOperand(MachineOperand &MO) { | |||
1503 | return MO.isReg() && MO.getReg().isVirtual(); | |||
1504 | } | |||
1505 | ||||
1506 | bool PeepholeOptimizer::findTargetRecurrence( | |||
1507 | Register Reg, const SmallSet<Register, 2> &TargetRegs, | |||
1508 | RecurrenceCycle &RC) { | |||
1509 | // Recurrence found if Reg is in TargetRegs. | |||
1510 | if (TargetRegs.count(Reg)) | |||
1511 | return true; | |||
1512 | ||||
1513 | // TODO: Curerntly, we only allow the last instruction of the recurrence | |||
1514 | // cycle (the instruction that feeds the PHI instruction) to have more than | |||
1515 | // one uses to guarantee that commuting operands does not tie registers | |||
1516 | // with overlapping live range. Once we have actual live range info of | |||
1517 | // each register, this constraint can be relaxed. | |||
1518 | if (!MRI->hasOneNonDBGUse(Reg)) | |||
1519 | return false; | |||
1520 | ||||
1521 | // Give up if the reccurrence chain length is longer than the limit. | |||
1522 | if (RC.size() >= MaxRecurrenceChain) | |||
1523 | return false; | |||
1524 | ||||
1525 | MachineInstr &MI = *(MRI->use_instr_nodbg_begin(Reg)); | |||
1526 | unsigned Idx = MI.findRegisterUseOperandIdx(Reg); | |||
1527 | ||||
1528 | // Only interested in recurrences whose instructions have only one def, which | |||
1529 | // is a virtual register. | |||
1530 | if (MI.getDesc().getNumDefs() != 1) | |||
1531 | return false; | |||
1532 | ||||
1533 | MachineOperand &DefOp = MI.getOperand(0); | |||
1534 | if (!isVirtualRegisterOperand(DefOp)) | |||
1535 | return false; | |||
1536 | ||||
1537 | // Check if def operand of MI is tied to any use operand. We are only | |||
1538 | // interested in the case that all the instructions in the recurrence chain | |||
1539 | // have there def operand tied with one of the use operand. | |||
1540 | unsigned TiedUseIdx; | |||
1541 | if (!MI.isRegTiedToUseOperand(0, &TiedUseIdx)) | |||
1542 | return false; | |||
1543 | ||||
1544 | if (Idx == TiedUseIdx) { | |||
1545 | RC.push_back(RecurrenceInstr(&MI)); | |||
1546 | return findTargetRecurrence(DefOp.getReg(), TargetRegs, RC); | |||
1547 | } else { | |||
1548 | // If Idx is not TiedUseIdx, check if Idx is commutable with TiedUseIdx. | |||
1549 | unsigned CommIdx = TargetInstrInfo::CommuteAnyOperandIndex; | |||
1550 | if (TII->findCommutedOpIndices(MI, Idx, CommIdx) && CommIdx == TiedUseIdx) { | |||
1551 | RC.push_back(RecurrenceInstr(&MI, Idx, CommIdx)); | |||
1552 | return findTargetRecurrence(DefOp.getReg(), TargetRegs, RC); | |||
1553 | } | |||
1554 | } | |||
1555 | ||||
1556 | return false; | |||
1557 | } | |||
1558 | ||||
1559 | /// Phi instructions will eventually be lowered to copy instructions. | |||
1560 | /// If phi is in a loop header, a recurrence may formulated around the source | |||
1561 | /// and destination of the phi. For such case commuting operands of the | |||
1562 | /// instructions in the recurrence may enable coalescing of the copy instruction | |||
1563 | /// generated from the phi. For example, if there is a recurrence of | |||
1564 | /// | |||
1565 | /// LoopHeader: | |||
1566 | /// %1 = phi(%0, %100) | |||
1567 | /// LoopLatch: | |||
1568 | /// %0<def, tied1> = ADD %2<def, tied0>, %1 | |||
1569 | /// | |||
1570 | /// , the fact that %0 and %2 are in the same tied operands set makes | |||
1571 | /// the coalescing of copy instruction generated from the phi in | |||
1572 | /// LoopHeader(i.e. %1 = COPY %0) impossible, because %1 and | |||
1573 | /// %2 have overlapping live range. This introduces additional move | |||
1574 | /// instruction to the final assembly. However, if we commute %2 and | |||
1575 | /// %1 of ADD instruction, the redundant move instruction can be | |||
1576 | /// avoided. | |||
1577 | bool PeepholeOptimizer::optimizeRecurrence(MachineInstr &PHI) { | |||
1578 | SmallSet<Register, 2> TargetRegs; | |||
1579 | for (unsigned Idx = 1; Idx < PHI.getNumOperands(); Idx += 2) { | |||
1580 | MachineOperand &MO = PHI.getOperand(Idx); | |||
1581 | assert(isVirtualRegisterOperand(MO) && "Invalid PHI instruction")(static_cast <bool> (isVirtualRegisterOperand(MO) && "Invalid PHI instruction") ? void (0) : __assert_fail ("isVirtualRegisterOperand(MO) && \"Invalid PHI instruction\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1581, __extension__ __PRETTY_FUNCTION__)); | |||
1582 | TargetRegs.insert(MO.getReg()); | |||
1583 | } | |||
1584 | ||||
1585 | bool Changed = false; | |||
1586 | RecurrenceCycle RC; | |||
1587 | if (findTargetRecurrence(PHI.getOperand(0).getReg(), TargetRegs, RC)) { | |||
1588 | // Commutes operands of instructions in RC if necessary so that the copy to | |||
1589 | // be generated from PHI can be coalesced. | |||
1590 | LLVM_DEBUG(dbgs() << "Optimize recurrence chain from " << PHI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "Optimize recurrence chain from " << PHI; } } while (false); | |||
1591 | for (auto &RI : RC) { | |||
1592 | LLVM_DEBUG(dbgs() << "\tInst: " << *(RI.getMI()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "\tInst: " << *(RI. getMI()); } } while (false); | |||
1593 | auto CP = RI.getCommutePair(); | |||
1594 | if (CP) { | |||
1595 | Changed = true; | |||
1596 | TII->commuteInstruction(*(RI.getMI()), false, (*CP).first, | |||
1597 | (*CP).second); | |||
1598 | LLVM_DEBUG(dbgs() << "\t\tCommuted: " << *(RI.getMI()))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "\t\tCommuted: " << *(RI.getMI()); } } while (false); | |||
1599 | } | |||
1600 | } | |||
1601 | } | |||
1602 | ||||
1603 | return Changed; | |||
1604 | } | |||
1605 | ||||
1606 | bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { | |||
1607 | if (skipFunction(MF.getFunction())) | |||
| ||||
1608 | return false; | |||
1609 | ||||
1610 | LLVM_DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "********** PEEPHOLE OPTIMIZER **********\n" ; } } while (false); | |||
1611 | LLVM_DEBUG(dbgs() << "********** Function: " << MF.getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "********** Function: " << MF.getName() << '\n'; } } while (false); | |||
1612 | ||||
1613 | if (DisablePeephole) | |||
1614 | return false; | |||
1615 | ||||
1616 | TII = MF.getSubtarget().getInstrInfo(); | |||
1617 | TRI = MF.getSubtarget().getRegisterInfo(); | |||
1618 | MRI = &MF.getRegInfo(); | |||
1619 | DT = Aggressive ? &getAnalysis<MachineDominatorTree>() : nullptr; | |||
1620 | MLI = &getAnalysis<MachineLoopInfo>(); | |||
1621 | ||||
1622 | bool Changed = false; | |||
1623 | ||||
1624 | for (MachineBasicBlock &MBB : MF) { | |||
1625 | bool SeenMoveImm = false; | |||
1626 | ||||
1627 | // During this forward scan, at some point it needs to answer the question | |||
1628 | // "given a pointer to an MI in the current BB, is it located before or | |||
1629 | // after the current instruction". | |||
1630 | // To perform this, the following set keeps track of the MIs already seen | |||
1631 | // during the scan, if a MI is not in the set, it is assumed to be located | |||
1632 | // after. Newly created MIs have to be inserted in the set as well. | |||
1633 | SmallPtrSet<MachineInstr*, 16> LocalMIs; | |||
1634 | SmallSet<Register, 4> ImmDefRegs; | |||
1635 | DenseMap<Register, MachineInstr *> ImmDefMIs; | |||
1636 | SmallSet<Register, 16> FoldAsLoadDefCandidates; | |||
1637 | ||||
1638 | // Track when a non-allocatable physical register is copied to a virtual | |||
1639 | // register so that useless moves can be removed. | |||
1640 | // | |||
1641 | // $physreg is the map index; MI is the last valid `%vreg = COPY $physreg` | |||
1642 | // without any intervening re-definition of $physreg. | |||
1643 | DenseMap<Register, MachineInstr *> NAPhysToVirtMIs; | |||
1644 | ||||
1645 | // Set of pairs of virtual registers and their subregs that are copied | |||
1646 | // from. | |||
1647 | DenseMap<RegSubRegPair, MachineInstr *> CopySrcMIs; | |||
1648 | ||||
1649 | bool IsLoopHeader = MLI->isLoopHeader(&MBB); | |||
1650 | ||||
1651 | for (MachineBasicBlock::iterator MII = MBB.begin(), MIE = MBB.end(); | |||
1652 | MII != MIE; ) { | |||
1653 | MachineInstr *MI = &*MII; | |||
1654 | // We may be erasing MI below, increment MII now. | |||
1655 | ++MII; | |||
1656 | LocalMIs.insert(MI); | |||
1657 | ||||
1658 | // Skip debug instructions. They should not affect this peephole | |||
1659 | // optimization. | |||
1660 | if (MI->isDebugInstr()) | |||
1661 | continue; | |||
1662 | ||||
1663 | if (MI->isPosition()) | |||
1664 | continue; | |||
1665 | ||||
1666 | if (IsLoopHeader && MI->isPHI()) { | |||
1667 | if (optimizeRecurrence(*MI)) { | |||
1668 | Changed = true; | |||
1669 | continue; | |||
1670 | } | |||
1671 | } | |||
1672 | ||||
1673 | if (!MI->isCopy()) { | |||
1674 | for (const MachineOperand &MO : MI->operands()) { | |||
1675 | // Visit all operands: definitions can be implicit or explicit. | |||
1676 | if (MO.isReg()) { | |||
1677 | Register Reg = MO.getReg(); | |||
1678 | if (MO.isDef() && isNAPhysCopy(Reg)) { | |||
1679 | const auto &Def = NAPhysToVirtMIs.find(Reg); | |||
1680 | if (Def != NAPhysToVirtMIs.end()) { | |||
1681 | // A new definition of the non-allocatable physical register | |||
1682 | // invalidates previous copies. | |||
1683 | LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "NAPhysCopy: invalidating because of " << *MI; } } while (false) | |||
1684 | << "NAPhysCopy: invalidating because of " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "NAPhysCopy: invalidating because of " << *MI; } } while (false); | |||
1685 | NAPhysToVirtMIs.erase(Def); | |||
1686 | } | |||
1687 | } | |||
1688 | } else if (MO.isRegMask()) { | |||
1689 | const uint32_t *RegMask = MO.getRegMask(); | |||
1690 | for (auto &RegMI : NAPhysToVirtMIs) { | |||
1691 | Register Def = RegMI.first; | |||
1692 | if (MachineOperand::clobbersPhysReg(RegMask, Def)) { | |||
1693 | LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "NAPhysCopy: invalidating because of " << *MI; } } while (false) | |||
1694 | << "NAPhysCopy: invalidating because of " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "NAPhysCopy: invalidating because of " << *MI; } } while (false); | |||
1695 | NAPhysToVirtMIs.erase(Def); | |||
1696 | } | |||
1697 | } | |||
1698 | } | |||
1699 | } | |||
1700 | } | |||
1701 | ||||
1702 | if (MI->isImplicitDef() || MI->isKill()) | |||
1703 | continue; | |||
1704 | ||||
1705 | if (MI->isInlineAsm() || MI->hasUnmodeledSideEffects()) { | |||
1706 | // Blow away all non-allocatable physical registers knowledge since we | |||
1707 | // don't know what's correct anymore. | |||
1708 | // | |||
1709 | // FIXME: handle explicit asm clobbers. | |||
1710 | LLVM_DEBUG(dbgs() << "NAPhysCopy: blowing away all info due to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "NAPhysCopy: blowing away all info due to " << *MI; } } while (false) | |||
1711 | << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "NAPhysCopy: blowing away all info due to " << *MI; } } while (false); | |||
1712 | NAPhysToVirtMIs.clear(); | |||
1713 | } | |||
1714 | ||||
1715 | if ((isUncoalescableCopy(*MI) && | |||
1716 | optimizeUncoalescableCopy(*MI, LocalMIs)) || | |||
1717 | (MI->isCompare() && optimizeCmpInstr(*MI)) || | |||
1718 | (MI->isSelect() && optimizeSelect(*MI, LocalMIs))) { | |||
1719 | // MI is deleted. | |||
1720 | LocalMIs.erase(MI); | |||
1721 | Changed = true; | |||
1722 | continue; | |||
1723 | } | |||
1724 | ||||
1725 | if (MI->isConditionalBranch() && optimizeCondBranch(*MI)) { | |||
1726 | Changed = true; | |||
1727 | continue; | |||
1728 | } | |||
1729 | ||||
1730 | if (isCoalescableCopy(*MI) && optimizeCoalescableCopy(*MI)) { | |||
1731 | // MI is just rewritten. | |||
1732 | Changed = true; | |||
1733 | continue; | |||
1734 | } | |||
1735 | ||||
1736 | if (MI->isCopy() && (foldRedundantCopy(*MI, CopySrcMIs) || | |||
1737 | foldRedundantNAPhysCopy(*MI, NAPhysToVirtMIs))) { | |||
1738 | LocalMIs.erase(MI); | |||
1739 | LLVM_DEBUG(dbgs() << "Deleting redundant copy: " << *MI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "Deleting redundant copy: " << *MI << "\n"; } } while (false); | |||
1740 | MI->eraseFromParent(); | |||
1741 | Changed = true; | |||
1742 | continue; | |||
1743 | } | |||
1744 | ||||
1745 | if (isMoveImmediate(*MI, ImmDefRegs, ImmDefMIs)) { | |||
1746 | SeenMoveImm = true; | |||
1747 | } else { | |||
1748 | Changed |= optimizeExtInstr(*MI, MBB, LocalMIs); | |||
1749 | // optimizeExtInstr might have created new instructions after MI | |||
1750 | // and before the already incremented MII. Adjust MII so that the | |||
1751 | // next iteration sees the new instructions. | |||
1752 | MII = MI; | |||
1753 | ++MII; | |||
1754 | if (SeenMoveImm) | |||
1755 | Changed |= foldImmediate(*MI, ImmDefRegs, ImmDefMIs); | |||
1756 | } | |||
1757 | ||||
1758 | // Check whether MI is a load candidate for folding into a later | |||
1759 | // instruction. If MI is not a candidate, check whether we can fold an | |||
1760 | // earlier load into MI. | |||
1761 | if (!isLoadFoldable(*MI, FoldAsLoadDefCandidates) && | |||
1762 | !FoldAsLoadDefCandidates.empty()) { | |||
1763 | ||||
1764 | // We visit each operand even after successfully folding a previous | |||
1765 | // one. This allows us to fold multiple loads into a single | |||
1766 | // instruction. We do assume that optimizeLoadInstr doesn't insert | |||
1767 | // foldable uses earlier in the argument list. Since we don't restart | |||
1768 | // iteration, we'd miss such cases. | |||
1769 | const MCInstrDesc &MIDesc = MI->getDesc(); | |||
1770 | for (unsigned i = MIDesc.getNumDefs(); i != MI->getNumOperands(); | |||
1771 | ++i) { | |||
1772 | const MachineOperand &MOp = MI->getOperand(i); | |||
1773 | if (!MOp.isReg()) | |||
1774 | continue; | |||
1775 | Register FoldAsLoadDefReg = MOp.getReg(); | |||
1776 | if (FoldAsLoadDefCandidates.count(FoldAsLoadDefReg)) { | |||
1777 | // We need to fold load after optimizeCmpInstr, since | |||
1778 | // optimizeCmpInstr can enable folding by converting SUB to CMP. | |||
1779 | // Save FoldAsLoadDefReg because optimizeLoadInstr() resets it and | |||
1780 | // we need it for markUsesInDebugValueAsUndef(). | |||
1781 | Register FoldedReg = FoldAsLoadDefReg; | |||
1782 | MachineInstr *DefMI = nullptr; | |||
1783 | if (MachineInstr *FoldMI = | |||
1784 | TII->optimizeLoadInstr(*MI, MRI, FoldAsLoadDefReg, DefMI)) { | |||
1785 | // Update LocalMIs since we replaced MI with FoldMI and deleted | |||
1786 | // DefMI. | |||
1787 | LLVM_DEBUG(dbgs() << "Replacing: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "Replacing: " << *MI ; } } while (false); | |||
1788 | LLVM_DEBUG(dbgs() << " With: " << *FoldMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << " With: " << *FoldMI ; } } while (false); | |||
1789 | LocalMIs.erase(MI); | |||
1790 | LocalMIs.erase(DefMI); | |||
1791 | LocalMIs.insert(FoldMI); | |||
1792 | // Update the call site info. | |||
1793 | if (MI->shouldUpdateCallSiteInfo()) | |||
1794 | MI->getMF()->moveCallSiteInfo(MI, FoldMI); | |||
1795 | MI->eraseFromParent(); | |||
1796 | DefMI->eraseFromParent(); | |||
1797 | MRI->markUsesInDebugValueAsUndef(FoldedReg); | |||
1798 | FoldAsLoadDefCandidates.erase(FoldedReg); | |||
1799 | ++NumLoadFold; | |||
1800 | ||||
1801 | // MI is replaced with FoldMI so we can continue trying to fold | |||
1802 | Changed = true; | |||
1803 | MI = FoldMI; | |||
1804 | } | |||
1805 | } | |||
1806 | } | |||
1807 | } | |||
1808 | ||||
1809 | // If we run into an instruction we can't fold across, discard | |||
1810 | // the load candidates. Note: We might be able to fold *into* this | |||
1811 | // instruction, so this needs to be after the folding logic. | |||
1812 | if (MI->isLoadFoldBarrier()) { | |||
1813 | LLVM_DEBUG(dbgs() << "Encountered load fold barrier on " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("peephole-opt")) { dbgs() << "Encountered load fold barrier on " << *MI; } } while (false); | |||
1814 | FoldAsLoadDefCandidates.clear(); | |||
1815 | } | |||
1816 | } | |||
1817 | } | |||
1818 | ||||
1819 | return Changed; | |||
1820 | } | |||
1821 | ||||
1822 | ValueTrackerResult ValueTracker::getNextSourceFromCopy() { | |||
1823 | assert(Def->isCopy() && "Invalid definition")(static_cast <bool> (Def->isCopy() && "Invalid definition" ) ? void (0) : __assert_fail ("Def->isCopy() && \"Invalid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1823, __extension__ __PRETTY_FUNCTION__)); | |||
1824 | // Copy instruction are supposed to be: Def = Src. | |||
1825 | // If someone breaks this assumption, bad things will happen everywhere. | |||
1826 | // There may be implicit uses preventing the copy to be moved across | |||
1827 | // some target specific register definitions | |||
1828 | assert(Def->getNumOperands() - Def->getNumImplicitOperands() == 2 &&(static_cast <bool> (Def->getNumOperands() - Def-> getNumImplicitOperands() == 2 && "Invalid number of operands" ) ? void (0) : __assert_fail ("Def->getNumOperands() - Def->getNumImplicitOperands() == 2 && \"Invalid number of operands\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1829, __extension__ __PRETTY_FUNCTION__)) | |||
1829 | "Invalid number of operands")(static_cast <bool> (Def->getNumOperands() - Def-> getNumImplicitOperands() == 2 && "Invalid number of operands" ) ? void (0) : __assert_fail ("Def->getNumOperands() - Def->getNumImplicitOperands() == 2 && \"Invalid number of operands\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1829, __extension__ __PRETTY_FUNCTION__)); | |||
1830 | assert(!Def->hasImplicitDef() && "Only implicit uses are allowed")(static_cast <bool> (!Def->hasImplicitDef() && "Only implicit uses are allowed") ? void (0) : __assert_fail ("!Def->hasImplicitDef() && \"Only implicit uses are allowed\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1830, __extension__ __PRETTY_FUNCTION__)); | |||
1831 | ||||
1832 | if (Def->getOperand(DefIdx).getSubReg() != DefSubReg) | |||
1833 | // If we look for a different subreg, it means we want a subreg of src. | |||
1834 | // Bails as we do not support composing subregs yet. | |||
1835 | return ValueTrackerResult(); | |||
1836 | // Otherwise, we want the whole source. | |||
1837 | const MachineOperand &Src = Def->getOperand(1); | |||
1838 | if (Src.isUndef()) | |||
1839 | return ValueTrackerResult(); | |||
1840 | return ValueTrackerResult(Src.getReg(), Src.getSubReg()); | |||
1841 | } | |||
1842 | ||||
1843 | ValueTrackerResult ValueTracker::getNextSourceFromBitcast() { | |||
1844 | assert(Def->isBitcast() && "Invalid definition")(static_cast <bool> (Def->isBitcast() && "Invalid definition" ) ? void (0) : __assert_fail ("Def->isBitcast() && \"Invalid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1844, __extension__ __PRETTY_FUNCTION__)); | |||
1845 | ||||
1846 | // Bail if there are effects that a plain copy will not expose. | |||
1847 | if (Def->mayRaiseFPException() || Def->hasUnmodeledSideEffects()) | |||
1848 | return ValueTrackerResult(); | |||
1849 | ||||
1850 | // Bitcasts with more than one def are not supported. | |||
1851 | if (Def->getDesc().getNumDefs() != 1) | |||
1852 | return ValueTrackerResult(); | |||
1853 | const MachineOperand DefOp = Def->getOperand(DefIdx); | |||
1854 | if (DefOp.getSubReg() != DefSubReg) | |||
1855 | // If we look for a different subreg, it means we want a subreg of the src. | |||
1856 | // Bails as we do not support composing subregs yet. | |||
1857 | return ValueTrackerResult(); | |||
1858 | ||||
1859 | unsigned SrcIdx = Def->getNumOperands(); | |||
1860 | for (unsigned OpIdx = DefIdx + 1, EndOpIdx = SrcIdx; OpIdx != EndOpIdx; | |||
1861 | ++OpIdx) { | |||
1862 | const MachineOperand &MO = Def->getOperand(OpIdx); | |||
1863 | if (!MO.isReg() || !MO.getReg()) | |||
1864 | continue; | |||
1865 | // Ignore dead implicit defs. | |||
1866 | if (MO.isImplicit() && MO.isDead()) | |||
1867 | continue; | |||
1868 | assert(!MO.isDef() && "We should have skipped all the definitions by now")(static_cast <bool> (!MO.isDef() && "We should have skipped all the definitions by now" ) ? void (0) : __assert_fail ("!MO.isDef() && \"We should have skipped all the definitions by now\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1868, __extension__ __PRETTY_FUNCTION__)); | |||
1869 | if (SrcIdx != EndOpIdx) | |||
1870 | // Multiple sources? | |||
1871 | return ValueTrackerResult(); | |||
1872 | SrcIdx = OpIdx; | |||
1873 | } | |||
1874 | ||||
1875 | // In some rare case, Def has no input, SrcIdx is out of bound, | |||
1876 | // getOperand(SrcIdx) will fail below. | |||
1877 | if (SrcIdx >= Def->getNumOperands()) | |||
1878 | return ValueTrackerResult(); | |||
1879 | ||||
1880 | // Stop when any user of the bitcast is a SUBREG_TO_REG, replacing with a COPY | |||
1881 | // will break the assumed guarantees for the upper bits. | |||
1882 | for (const MachineInstr &UseMI : MRI.use_nodbg_instructions(DefOp.getReg())) { | |||
1883 | if (UseMI.isSubregToReg()) | |||
1884 | return ValueTrackerResult(); | |||
1885 | } | |||
1886 | ||||
1887 | const MachineOperand &Src = Def->getOperand(SrcIdx); | |||
1888 | if (Src.isUndef()) | |||
1889 | return ValueTrackerResult(); | |||
1890 | return ValueTrackerResult(Src.getReg(), Src.getSubReg()); | |||
1891 | } | |||
1892 | ||||
1893 | ValueTrackerResult ValueTracker::getNextSourceFromRegSequence() { | |||
1894 | assert((Def->isRegSequence() || Def->isRegSequenceLike()) &&(static_cast <bool> ((Def->isRegSequence() || Def-> isRegSequenceLike()) && "Invalid definition") ? void ( 0) : __assert_fail ("(Def->isRegSequence() || Def->isRegSequenceLike()) && \"Invalid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1895, __extension__ __PRETTY_FUNCTION__)) | |||
1895 | "Invalid definition")(static_cast <bool> ((Def->isRegSequence() || Def-> isRegSequenceLike()) && "Invalid definition") ? void ( 0) : __assert_fail ("(Def->isRegSequence() || Def->isRegSequenceLike()) && \"Invalid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1895, __extension__ __PRETTY_FUNCTION__)); | |||
1896 | ||||
1897 | if (Def->getOperand(DefIdx).getSubReg()) | |||
1898 | // If we are composing subregs, bail out. | |||
1899 | // The case we are checking is Def.<subreg> = REG_SEQUENCE. | |||
1900 | // This should almost never happen as the SSA property is tracked at | |||
1901 | // the register level (as opposed to the subreg level). | |||
1902 | // I.e., | |||
1903 | // Def.sub0 = | |||
1904 | // Def.sub1 = | |||
1905 | // is a valid SSA representation for Def.sub0 and Def.sub1, but not for | |||
1906 | // Def. Thus, it must not be generated. | |||
1907 | // However, some code could theoretically generates a single | |||
1908 | // Def.sub0 (i.e, not defining the other subregs) and we would | |||
1909 | // have this case. | |||
1910 | // If we can ascertain (or force) that this never happens, we could | |||
1911 | // turn that into an assertion. | |||
1912 | return ValueTrackerResult(); | |||
1913 | ||||
1914 | if (!TII) | |||
1915 | // We could handle the REG_SEQUENCE here, but we do not want to | |||
1916 | // duplicate the code from the generic TII. | |||
1917 | return ValueTrackerResult(); | |||
1918 | ||||
1919 | SmallVector<RegSubRegPairAndIdx, 8> RegSeqInputRegs; | |||
1920 | if (!TII->getRegSequenceInputs(*Def, DefIdx, RegSeqInputRegs)) | |||
1921 | return ValueTrackerResult(); | |||
1922 | ||||
1923 | // We are looking at: | |||
1924 | // Def = REG_SEQUENCE v0, sub0, v1, sub1, ... | |||
1925 | // Check if one of the operand defines the subreg we are interested in. | |||
1926 | for (const RegSubRegPairAndIdx &RegSeqInput : RegSeqInputRegs) { | |||
1927 | if (RegSeqInput.SubIdx == DefSubReg) | |||
1928 | return ValueTrackerResult(RegSeqInput.Reg, RegSeqInput.SubReg); | |||
1929 | } | |||
1930 | ||||
1931 | // If the subreg we are tracking is super-defined by another subreg, | |||
1932 | // we could follow this value. However, this would require to compose | |||
1933 | // the subreg and we do not do that for now. | |||
1934 | return ValueTrackerResult(); | |||
1935 | } | |||
1936 | ||||
1937 | ValueTrackerResult ValueTracker::getNextSourceFromInsertSubreg() { | |||
1938 | assert((Def->isInsertSubreg() || Def->isInsertSubregLike()) &&(static_cast <bool> ((Def->isInsertSubreg() || Def-> isInsertSubregLike()) && "Invalid definition") ? void (0) : __assert_fail ("(Def->isInsertSubreg() || Def->isInsertSubregLike()) && \"Invalid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1939, __extension__ __PRETTY_FUNCTION__)) | |||
1939 | "Invalid definition")(static_cast <bool> ((Def->isInsertSubreg() || Def-> isInsertSubregLike()) && "Invalid definition") ? void (0) : __assert_fail ("(Def->isInsertSubreg() || Def->isInsertSubregLike()) && \"Invalid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1939, __extension__ __PRETTY_FUNCTION__)); | |||
1940 | ||||
1941 | if (Def->getOperand(DefIdx).getSubReg()) | |||
1942 | // If we are composing subreg, bail out. | |||
1943 | // Same remark as getNextSourceFromRegSequence. | |||
1944 | // I.e., this may be turned into an assert. | |||
1945 | return ValueTrackerResult(); | |||
1946 | ||||
1947 | if (!TII) | |||
1948 | // We could handle the REG_SEQUENCE here, but we do not want to | |||
1949 | // duplicate the code from the generic TII. | |||
1950 | return ValueTrackerResult(); | |||
1951 | ||||
1952 | RegSubRegPair BaseReg; | |||
1953 | RegSubRegPairAndIdx InsertedReg; | |||
1954 | if (!TII->getInsertSubregInputs(*Def, DefIdx, BaseReg, InsertedReg)) | |||
1955 | return ValueTrackerResult(); | |||
1956 | ||||
1957 | // We are looking at: | |||
1958 | // Def = INSERT_SUBREG v0, v1, sub1 | |||
1959 | // There are two cases: | |||
1960 | // 1. DefSubReg == sub1, get v1. | |||
1961 | // 2. DefSubReg != sub1, the value may be available through v0. | |||
1962 | ||||
1963 | // #1 Check if the inserted register matches the required sub index. | |||
1964 | if (InsertedReg.SubIdx == DefSubReg) { | |||
1965 | return ValueTrackerResult(InsertedReg.Reg, InsertedReg.SubReg); | |||
1966 | } | |||
1967 | // #2 Otherwise, if the sub register we are looking for is not partial | |||
1968 | // defined by the inserted element, we can look through the main | |||
1969 | // register (v0). | |||
1970 | const MachineOperand &MODef = Def->getOperand(DefIdx); | |||
1971 | // If the result register (Def) and the base register (v0) do not | |||
1972 | // have the same register class or if we have to compose | |||
1973 | // subregisters, bail out. | |||
1974 | if (MRI.getRegClass(MODef.getReg()) != MRI.getRegClass(BaseReg.Reg) || | |||
1975 | BaseReg.SubReg) | |||
1976 | return ValueTrackerResult(); | |||
1977 | ||||
1978 | // Get the TRI and check if the inserted sub-register overlaps with the | |||
1979 | // sub-register we are tracking. | |||
1980 | const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo(); | |||
1981 | if (!TRI || | |||
1982 | !(TRI->getSubRegIndexLaneMask(DefSubReg) & | |||
1983 | TRI->getSubRegIndexLaneMask(InsertedReg.SubIdx)).none()) | |||
1984 | return ValueTrackerResult(); | |||
1985 | // At this point, the value is available in v0 via the same subreg | |||
1986 | // we used for Def. | |||
1987 | return ValueTrackerResult(BaseReg.Reg, DefSubReg); | |||
1988 | } | |||
1989 | ||||
1990 | ValueTrackerResult ValueTracker::getNextSourceFromExtractSubreg() { | |||
1991 | assert((Def->isExtractSubreg() ||(static_cast <bool> ((Def->isExtractSubreg() || Def-> isExtractSubregLike()) && "Invalid definition") ? void (0) : __assert_fail ("(Def->isExtractSubreg() || Def->isExtractSubregLike()) && \"Invalid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1992, __extension__ __PRETTY_FUNCTION__)) | |||
1992 | Def->isExtractSubregLike()) && "Invalid definition")(static_cast <bool> ((Def->isExtractSubreg() || Def-> isExtractSubregLike()) && "Invalid definition") ? void (0) : __assert_fail ("(Def->isExtractSubreg() || Def->isExtractSubregLike()) && \"Invalid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 1992, __extension__ __PRETTY_FUNCTION__)); | |||
1993 | // We are looking at: | |||
1994 | // Def = EXTRACT_SUBREG v0, sub0 | |||
1995 | ||||
1996 | // Bail if we have to compose sub registers. | |||
1997 | // Indeed, if DefSubReg != 0, we would have to compose it with sub0. | |||
1998 | if (DefSubReg) | |||
1999 | return ValueTrackerResult(); | |||
2000 | ||||
2001 | if (!TII) | |||
2002 | // We could handle the EXTRACT_SUBREG here, but we do not want to | |||
2003 | // duplicate the code from the generic TII. | |||
2004 | return ValueTrackerResult(); | |||
2005 | ||||
2006 | RegSubRegPairAndIdx ExtractSubregInputReg; | |||
2007 | if (!TII->getExtractSubregInputs(*Def, DefIdx, ExtractSubregInputReg)) | |||
2008 | return ValueTrackerResult(); | |||
2009 | ||||
2010 | // Bail if we have to compose sub registers. | |||
2011 | // Likewise, if v0.subreg != 0, we would have to compose v0.subreg with sub0. | |||
2012 | if (ExtractSubregInputReg.SubReg) | |||
2013 | return ValueTrackerResult(); | |||
2014 | // Otherwise, the value is available in the v0.sub0. | |||
2015 | return ValueTrackerResult(ExtractSubregInputReg.Reg, | |||
2016 | ExtractSubregInputReg.SubIdx); | |||
2017 | } | |||
2018 | ||||
2019 | ValueTrackerResult ValueTracker::getNextSourceFromSubregToReg() { | |||
2020 | assert(Def->isSubregToReg() && "Invalid definition")(static_cast <bool> (Def->isSubregToReg() && "Invalid definition") ? void (0) : __assert_fail ("Def->isSubregToReg() && \"Invalid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 2020, __extension__ __PRETTY_FUNCTION__)); | |||
2021 | // We are looking at: | |||
2022 | // Def = SUBREG_TO_REG Imm, v0, sub0 | |||
2023 | ||||
2024 | // Bail if we have to compose sub registers. | |||
2025 | // If DefSubReg != sub0, we would have to check that all the bits | |||
2026 | // we track are included in sub0 and if yes, we would have to | |||
2027 | // determine the right subreg in v0. | |||
2028 | if (DefSubReg != Def->getOperand(3).getImm()) | |||
2029 | return ValueTrackerResult(); | |||
2030 | // Bail if we have to compose sub registers. | |||
2031 | // Likewise, if v0.subreg != 0, we would have to compose it with sub0. | |||
2032 | if (Def->getOperand(2).getSubReg()) | |||
2033 | return ValueTrackerResult(); | |||
2034 | ||||
2035 | return ValueTrackerResult(Def->getOperand(2).getReg(), | |||
2036 | Def->getOperand(3).getImm()); | |||
2037 | } | |||
2038 | ||||
2039 | /// Explore each PHI incoming operand and return its sources. | |||
2040 | ValueTrackerResult ValueTracker::getNextSourceFromPHI() { | |||
2041 | assert(Def->isPHI() && "Invalid definition")(static_cast <bool> (Def->isPHI() && "Invalid definition" ) ? void (0) : __assert_fail ("Def->isPHI() && \"Invalid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 2041, __extension__ __PRETTY_FUNCTION__)); | |||
2042 | ValueTrackerResult Res; | |||
2043 | ||||
2044 | // If we look for a different subreg, bail as we do not support composing | |||
2045 | // subregs yet. | |||
2046 | if (Def->getOperand(0).getSubReg() != DefSubReg) | |||
2047 | return ValueTrackerResult(); | |||
2048 | ||||
2049 | // Return all register sources for PHI instructions. | |||
2050 | for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) { | |||
2051 | const MachineOperand &MO = Def->getOperand(i); | |||
2052 | assert(MO.isReg() && "Invalid PHI instruction")(static_cast <bool> (MO.isReg() && "Invalid PHI instruction" ) ? void (0) : __assert_fail ("MO.isReg() && \"Invalid PHI instruction\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 2052, __extension__ __PRETTY_FUNCTION__)); | |||
2053 | // We have no code to deal with undef operands. They shouldn't happen in | |||
2054 | // normal programs anyway. | |||
2055 | if (MO.isUndef()) | |||
2056 | return ValueTrackerResult(); | |||
2057 | Res.addSource(MO.getReg(), MO.getSubReg()); | |||
2058 | } | |||
2059 | ||||
2060 | return Res; | |||
2061 | } | |||
2062 | ||||
2063 | ValueTrackerResult ValueTracker::getNextSourceImpl() { | |||
2064 | assert(Def && "This method needs a valid definition")(static_cast <bool> (Def && "This method needs a valid definition" ) ? void (0) : __assert_fail ("Def && \"This method needs a valid definition\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 2064, __extension__ __PRETTY_FUNCTION__)); | |||
2065 | ||||
2066 | assert(((Def->getOperand(DefIdx).isDef() &&(static_cast <bool> (((Def->getOperand(DefIdx).isDef () && (DefIdx < Def->getDesc().getNumDefs() || Def ->getDesc().isVariadic())) || Def->getOperand(DefIdx).isImplicit ()) && "Invalid DefIdx") ? void (0) : __assert_fail ( "((Def->getOperand(DefIdx).isDef() && (DefIdx < Def->getDesc().getNumDefs() || Def->getDesc().isVariadic())) || Def->getOperand(DefIdx).isImplicit()) && \"Invalid DefIdx\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 2070, __extension__ __PRETTY_FUNCTION__)) | |||
2067 | (DefIdx < Def->getDesc().getNumDefs() ||(static_cast <bool> (((Def->getOperand(DefIdx).isDef () && (DefIdx < Def->getDesc().getNumDefs() || Def ->getDesc().isVariadic())) || Def->getOperand(DefIdx).isImplicit ()) && "Invalid DefIdx") ? void (0) : __assert_fail ( "((Def->getOperand(DefIdx).isDef() && (DefIdx < Def->getDesc().getNumDefs() || Def->getDesc().isVariadic())) || Def->getOperand(DefIdx).isImplicit()) && \"Invalid DefIdx\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 2070, __extension__ __PRETTY_FUNCTION__)) | |||
2068 | Def->getDesc().isVariadic())) ||(static_cast <bool> (((Def->getOperand(DefIdx).isDef () && (DefIdx < Def->getDesc().getNumDefs() || Def ->getDesc().isVariadic())) || Def->getOperand(DefIdx).isImplicit ()) && "Invalid DefIdx") ? void (0) : __assert_fail ( "((Def->getOperand(DefIdx).isDef() && (DefIdx < Def->getDesc().getNumDefs() || Def->getDesc().isVariadic())) || Def->getOperand(DefIdx).isImplicit()) && \"Invalid DefIdx\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 2070, __extension__ __PRETTY_FUNCTION__)) | |||
2069 | Def->getOperand(DefIdx).isImplicit()) &&(static_cast <bool> (((Def->getOperand(DefIdx).isDef () && (DefIdx < Def->getDesc().getNumDefs() || Def ->getDesc().isVariadic())) || Def->getOperand(DefIdx).isImplicit ()) && "Invalid DefIdx") ? void (0) : __assert_fail ( "((Def->getOperand(DefIdx).isDef() && (DefIdx < Def->getDesc().getNumDefs() || Def->getDesc().isVariadic())) || Def->getOperand(DefIdx).isImplicit()) && \"Invalid DefIdx\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 2070, __extension__ __PRETTY_FUNCTION__)) | |||
2070 | "Invalid DefIdx")(static_cast <bool> (((Def->getOperand(DefIdx).isDef () && (DefIdx < Def->getDesc().getNumDefs() || Def ->getDesc().isVariadic())) || Def->getOperand(DefIdx).isImplicit ()) && "Invalid DefIdx") ? void (0) : __assert_fail ( "((Def->getOperand(DefIdx).isDef() && (DefIdx < Def->getDesc().getNumDefs() || Def->getDesc().isVariadic())) || Def->getOperand(DefIdx).isImplicit()) && \"Invalid DefIdx\"" , "llvm/lib/CodeGen/PeepholeOptimizer.cpp", 2070, __extension__ __PRETTY_FUNCTION__)); | |||
2071 | if (Def->isCopy()) | |||
2072 | return getNextSourceFromCopy(); | |||
2073 | if (Def->isBitcast()) | |||
2074 | return getNextSourceFromBitcast(); | |||
2075 | // All the remaining cases involve "complex" instructions. | |||
2076 | // Bail if we did not ask for the advanced tracking. | |||
2077 | if (DisableAdvCopyOpt) | |||
2078 | return ValueTrackerResult(); | |||
2079 | if (Def->isRegSequence() || Def->isRegSequenceLike()) | |||
2080 | return getNextSourceFromRegSequence(); | |||
2081 | if (Def->isInsertSubreg() || Def->isInsertSubregLike()) | |||
2082 | return getNextSourceFromInsertSubreg(); | |||
2083 | if (Def->isExtractSubreg() || Def->isExtractSubregLike()) | |||
2084 | return getNextSourceFromExtractSubreg(); | |||
2085 | if (Def->isSubregToReg()) | |||
2086 | return getNextSourceFromSubregToReg(); | |||
2087 | if (Def->isPHI()) | |||
2088 | return getNextSourceFromPHI(); | |||
2089 | return ValueTrackerResult(); | |||
2090 | } | |||
2091 | ||||
2092 | ValueTrackerResult ValueTracker::getNextSource() { | |||
2093 | // If we reach a point where we cannot move up in the use-def chain, | |||
2094 | // there is nothing we can get. | |||
2095 | if (!Def) | |||
2096 | return ValueTrackerResult(); | |||
2097 | ||||
2098 | ValueTrackerResult Res = getNextSourceImpl(); | |||
2099 | if (Res.isValid()) { | |||
2100 | // Update definition, definition index, and subregister for the | |||
2101 | // next call of getNextSource. | |||
2102 | // Update the current register. | |||
2103 | bool OneRegSrc = Res.getNumSources() == 1; | |||
2104 | if (OneRegSrc) | |||
2105 | Reg = Res.getSrcReg(0); | |||
2106 | // Update the result before moving up in the use-def chain | |||
2107 | // with the instruction containing the last found sources. | |||
2108 | Res.setInst(Def); | |||
2109 | ||||
2110 | // If we can still move up in the use-def chain, move to the next | |||
2111 | // definition. | |||
2112 | if (!Register::isPhysicalRegister(Reg) && OneRegSrc) { | |||
2113 | MachineRegisterInfo::def_iterator DI = MRI.def_begin(Reg); | |||
2114 | if (DI != MRI.def_end()) { | |||
2115 | Def = DI->getParent(); | |||
2116 | DefIdx = DI.getOperandNo(); | |||
2117 | DefSubReg = Res.getSrcSubReg(0); | |||
2118 | } else { | |||
2119 | Def = nullptr; | |||
2120 | } | |||
2121 | return Res; | |||
2122 | } | |||
2123 | } | |||
2124 | // If we end up here, this means we will not be able to find another source | |||
2125 | // for the next iteration. Make sure any new call to getNextSource bails out | |||
2126 | // early by cutting the use-def chain. | |||
2127 | Def = nullptr; | |||
2128 | return Res; | |||
2129 | } |