LLVM 20.0.0git
TwoAddressInstructionPass.cpp
Go to the documentation of this file.
1//===- TwoAddressInstructionPass.cpp - Two-Address instruction pass -------===//
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// This file implements the TwoAddress instruction pass which is used
10// by most register allocators. Two-Address instructions are rewritten
11// from:
12//
13// A = B op C
14//
15// to:
16//
17// A = B
18// A op= C
19//
20// Note that if a register allocator chooses to use this pass, that it
21// has to be capable of handling the non-SSA nature of these rewritten
22// virtual registers.
23//
24// It is also worth noting that the duplicate operand of the two
25// address instruction is removed.
26//
27//===----------------------------------------------------------------------===//
28
30#include "llvm/ADT/DenseMap.h"
33#include "llvm/ADT/Statistic.h"
48#include "llvm/CodeGen/Passes.h"
54#include "llvm/MC/MCInstrDesc.h"
55#include "llvm/Pass.h"
58#include "llvm/Support/Debug.h"
62#include <cassert>
63#include <iterator>
64#include <utility>
65
66using namespace llvm;
67
68#define DEBUG_TYPE "twoaddressinstruction"
69
70STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
71STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
72STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted");
73STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
74STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up");
75STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down");
76
77// Temporary flag to disable rescheduling.
78static cl::opt<bool>
79EnableRescheduling("twoaddr-reschedule",
80 cl::desc("Coalesce copies by rescheduling (default=true)"),
81 cl::init(true), cl::Hidden);
82
83// Limit the number of dataflow edges to traverse when evaluating the benefit
84// of commuting operands.
86 "dataflow-edge-limit", cl::Hidden, cl::init(3),
87 cl::desc("Maximum number of dataflow edges to traverse when evaluating "
88 "the benefit of commuting operands"));
89
90namespace {
91
92class TwoAddressInstructionImpl {
93 MachineFunction *MF = nullptr;
94 const TargetInstrInfo *TII = nullptr;
95 const TargetRegisterInfo *TRI = nullptr;
96 const InstrItineraryData *InstrItins = nullptr;
97 MachineRegisterInfo *MRI = nullptr;
98 LiveVariables *LV = nullptr;
99 LiveIntervals *LIS = nullptr;
100 AliasAnalysis *AA = nullptr;
101 CodeGenOptLevel OptLevel = CodeGenOptLevel::None;
102
103 // The current basic block being processed.
104 MachineBasicBlock *MBB = nullptr;
105
106 // Keep track the distance of a MI from the start of the current basic block.
108
109 // Set of already processed instructions in the current block.
111
112 // A map from virtual registers to physical registers which are likely targets
113 // to be coalesced to due to copies from physical registers to virtual
114 // registers. e.g. v1024 = move r0.
116
117 // A map from virtual registers to physical registers which are likely targets
118 // to be coalesced to due to copies to physical registers from virtual
119 // registers. e.g. r1 = move v1024.
121
122 MachineInstr *getSingleDef(Register Reg, MachineBasicBlock *BB) const;
123
124 bool isRevCopyChain(Register FromReg, Register ToReg, int Maxlen);
125
126 bool noUseAfterLastDef(Register Reg, unsigned Dist, unsigned &LastDef);
127
128 bool isCopyToReg(MachineInstr &MI, Register &SrcReg, Register &DstReg,
129 bool &IsSrcPhys, bool &IsDstPhys) const;
130
131 bool isPlainlyKilled(const MachineInstr *MI, LiveRange &LR) const;
132 bool isPlainlyKilled(const MachineInstr *MI, Register Reg) const;
133 bool isPlainlyKilled(const MachineOperand &MO) const;
134
135 bool isKilled(MachineInstr &MI, Register Reg, bool allowFalsePositives) const;
136
137 MachineInstr *findOnlyInterestingUse(Register Reg, MachineBasicBlock *MBB,
138 bool &IsCopy, Register &DstReg,
139 bool &IsDstPhys) const;
140
141 bool regsAreCompatible(Register RegA, Register RegB) const;
142
143 void removeMapRegEntry(const MachineOperand &MO,
144 DenseMap<Register, Register> &RegMap) const;
145
146 void removeClobberedSrcRegMap(MachineInstr *MI);
147
148 bool regOverlapsSet(const SmallVectorImpl<Register> &Set, Register Reg) const;
149
150 bool isProfitableToCommute(Register RegA, Register RegB, Register RegC,
151 MachineInstr *MI, unsigned Dist);
152
153 bool commuteInstruction(MachineInstr *MI, unsigned DstIdx,
154 unsigned RegBIdx, unsigned RegCIdx, unsigned Dist);
155
156 bool isProfitableToConv3Addr(Register RegA, Register RegB);
157
158 bool convertInstTo3Addr(MachineBasicBlock::iterator &mi,
160 Register RegB, unsigned &Dist);
161
162 bool isDefTooClose(Register Reg, unsigned Dist, MachineInstr *MI);
163
164 bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi,
166 bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi,
168
169 bool tryInstructionTransform(MachineBasicBlock::iterator &mi,
171 unsigned SrcIdx, unsigned DstIdx,
172 unsigned &Dist, bool shouldOnlyCommute);
173
174 bool tryInstructionCommute(MachineInstr *MI,
175 unsigned DstOpIdx,
176 unsigned BaseOpIdx,
177 bool BaseOpKilled,
178 unsigned Dist);
179 void scanUses(Register DstReg);
180
181 void processCopy(MachineInstr *MI);
182
183 using TiedPairList = SmallVector<std::pair<unsigned, unsigned>, 4>;
184 using TiedOperandMap = SmallDenseMap<unsigned, TiedPairList>;
185
186 bool collectTiedOperands(MachineInstr *MI, TiedOperandMap&);
187 void processTiedPairs(MachineInstr *MI, TiedPairList&, unsigned &Dist);
188 void eliminateRegSequence(MachineBasicBlock::iterator&);
189 bool processStatepoint(MachineInstr *MI, TiedOperandMap &TiedOperands);
190
191public:
192 TwoAddressInstructionImpl(MachineFunction &MF, MachineFunctionPass *P);
193 TwoAddressInstructionImpl(MachineFunction &MF,
195 void setOptLevel(CodeGenOptLevel Level) { OptLevel = Level; }
196 bool run();
197};
198
199class TwoAddressInstructionLegacyPass : public MachineFunctionPass {
200public:
201 static char ID; // Pass identification, replacement for typeid
202
203 TwoAddressInstructionLegacyPass() : MachineFunctionPass(ID) {
206 }
207
208 /// Pass entry point.
209 bool runOnMachineFunction(MachineFunction &MF) override {
210 TwoAddressInstructionImpl Impl(MF, this);
211 // Disable optimizations if requested. We cannot skip the whole pass as some
212 // fixups are necessary for correctness.
213 if (skipFunction(MF.getFunction()))
214 Impl.setOptLevel(CodeGenOptLevel::None);
215 return Impl.run();
216 }
217
218 void getAnalysisUsage(AnalysisUsage &AU) const override {
219 AU.setPreservesCFG();
228 }
229};
230
231} // end anonymous namespace
232
236 // Disable optimizations if requested. We cannot skip the whole pass as some
237 // fixups are necessary for correctness.
238 TwoAddressInstructionImpl Impl(MF, MFAM);
239 if (MF.getFunction().hasOptNone())
240 Impl.setOptLevel(CodeGenOptLevel::None);
241
242 MFPropsModifier _(*this, MF);
243 bool Changed = Impl.run();
244 if (!Changed)
245 return PreservedAnalyses::all();
247 PA.preserve<LiveIntervalsAnalysis>();
248 PA.preserve<LiveVariablesAnalysis>();
249 PA.preserve<MachineDominatorTreeAnalysis>();
250 PA.preserve<MachineLoopAnalysis>();
251 PA.preserve<SlotIndexesAnalysis>();
252 PA.preserveSet<CFGAnalyses>();
253 return PA;
254}
255
256char TwoAddressInstructionLegacyPass::ID = 0;
257
258char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionLegacyPass::ID;
259
260INITIALIZE_PASS_BEGIN(TwoAddressInstructionLegacyPass, DEBUG_TYPE,
261 "Two-Address instruction pass", false, false)
263INITIALIZE_PASS_END(TwoAddressInstructionLegacyPass, DEBUG_TYPE,
264 "Two-Address instruction pass", false, false)
265
266TwoAddressInstructionImpl::TwoAddressInstructionImpl(
268 : MF(&Func), TII(Func.getSubtarget().getInstrInfo()),
269 TRI(Func.getSubtarget().getRegisterInfo()),
270 InstrItins(Func.getSubtarget().getInstrItineraryData()),
271 MRI(&Func.getRegInfo()),
272 LV(MFAM.getCachedResult<LiveVariablesAnalysis>(Func)),
273 LIS(MFAM.getCachedResult<LiveIntervalsAnalysis>(Func)),
274 OptLevel(Func.getTarget().getOptLevel()) {
276 .getManager();
277 AA = FAM.getCachedResult<AAManager>(Func.getFunction());
278}
279
280TwoAddressInstructionImpl::TwoAddressInstructionImpl(MachineFunction &Func,
282 : MF(&Func), TII(Func.getSubtarget().getInstrInfo()),
283 TRI(Func.getSubtarget().getRegisterInfo()),
284 InstrItins(Func.getSubtarget().getInstrItineraryData()),
285 MRI(&Func.getRegInfo()), OptLevel(Func.getTarget().getOptLevel()) {
286 auto *LVWrapper = P->getAnalysisIfAvailable<LiveVariablesWrapperPass>();
287 LV = LVWrapper ? &LVWrapper->getLV() : nullptr;
288 auto *LISWrapper = P->getAnalysisIfAvailable<LiveIntervalsWrapperPass>();
289 LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;
290 if (auto *AAPass = P->getAnalysisIfAvailable<AAResultsWrapperPass>())
291 AA = &AAPass->getAAResults();
292 else
293 AA = nullptr;
294}
295
296/// Return the MachineInstr* if it is the single def of the Reg in current BB.
298TwoAddressInstructionImpl::getSingleDef(Register Reg,
299 MachineBasicBlock *BB) const {
300 MachineInstr *Ret = nullptr;
301 for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
302 if (DefMI.getParent() != BB || DefMI.isDebugValue())
303 continue;
304 if (!Ret)
305 Ret = &DefMI;
306 else if (Ret != &DefMI)
307 return nullptr;
308 }
309 return Ret;
310}
311
312/// Check if there is a reversed copy chain from FromReg to ToReg:
313/// %Tmp1 = copy %Tmp2;
314/// %FromReg = copy %Tmp1;
315/// %ToReg = add %FromReg ...
316/// %Tmp2 = copy %ToReg;
317/// MaxLen specifies the maximum length of the copy chain the func
318/// can walk through.
319bool TwoAddressInstructionImpl::isRevCopyChain(Register FromReg, Register ToReg,
320 int Maxlen) {
321 Register TmpReg = FromReg;
322 for (int i = 0; i < Maxlen; i++) {
323 MachineInstr *Def = getSingleDef(TmpReg, MBB);
324 if (!Def || !Def->isCopy())
325 return false;
326
327 TmpReg = Def->getOperand(1).getReg();
328
329 if (TmpReg == ToReg)
330 return true;
331 }
332 return false;
333}
334
335/// Return true if there are no intervening uses between the last instruction
336/// in the MBB that defines the specified register and the two-address
337/// instruction which is being processed. It also returns the last def location
338/// by reference.
339bool TwoAddressInstructionImpl::noUseAfterLastDef(Register Reg, unsigned Dist,
340 unsigned &LastDef) {
341 LastDef = 0;
342 unsigned LastUse = Dist;
343 for (MachineOperand &MO : MRI->reg_operands(Reg)) {
344 MachineInstr *MI = MO.getParent();
345 if (MI->getParent() != MBB || MI->isDebugValue())
346 continue;
348 if (DI == DistanceMap.end())
349 continue;
350 if (MO.isUse() && DI->second < LastUse)
351 LastUse = DI->second;
352 if (MO.isDef() && DI->second > LastDef)
353 LastDef = DI->second;
354 }
355
356 return !(LastUse > LastDef && LastUse < Dist);
357}
358
359/// Return true if the specified MI is a copy instruction or an extract_subreg
360/// instruction. It also returns the source and destination registers and
361/// whether they are physical registers by reference.
362bool TwoAddressInstructionImpl::isCopyToReg(MachineInstr &MI, Register &SrcReg,
363 Register &DstReg, bool &IsSrcPhys,
364 bool &IsDstPhys) const {
365 SrcReg = 0;
366 DstReg = 0;
367 if (MI.isCopy()) {
368 DstReg = MI.getOperand(0).getReg();
369 SrcReg = MI.getOperand(1).getReg();
370 } else if (MI.isInsertSubreg() || MI.isSubregToReg()) {
371 DstReg = MI.getOperand(0).getReg();
372 SrcReg = MI.getOperand(2).getReg();
373 } else {
374 return false;
375 }
376
377 IsSrcPhys = SrcReg.isPhysical();
378 IsDstPhys = DstReg.isPhysical();
379 return true;
380}
381
382bool TwoAddressInstructionImpl::isPlainlyKilled(const MachineInstr *MI,
383 LiveRange &LR) const {
384 // This is to match the kill flag version where undefs don't have kill flags.
385 if (!LR.hasAtLeastOneValue())
386 return false;
387
388 SlotIndex useIdx = LIS->getInstructionIndex(*MI);
390 assert(I != LR.end() && "Reg must be live-in to use.");
391 return !I->end.isBlock() && SlotIndex::isSameInstr(I->end, useIdx);
392}
393
394/// Test if the given register value, which is used by the
395/// given instruction, is killed by the given instruction.
396bool TwoAddressInstructionImpl::isPlainlyKilled(const MachineInstr *MI,
397 Register Reg) const {
398 // FIXME: Sometimes tryInstructionTransform() will add instructions and
399 // test whether they can be folded before keeping them. In this case it
400 // sets a kill before recursively calling tryInstructionTransform() again.
401 // If there is no interval available, we assume that this instruction is
402 // one of those. A kill flag is manually inserted on the operand so the
403 // check below will handle it.
404 if (LIS && !LIS->isNotInMIMap(*MI)) {
405 if (Reg.isVirtual())
406 return isPlainlyKilled(MI, LIS->getInterval(Reg));
407 // Reserved registers are considered always live.
408 if (MRI->isReserved(Reg))
409 return false;
410 return all_of(TRI->regunits(Reg), [&](MCRegUnit U) {
411 return isPlainlyKilled(MI, LIS->getRegUnit(U));
412 });
413 }
414
415 return MI->killsRegister(Reg, /*TRI=*/nullptr);
416}
417
418/// Test if the register used by the given operand is killed by the operand's
419/// instruction.
420bool TwoAddressInstructionImpl::isPlainlyKilled(
421 const MachineOperand &MO) const {
422 return MO.isKill() || isPlainlyKilled(MO.getParent(), MO.getReg());
423}
424
425/// Test if the given register value, which is used by the given
426/// instruction, is killed by the given instruction. This looks through
427/// coalescable copies to see if the original value is potentially not killed.
428///
429/// For example, in this code:
430///
431/// %reg1034 = copy %reg1024
432/// %reg1035 = copy killed %reg1025
433/// %reg1036 = add killed %reg1034, killed %reg1035
434///
435/// %reg1034 is not considered to be killed, since it is copied from a
436/// register which is not killed. Treating it as not killed lets the
437/// normal heuristics commute the (two-address) add, which lets
438/// coalescing eliminate the extra copy.
439///
440/// If allowFalsePositives is true then likely kills are treated as kills even
441/// if it can't be proven that they are kills.
442bool TwoAddressInstructionImpl::isKilled(MachineInstr &MI, Register Reg,
443 bool allowFalsePositives) const {
445 while (true) {
446 // All uses of physical registers are likely to be kills.
447 if (Reg.isPhysical() && (allowFalsePositives || MRI->hasOneUse(Reg)))
448 return true;
449 if (!isPlainlyKilled(DefMI, Reg))
450 return false;
451 if (Reg.isPhysical())
452 return true;
453 MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg);
454 // If there are multiple defs, we can't do a simple analysis, so just
455 // go with what the kill flag says.
456 if (std::next(Begin) != MRI->def_end())
457 return true;
458 DefMI = Begin->getParent();
459 bool IsSrcPhys, IsDstPhys;
460 Register SrcReg, DstReg;
461 // If the def is something other than a copy, then it isn't going to
462 // be coalesced, so follow the kill flag.
463 if (!isCopyToReg(*DefMI, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
464 return true;
465 Reg = SrcReg;
466 }
467}
468
469/// Return true if the specified MI uses the specified register as a two-address
470/// use. If so, return the destination register by reference.
471static bool isTwoAddrUse(MachineInstr &MI, Register Reg, Register &DstReg) {
472 for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) {
473 const MachineOperand &MO = MI.getOperand(i);
474 if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
475 continue;
476 unsigned ti;
477 if (MI.isRegTiedToDefOperand(i, &ti)) {
478 DstReg = MI.getOperand(ti).getReg();
479 return true;
480 }
481 }
482 return false;
483}
484
485/// Given a register, if all its uses are in the same basic block, return the
486/// last use instruction if it's a copy or a two-address use.
487MachineInstr *TwoAddressInstructionImpl::findOnlyInterestingUse(
488 Register Reg, MachineBasicBlock *MBB, bool &IsCopy, Register &DstReg,
489 bool &IsDstPhys) const {
490 MachineOperand *UseOp = nullptr;
491 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
492 MachineInstr *MI = MO.getParent();
493 if (MI->getParent() != MBB)
494 return nullptr;
495 if (isPlainlyKilled(MI, Reg))
496 UseOp = &MO;
497 }
498 if (!UseOp)
499 return nullptr;
500 MachineInstr &UseMI = *UseOp->getParent();
501
502 Register SrcReg;
503 bool IsSrcPhys;
504 if (isCopyToReg(UseMI, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
505 IsCopy = true;
506 return &UseMI;
507 }
508 IsDstPhys = false;
509 if (isTwoAddrUse(UseMI, Reg, DstReg)) {
510 IsDstPhys = DstReg.isPhysical();
511 return &UseMI;
512 }
513 if (UseMI.isCommutable()) {
515 unsigned Src2 = UseOp->getOperandNo();
516 if (TII->findCommutedOpIndices(UseMI, Src1, Src2)) {
517 MachineOperand &MO = UseMI.getOperand(Src1);
518 if (MO.isReg() && MO.isUse() &&
519 isTwoAddrUse(UseMI, MO.getReg(), DstReg)) {
520 IsDstPhys = DstReg.isPhysical();
521 return &UseMI;
522 }
523 }
524 }
525 return nullptr;
526}
527
528/// Return the physical register the specified virtual register might be mapped
529/// to.
532 while (Reg.isVirtual()) {
534 if (SI == RegMap.end())
535 return 0;
536 Reg = SI->second;
537 }
538 if (Reg.isPhysical())
539 return Reg;
540 return 0;
541}
542
543/// Return true if the two registers are equal or aliased.
544bool TwoAddressInstructionImpl::regsAreCompatible(Register RegA,
545 Register RegB) const {
546 if (RegA == RegB)
547 return true;
548 if (!RegA || !RegB)
549 return false;
550 return TRI->regsOverlap(RegA, RegB);
551}
552
553/// From RegMap remove entries mapped to a physical register which overlaps MO.
554void TwoAddressInstructionImpl::removeMapRegEntry(
555 const MachineOperand &MO, DenseMap<Register, Register> &RegMap) const {
556 assert(
557 (MO.isReg() || MO.isRegMask()) &&
558 "removeMapRegEntry must be called with a register or regmask operand.");
559
561 for (auto SI : RegMap) {
562 Register ToReg = SI.second;
563 if (ToReg.isVirtual())
564 continue;
565
566 if (MO.isReg()) {
567 Register Reg = MO.getReg();
568 if (TRI->regsOverlap(ToReg, Reg))
569 Srcs.push_back(SI.first);
570 } else if (MO.clobbersPhysReg(ToReg))
571 Srcs.push_back(SI.first);
572 }
573
574 for (auto SrcReg : Srcs)
575 RegMap.erase(SrcReg);
576}
577
578/// If a physical register is clobbered, old entries mapped to it should be
579/// deleted. For example
580///
581/// %2:gr64 = COPY killed $rdx
582/// MUL64r %3:gr64, implicit-def $rax, implicit-def $rdx
583///
584/// After the MUL instruction, $rdx contains different value than in the COPY
585/// instruction. So %2 should not map to $rdx after MUL.
586void TwoAddressInstructionImpl::removeClobberedSrcRegMap(MachineInstr *MI) {
587 if (MI->isCopy()) {
588 // If a virtual register is copied to its mapped physical register, it
589 // doesn't change the potential coalescing between them, so we don't remove
590 // entries mapped to the physical register. For example
591 //
592 // %100 = COPY $r8
593 // ...
594 // $r8 = COPY %100
595 //
596 // The first copy constructs SrcRegMap[%100] = $r8, the second copy doesn't
597 // destroy the content of $r8, and should not impact SrcRegMap.
598 Register Dst = MI->getOperand(0).getReg();
599 if (!Dst || Dst.isVirtual())
600 return;
601
602 Register Src = MI->getOperand(1).getReg();
603 if (regsAreCompatible(Dst, getMappedReg(Src, SrcRegMap)))
604 return;
605 }
606
607 for (const MachineOperand &MO : MI->operands()) {
608 if (MO.isRegMask()) {
609 removeMapRegEntry(MO, SrcRegMap);
610 continue;
611 }
612 if (!MO.isReg() || !MO.isDef())
613 continue;
614 Register Reg = MO.getReg();
615 if (!Reg || Reg.isVirtual())
616 continue;
617 removeMapRegEntry(MO, SrcRegMap);
618 }
619}
620
621// Returns true if Reg is equal or aliased to at least one register in Set.
622bool TwoAddressInstructionImpl::regOverlapsSet(
623 const SmallVectorImpl<Register> &Set, Register Reg) const {
624 for (unsigned R : Set)
625 if (TRI->regsOverlap(R, Reg))
626 return true;
627
628 return false;
629}
630
631/// Return true if it's potentially profitable to commute the two-address
632/// instruction that's being processed.
633bool TwoAddressInstructionImpl::isProfitableToCommute(Register RegA,
634 Register RegB,
635 Register RegC,
637 unsigned Dist) {
638 if (OptLevel == CodeGenOptLevel::None)
639 return false;
640
641 // Determine if it's profitable to commute this two address instruction. In
642 // general, we want no uses between this instruction and the definition of
643 // the two-address register.
644 // e.g.
645 // %reg1028 = EXTRACT_SUBREG killed %reg1027, 1
646 // %reg1029 = COPY %reg1028
647 // %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags
648 // insert => %reg1030 = COPY %reg1028
649 // %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags
650 // In this case, it might not be possible to coalesce the second COPY
651 // instruction if the first one is coalesced. So it would be profitable to
652 // commute it:
653 // %reg1028 = EXTRACT_SUBREG killed %reg1027, 1
654 // %reg1029 = COPY %reg1028
655 // %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags
656 // insert => %reg1030 = COPY %reg1029
657 // %reg1030 = ADD8rr killed %reg1029, killed %reg1028, implicit dead %eflags
658
659 if (!isPlainlyKilled(MI, RegC))
660 return false;
661
662 // Ok, we have something like:
663 // %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags
664 // let's see if it's worth commuting it.
665
666 // Look for situations like this:
667 // %reg1024 = MOV r1
668 // %reg1025 = MOV r0
669 // %reg1026 = ADD %reg1024, %reg1025
670 // r0 = MOV %reg1026
671 // Commute the ADD to hopefully eliminate an otherwise unavoidable copy.
672 MCRegister ToRegA = getMappedReg(RegA, DstRegMap);
673 if (ToRegA) {
674 MCRegister FromRegB = getMappedReg(RegB, SrcRegMap);
675 MCRegister FromRegC = getMappedReg(RegC, SrcRegMap);
676 bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA);
677 bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA);
678
679 // Compute if any of the following are true:
680 // -RegB is not tied to a register and RegC is compatible with RegA.
681 // -RegB is tied to the wrong physical register, but RegC is.
682 // -RegB is tied to the wrong physical register, and RegC isn't tied.
683 if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC)))
684 return true;
685 // Don't compute if any of the following are true:
686 // -RegC is not tied to a register and RegB is compatible with RegA.
687 // -RegC is tied to the wrong physical register, but RegB is.
688 // -RegC is tied to the wrong physical register, and RegB isn't tied.
689 if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB)))
690 return false;
691 }
692
693 // If there is a use of RegC between its last def (could be livein) and this
694 // instruction, then bail.
695 unsigned LastDefC = 0;
696 if (!noUseAfterLastDef(RegC, Dist, LastDefC))
697 return false;
698
699 // If there is a use of RegB between its last def (could be livein) and this
700 // instruction, then go ahead and make this transformation.
701 unsigned LastDefB = 0;
702 if (!noUseAfterLastDef(RegB, Dist, LastDefB))
703 return true;
704
705 // Look for situation like this:
706 // %reg101 = MOV %reg100
707 // %reg102 = ...
708 // %reg103 = ADD %reg102, %reg101
709 // ... = %reg103 ...
710 // %reg100 = MOV %reg103
711 // If there is a reversed copy chain from reg101 to reg103, commute the ADD
712 // to eliminate an otherwise unavoidable copy.
713 // FIXME:
714 // We can extend the logic further: If an pair of operands in an insn has
715 // been merged, the insn could be regarded as a virtual copy, and the virtual
716 // copy could also be used to construct a copy chain.
717 // To more generally minimize register copies, ideally the logic of two addr
718 // instruction pass should be integrated with register allocation pass where
719 // interference graph is available.
720 if (isRevCopyChain(RegC, RegA, MaxDataFlowEdge))
721 return true;
722
723 if (isRevCopyChain(RegB, RegA, MaxDataFlowEdge))
724 return false;
725
726 // Look for other target specific commute preference.
727 bool Commute;
728 if (TII->hasCommutePreference(*MI, Commute))
729 return Commute;
730
731 // Since there are no intervening uses for both registers, then commute
732 // if the def of RegC is closer. Its live interval is shorter.
733 return LastDefB && LastDefC && LastDefC > LastDefB;
734}
735
736/// Commute a two-address instruction and update the basic block, distance map,
737/// and live variables if needed. Return true if it is successful.
738bool TwoAddressInstructionImpl::commuteInstruction(MachineInstr *MI,
739 unsigned DstIdx,
740 unsigned RegBIdx,
741 unsigned RegCIdx,
742 unsigned Dist) {
743 Register RegC = MI->getOperand(RegCIdx).getReg();
744 LLVM_DEBUG(dbgs() << "2addr: COMMUTING : " << *MI);
745 MachineInstr *NewMI = TII->commuteInstruction(*MI, false, RegBIdx, RegCIdx);
746
747 if (NewMI == nullptr) {
748 LLVM_DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n");
749 return false;
750 }
751
752 LLVM_DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI);
753 assert(NewMI == MI &&
754 "TargetInstrInfo::commuteInstruction() should not return a new "
755 "instruction unless it was requested.");
756
757 // Update source register map.
758 MCRegister FromRegC = getMappedReg(RegC, SrcRegMap);
759 if (FromRegC) {
760 Register RegA = MI->getOperand(DstIdx).getReg();
761 SrcRegMap[RegA] = FromRegC;
762 }
763
764 return true;
765}
766
767/// Return true if it is profitable to convert the given 2-address instruction
768/// to a 3-address one.
769bool TwoAddressInstructionImpl::isProfitableToConv3Addr(Register RegA,
770 Register RegB) {
771 // Look for situations like this:
772 // %reg1024 = MOV r1
773 // %reg1025 = MOV r0
774 // %reg1026 = ADD %reg1024, %reg1025
775 // r2 = MOV %reg1026
776 // Turn ADD into a 3-address instruction to avoid a copy.
777 MCRegister FromRegB = getMappedReg(RegB, SrcRegMap);
778 if (!FromRegB)
779 return false;
780 MCRegister ToRegA = getMappedReg(RegA, DstRegMap);
781 return (ToRegA && !regsAreCompatible(FromRegB, ToRegA));
782}
783
784/// Convert the specified two-address instruction into a three address one.
785/// Return true if this transformation was successful.
786bool TwoAddressInstructionImpl::convertInstTo3Addr(
788 Register RegA, Register RegB, unsigned &Dist) {
789 MachineInstrSpan MIS(mi, MBB);
790 MachineInstr *NewMI = TII->convertToThreeAddress(*mi, LV, LIS);
791 if (!NewMI)
792 return false;
793
794 LLVM_DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi);
795 LLVM_DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI);
796
797 // If the old instruction is debug value tracked, an update is required.
798 if (auto OldInstrNum = mi->peekDebugInstrNum()) {
799 assert(mi->getNumExplicitDefs() == 1);
800 assert(NewMI->getNumExplicitDefs() == 1);
801
802 // Find the old and new def location.
803 unsigned OldIdx = mi->defs().begin()->getOperandNo();
804 unsigned NewIdx = NewMI->defs().begin()->getOperandNo();
805
806 // Record that one def has been replaced by the other.
807 unsigned NewInstrNum = NewMI->getDebugInstrNum();
808 MF->makeDebugValueSubstitution(std::make_pair(OldInstrNum, OldIdx),
809 std::make_pair(NewInstrNum, NewIdx));
810 }
811
812 MBB->erase(mi); // Nuke the old inst.
813
814 for (MachineInstr &MI : MIS)
815 DistanceMap.insert(std::make_pair(&MI, Dist++));
816 Dist--;
817 mi = NewMI;
818 nmi = std::next(mi);
819
820 // Update source and destination register maps.
821 SrcRegMap.erase(RegA);
822 DstRegMap.erase(RegB);
823 return true;
824}
825
826/// Scan forward recursively for only uses, update maps if the use is a copy or
827/// a two-address instruction.
828void TwoAddressInstructionImpl::scanUses(Register DstReg) {
829 SmallVector<Register, 4> VirtRegPairs;
830 bool IsDstPhys;
831 bool IsCopy = false;
832 Register NewReg;
833 Register Reg = DstReg;
834 while (MachineInstr *UseMI =
835 findOnlyInterestingUse(Reg, MBB, IsCopy, NewReg, IsDstPhys)) {
836 if (IsCopy && !Processed.insert(UseMI).second)
837 break;
838
840 if (DI != DistanceMap.end())
841 // Earlier in the same MBB.Reached via a back edge.
842 break;
843
844 if (IsDstPhys) {
845 VirtRegPairs.push_back(NewReg);
846 break;
847 }
848 SrcRegMap[NewReg] = Reg;
849 VirtRegPairs.push_back(NewReg);
850 Reg = NewReg;
851 }
852
853 if (!VirtRegPairs.empty()) {
854 unsigned ToReg = VirtRegPairs.back();
855 VirtRegPairs.pop_back();
856 while (!VirtRegPairs.empty()) {
857 unsigned FromReg = VirtRegPairs.pop_back_val();
858 bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
859 if (!isNew)
860 assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!");
861 ToReg = FromReg;
862 }
863 bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second;
864 if (!isNew)
865 assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!");
866 }
867}
868
869/// If the specified instruction is not yet processed, process it if it's a
870/// copy. For a copy instruction, we find the physical registers the
871/// source and destination registers might be mapped to. These are kept in
872/// point-to maps used to determine future optimizations. e.g.
873/// v1024 = mov r0
874/// v1025 = mov r1
875/// v1026 = add v1024, v1025
876/// r1 = mov r1026
877/// If 'add' is a two-address instruction, v1024, v1026 are both potentially
878/// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is
879/// potentially joined with r1 on the output side. It's worthwhile to commute
880/// 'add' to eliminate a copy.
881void TwoAddressInstructionImpl::processCopy(MachineInstr *MI) {
882 if (Processed.count(MI))
883 return;
884
885 bool IsSrcPhys, IsDstPhys;
886 Register SrcReg, DstReg;
887 if (!isCopyToReg(*MI, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
888 return;
889
890 if (IsDstPhys && !IsSrcPhys) {
891 DstRegMap.insert(std::make_pair(SrcReg, DstReg));
892 } else if (!IsDstPhys && IsSrcPhys) {
893 bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
894 if (!isNew)
895 assert(SrcRegMap[DstReg] == SrcReg &&
896 "Can't map to two src physical registers!");
897
898 scanUses(DstReg);
899 }
900
901 Processed.insert(MI);
902}
903
904/// If there is one more local instruction that reads 'Reg' and it kills 'Reg,
905/// consider moving the instruction below the kill instruction in order to
906/// eliminate the need for the copy.
907bool TwoAddressInstructionImpl::rescheduleMIBelowKill(
909 Register Reg) {
910 // Bail immediately if we don't have LV or LIS available. We use them to find
911 // kills efficiently.
912 if (!LV && !LIS)
913 return false;
914
915 MachineInstr *MI = &*mi;
917 if (DI == DistanceMap.end())
918 // Must be created from unfolded load. Don't waste time trying this.
919 return false;
920
921 MachineInstr *KillMI = nullptr;
922 if (LIS) {
923 LiveInterval &LI = LIS->getInterval(Reg);
924 assert(LI.end() != LI.begin() &&
925 "Reg should not have empty live interval.");
926
927 SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
928 LiveInterval::const_iterator I = LI.find(MBBEndIdx);
929 if (I != LI.end() && I->start < MBBEndIdx)
930 return false;
931
932 --I;
933 KillMI = LIS->getInstructionFromIndex(I->end);
934 } else {
935 KillMI = LV->getVarInfo(Reg).findKill(MBB);
936 }
937 if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
938 // Don't mess with copies, they may be coalesced later.
939 return false;
940
941 if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() ||
942 KillMI->isBranch() || KillMI->isTerminator())
943 // Don't move pass calls, etc.
944 return false;
945
946 Register DstReg;
947 if (isTwoAddrUse(*KillMI, Reg, DstReg))
948 return false;
949
950 bool SeenStore = true;
951 if (!MI->isSafeToMove(SeenStore))
952 return false;
953
954 if (TII->getInstrLatency(InstrItins, *MI) > 1)
955 // FIXME: Needs more sophisticated heuristics.
956 return false;
957
961 for (const MachineOperand &MO : MI->operands()) {
962 if (!MO.isReg())
963 continue;
964 Register MOReg = MO.getReg();
965 if (!MOReg)
966 continue;
967 if (MO.isDef())
968 Defs.push_back(MOReg);
969 else {
970 Uses.push_back(MOReg);
971 if (MOReg != Reg && isPlainlyKilled(MO))
972 Kills.push_back(MOReg);
973 }
974 }
975
976 // Move the copies connected to MI down as well.
978 MachineBasicBlock::iterator AfterMI = std::next(Begin);
980 while (End != MBB->end()) {
982 if (End->isCopy() && regOverlapsSet(Defs, End->getOperand(1).getReg()))
983 Defs.push_back(End->getOperand(0).getReg());
984 else
985 break;
986 ++End;
987 }
988
989 // Check if the reschedule will not break dependencies.
990 unsigned NumVisited = 0;
991 MachineBasicBlock::iterator KillPos = KillMI;
992 ++KillPos;
993 for (MachineInstr &OtherMI : make_range(End, KillPos)) {
994 // Debug or pseudo instructions cannot be counted against the limit.
995 if (OtherMI.isDebugOrPseudoInstr())
996 continue;
997 if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
998 return false;
999 ++NumVisited;
1000 if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
1001 OtherMI.isBranch() || OtherMI.isTerminator())
1002 // Don't move pass calls, etc.
1003 return false;
1004 for (const MachineOperand &MO : OtherMI.operands()) {
1005 if (!MO.isReg())
1006 continue;
1007 Register MOReg = MO.getReg();
1008 if (!MOReg)
1009 continue;
1010 if (MO.isDef()) {
1011 if (regOverlapsSet(Uses, MOReg))
1012 // Physical register use would be clobbered.
1013 return false;
1014 if (!MO.isDead() && regOverlapsSet(Defs, MOReg))
1015 // May clobber a physical register def.
1016 // FIXME: This may be too conservative. It's ok if the instruction
1017 // is sunken completely below the use.
1018 return false;
1019 } else {
1020 if (regOverlapsSet(Defs, MOReg))
1021 return false;
1022 bool isKill = isPlainlyKilled(MO);
1023 if (MOReg != Reg && ((isKill && regOverlapsSet(Uses, MOReg)) ||
1024 regOverlapsSet(Kills, MOReg)))
1025 // Don't want to extend other live ranges and update kills.
1026 return false;
1027 if (MOReg == Reg && !isKill)
1028 // We can't schedule across a use of the register in question.
1029 return false;
1030 // Ensure that if this is register in question, its the kill we expect.
1031 assert((MOReg != Reg || &OtherMI == KillMI) &&
1032 "Found multiple kills of a register in a basic block");
1033 }
1034 }
1035 }
1036
1037 // Move debug info as well.
1038 while (Begin != MBB->begin() && std::prev(Begin)->isDebugInstr())
1039 --Begin;
1040
1041 nmi = End;
1042 MachineBasicBlock::iterator InsertPos = KillPos;
1043 if (LIS) {
1044 // We have to move the copies (and any interleaved debug instructions)
1045 // first so that the MBB is still well-formed when calling handleMove().
1046 for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) {
1047 auto CopyMI = MBBI++;
1048 MBB->splice(InsertPos, MBB, CopyMI);
1049 if (!CopyMI->isDebugOrPseudoInstr())
1050 LIS->handleMove(*CopyMI);
1051 InsertPos = CopyMI;
1052 }
1053 End = std::next(MachineBasicBlock::iterator(MI));
1054 }
1055
1056 // Copies following MI may have been moved as well.
1057 MBB->splice(InsertPos, MBB, Begin, End);
1058 DistanceMap.erase(DI);
1059
1060 // Update live variables
1061 if (LIS) {
1062 LIS->handleMove(*MI);
1063 } else {
1064 LV->removeVirtualRegisterKilled(Reg, *KillMI);
1065 LV->addVirtualRegisterKilled(Reg, *MI);
1066 }
1067
1068 LLVM_DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI);
1069 return true;
1070}
1071
1072/// Return true if the re-scheduling will put the given instruction too close
1073/// to the defs of its register dependencies.
1074bool TwoAddressInstructionImpl::isDefTooClose(Register Reg, unsigned Dist,
1075 MachineInstr *MI) {
1076 for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
1077 if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike())
1078 continue;
1079 if (&DefMI == MI)
1080 return true; // MI is defining something KillMI uses
1082 if (DDI == DistanceMap.end())
1083 return true; // Below MI
1084 unsigned DefDist = DDI->second;
1085 assert(Dist > DefDist && "Visited def already?");
1086 if (TII->getInstrLatency(InstrItins, DefMI) > (Dist - DefDist))
1087 return true;
1088 }
1089 return false;
1090}
1091
1092/// If there is one more local instruction that reads 'Reg' and it kills 'Reg,
1093/// consider moving the kill instruction above the current two-address
1094/// instruction in order to eliminate the need for the copy.
1095bool TwoAddressInstructionImpl::rescheduleKillAboveMI(
1097 Register Reg) {
1098 // Bail immediately if we don't have LV or LIS available. We use them to find
1099 // kills efficiently.
1100 if (!LV && !LIS)
1101 return false;
1102
1103 MachineInstr *MI = &*mi;
1105 if (DI == DistanceMap.end())
1106 // Must be created from unfolded load. Don't waste time trying this.
1107 return false;
1108
1109 MachineInstr *KillMI = nullptr;
1110 if (LIS) {
1111 LiveInterval &LI = LIS->getInterval(Reg);
1112 assert(LI.end() != LI.begin() &&
1113 "Reg should not have empty live interval.");
1114
1115 SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot();
1116 LiveInterval::const_iterator I = LI.find(MBBEndIdx);
1117 if (I != LI.end() && I->start < MBBEndIdx)
1118 return false;
1119
1120 --I;
1121 KillMI = LIS->getInstructionFromIndex(I->end);
1122 } else {
1123 KillMI = LV->getVarInfo(Reg).findKill(MBB);
1124 }
1125 if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike())
1126 // Don't mess with copies, they may be coalesced later.
1127 return false;
1128
1129 Register DstReg;
1130 if (isTwoAddrUse(*KillMI, Reg, DstReg))
1131 return false;
1132
1133 bool SeenStore = true;
1134 if (!KillMI->isSafeToMove(SeenStore))
1135 return false;
1136
1140 SmallVector<Register, 2> LiveDefs;
1141 for (const MachineOperand &MO : KillMI->operands()) {
1142 if (!MO.isReg())
1143 continue;
1144 Register MOReg = MO.getReg();
1145 if (MO.isUse()) {
1146 if (!MOReg)
1147 continue;
1148 if (isDefTooClose(MOReg, DI->second, MI))
1149 return false;
1150 bool isKill = isPlainlyKilled(MO);
1151 if (MOReg == Reg && !isKill)
1152 return false;
1153 Uses.push_back(MOReg);
1154 if (isKill && MOReg != Reg)
1155 Kills.push_back(MOReg);
1156 } else if (MOReg.isPhysical()) {
1157 Defs.push_back(MOReg);
1158 if (!MO.isDead())
1159 LiveDefs.push_back(MOReg);
1160 }
1161 }
1162
1163 // Check if the reschedule will not break dependencies.
1164 unsigned NumVisited = 0;
1165 for (MachineInstr &OtherMI :
1167 // Debug or pseudo instructions cannot be counted against the limit.
1168 if (OtherMI.isDebugOrPseudoInstr())
1169 continue;
1170 if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost.
1171 return false;
1172 ++NumVisited;
1173 if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() ||
1174 OtherMI.isBranch() || OtherMI.isTerminator())
1175 // Don't move pass calls, etc.
1176 return false;
1177 SmallVector<Register, 2> OtherDefs;
1178 for (const MachineOperand &MO : OtherMI.operands()) {
1179 if (!MO.isReg())
1180 continue;
1181 Register MOReg = MO.getReg();
1182 if (!MOReg)
1183 continue;
1184 if (MO.isUse()) {
1185 if (regOverlapsSet(Defs, MOReg))
1186 // Moving KillMI can clobber the physical register if the def has
1187 // not been seen.
1188 return false;
1189 if (regOverlapsSet(Kills, MOReg))
1190 // Don't want to extend other live ranges and update kills.
1191 return false;
1192 if (&OtherMI != MI && MOReg == Reg && !isPlainlyKilled(MO))
1193 // We can't schedule across a use of the register in question.
1194 return false;
1195 } else {
1196 OtherDefs.push_back(MOReg);
1197 }
1198 }
1199
1200 for (Register MOReg : OtherDefs) {
1201 if (regOverlapsSet(Uses, MOReg))
1202 return false;
1203 if (MOReg.isPhysical() && regOverlapsSet(LiveDefs, MOReg))
1204 return false;
1205 // Physical register def is seen.
1206 llvm::erase(Defs, MOReg);
1207 }
1208 }
1209
1210 // Move the old kill above MI, don't forget to move debug info as well.
1211 MachineBasicBlock::iterator InsertPos = mi;
1212 while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugInstr())
1213 --InsertPos;
1215 MachineBasicBlock::iterator To = std::next(From);
1216 while (std::prev(From)->isDebugInstr())
1217 --From;
1218 MBB->splice(InsertPos, MBB, From, To);
1219
1220 nmi = std::prev(InsertPos); // Backtrack so we process the moved instr.
1221 DistanceMap.erase(DI);
1222
1223 // Update live variables
1224 if (LIS) {
1225 LIS->handleMove(*KillMI);
1226 } else {
1227 LV->removeVirtualRegisterKilled(Reg, *KillMI);
1228 LV->addVirtualRegisterKilled(Reg, *MI);
1229 }
1230
1231 LLVM_DEBUG(dbgs() << "\trescheduled kill: " << *KillMI);
1232 return true;
1233}
1234
1235/// Tries to commute the operand 'BaseOpIdx' and some other operand in the
1236/// given machine instruction to improve opportunities for coalescing and
1237/// elimination of a register to register copy.
1238///
1239/// 'DstOpIdx' specifies the index of MI def operand.
1240/// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx'
1241/// operand is killed by the given instruction.
1242/// The 'Dist' arguments provides the distance of MI from the start of the
1243/// current basic block and it is used to determine if it is profitable
1244/// to commute operands in the instruction.
1245///
1246/// Returns true if the transformation happened. Otherwise, returns false.
1247bool TwoAddressInstructionImpl::tryInstructionCommute(MachineInstr *MI,
1248 unsigned DstOpIdx,
1249 unsigned BaseOpIdx,
1250 bool BaseOpKilled,
1251 unsigned Dist) {
1252 if (!MI->isCommutable())
1253 return false;
1254
1255 bool MadeChange = false;
1256 Register DstOpReg = MI->getOperand(DstOpIdx).getReg();
1257 Register BaseOpReg = MI->getOperand(BaseOpIdx).getReg();
1258 unsigned OpsNum = MI->getDesc().getNumOperands();
1259 unsigned OtherOpIdx = MI->getDesc().getNumDefs();
1260 for (; OtherOpIdx < OpsNum; OtherOpIdx++) {
1261 // The call of findCommutedOpIndices below only checks if BaseOpIdx
1262 // and OtherOpIdx are commutable, it does not really search for
1263 // other commutable operands and does not change the values of passed
1264 // variables.
1265 if (OtherOpIdx == BaseOpIdx || !MI->getOperand(OtherOpIdx).isReg() ||
1266 !TII->findCommutedOpIndices(*MI, BaseOpIdx, OtherOpIdx))
1267 continue;
1268
1269 Register OtherOpReg = MI->getOperand(OtherOpIdx).getReg();
1270 bool AggressiveCommute = false;
1271
1272 // If OtherOp dies but BaseOp does not, swap the OtherOp and BaseOp
1273 // operands. This makes the live ranges of DstOp and OtherOp joinable.
1274 bool OtherOpKilled = isKilled(*MI, OtherOpReg, false);
1275 bool DoCommute = !BaseOpKilled && OtherOpKilled;
1276
1277 if (!DoCommute &&
1278 isProfitableToCommute(DstOpReg, BaseOpReg, OtherOpReg, MI, Dist)) {
1279 DoCommute = true;
1280 AggressiveCommute = true;
1281 }
1282
1283 // If it's profitable to commute, try to do so.
1284 if (DoCommute && commuteInstruction(MI, DstOpIdx, BaseOpIdx, OtherOpIdx,
1285 Dist)) {
1286 MadeChange = true;
1287 ++NumCommuted;
1288 if (AggressiveCommute)
1289 ++NumAggrCommuted;
1290
1291 // There might be more than two commutable operands, update BaseOp and
1292 // continue scanning.
1293 // FIXME: This assumes that the new instruction's operands are in the
1294 // same positions and were simply swapped.
1295 BaseOpReg = OtherOpReg;
1296 BaseOpKilled = OtherOpKilled;
1297 // Resamples OpsNum in case the number of operands was reduced. This
1298 // happens with X86.
1299 OpsNum = MI->getDesc().getNumOperands();
1300 }
1301 }
1302 return MadeChange;
1303}
1304
1305/// For the case where an instruction has a single pair of tied register
1306/// operands, attempt some transformations that may either eliminate the tied
1307/// operands or improve the opportunities for coalescing away the register copy.
1308/// Returns true if no copy needs to be inserted to untie mi's operands
1309/// (either because they were untied, or because mi was rescheduled, and will
1310/// be visited again later). If the shouldOnlyCommute flag is true, only
1311/// instruction commutation is attempted.
1312bool TwoAddressInstructionImpl::tryInstructionTransform(
1314 unsigned SrcIdx, unsigned DstIdx, unsigned &Dist, bool shouldOnlyCommute) {
1315 if (OptLevel == CodeGenOptLevel::None)
1316 return false;
1317
1318 MachineInstr &MI = *mi;
1319 Register regA = MI.getOperand(DstIdx).getReg();
1320 Register regB = MI.getOperand(SrcIdx).getReg();
1321
1322 assert(regB.isVirtual() && "cannot make instruction into two-address form");
1323 bool regBKilled = isKilled(MI, regB, true);
1324
1325 if (regA.isVirtual())
1326 scanUses(regA);
1327
1328 bool Commuted = tryInstructionCommute(&MI, DstIdx, SrcIdx, regBKilled, Dist);
1329
1330 // If the instruction is convertible to 3 Addr, instead
1331 // of returning try 3 Addr transformation aggressively and
1332 // use this variable to check later. Because it might be better.
1333 // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret`
1334 // instead of the following code.
1335 // addl %esi, %edi
1336 // movl %edi, %eax
1337 // ret
1338 if (Commuted && !MI.isConvertibleTo3Addr())
1339 return false;
1340
1341 if (shouldOnlyCommute)
1342 return false;
1343
1344 // If there is one more use of regB later in the same MBB, consider
1345 // re-schedule this MI below it.
1346 if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) {
1347 ++NumReSchedDowns;
1348 return true;
1349 }
1350
1351 // If we commuted, regB may have changed so we should re-sample it to avoid
1352 // confusing the three address conversion below.
1353 if (Commuted) {
1354 regB = MI.getOperand(SrcIdx).getReg();
1355 regBKilled = isKilled(MI, regB, true);
1356 }
1357
1358 if (MI.isConvertibleTo3Addr()) {
1359 // This instruction is potentially convertible to a true
1360 // three-address instruction. Check if it is profitable.
1361 if (!regBKilled || isProfitableToConv3Addr(regA, regB)) {
1362 // Try to convert it.
1363 if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) {
1364 ++NumConvertedTo3Addr;
1365 return true; // Done with this instruction.
1366 }
1367 }
1368 }
1369
1370 // Return if it is commuted but 3 addr conversion is failed.
1371 if (Commuted)
1372 return false;
1373
1374 // If there is one more use of regB later in the same MBB, consider
1375 // re-schedule it before this MI if it's legal.
1376 if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) {
1377 ++NumReSchedUps;
1378 return true;
1379 }
1380
1381 // If this is an instruction with a load folded into it, try unfolding
1382 // the load, e.g. avoid this:
1383 // movq %rdx, %rcx
1384 // addq (%rax), %rcx
1385 // in favor of this:
1386 // movq (%rax), %rcx
1387 // addq %rdx, %rcx
1388 // because it's preferable to schedule a load than a register copy.
1389 if (MI.mayLoad() && !regBKilled) {
1390 // Determine if a load can be unfolded.
1391 unsigned LoadRegIndex;
1392 unsigned NewOpc =
1393 TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(),
1394 /*UnfoldLoad=*/true,
1395 /*UnfoldStore=*/false,
1396 &LoadRegIndex);
1397 if (NewOpc != 0) {
1398 const MCInstrDesc &UnfoldMCID = TII->get(NewOpc);
1399 if (UnfoldMCID.getNumDefs() == 1) {
1400 // Unfold the load.
1401 LLVM_DEBUG(dbgs() << "2addr: UNFOLDING: " << MI);
1402 const TargetRegisterClass *RC =
1403 TRI->getAllocatableClass(
1404 TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF));
1405 Register Reg = MRI->createVirtualRegister(RC);
1407 if (!TII->unfoldMemoryOperand(*MF, MI, Reg,
1408 /*UnfoldLoad=*/true,
1409 /*UnfoldStore=*/false, NewMIs)) {
1410 LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1411 return false;
1412 }
1413 assert(NewMIs.size() == 2 &&
1414 "Unfolded a load into multiple instructions!");
1415 // The load was previously folded, so this is the only use.
1416 NewMIs[1]->addRegisterKilled(Reg, TRI);
1417
1418 // Tentatively insert the instructions into the block so that they
1419 // look "normal" to the transformation logic.
1420 MBB->insert(mi, NewMIs[0]);
1421 MBB->insert(mi, NewMIs[1]);
1422 DistanceMap.insert(std::make_pair(NewMIs[0], Dist++));
1423 DistanceMap.insert(std::make_pair(NewMIs[1], Dist));
1424
1425 LLVM_DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0]
1426 << "2addr: NEW INST: " << *NewMIs[1]);
1427
1428 // Transform the instruction, now that it no longer has a load.
1429 unsigned NewDstIdx =
1430 NewMIs[1]->findRegisterDefOperandIdx(regA, /*TRI=*/nullptr);
1431 unsigned NewSrcIdx =
1432 NewMIs[1]->findRegisterUseOperandIdx(regB, /*TRI=*/nullptr);
1433 MachineBasicBlock::iterator NewMI = NewMIs[1];
1434 bool TransformResult =
1435 tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist, true);
1436 (void)TransformResult;
1437 assert(!TransformResult &&
1438 "tryInstructionTransform() should return false.");
1439 if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) {
1440 // Success, or at least we made an improvement. Keep the unfolded
1441 // instructions and discard the original.
1442 if (LV) {
1443 for (const MachineOperand &MO : MI.operands()) {
1444 if (MO.isReg() && MO.getReg().isVirtual()) {
1445 if (MO.isUse()) {
1446 if (MO.isKill()) {
1447 if (NewMIs[0]->killsRegister(MO.getReg(), /*TRI=*/nullptr))
1448 LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[0]);
1449 else {
1450 assert(NewMIs[1]->killsRegister(MO.getReg(),
1451 /*TRI=*/nullptr) &&
1452 "Kill missing after load unfold!");
1453 LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[1]);
1454 }
1455 }
1456 } else if (LV->removeVirtualRegisterDead(MO.getReg(), MI)) {
1457 if (NewMIs[1]->registerDefIsDead(MO.getReg(),
1458 /*TRI=*/nullptr))
1459 LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[1]);
1460 else {
1461 assert(NewMIs[0]->registerDefIsDead(MO.getReg(),
1462 /*TRI=*/nullptr) &&
1463 "Dead flag missing after load unfold!");
1464 LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[0]);
1465 }
1466 }
1467 }
1468 }
1469 LV->addVirtualRegisterKilled(Reg, *NewMIs[1]);
1470 }
1471
1472 SmallVector<Register, 4> OrigRegs;
1473 if (LIS) {
1474 for (const MachineOperand &MO : MI.operands()) {
1475 if (MO.isReg())
1476 OrigRegs.push_back(MO.getReg());
1477 }
1478
1479 LIS->RemoveMachineInstrFromMaps(MI);
1480 }
1481
1482 MI.eraseFromParent();
1483 DistanceMap.erase(&MI);
1484
1485 // Update LiveIntervals.
1486 if (LIS) {
1487 MachineBasicBlock::iterator Begin(NewMIs[0]);
1489 LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs);
1490 }
1491
1492 mi = NewMIs[1];
1493 } else {
1494 // Transforming didn't eliminate the tie and didn't lead to an
1495 // improvement. Clean up the unfolded instructions and keep the
1496 // original.
1497 LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1498 NewMIs[0]->eraseFromParent();
1499 NewMIs[1]->eraseFromParent();
1500 DistanceMap.erase(NewMIs[0]);
1501 DistanceMap.erase(NewMIs[1]);
1502 Dist--;
1503 }
1504 }
1505 }
1506 }
1507
1508 return false;
1509}
1510
1511// Collect tied operands of MI that need to be handled.
1512// Rewrite trivial cases immediately.
1513// Return true if any tied operands where found, including the trivial ones.
1514bool TwoAddressInstructionImpl::collectTiedOperands(
1515 MachineInstr *MI, TiedOperandMap &TiedOperands) {
1516 bool AnyOps = false;
1517 unsigned NumOps = MI->getNumOperands();
1518
1519 for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
1520 unsigned DstIdx = 0;
1521 if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx))
1522 continue;
1523 AnyOps = true;
1524 MachineOperand &SrcMO = MI->getOperand(SrcIdx);
1525 MachineOperand &DstMO = MI->getOperand(DstIdx);
1526 Register SrcReg = SrcMO.getReg();
1527 Register DstReg = DstMO.getReg();
1528 // Tied constraint already satisfied?
1529 if (SrcReg == DstReg)
1530 continue;
1531
1532 assert(SrcReg && SrcMO.isUse() && "two address instruction invalid");
1533
1534 // Deal with undef uses immediately - simply rewrite the src operand.
1535 if (SrcMO.isUndef() && !DstMO.getSubReg()) {
1536 // Constrain the DstReg register class if required.
1537 if (DstReg.isVirtual()) {
1538 const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
1539 MRI->constrainRegClass(DstReg, RC);
1540 }
1541 SrcMO.setReg(DstReg);
1542 SrcMO.setSubReg(0);
1543 LLVM_DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI);
1544 continue;
1545 }
1546 TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx));
1547 }
1548 return AnyOps;
1549}
1550
1551// Process a list of tied MI operands that all use the same source register.
1552// The tied pairs are of the form (SrcIdx, DstIdx).
1553void TwoAddressInstructionImpl::processTiedPairs(MachineInstr *MI,
1554 TiedPairList &TiedPairs,
1555 unsigned &Dist) {
1556 bool IsEarlyClobber = llvm::any_of(TiedPairs, [MI](auto const &TP) {
1557 return MI->getOperand(TP.second).isEarlyClobber();
1558 });
1559
1560 bool RemovedKillFlag = false;
1561 bool AllUsesCopied = true;
1562 unsigned LastCopiedReg = 0;
1563 SlotIndex LastCopyIdx;
1564 Register RegB = 0;
1565 unsigned SubRegB = 0;
1566 for (auto &TP : TiedPairs) {
1567 unsigned SrcIdx = TP.first;
1568 unsigned DstIdx = TP.second;
1569
1570 const MachineOperand &DstMO = MI->getOperand(DstIdx);
1571 Register RegA = DstMO.getReg();
1572
1573 // Grab RegB from the instruction because it may have changed if the
1574 // instruction was commuted.
1575 RegB = MI->getOperand(SrcIdx).getReg();
1576 SubRegB = MI->getOperand(SrcIdx).getSubReg();
1577
1578 if (RegA == RegB) {
1579 // The register is tied to multiple destinations (or else we would
1580 // not have continued this far), but this use of the register
1581 // already matches the tied destination. Leave it.
1582 AllUsesCopied = false;
1583 continue;
1584 }
1585 LastCopiedReg = RegA;
1586
1587 assert(RegB.isVirtual() && "cannot make instruction into two-address form");
1588
1589#ifndef NDEBUG
1590 // First, verify that we don't have a use of "a" in the instruction
1591 // (a = b + a for example) because our transformation will not
1592 // work. This should never occur because we are in SSA form.
1593 for (unsigned i = 0; i != MI->getNumOperands(); ++i)
1594 assert(i == DstIdx ||
1595 !MI->getOperand(i).isReg() ||
1596 MI->getOperand(i).getReg() != RegA);
1597#endif
1598
1599 // Emit a copy.
1600 MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
1601 TII->get(TargetOpcode::COPY), RegA);
1602 // If this operand is folding a truncation, the truncation now moves to the
1603 // copy so that the register classes remain valid for the operands.
1604 MIB.addReg(RegB, 0, SubRegB);
1605 const TargetRegisterClass *RC = MRI->getRegClass(RegB);
1606 if (SubRegB) {
1607 if (RegA.isVirtual()) {
1608 assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA),
1609 SubRegB) &&
1610 "tied subregister must be a truncation");
1611 // The superreg class will not be used to constrain the subreg class.
1612 RC = nullptr;
1613 } else {
1614 assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB))
1615 && "tied subregister must be a truncation");
1616 }
1617 }
1618
1619 // Update DistanceMap.
1621 --PrevMI;
1622 DistanceMap.insert(std::make_pair(&*PrevMI, Dist));
1623 DistanceMap[MI] = ++Dist;
1624
1625 if (LIS) {
1626 LastCopyIdx = LIS->InsertMachineInstrInMaps(*PrevMI).getRegSlot();
1627
1628 SlotIndex endIdx =
1629 LIS->getInstructionIndex(*MI).getRegSlot(IsEarlyClobber);
1630 if (RegA.isVirtual()) {
1631 LiveInterval &LI = LIS->getInterval(RegA);
1632 VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1633 LI.addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1634 for (auto &S : LI.subranges()) {
1635 VNI = S.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1636 S.addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1637 }
1638 } else {
1639 for (MCRegUnit Unit : TRI->regunits(RegA)) {
1640 if (LiveRange *LR = LIS->getCachedRegUnit(Unit)) {
1641 VNInfo *VNI =
1642 LR->getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1643 LR->addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1644 }
1645 }
1646 }
1647 }
1648
1649 LLVM_DEBUG(dbgs() << "\t\tprepend:\t" << *MIB);
1650
1651 MachineOperand &MO = MI->getOperand(SrcIdx);
1652 assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() &&
1653 "inconsistent operand info for 2-reg pass");
1654 if (isPlainlyKilled(MO)) {
1655 MO.setIsKill(false);
1656 RemovedKillFlag = true;
1657 }
1658
1659 // Make sure regA is a legal regclass for the SrcIdx operand.
1660 if (RegA.isVirtual() && RegB.isVirtual())
1661 MRI->constrainRegClass(RegA, RC);
1662 MO.setReg(RegA);
1663 // The getMatchingSuper asserts guarantee that the register class projected
1664 // by SubRegB is compatible with RegA with no subregister. So regardless of
1665 // whether the dest oper writes a subreg, the source oper should not.
1666 MO.setSubReg(0);
1667 }
1668
1669 if (AllUsesCopied) {
1670 LaneBitmask RemainingUses = LaneBitmask::getNone();
1671 // Replace other (un-tied) uses of regB with LastCopiedReg.
1672 for (MachineOperand &MO : MI->all_uses()) {
1673 if (MO.getReg() == RegB) {
1674 if (MO.getSubReg() == SubRegB && !IsEarlyClobber) {
1675 if (isPlainlyKilled(MO)) {
1676 MO.setIsKill(false);
1677 RemovedKillFlag = true;
1678 }
1679 MO.setReg(LastCopiedReg);
1680 MO.setSubReg(0);
1681 } else {
1682 RemainingUses |= TRI->getSubRegIndexLaneMask(MO.getSubReg());
1683 }
1684 }
1685 }
1686
1687 // Update live variables for regB.
1688 if (RemovedKillFlag && RemainingUses.none() && LV &&
1689 LV->getVarInfo(RegB).removeKill(*MI)) {
1691 --PrevMI;
1692 LV->addVirtualRegisterKilled(RegB, *PrevMI);
1693 }
1694
1695 if (RemovedKillFlag && RemainingUses.none())
1696 SrcRegMap[LastCopiedReg] = RegB;
1697
1698 // Update LiveIntervals.
1699 if (LIS) {
1700 SlotIndex UseIdx = LIS->getInstructionIndex(*MI);
1701 auto Shrink = [=](LiveRange &LR, LaneBitmask LaneMask) {
1702 LiveRange::Segment *S = LR.getSegmentContaining(LastCopyIdx);
1703 if (!S)
1704 return true;
1705 if ((LaneMask & RemainingUses).any())
1706 return false;
1707 if (S->end.getBaseIndex() != UseIdx)
1708 return false;
1709 S->end = LastCopyIdx;
1710 return true;
1711 };
1712
1713 LiveInterval &LI = LIS->getInterval(RegB);
1714 bool ShrinkLI = true;
1715 for (auto &S : LI.subranges())
1716 ShrinkLI &= Shrink(S, S.LaneMask);
1717 if (ShrinkLI)
1718 Shrink(LI, LaneBitmask::getAll());
1719 }
1720 } else if (RemovedKillFlag) {
1721 // Some tied uses of regB matched their destination registers, so
1722 // regB is still used in this instruction, but a kill flag was
1723 // removed from a different tied use of regB, so now we need to add
1724 // a kill flag to one of the remaining uses of regB.
1725 for (MachineOperand &MO : MI->all_uses()) {
1726 if (MO.getReg() == RegB) {
1727 MO.setIsKill(true);
1728 break;
1729 }
1730 }
1731 }
1732}
1733
1734// For every tied operand pair this function transforms statepoint from
1735// RegA = STATEPOINT ... RegB(tied-def N)
1736// to
1737// RegB = STATEPOINT ... RegB(tied-def N)
1738// and replaces all uses of RegA with RegB.
1739// No extra COPY instruction is necessary because tied use is killed at
1740// STATEPOINT.
1741bool TwoAddressInstructionImpl::processStatepoint(
1742 MachineInstr *MI, TiedOperandMap &TiedOperands) {
1743
1744 bool NeedCopy = false;
1745 for (auto &TO : TiedOperands) {
1746 Register RegB = TO.first;
1747 if (TO.second.size() != 1) {
1748 NeedCopy = true;
1749 continue;
1750 }
1751
1752 unsigned SrcIdx = TO.second[0].first;
1753 unsigned DstIdx = TO.second[0].second;
1754
1755 MachineOperand &DstMO = MI->getOperand(DstIdx);
1756 Register RegA = DstMO.getReg();
1757
1758 assert(RegB == MI->getOperand(SrcIdx).getReg());
1759
1760 if (RegA == RegB)
1761 continue;
1762
1763 // CodeGenPrepare can sink pointer compare past statepoint, which
1764 // breaks assumption that statepoint kills tied-use register when
1765 // in SSA form (see note in IR/SafepointIRVerifier.cpp). Fall back
1766 // to generic tied register handling to avoid assertion failures.
1767 // TODO: Recompute LIS/LV information for new range here.
1768 if (LIS) {
1769 const auto &UseLI = LIS->getInterval(RegB);
1770 const auto &DefLI = LIS->getInterval(RegA);
1771 if (DefLI.overlaps(UseLI)) {
1772 LLVM_DEBUG(dbgs() << "LIS: " << printReg(RegB, TRI, 0)
1773 << " UseLI overlaps with DefLI\n");
1774 NeedCopy = true;
1775 continue;
1776 }
1777 } else if (LV && LV->getVarInfo(RegB).findKill(MI->getParent()) != MI) {
1778 // Note that MachineOperand::isKill does not work here, because it
1779 // is set only on first register use in instruction and for statepoint
1780 // tied-use register will usually be found in preceeding deopt bundle.
1781 LLVM_DEBUG(dbgs() << "LV: " << printReg(RegB, TRI, 0)
1782 << " not killed by statepoint\n");
1783 NeedCopy = true;
1784 continue;
1785 }
1786
1787 if (!MRI->constrainRegClass(RegB, MRI->getRegClass(RegA))) {
1788 LLVM_DEBUG(dbgs() << "MRI: couldn't constrain" << printReg(RegB, TRI, 0)
1789 << " to register class of " << printReg(RegA, TRI, 0)
1790 << '\n');
1791 NeedCopy = true;
1792 continue;
1793 }
1794 MRI->replaceRegWith(RegA, RegB);
1795
1796 if (LIS) {
1797 VNInfo::Allocator &A = LIS->getVNInfoAllocator();
1798 LiveInterval &LI = LIS->getInterval(RegB);
1799 LiveInterval &Other = LIS->getInterval(RegA);
1800 SmallVector<VNInfo *> NewVNIs;
1801 for (const VNInfo *VNI : Other.valnos) {
1802 assert(VNI->id == NewVNIs.size() && "assumed");
1803 NewVNIs.push_back(LI.createValueCopy(VNI, A));
1804 }
1805 for (auto &S : Other) {
1806 VNInfo *VNI = NewVNIs[S.valno->id];
1807 LiveRange::Segment NewSeg(S.start, S.end, VNI);
1808 LI.addSegment(NewSeg);
1809 }
1810 LIS->removeInterval(RegA);
1811 }
1812
1813 if (LV) {
1814 if (MI->getOperand(SrcIdx).isKill())
1815 LV->removeVirtualRegisterKilled(RegB, *MI);
1816 LiveVariables::VarInfo &SrcInfo = LV->getVarInfo(RegB);
1817 LiveVariables::VarInfo &DstInfo = LV->getVarInfo(RegA);
1818 SrcInfo.AliveBlocks |= DstInfo.AliveBlocks;
1819 DstInfo.AliveBlocks.clear();
1820 for (auto *KillMI : DstInfo.Kills)
1821 LV->addVirtualRegisterKilled(RegB, *KillMI, false);
1822 }
1823 }
1824 return !NeedCopy;
1825}
1826
1827/// Reduce two-address instructions to two operands.
1828bool TwoAddressInstructionImpl::run() {
1829 bool MadeChange = false;
1830
1831 LLVM_DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
1832 LLVM_DEBUG(dbgs() << "********** Function: " << MF->getName() << '\n');
1833
1834 // This pass takes the function out of SSA form.
1835 MRI->leaveSSA();
1836
1837 // This pass will rewrite the tied-def to meet the RegConstraint.
1838 MF->getProperties()
1839 .set(MachineFunctionProperties::Property::TiedOpsRewritten);
1840
1841 TiedOperandMap TiedOperands;
1842 for (MachineBasicBlock &MBBI : *MF) {
1843 MBB = &MBBI;
1844 unsigned Dist = 0;
1845 DistanceMap.clear();
1846 SrcRegMap.clear();
1847 DstRegMap.clear();
1848 Processed.clear();
1849 for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end();
1850 mi != me; ) {
1851 MachineBasicBlock::iterator nmi = std::next(mi);
1852 // Skip debug instructions.
1853 if (mi->isDebugInstr()) {
1854 mi = nmi;
1855 continue;
1856 }
1857
1858 // Expand REG_SEQUENCE instructions. This will position mi at the first
1859 // expanded instruction.
1860 if (mi->isRegSequence())
1861 eliminateRegSequence(mi);
1862
1863 DistanceMap.insert(std::make_pair(&*mi, ++Dist));
1864
1865 processCopy(&*mi);
1866
1867 // First scan through all the tied register uses in this instruction
1868 // and record a list of pairs of tied operands for each register.
1869 if (!collectTiedOperands(&*mi, TiedOperands)) {
1870 removeClobberedSrcRegMap(&*mi);
1871 mi = nmi;
1872 continue;
1873 }
1874
1875 ++NumTwoAddressInstrs;
1876 MadeChange = true;
1877 LLVM_DEBUG(dbgs() << '\t' << *mi);
1878
1879 // If the instruction has a single pair of tied operands, try some
1880 // transformations that may either eliminate the tied operands or
1881 // improve the opportunities for coalescing away the register copy.
1882 if (TiedOperands.size() == 1) {
1884 = TiedOperands.begin()->second;
1885 if (TiedPairs.size() == 1) {
1886 unsigned SrcIdx = TiedPairs[0].first;
1887 unsigned DstIdx = TiedPairs[0].second;
1888 Register SrcReg = mi->getOperand(SrcIdx).getReg();
1889 Register DstReg = mi->getOperand(DstIdx).getReg();
1890 if (SrcReg != DstReg &&
1891 tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) {
1892 // The tied operands have been eliminated or shifted further down
1893 // the block to ease elimination. Continue processing with 'nmi'.
1894 TiedOperands.clear();
1895 removeClobberedSrcRegMap(&*mi);
1896 mi = nmi;
1897 continue;
1898 }
1899 }
1900 }
1901
1902 if (mi->getOpcode() == TargetOpcode::STATEPOINT &&
1903 processStatepoint(&*mi, TiedOperands)) {
1904 TiedOperands.clear();
1905 LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1906 mi = nmi;
1907 continue;
1908 }
1909
1910 // Now iterate over the information collected above.
1911 for (auto &TO : TiedOperands) {
1912 processTiedPairs(&*mi, TO.second, Dist);
1913 LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1914 }
1915
1916 // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form.
1917 if (mi->isInsertSubreg()) {
1918 // From %reg = INSERT_SUBREG %reg, %subreg, subidx
1919 // To %reg:subidx = COPY %subreg
1920 unsigned SubIdx = mi->getOperand(3).getImm();
1921 mi->removeOperand(3);
1922 assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
1923 mi->getOperand(0).setSubReg(SubIdx);
1924 mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef());
1925 mi->removeOperand(1);
1926 mi->setDesc(TII->get(TargetOpcode::COPY));
1927 LLVM_DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
1928
1929 // Update LiveIntervals.
1930 if (LIS) {
1931 Register Reg = mi->getOperand(0).getReg();
1932 LiveInterval &LI = LIS->getInterval(Reg);
1933 if (LI.hasSubRanges()) {
1934 // The COPY no longer defines subregs of %reg except for
1935 // %reg.subidx.
1936 LaneBitmask LaneMask =
1937 TRI->getSubRegIndexLaneMask(mi->getOperand(0).getSubReg());
1938 SlotIndex Idx = LIS->getInstructionIndex(*mi).getRegSlot();
1939 for (auto &S : LI.subranges()) {
1940 if ((S.LaneMask & LaneMask).none()) {
1941 LiveRange::iterator DefSeg = S.FindSegmentContaining(Idx);
1942 if (mi->getOperand(0).isUndef()) {
1943 S.removeValNo(DefSeg->valno);
1944 } else {
1945 LiveRange::iterator UseSeg = std::prev(DefSeg);
1946 S.MergeValueNumberInto(DefSeg->valno, UseSeg->valno);
1947 }
1948 }
1949 }
1950
1951 // The COPY no longer has a use of %reg.
1952 LIS->shrinkToUses(&LI);
1953 } else {
1954 // The live interval for Reg did not have subranges but now it needs
1955 // them because we have introduced a subreg def. Recompute it.
1956 LIS->removeInterval(Reg);
1957 LIS->createAndComputeVirtRegInterval(Reg);
1958 }
1959 }
1960 }
1961
1962 // Clear TiedOperands here instead of at the top of the loop
1963 // since most instructions do not have tied operands.
1964 TiedOperands.clear();
1965 removeClobberedSrcRegMap(&*mi);
1966 mi = nmi;
1967 }
1968 }
1969
1970 return MadeChange;
1971}
1972
1973/// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process.
1974///
1975/// The instruction is turned into a sequence of sub-register copies:
1976///
1977/// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1
1978///
1979/// Becomes:
1980///
1981/// undef %dst:ssub0 = COPY %v1
1982/// %dst:ssub1 = COPY %v2
1983void TwoAddressInstructionImpl::eliminateRegSequence(
1985 MachineInstr &MI = *MBBI;
1986 Register DstReg = MI.getOperand(0).getReg();
1987
1988 SmallVector<Register, 4> OrigRegs;
1989 VNInfo *DefVN = nullptr;
1990 if (LIS) {
1991 OrigRegs.push_back(MI.getOperand(0).getReg());
1992 for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2)
1993 OrigRegs.push_back(MI.getOperand(i).getReg());
1994 if (LIS->hasInterval(DstReg)) {
1995 DefVN = LIS->getInterval(DstReg)
1996 .Query(LIS->getInstructionIndex(MI))
1997 .valueOut();
1998 }
1999 }
2000
2001 LaneBitmask UndefLanes = LaneBitmask::getNone();
2002 bool DefEmitted = false;
2003 for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) {
2004 MachineOperand &UseMO = MI.getOperand(i);
2005 Register SrcReg = UseMO.getReg();
2006 unsigned SubIdx = MI.getOperand(i+1).getImm();
2007 // Nothing needs to be inserted for undef operands.
2008 if (UseMO.isUndef()) {
2009 UndefLanes |= TRI->getSubRegIndexLaneMask(SubIdx);
2010 continue;
2011 }
2012
2013 // Defer any kill flag to the last operand using SrcReg. Otherwise, we
2014 // might insert a COPY that uses SrcReg after is was killed.
2015 bool isKill = UseMO.isKill();
2016 if (isKill)
2017 for (unsigned j = i + 2; j < e; j += 2)
2018 if (MI.getOperand(j).getReg() == SrcReg) {
2019 MI.getOperand(j).setIsKill();
2020 UseMO.setIsKill(false);
2021 isKill = false;
2022 break;
2023 }
2024
2025 // Insert the sub-register copy.
2026 MachineInstr *CopyMI = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(),
2027 TII->get(TargetOpcode::COPY))
2028 .addReg(DstReg, RegState::Define, SubIdx)
2029 .add(UseMO);
2030
2031 // The first def needs an undef flag because there is no live register
2032 // before it.
2033 if (!DefEmitted) {
2034 CopyMI->getOperand(0).setIsUndef(true);
2035 // Return an iterator pointing to the first inserted instr.
2036 MBBI = CopyMI;
2037 }
2038 DefEmitted = true;
2039
2040 // Update LiveVariables' kill info.
2041 if (LV && isKill && !SrcReg.isPhysical())
2042 LV->replaceKillInstruction(SrcReg, MI, *CopyMI);
2043
2044 LLVM_DEBUG(dbgs() << "Inserted: " << *CopyMI);
2045 }
2046
2048 std::next(MachineBasicBlock::iterator(MI));
2049
2050 if (!DefEmitted) {
2051 LLVM_DEBUG(dbgs() << "Turned: " << MI << " into an IMPLICIT_DEF");
2052 MI.setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
2053 for (int j = MI.getNumOperands() - 1, ee = 0; j > ee; --j)
2054 MI.removeOperand(j);
2055 } else {
2056 if (LIS) {
2057 // Force live interval recomputation if we moved to a partial definition
2058 // of the register. Undef flags must be propagate to uses of undefined
2059 // subregister for accurate interval computation.
2060 if (UndefLanes.any() && DefVN && MRI->shouldTrackSubRegLiveness(DstReg)) {
2061 auto &LI = LIS->getInterval(DstReg);
2062 for (MachineOperand &UseOp : MRI->use_operands(DstReg)) {
2063 unsigned SubReg = UseOp.getSubReg();
2064 if (UseOp.isUndef() || !SubReg)
2065 continue;
2066 auto *VN =
2067 LI.getVNInfoAt(LIS->getInstructionIndex(*UseOp.getParent()));
2068 if (DefVN != VN)
2069 continue;
2070 LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
2071 if ((UndefLanes & LaneMask).any())
2072 UseOp.setIsUndef(true);
2073 }
2074 LIS->removeInterval(DstReg);
2075 }
2076 LIS->RemoveMachineInstrFromMaps(MI);
2077 }
2078
2079 LLVM_DEBUG(dbgs() << "Eliminated: " << MI);
2080 MI.eraseFromParent();
2081 }
2082
2083 // Udpate LiveIntervals.
2084 if (LIS)
2085 LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs);
2086}
unsigned SubReg
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator MBBI
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
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:1295
bool End
Definition: ELF_riscv.cpp:480
Rewrite Partial Register Uses
#define DEBUG_TYPE
const HexagonInstrInfo * TII
#define _
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
modulo schedule Modulo Schedule test pass
#define P(N)
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:57
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet 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
static bool isTwoAddrUse(MachineInstr &MI, Register Reg, Register &DstReg)
Return true if the specified MI uses the specified register as a two-address use.
static MCRegister getMappedReg(Register Reg, DenseMap< Register, Register > &RegMap)
Return the physical register the specified virtual register might be mapped to.
static cl::opt< bool > EnableRescheduling("twoaddr-reschedule", cl::desc("Coalesce copies by rescheduling (default=true)"), cl::init(true), cl::Hidden)
static cl::opt< unsigned > MaxDataFlowEdge("dataflow-edge-limit", cl::Hidden, cl::init(3), cl::desc("Maximum number of dataflow edges to traverse when evaluating " "the benefit of commuting operands"))
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:424
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
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:256
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:72
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:178
bool hasOptNone() const
Do not optimize this function (-O0).
Definition: Function.h:699
unsigned getInstrLatency(const InstrItineraryData *ItinData, const MachineInstr &MI, unsigned *PredCost=nullptr) const override
Compute the instruction latency of a given instruction.
Itinerary data supplied by a subtarget to be used by a target.
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:810
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:782
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
Definition: LiveInterval.h:408
VNInfo * createValueCopy(const VNInfo *orig, VNInfo::Allocator &VNInfoAllocator)
Create a copy of the given value.
Definition: LiveInterval.h:349
iterator end()
Definition: LiveInterval.h:216
iterator begin()
Definition: LiveInterval.h:215
bool hasAtLeastOneValue() const
Definition: LiveInterval.h:309
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:421
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
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
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
An RAII based helper class to modify MachineFunctionProperties when running pass.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Analysis pass which computes a MachineDominatorTree.
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...
MachineFunctionProperties & set(Property P)
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
void makeDebugValueSubstitution(DebugInstrOperandPair, DebugInstrOperandPair, unsigned SubReg=0)
Create a substitution between one <instr,operand> value to a different, new value.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineFunctionProperties & getProperties() const
Get the function properties.
const MachineInstrBuilder & add(const MachineOperand &MO) const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
MachineInstrSpan provides an interface to get an iteration range containing the instruction it was in...
Representation of each machine instruction.
Definition: MachineInstr.h:69
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:974
bool isCopy() const
bool isCopyLike() const
Return true if the instruction behaves like a copy.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:950
bool isSafeToMove(bool &SawStore) const
Return true if it is safe to move this instruction.
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:982
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore,...
unsigned getNumExplicitDefs() const
Returns the number of non-implicit definitions.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:685
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:722
unsigned getDebugInstrNum()
Fetch the instruction number of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:579
Analysis pass that exposes the MachineLoopInfo for a machine function.
MachineOperand class - Representation of each machine instruction operand.
void setSubReg(unsigned subReg)
unsigned getSubReg() const
unsigned getOperandNo() const
Returns the index of this operand in the instruction that it belongs to.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
void setReg(Register Reg)
Change the register this operand corresponds to.
void setIsKill(bool Val=true)
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.
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
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...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
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
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:65
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:176
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:224
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:503
bool empty() const
Definition: SmallVector.h:95
size_t size() const
Definition: SmallVector.h:92
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
iterator erase(const_iterator CI)
Definition: SmallVector.h:751
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
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...
PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
unsigned id
The ID number of this value.
Definition: LiveInterval.h:58
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
constexpr bool any(E Val)
Definition: BitmaskEnum.h:141
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ Define
Register definition.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
constexpr double e
Definition: MathExtras.h:47
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
NodeAddr< FuncNode * > Func
Definition: RDFGraph.h:393
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void initializeTwoAddressInstructionLegacyPassPass(PassRegistry &)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2065
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CodeGenOptLevel
Code generation optimization level.
Definition: CodeGen.h:54
char & TwoAddressInstructionPassID
TwoAddressInstruction - This pass reduces two-address instructions to use two operands.
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
constexpr bool none() const
Definition: LaneBitmask.h:52
constexpr bool any() const
Definition: LaneBitmask.h:53
static constexpr LaneBitmask getNone()
Definition: LaneBitmask.h:81
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:78
std::vector< MachineInstr * > Kills
Kills - List of MachineInstruction's which are the last use of this virtual register (kill it) in the...
Definition: LiveVariables.h:88
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:83