1327952Sdim//===- TwoAddressInstructionPass.cpp - Two-Address instruction pass -------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This file implements the TwoAddress instruction pass which is used 10193323Sed// by most register allocators. Two-Address instructions are rewritten 11193323Sed// from: 12193323Sed// 13193323Sed// A = B op C 14193323Sed// 15193323Sed// to: 16193323Sed// 17193323Sed// A = B 18193323Sed// A op= C 19193323Sed// 20193323Sed// Note that if a register allocator chooses to use this pass, that it 21193323Sed// has to be capable of handling the non-SSA nature of these rewritten 22193323Sed// virtual registers. 23193323Sed// 24193323Sed// It is also worth noting that the duplicate operand of the two 25193323Sed// address instruction is removed. 26193323Sed// 27193323Sed//===----------------------------------------------------------------------===// 28193323Sed 29249423Sdim#include "llvm/ADT/DenseMap.h" 30327952Sdim#include "llvm/ADT/SmallPtrSet.h" 31327952Sdim#include "llvm/ADT/SmallSet.h" 32309124Sdim#include "llvm/ADT/SmallVector.h" 33249423Sdim#include "llvm/ADT/Statistic.h" 34327952Sdim#include "llvm/ADT/iterator_range.h" 35249423Sdim#include "llvm/Analysis/AliasAnalysis.h" 36327952Sdim#include "llvm/CodeGen/LiveInterval.h" 37327952Sdim#include "llvm/CodeGen/LiveIntervals.h" 38193323Sed#include "llvm/CodeGen/LiveVariables.h" 39327952Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 40327952Sdim#include "llvm/CodeGen/MachineFunction.h" 41193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 42193323Sed#include "llvm/CodeGen/MachineInstr.h" 43210299Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 44327952Sdim#include "llvm/CodeGen/MachineOperand.h" 45193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 46309124Sdim#include "llvm/CodeGen/Passes.h" 47327952Sdim#include "llvm/CodeGen/SlotIndexes.h" 48327952Sdim#include "llvm/CodeGen/TargetInstrInfo.h" 49327952Sdim#include "llvm/CodeGen/TargetOpcodes.h" 50327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 51327952Sdim#include "llvm/CodeGen/TargetSubtargetInfo.h" 52327952Sdim#include "llvm/MC/MCInstrDesc.h" 53234353Sdim#include "llvm/MC/MCInstrItineraries.h" 54327952Sdim#include "llvm/Pass.h" 55327952Sdim#include "llvm/Support/CodeGen.h" 56251662Sdim#include "llvm/Support/CommandLine.h" 57249423Sdim#include "llvm/Support/Debug.h" 58249423Sdim#include "llvm/Support/ErrorHandling.h" 59288943Sdim#include "llvm/Support/raw_ostream.h" 60193323Sed#include "llvm/Target/TargetMachine.h" 61327952Sdim#include <cassert> 62327952Sdim#include <iterator> 63327952Sdim#include <utility> 64309124Sdim 65193323Sedusing namespace llvm; 66193323Sed 67321369Sdim#define DEBUG_TYPE "twoaddressinstruction" 68276479Sdim 69193323SedSTATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); 70193323SedSTATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); 71193323SedSTATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted"); 72193323SedSTATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); 73193323SedSTATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); 74234353SdimSTATISTIC(NumReSchedUps, "Number of instructions re-scheduled up"); 75234353SdimSTATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down"); 76193323Sed 77251662Sdim// Temporary flag to disable rescheduling. 78251662Sdimstatic cl::opt<bool> 79251662SdimEnableRescheduling("twoaddr-reschedule", 80251662Sdim cl::desc("Coalesce copies by rescheduling (default=true)"), 81251662Sdim cl::init(true), cl::Hidden); 82251662Sdim 83321369Sdim// Limit the number of dataflow edges to traverse when evaluating the benefit 84321369Sdim// of commuting operands. 85321369Sdimstatic cl::opt<unsigned> MaxDataFlowEdge( 86321369Sdim "dataflow-edge-limit", cl::Hidden, cl::init(3), 87321369Sdim cl::desc("Maximum number of dataflow edges to traverse when evaluating " 88321369Sdim "the benefit of commuting operands")); 89321369Sdim 90193323Sednamespace { 91327952Sdim 92243830Sdimclass TwoAddressInstructionPass : public MachineFunctionPass { 93243830Sdim MachineFunction *MF; 94243830Sdim const TargetInstrInfo *TII; 95243830Sdim const TargetRegisterInfo *TRI; 96243830Sdim const InstrItineraryData *InstrItins; 97243830Sdim MachineRegisterInfo *MRI; 98243830Sdim LiveVariables *LV; 99243830Sdim LiveIntervals *LIS; 100243830Sdim AliasAnalysis *AA; 101243830Sdim CodeGenOpt::Level OptLevel; 102193323Sed 103243830Sdim // The current basic block being processed. 104243830Sdim MachineBasicBlock *MBB; 105193323Sed 106296417Sdim // Keep track the distance of a MI from the start of the current basic block. 107243830Sdim DenseMap<MachineInstr*, unsigned> DistanceMap; 108193323Sed 109243830Sdim // Set of already processed instructions in the current block. 110243830Sdim SmallPtrSet<MachineInstr*, 8> Processed; 111193323Sed 112327952Sdim // Set of instructions converted to three-address by target and then sunk 113327952Sdim // down current basic block. 114327952Sdim SmallPtrSet<MachineInstr*, 8> SunkInstrs; 115327952Sdim 116296417Sdim // A map from virtual registers to physical registers which are likely targets 117296417Sdim // to be coalesced to due to copies from physical registers to virtual 118296417Sdim // registers. e.g. v1024 = move r0. 119243830Sdim DenseMap<unsigned, unsigned> SrcRegMap; 120208599Srdivacky 121296417Sdim // A map from virtual registers to physical registers which are likely targets 122296417Sdim // to be coalesced to due to copies to physical registers from virtual 123296417Sdim // registers. e.g. r1 = move v1024. 124243830Sdim DenseMap<unsigned, unsigned> DstRegMap; 125193323Sed 126243830Sdim bool sink3AddrInstruction(MachineInstr *MI, unsigned Reg, 127243830Sdim MachineBasicBlock::iterator OldPos); 128193323Sed 129288943Sdim bool isRevCopyChain(unsigned FromReg, unsigned ToReg, int Maxlen); 130288943Sdim 131243830Sdim bool noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef); 132193323Sed 133243830Sdim bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, 134243830Sdim MachineInstr *MI, unsigned Dist); 135193323Sed 136314564Sdim bool commuteInstruction(MachineInstr *MI, unsigned DstIdx, 137296417Sdim unsigned RegBIdx, unsigned RegCIdx, unsigned Dist); 138193323Sed 139243830Sdim bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB); 140234353Sdim 141243830Sdim bool convertInstTo3Addr(MachineBasicBlock::iterator &mi, 142243830Sdim MachineBasicBlock::iterator &nmi, 143243830Sdim unsigned RegA, unsigned RegB, unsigned Dist); 144234353Sdim 145243830Sdim bool isDefTooClose(unsigned Reg, unsigned Dist, MachineInstr *MI); 146198090Srdivacky 147243830Sdim bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, 148243830Sdim MachineBasicBlock::iterator &nmi, 149243830Sdim unsigned Reg); 150243830Sdim bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, 151243830Sdim MachineBasicBlock::iterator &nmi, 152243830Sdim unsigned Reg); 153221345Sdim 154243830Sdim bool tryInstructionTransform(MachineBasicBlock::iterator &mi, 155243830Sdim MachineBasicBlock::iterator &nmi, 156243830Sdim unsigned SrcIdx, unsigned DstIdx, 157249423Sdim unsigned Dist, bool shouldOnlyCommute); 158198090Srdivacky 159296417Sdim bool tryInstructionCommute(MachineInstr *MI, 160296417Sdim unsigned DstOpIdx, 161296417Sdim unsigned BaseOpIdx, 162296417Sdim bool BaseOpKilled, 163296417Sdim unsigned Dist); 164243830Sdim void scanUses(unsigned DstReg); 165239462Sdim 166243830Sdim void processCopy(MachineInstr *MI); 167208599Srdivacky 168327952Sdim using TiedPairList = SmallVector<std::pair<unsigned, unsigned>, 4>; 169327952Sdim using TiedOperandMap = SmallDenseMap<unsigned, TiedPairList>; 170327952Sdim 171243830Sdim bool collectTiedOperands(MachineInstr *MI, TiedOperandMap&); 172243830Sdim void processTiedPairs(MachineInstr *MI, TiedPairList&, unsigned &Dist); 173249423Sdim void eliminateRegSequence(MachineBasicBlock::iterator&); 174208599Srdivacky 175243830Sdimpublic: 176243830Sdim static char ID; // Pass identification, replacement for typeid 177327952Sdim 178243830Sdim TwoAddressInstructionPass() : MachineFunctionPass(ID) { 179243830Sdim initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry()); 180243830Sdim } 181193323Sed 182276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 183243830Sdim AU.setPreservesCFG(); 184321369Sdim AU.addUsedIfAvailable<AAResultsWrapperPass>(); 185309124Sdim AU.addUsedIfAvailable<LiveVariables>(); 186243830Sdim AU.addPreserved<LiveVariables>(); 187243830Sdim AU.addPreserved<SlotIndexes>(); 188243830Sdim AU.addPreserved<LiveIntervals>(); 189243830Sdim AU.addPreservedID(MachineLoopInfoID); 190243830Sdim AU.addPreservedID(MachineDominatorsID); 191243830Sdim MachineFunctionPass::getAnalysisUsage(AU); 192243830Sdim } 193193323Sed 194296417Sdim /// Pass entry point. 195276479Sdim bool runOnMachineFunction(MachineFunction&) override; 196243830Sdim}; 197327952Sdim 198243830Sdim} // end anonymous namespace 199243830Sdim 200193323Sedchar TwoAddressInstructionPass::ID = 0; 201327952Sdim 202327952Sdimchar &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID; 203327952Sdim 204321369SdimINITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, DEBUG_TYPE, 205218893Sdim "Two-Address instruction pass", false, false) 206296417SdimINITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 207321369SdimINITIALIZE_PASS_END(TwoAddressInstructionPass, DEBUG_TYPE, 208218893Sdim "Two-Address instruction pass", false, false) 209193323Sed 210249423Sdimstatic bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, LiveIntervals *LIS); 211249423Sdim 212296417Sdim/// A two-address instruction has been converted to a three-address instruction 213296417Sdim/// to avoid clobbering a register. Try to sink it past the instruction that 214296417Sdim/// would kill the above mentioned register to reduce register pressure. 215243830Sdimbool TwoAddressInstructionPass:: 216243830Sdimsink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, 217243830Sdim MachineBasicBlock::iterator OldPos) { 218226633Sdim // FIXME: Shouldn't we be trying to do this before we three-addressify the 219226633Sdim // instruction? After this transformation is done, we no longer need 220226633Sdim // the instruction to be in three-address form. 221226633Sdim 222193323Sed // Check if it's safe to move this instruction. 223193323Sed bool SeenStore = true; // Be conservative. 224288943Sdim if (!MI->isSafeToMove(AA, SeenStore)) 225193323Sed return false; 226193323Sed 227193323Sed unsigned DefReg = 0; 228193323Sed SmallSet<unsigned, 4> UseRegs; 229193323Sed 230296417Sdim for (const MachineOperand &MO : MI->operands()) { 231193323Sed if (!MO.isReg()) 232193323Sed continue; 233360784Sdim Register MOReg = MO.getReg(); 234193323Sed if (!MOReg) 235193323Sed continue; 236193323Sed if (MO.isUse() && MOReg != SavedReg) 237193323Sed UseRegs.insert(MO.getReg()); 238193323Sed if (!MO.isDef()) 239193323Sed continue; 240193323Sed if (MO.isImplicit()) 241193323Sed // Don't try to move it if it implicitly defines a register. 242193323Sed return false; 243193323Sed if (DefReg) 244193323Sed // For now, don't move any instructions that define multiple registers. 245193323Sed return false; 246193323Sed DefReg = MO.getReg(); 247193323Sed } 248193323Sed 249193323Sed // Find the instruction that kills SavedReg. 250276479Sdim MachineInstr *KillMI = nullptr; 251249423Sdim if (LIS) { 252249423Sdim LiveInterval &LI = LIS->getInterval(SavedReg); 253249423Sdim assert(LI.end() != LI.begin() && 254249423Sdim "Reg should not have empty live interval."); 255249423Sdim 256249423Sdim SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 257249423Sdim LiveInterval::const_iterator I = LI.find(MBBEndIdx); 258249423Sdim if (I != LI.end() && I->start < MBBEndIdx) 259249423Sdim return false; 260249423Sdim 261249423Sdim --I; 262249423Sdim KillMI = LIS->getInstructionFromIndex(I->end); 263193323Sed } 264249423Sdim if (!KillMI) { 265296417Sdim for (MachineOperand &UseMO : MRI->use_nodbg_operands(SavedReg)) { 266249423Sdim if (!UseMO.isKill()) 267249423Sdim continue; 268249423Sdim KillMI = UseMO.getParent(); 269249423Sdim break; 270249423Sdim } 271249423Sdim } 272193323Sed 273226633Sdim // If we find the instruction that kills SavedReg, and it is in an 274226633Sdim // appropriate location, we can try to sink the current instruction 275226633Sdim // past it. 276226633Sdim if (!KillMI || KillMI->getParent() != MBB || KillMI == MI || 277309124Sdim MachineBasicBlock::iterator(KillMI) == OldPos || KillMI->isTerminator()) 278193323Sed return false; 279193323Sed 280193323Sed // If any of the definitions are used by another instruction between the 281193323Sed // position and the kill use, then it's not safe to sink it. 282234353Sdim // 283193323Sed // FIXME: This can be sped up if there is an easy way to query whether an 284193323Sed // instruction is before or after another instruction. Then we can use 285193323Sed // MachineRegisterInfo def / use instead. 286276479Sdim MachineOperand *KillMO = nullptr; 287193323Sed MachineBasicBlock::iterator KillPos = KillMI; 288193323Sed ++KillPos; 289193323Sed 290193323Sed unsigned NumVisited = 0; 291327952Sdim for (MachineInstr &OtherMI : make_range(std::next(OldPos), KillPos)) { 292341825Sdim // Debug instructions cannot be counted against the limit. 293341825Sdim if (OtherMI.isDebugInstr()) 294203954Srdivacky continue; 295193323Sed if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost. 296193323Sed return false; 297193323Sed ++NumVisited; 298309124Sdim for (unsigned i = 0, e = OtherMI.getNumOperands(); i != e; ++i) { 299309124Sdim MachineOperand &MO = OtherMI.getOperand(i); 300193323Sed if (!MO.isReg()) 301193323Sed continue; 302360784Sdim Register MOReg = MO.getReg(); 303193323Sed if (!MOReg) 304193323Sed continue; 305193323Sed if (DefReg == MOReg) 306193323Sed return false; 307193323Sed 308309124Sdim if (MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS))) { 309309124Sdim if (&OtherMI == KillMI && MOReg == SavedReg) 310193323Sed // Save the operand that kills the register. We want to unset the kill 311193323Sed // marker if we can sink MI past it. 312193323Sed KillMO = &MO; 313193323Sed else if (UseRegs.count(MOReg)) 314193323Sed // One of the uses is killed before the destination. 315193323Sed return false; 316193323Sed } 317193323Sed } 318193323Sed } 319239462Sdim assert(KillMO && "Didn't find kill"); 320193323Sed 321249423Sdim if (!LIS) { 322249423Sdim // Update kill and LV information. 323249423Sdim KillMO->setIsKill(false); 324249423Sdim KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); 325249423Sdim KillMO->setIsKill(true); 326234353Sdim 327249423Sdim if (LV) 328309124Sdim LV->replaceKillInstruction(SavedReg, *KillMI, *MI); 329249423Sdim } 330193323Sed 331193323Sed // Move instruction to its destination. 332193323Sed MBB->remove(MI); 333193323Sed MBB->insert(KillPos, MI); 334193323Sed 335239462Sdim if (LIS) 336309124Sdim LIS->handleMove(*MI); 337239462Sdim 338193323Sed ++Num3AddrSunk; 339193323Sed return true; 340193323Sed} 341193323Sed 342296417Sdim/// Return the MachineInstr* if it is the single def of the Reg in current BB. 343288943Sdimstatic MachineInstr *getSingleDef(unsigned Reg, MachineBasicBlock *BB, 344288943Sdim const MachineRegisterInfo *MRI) { 345288943Sdim MachineInstr *Ret = nullptr; 346288943Sdim for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { 347288943Sdim if (DefMI.getParent() != BB || DefMI.isDebugValue()) 348288943Sdim continue; 349288943Sdim if (!Ret) 350288943Sdim Ret = &DefMI; 351288943Sdim else if (Ret != &DefMI) 352288943Sdim return nullptr; 353288943Sdim } 354288943Sdim return Ret; 355288943Sdim} 356288943Sdim 357288943Sdim/// Check if there is a reversed copy chain from FromReg to ToReg: 358288943Sdim/// %Tmp1 = copy %Tmp2; 359288943Sdim/// %FromReg = copy %Tmp1; 360288943Sdim/// %ToReg = add %FromReg ... 361288943Sdim/// %Tmp2 = copy %ToReg; 362288943Sdim/// MaxLen specifies the maximum length of the copy chain the func 363288943Sdim/// can walk through. 364288943Sdimbool TwoAddressInstructionPass::isRevCopyChain(unsigned FromReg, unsigned ToReg, 365288943Sdim int Maxlen) { 366288943Sdim unsigned TmpReg = FromReg; 367288943Sdim for (int i = 0; i < Maxlen; i++) { 368288943Sdim MachineInstr *Def = getSingleDef(TmpReg, MBB, MRI); 369288943Sdim if (!Def || !Def->isCopy()) 370288943Sdim return false; 371288943Sdim 372288943Sdim TmpReg = Def->getOperand(1).getReg(); 373288943Sdim 374288943Sdim if (TmpReg == ToReg) 375288943Sdim return true; 376288943Sdim } 377288943Sdim return false; 378288943Sdim} 379288943Sdim 380296417Sdim/// Return true if there are no intervening uses between the last instruction 381296417Sdim/// in the MBB that defines the specified register and the two-address 382296417Sdim/// instruction which is being processed. It also returns the last def location 383296417Sdim/// by reference. 384243830Sdimbool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist, 385243830Sdim unsigned &LastDef) { 386193323Sed LastDef = 0; 387193323Sed unsigned LastUse = Dist; 388276479Sdim for (MachineOperand &MO : MRI->reg_operands(Reg)) { 389193323Sed MachineInstr *MI = MO.getParent(); 390203954Srdivacky if (MI->getParent() != MBB || MI->isDebugValue()) 391193323Sed continue; 392193323Sed DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 393193323Sed if (DI == DistanceMap.end()) 394193323Sed continue; 395193323Sed if (MO.isUse() && DI->second < LastUse) 396193323Sed LastUse = DI->second; 397193323Sed if (MO.isDef() && DI->second > LastDef) 398193323Sed LastDef = DI->second; 399193323Sed } 400193323Sed 401193323Sed return !(LastUse > LastDef && LastUse < Dist); 402193323Sed} 403193323Sed 404296417Sdim/// Return true if the specified MI is a copy instruction or an extract_subreg 405296417Sdim/// instruction. It also returns the source and destination registers and 406296417Sdim/// whether they are physical registers by reference. 407193323Sedstatic bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, 408193323Sed unsigned &SrcReg, unsigned &DstReg, 409193323Sed bool &IsSrcPhys, bool &IsDstPhys) { 410193323Sed SrcReg = 0; 411193323Sed DstReg = 0; 412212904Sdim if (MI.isCopy()) { 413212904Sdim DstReg = MI.getOperand(0).getReg(); 414212904Sdim SrcReg = MI.getOperand(1).getReg(); 415212904Sdim } else if (MI.isInsertSubreg() || MI.isSubregToReg()) { 416212904Sdim DstReg = MI.getOperand(0).getReg(); 417212904Sdim SrcReg = MI.getOperand(2).getReg(); 418212904Sdim } else 419212904Sdim return false; 420193323Sed 421360784Sdim IsSrcPhys = Register::isPhysicalRegister(SrcReg); 422360784Sdim IsDstPhys = Register::isPhysicalRegister(DstReg); 423212904Sdim return true; 424193323Sed} 425193323Sed 426296417Sdim/// Test if the given register value, which is used by the 427296417Sdim/// given instruction, is killed by the given instruction. 428249423Sdimstatic bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, 429249423Sdim LiveIntervals *LIS) { 430360784Sdim if (LIS && Register::isVirtualRegister(Reg) && !LIS->isNotInMIMap(*MI)) { 431249423Sdim // FIXME: Sometimes tryInstructionTransform() will add instructions and 432249423Sdim // test whether they can be folded before keeping them. In this case it 433249423Sdim // sets a kill before recursively calling tryInstructionTransform() again. 434249423Sdim // If there is no interval available, we assume that this instruction is 435249423Sdim // one of those. A kill flag is manually inserted on the operand so the 436249423Sdim // check below will handle it. 437249423Sdim LiveInterval &LI = LIS->getInterval(Reg); 438249423Sdim // This is to match the kill flag version where undefs don't have kill 439249423Sdim // flags. 440249423Sdim if (!LI.hasAtLeastOneValue()) 441249423Sdim return false; 442249423Sdim 443309124Sdim SlotIndex useIdx = LIS->getInstructionIndex(*MI); 444249423Sdim LiveInterval::const_iterator I = LI.find(useIdx); 445249423Sdim assert(I != LI.end() && "Reg must be live-in to use."); 446249423Sdim return !I->end.isBlock() && SlotIndex::isSameInstr(I->end, useIdx); 447249423Sdim } 448249423Sdim 449249423Sdim return MI->killsRegister(Reg); 450249423Sdim} 451249423Sdim 452296417Sdim/// Test if the given register value, which is used by the given 453193323Sed/// instruction, is killed by the given instruction. This looks through 454193323Sed/// coalescable copies to see if the original value is potentially not killed. 455193323Sed/// 456193323Sed/// For example, in this code: 457193323Sed/// 458193323Sed/// %reg1034 = copy %reg1024 459327952Sdim/// %reg1035 = copy killed %reg1025 460327952Sdim/// %reg1036 = add killed %reg1034, killed %reg1035 461193323Sed/// 462193323Sed/// %reg1034 is not considered to be killed, since it is copied from a 463193323Sed/// register which is not killed. Treating it as not killed lets the 464193323Sed/// normal heuristics commute the (two-address) add, which lets 465193323Sed/// coalescing eliminate the extra copy. 466193323Sed/// 467249423Sdim/// If allowFalsePositives is true then likely kills are treated as kills even 468249423Sdim/// if it can't be proven that they are kills. 469193323Sedstatic bool isKilled(MachineInstr &MI, unsigned Reg, 470193323Sed const MachineRegisterInfo *MRI, 471249423Sdim const TargetInstrInfo *TII, 472249423Sdim LiveIntervals *LIS, 473249423Sdim bool allowFalsePositives) { 474193323Sed MachineInstr *DefMI = &MI; 475327952Sdim while (true) { 476249423Sdim // All uses of physical registers are likely to be kills. 477360784Sdim if (Register::isPhysicalRegister(Reg) && 478249423Sdim (allowFalsePositives || MRI->hasOneUse(Reg))) 479249423Sdim return true; 480249423Sdim if (!isPlainlyKilled(DefMI, Reg, LIS)) 481193323Sed return false; 482360784Sdim if (Register::isPhysicalRegister(Reg)) 483193323Sed return true; 484193323Sed MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); 485193323Sed // If there are multiple defs, we can't do a simple analysis, so just 486193323Sed // go with what the kill flag says. 487276479Sdim if (std::next(Begin) != MRI->def_end()) 488193323Sed return true; 489276479Sdim DefMI = Begin->getParent(); 490193323Sed bool IsSrcPhys, IsDstPhys; 491193323Sed unsigned SrcReg, DstReg; 492193323Sed // If the def is something other than a copy, then it isn't going to 493193323Sed // be coalesced, so follow the kill flag. 494193323Sed if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 495193323Sed return true; 496193323Sed Reg = SrcReg; 497193323Sed } 498193323Sed} 499193323Sed 500296417Sdim/// Return true if the specified MI uses the specified register as a two-address 501296417Sdim/// use. If so, return the destination register by reference. 502193323Sedstatic bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { 503251662Sdim for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) { 504193323Sed const MachineOperand &MO = MI.getOperand(i); 505193323Sed if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) 506193323Sed continue; 507193323Sed unsigned ti; 508193323Sed if (MI.isRegTiedToDefOperand(i, &ti)) { 509193323Sed DstReg = MI.getOperand(ti).getReg(); 510193323Sed return true; 511193323Sed } 512193323Sed } 513193323Sed return false; 514193323Sed} 515193323Sed 516296417Sdim/// Given a register, if has a single in-basic block use, return the use 517296417Sdim/// instruction if it's a copy or a two-address use. 518193323Sedstatic 519193323SedMachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, 520193323Sed MachineRegisterInfo *MRI, 521193323Sed const TargetInstrInfo *TII, 522193323Sed bool &IsCopy, 523193323Sed unsigned &DstReg, bool &IsDstPhys) { 524204792Srdivacky if (!MRI->hasOneNonDBGUse(Reg)) 525204792Srdivacky // None or more than one use. 526276479Sdim return nullptr; 527276479Sdim MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(Reg); 528193323Sed if (UseMI.getParent() != MBB) 529276479Sdim return nullptr; 530193323Sed unsigned SrcReg; 531193323Sed bool IsSrcPhys; 532193323Sed if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) { 533193323Sed IsCopy = true; 534193323Sed return &UseMI; 535193323Sed } 536193323Sed IsDstPhys = false; 537193323Sed if (isTwoAddrUse(UseMI, Reg, DstReg)) { 538360784Sdim IsDstPhys = Register::isPhysicalRegister(DstReg); 539193323Sed return &UseMI; 540193323Sed } 541276479Sdim return nullptr; 542193323Sed} 543193323Sed 544296417Sdim/// Return the physical register the specified virtual register might be mapped 545296417Sdim/// to. 546193323Sedstatic unsigned 547193323SedgetMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) { 548360784Sdim while (Register::isVirtualRegister(Reg)) { 549193323Sed DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg); 550193323Sed if (SI == RegMap.end()) 551193323Sed return 0; 552193323Sed Reg = SI->second; 553193323Sed } 554360784Sdim if (Register::isPhysicalRegister(Reg)) 555193323Sed return Reg; 556193323Sed return 0; 557193323Sed} 558193323Sed 559296417Sdim/// Return true if the two registers are equal or aliased. 560193323Sedstatic bool 561193323SedregsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { 562193323Sed if (RegA == RegB) 563193323Sed return true; 564193323Sed if (!RegA || !RegB) 565193323Sed return false; 566193323Sed return TRI->regsOverlap(RegA, RegB); 567193323Sed} 568193323Sed 569309124Sdim// Returns true if Reg is equal or aliased to at least one register in Set. 570309124Sdimstatic bool regOverlapsSet(const SmallVectorImpl<unsigned> &Set, unsigned Reg, 571309124Sdim const TargetRegisterInfo *TRI) { 572309124Sdim for (unsigned R : Set) 573309124Sdim if (TRI->regsOverlap(R, Reg)) 574309124Sdim return true; 575193323Sed 576309124Sdim return false; 577309124Sdim} 578309124Sdim 579296417Sdim/// Return true if it's potentially profitable to commute the two-address 580296417Sdim/// instruction that's being processed. 581193323Sedbool 582243830SdimTwoAddressInstructionPass:: 583243830SdimisProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, 584243830Sdim MachineInstr *MI, unsigned Dist) { 585234353Sdim if (OptLevel == CodeGenOpt::None) 586234353Sdim return false; 587234353Sdim 588193323Sed // Determine if it's profitable to commute this two address instruction. In 589193323Sed // general, we want no uses between this instruction and the definition of 590193323Sed // the two-address register. 591193323Sed // e.g. 592327952Sdim // %reg1028 = EXTRACT_SUBREG killed %reg1027, 1 593344779Sdim // %reg1029 = COPY %reg1028 594327952Sdim // %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags 595344779Sdim // insert => %reg1030 = COPY %reg1028 596327952Sdim // %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags 597344779Sdim // In this case, it might not be possible to coalesce the second COPY 598193323Sed // instruction if the first one is coalesced. So it would be profitable to 599193323Sed // commute it: 600327952Sdim // %reg1028 = EXTRACT_SUBREG killed %reg1027, 1 601344779Sdim // %reg1029 = COPY %reg1028 602327952Sdim // %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags 603344779Sdim // insert => %reg1030 = COPY %reg1029 604327952Sdim // %reg1030 = ADD8rr killed %reg1029, killed %reg1028, implicit dead %eflags 605193323Sed 606249423Sdim if (!isPlainlyKilled(MI, regC, LIS)) 607193323Sed return false; 608193323Sed 609193323Sed // Ok, we have something like: 610327952Sdim // %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags 611193323Sed // let's see if it's worth commuting it. 612193323Sed 613193323Sed // Look for situations like this: 614327952Sdim // %reg1024 = MOV r1 615327952Sdim // %reg1025 = MOV r0 616327952Sdim // %reg1026 = ADD %reg1024, %reg1025 617193323Sed // r0 = MOV %reg1026 618193323Sed // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. 619239462Sdim unsigned ToRegA = getMappedReg(regA, DstRegMap); 620239462Sdim if (ToRegA) { 621239462Sdim unsigned FromRegB = getMappedReg(regB, SrcRegMap); 622239462Sdim unsigned FromRegC = getMappedReg(regC, SrcRegMap); 623280031Sdim bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA, TRI); 624280031Sdim bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA, TRI); 625280031Sdim 626280031Sdim // Compute if any of the following are true: 627280031Sdim // -RegB is not tied to a register and RegC is compatible with RegA. 628280031Sdim // -RegB is tied to the wrong physical register, but RegC is. 629280031Sdim // -RegB is tied to the wrong physical register, and RegC isn't tied. 630280031Sdim if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC))) 631280031Sdim return true; 632280031Sdim // Don't compute if any of the following are true: 633280031Sdim // -RegC is not tied to a register and RegB is compatible with RegA. 634280031Sdim // -RegC is tied to the wrong physical register, but RegB is. 635280031Sdim // -RegC is tied to the wrong physical register, and RegB isn't tied. 636280031Sdim if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB))) 637280031Sdim return false; 638239462Sdim } 639193323Sed 640193323Sed // If there is a use of regC between its last def (could be livein) and this 641193323Sed // instruction, then bail. 642193323Sed unsigned LastDefC = 0; 643243830Sdim if (!noUseAfterLastDef(regC, Dist, LastDefC)) 644193323Sed return false; 645193323Sed 646193323Sed // If there is a use of regB between its last def (could be livein) and this 647193323Sed // instruction, then go ahead and make this transformation. 648193323Sed unsigned LastDefB = 0; 649243830Sdim if (!noUseAfterLastDef(regB, Dist, LastDefB)) 650193323Sed return true; 651193323Sed 652288943Sdim // Look for situation like this: 653288943Sdim // %reg101 = MOV %reg100 654288943Sdim // %reg102 = ... 655288943Sdim // %reg103 = ADD %reg102, %reg101 656288943Sdim // ... = %reg103 ... 657288943Sdim // %reg100 = MOV %reg103 658288943Sdim // If there is a reversed copy chain from reg101 to reg103, commute the ADD 659288943Sdim // to eliminate an otherwise unavoidable copy. 660288943Sdim // FIXME: 661288943Sdim // We can extend the logic further: If an pair of operands in an insn has 662288943Sdim // been merged, the insn could be regarded as a virtual copy, and the virtual 663288943Sdim // copy could also be used to construct a copy chain. 664288943Sdim // To more generally minimize register copies, ideally the logic of two addr 665288943Sdim // instruction pass should be integrated with register allocation pass where 666288943Sdim // interference graph is available. 667321369Sdim if (isRevCopyChain(regC, regA, MaxDataFlowEdge)) 668288943Sdim return true; 669288943Sdim 670321369Sdim if (isRevCopyChain(regB, regA, MaxDataFlowEdge)) 671288943Sdim return false; 672288943Sdim 673193323Sed // Since there are no intervening uses for both registers, then commute 674193323Sed // if the def of regC is closer. Its live interval is shorter. 675193323Sed return LastDefB && LastDefC && LastDefC > LastDefB; 676193323Sed} 677193323Sed 678296417Sdim/// Commute a two-address instruction and update the basic block, distance map, 679296417Sdim/// and live variables if needed. Return true if it is successful. 680296417Sdimbool TwoAddressInstructionPass::commuteInstruction(MachineInstr *MI, 681314564Sdim unsigned DstIdx, 682296417Sdim unsigned RegBIdx, 683296417Sdim unsigned RegCIdx, 684296417Sdim unsigned Dist) { 685360784Sdim Register RegC = MI->getOperand(RegCIdx).getReg(); 686341825Sdim LLVM_DEBUG(dbgs() << "2addr: COMMUTING : " << *MI); 687309124Sdim MachineInstr *NewMI = TII->commuteInstruction(*MI, false, RegBIdx, RegCIdx); 688193323Sed 689276479Sdim if (NewMI == nullptr) { 690341825Sdim LLVM_DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n"); 691193323Sed return false; 692193323Sed } 693193323Sed 694341825Sdim LLVM_DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI); 695249423Sdim assert(NewMI == MI && 696249423Sdim "TargetInstrInfo::commuteInstruction() should not return a new " 697249423Sdim "instruction unless it was requested."); 698193323Sed 699193323Sed // Update source register map. 700193323Sed unsigned FromRegC = getMappedReg(RegC, SrcRegMap); 701193323Sed if (FromRegC) { 702360784Sdim Register RegA = MI->getOperand(DstIdx).getReg(); 703193323Sed SrcRegMap[RegA] = FromRegC; 704193323Sed } 705193323Sed 706193323Sed return true; 707193323Sed} 708193323Sed 709296417Sdim/// Return true if it is profitable to convert the given 2-address instruction 710296417Sdim/// to a 3-address one. 711193323Sedbool 712221345SdimTwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){ 713193323Sed // Look for situations like this: 714327952Sdim // %reg1024 = MOV r1 715327952Sdim // %reg1025 = MOV r0 716327952Sdim // %reg1026 = ADD %reg1024, %reg1025 717193323Sed // r2 = MOV %reg1026 718193323Sed // Turn ADD into a 3-address instruction to avoid a copy. 719221345Sdim unsigned FromRegB = getMappedReg(RegB, SrcRegMap); 720221345Sdim if (!FromRegB) 721221345Sdim return false; 722193323Sed unsigned ToRegA = getMappedReg(RegA, DstRegMap); 723221345Sdim return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI)); 724193323Sed} 725193323Sed 726296417Sdim/// Convert the specified two-address instruction into a three address one. 727296417Sdim/// Return true if this transformation was successful. 728193323Sedbool 729243830SdimTwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi, 730193323Sed MachineBasicBlock::iterator &nmi, 731218893Sdim unsigned RegA, unsigned RegB, 732218893Sdim unsigned Dist) { 733243830Sdim // FIXME: Why does convertToThreeAddress() need an iterator reference? 734296417Sdim MachineFunction::iterator MFI = MBB->getIterator(); 735309124Sdim MachineInstr *NewMI = TII->convertToThreeAddress(MFI, *mi, LV); 736296417Sdim assert(MBB->getIterator() == MFI && 737296417Sdim "convertToThreeAddress changed iterator reference"); 738243830Sdim if (!NewMI) 739243830Sdim return false; 740193323Sed 741341825Sdim LLVM_DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi); 742341825Sdim LLVM_DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI); 743243830Sdim bool Sunk = false; 744239462Sdim 745249423Sdim if (LIS) 746309124Sdim LIS->ReplaceMachineInstrInMaps(*mi, *NewMI); 747193323Sed 748243830Sdim if (NewMI->findRegisterUseOperand(RegB, false, TRI)) 749243830Sdim // FIXME: Temporary workaround. If the new instruction doesn't 750243830Sdim // uses RegB, convertToThreeAddress must have created more 751243830Sdim // then one instruction. 752243830Sdim Sunk = sink3AddrInstruction(NewMI, RegB, mi); 753193323Sed 754243830Sdim MBB->erase(mi); // Nuke the old inst. 755218893Sdim 756243830Sdim if (!Sunk) { 757243830Sdim DistanceMap.insert(std::make_pair(NewMI, Dist)); 758243830Sdim mi = NewMI; 759276479Sdim nmi = std::next(mi); 760193323Sed } 761327952Sdim else 762327952Sdim SunkInstrs.insert(NewMI); 763193323Sed 764243830Sdim // Update source and destination register maps. 765243830Sdim SrcRegMap.erase(RegA); 766243830Sdim DstRegMap.erase(RegB); 767243830Sdim return true; 768193323Sed} 769193323Sed 770296417Sdim/// Scan forward recursively for only uses, update maps if the use is a copy or 771296417Sdim/// a two-address instruction. 772221345Sdimvoid 773243830SdimTwoAddressInstructionPass::scanUses(unsigned DstReg) { 774221345Sdim SmallVector<unsigned, 4> VirtRegPairs; 775221345Sdim bool IsDstPhys; 776221345Sdim bool IsCopy = false; 777221345Sdim unsigned NewReg = 0; 778221345Sdim unsigned Reg = DstReg; 779221345Sdim while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy, 780221345Sdim NewReg, IsDstPhys)) { 781280031Sdim if (IsCopy && !Processed.insert(UseMI).second) 782221345Sdim break; 783221345Sdim 784221345Sdim DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 785221345Sdim if (DI != DistanceMap.end()) 786221345Sdim // Earlier in the same MBB.Reached via a back edge. 787221345Sdim break; 788221345Sdim 789221345Sdim if (IsDstPhys) { 790221345Sdim VirtRegPairs.push_back(NewReg); 791221345Sdim break; 792221345Sdim } 793221345Sdim bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second; 794221345Sdim if (!isNew) 795221345Sdim assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!"); 796221345Sdim VirtRegPairs.push_back(NewReg); 797221345Sdim Reg = NewReg; 798221345Sdim } 799221345Sdim 800221345Sdim if (!VirtRegPairs.empty()) { 801221345Sdim unsigned ToReg = VirtRegPairs.back(); 802221345Sdim VirtRegPairs.pop_back(); 803221345Sdim while (!VirtRegPairs.empty()) { 804221345Sdim unsigned FromReg = VirtRegPairs.back(); 805221345Sdim VirtRegPairs.pop_back(); 806221345Sdim bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; 807221345Sdim if (!isNew) 808221345Sdim assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!"); 809221345Sdim ToReg = FromReg; 810221345Sdim } 811221345Sdim bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second; 812221345Sdim if (!isNew) 813221345Sdim assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!"); 814221345Sdim } 815221345Sdim} 816221345Sdim 817296417Sdim/// If the specified instruction is not yet processed, process it if it's a 818296417Sdim/// copy. For a copy instruction, we find the physical registers the 819193323Sed/// source and destination registers might be mapped to. These are kept in 820193323Sed/// point-to maps used to determine future optimizations. e.g. 821193323Sed/// v1024 = mov r0 822193323Sed/// v1025 = mov r1 823193323Sed/// v1026 = add v1024, v1025 824193323Sed/// r1 = mov r1026 825193323Sed/// If 'add' is a two-address instruction, v1024, v1026 are both potentially 826193323Sed/// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is 827193323Sed/// potentially joined with r1 on the output side. It's worthwhile to commute 828193323Sed/// 'add' to eliminate a copy. 829243830Sdimvoid TwoAddressInstructionPass::processCopy(MachineInstr *MI) { 830193323Sed if (Processed.count(MI)) 831193323Sed return; 832193323Sed 833193323Sed bool IsSrcPhys, IsDstPhys; 834193323Sed unsigned SrcReg, DstReg; 835193323Sed if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 836193323Sed return; 837193323Sed 838193323Sed if (IsDstPhys && !IsSrcPhys) 839193323Sed DstRegMap.insert(std::make_pair(SrcReg, DstReg)); 840193323Sed else if (!IsDstPhys && IsSrcPhys) { 841193323Sed bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second; 842193323Sed if (!isNew) 843193323Sed assert(SrcRegMap[DstReg] == SrcReg && 844193323Sed "Can't map to two src physical registers!"); 845193323Sed 846243830Sdim scanUses(DstReg); 847193323Sed } 848193323Sed 849193323Sed Processed.insert(MI); 850193323Sed} 851193323Sed 852296417Sdim/// If there is one more local instruction that reads 'Reg' and it kills 'Reg, 853296417Sdim/// consider moving the instruction below the kill instruction in order to 854296417Sdim/// eliminate the need for the copy. 855243830Sdimbool TwoAddressInstructionPass:: 856243830SdimrescheduleMIBelowKill(MachineBasicBlock::iterator &mi, 857243830Sdim MachineBasicBlock::iterator &nmi, 858243830Sdim unsigned Reg) { 859249423Sdim // Bail immediately if we don't have LV or LIS available. We use them to find 860249423Sdim // kills efficiently. 861249423Sdim if (!LV && !LIS) 862239462Sdim return false; 863239462Sdim 864234353Sdim MachineInstr *MI = &*mi; 865234353Sdim DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 866234353Sdim if (DI == DistanceMap.end()) 867234353Sdim // Must be created from unfolded load. Don't waste time trying this. 868234353Sdim return false; 869234353Sdim 870276479Sdim MachineInstr *KillMI = nullptr; 871249423Sdim if (LIS) { 872249423Sdim LiveInterval &LI = LIS->getInterval(Reg); 873249423Sdim assert(LI.end() != LI.begin() && 874249423Sdim "Reg should not have empty live interval."); 875249423Sdim 876249423Sdim SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 877249423Sdim LiveInterval::const_iterator I = LI.find(MBBEndIdx); 878249423Sdim if (I != LI.end() && I->start < MBBEndIdx) 879249423Sdim return false; 880249423Sdim 881249423Sdim --I; 882249423Sdim KillMI = LIS->getInstructionFromIndex(I->end); 883249423Sdim } else { 884249423Sdim KillMI = LV->getVarInfo(Reg).findKill(MBB); 885249423Sdim } 886239462Sdim if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike()) 887234353Sdim // Don't mess with copies, they may be coalesced later. 888234353Sdim return false; 889234353Sdim 890234353Sdim if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() || 891234353Sdim KillMI->isBranch() || KillMI->isTerminator()) 892234353Sdim // Don't move pass calls, etc. 893234353Sdim return false; 894234353Sdim 895234353Sdim unsigned DstReg; 896234353Sdim if (isTwoAddrUse(*KillMI, Reg, DstReg)) 897234353Sdim return false; 898234353Sdim 899234353Sdim bool SeenStore = true; 900288943Sdim if (!MI->isSafeToMove(AA, SeenStore)) 901234353Sdim return false; 902234353Sdim 903309124Sdim if (TII->getInstrLatency(InstrItins, *MI) > 1) 904234353Sdim // FIXME: Needs more sophisticated heuristics. 905234353Sdim return false; 906234353Sdim 907309124Sdim SmallVector<unsigned, 2> Uses; 908309124Sdim SmallVector<unsigned, 2> Kills; 909309124Sdim SmallVector<unsigned, 2> Defs; 910296417Sdim for (const MachineOperand &MO : MI->operands()) { 911234353Sdim if (!MO.isReg()) 912234353Sdim continue; 913360784Sdim Register MOReg = MO.getReg(); 914234353Sdim if (!MOReg) 915234353Sdim continue; 916234353Sdim if (MO.isDef()) 917309124Sdim Defs.push_back(MOReg); 918234353Sdim else { 919309124Sdim Uses.push_back(MOReg); 920249423Sdim if (MOReg != Reg && (MO.isKill() || 921249423Sdim (LIS && isPlainlyKilled(MI, MOReg, LIS)))) 922309124Sdim Kills.push_back(MOReg); 923234353Sdim } 924234353Sdim } 925234353Sdim 926234353Sdim // Move the copies connected to MI down as well. 927249423Sdim MachineBasicBlock::iterator Begin = MI; 928276479Sdim MachineBasicBlock::iterator AfterMI = std::next(Begin); 929249423Sdim MachineBasicBlock::iterator End = AfterMI; 930344779Sdim while (End != MBB->end()) { 931344779Sdim End = skipDebugInstructionsForward(End, MBB->end()); 932344779Sdim if (End->isCopy() && regOverlapsSet(Defs, End->getOperand(1).getReg(), TRI)) 933344779Sdim Defs.push_back(End->getOperand(0).getReg()); 934344779Sdim else 935344779Sdim break; 936249423Sdim ++End; 937234353Sdim } 938234353Sdim 939321369Sdim // Check if the reschedule will not break dependencies. 940234353Sdim unsigned NumVisited = 0; 941234353Sdim MachineBasicBlock::iterator KillPos = KillMI; 942234353Sdim ++KillPos; 943327952Sdim for (MachineInstr &OtherMI : make_range(End, KillPos)) { 944341825Sdim // Debug instructions cannot be counted against the limit. 945341825Sdim if (OtherMI.isDebugInstr()) 946234353Sdim continue; 947234353Sdim if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. 948234353Sdim return false; 949234353Sdim ++NumVisited; 950309124Sdim if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() || 951309124Sdim OtherMI.isBranch() || OtherMI.isTerminator()) 952234353Sdim // Don't move pass calls, etc. 953234353Sdim return false; 954309124Sdim for (const MachineOperand &MO : OtherMI.operands()) { 955234353Sdim if (!MO.isReg()) 956234353Sdim continue; 957360784Sdim Register MOReg = MO.getReg(); 958234353Sdim if (!MOReg) 959234353Sdim continue; 960234353Sdim if (MO.isDef()) { 961309124Sdim if (regOverlapsSet(Uses, MOReg, TRI)) 962234353Sdim // Physical register use would be clobbered. 963234353Sdim return false; 964309124Sdim if (!MO.isDead() && regOverlapsSet(Defs, MOReg, TRI)) 965234353Sdim // May clobber a physical register def. 966234353Sdim // FIXME: This may be too conservative. It's ok if the instruction 967234353Sdim // is sunken completely below the use. 968234353Sdim return false; 969234353Sdim } else { 970309124Sdim if (regOverlapsSet(Defs, MOReg, TRI)) 971234353Sdim return false; 972309124Sdim bool isKill = 973309124Sdim MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS)); 974309124Sdim if (MOReg != Reg && ((isKill && regOverlapsSet(Uses, MOReg, TRI)) || 975309124Sdim regOverlapsSet(Kills, MOReg, TRI))) 976234353Sdim // Don't want to extend other live ranges and update kills. 977234353Sdim return false; 978249423Sdim if (MOReg == Reg && !isKill) 979239462Sdim // We can't schedule across a use of the register in question. 980239462Sdim return false; 981239462Sdim // Ensure that if this is register in question, its the kill we expect. 982309124Sdim assert((MOReg != Reg || &OtherMI == KillMI) && 983239462Sdim "Found multiple kills of a register in a basic block"); 984234353Sdim } 985234353Sdim } 986234353Sdim } 987234353Sdim 988234353Sdim // Move debug info as well. 989341825Sdim while (Begin != MBB->begin() && std::prev(Begin)->isDebugInstr()) 990249423Sdim --Begin; 991234353Sdim 992249423Sdim nmi = End; 993249423Sdim MachineBasicBlock::iterator InsertPos = KillPos; 994249423Sdim if (LIS) { 995249423Sdim // We have to move the copies first so that the MBB is still well-formed 996249423Sdim // when calling handleMove(). 997249423Sdim for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) { 998309124Sdim auto CopyMI = MBBI++; 999249423Sdim MBB->splice(InsertPos, MBB, CopyMI); 1000309124Sdim LIS->handleMove(*CopyMI); 1001249423Sdim InsertPos = CopyMI; 1002249423Sdim } 1003276479Sdim End = std::next(MachineBasicBlock::iterator(MI)); 1004249423Sdim } 1005249423Sdim 1006234353Sdim // Copies following MI may have been moved as well. 1007249423Sdim MBB->splice(InsertPos, MBB, Begin, End); 1008234353Sdim DistanceMap.erase(DI); 1009234353Sdim 1010239462Sdim // Update live variables 1011249423Sdim if (LIS) { 1012309124Sdim LIS->handleMove(*MI); 1013249423Sdim } else { 1014309124Sdim LV->removeVirtualRegisterKilled(Reg, *KillMI); 1015309124Sdim LV->addVirtualRegisterKilled(Reg, *MI); 1016249423Sdim } 1017234353Sdim 1018341825Sdim LLVM_DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI); 1019234353Sdim return true; 1020234353Sdim} 1021234353Sdim 1022296417Sdim/// Return true if the re-scheduling will put the given instruction too close 1023296417Sdim/// to the defs of its register dependencies. 1024234353Sdimbool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist, 1025243830Sdim MachineInstr *MI) { 1026276479Sdim for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { 1027276479Sdim if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike()) 1028234353Sdim continue; 1029276479Sdim if (&DefMI == MI) 1030234353Sdim return true; // MI is defining something KillMI uses 1031276479Sdim DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(&DefMI); 1032234353Sdim if (DDI == DistanceMap.end()) 1033234353Sdim return true; // Below MI 1034234353Sdim unsigned DefDist = DDI->second; 1035234353Sdim assert(Dist > DefDist && "Visited def already?"); 1036309124Sdim if (TII->getInstrLatency(InstrItins, DefMI) > (Dist - DefDist)) 1037234353Sdim return true; 1038234353Sdim } 1039234353Sdim return false; 1040234353Sdim} 1041234353Sdim 1042296417Sdim/// If there is one more local instruction that reads 'Reg' and it kills 'Reg, 1043296417Sdim/// consider moving the kill instruction above the current two-address 1044296417Sdim/// instruction in order to eliminate the need for the copy. 1045243830Sdimbool TwoAddressInstructionPass:: 1046243830SdimrescheduleKillAboveMI(MachineBasicBlock::iterator &mi, 1047243830Sdim MachineBasicBlock::iterator &nmi, 1048243830Sdim unsigned Reg) { 1049249423Sdim // Bail immediately if we don't have LV or LIS available. We use them to find 1050249423Sdim // kills efficiently. 1051249423Sdim if (!LV && !LIS) 1052239462Sdim return false; 1053239462Sdim 1054234353Sdim MachineInstr *MI = &*mi; 1055234353Sdim DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 1056234353Sdim if (DI == DistanceMap.end()) 1057234353Sdim // Must be created from unfolded load. Don't waste time trying this. 1058234353Sdim return false; 1059234353Sdim 1060276479Sdim MachineInstr *KillMI = nullptr; 1061249423Sdim if (LIS) { 1062249423Sdim LiveInterval &LI = LIS->getInterval(Reg); 1063249423Sdim assert(LI.end() != LI.begin() && 1064249423Sdim "Reg should not have empty live interval."); 1065249423Sdim 1066249423Sdim SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 1067249423Sdim LiveInterval::const_iterator I = LI.find(MBBEndIdx); 1068249423Sdim if (I != LI.end() && I->start < MBBEndIdx) 1069249423Sdim return false; 1070249423Sdim 1071249423Sdim --I; 1072249423Sdim KillMI = LIS->getInstructionFromIndex(I->end); 1073249423Sdim } else { 1074249423Sdim KillMI = LV->getVarInfo(Reg).findKill(MBB); 1075249423Sdim } 1076239462Sdim if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike()) 1077234353Sdim // Don't mess with copies, they may be coalesced later. 1078234353Sdim return false; 1079234353Sdim 1080234353Sdim unsigned DstReg; 1081234353Sdim if (isTwoAddrUse(*KillMI, Reg, DstReg)) 1082234353Sdim return false; 1083234353Sdim 1084234353Sdim bool SeenStore = true; 1085288943Sdim if (!KillMI->isSafeToMove(AA, SeenStore)) 1086234353Sdim return false; 1087234353Sdim 1088234353Sdim SmallSet<unsigned, 2> Uses; 1089234353Sdim SmallSet<unsigned, 2> Kills; 1090234353Sdim SmallSet<unsigned, 2> Defs; 1091234353Sdim SmallSet<unsigned, 2> LiveDefs; 1092296417Sdim for (const MachineOperand &MO : KillMI->operands()) { 1093234353Sdim if (!MO.isReg()) 1094234353Sdim continue; 1095360784Sdim Register MOReg = MO.getReg(); 1096234353Sdim if (MO.isUse()) { 1097234353Sdim if (!MOReg) 1098234353Sdim continue; 1099243830Sdim if (isDefTooClose(MOReg, DI->second, MI)) 1100234353Sdim return false; 1101249423Sdim bool isKill = MO.isKill() || (LIS && isPlainlyKilled(KillMI, MOReg, LIS)); 1102249423Sdim if (MOReg == Reg && !isKill) 1103239462Sdim return false; 1104234353Sdim Uses.insert(MOReg); 1105249423Sdim if (isKill && MOReg != Reg) 1106234353Sdim Kills.insert(MOReg); 1107360784Sdim } else if (Register::isPhysicalRegister(MOReg)) { 1108234353Sdim Defs.insert(MOReg); 1109234353Sdim if (!MO.isDead()) 1110234353Sdim LiveDefs.insert(MOReg); 1111234353Sdim } 1112234353Sdim } 1113234353Sdim 1114234353Sdim // Check if the reschedule will not break depedencies. 1115234353Sdim unsigned NumVisited = 0; 1116309124Sdim for (MachineInstr &OtherMI : 1117327952Sdim make_range(mi, MachineBasicBlock::iterator(KillMI))) { 1118341825Sdim // Debug instructions cannot be counted against the limit. 1119341825Sdim if (OtherMI.isDebugInstr()) 1120234353Sdim continue; 1121234353Sdim if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. 1122234353Sdim return false; 1123234353Sdim ++NumVisited; 1124309124Sdim if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() || 1125309124Sdim OtherMI.isBranch() || OtherMI.isTerminator()) 1126234353Sdim // Don't move pass calls, etc. 1127234353Sdim return false; 1128234353Sdim SmallVector<unsigned, 2> OtherDefs; 1129309124Sdim for (const MachineOperand &MO : OtherMI.operands()) { 1130234353Sdim if (!MO.isReg()) 1131234353Sdim continue; 1132360784Sdim Register MOReg = MO.getReg(); 1133234353Sdim if (!MOReg) 1134234353Sdim continue; 1135234353Sdim if (MO.isUse()) { 1136234353Sdim if (Defs.count(MOReg)) 1137234353Sdim // Moving KillMI can clobber the physical register if the def has 1138234353Sdim // not been seen. 1139234353Sdim return false; 1140234353Sdim if (Kills.count(MOReg)) 1141234353Sdim // Don't want to extend other live ranges and update kills. 1142234353Sdim return false; 1143309124Sdim if (&OtherMI != MI && MOReg == Reg && 1144309124Sdim !(MO.isKill() || (LIS && isPlainlyKilled(&OtherMI, MOReg, LIS)))) 1145239462Sdim // We can't schedule across a use of the register in question. 1146239462Sdim return false; 1147234353Sdim } else { 1148234353Sdim OtherDefs.push_back(MOReg); 1149234353Sdim } 1150234353Sdim } 1151234353Sdim 1152234353Sdim for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) { 1153234353Sdim unsigned MOReg = OtherDefs[i]; 1154234353Sdim if (Uses.count(MOReg)) 1155234353Sdim return false; 1156360784Sdim if (Register::isPhysicalRegister(MOReg) && LiveDefs.count(MOReg)) 1157234353Sdim return false; 1158234353Sdim // Physical register def is seen. 1159234353Sdim Defs.erase(MOReg); 1160234353Sdim } 1161234353Sdim } 1162234353Sdim 1163234353Sdim // Move the old kill above MI, don't forget to move debug info as well. 1164234353Sdim MachineBasicBlock::iterator InsertPos = mi; 1165341825Sdim while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugInstr()) 1166234353Sdim --InsertPos; 1167234353Sdim MachineBasicBlock::iterator From = KillMI; 1168276479Sdim MachineBasicBlock::iterator To = std::next(From); 1169341825Sdim while (std::prev(From)->isDebugInstr()) 1170234353Sdim --From; 1171234353Sdim MBB->splice(InsertPos, MBB, From, To); 1172234353Sdim 1173276479Sdim nmi = std::prev(InsertPos); // Backtrack so we process the moved instr. 1174234353Sdim DistanceMap.erase(DI); 1175234353Sdim 1176239462Sdim // Update live variables 1177249423Sdim if (LIS) { 1178309124Sdim LIS->handleMove(*KillMI); 1179249423Sdim } else { 1180309124Sdim LV->removeVirtualRegisterKilled(Reg, *KillMI); 1181309124Sdim LV->addVirtualRegisterKilled(Reg, *MI); 1182249423Sdim } 1183239462Sdim 1184341825Sdim LLVM_DEBUG(dbgs() << "\trescheduled kill: " << *KillMI); 1185234353Sdim return true; 1186234353Sdim} 1187234353Sdim 1188296417Sdim/// Tries to commute the operand 'BaseOpIdx' and some other operand in the 1189296417Sdim/// given machine instruction to improve opportunities for coalescing and 1190296417Sdim/// elimination of a register to register copy. 1191296417Sdim/// 1192296417Sdim/// 'DstOpIdx' specifies the index of MI def operand. 1193296417Sdim/// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx' 1194296417Sdim/// operand is killed by the given instruction. 1195296417Sdim/// The 'Dist' arguments provides the distance of MI from the start of the 1196296417Sdim/// current basic block and it is used to determine if it is profitable 1197296417Sdim/// to commute operands in the instruction. 1198296417Sdim/// 1199296417Sdim/// Returns true if the transformation happened. Otherwise, returns false. 1200296417Sdimbool TwoAddressInstructionPass::tryInstructionCommute(MachineInstr *MI, 1201296417Sdim unsigned DstOpIdx, 1202296417Sdim unsigned BaseOpIdx, 1203296417Sdim bool BaseOpKilled, 1204296417Sdim unsigned Dist) { 1205314564Sdim if (!MI->isCommutable()) 1206314564Sdim return false; 1207314564Sdim 1208341825Sdim bool MadeChange = false; 1209360784Sdim Register DstOpReg = MI->getOperand(DstOpIdx).getReg(); 1210360784Sdim Register BaseOpReg = MI->getOperand(BaseOpIdx).getReg(); 1211296417Sdim unsigned OpsNum = MI->getDesc().getNumOperands(); 1212296417Sdim unsigned OtherOpIdx = MI->getDesc().getNumDefs(); 1213296417Sdim for (; OtherOpIdx < OpsNum; OtherOpIdx++) { 1214296417Sdim // The call of findCommutedOpIndices below only checks if BaseOpIdx 1215296417Sdim // and OtherOpIdx are commutable, it does not really search for 1216296417Sdim // other commutable operands and does not change the values of passed 1217296417Sdim // variables. 1218314564Sdim if (OtherOpIdx == BaseOpIdx || !MI->getOperand(OtherOpIdx).isReg() || 1219309124Sdim !TII->findCommutedOpIndices(*MI, BaseOpIdx, OtherOpIdx)) 1220296417Sdim continue; 1221296417Sdim 1222360784Sdim Register OtherOpReg = MI->getOperand(OtherOpIdx).getReg(); 1223296417Sdim bool AggressiveCommute = false; 1224296417Sdim 1225296417Sdim // If OtherOp dies but BaseOp does not, swap the OtherOp and BaseOp 1226296417Sdim // operands. This makes the live ranges of DstOp and OtherOp joinable. 1227341825Sdim bool OtherOpKilled = isKilled(*MI, OtherOpReg, MRI, TII, LIS, false); 1228341825Sdim bool DoCommute = !BaseOpKilled && OtherOpKilled; 1229296417Sdim 1230296417Sdim if (!DoCommute && 1231296417Sdim isProfitableToCommute(DstOpReg, BaseOpReg, OtherOpReg, MI, Dist)) { 1232296417Sdim DoCommute = true; 1233296417Sdim AggressiveCommute = true; 1234296417Sdim } 1235296417Sdim 1236296417Sdim // If it's profitable to commute, try to do so. 1237314564Sdim if (DoCommute && commuteInstruction(MI, DstOpIdx, BaseOpIdx, OtherOpIdx, 1238314564Sdim Dist)) { 1239341825Sdim MadeChange = true; 1240296417Sdim ++NumCommuted; 1241341825Sdim if (AggressiveCommute) { 1242296417Sdim ++NumAggrCommuted; 1243341825Sdim // There might be more than two commutable operands, update BaseOp and 1244341825Sdim // continue scanning. 1245353358Sdim // FIXME: This assumes that the new instruction's operands are in the 1246353358Sdim // same positions and were simply swapped. 1247341825Sdim BaseOpReg = OtherOpReg; 1248341825Sdim BaseOpKilled = OtherOpKilled; 1249353358Sdim // Resamples OpsNum in case the number of operands was reduced. This 1250353358Sdim // happens with X86. 1251353358Sdim OpsNum = MI->getDesc().getNumOperands(); 1252341825Sdim continue; 1253341825Sdim } 1254341825Sdim // If this was a commute based on kill, we won't do better continuing. 1255341825Sdim return MadeChange; 1256296417Sdim } 1257296417Sdim } 1258341825Sdim return MadeChange; 1259296417Sdim} 1260296417Sdim 1261296417Sdim/// For the case where an instruction has a single pair of tied register 1262296417Sdim/// operands, attempt some transformations that may either eliminate the tied 1263296417Sdim/// operands or improve the opportunities for coalescing away the register copy. 1264296417Sdim/// Returns true if no copy needs to be inserted to untie mi's operands 1265296417Sdim/// (either because they were untied, or because mi was rescheduled, and will 1266296417Sdim/// be visited again later). If the shouldOnlyCommute flag is true, only 1267296417Sdim/// instruction commutation is attempted. 1268198090Srdivackybool TwoAddressInstructionPass:: 1269243830SdimtryInstructionTransform(MachineBasicBlock::iterator &mi, 1270198090Srdivacky MachineBasicBlock::iterator &nmi, 1271249423Sdim unsigned SrcIdx, unsigned DstIdx, 1272249423Sdim unsigned Dist, bool shouldOnlyCommute) { 1273234353Sdim if (OptLevel == CodeGenOpt::None) 1274234353Sdim return false; 1275198090Srdivacky 1276234353Sdim MachineInstr &MI = *mi; 1277360784Sdim Register regA = MI.getOperand(DstIdx).getReg(); 1278360784Sdim Register regB = MI.getOperand(SrcIdx).getReg(); 1279234353Sdim 1280360784Sdim assert(Register::isVirtualRegister(regB) && 1281198090Srdivacky "cannot make instruction into two-address form"); 1282249423Sdim bool regBKilled = isKilled(MI, regB, MRI, TII, LIS, true); 1283198090Srdivacky 1284360784Sdim if (Register::isVirtualRegister(regA)) 1285243830Sdim scanUses(regA); 1286239462Sdim 1287296417Sdim bool Commuted = tryInstructionCommute(&MI, DstIdx, SrcIdx, regBKilled, Dist); 1288198090Srdivacky 1289288943Sdim // If the instruction is convertible to 3 Addr, instead 1290360784Sdim // of returning try 3 Addr transformation aggressively and 1291288943Sdim // use this variable to check later. Because it might be better. 1292288943Sdim // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret` 1293288943Sdim // instead of the following code. 1294296417Sdim // addl %esi, %edi 1295296417Sdim // movl %edi, %eax 1296288943Sdim // ret 1297296417Sdim if (Commuted && !MI.isConvertibleTo3Addr()) 1298296417Sdim return false; 1299288943Sdim 1300249423Sdim if (shouldOnlyCommute) 1301249423Sdim return false; 1302249423Sdim 1303234353Sdim // If there is one more use of regB later in the same MBB, consider 1304234353Sdim // re-schedule this MI below it. 1305288943Sdim if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) { 1306234353Sdim ++NumReSchedDowns; 1307234353Sdim return true; 1308234353Sdim } 1309234353Sdim 1310296417Sdim // If we commuted, regB may have changed so we should re-sample it to avoid 1311296417Sdim // confusing the three address conversion below. 1312296417Sdim if (Commuted) { 1313296417Sdim regB = MI.getOperand(SrcIdx).getReg(); 1314296417Sdim regBKilled = isKilled(MI, regB, MRI, TII, LIS, true); 1315296417Sdim } 1316296417Sdim 1317234353Sdim if (MI.isConvertibleTo3Addr()) { 1318198090Srdivacky // This instruction is potentially convertible to a true 1319198090Srdivacky // three-address instruction. Check if it is profitable. 1320221345Sdim if (!regBKilled || isProfitableToConv3Addr(regA, regB)) { 1321198090Srdivacky // Try to convert it. 1322243830Sdim if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) { 1323198090Srdivacky ++NumConvertedTo3Addr; 1324198090Srdivacky return true; // Done with this instruction. 1325198090Srdivacky } 1326198090Srdivacky } 1327198090Srdivacky } 1328210299Sed 1329288943Sdim // Return if it is commuted but 3 addr conversion is failed. 1330288943Sdim if (Commuted) 1331288943Sdim return false; 1332288943Sdim 1333234353Sdim // If there is one more use of regB later in the same MBB, consider 1334234353Sdim // re-schedule it before this MI if it's legal. 1335251662Sdim if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) { 1336234353Sdim ++NumReSchedUps; 1337234353Sdim return true; 1338234353Sdim } 1339234353Sdim 1340210299Sed // If this is an instruction with a load folded into it, try unfolding 1341210299Sed // the load, e.g. avoid this: 1342210299Sed // movq %rdx, %rcx 1343210299Sed // addq (%rax), %rcx 1344210299Sed // in favor of this: 1345210299Sed // movq (%rax), %rcx 1346210299Sed // addq %rdx, %rcx 1347210299Sed // because it's preferable to schedule a load than a register copy. 1348234353Sdim if (MI.mayLoad() && !regBKilled) { 1349210299Sed // Determine if a load can be unfolded. 1350210299Sed unsigned LoadRegIndex; 1351210299Sed unsigned NewOpc = 1352234353Sdim TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), 1353210299Sed /*UnfoldLoad=*/true, 1354210299Sed /*UnfoldStore=*/false, 1355210299Sed &LoadRegIndex); 1356210299Sed if (NewOpc != 0) { 1357224145Sdim const MCInstrDesc &UnfoldMCID = TII->get(NewOpc); 1358224145Sdim if (UnfoldMCID.getNumDefs() == 1) { 1359210299Sed // Unfold the load. 1360341825Sdim LLVM_DEBUG(dbgs() << "2addr: UNFOLDING: " << MI); 1361210299Sed const TargetRegisterClass *RC = 1362239462Sdim TRI->getAllocatableClass( 1363239462Sdim TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF)); 1364360784Sdim Register Reg = MRI->createVirtualRegister(RC); 1365210299Sed SmallVector<MachineInstr *, 2> NewMIs; 1366309124Sdim if (!TII->unfoldMemoryOperand(*MF, MI, Reg, 1367309124Sdim /*UnfoldLoad=*/true, 1368309124Sdim /*UnfoldStore=*/false, NewMIs)) { 1369341825Sdim LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); 1370210299Sed return false; 1371210299Sed } 1372210299Sed assert(NewMIs.size() == 2 && 1373210299Sed "Unfolded a load into multiple instructions!"); 1374210299Sed // The load was previously folded, so this is the only use. 1375210299Sed NewMIs[1]->addRegisterKilled(Reg, TRI); 1376210299Sed 1377210299Sed // Tentatively insert the instructions into the block so that they 1378210299Sed // look "normal" to the transformation logic. 1379243830Sdim MBB->insert(mi, NewMIs[0]); 1380243830Sdim MBB->insert(mi, NewMIs[1]); 1381210299Sed 1382341825Sdim LLVM_DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0] 1383341825Sdim << "2addr: NEW INST: " << *NewMIs[1]); 1384210299Sed 1385210299Sed // Transform the instruction, now that it no longer has a load. 1386210299Sed unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA); 1387210299Sed unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB); 1388210299Sed MachineBasicBlock::iterator NewMI = NewMIs[1]; 1389249423Sdim bool TransformResult = 1390249423Sdim tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist, true); 1391249423Sdim (void)TransformResult; 1392249423Sdim assert(!TransformResult && 1393249423Sdim "tryInstructionTransform() should return false."); 1394249423Sdim if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) { 1395210299Sed // Success, or at least we made an improvement. Keep the unfolded 1396210299Sed // instructions and discard the original. 1397210299Sed if (LV) { 1398234353Sdim for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 1399234353Sdim MachineOperand &MO = MI.getOperand(i); 1400360784Sdim if (MO.isReg() && Register::isVirtualRegister(MO.getReg())) { 1401210299Sed if (MO.isUse()) { 1402210299Sed if (MO.isKill()) { 1403210299Sed if (NewMIs[0]->killsRegister(MO.getReg())) 1404309124Sdim LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[0]); 1405210299Sed else { 1406210299Sed assert(NewMIs[1]->killsRegister(MO.getReg()) && 1407210299Sed "Kill missing after load unfold!"); 1408309124Sdim LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[1]); 1409210299Sed } 1410210299Sed } 1411309124Sdim } else if (LV->removeVirtualRegisterDead(MO.getReg(), MI)) { 1412210299Sed if (NewMIs[1]->registerDefIsDead(MO.getReg())) 1413309124Sdim LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[1]); 1414210299Sed else { 1415210299Sed assert(NewMIs[0]->registerDefIsDead(MO.getReg()) && 1416210299Sed "Dead flag missing after load unfold!"); 1417309124Sdim LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[0]); 1418210299Sed } 1419210299Sed } 1420210299Sed } 1421210299Sed } 1422309124Sdim LV->addVirtualRegisterKilled(Reg, *NewMIs[1]); 1423210299Sed } 1424249423Sdim 1425249423Sdim SmallVector<unsigned, 4> OrigRegs; 1426249423Sdim if (LIS) { 1427296417Sdim for (const MachineOperand &MO : MI.operands()) { 1428296417Sdim if (MO.isReg()) 1429296417Sdim OrigRegs.push_back(MO.getReg()); 1430249423Sdim } 1431249423Sdim } 1432249423Sdim 1433234353Sdim MI.eraseFromParent(); 1434249423Sdim 1435249423Sdim // Update LiveIntervals. 1436249423Sdim if (LIS) { 1437249423Sdim MachineBasicBlock::iterator Begin(NewMIs[0]); 1438249423Sdim MachineBasicBlock::iterator End(NewMIs[1]); 1439249423Sdim LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs); 1440249423Sdim } 1441249423Sdim 1442210299Sed mi = NewMIs[1]; 1443210299Sed } else { 1444210299Sed // Transforming didn't eliminate the tie and didn't lead to an 1445210299Sed // improvement. Clean up the unfolded instructions and keep the 1446210299Sed // original. 1447341825Sdim LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); 1448210299Sed NewMIs[0]->eraseFromParent(); 1449210299Sed NewMIs[1]->eraseFromParent(); 1450210299Sed } 1451210299Sed } 1452210299Sed } 1453210299Sed } 1454210299Sed 1455198090Srdivacky return false; 1456198090Srdivacky} 1457198090Srdivacky 1458239462Sdim// Collect tied operands of MI that need to be handled. 1459239462Sdim// Rewrite trivial cases immediately. 1460239462Sdim// Return true if any tied operands where found, including the trivial ones. 1461239462Sdimbool TwoAddressInstructionPass:: 1462239462SdimcollectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) { 1463239462Sdim const MCInstrDesc &MCID = MI->getDesc(); 1464239462Sdim bool AnyOps = false; 1465243830Sdim unsigned NumOps = MI->getNumOperands(); 1466239462Sdim 1467239462Sdim for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) { 1468239462Sdim unsigned DstIdx = 0; 1469239462Sdim if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx)) 1470239462Sdim continue; 1471239462Sdim AnyOps = true; 1472239462Sdim MachineOperand &SrcMO = MI->getOperand(SrcIdx); 1473239462Sdim MachineOperand &DstMO = MI->getOperand(DstIdx); 1474360784Sdim Register SrcReg = SrcMO.getReg(); 1475360784Sdim Register DstReg = DstMO.getReg(); 1476239462Sdim // Tied constraint already satisfied? 1477239462Sdim if (SrcReg == DstReg) 1478239462Sdim continue; 1479239462Sdim 1480239462Sdim assert(SrcReg && SrcMO.isUse() && "two address instruction invalid"); 1481239462Sdim 1482327952Sdim // Deal with undef uses immediately - simply rewrite the src operand. 1483276479Sdim if (SrcMO.isUndef() && !DstMO.getSubReg()) { 1484239462Sdim // Constrain the DstReg register class if required. 1485360784Sdim if (Register::isVirtualRegister(DstReg)) 1486239462Sdim if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx, 1487239462Sdim TRI, *MF)) 1488239462Sdim MRI->constrainRegClass(DstReg, RC); 1489239462Sdim SrcMO.setReg(DstReg); 1490276479Sdim SrcMO.setSubReg(0); 1491341825Sdim LLVM_DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI); 1492239462Sdim continue; 1493239462Sdim } 1494239462Sdim TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx)); 1495239462Sdim } 1496239462Sdim return AnyOps; 1497239462Sdim} 1498239462Sdim 1499239462Sdim// Process a list of tied MI operands that all use the same source register. 1500239462Sdim// The tied pairs are of the form (SrcIdx, DstIdx). 1501239462Sdimvoid 1502239462SdimTwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, 1503239462Sdim TiedPairList &TiedPairs, 1504239462Sdim unsigned &Dist) { 1505239462Sdim bool IsEarlyClobber = false; 1506249423Sdim for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { 1507249423Sdim const MachineOperand &DstMO = MI->getOperand(TiedPairs[tpi].second); 1508249423Sdim IsEarlyClobber |= DstMO.isEarlyClobber(); 1509249423Sdim } 1510249423Sdim 1511239462Sdim bool RemovedKillFlag = false; 1512239462Sdim bool AllUsesCopied = true; 1513239462Sdim unsigned LastCopiedReg = 0; 1514249423Sdim SlotIndex LastCopyIdx; 1515239462Sdim unsigned RegB = 0; 1516276479Sdim unsigned SubRegB = 0; 1517239462Sdim for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { 1518239462Sdim unsigned SrcIdx = TiedPairs[tpi].first; 1519239462Sdim unsigned DstIdx = TiedPairs[tpi].second; 1520239462Sdim 1521239462Sdim const MachineOperand &DstMO = MI->getOperand(DstIdx); 1522360784Sdim Register RegA = DstMO.getReg(); 1523239462Sdim 1524239462Sdim // Grab RegB from the instruction because it may have changed if the 1525239462Sdim // instruction was commuted. 1526239462Sdim RegB = MI->getOperand(SrcIdx).getReg(); 1527276479Sdim SubRegB = MI->getOperand(SrcIdx).getSubReg(); 1528239462Sdim 1529239462Sdim if (RegA == RegB) { 1530239462Sdim // The register is tied to multiple destinations (or else we would 1531239462Sdim // not have continued this far), but this use of the register 1532239462Sdim // already matches the tied destination. Leave it. 1533239462Sdim AllUsesCopied = false; 1534239462Sdim continue; 1535239462Sdim } 1536239462Sdim LastCopiedReg = RegA; 1537239462Sdim 1538360784Sdim assert(Register::isVirtualRegister(RegB) && 1539239462Sdim "cannot make instruction into two-address form"); 1540239462Sdim 1541239462Sdim#ifndef NDEBUG 1542239462Sdim // First, verify that we don't have a use of "a" in the instruction 1543239462Sdim // (a = b + a for example) because our transformation will not 1544239462Sdim // work. This should never occur because we are in SSA form. 1545239462Sdim for (unsigned i = 0; i != MI->getNumOperands(); ++i) 1546239462Sdim assert(i == DstIdx || 1547239462Sdim !MI->getOperand(i).isReg() || 1548239462Sdim MI->getOperand(i).getReg() != RegA); 1549239462Sdim#endif 1550239462Sdim 1551239462Sdim // Emit a copy. 1552276479Sdim MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), 1553276479Sdim TII->get(TargetOpcode::COPY), RegA); 1554276479Sdim // If this operand is folding a truncation, the truncation now moves to the 1555276479Sdim // copy so that the register classes remain valid for the operands. 1556276479Sdim MIB.addReg(RegB, 0, SubRegB); 1557276479Sdim const TargetRegisterClass *RC = MRI->getRegClass(RegB); 1558276479Sdim if (SubRegB) { 1559360784Sdim if (Register::isVirtualRegister(RegA)) { 1560276479Sdim assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA), 1561276479Sdim SubRegB) && 1562276479Sdim "tied subregister must be a truncation"); 1563276479Sdim // The superreg class will not be used to constrain the subreg class. 1564276479Sdim RC = nullptr; 1565360784Sdim } else { 1566276479Sdim assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB)) 1567276479Sdim && "tied subregister must be a truncation"); 1568276479Sdim } 1569276479Sdim } 1570239462Sdim 1571239462Sdim // Update DistanceMap. 1572239462Sdim MachineBasicBlock::iterator PrevMI = MI; 1573239462Sdim --PrevMI; 1574309124Sdim DistanceMap.insert(std::make_pair(&*PrevMI, Dist)); 1575239462Sdim DistanceMap[MI] = ++Dist; 1576239462Sdim 1577249423Sdim if (LIS) { 1578309124Sdim LastCopyIdx = LIS->InsertMachineInstrInMaps(*PrevMI).getRegSlot(); 1579239462Sdim 1580360784Sdim if (Register::isVirtualRegister(RegA)) { 1581249423Sdim LiveInterval &LI = LIS->getInterval(RegA); 1582249423Sdim VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator()); 1583249423Sdim SlotIndex endIdx = 1584309124Sdim LIS->getInstructionIndex(*MI).getRegSlot(IsEarlyClobber); 1585261991Sdim LI.addSegment(LiveInterval::Segment(LastCopyIdx, endIdx, VNI)); 1586249423Sdim } 1587249423Sdim } 1588249423Sdim 1589341825Sdim LLVM_DEBUG(dbgs() << "\t\tprepend:\t" << *MIB); 1590239462Sdim 1591239462Sdim MachineOperand &MO = MI->getOperand(SrcIdx); 1592239462Sdim assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() && 1593239462Sdim "inconsistent operand info for 2-reg pass"); 1594239462Sdim if (MO.isKill()) { 1595239462Sdim MO.setIsKill(false); 1596239462Sdim RemovedKillFlag = true; 1597239462Sdim } 1598239462Sdim 1599239462Sdim // Make sure regA is a legal regclass for the SrcIdx operand. 1600360784Sdim if (Register::isVirtualRegister(RegA) && Register::isVirtualRegister(RegB)) 1601276479Sdim MRI->constrainRegClass(RegA, RC); 1602239462Sdim MO.setReg(RegA); 1603276479Sdim // The getMatchingSuper asserts guarantee that the register class projected 1604276479Sdim // by SubRegB is compatible with RegA with no subregister. So regardless of 1605276479Sdim // whether the dest oper writes a subreg, the source oper should not. 1606276479Sdim MO.setSubReg(0); 1607239462Sdim 1608239462Sdim // Propagate SrcRegMap. 1609239462Sdim SrcRegMap[RegA] = RegB; 1610239462Sdim } 1611239462Sdim 1612239462Sdim if (AllUsesCopied) { 1613344779Sdim bool ReplacedAllUntiedUses = true; 1614239462Sdim if (!IsEarlyClobber) { 1615239462Sdim // Replace other (un-tied) uses of regB with LastCopiedReg. 1616296417Sdim for (MachineOperand &MO : MI->operands()) { 1617344779Sdim if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) { 1618344779Sdim if (MO.getSubReg() == SubRegB) { 1619344779Sdim if (MO.isKill()) { 1620344779Sdim MO.setIsKill(false); 1621344779Sdim RemovedKillFlag = true; 1622344779Sdim } 1623344779Sdim MO.setReg(LastCopiedReg); 1624344779Sdim MO.setSubReg(0); 1625344779Sdim } else { 1626344779Sdim ReplacedAllUntiedUses = false; 1627239462Sdim } 1628239462Sdim } 1629239462Sdim } 1630239462Sdim } 1631239462Sdim 1632239462Sdim // Update live variables for regB. 1633344779Sdim if (RemovedKillFlag && ReplacedAllUntiedUses && 1634344779Sdim LV && LV->getVarInfo(RegB).removeKill(*MI)) { 1635239462Sdim MachineBasicBlock::iterator PrevMI = MI; 1636239462Sdim --PrevMI; 1637309124Sdim LV->addVirtualRegisterKilled(RegB, *PrevMI); 1638239462Sdim } 1639239462Sdim 1640249423Sdim // Update LiveIntervals. 1641249423Sdim if (LIS) { 1642249423Sdim LiveInterval &LI = LIS->getInterval(RegB); 1643309124Sdim SlotIndex MIIdx = LIS->getInstructionIndex(*MI); 1644249423Sdim LiveInterval::const_iterator I = LI.find(MIIdx); 1645249423Sdim assert(I != LI.end() && "RegB must be live-in to use."); 1646249423Sdim 1647249423Sdim SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber); 1648249423Sdim if (I->end == UseIdx) 1649261991Sdim LI.removeSegment(LastCopyIdx, UseIdx); 1650249423Sdim } 1651239462Sdim } else if (RemovedKillFlag) { 1652239462Sdim // Some tied uses of regB matched their destination registers, so 1653239462Sdim // regB is still used in this instruction, but a kill flag was 1654239462Sdim // removed from a different tied use of regB, so now we need to add 1655239462Sdim // a kill flag to one of the remaining uses of regB. 1656296417Sdim for (MachineOperand &MO : MI->operands()) { 1657239462Sdim if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) { 1658239462Sdim MO.setIsKill(true); 1659239462Sdim break; 1660239462Sdim } 1661239462Sdim } 1662239462Sdim } 1663239462Sdim} 1664239462Sdim 1665296417Sdim/// Reduce two-address instructions to two operands. 1666239462Sdimbool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) { 1667239462Sdim MF = &Func; 1668239462Sdim const TargetMachine &TM = MF->getTarget(); 1669239462Sdim MRI = &MF->getRegInfo(); 1670288943Sdim TII = MF->getSubtarget().getInstrInfo(); 1671288943Sdim TRI = MF->getSubtarget().getRegisterInfo(); 1672288943Sdim InstrItins = MF->getSubtarget().getInstrItineraryData(); 1673193323Sed LV = getAnalysisIfAvailable<LiveVariables>(); 1674239462Sdim LIS = getAnalysisIfAvailable<LiveIntervals>(); 1675321369Sdim if (auto *AAPass = getAnalysisIfAvailable<AAResultsWrapperPass>()) 1676321369Sdim AA = &AAPass->getAAResults(); 1677321369Sdim else 1678321369Sdim AA = nullptr; 1679234353Sdim OptLevel = TM.getOptLevel(); 1680327952Sdim // Disable optimizations if requested. We cannot skip the whole pass as some 1681327952Sdim // fixups are necessary for correctness. 1682327952Sdim if (skipFunction(Func.getFunction())) 1683327952Sdim OptLevel = CodeGenOpt::None; 1684193323Sed 1685193323Sed bool MadeChange = false; 1686193323Sed 1687341825Sdim LLVM_DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n"); 1688341825Sdim LLVM_DEBUG(dbgs() << "********** Function: " << MF->getName() << '\n'); 1689193323Sed 1690226633Sdim // This pass takes the function out of SSA form. 1691226633Sdim MRI->leaveSSA(); 1692226633Sdim 1693239462Sdim TiedOperandMap TiedOperands; 1694243830Sdim for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 1695243830Sdim MBBI != MBBE; ++MBBI) { 1696296417Sdim MBB = &*MBBI; 1697193323Sed unsigned Dist = 0; 1698193323Sed DistanceMap.clear(); 1699193323Sed SrcRegMap.clear(); 1700193323Sed DstRegMap.clear(); 1701193323Sed Processed.clear(); 1702327952Sdim SunkInstrs.clear(); 1703243830Sdim for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end(); 1704193323Sed mi != me; ) { 1705276479Sdim MachineBasicBlock::iterator nmi = std::next(mi); 1706327952Sdim // Don't revisit an instruction previously converted by target. It may 1707327952Sdim // contain undef register operands (%noreg), which are not handled. 1708341825Sdim if (mi->isDebugInstr() || SunkInstrs.count(&*mi)) { 1709203954Srdivacky mi = nmi; 1710203954Srdivacky continue; 1711203954Srdivacky } 1712206083Srdivacky 1713249423Sdim // Expand REG_SEQUENCE instructions. This will position mi at the first 1714249423Sdim // expanded instruction. 1715208599Srdivacky if (mi->isRegSequence()) 1716249423Sdim eliminateRegSequence(mi); 1717208599Srdivacky 1718309124Sdim DistanceMap.insert(std::make_pair(&*mi, ++Dist)); 1719193323Sed 1720243830Sdim processCopy(&*mi); 1721193323Sed 1722198090Srdivacky // First scan through all the tied register uses in this instruction 1723198090Srdivacky // and record a list of pairs of tied operands for each register. 1724309124Sdim if (!collectTiedOperands(&*mi, TiedOperands)) { 1725239462Sdim mi = nmi; 1726239462Sdim continue; 1727198090Srdivacky } 1728193323Sed 1729239462Sdim ++NumTwoAddressInstrs; 1730239462Sdim MadeChange = true; 1731341825Sdim LLVM_DEBUG(dbgs() << '\t' << *mi); 1732193323Sed 1733239462Sdim // If the instruction has a single pair of tied operands, try some 1734239462Sdim // transformations that may either eliminate the tied operands or 1735239462Sdim // improve the opportunities for coalescing away the register copy. 1736239462Sdim if (TiedOperands.size() == 1) { 1737327952Sdim SmallVectorImpl<std::pair<unsigned, unsigned>> &TiedPairs 1738239462Sdim = TiedOperands.begin()->second; 1739239462Sdim if (TiedPairs.size() == 1) { 1740198090Srdivacky unsigned SrcIdx = TiedPairs[0].first; 1741198090Srdivacky unsigned DstIdx = TiedPairs[0].second; 1742360784Sdim Register SrcReg = mi->getOperand(SrcIdx).getReg(); 1743360784Sdim Register DstReg = mi->getOperand(DstIdx).getReg(); 1744239462Sdim if (SrcReg != DstReg && 1745249423Sdim tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) { 1746296417Sdim // The tied operands have been eliminated or shifted further down 1747296417Sdim // the block to ease elimination. Continue processing with 'nmi'. 1748239462Sdim TiedOperands.clear(); 1749239462Sdim mi = nmi; 1750198090Srdivacky continue; 1751198090Srdivacky } 1752198090Srdivacky } 1753239462Sdim } 1754193323Sed 1755239462Sdim // Now iterate over the information collected above. 1756296417Sdim for (auto &TO : TiedOperands) { 1757309124Sdim processTiedPairs(&*mi, TO.second, Dist); 1758341825Sdim LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi); 1759239462Sdim } 1760193323Sed 1761239462Sdim // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form. 1762239462Sdim if (mi->isInsertSubreg()) { 1763239462Sdim // From %reg = INSERT_SUBREG %reg, %subreg, subidx 1764239462Sdim // To %reg:subidx = COPY %subreg 1765239462Sdim unsigned SubIdx = mi->getOperand(3).getImm(); 1766239462Sdim mi->RemoveOperand(3); 1767239462Sdim assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx"); 1768239462Sdim mi->getOperand(0).setSubReg(SubIdx); 1769239462Sdim mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef()); 1770239462Sdim mi->RemoveOperand(1); 1771239462Sdim mi->setDesc(TII->get(TargetOpcode::COPY)); 1772341825Sdim LLVM_DEBUG(dbgs() << "\t\tconvert to:\t" << *mi); 1773210299Sed } 1774210299Sed 1775198090Srdivacky // Clear TiedOperands here instead of at the top of the loop 1776198090Srdivacky // since most instructions do not have tied operands. 1777198090Srdivacky TiedOperands.clear(); 1778193323Sed mi = nmi; 1779193323Sed } 1780193323Sed } 1781193323Sed 1782249423Sdim if (LIS) 1783249423Sdim MF->verify(this, "After two-address instruction pass"); 1784208599Srdivacky 1785193323Sed return MadeChange; 1786193323Sed} 1787208599Srdivacky 1788249423Sdim/// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process. 1789249423Sdim/// 1790249423Sdim/// The instruction is turned into a sequence of sub-register copies: 1791249423Sdim/// 1792249423Sdim/// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1 1793249423Sdim/// 1794249423Sdim/// Becomes: 1795249423Sdim/// 1796327952Sdim/// undef %dst:ssub0 = COPY %v1 1797327952Sdim/// %dst:ssub1 = COPY %v2 1798249423Sdimvoid TwoAddressInstructionPass:: 1799249423SdimeliminateRegSequence(MachineBasicBlock::iterator &MBBI) { 1800309124Sdim MachineInstr &MI = *MBBI; 1801360784Sdim Register DstReg = MI.getOperand(0).getReg(); 1802360784Sdim if (MI.getOperand(0).getSubReg() || Register::isPhysicalRegister(DstReg) || 1803309124Sdim !(MI.getNumOperands() & 1)) { 1804341825Sdim LLVM_DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << MI); 1805276479Sdim llvm_unreachable(nullptr); 1806208599Srdivacky } 1807208599Srdivacky 1808249423Sdim SmallVector<unsigned, 4> OrigRegs; 1809249423Sdim if (LIS) { 1810309124Sdim OrigRegs.push_back(MI.getOperand(0).getReg()); 1811309124Sdim for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) 1812309124Sdim OrigRegs.push_back(MI.getOperand(i).getReg()); 1813249423Sdim } 1814234353Sdim 1815249423Sdim bool DefEmitted = false; 1816309124Sdim for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) { 1817309124Sdim MachineOperand &UseMO = MI.getOperand(i); 1818360784Sdim Register SrcReg = UseMO.getReg(); 1819309124Sdim unsigned SubIdx = MI.getOperand(i+1).getImm(); 1820327952Sdim // Nothing needs to be inserted for undef operands. 1821249423Sdim if (UseMO.isUndef()) 1822249423Sdim continue; 1823234353Sdim 1824249423Sdim // Defer any kill flag to the last operand using SrcReg. Otherwise, we 1825249423Sdim // might insert a COPY that uses SrcReg after is was killed. 1826249423Sdim bool isKill = UseMO.isKill(); 1827249423Sdim if (isKill) 1828249423Sdim for (unsigned j = i + 2; j < e; j += 2) 1829309124Sdim if (MI.getOperand(j).getReg() == SrcReg) { 1830309124Sdim MI.getOperand(j).setIsKill(); 1831249423Sdim UseMO.setIsKill(false); 1832249423Sdim isKill = false; 1833249423Sdim break; 1834249423Sdim } 1835208599Srdivacky 1836249423Sdim // Insert the sub-register copy. 1837309124Sdim MachineInstr *CopyMI = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), 1838249423Sdim TII->get(TargetOpcode::COPY)) 1839309124Sdim .addReg(DstReg, RegState::Define, SubIdx) 1840321369Sdim .add(UseMO); 1841208599Srdivacky 1842327952Sdim // The first def needs an undef flag because there is no live register 1843249423Sdim // before it. 1844249423Sdim if (!DefEmitted) { 1845249423Sdim CopyMI->getOperand(0).setIsUndef(true); 1846249423Sdim // Return an iterator pointing to the first inserted instr. 1847249423Sdim MBBI = CopyMI; 1848208599Srdivacky } 1849249423Sdim DefEmitted = true; 1850208599Srdivacky 1851249423Sdim // Update LiveVariables' kill info. 1852360784Sdim if (LV && isKill && !Register::isPhysicalRegister(SrcReg)) 1853309124Sdim LV->replaceKillInstruction(SrcReg, MI, *CopyMI); 1854208599Srdivacky 1855341825Sdim LLVM_DEBUG(dbgs() << "Inserted: " << *CopyMI); 1856249423Sdim } 1857208599Srdivacky 1858249423Sdim MachineBasicBlock::iterator EndMBBI = 1859276479Sdim std::next(MachineBasicBlock::iterator(MI)); 1860208599Srdivacky 1861249423Sdim if (!DefEmitted) { 1862341825Sdim LLVM_DEBUG(dbgs() << "Turned: " << MI << " into an IMPLICIT_DEF"); 1863309124Sdim MI.setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); 1864309124Sdim for (int j = MI.getNumOperands() - 1, ee = 0; j > ee; --j) 1865309124Sdim MI.RemoveOperand(j); 1866249423Sdim } else { 1867341825Sdim LLVM_DEBUG(dbgs() << "Eliminated: " << MI); 1868309124Sdim MI.eraseFromParent(); 1869208599Srdivacky } 1870208599Srdivacky 1871249423Sdim // Udpate LiveIntervals. 1872249423Sdim if (LIS) 1873249423Sdim LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs); 1874208599Srdivacky} 1875