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