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