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