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