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