1 //===- PeepholeOptimizer.cpp - Peephole Optimizations ---------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // Perform peephole optimizations on the machine code:
11 // - Optimize Extensions
13 // Optimization of sign / zero extension instructions. It may be extended to
14 // handle other instructions with similar properties.
16 // On some targets, some instructions, e.g. X86 sign / zero extension, may
17 // leave the source value in the lower part of the result. This optimization
18 // will replace some uses of the pre-extension value with uses of the
19 // sub-register of the results.
21 // - Optimize Comparisons
23 // Optimization of comparison instructions. For instance, in this code:
29 // If the "sub" instruction all ready sets (or could be modified to set) the
30 // same flag that the "cmp" instruction sets and that "bz" uses, then we can
31 // eliminate the "cmp" instruction.
33 // Another instance, in this code:
35 // sub r1, r3 | sub r1, imm
36 // cmp r3, r1 or cmp r1, r3 | cmp r1, imm
39 // If the branch instruction can use flag from "sub", then we can replace
40 // "sub" with "subs" and eliminate the "cmp" instruction.
44 // Loads that can be folded into a later instruction. A load is foldable
45 // if it loads to virtual registers and the virtual register defined has
48 // - Optimize Copies and Bitcast (more generally, target specific copies):
50 // Rewrite copies and bitcasts to avoid cross register bank copies
52 // E.g., Consider the following example, where capital and lower
53 // letters denote different register file:
54 // b = copy A <-- cross-bank copy
55 // C = copy b <-- cross-bank copy
57 // b = copy A <-- cross-bank copy
58 // C = copy A <-- same-bank copy
61 // b = bitcast A <-- cross-bank copy
62 // C = bitcast b <-- cross-bank copy
64 // b = bitcast A <-- cross-bank copy
65 // C = copy A <-- same-bank copy
66 //===----------------------------------------------------------------------===//
68 #include "llvm/ADT/DenseMap.h"
69 #include "llvm/ADT/Optional.h"
70 #include "llvm/ADT/SmallPtrSet.h"
71 #include "llvm/ADT/SmallSet.h"
72 #include "llvm/ADT/SmallVector.h"
73 #include "llvm/ADT/Statistic.h"
74 #include "llvm/CodeGen/MachineBasicBlock.h"
75 #include "llvm/CodeGen/MachineDominators.h"
76 #include "llvm/CodeGen/MachineFunction.h"
77 #include "llvm/CodeGen/MachineFunctionPass.h"
78 #include "llvm/CodeGen/MachineInstr.h"
79 #include "llvm/CodeGen/MachineInstrBuilder.h"
80 #include "llvm/CodeGen/MachineLoopInfo.h"
81 #include "llvm/CodeGen/MachineOperand.h"
82 #include "llvm/CodeGen/MachineRegisterInfo.h"
83 #include "llvm/CodeGen/TargetInstrInfo.h"
84 #include "llvm/CodeGen/TargetOpcodes.h"
85 #include "llvm/CodeGen/TargetRegisterInfo.h"
86 #include "llvm/CodeGen/TargetSubtargetInfo.h"
87 #include "llvm/MC/LaneBitmask.h"
88 #include "llvm/MC/MCInstrDesc.h"
89 #include "llvm/Pass.h"
90 #include "llvm/Support/CommandLine.h"
91 #include "llvm/Support/Debug.h"
92 #include "llvm/Support/ErrorHandling.h"
93 #include "llvm/Support/raw_ostream.h"
100 using RegSubRegPair
= TargetInstrInfo::RegSubRegPair
;
101 using RegSubRegPairAndIdx
= TargetInstrInfo::RegSubRegPairAndIdx
;
103 #define DEBUG_TYPE "peephole-opt"
105 // Optimize Extensions
107 Aggressive("aggressive-ext-opt", cl::Hidden
,
108 cl::desc("Aggressive extension optimization"));
111 DisablePeephole("disable-peephole", cl::Hidden
, cl::init(false),
112 cl::desc("Disable the peephole optimizer"));
114 /// Specifiy whether or not the value tracking looks through
115 /// complex instructions. When this is true, the value tracker
116 /// bails on everything that is not a copy or a bitcast.
118 DisableAdvCopyOpt("disable-adv-copy-opt", cl::Hidden
, cl::init(false),
119 cl::desc("Disable advanced copy optimization"));
121 static cl::opt
<bool> DisableNAPhysCopyOpt(
122 "disable-non-allocatable-phys-copy-opt", cl::Hidden
, cl::init(false),
123 cl::desc("Disable non-allocatable physical register copy optimization"));
125 // Limit the number of PHI instructions to process
126 // in PeepholeOptimizer::getNextSource.
127 static cl::opt
<unsigned> RewritePHILimit(
128 "rewrite-phi-limit", cl::Hidden
, cl::init(10),
129 cl::desc("Limit the length of PHI chains to lookup"));
131 // Limit the length of recurrence chain when evaluating the benefit of
132 // commuting operands.
133 static cl::opt
<unsigned> MaxRecurrenceChain(
134 "recurrence-chain-limit", cl::Hidden
, cl::init(3),
135 cl::desc("Maximum length of recurrence chain when evaluating the benefit "
136 "of commuting operands"));
139 STATISTIC(NumReuse
, "Number of extension results reused");
140 STATISTIC(NumCmps
, "Number of compares eliminated");
141 STATISTIC(NumImmFold
, "Number of move immediate folded");
142 STATISTIC(NumLoadFold
, "Number of loads folded");
143 STATISTIC(NumSelects
, "Number of selects optimized");
144 STATISTIC(NumUncoalescableCopies
, "Number of uncoalescable copies optimized");
145 STATISTIC(NumRewrittenCopies
, "Number of copies rewritten");
146 STATISTIC(NumNAPhysCopies
, "Number of non-allocatable physical copies removed");
150 class ValueTrackerResult
;
151 class RecurrenceInstr
;
153 class PeepholeOptimizer
: public MachineFunctionPass
{
154 const TargetInstrInfo
*TII
;
155 const TargetRegisterInfo
*TRI
;
156 MachineRegisterInfo
*MRI
;
157 MachineDominatorTree
*DT
; // Machine dominator tree
158 MachineLoopInfo
*MLI
;
161 static char ID
; // Pass identification
163 PeepholeOptimizer() : MachineFunctionPass(ID
) {
164 initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry());
167 bool runOnMachineFunction(MachineFunction
&MF
) override
;
169 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
170 AU
.setPreservesCFG();
171 MachineFunctionPass::getAnalysisUsage(AU
);
172 AU
.addRequired
<MachineLoopInfo
>();
173 AU
.addPreserved
<MachineLoopInfo
>();
175 AU
.addRequired
<MachineDominatorTree
>();
176 AU
.addPreserved
<MachineDominatorTree
>();
180 /// Track Def -> Use info used for rewriting copies.
181 using RewriteMapTy
= SmallDenseMap
<RegSubRegPair
, ValueTrackerResult
>;
183 /// Sequence of instructions that formulate recurrence cycle.
184 using RecurrenceCycle
= SmallVector
<RecurrenceInstr
, 4>;
187 bool optimizeCmpInstr(MachineInstr
&MI
);
188 bool optimizeExtInstr(MachineInstr
&MI
, MachineBasicBlock
&MBB
,
189 SmallPtrSetImpl
<MachineInstr
*> &LocalMIs
);
190 bool optimizeSelect(MachineInstr
&MI
,
191 SmallPtrSetImpl
<MachineInstr
*> &LocalMIs
);
192 bool optimizeCondBranch(MachineInstr
&MI
);
193 bool optimizeCoalescableCopy(MachineInstr
&MI
);
194 bool optimizeUncoalescableCopy(MachineInstr
&MI
,
195 SmallPtrSetImpl
<MachineInstr
*> &LocalMIs
);
196 bool optimizeRecurrence(MachineInstr
&PHI
);
197 bool findNextSource(RegSubRegPair RegSubReg
, RewriteMapTy
&RewriteMap
);
198 bool isMoveImmediate(MachineInstr
&MI
,
199 SmallSet
<unsigned, 4> &ImmDefRegs
,
200 DenseMap
<unsigned, MachineInstr
*> &ImmDefMIs
);
201 bool foldImmediate(MachineInstr
&MI
, SmallSet
<unsigned, 4> &ImmDefRegs
,
202 DenseMap
<unsigned, MachineInstr
*> &ImmDefMIs
);
204 /// Finds recurrence cycles, but only ones that formulated around
205 /// a def operand and a use operand that are tied. If there is a use
206 /// operand commutable with the tied use operand, find recurrence cycle
207 /// along that operand as well.
208 bool findTargetRecurrence(unsigned Reg
,
209 const SmallSet
<unsigned, 2> &TargetReg
,
210 RecurrenceCycle
&RC
);
212 /// If copy instruction \p MI is a virtual register copy, track it in
213 /// the set \p CopySrcRegs and \p CopyMIs. If this virtual register was
214 /// previously seen as a copy, replace the uses of this copy with the
215 /// previously seen copy's destination register.
216 bool foldRedundantCopy(MachineInstr
&MI
,
217 SmallSet
<unsigned, 4> &CopySrcRegs
,
218 DenseMap
<unsigned, MachineInstr
*> &CopyMIs
);
220 /// Is the register \p Reg a non-allocatable physical register?
221 bool isNAPhysCopy(unsigned Reg
);
223 /// If copy instruction \p MI is a non-allocatable virtual<->physical
224 /// register copy, track it in the \p NAPhysToVirtMIs map. If this
225 /// non-allocatable physical register was previously copied to a virtual
226 /// registered and hasn't been clobbered, the virt->phys copy can be
228 bool foldRedundantNAPhysCopy(MachineInstr
&MI
,
229 DenseMap
<unsigned, MachineInstr
*> &NAPhysToVirtMIs
);
231 bool isLoadFoldable(MachineInstr
&MI
,
232 SmallSet
<unsigned, 16> &FoldAsLoadDefCandidates
);
234 /// Check whether \p MI is understood by the register coalescer
235 /// but may require some rewriting.
236 bool isCoalescableCopy(const MachineInstr
&MI
) {
237 // SubregToRegs are not interesting, because they are already register
238 // coalescer friendly.
239 return MI
.isCopy() || (!DisableAdvCopyOpt
&&
240 (MI
.isRegSequence() || MI
.isInsertSubreg() ||
241 MI
.isExtractSubreg()));
244 /// Check whether \p MI is a copy like instruction that is
245 /// not recognized by the register coalescer.
246 bool isUncoalescableCopy(const MachineInstr
&MI
) {
247 return MI
.isBitcast() ||
248 (!DisableAdvCopyOpt
&&
249 (MI
.isRegSequenceLike() || MI
.isInsertSubregLike() ||
250 MI
.isExtractSubregLike()));
253 MachineInstr
&rewriteSource(MachineInstr
&CopyLike
,
254 RegSubRegPair Def
, RewriteMapTy
&RewriteMap
);
257 /// Helper class to hold instructions that are inside recurrence cycles.
258 /// The recurrence cycle is formulated around 1) a def operand and its
259 /// tied use operand, or 2) a def operand and a use operand that is commutable
260 /// with another use operand which is tied to the def operand. In the latter
261 /// case, index of the tied use operand and the commutable use operand are
262 /// maintained with CommutePair.
263 class RecurrenceInstr
{
265 using IndexPair
= std::pair
<unsigned, unsigned>;
267 RecurrenceInstr(MachineInstr
*MI
) : MI(MI
) {}
268 RecurrenceInstr(MachineInstr
*MI
, unsigned Idx1
, unsigned Idx2
)
269 : MI(MI
), CommutePair(std::make_pair(Idx1
, Idx2
)) {}
271 MachineInstr
*getMI() const { return MI
; }
272 Optional
<IndexPair
> getCommutePair() const { return CommutePair
; }
276 Optional
<IndexPair
> CommutePair
;
279 /// Helper class to hold a reply for ValueTracker queries.
280 /// Contains the returned sources for a given search and the instructions
281 /// where the sources were tracked from.
282 class ValueTrackerResult
{
284 /// Track all sources found by one ValueTracker query.
285 SmallVector
<RegSubRegPair
, 2> RegSrcs
;
287 /// Instruction using the sources in 'RegSrcs'.
288 const MachineInstr
*Inst
= nullptr;
291 ValueTrackerResult() = default;
293 ValueTrackerResult(unsigned Reg
, unsigned SubReg
) {
294 addSource(Reg
, SubReg
);
297 bool isValid() const { return getNumSources() > 0; }
299 void setInst(const MachineInstr
*I
) { Inst
= I
; }
300 const MachineInstr
*getInst() const { return Inst
; }
307 void addSource(unsigned SrcReg
, unsigned SrcSubReg
) {
308 RegSrcs
.push_back(RegSubRegPair(SrcReg
, SrcSubReg
));
311 void setSource(int Idx
, unsigned SrcReg
, unsigned SrcSubReg
) {
312 assert(Idx
< getNumSources() && "Reg pair source out of index");
313 RegSrcs
[Idx
] = RegSubRegPair(SrcReg
, SrcSubReg
);
316 int getNumSources() const { return RegSrcs
.size(); }
318 RegSubRegPair
getSrc(int Idx
) const {
322 unsigned getSrcReg(int Idx
) const {
323 assert(Idx
< getNumSources() && "Reg source out of index");
324 return RegSrcs
[Idx
].Reg
;
327 unsigned getSrcSubReg(int Idx
) const {
328 assert(Idx
< getNumSources() && "SubReg source out of index");
329 return RegSrcs
[Idx
].SubReg
;
332 bool operator==(const ValueTrackerResult
&Other
) {
333 if (Other
.getInst() != getInst())
336 if (Other
.getNumSources() != getNumSources())
339 for (int i
= 0, e
= Other
.getNumSources(); i
!= e
; ++i
)
340 if (Other
.getSrcReg(i
) != getSrcReg(i
) ||
341 Other
.getSrcSubReg(i
) != getSrcSubReg(i
))
347 /// Helper class to track the possible sources of a value defined by
348 /// a (chain of) copy related instructions.
349 /// Given a definition (instruction and definition index), this class
350 /// follows the use-def chain to find successive suitable sources.
351 /// The given source can be used to rewrite the definition into
354 /// For instance, let us consider the following snippet:
356 /// v2 = INSERT_SUBREG v1, v0, sub0
357 /// def = COPY v2.sub0
359 /// Using a ValueTracker for def = COPY v2.sub0 will give the following
360 /// suitable sources:
362 /// Then, def can be rewritten into def = COPY v0.
365 /// The current point into the use-def chain.
366 const MachineInstr
*Def
= nullptr;
368 /// The index of the definition in Def.
371 /// The sub register index of the definition.
374 /// The register where the value can be found.
377 /// MachineRegisterInfo used to perform tracking.
378 const MachineRegisterInfo
&MRI
;
380 /// Optional TargetInstrInfo used to perform some complex tracking.
381 const TargetInstrInfo
*TII
;
383 /// Dispatcher to the right underlying implementation of getNextSource.
384 ValueTrackerResult
getNextSourceImpl();
386 /// Specialized version of getNextSource for Copy instructions.
387 ValueTrackerResult
getNextSourceFromCopy();
389 /// Specialized version of getNextSource for Bitcast instructions.
390 ValueTrackerResult
getNextSourceFromBitcast();
392 /// Specialized version of getNextSource for RegSequence instructions.
393 ValueTrackerResult
getNextSourceFromRegSequence();
395 /// Specialized version of getNextSource for InsertSubreg instructions.
396 ValueTrackerResult
getNextSourceFromInsertSubreg();
398 /// Specialized version of getNextSource for ExtractSubreg instructions.
399 ValueTrackerResult
getNextSourceFromExtractSubreg();
401 /// Specialized version of getNextSource for SubregToReg instructions.
402 ValueTrackerResult
getNextSourceFromSubregToReg();
404 /// Specialized version of getNextSource for PHI instructions.
405 ValueTrackerResult
getNextSourceFromPHI();
408 /// Create a ValueTracker instance for the value defined by \p Reg.
409 /// \p DefSubReg represents the sub register index the value tracker will
410 /// track. It does not need to match the sub register index used in the
411 /// definition of \p Reg.
412 /// If \p Reg is a physical register, a value tracker constructed with
413 /// this constructor will not find any alternative source.
414 /// Indeed, when \p Reg is a physical register that constructor does not
415 /// know which definition of \p Reg it should track.
416 /// Use the next constructor to track a physical register.
417 ValueTracker(unsigned Reg
, unsigned DefSubReg
,
418 const MachineRegisterInfo
&MRI
,
419 const TargetInstrInfo
*TII
= nullptr)
420 : DefSubReg(DefSubReg
), Reg(Reg
), MRI(MRI
), TII(TII
) {
421 if (!Register::isPhysicalRegister(Reg
)) {
422 Def
= MRI
.getVRegDef(Reg
);
423 DefIdx
= MRI
.def_begin(Reg
).getOperandNo();
427 /// Following the use-def chain, get the next available source
428 /// for the tracked value.
429 /// \return A ValueTrackerResult containing a set of registers
430 /// and sub registers with tracked values. A ValueTrackerResult with
431 /// an empty set of registers means no source was found.
432 ValueTrackerResult
getNextSource();
435 } // end anonymous namespace
437 char PeepholeOptimizer::ID
= 0;
439 char &llvm::PeepholeOptimizerID
= PeepholeOptimizer::ID
;
441 INITIALIZE_PASS_BEGIN(PeepholeOptimizer
, DEBUG_TYPE
,
442 "Peephole Optimizations", false, false)
443 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree
)
444 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo
)
445 INITIALIZE_PASS_END(PeepholeOptimizer
, DEBUG_TYPE
,
446 "Peephole Optimizations", false, false)
448 /// If instruction is a copy-like instruction, i.e. it reads a single register
449 /// and writes a single register and it does not modify the source, and if the
450 /// source value is preserved as a sub-register of the result, then replace all
451 /// reachable uses of the source with the subreg of the result.
453 /// Do not generate an EXTRACT that is used only in a debug use, as this changes
454 /// the code. Since this code does not currently share EXTRACTs, just ignore all
456 bool PeepholeOptimizer::
457 optimizeExtInstr(MachineInstr
&MI
, MachineBasicBlock
&MBB
,
458 SmallPtrSetImpl
<MachineInstr
*> &LocalMIs
) {
459 unsigned SrcReg
, DstReg
, SubIdx
;
460 if (!TII
->isCoalescableExtInstr(MI
, SrcReg
, DstReg
, SubIdx
))
463 if (Register::isPhysicalRegister(DstReg
) ||
464 Register::isPhysicalRegister(SrcReg
))
467 if (MRI
->hasOneNonDBGUse(SrcReg
))
471 // Ensure DstReg can get a register class that actually supports
472 // sub-registers. Don't change the class until we commit.
473 const TargetRegisterClass
*DstRC
= MRI
->getRegClass(DstReg
);
474 DstRC
= TRI
->getSubClassWithSubReg(DstRC
, SubIdx
);
478 // The ext instr may be operating on a sub-register of SrcReg as well.
479 // PPC::EXTSW is a 32 -> 64-bit sign extension, but it reads a 64-bit
481 // If UseSrcSubIdx is Set, SubIdx also applies to SrcReg, and only uses of
482 // SrcReg:SubIdx should be replaced.
484 TRI
->getSubClassWithSubReg(MRI
->getRegClass(SrcReg
), SubIdx
) != nullptr;
486 // The source has other uses. See if we can replace the other uses with use of
487 // the result of the extension.
488 SmallPtrSet
<MachineBasicBlock
*, 4> ReachedBBs
;
489 for (MachineInstr
&UI
: MRI
->use_nodbg_instructions(DstReg
))
490 ReachedBBs
.insert(UI
.getParent());
492 // Uses that are in the same BB of uses of the result of the instruction.
493 SmallVector
<MachineOperand
*, 8> Uses
;
495 // Uses that the result of the instruction can reach.
496 SmallVector
<MachineOperand
*, 8> ExtendedUses
;
498 bool ExtendLife
= true;
499 for (MachineOperand
&UseMO
: MRI
->use_nodbg_operands(SrcReg
)) {
500 MachineInstr
*UseMI
= UseMO
.getParent();
504 if (UseMI
->isPHI()) {
509 // Only accept uses of SrcReg:SubIdx.
510 if (UseSrcSubIdx
&& UseMO
.getSubReg() != SubIdx
)
513 // It's an error to translate this:
515 // %reg1025 = <sext> %reg1024
517 // %reg1026 = SUBREG_TO_REG 0, %reg1024, 4
521 // %reg1025 = <sext> %reg1024
523 // %reg1027 = COPY %reg1025:4
524 // %reg1026 = SUBREG_TO_REG 0, %reg1027, 4
526 // The problem here is that SUBREG_TO_REG is there to assert that an
527 // implicit zext occurs. It doesn't insert a zext instruction. If we allow
528 // the COPY here, it will give us the value after the <sext>, not the
529 // original value of %reg1024 before <sext>.
530 if (UseMI
->getOpcode() == TargetOpcode::SUBREG_TO_REG
)
533 MachineBasicBlock
*UseMBB
= UseMI
->getParent();
534 if (UseMBB
== &MBB
) {
535 // Local uses that come after the extension.
536 if (!LocalMIs
.count(UseMI
))
537 Uses
.push_back(&UseMO
);
538 } else if (ReachedBBs
.count(UseMBB
)) {
539 // Non-local uses where the result of the extension is used. Always
540 // replace these unless it's a PHI.
541 Uses
.push_back(&UseMO
);
542 } else if (Aggressive
&& DT
->dominates(&MBB
, UseMBB
)) {
543 // We may want to extend the live range of the extension result in order
544 // to replace these uses.
545 ExtendedUses
.push_back(&UseMO
);
547 // Both will be live out of the def MBB anyway. Don't extend live range of
548 // the extension result.
554 if (ExtendLife
&& !ExtendedUses
.empty())
555 // Extend the liveness of the extension result.
556 Uses
.append(ExtendedUses
.begin(), ExtendedUses
.end());
558 // Now replace all uses.
559 bool Changed
= false;
561 SmallPtrSet
<MachineBasicBlock
*, 4> PHIBBs
;
563 // Look for PHI uses of the extended result, we don't want to extend the
564 // liveness of a PHI input. It breaks all kinds of assumptions down
565 // stream. A PHI use is expected to be the kill of its source values.
566 for (MachineInstr
&UI
: MRI
->use_nodbg_instructions(DstReg
))
568 PHIBBs
.insert(UI
.getParent());
570 const TargetRegisterClass
*RC
= MRI
->getRegClass(SrcReg
);
571 for (unsigned i
= 0, e
= Uses
.size(); i
!= e
; ++i
) {
572 MachineOperand
*UseMO
= Uses
[i
];
573 MachineInstr
*UseMI
= UseMO
->getParent();
574 MachineBasicBlock
*UseMBB
= UseMI
->getParent();
575 if (PHIBBs
.count(UseMBB
))
578 // About to add uses of DstReg, clear DstReg's kill flags.
580 MRI
->clearKillFlags(DstReg
);
581 MRI
->constrainRegClass(DstReg
, DstRC
);
584 Register NewVR
= MRI
->createVirtualRegister(RC
);
585 MachineInstr
*Copy
= BuildMI(*UseMBB
, UseMI
, UseMI
->getDebugLoc(),
586 TII
->get(TargetOpcode::COPY
), NewVR
)
587 .addReg(DstReg
, 0, SubIdx
);
588 // SubIdx applies to both SrcReg and DstReg when UseSrcSubIdx is set.
590 Copy
->getOperand(0).setSubReg(SubIdx
);
591 Copy
->getOperand(0).setIsUndef();
593 UseMO
->setReg(NewVR
);
602 /// If the instruction is a compare and the previous instruction it's comparing
603 /// against already sets (or could be modified to set) the same flag as the
604 /// compare, then we can remove the comparison and use the flag from the
605 /// previous instruction.
606 bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr
&MI
) {
607 // If this instruction is a comparison against zero and isn't comparing a
608 // physical register, we can try to optimize it.
609 unsigned SrcReg
, SrcReg2
;
610 int CmpMask
, CmpValue
;
611 if (!TII
->analyzeCompare(MI
, SrcReg
, SrcReg2
, CmpMask
, CmpValue
) ||
612 Register::isPhysicalRegister(SrcReg
) ||
613 (SrcReg2
!= 0 && Register::isPhysicalRegister(SrcReg2
)))
616 // Attempt to optimize the comparison instruction.
617 if (TII
->optimizeCompareInstr(MI
, SrcReg
, SrcReg2
, CmpMask
, CmpValue
, MRI
)) {
625 /// Optimize a select instruction.
626 bool PeepholeOptimizer::optimizeSelect(MachineInstr
&MI
,
627 SmallPtrSetImpl
<MachineInstr
*> &LocalMIs
) {
629 unsigned FalseOp
= 0;
630 bool Optimizable
= false;
631 SmallVector
<MachineOperand
, 4> Cond
;
632 if (TII
->analyzeSelect(MI
, Cond
, TrueOp
, FalseOp
, Optimizable
))
636 if (!TII
->optimizeSelect(MI
, LocalMIs
))
638 MI
.eraseFromParent();
643 /// Check if a simpler conditional branch can be generated.
644 bool PeepholeOptimizer::optimizeCondBranch(MachineInstr
&MI
) {
645 return TII
->optimizeCondBranch(MI
);
648 /// Try to find the next source that share the same register file
649 /// for the value defined by \p Reg and \p SubReg.
650 /// When true is returned, the \p RewriteMap can be used by the client to
651 /// retrieve all Def -> Use along the way up to the next source. Any found
652 /// Use that is not itself a key for another entry, is the next source to
653 /// use. During the search for the next source, multiple sources can be found
654 /// given multiple incoming sources of a PHI instruction. In this case, we
655 /// look in each PHI source for the next source; all found next sources must
656 /// share the same register file as \p Reg and \p SubReg. The client should
657 /// then be capable to rewrite all intermediate PHIs to get the next source.
658 /// \return False if no alternative sources are available. True otherwise.
659 bool PeepholeOptimizer::findNextSource(RegSubRegPair RegSubReg
,
660 RewriteMapTy
&RewriteMap
) {
661 // Do not try to find a new source for a physical register.
662 // So far we do not have any motivating example for doing that.
663 // Thus, instead of maintaining untested code, we will revisit that if
664 // that changes at some point.
665 unsigned Reg
= RegSubReg
.Reg
;
666 if (Register::isPhysicalRegister(Reg
))
668 const TargetRegisterClass
*DefRC
= MRI
->getRegClass(Reg
);
670 SmallVector
<RegSubRegPair
, 4> SrcToLook
;
671 RegSubRegPair CurSrcPair
= RegSubReg
;
672 SrcToLook
.push_back(CurSrcPair
);
674 unsigned PHICount
= 0;
676 CurSrcPair
= SrcToLook
.pop_back_val();
677 // As explained above, do not handle physical registers
678 if (Register::isPhysicalRegister(CurSrcPair
.Reg
))
681 ValueTracker
ValTracker(CurSrcPair
.Reg
, CurSrcPair
.SubReg
, *MRI
, TII
);
683 // Follow the chain of copies until we find a more suitable source, a phi
686 ValueTrackerResult Res
= ValTracker
.getNextSource();
687 // Abort at the end of a chain (without finding a suitable source).
691 // Insert the Def -> Use entry for the recently found source.
692 ValueTrackerResult CurSrcRes
= RewriteMap
.lookup(CurSrcPair
);
693 if (CurSrcRes
.isValid()) {
694 assert(CurSrcRes
== Res
&& "ValueTrackerResult found must match");
695 // An existent entry with multiple sources is a PHI cycle we must avoid.
696 // Otherwise it's an entry with a valid next source we already found.
697 if (CurSrcRes
.getNumSources() > 1) {
699 << "findNextSource: found PHI cycle, aborting...\n");
704 RewriteMap
.insert(std::make_pair(CurSrcPair
, Res
));
706 // ValueTrackerResult usually have one source unless it's the result from
707 // a PHI instruction. Add the found PHI edges to be looked up further.
708 unsigned NumSrcs
= Res
.getNumSources();
711 if (PHICount
>= RewritePHILimit
) {
712 LLVM_DEBUG(dbgs() << "findNextSource: PHI limit reached\n");
716 for (unsigned i
= 0; i
< NumSrcs
; ++i
)
717 SrcToLook
.push_back(Res
.getSrc(i
));
721 CurSrcPair
= Res
.getSrc(0);
722 // Do not extend the live-ranges of physical registers as they add
723 // constraints to the register allocator. Moreover, if we want to extend
724 // the live-range of a physical register, unlike SSA virtual register,
725 // we will have to check that they aren't redefine before the related use.
726 if (Register::isPhysicalRegister(CurSrcPair
.Reg
))
729 // Keep following the chain if the value isn't any better yet.
730 const TargetRegisterClass
*SrcRC
= MRI
->getRegClass(CurSrcPair
.Reg
);
731 if (!TRI
->shouldRewriteCopySrc(DefRC
, RegSubReg
.SubReg
, SrcRC
,
735 // We currently cannot deal with subreg operands on PHI instructions
736 // (see insertPHI()).
737 if (PHICount
> 0 && CurSrcPair
.SubReg
!= 0)
740 // We found a suitable source, and are done with this chain.
743 } while (!SrcToLook
.empty());
745 // If we did not find a more suitable source, there is nothing to optimize.
746 return CurSrcPair
.Reg
!= Reg
;
749 /// Insert a PHI instruction with incoming edges \p SrcRegs that are
750 /// guaranteed to have the same register class. This is necessary whenever we
751 /// successfully traverse a PHI instruction and find suitable sources coming
752 /// from its edges. By inserting a new PHI, we provide a rewritten PHI def
753 /// suitable to be used in a new COPY instruction.
754 static MachineInstr
&
755 insertPHI(MachineRegisterInfo
&MRI
, const TargetInstrInfo
&TII
,
756 const SmallVectorImpl
<RegSubRegPair
> &SrcRegs
,
757 MachineInstr
&OrigPHI
) {
758 assert(!SrcRegs
.empty() && "No sources to create a PHI instruction?");
760 const TargetRegisterClass
*NewRC
= MRI
.getRegClass(SrcRegs
[0].Reg
);
761 // NewRC is only correct if no subregisters are involved. findNextSource()
762 // should have rejected those cases already.
763 assert(SrcRegs
[0].SubReg
== 0 && "should not have subreg operand");
764 Register NewVR
= MRI
.createVirtualRegister(NewRC
);
765 MachineBasicBlock
*MBB
= OrigPHI
.getParent();
766 MachineInstrBuilder MIB
= BuildMI(*MBB
, &OrigPHI
, OrigPHI
.getDebugLoc(),
767 TII
.get(TargetOpcode::PHI
), NewVR
);
769 unsigned MBBOpIdx
= 2;
770 for (const RegSubRegPair
&RegPair
: SrcRegs
) {
771 MIB
.addReg(RegPair
.Reg
, 0, RegPair
.SubReg
);
772 MIB
.addMBB(OrigPHI
.getOperand(MBBOpIdx
).getMBB());
773 // Since we're extended the lifetime of RegPair.Reg, clear the
774 // kill flags to account for that and make RegPair.Reg reaches
776 MRI
.clearKillFlags(RegPair
.Reg
);
785 /// Interface to query instructions amenable to copy rewriting.
788 MachineInstr
&CopyLike
;
789 unsigned CurrentSrcIdx
= 0; ///< The index of the source being rewritten.
791 Rewriter(MachineInstr
&CopyLike
) : CopyLike(CopyLike
) {}
792 virtual ~Rewriter() {}
794 /// Get the next rewritable source (SrcReg, SrcSubReg) and
795 /// the related value that it affects (DstReg, DstSubReg).
796 /// A source is considered rewritable if its register class and the
797 /// register class of the related DstReg may not be register
798 /// coalescer friendly. In other words, given a copy-like instruction
799 /// not all the arguments may be returned at rewritable source, since
800 /// some arguments are none to be register coalescer friendly.
802 /// Each call of this method moves the current source to the next
803 /// rewritable source.
804 /// For instance, let CopyLike be the instruction to rewrite.
805 /// CopyLike has one definition and one source:
806 /// dst.dstSubIdx = CopyLike src.srcSubIdx.
808 /// The first call will give the first rewritable source, i.e.,
809 /// the only source this instruction has:
810 /// (SrcReg, SrcSubReg) = (src, srcSubIdx).
811 /// This source defines the whole definition, i.e.,
812 /// (DstReg, DstSubReg) = (dst, dstSubIdx).
814 /// The second and subsequent calls will return false, as there is only one
815 /// rewritable source.
817 /// \return True if a rewritable source has been found, false otherwise.
818 /// The output arguments are valid if and only if true is returned.
819 virtual bool getNextRewritableSource(RegSubRegPair
&Src
,
820 RegSubRegPair
&Dst
) = 0;
822 /// Rewrite the current source with \p NewReg and \p NewSubReg if possible.
823 /// \return True if the rewriting was possible, false otherwise.
824 virtual bool RewriteCurrentSource(unsigned NewReg
, unsigned NewSubReg
) = 0;
827 /// Rewriter for COPY instructions.
828 class CopyRewriter
: public Rewriter
{
830 CopyRewriter(MachineInstr
&MI
) : Rewriter(MI
) {
831 assert(MI
.isCopy() && "Expected copy instruction");
833 virtual ~CopyRewriter() = default;
835 bool getNextRewritableSource(RegSubRegPair
&Src
,
836 RegSubRegPair
&Dst
) override
{
837 // CurrentSrcIdx > 0 means this function has already been called.
838 if (CurrentSrcIdx
> 0)
840 // This is the first call to getNextRewritableSource.
841 // Move the CurrentSrcIdx to remember that we made that call.
843 // The rewritable source is the argument.
844 const MachineOperand
&MOSrc
= CopyLike
.getOperand(1);
845 Src
= RegSubRegPair(MOSrc
.getReg(), MOSrc
.getSubReg());
846 // What we track are the alternative sources of the definition.
847 const MachineOperand
&MODef
= CopyLike
.getOperand(0);
848 Dst
= RegSubRegPair(MODef
.getReg(), MODef
.getSubReg());
852 bool RewriteCurrentSource(unsigned NewReg
, unsigned NewSubReg
) override
{
853 if (CurrentSrcIdx
!= 1)
855 MachineOperand
&MOSrc
= CopyLike
.getOperand(CurrentSrcIdx
);
856 MOSrc
.setReg(NewReg
);
857 MOSrc
.setSubReg(NewSubReg
);
862 /// Helper class to rewrite uncoalescable copy like instructions
863 /// into new COPY (coalescable friendly) instructions.
864 class UncoalescableRewriter
: public Rewriter
{
865 unsigned NumDefs
; ///< Number of defs in the bitcast.
868 UncoalescableRewriter(MachineInstr
&MI
) : Rewriter(MI
) {
869 NumDefs
= MI
.getDesc().getNumDefs();
872 /// \see See Rewriter::getNextRewritableSource()
873 /// All such sources need to be considered rewritable in order to
874 /// rewrite a uncoalescable copy-like instruction. This method return
875 /// each definition that must be checked if rewritable.
876 bool getNextRewritableSource(RegSubRegPair
&Src
,
877 RegSubRegPair
&Dst
) override
{
878 // Find the next non-dead definition and continue from there.
879 if (CurrentSrcIdx
== NumDefs
)
882 while (CopyLike
.getOperand(CurrentSrcIdx
).isDead()) {
884 if (CurrentSrcIdx
== NumDefs
)
888 // What we track are the alternative sources of the definition.
889 Src
= RegSubRegPair(0, 0);
890 const MachineOperand
&MODef
= CopyLike
.getOperand(CurrentSrcIdx
);
891 Dst
= RegSubRegPair(MODef
.getReg(), MODef
.getSubReg());
897 bool RewriteCurrentSource(unsigned NewReg
, unsigned NewSubReg
) override
{
902 /// Specialized rewriter for INSERT_SUBREG instruction.
903 class InsertSubregRewriter
: public Rewriter
{
905 InsertSubregRewriter(MachineInstr
&MI
) : Rewriter(MI
) {
906 assert(MI
.isInsertSubreg() && "Invalid instruction");
909 /// \see See Rewriter::getNextRewritableSource()
910 /// Here CopyLike has the following form:
911 /// dst = INSERT_SUBREG Src1, Src2.src2SubIdx, subIdx.
912 /// Src1 has the same register class has dst, hence, there is
913 /// nothing to rewrite.
914 /// Src2.src2SubIdx, may not be register coalescer friendly.
915 /// Therefore, the first call to this method returns:
916 /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx).
917 /// (DstReg, DstSubReg) = (dst, subIdx).
919 /// Subsequence calls will return false.
920 bool getNextRewritableSource(RegSubRegPair
&Src
,
921 RegSubRegPair
&Dst
) override
{
922 // If we already get the only source we can rewrite, return false.
923 if (CurrentSrcIdx
== 2)
925 // We are looking at v2 = INSERT_SUBREG v0, v1, sub0.
927 const MachineOperand
&MOInsertedReg
= CopyLike
.getOperand(2);
928 Src
= RegSubRegPair(MOInsertedReg
.getReg(), MOInsertedReg
.getSubReg());
929 const MachineOperand
&MODef
= CopyLike
.getOperand(0);
931 // We want to track something that is compatible with the
932 // partial definition.
933 if (MODef
.getSubReg())
934 // Bail if we have to compose sub-register indices.
936 Dst
= RegSubRegPair(MODef
.getReg(),
937 (unsigned)CopyLike
.getOperand(3).getImm());
941 bool RewriteCurrentSource(unsigned NewReg
, unsigned NewSubReg
) override
{
942 if (CurrentSrcIdx
!= 2)
944 // We are rewriting the inserted reg.
945 MachineOperand
&MO
= CopyLike
.getOperand(CurrentSrcIdx
);
947 MO
.setSubReg(NewSubReg
);
952 /// Specialized rewriter for EXTRACT_SUBREG instruction.
953 class ExtractSubregRewriter
: public Rewriter
{
954 const TargetInstrInfo
&TII
;
957 ExtractSubregRewriter(MachineInstr
&MI
, const TargetInstrInfo
&TII
)
958 : Rewriter(MI
), TII(TII
) {
959 assert(MI
.isExtractSubreg() && "Invalid instruction");
962 /// \see Rewriter::getNextRewritableSource()
963 /// Here CopyLike has the following form:
964 /// dst.dstSubIdx = EXTRACT_SUBREG Src, subIdx.
965 /// There is only one rewritable source: Src.subIdx,
966 /// which defines dst.dstSubIdx.
967 bool getNextRewritableSource(RegSubRegPair
&Src
,
968 RegSubRegPair
&Dst
) override
{
969 // If we already get the only source we can rewrite, return false.
970 if (CurrentSrcIdx
== 1)
972 // We are looking at v1 = EXTRACT_SUBREG v0, sub0.
974 const MachineOperand
&MOExtractedReg
= CopyLike
.getOperand(1);
975 // If we have to compose sub-register indices, bail out.
976 if (MOExtractedReg
.getSubReg())
979 Src
= RegSubRegPair(MOExtractedReg
.getReg(),
980 CopyLike
.getOperand(2).getImm());
982 // We want to track something that is compatible with the definition.
983 const MachineOperand
&MODef
= CopyLike
.getOperand(0);
984 Dst
= RegSubRegPair(MODef
.getReg(), MODef
.getSubReg());
988 bool RewriteCurrentSource(unsigned NewReg
, unsigned NewSubReg
) override
{
989 // The only source we can rewrite is the input register.
990 if (CurrentSrcIdx
!= 1)
993 CopyLike
.getOperand(CurrentSrcIdx
).setReg(NewReg
);
995 // If we find a source that does not require to extract something,
996 // rewrite the operation with a copy.
998 // Move the current index to an invalid position.
999 // We do not want another call to this method to be able
1000 // to do any change.
1002 // Rewrite the operation as a COPY.
1003 // Get rid of the sub-register index.
1004 CopyLike
.RemoveOperand(2);
1005 // Morph the operation into a COPY.
1006 CopyLike
.setDesc(TII
.get(TargetOpcode::COPY
));
1009 CopyLike
.getOperand(CurrentSrcIdx
+ 1).setImm(NewSubReg
);
1014 /// Specialized rewriter for REG_SEQUENCE instruction.
1015 class RegSequenceRewriter
: public Rewriter
{
1017 RegSequenceRewriter(MachineInstr
&MI
) : Rewriter(MI
) {
1018 assert(MI
.isRegSequence() && "Invalid instruction");
1021 /// \see Rewriter::getNextRewritableSource()
1022 /// Here CopyLike has the following form:
1023 /// dst = REG_SEQUENCE Src1.src1SubIdx, subIdx1, Src2.src2SubIdx, subIdx2.
1024 /// Each call will return a different source, walking all the available
1027 /// The first call returns:
1028 /// (SrcReg, SrcSubReg) = (Src1, src1SubIdx).
1029 /// (DstReg, DstSubReg) = (dst, subIdx1).
1031 /// The second call returns:
1032 /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx).
1033 /// (DstReg, DstSubReg) = (dst, subIdx2).
1035 /// And so on, until all the sources have been traversed, then
1036 /// it returns false.
1037 bool getNextRewritableSource(RegSubRegPair
&Src
,
1038 RegSubRegPair
&Dst
) override
{
1039 // We are looking at v0 = REG_SEQUENCE v1, sub1, v2, sub2, etc.
1041 // If this is the first call, move to the first argument.
1042 if (CurrentSrcIdx
== 0) {
1045 // Otherwise, move to the next argument and check that it is valid.
1047 if (CurrentSrcIdx
>= CopyLike
.getNumOperands())
1050 const MachineOperand
&MOInsertedReg
= CopyLike
.getOperand(CurrentSrcIdx
);
1051 Src
.Reg
= MOInsertedReg
.getReg();
1052 // If we have to compose sub-register indices, bail out.
1053 if ((Src
.SubReg
= MOInsertedReg
.getSubReg()))
1056 // We want to track something that is compatible with the related
1057 // partial definition.
1058 Dst
.SubReg
= CopyLike
.getOperand(CurrentSrcIdx
+ 1).getImm();
1060 const MachineOperand
&MODef
= CopyLike
.getOperand(0);
1061 Dst
.Reg
= MODef
.getReg();
1062 // If we have to compose sub-registers, bail.
1063 return MODef
.getSubReg() == 0;
1066 bool RewriteCurrentSource(unsigned NewReg
, unsigned NewSubReg
) override
{
1067 // We cannot rewrite out of bound operands.
1068 // Moreover, rewritable sources are at odd positions.
1069 if ((CurrentSrcIdx
& 1) != 1 || CurrentSrcIdx
> CopyLike
.getNumOperands())
1072 MachineOperand
&MO
= CopyLike
.getOperand(CurrentSrcIdx
);
1074 MO
.setSubReg(NewSubReg
);
1079 } // end anonymous namespace
1081 /// Get the appropriated Rewriter for \p MI.
1082 /// \return A pointer to a dynamically allocated Rewriter or nullptr if no
1083 /// rewriter works for \p MI.
1084 static Rewriter
*getCopyRewriter(MachineInstr
&MI
, const TargetInstrInfo
&TII
) {
1085 // Handle uncoalescable copy-like instructions.
1086 if (MI
.isBitcast() || MI
.isRegSequenceLike() || MI
.isInsertSubregLike() ||
1087 MI
.isExtractSubregLike())
1088 return new UncoalescableRewriter(MI
);
1090 switch (MI
.getOpcode()) {
1093 case TargetOpcode::COPY
:
1094 return new CopyRewriter(MI
);
1095 case TargetOpcode::INSERT_SUBREG
:
1096 return new InsertSubregRewriter(MI
);
1097 case TargetOpcode::EXTRACT_SUBREG
:
1098 return new ExtractSubregRewriter(MI
, TII
);
1099 case TargetOpcode::REG_SEQUENCE
:
1100 return new RegSequenceRewriter(MI
);
1104 /// Given a \p Def.Reg and Def.SubReg pair, use \p RewriteMap to find
1105 /// the new source to use for rewrite. If \p HandleMultipleSources is true and
1106 /// multiple sources for a given \p Def are found along the way, we found a
1107 /// PHI instructions that needs to be rewritten.
1108 /// TODO: HandleMultipleSources should be removed once we test PHI handling
1109 /// with coalescable copies.
1110 static RegSubRegPair
1111 getNewSource(MachineRegisterInfo
*MRI
, const TargetInstrInfo
*TII
,
1113 const PeepholeOptimizer::RewriteMapTy
&RewriteMap
,
1114 bool HandleMultipleSources
= true) {
1115 RegSubRegPair
LookupSrc(Def
.Reg
, Def
.SubReg
);
1117 ValueTrackerResult Res
= RewriteMap
.lookup(LookupSrc
);
1118 // If there are no entries on the map, LookupSrc is the new source.
1122 // There's only one source for this definition, keep searching...
1123 unsigned NumSrcs
= Res
.getNumSources();
1125 LookupSrc
.Reg
= Res
.getSrcReg(0);
1126 LookupSrc
.SubReg
= Res
.getSrcSubReg(0);
1130 // TODO: Remove once multiple srcs w/ coalescable copies are supported.
1131 if (!HandleMultipleSources
)
1134 // Multiple sources, recurse into each source to find a new source
1135 // for it. Then, rewrite the PHI accordingly to its new edges.
1136 SmallVector
<RegSubRegPair
, 4> NewPHISrcs
;
1137 for (unsigned i
= 0; i
< NumSrcs
; ++i
) {
1138 RegSubRegPair
PHISrc(Res
.getSrcReg(i
), Res
.getSrcSubReg(i
));
1139 NewPHISrcs
.push_back(
1140 getNewSource(MRI
, TII
, PHISrc
, RewriteMap
, HandleMultipleSources
));
1143 // Build the new PHI node and return its def register as the new source.
1144 MachineInstr
&OrigPHI
= const_cast<MachineInstr
&>(*Res
.getInst());
1145 MachineInstr
&NewPHI
= insertPHI(*MRI
, *TII
, NewPHISrcs
, OrigPHI
);
1146 LLVM_DEBUG(dbgs() << "-- getNewSource\n");
1147 LLVM_DEBUG(dbgs() << " Replacing: " << OrigPHI
);
1148 LLVM_DEBUG(dbgs() << " With: " << NewPHI
);
1149 const MachineOperand
&MODef
= NewPHI
.getOperand(0);
1150 return RegSubRegPair(MODef
.getReg(), MODef
.getSubReg());
1153 return RegSubRegPair(0, 0);
1156 /// Optimize generic copy instructions to avoid cross register bank copy.
1157 /// The optimization looks through a chain of copies and tries to find a source
1158 /// that has a compatible register class.
1159 /// Two register classes are considered to be compatible if they share the same
1161 /// New copies issued by this optimization are register allocator
1162 /// friendly. This optimization does not remove any copy as it may
1163 /// overconstrain the register allocator, but replaces some operands
1165 /// \pre isCoalescableCopy(*MI) is true.
1166 /// \return True, when \p MI has been rewritten. False otherwise.
1167 bool PeepholeOptimizer::optimizeCoalescableCopy(MachineInstr
&MI
) {
1168 assert(isCoalescableCopy(MI
) && "Invalid argument");
1169 assert(MI
.getDesc().getNumDefs() == 1 &&
1170 "Coalescer can understand multiple defs?!");
1171 const MachineOperand
&MODef
= MI
.getOperand(0);
1172 // Do not rewrite physical definitions.
1173 if (Register::isPhysicalRegister(MODef
.getReg()))
1176 bool Changed
= false;
1177 // Get the right rewriter for the current copy.
1178 std::unique_ptr
<Rewriter
> CpyRewriter(getCopyRewriter(MI
, *TII
));
1179 // If none exists, bail out.
1182 // Rewrite each rewritable source.
1184 RegSubRegPair TrackPair
;
1185 while (CpyRewriter
->getNextRewritableSource(Src
, TrackPair
)) {
1186 // Keep track of PHI nodes and its incoming edges when looking for sources.
1187 RewriteMapTy RewriteMap
;
1188 // Try to find a more suitable source. If we failed to do so, or get the
1189 // actual source, move to the next source.
1190 if (!findNextSource(TrackPair
, RewriteMap
))
1193 // Get the new source to rewrite. TODO: Only enable handling of multiple
1194 // sources (PHIs) once we have a motivating example and testcases for it.
1195 RegSubRegPair NewSrc
= getNewSource(MRI
, TII
, TrackPair
, RewriteMap
,
1196 /*HandleMultipleSources=*/false);
1197 if (Src
.Reg
== NewSrc
.Reg
|| NewSrc
.Reg
== 0)
1201 if (CpyRewriter
->RewriteCurrentSource(NewSrc
.Reg
, NewSrc
.SubReg
)) {
1202 // We may have extended the live-range of NewSrc, account for that.
1203 MRI
->clearKillFlags(NewSrc
.Reg
);
1207 // TODO: We could have a clean-up method to tidy the instruction.
1208 // E.g., v0 = INSERT_SUBREG v1, v1.sub0, sub0
1210 // Currently we haven't seen motivating example for that and we
1211 // want to avoid untested code.
1212 NumRewrittenCopies
+= Changed
;
1216 /// Rewrite the source found through \p Def, by using the \p RewriteMap
1217 /// and create a new COPY instruction. More info about RewriteMap in
1218 /// PeepholeOptimizer::findNextSource. Right now this is only used to handle
1219 /// Uncoalescable copies, since they are copy like instructions that aren't
1220 /// recognized by the register allocator.
1222 PeepholeOptimizer::rewriteSource(MachineInstr
&CopyLike
,
1223 RegSubRegPair Def
, RewriteMapTy
&RewriteMap
) {
1224 assert(!Register::isPhysicalRegister(Def
.Reg
) &&
1225 "We do not rewrite physical registers");
1227 // Find the new source to use in the COPY rewrite.
1228 RegSubRegPair NewSrc
= getNewSource(MRI
, TII
, Def
, RewriteMap
);
1231 const TargetRegisterClass
*DefRC
= MRI
->getRegClass(Def
.Reg
);
1232 Register NewVReg
= MRI
->createVirtualRegister(DefRC
);
1234 MachineInstr
*NewCopy
=
1235 BuildMI(*CopyLike
.getParent(), &CopyLike
, CopyLike
.getDebugLoc(),
1236 TII
->get(TargetOpcode::COPY
), NewVReg
)
1237 .addReg(NewSrc
.Reg
, 0, NewSrc
.SubReg
);
1240 NewCopy
->getOperand(0).setSubReg(Def
.SubReg
);
1241 NewCopy
->getOperand(0).setIsUndef();
1244 LLVM_DEBUG(dbgs() << "-- RewriteSource\n");
1245 LLVM_DEBUG(dbgs() << " Replacing: " << CopyLike
);
1246 LLVM_DEBUG(dbgs() << " With: " << *NewCopy
);
1247 MRI
->replaceRegWith(Def
.Reg
, NewVReg
);
1248 MRI
->clearKillFlags(NewVReg
);
1250 // We extended the lifetime of NewSrc.Reg, clear the kill flags to
1251 // account for that.
1252 MRI
->clearKillFlags(NewSrc
.Reg
);
1257 /// Optimize copy-like instructions to create
1258 /// register coalescer friendly instruction.
1259 /// The optimization tries to kill-off the \p MI by looking
1260 /// through a chain of copies to find a source that has a compatible
1262 /// If such a source is found, it replace \p MI by a generic COPY
1264 /// \pre isUncoalescableCopy(*MI) is true.
1265 /// \return True, when \p MI has been optimized. In that case, \p MI has
1266 /// been removed from its parent.
1267 /// All COPY instructions created, are inserted in \p LocalMIs.
1268 bool PeepholeOptimizer::optimizeUncoalescableCopy(
1269 MachineInstr
&MI
, SmallPtrSetImpl
<MachineInstr
*> &LocalMIs
) {
1270 assert(isUncoalescableCopy(MI
) && "Invalid argument");
1271 UncoalescableRewriter
CpyRewriter(MI
);
1273 // Rewrite each rewritable source by generating new COPYs. This works
1274 // differently from optimizeCoalescableCopy since it first makes sure that all
1275 // definitions can be rewritten.
1276 RewriteMapTy RewriteMap
;
1279 SmallVector
<RegSubRegPair
, 4> RewritePairs
;
1280 while (CpyRewriter
.getNextRewritableSource(Src
, Def
)) {
1281 // If a physical register is here, this is probably for a good reason.
1282 // Do not rewrite that.
1283 if (Register::isPhysicalRegister(Def
.Reg
))
1286 // If we do not know how to rewrite this definition, there is no point
1287 // in trying to kill this instruction.
1288 if (!findNextSource(Def
, RewriteMap
))
1291 RewritePairs
.push_back(Def
);
1294 // The change is possible for all defs, do it.
1295 for (const RegSubRegPair
&Def
: RewritePairs
) {
1296 // Rewrite the "copy" in a way the register coalescer understands.
1297 MachineInstr
&NewCopy
= rewriteSource(MI
, Def
, RewriteMap
);
1298 LocalMIs
.insert(&NewCopy
);
1302 MI
.eraseFromParent();
1303 ++NumUncoalescableCopies
;
1307 /// Check whether MI is a candidate for folding into a later instruction.
1308 /// We only fold loads to virtual registers and the virtual register defined
1309 /// has a single user.
1310 bool PeepholeOptimizer::isLoadFoldable(
1311 MachineInstr
&MI
, SmallSet
<unsigned, 16> &FoldAsLoadDefCandidates
) {
1312 if (!MI
.canFoldAsLoad() || !MI
.mayLoad())
1314 const MCInstrDesc
&MCID
= MI
.getDesc();
1315 if (MCID
.getNumDefs() != 1)
1318 Register Reg
= MI
.getOperand(0).getReg();
1319 // To reduce compilation time, we check MRI->hasOneNonDBGUser when inserting
1320 // loads. It should be checked when processing uses of the load, since
1321 // uses can be removed during peephole.
1322 if (!MI
.getOperand(0).getSubReg() && Register::isVirtualRegister(Reg
) &&
1323 MRI
->hasOneNonDBGUser(Reg
)) {
1324 FoldAsLoadDefCandidates
.insert(Reg
);
1330 bool PeepholeOptimizer::isMoveImmediate(
1331 MachineInstr
&MI
, SmallSet
<unsigned, 4> &ImmDefRegs
,
1332 DenseMap
<unsigned, MachineInstr
*> &ImmDefMIs
) {
1333 const MCInstrDesc
&MCID
= MI
.getDesc();
1334 if (!MI
.isMoveImmediate())
1336 if (MCID
.getNumDefs() != 1)
1338 Register Reg
= MI
.getOperand(0).getReg();
1339 if (Register::isVirtualRegister(Reg
)) {
1340 ImmDefMIs
.insert(std::make_pair(Reg
, &MI
));
1341 ImmDefRegs
.insert(Reg
);
1348 /// Try folding register operands that are defined by move immediate
1349 /// instructions, i.e. a trivial constant folding optimization, if
1350 /// and only if the def and use are in the same BB.
1351 bool PeepholeOptimizer::foldImmediate(MachineInstr
&MI
,
1352 SmallSet
<unsigned, 4> &ImmDefRegs
,
1353 DenseMap
<unsigned, MachineInstr
*> &ImmDefMIs
) {
1354 for (unsigned i
= 0, e
= MI
.getDesc().getNumOperands(); i
!= e
; ++i
) {
1355 MachineOperand
&MO
= MI
.getOperand(i
);
1356 if (!MO
.isReg() || MO
.isDef())
1358 // Ignore dead implicit defs.
1359 if (MO
.isImplicit() && MO
.isDead())
1361 Register Reg
= MO
.getReg();
1362 if (!Register::isVirtualRegister(Reg
))
1364 if (ImmDefRegs
.count(Reg
) == 0)
1366 DenseMap
<unsigned, MachineInstr
*>::iterator II
= ImmDefMIs
.find(Reg
);
1367 assert(II
!= ImmDefMIs
.end() && "couldn't find immediate definition");
1368 if (TII
->FoldImmediate(MI
, *II
->second
, Reg
, MRI
)) {
1376 // FIXME: This is very simple and misses some cases which should be handled when
1377 // motivating examples are found.
1379 // The copy rewriting logic should look at uses as well as defs and be able to
1380 // eliminate copies across blocks.
1382 // Later copies that are subregister extracts will also not be eliminated since
1383 // only the first copy is considered.
1387 // %2 = COPY %0:sub1
1389 // Should replace %2 uses with %1:sub1
1390 bool PeepholeOptimizer::foldRedundantCopy(MachineInstr
&MI
,
1391 SmallSet
<unsigned, 4> &CopySrcRegs
,
1392 DenseMap
<unsigned, MachineInstr
*> &CopyMIs
) {
1393 assert(MI
.isCopy() && "expected a COPY machine instruction");
1395 Register SrcReg
= MI
.getOperand(1).getReg();
1396 if (!Register::isVirtualRegister(SrcReg
))
1399 Register DstReg
= MI
.getOperand(0).getReg();
1400 if (!Register::isVirtualRegister(DstReg
))
1403 if (CopySrcRegs
.insert(SrcReg
).second
) {
1404 // First copy of this reg seen.
1405 CopyMIs
.insert(std::make_pair(SrcReg
, &MI
));
1409 MachineInstr
*PrevCopy
= CopyMIs
.find(SrcReg
)->second
;
1411 unsigned SrcSubReg
= MI
.getOperand(1).getSubReg();
1412 unsigned PrevSrcSubReg
= PrevCopy
->getOperand(1).getSubReg();
1414 // Can't replace different subregister extracts.
1415 if (SrcSubReg
!= PrevSrcSubReg
)
1418 Register PrevDstReg
= PrevCopy
->getOperand(0).getReg();
1420 // Only replace if the copy register class is the same.
1422 // TODO: If we have multiple copies to different register classes, we may want
1423 // to track multiple copies of the same source register.
1424 if (MRI
->getRegClass(DstReg
) != MRI
->getRegClass(PrevDstReg
))
1427 MRI
->replaceRegWith(DstReg
, PrevDstReg
);
1429 // Lifetime of the previous copy has been extended.
1430 MRI
->clearKillFlags(PrevDstReg
);
1434 bool PeepholeOptimizer::isNAPhysCopy(unsigned Reg
) {
1435 return Register::isPhysicalRegister(Reg
) && !MRI
->isAllocatable(Reg
);
1438 bool PeepholeOptimizer::foldRedundantNAPhysCopy(
1439 MachineInstr
&MI
, DenseMap
<unsigned, MachineInstr
*> &NAPhysToVirtMIs
) {
1440 assert(MI
.isCopy() && "expected a COPY machine instruction");
1442 if (DisableNAPhysCopyOpt
)
1445 Register DstReg
= MI
.getOperand(0).getReg();
1446 Register SrcReg
= MI
.getOperand(1).getReg();
1447 if (isNAPhysCopy(SrcReg
) && Register::isVirtualRegister(DstReg
)) {
1448 // %vreg = COPY %physreg
1449 // Avoid using a datastructure which can track multiple live non-allocatable
1450 // phys->virt copies since LLVM doesn't seem to do this.
1451 NAPhysToVirtMIs
.insert({SrcReg
, &MI
});
1455 if (!(Register::isVirtualRegister(SrcReg
) && isNAPhysCopy(DstReg
)))
1458 // %physreg = COPY %vreg
1459 auto PrevCopy
= NAPhysToVirtMIs
.find(DstReg
);
1460 if (PrevCopy
== NAPhysToVirtMIs
.end()) {
1461 // We can't remove the copy: there was an intervening clobber of the
1462 // non-allocatable physical register after the copy to virtual.
1463 LLVM_DEBUG(dbgs() << "NAPhysCopy: intervening clobber forbids erasing "
1468 Register PrevDstReg
= PrevCopy
->second
->getOperand(0).getReg();
1469 if (PrevDstReg
== SrcReg
) {
1470 // Remove the virt->phys copy: we saw the virtual register definition, and
1471 // the non-allocatable physical register's state hasn't changed since then.
1472 LLVM_DEBUG(dbgs() << "NAPhysCopy: erasing " << MI
);
1477 // Potential missed optimization opportunity: we saw a different virtual
1478 // register get a copy of the non-allocatable physical register, and we only
1479 // track one such copy. Avoid getting confused by this new non-allocatable
1480 // physical register definition, and remove it from the tracked copies.
1481 LLVM_DEBUG(dbgs() << "NAPhysCopy: missed opportunity " << MI
);
1482 NAPhysToVirtMIs
.erase(PrevCopy
);
1486 /// \bried Returns true if \p MO is a virtual register operand.
1487 static bool isVirtualRegisterOperand(MachineOperand
&MO
) {
1490 return Register::isVirtualRegister(MO
.getReg());
1493 bool PeepholeOptimizer::findTargetRecurrence(
1494 unsigned Reg
, const SmallSet
<unsigned, 2> &TargetRegs
,
1495 RecurrenceCycle
&RC
) {
1496 // Recurrence found if Reg is in TargetRegs.
1497 if (TargetRegs
.count(Reg
))
1500 // TODO: Curerntly, we only allow the last instruction of the recurrence
1501 // cycle (the instruction that feeds the PHI instruction) to have more than
1502 // one uses to guarantee that commuting operands does not tie registers
1503 // with overlapping live range. Once we have actual live range info of
1504 // each register, this constraint can be relaxed.
1505 if (!MRI
->hasOneNonDBGUse(Reg
))
1508 // Give up if the reccurrence chain length is longer than the limit.
1509 if (RC
.size() >= MaxRecurrenceChain
)
1512 MachineInstr
&MI
= *(MRI
->use_instr_nodbg_begin(Reg
));
1513 unsigned Idx
= MI
.findRegisterUseOperandIdx(Reg
);
1515 // Only interested in recurrences whose instructions have only one def, which
1516 // is a virtual register.
1517 if (MI
.getDesc().getNumDefs() != 1)
1520 MachineOperand
&DefOp
= MI
.getOperand(0);
1521 if (!isVirtualRegisterOperand(DefOp
))
1524 // Check if def operand of MI is tied to any use operand. We are only
1525 // interested in the case that all the instructions in the recurrence chain
1526 // have there def operand tied with one of the use operand.
1527 unsigned TiedUseIdx
;
1528 if (!MI
.isRegTiedToUseOperand(0, &TiedUseIdx
))
1531 if (Idx
== TiedUseIdx
) {
1532 RC
.push_back(RecurrenceInstr(&MI
));
1533 return findTargetRecurrence(DefOp
.getReg(), TargetRegs
, RC
);
1535 // If Idx is not TiedUseIdx, check if Idx is commutable with TiedUseIdx.
1536 unsigned CommIdx
= TargetInstrInfo::CommuteAnyOperandIndex
;
1537 if (TII
->findCommutedOpIndices(MI
, Idx
, CommIdx
) && CommIdx
== TiedUseIdx
) {
1538 RC
.push_back(RecurrenceInstr(&MI
, Idx
, CommIdx
));
1539 return findTargetRecurrence(DefOp
.getReg(), TargetRegs
, RC
);
1546 /// Phi instructions will eventually be lowered to copy instructions.
1547 /// If phi is in a loop header, a recurrence may formulated around the source
1548 /// and destination of the phi. For such case commuting operands of the
1549 /// instructions in the recurrence may enable coalescing of the copy instruction
1550 /// generated from the phi. For example, if there is a recurrence of
1553 /// %1 = phi(%0, %100)
1555 /// %0<def, tied1> = ADD %2<def, tied0>, %1
1557 /// , the fact that %0 and %2 are in the same tied operands set makes
1558 /// the coalescing of copy instruction generated from the phi in
1559 /// LoopHeader(i.e. %1 = COPY %0) impossible, because %1 and
1560 /// %2 have overlapping live range. This introduces additional move
1561 /// instruction to the final assembly. However, if we commute %2 and
1562 /// %1 of ADD instruction, the redundant move instruction can be
1564 bool PeepholeOptimizer::optimizeRecurrence(MachineInstr
&PHI
) {
1565 SmallSet
<unsigned, 2> TargetRegs
;
1566 for (unsigned Idx
= 1; Idx
< PHI
.getNumOperands(); Idx
+= 2) {
1567 MachineOperand
&MO
= PHI
.getOperand(Idx
);
1568 assert(isVirtualRegisterOperand(MO
) && "Invalid PHI instruction");
1569 TargetRegs
.insert(MO
.getReg());
1572 bool Changed
= false;
1574 if (findTargetRecurrence(PHI
.getOperand(0).getReg(), TargetRegs
, RC
)) {
1575 // Commutes operands of instructions in RC if necessary so that the copy to
1576 // be generated from PHI can be coalesced.
1577 LLVM_DEBUG(dbgs() << "Optimize recurrence chain from " << PHI
);
1578 for (auto &RI
: RC
) {
1579 LLVM_DEBUG(dbgs() << "\tInst: " << *(RI
.getMI()));
1580 auto CP
= RI
.getCommutePair();
1583 TII
->commuteInstruction(*(RI
.getMI()), false, (*CP
).first
,
1585 LLVM_DEBUG(dbgs() << "\t\tCommuted: " << *(RI
.getMI()));
1593 bool PeepholeOptimizer::runOnMachineFunction(MachineFunction
&MF
) {
1594 if (skipFunction(MF
.getFunction()))
1597 LLVM_DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n");
1598 LLVM_DEBUG(dbgs() << "********** Function: " << MF
.getName() << '\n');
1600 if (DisablePeephole
)
1603 TII
= MF
.getSubtarget().getInstrInfo();
1604 TRI
= MF
.getSubtarget().getRegisterInfo();
1605 MRI
= &MF
.getRegInfo();
1606 DT
= Aggressive
? &getAnalysis
<MachineDominatorTree
>() : nullptr;
1607 MLI
= &getAnalysis
<MachineLoopInfo
>();
1609 bool Changed
= false;
1611 for (MachineBasicBlock
&MBB
: MF
) {
1612 bool SeenMoveImm
= false;
1614 // During this forward scan, at some point it needs to answer the question
1615 // "given a pointer to an MI in the current BB, is it located before or
1616 // after the current instruction".
1617 // To perform this, the following set keeps track of the MIs already seen
1618 // during the scan, if a MI is not in the set, it is assumed to be located
1619 // after. Newly created MIs have to be inserted in the set as well.
1620 SmallPtrSet
<MachineInstr
*, 16> LocalMIs
;
1621 SmallSet
<unsigned, 4> ImmDefRegs
;
1622 DenseMap
<unsigned, MachineInstr
*> ImmDefMIs
;
1623 SmallSet
<unsigned, 16> FoldAsLoadDefCandidates
;
1625 // Track when a non-allocatable physical register is copied to a virtual
1626 // register so that useless moves can be removed.
1628 // %physreg is the map index; MI is the last valid `%vreg = COPY %physreg`
1629 // without any intervening re-definition of %physreg.
1630 DenseMap
<unsigned, MachineInstr
*> NAPhysToVirtMIs
;
1632 // Set of virtual registers that are copied from.
1633 SmallSet
<unsigned, 4> CopySrcRegs
;
1634 DenseMap
<unsigned, MachineInstr
*> CopySrcMIs
;
1636 bool IsLoopHeader
= MLI
->isLoopHeader(&MBB
);
1638 for (MachineBasicBlock::iterator MII
= MBB
.begin(), MIE
= MBB
.end();
1640 MachineInstr
*MI
= &*MII
;
1641 // We may be erasing MI below, increment MII now.
1643 LocalMIs
.insert(MI
);
1645 // Skip debug instructions. They should not affect this peephole optimization.
1646 if (MI
->isDebugInstr())
1649 if (MI
->isPosition())
1652 if (IsLoopHeader
&& MI
->isPHI()) {
1653 if (optimizeRecurrence(*MI
)) {
1659 if (!MI
->isCopy()) {
1660 for (const MachineOperand
&MO
: MI
->operands()) {
1661 // Visit all operands: definitions can be implicit or explicit.
1663 Register Reg
= MO
.getReg();
1664 if (MO
.isDef() && isNAPhysCopy(Reg
)) {
1665 const auto &Def
= NAPhysToVirtMIs
.find(Reg
);
1666 if (Def
!= NAPhysToVirtMIs
.end()) {
1667 // A new definition of the non-allocatable physical register
1668 // invalidates previous copies.
1670 << "NAPhysCopy: invalidating because of " << *MI
);
1671 NAPhysToVirtMIs
.erase(Def
);
1674 } else if (MO
.isRegMask()) {
1675 const uint32_t *RegMask
= MO
.getRegMask();
1676 for (auto &RegMI
: NAPhysToVirtMIs
) {
1677 unsigned Def
= RegMI
.first
;
1678 if (MachineOperand::clobbersPhysReg(RegMask
, Def
)) {
1680 << "NAPhysCopy: invalidating because of " << *MI
);
1681 NAPhysToVirtMIs
.erase(Def
);
1688 if (MI
->isImplicitDef() || MI
->isKill())
1691 if (MI
->isInlineAsm() || MI
->hasUnmodeledSideEffects()) {
1692 // Blow away all non-allocatable physical registers knowledge since we
1693 // don't know what's correct anymore.
1695 // FIXME: handle explicit asm clobbers.
1696 LLVM_DEBUG(dbgs() << "NAPhysCopy: blowing away all info due to "
1698 NAPhysToVirtMIs
.clear();
1701 if ((isUncoalescableCopy(*MI
) &&
1702 optimizeUncoalescableCopy(*MI
, LocalMIs
)) ||
1703 (MI
->isCompare() && optimizeCmpInstr(*MI
)) ||
1704 (MI
->isSelect() && optimizeSelect(*MI
, LocalMIs
))) {
1711 if (MI
->isConditionalBranch() && optimizeCondBranch(*MI
)) {
1716 if (isCoalescableCopy(*MI
) && optimizeCoalescableCopy(*MI
)) {
1717 // MI is just rewritten.
1723 (foldRedundantCopy(*MI
, CopySrcRegs
, CopySrcMIs
) ||
1724 foldRedundantNAPhysCopy(*MI
, NAPhysToVirtMIs
))) {
1726 MI
->eraseFromParent();
1731 if (isMoveImmediate(*MI
, ImmDefRegs
, ImmDefMIs
)) {
1734 Changed
|= optimizeExtInstr(*MI
, MBB
, LocalMIs
);
1735 // optimizeExtInstr might have created new instructions after MI
1736 // and before the already incremented MII. Adjust MII so that the
1737 // next iteration sees the new instructions.
1741 Changed
|= foldImmediate(*MI
, ImmDefRegs
, ImmDefMIs
);
1744 // Check whether MI is a load candidate for folding into a later
1745 // instruction. If MI is not a candidate, check whether we can fold an
1746 // earlier load into MI.
1747 if (!isLoadFoldable(*MI
, FoldAsLoadDefCandidates
) &&
1748 !FoldAsLoadDefCandidates
.empty()) {
1750 // We visit each operand even after successfully folding a previous
1751 // one. This allows us to fold multiple loads into a single
1752 // instruction. We do assume that optimizeLoadInstr doesn't insert
1753 // foldable uses earlier in the argument list. Since we don't restart
1754 // iteration, we'd miss such cases.
1755 const MCInstrDesc
&MIDesc
= MI
->getDesc();
1756 for (unsigned i
= MIDesc
.getNumDefs(); i
!= MI
->getNumOperands();
1758 const MachineOperand
&MOp
= MI
->getOperand(i
);
1761 unsigned FoldAsLoadDefReg
= MOp
.getReg();
1762 if (FoldAsLoadDefCandidates
.count(FoldAsLoadDefReg
)) {
1763 // We need to fold load after optimizeCmpInstr, since
1764 // optimizeCmpInstr can enable folding by converting SUB to CMP.
1765 // Save FoldAsLoadDefReg because optimizeLoadInstr() resets it and
1766 // we need it for markUsesInDebugValueAsUndef().
1767 unsigned FoldedReg
= FoldAsLoadDefReg
;
1768 MachineInstr
*DefMI
= nullptr;
1769 if (MachineInstr
*FoldMI
=
1770 TII
->optimizeLoadInstr(*MI
, MRI
, FoldAsLoadDefReg
, DefMI
)) {
1771 // Update LocalMIs since we replaced MI with FoldMI and deleted
1773 LLVM_DEBUG(dbgs() << "Replacing: " << *MI
);
1774 LLVM_DEBUG(dbgs() << " With: " << *FoldMI
);
1776 LocalMIs
.erase(DefMI
);
1777 LocalMIs
.insert(FoldMI
);
1779 MI
->getMF()->updateCallSiteInfo(MI
, FoldMI
);
1780 MI
->eraseFromParent();
1781 DefMI
->eraseFromParent();
1782 MRI
->markUsesInDebugValueAsUndef(FoldedReg
);
1783 FoldAsLoadDefCandidates
.erase(FoldedReg
);
1786 // MI is replaced with FoldMI so we can continue trying to fold
1794 // If we run into an instruction we can't fold across, discard
1795 // the load candidates. Note: We might be able to fold *into* this
1796 // instruction, so this needs to be after the folding logic.
1797 if (MI
->isLoadFoldBarrier()) {
1798 LLVM_DEBUG(dbgs() << "Encountered load fold barrier on " << *MI
);
1799 FoldAsLoadDefCandidates
.clear();
1807 ValueTrackerResult
ValueTracker::getNextSourceFromCopy() {
1808 assert(Def
->isCopy() && "Invalid definition");
1809 // Copy instruction are supposed to be: Def = Src.
1810 // If someone breaks this assumption, bad things will happen everywhere.
1811 // There may be implicit uses preventing the copy to be moved across
1812 // some target specific register definitions
1813 assert(Def
->getNumOperands() - Def
->getNumImplicitOperands() == 2 &&
1814 "Invalid number of operands");
1815 assert(!Def
->hasImplicitDef() && "Only implicit uses are allowed");
1817 if (Def
->getOperand(DefIdx
).getSubReg() != DefSubReg
)
1818 // If we look for a different subreg, it means we want a subreg of src.
1819 // Bails as we do not support composing subregs yet.
1820 return ValueTrackerResult();
1821 // Otherwise, we want the whole source.
1822 const MachineOperand
&Src
= Def
->getOperand(1);
1824 return ValueTrackerResult();
1825 return ValueTrackerResult(Src
.getReg(), Src
.getSubReg());
1828 ValueTrackerResult
ValueTracker::getNextSourceFromBitcast() {
1829 assert(Def
->isBitcast() && "Invalid definition");
1831 // Bail if there are effects that a plain copy will not expose.
1832 if (Def
->mayRaiseFPException() || Def
->hasUnmodeledSideEffects())
1833 return ValueTrackerResult();
1835 // Bitcasts with more than one def are not supported.
1836 if (Def
->getDesc().getNumDefs() != 1)
1837 return ValueTrackerResult();
1838 const MachineOperand DefOp
= Def
->getOperand(DefIdx
);
1839 if (DefOp
.getSubReg() != DefSubReg
)
1840 // If we look for a different subreg, it means we want a subreg of the src.
1841 // Bails as we do not support composing subregs yet.
1842 return ValueTrackerResult();
1844 unsigned SrcIdx
= Def
->getNumOperands();
1845 for (unsigned OpIdx
= DefIdx
+ 1, EndOpIdx
= SrcIdx
; OpIdx
!= EndOpIdx
;
1847 const MachineOperand
&MO
= Def
->getOperand(OpIdx
);
1848 if (!MO
.isReg() || !MO
.getReg())
1850 // Ignore dead implicit defs.
1851 if (MO
.isImplicit() && MO
.isDead())
1853 assert(!MO
.isDef() && "We should have skipped all the definitions by now");
1854 if (SrcIdx
!= EndOpIdx
)
1855 // Multiple sources?
1856 return ValueTrackerResult();
1860 // In some rare case, Def has no input, SrcIdx is out of bound,
1861 // getOperand(SrcIdx) will fail below.
1862 if (SrcIdx
>= Def
->getNumOperands())
1863 return ValueTrackerResult();
1865 // Stop when any user of the bitcast is a SUBREG_TO_REG, replacing with a COPY
1866 // will break the assumed guarantees for the upper bits.
1867 for (const MachineInstr
&UseMI
: MRI
.use_nodbg_instructions(DefOp
.getReg())) {
1868 if (UseMI
.isSubregToReg())
1869 return ValueTrackerResult();
1872 const MachineOperand
&Src
= Def
->getOperand(SrcIdx
);
1874 return ValueTrackerResult();
1875 return ValueTrackerResult(Src
.getReg(), Src
.getSubReg());
1878 ValueTrackerResult
ValueTracker::getNextSourceFromRegSequence() {
1879 assert((Def
->isRegSequence() || Def
->isRegSequenceLike()) &&
1880 "Invalid definition");
1882 if (Def
->getOperand(DefIdx
).getSubReg())
1883 // If we are composing subregs, bail out.
1884 // The case we are checking is Def.<subreg> = REG_SEQUENCE.
1885 // This should almost never happen as the SSA property is tracked at
1886 // the register level (as opposed to the subreg level).
1890 // is a valid SSA representation for Def.sub0 and Def.sub1, but not for
1891 // Def. Thus, it must not be generated.
1892 // However, some code could theoretically generates a single
1893 // Def.sub0 (i.e, not defining the other subregs) and we would
1895 // If we can ascertain (or force) that this never happens, we could
1896 // turn that into an assertion.
1897 return ValueTrackerResult();
1900 // We could handle the REG_SEQUENCE here, but we do not want to
1901 // duplicate the code from the generic TII.
1902 return ValueTrackerResult();
1904 SmallVector
<RegSubRegPairAndIdx
, 8> RegSeqInputRegs
;
1905 if (!TII
->getRegSequenceInputs(*Def
, DefIdx
, RegSeqInputRegs
))
1906 return ValueTrackerResult();
1908 // We are looking at:
1909 // Def = REG_SEQUENCE v0, sub0, v1, sub1, ...
1910 // Check if one of the operand defines the subreg we are interested in.
1911 for (const RegSubRegPairAndIdx
&RegSeqInput
: RegSeqInputRegs
) {
1912 if (RegSeqInput
.SubIdx
== DefSubReg
)
1913 return ValueTrackerResult(RegSeqInput
.Reg
, RegSeqInput
.SubReg
);
1916 // If the subreg we are tracking is super-defined by another subreg,
1917 // we could follow this value. However, this would require to compose
1918 // the subreg and we do not do that for now.
1919 return ValueTrackerResult();
1922 ValueTrackerResult
ValueTracker::getNextSourceFromInsertSubreg() {
1923 assert((Def
->isInsertSubreg() || Def
->isInsertSubregLike()) &&
1924 "Invalid definition");
1926 if (Def
->getOperand(DefIdx
).getSubReg())
1927 // If we are composing subreg, bail out.
1928 // Same remark as getNextSourceFromRegSequence.
1929 // I.e., this may be turned into an assert.
1930 return ValueTrackerResult();
1933 // We could handle the REG_SEQUENCE here, but we do not want to
1934 // duplicate the code from the generic TII.
1935 return ValueTrackerResult();
1937 RegSubRegPair BaseReg
;
1938 RegSubRegPairAndIdx InsertedReg
;
1939 if (!TII
->getInsertSubregInputs(*Def
, DefIdx
, BaseReg
, InsertedReg
))
1940 return ValueTrackerResult();
1942 // We are looking at:
1943 // Def = INSERT_SUBREG v0, v1, sub1
1944 // There are two cases:
1945 // 1. DefSubReg == sub1, get v1.
1946 // 2. DefSubReg != sub1, the value may be available through v0.
1948 // #1 Check if the inserted register matches the required sub index.
1949 if (InsertedReg
.SubIdx
== DefSubReg
) {
1950 return ValueTrackerResult(InsertedReg
.Reg
, InsertedReg
.SubReg
);
1952 // #2 Otherwise, if the sub register we are looking for is not partial
1953 // defined by the inserted element, we can look through the main
1955 const MachineOperand
&MODef
= Def
->getOperand(DefIdx
);
1956 // If the result register (Def) and the base register (v0) do not
1957 // have the same register class or if we have to compose
1958 // subregisters, bail out.
1959 if (MRI
.getRegClass(MODef
.getReg()) != MRI
.getRegClass(BaseReg
.Reg
) ||
1961 return ValueTrackerResult();
1963 // Get the TRI and check if the inserted sub-register overlaps with the
1964 // sub-register we are tracking.
1965 const TargetRegisterInfo
*TRI
= MRI
.getTargetRegisterInfo();
1967 !(TRI
->getSubRegIndexLaneMask(DefSubReg
) &
1968 TRI
->getSubRegIndexLaneMask(InsertedReg
.SubIdx
)).none())
1969 return ValueTrackerResult();
1970 // At this point, the value is available in v0 via the same subreg
1972 return ValueTrackerResult(BaseReg
.Reg
, DefSubReg
);
1975 ValueTrackerResult
ValueTracker::getNextSourceFromExtractSubreg() {
1976 assert((Def
->isExtractSubreg() ||
1977 Def
->isExtractSubregLike()) && "Invalid definition");
1978 // We are looking at:
1979 // Def = EXTRACT_SUBREG v0, sub0
1981 // Bail if we have to compose sub registers.
1982 // Indeed, if DefSubReg != 0, we would have to compose it with sub0.
1984 return ValueTrackerResult();
1987 // We could handle the EXTRACT_SUBREG here, but we do not want to
1988 // duplicate the code from the generic TII.
1989 return ValueTrackerResult();
1991 RegSubRegPairAndIdx ExtractSubregInputReg
;
1992 if (!TII
->getExtractSubregInputs(*Def
, DefIdx
, ExtractSubregInputReg
))
1993 return ValueTrackerResult();
1995 // Bail if we have to compose sub registers.
1996 // Likewise, if v0.subreg != 0, we would have to compose v0.subreg with sub0.
1997 if (ExtractSubregInputReg
.SubReg
)
1998 return ValueTrackerResult();
1999 // Otherwise, the value is available in the v0.sub0.
2000 return ValueTrackerResult(ExtractSubregInputReg
.Reg
,
2001 ExtractSubregInputReg
.SubIdx
);
2004 ValueTrackerResult
ValueTracker::getNextSourceFromSubregToReg() {
2005 assert(Def
->isSubregToReg() && "Invalid definition");
2006 // We are looking at:
2007 // Def = SUBREG_TO_REG Imm, v0, sub0
2009 // Bail if we have to compose sub registers.
2010 // If DefSubReg != sub0, we would have to check that all the bits
2011 // we track are included in sub0 and if yes, we would have to
2012 // determine the right subreg in v0.
2013 if (DefSubReg
!= Def
->getOperand(3).getImm())
2014 return ValueTrackerResult();
2015 // Bail if we have to compose sub registers.
2016 // Likewise, if v0.subreg != 0, we would have to compose it with sub0.
2017 if (Def
->getOperand(2).getSubReg())
2018 return ValueTrackerResult();
2020 return ValueTrackerResult(Def
->getOperand(2).getReg(),
2021 Def
->getOperand(3).getImm());
2024 /// Explore each PHI incoming operand and return its sources.
2025 ValueTrackerResult
ValueTracker::getNextSourceFromPHI() {
2026 assert(Def
->isPHI() && "Invalid definition");
2027 ValueTrackerResult Res
;
2029 // If we look for a different subreg, bail as we do not support composing
2031 if (Def
->getOperand(0).getSubReg() != DefSubReg
)
2032 return ValueTrackerResult();
2034 // Return all register sources for PHI instructions.
2035 for (unsigned i
= 1, e
= Def
->getNumOperands(); i
< e
; i
+= 2) {
2036 const MachineOperand
&MO
= Def
->getOperand(i
);
2037 assert(MO
.isReg() && "Invalid PHI instruction");
2038 // We have no code to deal with undef operands. They shouldn't happen in
2039 // normal programs anyway.
2041 return ValueTrackerResult();
2042 Res
.addSource(MO
.getReg(), MO
.getSubReg());
2048 ValueTrackerResult
ValueTracker::getNextSourceImpl() {
2049 assert(Def
&& "This method needs a valid definition");
2051 assert(((Def
->getOperand(DefIdx
).isDef() &&
2052 (DefIdx
< Def
->getDesc().getNumDefs() ||
2053 Def
->getDesc().isVariadic())) ||
2054 Def
->getOperand(DefIdx
).isImplicit()) &&
2057 return getNextSourceFromCopy();
2058 if (Def
->isBitcast())
2059 return getNextSourceFromBitcast();
2060 // All the remaining cases involve "complex" instructions.
2061 // Bail if we did not ask for the advanced tracking.
2062 if (DisableAdvCopyOpt
)
2063 return ValueTrackerResult();
2064 if (Def
->isRegSequence() || Def
->isRegSequenceLike())
2065 return getNextSourceFromRegSequence();
2066 if (Def
->isInsertSubreg() || Def
->isInsertSubregLike())
2067 return getNextSourceFromInsertSubreg();
2068 if (Def
->isExtractSubreg() || Def
->isExtractSubregLike())
2069 return getNextSourceFromExtractSubreg();
2070 if (Def
->isSubregToReg())
2071 return getNextSourceFromSubregToReg();
2073 return getNextSourceFromPHI();
2074 return ValueTrackerResult();
2077 ValueTrackerResult
ValueTracker::getNextSource() {
2078 // If we reach a point where we cannot move up in the use-def chain,
2079 // there is nothing we can get.
2081 return ValueTrackerResult();
2083 ValueTrackerResult Res
= getNextSourceImpl();
2084 if (Res
.isValid()) {
2085 // Update definition, definition index, and subregister for the
2086 // next call of getNextSource.
2087 // Update the current register.
2088 bool OneRegSrc
= Res
.getNumSources() == 1;
2090 Reg
= Res
.getSrcReg(0);
2091 // Update the result before moving up in the use-def chain
2092 // with the instruction containing the last found sources.
2095 // If we can still move up in the use-def chain, move to the next
2097 if (!Register::isPhysicalRegister(Reg
) && OneRegSrc
) {
2098 MachineRegisterInfo::def_iterator DI
= MRI
.def_begin(Reg
);
2099 if (DI
!= MRI
.def_end()) {
2100 Def
= DI
->getParent();
2101 DefIdx
= DI
.getOperandNo();
2102 DefSubReg
= Res
.getSrcSubReg(0);
2109 // If we end up here, this means we will not be able to find another source
2110 // for the next iteration. Make sure any new call to getNextSource bails out
2111 // early by cutting the use-def chain.