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);
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 = NewMIs[1]->findRegisterDefOperandIdx(regA);
1359 unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB);
1360 MachineBasicBlock::iterator NewMI = NewMIs[1];
1361 bool TransformResult =
1362 tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist, true);
1363 (void)TransformResult;
1364 assert(!TransformResult &&
1365 "tryInstructionTransform() should return false.");
1366 if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) {
1367 // Success, or at least we made an improvement. Keep the unfolded
1368 // instructions and discard the original.
1369 if (LV) {
1370 for (const MachineOperand &MO : MI.operands()) {
1371 if (MO.isReg() && MO.getReg().isVirtual()) {
1372 if (MO.isUse()) {
1373 if (MO.isKill()) {
1374 if (NewMIs[0]->killsRegister(MO.getReg()))
1375 LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[0]);
1376 else {
1377 assert(NewMIs[1]->killsRegister(MO.getReg()) &&
1378 "Kill missing after load unfold!");
1379 LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[1]);
1380 }
1381 }
1382 } else if (LV->removeVirtualRegisterDead(MO.getReg(), MI)) {
1383 if (NewMIs[1]->registerDefIsDead(MO.getReg()))
1384 LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[1]);
1385 else {
1386 assert(NewMIs[0]->registerDefIsDead(MO.getReg()) &&
1387 "Dead flag missing after load unfold!");
1388 LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[0]);
1389 }
1390 }
1391 }
1392 }
1393 LV->addVirtualRegisterKilled(Reg, *NewMIs[1]);
1394 }
1395
1396 SmallVector<Register, 4> OrigRegs;
1397 if (LIS) {
1398 for (const MachineOperand &MO : MI.operands()) {
1399 if (MO.isReg())
1400 OrigRegs.push_back(MO.getReg());
1401 }
1402
1404 }
1405
1406 MI.eraseFromParent();
1407 DistanceMap.erase(&MI);
1408
1409 // Update LiveIntervals.
1410 if (LIS) {
1411 MachineBasicBlock::iterator Begin(NewMIs[0]);
1413 LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs);
1414 }
1415
1416 mi = NewMIs[1];
1417 } else {
1418 // Transforming didn't eliminate the tie and didn't lead to an
1419 // improvement. Clean up the unfolded instructions and keep the
1420 // original.
1421 LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n");
1422 NewMIs[0]->eraseFromParent();
1423 NewMIs[1]->eraseFromParent();
1424 DistanceMap.erase(NewMIs[0]);
1425 DistanceMap.erase(NewMIs[1]);
1426 Dist--;
1427 }
1428 }
1429 }
1430 }
1431
1432 return false;
1433}
1434
1435// Collect tied operands of MI that need to be handled.
1436// Rewrite trivial cases immediately.
1437// Return true if any tied operands where found, including the trivial ones.
1438bool TwoAddressInstructionPass::
1439collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) {
1440 bool AnyOps = false;
1441 unsigned NumOps = MI->getNumOperands();
1442
1443 for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) {
1444 unsigned DstIdx = 0;
1445 if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx))
1446 continue;
1447 AnyOps = true;
1448 MachineOperand &SrcMO = MI->getOperand(SrcIdx);
1449 MachineOperand &DstMO = MI->getOperand(DstIdx);
1450 Register SrcReg = SrcMO.getReg();
1451 Register DstReg = DstMO.getReg();
1452 // Tied constraint already satisfied?
1453 if (SrcReg == DstReg)
1454 continue;
1455
1456 assert(SrcReg && SrcMO.isUse() && "two address instruction invalid");
1457
1458 // Deal with undef uses immediately - simply rewrite the src operand.
1459 if (SrcMO.isUndef() && !DstMO.getSubReg()) {
1460 // Constrain the DstReg register class if required.
1461 if (DstReg.isVirtual()) {
1462 const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
1463 MRI->constrainRegClass(DstReg, RC);
1464 }
1465 SrcMO.setReg(DstReg);
1466 SrcMO.setSubReg(0);
1467 LLVM_DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI);
1468 continue;
1469 }
1470 TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx));
1471 }
1472 return AnyOps;
1473}
1474
1475// Process a list of tied MI operands that all use the same source register.
1476// The tied pairs are of the form (SrcIdx, DstIdx).
1477void
1478TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI,
1479 TiedPairList &TiedPairs,
1480 unsigned &Dist) {
1481 bool IsEarlyClobber = llvm::any_of(TiedPairs, [MI](auto const &TP) {
1482 return MI->getOperand(TP.second).isEarlyClobber();
1483 });
1484
1485 bool RemovedKillFlag = false;
1486 bool AllUsesCopied = true;
1487 unsigned LastCopiedReg = 0;
1488 SlotIndex LastCopyIdx;
1489 Register RegB = 0;
1490 unsigned SubRegB = 0;
1491 for (auto &TP : TiedPairs) {
1492 unsigned SrcIdx = TP.first;
1493 unsigned DstIdx = TP.second;
1494
1495 const MachineOperand &DstMO = MI->getOperand(DstIdx);
1496 Register RegA = DstMO.getReg();
1497
1498 // Grab RegB from the instruction because it may have changed if the
1499 // instruction was commuted.
1500 RegB = MI->getOperand(SrcIdx).getReg();
1501 SubRegB = MI->getOperand(SrcIdx).getSubReg();
1502
1503 if (RegA == RegB) {
1504 // The register is tied to multiple destinations (or else we would
1505 // not have continued this far), but this use of the register
1506 // already matches the tied destination. Leave it.
1507 AllUsesCopied = false;
1508 continue;
1509 }
1510 LastCopiedReg = RegA;
1511
1512 assert(RegB.isVirtual() && "cannot make instruction into two-address form");
1513
1514#ifndef NDEBUG
1515 // First, verify that we don't have a use of "a" in the instruction
1516 // (a = b + a for example) because our transformation will not
1517 // work. This should never occur because we are in SSA form.
1518 for (unsigned i = 0; i != MI->getNumOperands(); ++i)
1519 assert(i == DstIdx ||
1520 !MI->getOperand(i).isReg() ||
1521 MI->getOperand(i).getReg() != RegA);
1522#endif
1523
1524 // Emit a copy.
1525 MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
1526 TII->get(TargetOpcode::COPY), RegA);
1527 // If this operand is folding a truncation, the truncation now moves to the
1528 // copy so that the register classes remain valid for the operands.
1529 MIB.addReg(RegB, 0, SubRegB);
1530 const TargetRegisterClass *RC = MRI->getRegClass(RegB);
1531 if (SubRegB) {
1532 if (RegA.isVirtual()) {
1533 assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA),
1534 SubRegB) &&
1535 "tied subregister must be a truncation");
1536 // The superreg class will not be used to constrain the subreg class.
1537 RC = nullptr;
1538 } else {
1539 assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB))
1540 && "tied subregister must be a truncation");
1541 }
1542 }
1543
1544 // Update DistanceMap.
1546 --PrevMI;
1547 DistanceMap.insert(std::make_pair(&*PrevMI, Dist));
1548 DistanceMap[MI] = ++Dist;
1549
1550 if (LIS) {
1551 LastCopyIdx = LIS->InsertMachineInstrInMaps(*PrevMI).getRegSlot();
1552
1553 SlotIndex endIdx =
1554 LIS->getInstructionIndex(*MI).getRegSlot(IsEarlyClobber);
1555 if (RegA.isVirtual()) {
1556 LiveInterval &LI = LIS->getInterval(RegA);
1557 VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1558 LI.addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1559 for (auto &S : LI.subranges()) {
1560 VNI = S.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1561 S.addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1562 }
1563 } else {
1564 for (MCRegUnit Unit : TRI->regunits(RegA)) {
1565 if (LiveRange *LR = LIS->getCachedRegUnit(Unit)) {
1566 VNInfo *VNI =
1567 LR->getNextValue(LastCopyIdx, LIS->getVNInfoAllocator());
1568 LR->addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI));
1569 }
1570 }
1571 }
1572 }
1573
1574 LLVM_DEBUG(dbgs() << "\t\tprepend:\t" << *MIB);
1575
1576 MachineOperand &MO = MI->getOperand(SrcIdx);
1577 assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() &&
1578 "inconsistent operand info for 2-reg pass");
1579 if (isPlainlyKilled(MO)) {
1580 MO.setIsKill(false);
1581 RemovedKillFlag = true;
1582 }
1583
1584 // Make sure regA is a legal regclass for the SrcIdx operand.
1585 if (RegA.isVirtual() && RegB.isVirtual())
1586 MRI->constrainRegClass(RegA, RC);
1587 MO.setReg(RegA);
1588 // The getMatchingSuper asserts guarantee that the register class projected
1589 // by SubRegB is compatible with RegA with no subregister. So regardless of
1590 // whether the dest oper writes a subreg, the source oper should not.
1591 MO.setSubReg(0);
1592 }
1593
1594 if (AllUsesCopied) {
1595 LaneBitmask RemainingUses = LaneBitmask::getNone();
1596 // Replace other (un-tied) uses of regB with LastCopiedReg.
1597 for (MachineOperand &MO : MI->all_uses()) {
1598 if (MO.getReg() == RegB) {
1599 if (MO.getSubReg() == SubRegB && !IsEarlyClobber) {
1600 if (isPlainlyKilled(MO)) {
1601 MO.setIsKill(false);
1602 RemovedKillFlag = true;
1603 }
1604 MO.setReg(LastCopiedReg);
1605 MO.setSubReg(0);
1606 } else {
1607 RemainingUses |= TRI->getSubRegIndexLaneMask(MO.getSubReg());
1608 }
1609 }
1610 }
1611
1612 // Update live variables for regB.
1613 if (RemovedKillFlag && RemainingUses.none() && LV &&
1614 LV->getVarInfo(RegB).removeKill(*MI)) {
1616 --PrevMI;
1617 LV->addVirtualRegisterKilled(RegB, *PrevMI);
1618 }
1619
1620 if (RemovedKillFlag && RemainingUses.none())
1621 SrcRegMap[LastCopiedReg] = RegB;
1622
1623 // Update LiveIntervals.
1624 if (LIS) {
1625 SlotIndex UseIdx = LIS->getInstructionIndex(*MI);
1626 auto Shrink = [=](LiveRange &LR, LaneBitmask LaneMask) {
1627 LiveRange::Segment *S = LR.getSegmentContaining(LastCopyIdx);
1628 if (!S)
1629 return true;
1630 if ((LaneMask & RemainingUses).any())
1631 return false;
1632 if (S->end.getBaseIndex() != UseIdx)
1633 return false;
1634 S->end = LastCopyIdx;
1635 return true;
1636 };
1637
1638 LiveInterval &LI = LIS->getInterval(RegB);
1639 bool ShrinkLI = true;
1640 for (auto &S : LI.subranges())
1641 ShrinkLI &= Shrink(S, S.LaneMask);
1642 if (ShrinkLI)
1643 Shrink(LI, LaneBitmask::getAll());
1644 }
1645 } else if (RemovedKillFlag) {
1646 // Some tied uses of regB matched their destination registers, so
1647 // regB is still used in this instruction, but a kill flag was
1648 // removed from a different tied use of regB, so now we need to add
1649 // a kill flag to one of the remaining uses of regB.
1650 for (MachineOperand &MO : MI->all_uses()) {
1651 if (MO.getReg() == RegB) {
1652 MO.setIsKill(true);
1653 break;
1654 }
1655 }
1656 }
1657}
1658
1659// For every tied operand pair this function transforms statepoint from
1660// RegA = STATEPOINT ... RegB(tied-def N)
1661// to
1662// RegB = STATEPOINT ... RegB(tied-def N)
1663// and replaces all uses of RegA with RegB.
1664// No extra COPY instruction is necessary because tied use is killed at
1665// STATEPOINT.
1666bool TwoAddressInstructionPass::processStatepoint(
1667 MachineInstr *MI, TiedOperandMap &TiedOperands) {
1668
1669 bool NeedCopy = false;
1670 for (auto &TO : TiedOperands) {
1671 Register RegB = TO.first;
1672 if (TO.second.size() != 1) {
1673 NeedCopy = true;
1674 continue;
1675 }
1676
1677 unsigned SrcIdx = TO.second[0].first;
1678 unsigned DstIdx = TO.second[0].second;
1679
1680 MachineOperand &DstMO = MI->getOperand(DstIdx);
1681 Register RegA = DstMO.getReg();
1682
1683 assert(RegB == MI->getOperand(SrcIdx).getReg());
1684
1685 if (RegA == RegB)
1686 continue;
1687
1688 // CodeGenPrepare can sink pointer compare past statepoint, which
1689 // breaks assumption that statepoint kills tied-use register when
1690 // in SSA form (see note in IR/SafepointIRVerifier.cpp). Fall back
1691 // to generic tied register handling to avoid assertion failures.
1692 // TODO: Recompute LIS/LV information for new range here.
1693 if (LIS) {
1694 const auto &UseLI = LIS->getInterval(RegB);
1695 const auto &DefLI = LIS->getInterval(RegA);
1696 if (DefLI.overlaps(UseLI)) {
1697 LLVM_DEBUG(dbgs() << "LIS: " << printReg(RegB, TRI, 0)
1698 << " UseLI overlaps with DefLI\n");
1699 NeedCopy = true;
1700 continue;
1701 }
1702 } else if (LV && LV->getVarInfo(RegB).findKill(MI->getParent()) != MI) {
1703 // Note that MachineOperand::isKill does not work here, because it
1704 // is set only on first register use in instruction and for statepoint
1705 // tied-use register will usually be found in preceeding deopt bundle.
1706 LLVM_DEBUG(dbgs() << "LV: " << printReg(RegB, TRI, 0)
1707 << " not killed by statepoint\n");
1708 NeedCopy = true;
1709 continue;
1710 }
1711
1712 if (!MRI->constrainRegClass(RegB, MRI->getRegClass(RegA))) {
1713 LLVM_DEBUG(dbgs() << "MRI: couldn't constrain" << printReg(RegB, TRI, 0)
1714 << " to register class of " << printReg(RegA, TRI, 0)
1715 << '\n');
1716 NeedCopy = true;
1717 continue;
1718 }
1719 MRI->replaceRegWith(RegA, RegB);
1720
1721 if (LIS) {
1723 LiveInterval &LI = LIS->getInterval(RegB);
1724 LiveInterval &Other = LIS->getInterval(RegA);
1725 SmallVector<VNInfo *> NewVNIs;
1726 for (const VNInfo *VNI : Other.valnos) {
1727 assert(VNI->id == NewVNIs.size() && "assumed");
1728 NewVNIs.push_back(LI.createValueCopy(VNI, A));
1729 }
1730 for (auto &S : Other) {
1731 VNInfo *VNI = NewVNIs[S.valno->id];
1732 LiveRange::Segment NewSeg(S.start, S.end, VNI);
1733 LI.addSegment(NewSeg);
1734 }
1735 LIS->removeInterval(RegA);
1736 }
1737
1738 if (LV) {
1739 if (MI->getOperand(SrcIdx).isKill())
1740 LV->removeVirtualRegisterKilled(RegB, *MI);
1741 LiveVariables::VarInfo &SrcInfo = LV->getVarInfo(RegB);
1742 LiveVariables::VarInfo &DstInfo = LV->getVarInfo(RegA);
1743 SrcInfo.AliveBlocks |= DstInfo.AliveBlocks;
1744 DstInfo.AliveBlocks.clear();
1745 for (auto *KillMI : DstInfo.Kills)
1746 LV->addVirtualRegisterKilled(RegB, *KillMI, false);
1747 }
1748 }
1749 return !NeedCopy;
1750}
1751
1752/// Reduce two-address instructions to two operands.
1753bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
1754 MF = &Func;
1755 const TargetMachine &TM = MF->getTarget();
1756 MRI = &MF->getRegInfo();
1757 TII = MF->getSubtarget().getInstrInfo();
1759 InstrItins = MF->getSubtarget().getInstrItineraryData();
1760 LV = getAnalysisIfAvailable<LiveVariables>();
1761 LIS = getAnalysisIfAvailable<LiveIntervals>();
1762 if (auto *AAPass = getAnalysisIfAvailable<AAResultsWrapperPass>())
1763 AA = &AAPass->getAAResults();
1764 else
1765 AA = nullptr;
1766 OptLevel = TM.getOptLevel();
1767 // Disable optimizations if requested. We cannot skip the whole pass as some
1768 // fixups are necessary for correctness.
1769 if (skipFunction(Func.getFunction()))
1770 OptLevel = CodeGenOptLevel::None;
1771
1772 bool MadeChange = false;
1773
1774 LLVM_DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n");
1775 LLVM_DEBUG(dbgs() << "********** Function: " << MF->getName() << '\n');
1776
1777 // This pass takes the function out of SSA form.
1778 MRI->leaveSSA();
1779
1780 // This pass will rewrite the tied-def to meet the RegConstraint.
1781 MF->getProperties()
1782 .set(MachineFunctionProperties::Property::TiedOpsRewritten);
1783
1784 TiedOperandMap TiedOperands;
1785 for (MachineBasicBlock &MBBI : *MF) {
1786 MBB = &MBBI;
1787 unsigned Dist = 0;
1788 DistanceMap.clear();
1789 SrcRegMap.clear();
1790 DstRegMap.clear();
1791 Processed.clear();
1792 for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end();
1793 mi != me; ) {
1794 MachineBasicBlock::iterator nmi = std::next(mi);
1795 // Skip debug instructions.
1796 if (mi->isDebugInstr()) {
1797 mi = nmi;
1798 continue;
1799 }
1800
1801 // Expand REG_SEQUENCE instructions. This will position mi at the first
1802 // expanded instruction.
1803 if (mi->isRegSequence())
1804 eliminateRegSequence(mi);
1805
1806 DistanceMap.insert(std::make_pair(&*mi, ++Dist));
1807
1808 processCopy(&*mi);
1809
1810 // First scan through all the tied register uses in this instruction
1811 // and record a list of pairs of tied operands for each register.
1812 if (!collectTiedOperands(&*mi, TiedOperands)) {
1813 removeClobberedSrcRegMap(&*mi);
1814 mi = nmi;
1815 continue;
1816 }
1817
1818 ++NumTwoAddressInstrs;
1819 MadeChange = true;
1820 LLVM_DEBUG(dbgs() << '\t' << *mi);
1821
1822 // If the instruction has a single pair of tied operands, try some
1823 // transformations that may either eliminate the tied operands or
1824 // improve the opportunities for coalescing away the register copy.
1825 if (TiedOperands.size() == 1) {
1827 = TiedOperands.begin()->second;
1828 if (TiedPairs.size() == 1) {
1829 unsigned SrcIdx = TiedPairs[0].first;
1830 unsigned DstIdx = TiedPairs[0].second;
1831 Register SrcReg = mi->getOperand(SrcIdx).getReg();
1832 Register DstReg = mi->getOperand(DstIdx).getReg();
1833 if (SrcReg != DstReg &&
1834 tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) {
1835 // The tied operands have been eliminated or shifted further down
1836 // the block to ease elimination. Continue processing with 'nmi'.
1837 TiedOperands.clear();
1838 removeClobberedSrcRegMap(&*mi);
1839 mi = nmi;
1840 continue;
1841 }
1842 }
1843 }
1844
1845 if (mi->getOpcode() == TargetOpcode::STATEPOINT &&
1846 processStatepoint(&*mi, TiedOperands)) {
1847 TiedOperands.clear();
1848 LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1849 mi = nmi;
1850 continue;
1851 }
1852
1853 // Now iterate over the information collected above.
1854 for (auto &TO : TiedOperands) {
1855 processTiedPairs(&*mi, TO.second, Dist);
1856 LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi);
1857 }
1858
1859 // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form.
1860 if (mi->isInsertSubreg()) {
1861 // From %reg = INSERT_SUBREG %reg, %subreg, subidx
1862 // To %reg:subidx = COPY %subreg
1863 unsigned SubIdx = mi->getOperand(3).getImm();
1864 mi->removeOperand(3);
1865 assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
1866 mi->getOperand(0).setSubReg(SubIdx);
1867 mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef());
1868 mi->removeOperand(1);
1869 mi->setDesc(TII->get(TargetOpcode::COPY));
1870 LLVM_DEBUG(dbgs() << "\t\tconvert to:\t" << *mi);
1871
1872 // Update LiveIntervals.
1873 if (LIS) {
1874 Register Reg = mi->getOperand(0).getReg();
1875 LiveInterval &LI = LIS->getInterval(Reg);
1876 if (LI.hasSubRanges()) {
1877 // The COPY no longer defines subregs of %reg except for
1878 // %reg.subidx.
1879 LaneBitmask LaneMask =
1880 TRI->getSubRegIndexLaneMask(mi->getOperand(0).getSubReg());
1882 for (auto &S : LI.subranges()) {
1883 if ((S.LaneMask & LaneMask).none()) {
1884 LiveRange::iterator DefSeg = S.FindSegmentContaining(Idx);
1885 if (mi->getOperand(0).isUndef()) {
1886 S.removeValNo(DefSeg->valno);
1887 } else {
1888 LiveRange::iterator UseSeg = std::prev(DefSeg);
1889 S.MergeValueNumberInto(DefSeg->valno, UseSeg->valno);
1890 }
1891 }
1892 }
1893
1894 // The COPY no longer has a use of %reg.
1895 LIS->shrinkToUses(&LI);
1896 } else {
1897 // The live interval for Reg did not have subranges but now it needs
1898 // them because we have introduced a subreg def. Recompute it.
1899 LIS->removeInterval(Reg);
1901 }
1902 }
1903 }
1904
1905 // Clear TiedOperands here instead of at the top of the loop
1906 // since most instructions do not have tied operands.
1907 TiedOperands.clear();
1908 removeClobberedSrcRegMap(&*mi);
1909 mi = nmi;
1910 }
1911 }
1912
1913 return MadeChange;
1914}
1915
1916/// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process.
1917///
1918/// The instruction is turned into a sequence of sub-register copies:
1919///
1920/// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1
1921///
1922/// Becomes:
1923///
1924/// undef %dst:ssub0 = COPY %v1
1925/// %dst:ssub1 = COPY %v2
1926void TwoAddressInstructionPass::
1927eliminateRegSequence(MachineBasicBlock::iterator &MBBI) {
1928 MachineInstr &MI = *MBBI;
1929 Register DstReg = MI.getOperand(0).getReg();
1930
1931 SmallVector<Register, 4> OrigRegs;
1932 VNInfo *DefVN = nullptr;
1933 if (LIS) {
1934 OrigRegs.push_back(MI.getOperand(0).getReg());
1935 for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2)
1936 OrigRegs.push_back(MI.getOperand(i).getReg());
1937 if (LIS->hasInterval(DstReg)) {
1938 DefVN = LIS->getInterval(DstReg)
1940 .valueOut();
1941 }
1942 }
1943
1944 LaneBitmask UndefLanes = LaneBitmask::getNone();
1945 bool DefEmitted = false;
1946 for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) {
1947 MachineOperand &UseMO = MI.getOperand(i);
1948 Register SrcReg = UseMO.getReg();
1949 unsigned SubIdx = MI.getOperand(i+1).getImm();
1950 // Nothing needs to be inserted for undef operands.
1951 if (UseMO.isUndef()) {
1952 UndefLanes |= TRI->getSubRegIndexLaneMask(SubIdx);
1953 continue;
1954 }
1955
1956 // Defer any kill flag to the last operand using SrcReg. Otherwise, we
1957 // might insert a COPY that uses SrcReg after is was killed.
1958 bool isKill = UseMO.isKill();
1959 if (isKill)
1960 for (unsigned j = i + 2; j < e; j += 2)
1961 if (MI.getOperand(j).getReg() == SrcReg) {
1962 MI.getOperand(j).setIsKill();
1963 UseMO.setIsKill(false);
1964 isKill = false;
1965 break;
1966 }
1967
1968 // Insert the sub-register copy.
1969 MachineInstr *CopyMI = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(),
1970 TII->get(TargetOpcode::COPY))
1971 .addReg(DstReg, RegState::Define, SubIdx)
1972 .add(UseMO);
1973
1974 // The first def needs an undef flag because there is no live register
1975 // before it.
1976 if (!DefEmitted) {
1977 CopyMI->getOperand(0).setIsUndef(true);
1978 // Return an iterator pointing to the first inserted instr.
1979 MBBI = CopyMI;
1980 }
1981 DefEmitted = true;
1982
1983 // Update LiveVariables' kill info.
1984 if (LV && isKill && !SrcReg.isPhysical())
1985 LV->replaceKillInstruction(SrcReg, MI, *CopyMI);
1986
1987 LLVM_DEBUG(dbgs() << "Inserted: " << *CopyMI);
1988 }
1989
1991 std::next(MachineBasicBlock::iterator(MI));
1992
1993 if (!DefEmitted) {
1994 LLVM_DEBUG(dbgs() << "Turned: " << MI << " into an IMPLICIT_DEF");
1995 MI.setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1996 for (int j = MI.getNumOperands() - 1, ee = 0; j > ee; --j)
1997 MI.removeOperand(j);
1998 } else {
1999 if (LIS) {
2000 // Force live interval recomputation if we moved to a partial definition
2001 // of the register. Undef flags must be propagate to uses of undefined
2002 // subregister for accurate interval computation.
2003 if (UndefLanes.any() && DefVN && MRI->shouldTrackSubRegLiveness(DstReg)) {
2004 auto &LI = LIS->getInterval(DstReg);
2005 for (MachineOperand &UseOp : MRI->use_operands(DstReg)) {
2006 unsigned SubReg = UseOp.getSubReg();
2007 if (UseOp.isUndef() || !SubReg)
2008 continue;
2009 auto *VN =
2010 LI.getVNInfoAt(LIS->getInstructionIndex(*UseOp.getParent()));
2011 if (DefVN != VN)
2012 continue;
2013 LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
2014 if ((UndefLanes & LaneMask).any())
2015 UseOp.setIsUndef(true);
2016 }
2017 LIS->removeInterval(DstReg);
2018 }
2020 }
2021
2022 LLVM_DEBUG(dbgs() << "Eliminated: " << MI);
2023 MI.eraseFromParent();
2024 }
2025
2026 // Udpate LiveIntervals.
2027 if (LIS)
2028 LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs);
2029}
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:1291
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:329
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:942
bool isCopy() const
bool isCopyLike() const
Return true if the instruction behaves like a copy.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:918
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:950
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:662
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:699
unsigned getDebugInstrNum()
Fetch the instruction number of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:556
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:76
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:450
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:1731
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.
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
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:2068
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:1738
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.