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