Bug Summary

File:lib/CodeGen/PeepholeOptimizer.cpp
Warning:line 512, column 30
Called C++ object pointer is null

Annotated Source Code

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