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