1193323Sed//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface -------==// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the generic RegisterCoalescer interface which 11193323Sed// is used as the common interface used by all clients and 12193323Sed// implementations of register coalescing. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16235633Sdim#define DEBUG_TYPE "regalloc" 17224145Sdim#include "RegisterCoalescer.h" 18245431Sdim#include "llvm/ADT/OwningPtr.h" 19245431Sdim#include "llvm/ADT/STLExtras.h" 20245431Sdim#include "llvm/ADT/SmallSet.h" 21245431Sdim#include "llvm/ADT/Statistic.h" 22245431Sdim#include "llvm/Analysis/AliasAnalysis.h" 23193323Sed#include "llvm/CodeGen/LiveIntervalAnalysis.h" 24245431Sdim#include "llvm/CodeGen/LiveRangeEdit.h" 25224145Sdim#include "llvm/CodeGen/MachineFrameInfo.h" 26224145Sdim#include "llvm/CodeGen/MachineInstr.h" 27224145Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 28224145Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 29224145Sdim#include "llvm/CodeGen/Passes.h" 30245431Sdim#include "llvm/CodeGen/RegisterClassInfo.h" 31252723Sdim#include "llvm/CodeGen/VirtRegMap.h" 32252723Sdim#include "llvm/IR/Value.h" 33252723Sdim#include "llvm/Pass.h" 34224145Sdim#include "llvm/Support/CommandLine.h" 35224145Sdim#include "llvm/Support/Debug.h" 36224145Sdim#include "llvm/Support/ErrorHandling.h" 37224145Sdim#include "llvm/Support/raw_ostream.h" 38245431Sdim#include "llvm/Target/TargetInstrInfo.h" 39245431Sdim#include "llvm/Target/TargetMachine.h" 40245431Sdim#include "llvm/Target/TargetRegisterInfo.h" 41252723Sdim#include "llvm/Target/TargetSubtargetInfo.h" 42224145Sdim#include <algorithm> 43224145Sdim#include <cmath> 44193323Sedusing namespace llvm; 45193323Sed 46224145SdimSTATISTIC(numJoins , "Number of interval joins performed"); 47224145SdimSTATISTIC(numCrossRCs , "Number of cross class joins performed"); 48224145SdimSTATISTIC(numCommutes , "Number of instruction commuting performed"); 49224145SdimSTATISTIC(numExtends , "Number of copies extended"); 50224145SdimSTATISTIC(NumReMats , "Number of instructions re-materialized"); 51226890SdimSTATISTIC(NumInflated , "Number of register classes inflated"); 52245431SdimSTATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested"); 53245431SdimSTATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved"); 54224145Sdim 55224145Sdimstatic cl::opt<bool> 56224145SdimEnableJoining("join-liveintervals", 57224145Sdim cl::desc("Coalesce copies (default=true)"), 58224145Sdim cl::init(true)); 59224145Sdim 60252723Sdim// Temporary flag to test critical edge unsplitting. 61224145Sdimstatic cl::opt<bool> 62252723SdimEnableJoinSplits("join-splitedges", 63252723Sdim cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden); 64252723Sdim 65252723Sdim// Temporary flag to test global copy optimization. 66252723Sdimstatic cl::opt<cl::boolOrDefault> 67252723SdimEnableGlobalCopies("join-globalcopies", 68252723Sdim cl::desc("Coalesce copies that span blocks (default=subtarget)"), 69252723Sdim cl::init(cl::BOU_UNSET), cl::Hidden); 70252723Sdim 71252723Sdimstatic cl::opt<bool> 72224145SdimVerifyCoalescing("verify-coalescing", 73224145Sdim cl::desc("Verify machine instrs before and after register coalescing"), 74224145Sdim cl::Hidden); 75224145Sdim 76226890Sdimnamespace { 77245431Sdim class RegisterCoalescer : public MachineFunctionPass, 78245431Sdim private LiveRangeEdit::Delegate { 79226890Sdim MachineFunction* MF; 80226890Sdim MachineRegisterInfo* MRI; 81226890Sdim const TargetMachine* TM; 82226890Sdim const TargetRegisterInfo* TRI; 83226890Sdim const TargetInstrInfo* TII; 84226890Sdim LiveIntervals *LIS; 85226890Sdim const MachineLoopInfo* Loops; 86226890Sdim AliasAnalysis *AA; 87226890Sdim RegisterClassInfo RegClassInfo; 88226890Sdim 89252723Sdim /// \brief True if the coalescer should aggressively coalesce global copies 90252723Sdim /// in favor of keeping local copies. 91252723Sdim bool JoinGlobalCopies; 92252723Sdim 93252723Sdim /// \brief True if the coalescer should aggressively coalesce fall-thru 94252723Sdim /// blocks exclusively containing copies. 95252723Sdim bool JoinSplitEdges; 96252723Sdim 97245431Sdim /// WorkList - Copy instructions yet to be coalesced. 98245431Sdim SmallVector<MachineInstr*, 8> WorkList; 99252723Sdim SmallVector<MachineInstr*, 8> LocalWorkList; 100226890Sdim 101245431Sdim /// ErasedInstrs - Set of instruction pointers that have been erased, and 102245431Sdim /// that may be present in WorkList. 103245431Sdim SmallPtrSet<MachineInstr*, 8> ErasedInstrs; 104226890Sdim 105245431Sdim /// Dead instructions that are about to be deleted. 106245431Sdim SmallVector<MachineInstr*, 8> DeadDefs; 107226890Sdim 108245431Sdim /// Virtual registers to be considered for register class inflation. 109245431Sdim SmallVector<unsigned, 8> InflateRegs; 110226890Sdim 111245431Sdim /// Recursively eliminate dead defs in DeadDefs. 112245431Sdim void eliminateDeadDefs(); 113226890Sdim 114245431Sdim /// LiveRangeEdit callback. 115245431Sdim void LRE_WillEraseInstruction(MachineInstr *MI); 116245431Sdim 117252723Sdim /// coalesceLocals - coalesce the LocalWorkList. 118252723Sdim void coalesceLocals(); 119252723Sdim 120245431Sdim /// joinAllIntervals - join compatible live intervals 121245431Sdim void joinAllIntervals(); 122245431Sdim 123245431Sdim /// copyCoalesceInMBB - Coalesce copies in the specified MBB, putting 124245431Sdim /// copies that cannot yet be coalesced into WorkList. 125245431Sdim void copyCoalesceInMBB(MachineBasicBlock *MBB); 126245431Sdim 127252723Sdim /// copyCoalesceWorkList - Try to coalesce all copies in CurrList. Return 128252723Sdim /// true if any progress was made. 129252723Sdim bool copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList); 130245431Sdim 131245431Sdim /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 132226890Sdim /// which are the src/dst of the copy instruction CopyMI. This returns 133226890Sdim /// true if the copy was successfully coalesced away. If it is not 134226890Sdim /// currently possible to coalesce this interval, but it may be possible if 135226890Sdim /// other things get coalesced, then it returns true by reference in 136226890Sdim /// 'Again'. 137245431Sdim bool joinCopy(MachineInstr *TheCopy, bool &Again); 138226890Sdim 139245431Sdim /// joinIntervals - Attempt to join these two intervals. On failure, this 140226890Sdim /// returns false. The output "SrcInt" will not have been modified, so we 141226890Sdim /// can use this information below to update aliases. 142245431Sdim bool joinIntervals(CoalescerPair &CP); 143226890Sdim 144245431Sdim /// Attempt joining two virtual registers. Return true on success. 145245431Sdim bool joinVirtRegs(CoalescerPair &CP); 146245431Sdim 147245431Sdim /// Attempt joining with a reserved physreg. 148245431Sdim bool joinReservedPhysReg(CoalescerPair &CP); 149245431Sdim 150245431Sdim /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy. If 151226890Sdim /// the source value number is defined by a copy from the destination reg 152226890Sdim /// see if we can merge these two destination reg valno# into a single 153226890Sdim /// value number, eliminating a copy. 154245431Sdim bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 155226890Sdim 156245431Sdim /// hasOtherReachingDefs - Return true if there are definitions of IntB 157226890Sdim /// other than BValNo val# that can reach uses of AValno val# of IntA. 158245431Sdim bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 159226890Sdim VNInfo *AValNo, VNInfo *BValNo); 160226890Sdim 161245431Sdim /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy. 162226890Sdim /// If the source value number is defined by a commutable instruction and 163226890Sdim /// its other operand is coalesced to the copy dest register, see if we 164226890Sdim /// can transform the copy into a noop by commuting the definition. 165245431Sdim bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 166226890Sdim 167245431Sdim /// reMaterializeTrivialDef - If the source of a copy is defined by a 168226890Sdim /// trivial computation, replace the copy by rematerialize the definition. 169263509Sdim bool reMaterializeTrivialDef(CoalescerPair &CP, MachineInstr *CopyMI, 170263509Sdim bool &IsDefCopy); 171226890Sdim 172245431Sdim /// canJoinPhys - Return true if a physreg copy should be joined. 173252723Sdim bool canJoinPhys(const CoalescerPair &CP); 174226890Sdim 175245431Sdim /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 176226890Sdim /// update the subregister number if it is not zero. If DstReg is a 177226890Sdim /// physical register and the existing subregister number of the def / use 178226890Sdim /// being updated is not zero, make sure to set it to the correct physical 179226890Sdim /// subregister. 180245431Sdim void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx); 181226890Sdim 182226890Sdim /// eliminateUndefCopy - Handle copies of undef values. 183226890Sdim bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP); 184226890Sdim 185226890Sdim public: 186226890Sdim static char ID; // Class identification, replacement for typeinfo 187226890Sdim RegisterCoalescer() : MachineFunctionPass(ID) { 188226890Sdim initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 189226890Sdim } 190226890Sdim 191226890Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const; 192226890Sdim 193226890Sdim virtual void releaseMemory(); 194226890Sdim 195226890Sdim /// runOnMachineFunction - pass entry point 196226890Sdim virtual bool runOnMachineFunction(MachineFunction&); 197226890Sdim 198226890Sdim /// print - Implement the dump method. 199226890Sdim virtual void print(raw_ostream &O, const Module* = 0) const; 200226890Sdim }; 201226890Sdim} /// end anonymous namespace 202226890Sdim 203235633Sdimchar &llvm::RegisterCoalescerID = RegisterCoalescer::ID; 204226890Sdim 205224145SdimINITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 206224145Sdim "Simple Register Coalescing", false, false) 207224145SdimINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 208224145SdimINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 209224145SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 210224145SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 211224145SdimINITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 212224145Sdim "Simple Register Coalescing", false, false) 213224145Sdim 214193323Sedchar RegisterCoalescer::ID = 0; 215193323Sed 216224145Sdimstatic bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, 217224145Sdim unsigned &Src, unsigned &Dst, 218224145Sdim unsigned &SrcSub, unsigned &DstSub) { 219210299Sed if (MI->isCopy()) { 220210299Sed Dst = MI->getOperand(0).getReg(); 221210299Sed DstSub = MI->getOperand(0).getSubReg(); 222210299Sed Src = MI->getOperand(1).getReg(); 223210299Sed SrcSub = MI->getOperand(1).getSubReg(); 224210299Sed } else if (MI->isSubregToReg()) { 225210299Sed Dst = MI->getOperand(0).getReg(); 226245431Sdim DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(), 227245431Sdim MI->getOperand(3).getImm()); 228210299Sed Src = MI->getOperand(2).getReg(); 229210299Sed SrcSub = MI->getOperand(2).getSubReg(); 230212904Sdim } else 231210299Sed return false; 232210299Sed return true; 233210299Sed} 234210299Sed 235252723Sdim// Return true if this block should be vacated by the coalescer to eliminate 236252723Sdim// branches. The important cases to handle in the coalescer are critical edges 237252723Sdim// split during phi elimination which contain only copies. Simple blocks that 238252723Sdim// contain non-branches should also be vacated, but this can be handled by an 239252723Sdim// earlier pass similar to early if-conversion. 240252723Sdimstatic bool isSplitEdge(const MachineBasicBlock *MBB) { 241252723Sdim if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 242252723Sdim return false; 243252723Sdim 244252723Sdim for (MachineBasicBlock::const_iterator MII = MBB->begin(), E = MBB->end(); 245252723Sdim MII != E; ++MII) { 246252723Sdim if (!MII->isCopyLike() && !MII->isUnconditionalBranch()) 247252723Sdim return false; 248252723Sdim } 249252723Sdim return true; 250252723Sdim} 251252723Sdim 252210299Sedbool CoalescerPair::setRegisters(const MachineInstr *MI) { 253245431Sdim SrcReg = DstReg = 0; 254245431Sdim SrcIdx = DstIdx = 0; 255226890Sdim NewRC = 0; 256226890Sdim Flipped = CrossClass = false; 257210299Sed 258210299Sed unsigned Src, Dst, SrcSub, DstSub; 259226890Sdim if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 260210299Sed return false; 261226890Sdim Partial = SrcSub || DstSub; 262210299Sed 263210299Sed // If one register is a physreg, it must be Dst. 264210299Sed if (TargetRegisterInfo::isPhysicalRegister(Src)) { 265210299Sed if (TargetRegisterInfo::isPhysicalRegister(Dst)) 266210299Sed return false; 267210299Sed std::swap(Src, Dst); 268210299Sed std::swap(SrcSub, DstSub); 269226890Sdim Flipped = true; 270210299Sed } 271210299Sed 272210299Sed const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 273210299Sed 274210299Sed if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 275210299Sed // Eliminate DstSub on a physreg. 276210299Sed if (DstSub) { 277226890Sdim Dst = TRI.getSubReg(Dst, DstSub); 278210299Sed if (!Dst) return false; 279210299Sed DstSub = 0; 280210299Sed } 281210299Sed 282210299Sed // Eliminate SrcSub by picking a corresponding Dst superregister. 283210299Sed if (SrcSub) { 284226890Sdim Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 285210299Sed if (!Dst) return false; 286210299Sed SrcSub = 0; 287210299Sed } else if (!MRI.getRegClass(Src)->contains(Dst)) { 288210299Sed return false; 289210299Sed } 290210299Sed } else { 291210299Sed // Both registers are virtual. 292245431Sdim const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 293245431Sdim const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 294210299Sed 295210299Sed // Both registers have subreg indices. 296210299Sed if (SrcSub && DstSub) { 297245431Sdim // Copies between different sub-registers are never coalescable. 298245431Sdim if (Src == Dst && SrcSub != DstSub) 299210299Sed return false; 300245431Sdim 301245431Sdim NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, 302245431Sdim SrcIdx, DstIdx); 303245431Sdim if (!NewRC) 304210299Sed return false; 305245431Sdim } else if (DstSub) { 306245431Sdim // SrcReg will be merged with a sub-register of DstReg. 307245431Sdim SrcIdx = DstSub; 308245431Sdim NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 309245431Sdim } else if (SrcSub) { 310245431Sdim // DstReg will be merged with a sub-register of SrcReg. 311245431Sdim DstIdx = SrcSub; 312245431Sdim NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub); 313245431Sdim } else { 314245431Sdim // This is a straight copy without sub-registers. 315245431Sdim NewRC = TRI.getCommonSubClass(DstRC, SrcRC); 316210299Sed } 317210299Sed 318245431Sdim // The combined constraint may be impossible to satisfy. 319245431Sdim if (!NewRC) 320245431Sdim return false; 321245431Sdim 322245431Sdim // Prefer SrcReg to be a sub-register of DstReg. 323245431Sdim // FIXME: Coalescer should support subregs symmetrically. 324245431Sdim if (DstIdx && !SrcIdx) { 325210299Sed std::swap(Src, Dst); 326245431Sdim std::swap(SrcIdx, DstIdx); 327245431Sdim Flipped = !Flipped; 328210299Sed } 329210299Sed 330226890Sdim CrossClass = NewRC != DstRC || NewRC != SrcRC; 331210299Sed } 332210299Sed // Check our invariants 333210299Sed assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 334210299Sed assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 335210299Sed "Cannot have a physical SubIdx"); 336226890Sdim SrcReg = Src; 337226890Sdim DstReg = Dst; 338210299Sed return true; 339210299Sed} 340210299Sed 341210299Sedbool CoalescerPair::flip() { 342245431Sdim if (TargetRegisterInfo::isPhysicalRegister(DstReg)) 343210299Sed return false; 344226890Sdim std::swap(SrcReg, DstReg); 345245431Sdim std::swap(SrcIdx, DstIdx); 346226890Sdim Flipped = !Flipped; 347210299Sed return true; 348210299Sed} 349210299Sed 350210299Sedbool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 351210299Sed if (!MI) 352210299Sed return false; 353210299Sed unsigned Src, Dst, SrcSub, DstSub; 354226890Sdim if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 355210299Sed return false; 356210299Sed 357226890Sdim // Find the virtual register that is SrcReg. 358226890Sdim if (Dst == SrcReg) { 359210299Sed std::swap(Src, Dst); 360210299Sed std::swap(SrcSub, DstSub); 361226890Sdim } else if (Src != SrcReg) { 362210299Sed return false; 363210299Sed } 364210299Sed 365226890Sdim // Now check that Dst matches DstReg. 366226890Sdim if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 367210299Sed if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 368210299Sed return false; 369245431Sdim assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state."); 370210299Sed // DstSub could be set for a physreg from INSERT_SUBREG. 371210299Sed if (DstSub) 372226890Sdim Dst = TRI.getSubReg(Dst, DstSub); 373210299Sed // Full copy of Src. 374210299Sed if (!SrcSub) 375226890Sdim return DstReg == Dst; 376210299Sed // This is a partial register copy. Check that the parts match. 377226890Sdim return TRI.getSubReg(DstReg, SrcSub) == Dst; 378210299Sed } else { 379226890Sdim // DstReg is virtual. 380226890Sdim if (DstReg != Dst) 381210299Sed return false; 382210299Sed // Registers match, do the subregisters line up? 383245431Sdim return TRI.composeSubRegIndices(SrcIdx, SrcSub) == 384245431Sdim TRI.composeSubRegIndices(DstIdx, DstSub); 385210299Sed } 386210299Sed} 387210299Sed 388224145Sdimvoid RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 389224145Sdim AU.setPreservesCFG(); 390224145Sdim AU.addRequired<AliasAnalysis>(); 391224145Sdim AU.addRequired<LiveIntervals>(); 392224145Sdim AU.addPreserved<LiveIntervals>(); 393224145Sdim AU.addPreserved<SlotIndexes>(); 394224145Sdim AU.addRequired<MachineLoopInfo>(); 395224145Sdim AU.addPreserved<MachineLoopInfo>(); 396224145Sdim AU.addPreservedID(MachineDominatorsID); 397224145Sdim MachineFunctionPass::getAnalysisUsage(AU); 398224145Sdim} 399224145Sdim 400245431Sdimvoid RegisterCoalescer::eliminateDeadDefs() { 401263509Sdim SmallVector<unsigned, 8> NewRegs; 402245431Sdim LiveRangeEdit(0, NewRegs, *MF, *LIS, 0, this).eliminateDeadDefs(DeadDefs); 403245431Sdim} 404224145Sdim 405245431Sdim// Callback from eliminateDeadDefs(). 406245431Sdimvoid RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) { 407245431Sdim // MI may be in WorkList. Make sure we don't visit it. 408245431Sdim ErasedInstrs.insert(MI); 409224145Sdim} 410224145Sdim 411245431Sdim/// adjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 412224145Sdim/// being the source and IntB being the dest, thus this defines a value number 413224145Sdim/// in IntB. If the source value number (in IntA) is defined by a copy from B, 414224145Sdim/// see if we can merge these two pieces of B into a single value number, 415224145Sdim/// eliminating a copy. For example: 416224145Sdim/// 417224145Sdim/// A3 = B0 418224145Sdim/// ... 419224145Sdim/// B1 = A3 <- this copy 420224145Sdim/// 421224145Sdim/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 422224145Sdim/// value number to be replaced with B0 (which simplifies the B liveinterval). 423224145Sdim/// 424224145Sdim/// This returns true if an interval was modified. 425224145Sdim/// 426245431Sdimbool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, 427245431Sdim MachineInstr *CopyMI) { 428245431Sdim assert(!CP.isPartial() && "This doesn't work for partial copies."); 429245431Sdim assert(!CP.isPhys() && "This doesn't work for physreg copies."); 430224145Sdim 431224145Sdim LiveInterval &IntA = 432226890Sdim LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 433224145Sdim LiveInterval &IntB = 434226890Sdim LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 435235633Sdim SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 436224145Sdim 437263509Sdim // BValNo is a value number in B that is defined by a copy from A. 'B1' in 438224145Sdim // the example above. 439263509Sdim LiveInterval::iterator BS = IntB.FindSegmentContaining(CopyIdx); 440263509Sdim if (BS == IntB.end()) return false; 441263509Sdim VNInfo *BValNo = BS->valno; 442224145Sdim 443224145Sdim // Get the location that B is defined at. Two options: either this value has 444224145Sdim // an unknown definition point or it is defined at CopyIdx. If unknown, we 445224145Sdim // can't process it. 446235633Sdim if (BValNo->def != CopyIdx) return false; 447224145Sdim 448224145Sdim // AValNo is the value number in A that defines the copy, A3 in the example. 449235633Sdim SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true); 450263509Sdim LiveInterval::iterator AS = IntA.FindSegmentContaining(CopyUseIdx); 451263509Sdim // The live segment might not exist after fun with physreg coalescing. 452263509Sdim if (AS == IntA.end()) return false; 453263509Sdim VNInfo *AValNo = AS->valno; 454224145Sdim 455224145Sdim // If AValNo is defined as a copy from IntB, we can potentially process this. 456224145Sdim // Get the instruction that defines this value number. 457235633Sdim MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def); 458245431Sdim // Don't allow any partial copies, even if isCoalescable() allows them. 459245431Sdim if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy()) 460224145Sdim return false; 461224145Sdim 462263509Sdim // Get the Segment in IntB that this value number starts with. 463263509Sdim LiveInterval::iterator ValS = 464263509Sdim IntB.FindSegmentContaining(AValNo->def.getPrevSlot()); 465263509Sdim if (ValS == IntB.end()) 466224145Sdim return false; 467224145Sdim 468263509Sdim // Make sure that the end of the live segment is inside the same block as 469224145Sdim // CopyMI. 470263509Sdim MachineInstr *ValSEndInst = 471263509Sdim LIS->getInstructionFromIndex(ValS->end.getPrevSlot()); 472263509Sdim if (!ValSEndInst || ValSEndInst->getParent() != CopyMI->getParent()) 473224145Sdim return false; 474224145Sdim 475263509Sdim // Okay, we now know that ValS ends in the same block that the CopyMI 476263509Sdim // live-range starts. If there are no intervening live segments between them 477263509Sdim // in IntB, we can merge them. 478263509Sdim if (ValS+1 != BS) return false; 479224145Sdim 480245431Sdim DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI)); 481224145Sdim 482263509Sdim SlotIndex FillerStart = ValS->end, FillerEnd = BS->start; 483224145Sdim // We are about to delete CopyMI, so need to remove it as the 'instruction 484224145Sdim // that defines this value #'. Update the valnum with the new defining 485224145Sdim // instruction #. 486235633Sdim BValNo->def = FillerStart; 487224145Sdim 488224145Sdim // Okay, we can merge them. We need to insert a new liverange: 489263509Sdim // [ValS.end, BS.begin) of either value number, then we merge the 490224145Sdim // two value numbers. 491263509Sdim IntB.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, BValNo)); 492224145Sdim 493224145Sdim // Okay, merge "B1" into the same value number as "B0". 494263509Sdim if (BValNo != ValS->valno) 495263509Sdim IntB.MergeValueNumberInto(BValNo, ValS->valno); 496245431Sdim DEBUG(dbgs() << " result = " << IntB << '\n'); 497224145Sdim 498224145Sdim // If the source instruction was killing the source register before the 499224145Sdim // merge, unset the isKill marker given the live range has been extended. 500263509Sdim int UIdx = ValSEndInst->findRegisterUseOperandIdx(IntB.reg, true); 501224145Sdim if (UIdx != -1) { 502263509Sdim ValSEndInst->getOperand(UIdx).setIsKill(false); 503224145Sdim } 504224145Sdim 505235633Sdim // Rewrite the copy. If the copy instruction was killing the destination 506235633Sdim // register before the merge, find the last use and trim the live range. That 507235633Sdim // will also add the isKill marker. 508245431Sdim CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); 509263509Sdim if (AS->end == CopyIdx) 510226890Sdim LIS->shrinkToUses(&IntA); 511224145Sdim 512224145Sdim ++numExtends; 513224145Sdim return true; 514224145Sdim} 515224145Sdim 516245431Sdim/// hasOtherReachingDefs - Return true if there are definitions of IntB 517224145Sdim/// other than BValNo val# that can reach uses of AValno val# of IntA. 518245431Sdimbool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, 519245431Sdim LiveInterval &IntB, 520245431Sdim VNInfo *AValNo, 521245431Sdim VNInfo *BValNo) { 522245431Sdim // If AValNo has PHI kills, conservatively assume that IntB defs can reach 523245431Sdim // the PHI values. 524245431Sdim if (LIS->hasPHIKill(IntA, AValNo)) 525245431Sdim return true; 526245431Sdim 527224145Sdim for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 528224145Sdim AI != AE; ++AI) { 529224145Sdim if (AI->valno != AValNo) continue; 530263509Sdim LiveInterval::iterator BI = 531263509Sdim std::upper_bound(IntB.begin(), IntB.end(), AI->start); 532263509Sdim if (BI != IntB.begin()) 533224145Sdim --BI; 534263509Sdim for (; BI != IntB.end() && AI->end >= BI->start; ++BI) { 535224145Sdim if (BI->valno == BValNo) 536224145Sdim continue; 537224145Sdim if (BI->start <= AI->start && BI->end > AI->start) 538224145Sdim return true; 539224145Sdim if (BI->start > AI->start && BI->start < AI->end) 540224145Sdim return true; 541224145Sdim } 542224145Sdim } 543224145Sdim return false; 544224145Sdim} 545224145Sdim 546245431Sdim/// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with 547224145Sdim/// IntA being the source and IntB being the dest, thus this defines a value 548224145Sdim/// number in IntB. If the source value number (in IntA) is defined by a 549224145Sdim/// commutable instruction and its other operand is coalesced to the copy dest 550224145Sdim/// register, see if we can transform the copy into a noop by commuting the 551224145Sdim/// definition. For example, 552224145Sdim/// 553224145Sdim/// A3 = op A2 B0<kill> 554224145Sdim/// ... 555224145Sdim/// B1 = A3 <- this copy 556224145Sdim/// ... 557224145Sdim/// = op A3 <- more uses 558224145Sdim/// 559224145Sdim/// ==> 560224145Sdim/// 561224145Sdim/// B2 = op B0 A2<kill> 562224145Sdim/// ... 563224145Sdim/// B1 = B2 <- now an identify copy 564224145Sdim/// ... 565224145Sdim/// = op B2 <- more uses 566224145Sdim/// 567224145Sdim/// This returns true if an interval was modified. 568224145Sdim/// 569245431Sdimbool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, 570245431Sdim MachineInstr *CopyMI) { 571245431Sdim assert (!CP.isPhys()); 572224145Sdim 573235633Sdim SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 574224145Sdim 575224145Sdim LiveInterval &IntA = 576226890Sdim LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 577224145Sdim LiveInterval &IntB = 578226890Sdim LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 579224145Sdim 580263509Sdim // BValNo is a value number in B that is defined by a copy from A. 'B1' in 581224145Sdim // the example above. 582224145Sdim VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 583235633Sdim if (!BValNo || BValNo->def != CopyIdx) 584224145Sdim return false; 585224145Sdim 586224145Sdim // AValNo is the value number in A that defines the copy, A3 in the example. 587235633Sdim VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 588224145Sdim assert(AValNo && "COPY source not live"); 589245431Sdim if (AValNo->isPHIDef() || AValNo->isUnused()) 590224145Sdim return false; 591226890Sdim MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 592224145Sdim if (!DefMI) 593224145Sdim return false; 594235633Sdim if (!DefMI->isCommutable()) 595224145Sdim return false; 596224145Sdim // If DefMI is a two-address instruction then commuting it will change the 597224145Sdim // destination register. 598224145Sdim int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 599224145Sdim assert(DefIdx != -1); 600224145Sdim unsigned UseOpIdx; 601224145Sdim if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 602224145Sdim return false; 603224145Sdim unsigned Op1, Op2, NewDstIdx; 604226890Sdim if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 605224145Sdim return false; 606224145Sdim if (Op1 == UseOpIdx) 607224145Sdim NewDstIdx = Op2; 608224145Sdim else if (Op2 == UseOpIdx) 609224145Sdim NewDstIdx = Op1; 610224145Sdim else 611224145Sdim return false; 612224145Sdim 613224145Sdim MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 614224145Sdim unsigned NewReg = NewDstMO.getReg(); 615263509Sdim if (NewReg != IntB.reg || !IntB.Query(AValNo->def).isKill()) 616224145Sdim return false; 617224145Sdim 618224145Sdim // Make sure there are no other definitions of IntB that would reach the 619224145Sdim // uses which the new definition can reach. 620245431Sdim if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 621224145Sdim return false; 622224145Sdim 623224145Sdim // If some of the uses of IntA.reg is already coalesced away, return false. 624224145Sdim // It's not possible to determine whether it's safe to perform the coalescing. 625226890Sdim for (MachineRegisterInfo::use_nodbg_iterator UI = 626226890Sdim MRI->use_nodbg_begin(IntA.reg), 627226890Sdim UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 628224145Sdim MachineInstr *UseMI = &*UI; 629226890Sdim SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 630263509Sdim LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx); 631263509Sdim if (US == IntA.end() || US->valno != AValNo) 632224145Sdim continue; 633245431Sdim // If this use is tied to a def, we can't rewrite the register. 634245431Sdim if (UseMI->isRegTiedToDefOperand(UI.getOperandNo())) 635224145Sdim return false; 636224145Sdim } 637224145Sdim 638245431Sdim DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t' 639224145Sdim << *DefMI); 640224145Sdim 641224145Sdim // At this point we have decided that it is legal to do this 642224145Sdim // transformation. Start by commuting the instruction. 643224145Sdim MachineBasicBlock *MBB = DefMI->getParent(); 644226890Sdim MachineInstr *NewMI = TII->commuteInstruction(DefMI); 645224145Sdim if (!NewMI) 646224145Sdim return false; 647224145Sdim if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 648224145Sdim TargetRegisterInfo::isVirtualRegister(IntB.reg) && 649226890Sdim !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 650224145Sdim return false; 651224145Sdim if (NewMI != DefMI) { 652226890Sdim LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 653235633Sdim MachineBasicBlock::iterator Pos = DefMI; 654235633Sdim MBB->insert(Pos, NewMI); 655224145Sdim MBB->erase(DefMI); 656224145Sdim } 657224145Sdim unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 658224145Sdim NewMI->getOperand(OpIdx).setIsKill(); 659224145Sdim 660224145Sdim // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 661224145Sdim // A = or A, B 662224145Sdim // ... 663224145Sdim // B = A 664224145Sdim // ... 665224145Sdim // C = A<kill> 666224145Sdim // ... 667224145Sdim // = B 668224145Sdim 669224145Sdim // Update uses of IntA of the specific Val# with IntB. 670226890Sdim for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 671226890Sdim UE = MRI->use_end(); UI != UE;) { 672224145Sdim MachineOperand &UseMO = UI.getOperand(); 673224145Sdim MachineInstr *UseMI = &*UI; 674224145Sdim ++UI; 675224145Sdim if (UseMI->isDebugValue()) { 676224145Sdim // FIXME These don't have an instruction index. Not clear we have enough 677224145Sdim // info to decide whether to do this replacement or not. For now do it. 678224145Sdim UseMO.setReg(NewReg); 679224145Sdim continue; 680224145Sdim } 681235633Sdim SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); 682263509Sdim LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx); 683263509Sdim if (US == IntA.end() || US->valno != AValNo) 684224145Sdim continue; 685245431Sdim // Kill flags are no longer accurate. They are recomputed after RA. 686245431Sdim UseMO.setIsKill(false); 687224145Sdim if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 688226890Sdim UseMO.substPhysReg(NewReg, *TRI); 689224145Sdim else 690224145Sdim UseMO.setReg(NewReg); 691224145Sdim if (UseMI == CopyMI) 692224145Sdim continue; 693224145Sdim if (!UseMI->isCopy()) 694224145Sdim continue; 695224145Sdim if (UseMI->getOperand(0).getReg() != IntB.reg || 696224145Sdim UseMI->getOperand(0).getSubReg()) 697224145Sdim continue; 698224145Sdim 699224145Sdim // This copy will become a noop. If it's defining a new val#, merge it into 700224145Sdim // BValNo. 701235633Sdim SlotIndex DefIdx = UseIdx.getRegSlot(); 702224145Sdim VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 703224145Sdim if (!DVNI) 704224145Sdim continue; 705224145Sdim DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 706224145Sdim assert(DVNI->def == DefIdx); 707224145Sdim BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 708245431Sdim ErasedInstrs.insert(UseMI); 709245431Sdim LIS->RemoveMachineInstrFromMaps(UseMI); 710245431Sdim UseMI->eraseFromParent(); 711224145Sdim } 712224145Sdim 713263509Sdim // Extend BValNo by merging in IntA live segments of AValNo. Val# definition 714224145Sdim // is updated. 715224145Sdim VNInfo *ValNo = BValNo; 716224145Sdim ValNo->def = AValNo->def; 717224145Sdim for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 718224145Sdim AI != AE; ++AI) { 719224145Sdim if (AI->valno != AValNo) continue; 720263509Sdim IntB.addSegment(LiveInterval::Segment(AI->start, AI->end, ValNo)); 721224145Sdim } 722224145Sdim DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 723224145Sdim 724224145Sdim IntA.removeValNo(AValNo); 725224145Sdim DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 726224145Sdim ++numCommutes; 727224145Sdim return true; 728224145Sdim} 729224145Sdim 730245431Sdim/// reMaterializeTrivialDef - If the source of a copy is defined by a trivial 731224145Sdim/// computation, replace the copy by rematerialize the definition. 732252723Sdimbool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, 733263509Sdim MachineInstr *CopyMI, 734263509Sdim bool &IsDefCopy) { 735263509Sdim IsDefCopy = false; 736252723Sdim unsigned SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg(); 737263509Sdim unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx(); 738252723Sdim unsigned DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg(); 739263509Sdim unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx(); 740252723Sdim if (TargetRegisterInfo::isPhysicalRegister(SrcReg)) 741252723Sdim return false; 742252723Sdim 743252723Sdim LiveInterval &SrcInt = LIS->getInterval(SrcReg); 744263509Sdim SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI); 745263509Sdim VNInfo *ValNo = SrcInt.Query(CopyIdx).valueIn(); 746263509Sdim assert(ValNo && "CopyMI input register not live"); 747226890Sdim if (ValNo->isPHIDef() || ValNo->isUnused()) 748224145Sdim return false; 749226890Sdim MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 750224145Sdim if (!DefMI) 751224145Sdim return false; 752263509Sdim if (DefMI->isCopyLike()) { 753263509Sdim IsDefCopy = true; 754263509Sdim return false; 755263509Sdim } 756235633Sdim if (!DefMI->isAsCheapAsAMove()) 757224145Sdim return false; 758226890Sdim if (!TII->isTriviallyReMaterializable(DefMI, AA)) 759224145Sdim return false; 760224145Sdim bool SawStore = false; 761226890Sdim if (!DefMI->isSafeToMove(TII, AA, SawStore)) 762224145Sdim return false; 763235633Sdim const MCInstrDesc &MCID = DefMI->getDesc(); 764224145Sdim if (MCID.getNumDefs() != 1) 765224145Sdim return false; 766252723Sdim // Only support subregister destinations when the def is read-undef. 767252723Sdim MachineOperand &DstOperand = CopyMI->getOperand(0); 768263509Sdim unsigned CopyDstReg = DstOperand.getReg(); 769252723Sdim if (DstOperand.getSubReg() && !DstOperand.isUndef()) 770252723Sdim return false; 771263509Sdim 772263509Sdim const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF); 773224145Sdim if (!DefMI->isImplicitDef()) { 774263509Sdim if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 775263509Sdim unsigned NewDstReg = DstReg; 776263509Sdim 777263509Sdim unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(), 778263509Sdim DefMI->getOperand(0).getSubReg()); 779263509Sdim if (NewDstIdx) 780263509Sdim NewDstReg = TRI->getSubReg(DstReg, NewDstIdx); 781263509Sdim 782263509Sdim // Finally, make sure that the physical subregister that will be 783263509Sdim // constructed later is permitted for the instruction. 784263509Sdim if (!DefRC->contains(NewDstReg)) 785224145Sdim return false; 786263509Sdim } else { 787263509Sdim // Theoretically, some stack frame reference could exist. Just make sure 788263509Sdim // it hasn't actually happened. 789263509Sdim assert(TargetRegisterInfo::isVirtualRegister(DstReg) && 790263509Sdim "Only expect to deal with virtual or physical registers"); 791263509Sdim } 792224145Sdim } 793224145Sdim 794224145Sdim MachineBasicBlock *MBB = CopyMI->getParent(); 795224145Sdim MachineBasicBlock::iterator MII = 796224145Sdim llvm::next(MachineBasicBlock::iterator(CopyMI)); 797263509Sdim TII->reMaterialize(*MBB, MII, DstReg, SrcIdx, DefMI, *TRI); 798224145Sdim MachineInstr *NewMI = prior(MII); 799224145Sdim 800263509Sdim LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 801263509Sdim CopyMI->eraseFromParent(); 802263509Sdim ErasedInstrs.insert(CopyMI); 803252723Sdim 804235633Sdim // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86). 805235633Sdim // We need to remember these so we can add intervals once we insert 806235633Sdim // NewMI into SlotIndexes. 807235633Sdim SmallVector<unsigned, 4> NewMIImplDefs; 808235633Sdim for (unsigned i = NewMI->getDesc().getNumOperands(), 809235633Sdim e = NewMI->getNumOperands(); i != e; ++i) { 810235633Sdim MachineOperand &MO = NewMI->getOperand(i); 811235633Sdim if (MO.isReg()) { 812235633Sdim assert(MO.isDef() && MO.isImplicit() && MO.isDead() && 813235633Sdim TargetRegisterInfo::isPhysicalRegister(MO.getReg())); 814235633Sdim NewMIImplDefs.push_back(MO.getReg()); 815235633Sdim } 816235633Sdim } 817235633Sdim 818263509Sdim if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 819263509Sdim unsigned NewIdx = NewMI->getOperand(0).getSubReg(); 820263509Sdim const TargetRegisterClass *RCForInst; 821263509Sdim if (NewIdx) 822263509Sdim RCForInst = TRI->getMatchingSuperRegClass(MRI->getRegClass(DstReg), DefRC, 823263509Sdim NewIdx); 824263509Sdim 825263509Sdim if (MRI->constrainRegClass(DstReg, DefRC)) { 826263509Sdim // The materialized instruction is quite capable of setting DstReg 827263509Sdim // directly, but it may still have a now-trivial subregister index which 828263509Sdim // we should clear. 829263509Sdim NewMI->getOperand(0).setSubReg(0); 830263509Sdim } else if (NewIdx && RCForInst) { 831263509Sdim // The subreg index on NewMI is essential; we still have to make sure 832263509Sdim // DstReg:idx is in a class that NewMI can use. 833263509Sdim MRI->constrainRegClass(DstReg, RCForInst); 834263509Sdim } else { 835263509Sdim // DstReg is actually incompatible with NewMI, we have to move to a 836263509Sdim // super-reg's class. This could come from a sequence like: 837263509Sdim // GR32 = MOV32r0 838263509Sdim // GR8 = COPY GR32:sub_8 839263509Sdim MRI->setRegClass(DstReg, CP.getNewRC()); 840263509Sdim updateRegDefsUses(DstReg, DstReg, DstIdx); 841263509Sdim NewMI->getOperand(0).setSubReg( 842263509Sdim TRI->composeSubRegIndices(SrcIdx, DefMI->getOperand(0).getSubReg())); 843263509Sdim } 844263509Sdim } else if (NewMI->getOperand(0).getReg() != CopyDstReg) { 845263509Sdim // The New instruction may be defining a sub-register of what's actually 846263509Sdim // been asked for. If so it must implicitly define the whole thing. 847263509Sdim assert(TargetRegisterInfo::isPhysicalRegister(DstReg) && 848263509Sdim "Only expect virtual or physical registers in remat"); 849263509Sdim NewMI->getOperand(0).setIsDead(true); 850263509Sdim NewMI->addOperand(MachineOperand::CreateReg(CopyDstReg, 851263509Sdim true /*IsDef*/, 852263509Sdim true /*IsImp*/, 853263509Sdim false /*IsKill*/)); 854263509Sdim } 855263509Sdim 856263509Sdim if (NewMI->getOperand(0).getSubReg()) 857263509Sdim NewMI->getOperand(0).setIsUndef(); 858263509Sdim 859224145Sdim // CopyMI may have implicit operands, transfer them over to the newly 860224145Sdim // rematerialized instruction. And update implicit def interval valnos. 861224145Sdim for (unsigned i = CopyMI->getDesc().getNumOperands(), 862224145Sdim e = CopyMI->getNumOperands(); i != e; ++i) { 863224145Sdim MachineOperand &MO = CopyMI->getOperand(i); 864235633Sdim if (MO.isReg()) { 865235633Sdim assert(MO.isImplicit() && "No explicit operands after implict operands."); 866235633Sdim // Discard VReg implicit defs. 867235633Sdim if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 868235633Sdim NewMI->addOperand(MO); 869235633Sdim } 870235633Sdim } 871224145Sdim } 872224145Sdim 873235633Sdim SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 874235633Sdim for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) { 875245431Sdim unsigned Reg = NewMIImplDefs[i]; 876245431Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 877263509Sdim if (LiveRange *LR = LIS->getCachedRegUnit(*Units)) 878263509Sdim LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); 879235633Sdim } 880235633Sdim 881224145Sdim DEBUG(dbgs() << "Remat: " << *NewMI); 882224145Sdim ++NumReMats; 883224145Sdim 884224145Sdim // The source interval can become smaller because we removed a use. 885245431Sdim LIS->shrinkToUses(&SrcInt, &DeadDefs); 886245431Sdim if (!DeadDefs.empty()) 887245431Sdim eliminateDeadDefs(); 888224145Sdim 889224145Sdim return true; 890224145Sdim} 891224145Sdim 892226890Sdim/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 893226890Sdim/// values, it only removes local variables. When we have a copy like: 894226890Sdim/// 895226890Sdim/// %vreg1 = COPY %vreg2<undef> 896226890Sdim/// 897226890Sdim/// We delete the copy and remove the corresponding value number from %vreg1. 898226890Sdim/// Any uses of that value number are marked as <undef>. 899226890Sdimbool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 900226890Sdim const CoalescerPair &CP) { 901226890Sdim SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 902226890Sdim LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 903226890Sdim if (SrcInt->liveAt(Idx)) 904226890Sdim return false; 905226890Sdim LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 906226890Sdim if (DstInt->liveAt(Idx)) 907226890Sdim return false; 908226890Sdim 909226890Sdim // No intervals are live-in to CopyMI - it is undef. 910226890Sdim if (CP.isFlipped()) 911226890Sdim DstInt = SrcInt; 912226890Sdim SrcInt = 0; 913226890Sdim 914235633Sdim VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); 915226890Sdim assert(DeadVNI && "No value defined in DstInt"); 916226890Sdim DstInt->removeValNo(DeadVNI); 917226890Sdim 918226890Sdim // Find new undef uses. 919226890Sdim for (MachineRegisterInfo::reg_nodbg_iterator 920226890Sdim I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); 921226890Sdim I != E; ++I) { 922226890Sdim MachineOperand &MO = I.getOperand(); 923226890Sdim if (MO.isDef() || MO.isUndef()) 924226890Sdim continue; 925226890Sdim MachineInstr *MI = MO.getParent(); 926226890Sdim SlotIndex Idx = LIS->getInstructionIndex(MI); 927226890Sdim if (DstInt->liveAt(Idx)) 928226890Sdim continue; 929226890Sdim MO.setIsUndef(true); 930226890Sdim DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 931226890Sdim } 932226890Sdim return true; 933226890Sdim} 934226890Sdim 935245431Sdim/// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 936224145Sdim/// update the subregister number if it is not zero. If DstReg is a 937224145Sdim/// physical register and the existing subregister number of the def / use 938224145Sdim/// being updated is not zero, make sure to set it to the correct physical 939224145Sdim/// subregister. 940245431Sdimvoid RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, 941245431Sdim unsigned DstReg, 942245431Sdim unsigned SubIdx) { 943245431Sdim bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 944245431Sdim LiveInterval *DstInt = DstIsPhys ? 0 : &LIS->getInterval(DstReg); 945224145Sdim 946245431Sdim SmallPtrSet<MachineInstr*, 8> Visited; 947226890Sdim for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); 948224145Sdim MachineInstr *UseMI = I.skipInstruction();) { 949245431Sdim // Each instruction can only be rewritten once because sub-register 950245431Sdim // composition is not always idempotent. When SrcReg != DstReg, rewriting 951245431Sdim // the UseMI operands removes them from the SrcReg use-def chain, but when 952245431Sdim // SrcReg is DstReg we could encounter UseMI twice if it has multiple 953245431Sdim // operands mentioning the virtual register. 954245431Sdim if (SrcReg == DstReg && !Visited.insert(UseMI)) 955245431Sdim continue; 956224145Sdim 957224145Sdim SmallVector<unsigned,8> Ops; 958224145Sdim bool Reads, Writes; 959224145Sdim tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 960224145Sdim 961245431Sdim // If SrcReg wasn't read, it may still be the case that DstReg is live-in 962245431Sdim // because SrcReg is a sub-register. 963245431Sdim if (DstInt && !Reads && SubIdx) 964245431Sdim Reads = DstInt->liveAt(LIS->getInstructionIndex(UseMI)); 965245431Sdim 966224145Sdim // Replace SrcReg with DstReg in all UseMI operands. 967224145Sdim for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 968224145Sdim MachineOperand &MO = UseMI->getOperand(Ops[i]); 969224145Sdim 970245431Sdim // Adjust <undef> flags in case of sub-register joins. We don't want to 971245431Sdim // turn a full def into a read-modify-write sub-register def and vice 972245431Sdim // versa. 973245431Sdim if (SubIdx && MO.isDef()) 974245431Sdim MO.setIsUndef(!Reads); 975226890Sdim 976224145Sdim if (DstIsPhys) 977226890Sdim MO.substPhysReg(DstReg, *TRI); 978224145Sdim else 979226890Sdim MO.substVirtReg(DstReg, SubIdx, *TRI); 980224145Sdim } 981224145Sdim 982224145Sdim DEBUG({ 983224145Sdim dbgs() << "\t\tupdated: "; 984224145Sdim if (!UseMI->isDebugValue()) 985226890Sdim dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 986224145Sdim dbgs() << *UseMI; 987224145Sdim }); 988224145Sdim } 989224145Sdim} 990224145Sdim 991245431Sdim/// canJoinPhys - Return true if a copy involving a physreg should be joined. 992252723Sdimbool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) { 993224145Sdim /// Always join simple intervals that are defined by a single copy from a 994224145Sdim /// reserved register. This doesn't increase register pressure, so it is 995224145Sdim /// always beneficial. 996245431Sdim if (!MRI->isReserved(CP.getDstReg())) { 997245431Sdim DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); 998224145Sdim return false; 999224145Sdim } 1000224145Sdim 1001245431Sdim LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 1002245431Sdim if (CP.isFlipped() && JoinVInt.containsOneValue()) 1003224145Sdim return true; 1004224145Sdim 1005245431Sdim DEBUG(dbgs() << "\tCannot join defs into reserved register.\n"); 1006245431Sdim return false; 1007224145Sdim} 1008224145Sdim 1009245431Sdim/// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 1010224145Sdim/// which are the src/dst of the copy instruction CopyMI. This returns true 1011224145Sdim/// if the copy was successfully coalesced away. If it is not currently 1012224145Sdim/// possible to coalesce this interval, but it may be possible if other 1013224145Sdim/// things get coalesced, then it returns true by reference in 'Again'. 1014245431Sdimbool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { 1015224145Sdim 1016224145Sdim Again = false; 1017226890Sdim DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 1018224145Sdim 1019245431Sdim CoalescerPair CP(*TRI); 1020224145Sdim if (!CP.setRegisters(CopyMI)) { 1021224145Sdim DEBUG(dbgs() << "\tNot coalescable.\n"); 1022224145Sdim return false; 1023224145Sdim } 1024224145Sdim 1025245431Sdim // Dead code elimination. This really should be handled by MachineDCE, but 1026245431Sdim // sometimes dead copies slip through, and we can't generate invalid live 1027245431Sdim // ranges. 1028245431Sdim if (!CP.isPhys() && CopyMI->allDefsAreDead()) { 1029245431Sdim DEBUG(dbgs() << "\tCopy is dead.\n"); 1030245431Sdim DeadDefs.push_back(CopyMI); 1031245431Sdim eliminateDeadDefs(); 1032245431Sdim return true; 1033224145Sdim } 1034224145Sdim 1035226890Sdim // Eliminate undefs. 1036226890Sdim if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 1037226890Sdim DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 1038245431Sdim LIS->RemoveMachineInstrFromMaps(CopyMI); 1039245431Sdim CopyMI->eraseFromParent(); 1040226890Sdim return false; // Not coalescable. 1041226890Sdim } 1042226890Sdim 1043245431Sdim // Coalesced copies are normally removed immediately, but transformations 1044245431Sdim // like removeCopyByCommutingDef() can inadvertently create identity copies. 1045245431Sdim // When that happens, just join the values and remove the copy. 1046245431Sdim if (CP.getSrcReg() == CP.getDstReg()) { 1047245431Sdim LiveInterval &LI = LIS->getInterval(CP.getSrcReg()); 1048245431Sdim DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n'); 1049263509Sdim LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(CopyMI)); 1050245431Sdim if (VNInfo *DefVNI = LRQ.valueDefined()) { 1051245431Sdim VNInfo *ReadVNI = LRQ.valueIn(); 1052245431Sdim assert(ReadVNI && "No value before copy and no <undef> flag."); 1053245431Sdim assert(ReadVNI != DefVNI && "Cannot read and define the same value."); 1054245431Sdim LI.MergeValueNumberInto(DefVNI, ReadVNI); 1055245431Sdim DEBUG(dbgs() << "\tMerged values: " << LI << '\n'); 1056245431Sdim } 1057245431Sdim LIS->RemoveMachineInstrFromMaps(CopyMI); 1058245431Sdim CopyMI->eraseFromParent(); 1059245431Sdim return true; 1060245431Sdim } 1061224145Sdim 1062224145Sdim // Enforce policies. 1063224145Sdim if (CP.isPhys()) { 1064245431Sdim DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 1065245431Sdim << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) 1066245431Sdim << '\n'); 1067245431Sdim if (!canJoinPhys(CP)) { 1068224145Sdim // Before giving up coalescing, if definition of source is defined by 1069224145Sdim // trivial computation, try rematerializing it. 1070263509Sdim bool IsDefCopy; 1071263509Sdim if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy)) 1072224145Sdim return true; 1073263509Sdim if (IsDefCopy) 1074263509Sdim Again = true; // May be possible to coalesce later. 1075224145Sdim return false; 1076224145Sdim } 1077224145Sdim } else { 1078245431Sdim DEBUG({ 1079245431Sdim dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName() 1080245431Sdim << " with "; 1081245431Sdim if (CP.getDstIdx() && CP.getSrcIdx()) 1082245431Sdim dbgs() << PrintReg(CP.getDstReg()) << " in " 1083245431Sdim << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " 1084245431Sdim << PrintReg(CP.getSrcReg()) << " in " 1085245431Sdim << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n'; 1086245431Sdim else 1087245431Sdim dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " 1088245431Sdim << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; 1089245431Sdim }); 1090224145Sdim 1091224145Sdim // When possible, let DstReg be the larger interval. 1092263509Sdim if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() > 1093263509Sdim LIS->getInterval(CP.getDstReg()).size()) 1094224145Sdim CP.flip(); 1095224145Sdim } 1096224145Sdim 1097224145Sdim // Okay, attempt to join these two intervals. On failure, this returns false. 1098224145Sdim // Otherwise, if one of the intervals being joined is a physreg, this method 1099224145Sdim // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1100224145Sdim // been modified, so we can use this information below to update aliases. 1101245431Sdim if (!joinIntervals(CP)) { 1102224145Sdim // Coalescing failed. 1103224145Sdim 1104224145Sdim // If definition of source is defined by trivial computation, try 1105224145Sdim // rematerializing it. 1106263509Sdim bool IsDefCopy; 1107263509Sdim if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy)) 1108224145Sdim return true; 1109224145Sdim 1110263509Sdim // If we can eliminate the copy without merging the live segments, do so 1111263509Sdim // now. 1112245431Sdim if (!CP.isPartial() && !CP.isPhys()) { 1113245431Sdim if (adjustCopiesBackFrom(CP, CopyMI) || 1114245431Sdim removeCopyByCommutingDef(CP, CopyMI)) { 1115245431Sdim LIS->RemoveMachineInstrFromMaps(CopyMI); 1116245431Sdim CopyMI->eraseFromParent(); 1117224145Sdim DEBUG(dbgs() << "\tTrivial!\n"); 1118224145Sdim return true; 1119224145Sdim } 1120224145Sdim } 1121224145Sdim 1122224145Sdim // Otherwise, we are unable to join the intervals. 1123224145Sdim DEBUG(dbgs() << "\tInterference!\n"); 1124224145Sdim Again = true; // May be possible to coalesce later. 1125224145Sdim return false; 1126224145Sdim } 1127224145Sdim 1128224145Sdim // Coalescing to a virtual register that is of a sub-register class of the 1129224145Sdim // other. Make sure the resulting register is set to the right register class. 1130224145Sdim if (CP.isCrossClass()) { 1131224145Sdim ++numCrossRCs; 1132226890Sdim MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1133224145Sdim } 1134224145Sdim 1135245431Sdim // Removing sub-register copies can ease the register class constraints. 1136245431Sdim // Make sure we attempt to inflate the register class of DstReg. 1137245431Sdim if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 1138245431Sdim InflateRegs.push_back(CP.getDstReg()); 1139224145Sdim 1140245431Sdim // CopyMI has been erased by joinIntervals at this point. Remove it from 1141245431Sdim // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 1142245431Sdim // to the work list. This keeps ErasedInstrs from growing needlessly. 1143245431Sdim ErasedInstrs.erase(CopyMI); 1144224145Sdim 1145245431Sdim // Rewrite all SrcReg operands to DstReg. 1146245431Sdim // Also update DstReg operands to include DstIdx if it is set. 1147245431Sdim if (CP.getDstIdx()) 1148245431Sdim updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1149245431Sdim updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1150224145Sdim 1151235633Sdim // SrcReg is guaranteed to be the register whose live interval that is 1152224145Sdim // being merged. 1153226890Sdim LIS->removeInterval(CP.getSrcReg()); 1154224145Sdim 1155224145Sdim // Update regalloc hint. 1156226890Sdim TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1157224145Sdim 1158224145Sdim DEBUG({ 1159263509Sdim dbgs() << "\tJoined. Result = "; 1160263509Sdim if (CP.isPhys()) 1161263509Sdim dbgs() << PrintReg(CP.getDstReg(), TRI); 1162263509Sdim else 1163245431Sdim dbgs() << LIS->getInterval(CP.getDstReg()); 1164263509Sdim dbgs() << '\n'; 1165224145Sdim }); 1166224145Sdim 1167224145Sdim ++numJoins; 1168224145Sdim return true; 1169224145Sdim} 1170224145Sdim 1171245431Sdim/// Attempt joining with a reserved physreg. 1172245431Sdimbool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 1173245431Sdim assert(CP.isPhys() && "Must be a physreg copy"); 1174245431Sdim assert(MRI->isReserved(CP.getDstReg()) && "Not a reserved register"); 1175245431Sdim LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1176263509Sdim DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n'); 1177224145Sdim 1178245431Sdim assert(CP.isFlipped() && RHS.containsOneValue() && 1179245431Sdim "Invalid join with reserved register"); 1180224145Sdim 1181245431Sdim // Optimization for reserved registers like ESP. We can only merge with a 1182245431Sdim // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). 1183245431Sdim // The live range of the reserved register will look like a set of dead defs 1184245431Sdim // - we don't properly track the live range of reserved registers. 1185224145Sdim 1186245431Sdim // Deny any overlapping intervals. This depends on all the reserved 1187245431Sdim // register live ranges to look like dead defs. 1188245431Sdim for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI) 1189245431Sdim if (RHS.overlaps(LIS->getRegUnit(*UI))) { 1190245431Sdim DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n'); 1191245431Sdim return false; 1192245431Sdim } 1193224145Sdim 1194245431Sdim // Skip any value computations, we are not adding new values to the 1195245431Sdim // reserved register. Also skip merging the live ranges, the reserved 1196245431Sdim // register live range doesn't need to be accurate as long as all the 1197245431Sdim // defs are there. 1198245431Sdim 1199245431Sdim // Delete the identity copy. 1200245431Sdim MachineInstr *CopyMI = MRI->getVRegDef(RHS.reg); 1201245431Sdim LIS->RemoveMachineInstrFromMaps(CopyMI); 1202245431Sdim CopyMI->eraseFromParent(); 1203245431Sdim 1204245431Sdim // We don't track kills for reserved registers. 1205245431Sdim MRI->clearKillFlags(CP.getSrcReg()); 1206245431Sdim 1207245431Sdim return true; 1208224145Sdim} 1209224145Sdim 1210245431Sdim//===----------------------------------------------------------------------===// 1211245431Sdim// Interference checking and interval joining 1212245431Sdim//===----------------------------------------------------------------------===// 1213245431Sdim// 1214245431Sdim// In the easiest case, the two live ranges being joined are disjoint, and 1215245431Sdim// there is no interference to consider. It is quite common, though, to have 1216245431Sdim// overlapping live ranges, and we need to check if the interference can be 1217245431Sdim// resolved. 1218245431Sdim// 1219245431Sdim// The live range of a single SSA value forms a sub-tree of the dominator tree. 1220245431Sdim// This means that two SSA values overlap if and only if the def of one value 1221245431Sdim// is contained in the live range of the other value. As a special case, the 1222245431Sdim// overlapping values can be defined at the same index. 1223245431Sdim// 1224245431Sdim// The interference from an overlapping def can be resolved in these cases: 1225245431Sdim// 1226245431Sdim// 1. Coalescable copies. The value is defined by a copy that would become an 1227245431Sdim// identity copy after joining SrcReg and DstReg. The copy instruction will 1228245431Sdim// be removed, and the value will be merged with the source value. 1229245431Sdim// 1230245431Sdim// There can be several copies back and forth, causing many values to be 1231245431Sdim// merged into one. We compute a list of ultimate values in the joined live 1232245431Sdim// range as well as a mappings from the old value numbers. 1233245431Sdim// 1234245431Sdim// 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI 1235245431Sdim// predecessors have a live out value. It doesn't cause real interference, 1236245431Sdim// and can be merged into the value it overlaps. Like a coalescable copy, it 1237245431Sdim// can be erased after joining. 1238245431Sdim// 1239245431Sdim// 3. Copy of external value. The overlapping def may be a copy of a value that 1240245431Sdim// is already in the other register. This is like a coalescable copy, but 1241245431Sdim// the live range of the source register must be trimmed after erasing the 1242245431Sdim// copy instruction: 1243245431Sdim// 1244245431Sdim// %src = COPY %ext 1245245431Sdim// %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext. 1246245431Sdim// 1247245431Sdim// 4. Clobbering undefined lanes. Vector registers are sometimes built by 1248245431Sdim// defining one lane at a time: 1249245431Sdim// 1250245431Sdim// %dst:ssub0<def,read-undef> = FOO 1251245431Sdim// %src = BAR 1252245431Sdim// %dst:ssub1<def> = COPY %src 1253245431Sdim// 1254245431Sdim// The live range of %src overlaps the %dst value defined by FOO, but 1255245431Sdim// merging %src into %dst:ssub1 is only going to clobber the ssub1 lane 1256245431Sdim// which was undef anyway. 1257245431Sdim// 1258245431Sdim// The value mapping is more complicated in this case. The final live range 1259245431Sdim// will have different value numbers for both FOO and BAR, but there is no 1260245431Sdim// simple mapping from old to new values. It may even be necessary to add 1261245431Sdim// new PHI values. 1262245431Sdim// 1263245431Sdim// 5. Clobbering dead lanes. A def may clobber a lane of a vector register that 1264245431Sdim// is live, but never read. This can happen because we don't compute 1265245431Sdim// individual live ranges per lane. 1266245431Sdim// 1267245431Sdim// %dst<def> = FOO 1268245431Sdim// %src = BAR 1269245431Sdim// %dst:ssub1<def> = COPY %src 1270245431Sdim// 1271245431Sdim// This kind of interference is only resolved locally. If the clobbered 1272245431Sdim// lane value escapes the block, the join is aborted. 1273224145Sdim 1274245431Sdimnamespace { 1275245431Sdim/// Track information about values in a single virtual register about to be 1276245431Sdim/// joined. Objects of this class are always created in pairs - one for each 1277245431Sdim/// side of the CoalescerPair. 1278245431Sdimclass JoinVals { 1279245431Sdim LiveInterval &LI; 1280224145Sdim 1281245431Sdim // Location of this register in the final joined register. 1282245431Sdim // Either CP.DstIdx or CP.SrcIdx. 1283245431Sdim unsigned SubIdx; 1284224145Sdim 1285245431Sdim // Values that will be present in the final live range. 1286245431Sdim SmallVectorImpl<VNInfo*> &NewVNInfo; 1287224145Sdim 1288245431Sdim const CoalescerPair &CP; 1289245431Sdim LiveIntervals *LIS; 1290245431Sdim SlotIndexes *Indexes; 1291245431Sdim const TargetRegisterInfo *TRI; 1292224145Sdim 1293245431Sdim // Value number assignments. Maps value numbers in LI to entries in NewVNInfo. 1294245431Sdim // This is suitable for passing to LiveInterval::join(). 1295245431Sdim SmallVector<int, 8> Assignments; 1296224145Sdim 1297245431Sdim // Conflict resolution for overlapping values. 1298245431Sdim enum ConflictResolution { 1299245431Sdim // No overlap, simply keep this value. 1300245431Sdim CR_Keep, 1301224145Sdim 1302245431Sdim // Merge this value into OtherVNI and erase the defining instruction. 1303245431Sdim // Used for IMPLICIT_DEF, coalescable copies, and copies from external 1304245431Sdim // values. 1305245431Sdim CR_Erase, 1306224145Sdim 1307245431Sdim // Merge this value into OtherVNI but keep the defining instruction. 1308245431Sdim // This is for the special case where OtherVNI is defined by the same 1309245431Sdim // instruction. 1310245431Sdim CR_Merge, 1311224145Sdim 1312245431Sdim // Keep this value, and have it replace OtherVNI where possible. This 1313245431Sdim // complicates value mapping since OtherVNI maps to two different values 1314245431Sdim // before and after this def. 1315245431Sdim // Used when clobbering undefined or dead lanes. 1316245431Sdim CR_Replace, 1317224145Sdim 1318245431Sdim // Unresolved conflict. Visit later when all values have been mapped. 1319245431Sdim CR_Unresolved, 1320224145Sdim 1321245431Sdim // Unresolvable conflict. Abort the join. 1322245431Sdim CR_Impossible 1323245431Sdim }; 1324224145Sdim 1325245431Sdim // Per-value info for LI. The lane bit masks are all relative to the final 1326245431Sdim // joined register, so they can be compared directly between SrcReg and 1327245431Sdim // DstReg. 1328245431Sdim struct Val { 1329245431Sdim ConflictResolution Resolution; 1330224145Sdim 1331245431Sdim // Lanes written by this def, 0 for unanalyzed values. 1332245431Sdim unsigned WriteLanes; 1333224145Sdim 1334245431Sdim // Lanes with defined values in this register. Other lanes are undef and 1335245431Sdim // safe to clobber. 1336245431Sdim unsigned ValidLanes; 1337224145Sdim 1338245431Sdim // Value in LI being redefined by this def. 1339245431Sdim VNInfo *RedefVNI; 1340224145Sdim 1341245431Sdim // Value in the other live range that overlaps this def, if any. 1342245431Sdim VNInfo *OtherVNI; 1343245431Sdim 1344252723Sdim // Is this value an IMPLICIT_DEF that can be erased? 1345252723Sdim // 1346252723Sdim // IMPLICIT_DEF values should only exist at the end of a basic block that 1347252723Sdim // is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be 1348252723Sdim // safely erased if they are overlapping a live value in the other live 1349252723Sdim // interval. 1350252723Sdim // 1351252723Sdim // Weird control flow graphs and incomplete PHI handling in 1352252723Sdim // ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with 1353252723Sdim // longer live ranges. Such IMPLICIT_DEF values should be treated like 1354252723Sdim // normal values. 1355252723Sdim bool ErasableImplicitDef; 1356245431Sdim 1357245431Sdim // True when the live range of this value will be pruned because of an 1358245431Sdim // overlapping CR_Replace value in the other live range. 1359245431Sdim bool Pruned; 1360245431Sdim 1361245431Sdim // True once Pruned above has been computed. 1362245431Sdim bool PrunedComputed; 1363245431Sdim 1364245431Sdim Val() : Resolution(CR_Keep), WriteLanes(0), ValidLanes(0), 1365252723Sdim RedefVNI(0), OtherVNI(0), ErasableImplicitDef(false), 1366252723Sdim Pruned(false), PrunedComputed(false) {} 1367245431Sdim 1368245431Sdim bool isAnalyzed() const { return WriteLanes != 0; } 1369245431Sdim }; 1370245431Sdim 1371245431Sdim // One entry per value number in LI. 1372245431Sdim SmallVector<Val, 8> Vals; 1373245431Sdim 1374245431Sdim unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef); 1375245431Sdim VNInfo *stripCopies(VNInfo *VNI); 1376245431Sdim ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other); 1377245431Sdim void computeAssignment(unsigned ValNo, JoinVals &Other); 1378245431Sdim bool taintExtent(unsigned, unsigned, JoinVals&, 1379245431Sdim SmallVectorImpl<std::pair<SlotIndex, unsigned> >&); 1380245431Sdim bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned); 1381245431Sdim bool isPrunedValue(unsigned ValNo, JoinVals &Other); 1382245431Sdim 1383245431Sdimpublic: 1384245431Sdim JoinVals(LiveInterval &li, unsigned subIdx, 1385245431Sdim SmallVectorImpl<VNInfo*> &newVNInfo, 1386245431Sdim const CoalescerPair &cp, 1387245431Sdim LiveIntervals *lis, 1388245431Sdim const TargetRegisterInfo *tri) 1389245431Sdim : LI(li), SubIdx(subIdx), NewVNInfo(newVNInfo), CP(cp), LIS(lis), 1390245431Sdim Indexes(LIS->getSlotIndexes()), TRI(tri), 1391245431Sdim Assignments(LI.getNumValNums(), -1), Vals(LI.getNumValNums()) 1392245431Sdim {} 1393245431Sdim 1394245431Sdim /// Analyze defs in LI and compute a value mapping in NewVNInfo. 1395245431Sdim /// Returns false if any conflicts were impossible to resolve. 1396245431Sdim bool mapValues(JoinVals &Other); 1397245431Sdim 1398245431Sdim /// Try to resolve conflicts that require all values to be mapped. 1399245431Sdim /// Returns false if any conflicts were impossible to resolve. 1400245431Sdim bool resolveConflicts(JoinVals &Other); 1401245431Sdim 1402245431Sdim /// Prune the live range of values in Other.LI where they would conflict with 1403245431Sdim /// CR_Replace values in LI. Collect end points for restoring the live range 1404245431Sdim /// after joining. 1405245431Sdim void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints); 1406245431Sdim 1407245431Sdim /// Erase any machine instructions that have been coalesced away. 1408245431Sdim /// Add erased instructions to ErasedInstrs. 1409245431Sdim /// Add foreign virtual registers to ShrinkRegs if their live range ended at 1410245431Sdim /// the erased instrs. 1411245431Sdim void eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1412245431Sdim SmallVectorImpl<unsigned> &ShrinkRegs); 1413245431Sdim 1414245431Sdim /// Get the value assignments suitable for passing to LiveInterval::join. 1415245431Sdim const int *getAssignments() const { return Assignments.data(); } 1416245431Sdim}; 1417245431Sdim} // end anonymous namespace 1418245431Sdim 1419245431Sdim/// Compute the bitmask of lanes actually written by DefMI. 1420245431Sdim/// Set Redef if there are any partial register definitions that depend on the 1421245431Sdim/// previous value of the register. 1422245431Sdimunsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) { 1423245431Sdim unsigned L = 0; 1424245431Sdim for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) { 1425245431Sdim if (!MO->isReg() || MO->getReg() != LI.reg || !MO->isDef()) 1426245431Sdim continue; 1427245431Sdim L |= TRI->getSubRegIndexLaneMask( 1428245431Sdim TRI->composeSubRegIndices(SubIdx, MO->getSubReg())); 1429245431Sdim if (MO->readsReg()) 1430245431Sdim Redef = true; 1431245431Sdim } 1432245431Sdim return L; 1433224145Sdim} 1434224145Sdim 1435245431Sdim/// Find the ultimate value that VNI was copied from. 1436245431SdimVNInfo *JoinVals::stripCopies(VNInfo *VNI) { 1437245431Sdim while (!VNI->isPHIDef()) { 1438245431Sdim MachineInstr *MI = Indexes->getInstructionFromIndex(VNI->def); 1439245431Sdim assert(MI && "No defining instruction"); 1440245431Sdim if (!MI->isFullCopy()) 1441245431Sdim break; 1442245431Sdim unsigned Reg = MI->getOperand(1).getReg(); 1443245431Sdim if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1444245431Sdim break; 1445263509Sdim LiveQueryResult LRQ = LIS->getInterval(Reg).Query(VNI->def); 1446245431Sdim if (!LRQ.valueIn()) 1447245431Sdim break; 1448245431Sdim VNI = LRQ.valueIn(); 1449245431Sdim } 1450245431Sdim return VNI; 1451245431Sdim} 1452224145Sdim 1453245431Sdim/// Analyze ValNo in this live range, and set all fields of Vals[ValNo]. 1454245431Sdim/// Return a conflict resolution when possible, but leave the hard cases as 1455245431Sdim/// CR_Unresolved. 1456245431Sdim/// Recursively calls computeAssignment() on this and Other, guaranteeing that 1457245431Sdim/// both OtherVNI and RedefVNI have been analyzed and mapped before returning. 1458245431Sdim/// The recursion always goes upwards in the dominator tree, making loops 1459245431Sdim/// impossible. 1460245431SdimJoinVals::ConflictResolution 1461245431SdimJoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { 1462245431Sdim Val &V = Vals[ValNo]; 1463245431Sdim assert(!V.isAnalyzed() && "Value has already been analyzed!"); 1464245431Sdim VNInfo *VNI = LI.getValNumInfo(ValNo); 1465245431Sdim if (VNI->isUnused()) { 1466245431Sdim V.WriteLanes = ~0u; 1467245431Sdim return CR_Keep; 1468245431Sdim } 1469245431Sdim 1470245431Sdim // Get the instruction defining this value, compute the lanes written. 1471245431Sdim const MachineInstr *DefMI = 0; 1472245431Sdim if (VNI->isPHIDef()) { 1473245431Sdim // Conservatively assume that all lanes in a PHI are valid. 1474245431Sdim V.ValidLanes = V.WriteLanes = TRI->getSubRegIndexLaneMask(SubIdx); 1475245431Sdim } else { 1476245431Sdim DefMI = Indexes->getInstructionFromIndex(VNI->def); 1477245431Sdim bool Redef = false; 1478245431Sdim V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef); 1479245431Sdim 1480245431Sdim // If this is a read-modify-write instruction, there may be more valid 1481245431Sdim // lanes than the ones written by this instruction. 1482245431Sdim // This only covers partial redef operands. DefMI may have normal use 1483245431Sdim // operands reading the register. They don't contribute valid lanes. 1484245431Sdim // 1485245431Sdim // This adds ssub1 to the set of valid lanes in %src: 1486245431Sdim // 1487245431Sdim // %src:ssub1<def> = FOO 1488245431Sdim // 1489245431Sdim // This leaves only ssub1 valid, making any other lanes undef: 1490245431Sdim // 1491245431Sdim // %src:ssub1<def,read-undef> = FOO %src:ssub2 1492245431Sdim // 1493245431Sdim // The <read-undef> flag on the def operand means that old lane values are 1494245431Sdim // not important. 1495245431Sdim if (Redef) { 1496263509Sdim V.RedefVNI = LI.Query(VNI->def).valueIn(); 1497245431Sdim assert(V.RedefVNI && "Instruction is reading nonexistent value"); 1498245431Sdim computeAssignment(V.RedefVNI->id, Other); 1499245431Sdim V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes; 1500235633Sdim } 1501235633Sdim 1502245431Sdim // An IMPLICIT_DEF writes undef values. 1503245431Sdim if (DefMI->isImplicitDef()) { 1504252723Sdim // We normally expect IMPLICIT_DEF values to be live only until the end 1505252723Sdim // of their block. If the value is really live longer and gets pruned in 1506252723Sdim // another block, this flag is cleared again. 1507252723Sdim V.ErasableImplicitDef = true; 1508245431Sdim V.ValidLanes &= ~V.WriteLanes; 1509235633Sdim } 1510245431Sdim } 1511235633Sdim 1512245431Sdim // Find the value in Other that overlaps VNI->def, if any. 1513263509Sdim LiveQueryResult OtherLRQ = Other.LI.Query(VNI->def); 1514224145Sdim 1515245431Sdim // It is possible that both values are defined by the same instruction, or 1516245431Sdim // the values are PHIs defined in the same block. When that happens, the two 1517245431Sdim // values should be merged into one, but not into any preceding value. 1518245431Sdim // The first value defined or visited gets CR_Keep, the other gets CR_Merge. 1519245431Sdim if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) { 1520245431Sdim assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ"); 1521245431Sdim 1522245431Sdim // One value stays, the other is merged. Keep the earlier one, or the first 1523245431Sdim // one we see. 1524245431Sdim if (OtherVNI->def < VNI->def) 1525245431Sdim Other.computeAssignment(OtherVNI->id, *this); 1526245431Sdim else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) { 1527245431Sdim // This is an early-clobber def overlapping a live-in value in the other 1528245431Sdim // register. Not mergeable. 1529245431Sdim V.OtherVNI = OtherLRQ.valueIn(); 1530245431Sdim return CR_Impossible; 1531224145Sdim } 1532245431Sdim V.OtherVNI = OtherVNI; 1533245431Sdim Val &OtherV = Other.Vals[OtherVNI->id]; 1534245431Sdim // Keep this value, check for conflicts when analyzing OtherVNI. 1535245431Sdim if (!OtherV.isAnalyzed()) 1536245431Sdim return CR_Keep; 1537245431Sdim // Both sides have been analyzed now. 1538245431Sdim // Allow overlapping PHI values. Any real interference would show up in a 1539245431Sdim // predecessor, the PHI itself can't introduce any conflicts. 1540245431Sdim if (VNI->isPHIDef()) 1541245431Sdim return CR_Merge; 1542245431Sdim if (V.ValidLanes & OtherV.ValidLanes) 1543245431Sdim // Overlapping lanes can't be resolved. 1544245431Sdim return CR_Impossible; 1545245431Sdim else 1546245431Sdim return CR_Merge; 1547224145Sdim } 1548224145Sdim 1549245431Sdim // No simultaneous def. Is Other live at the def? 1550245431Sdim V.OtherVNI = OtherLRQ.valueIn(); 1551245431Sdim if (!V.OtherVNI) 1552245431Sdim // No overlap, no conflict. 1553245431Sdim return CR_Keep; 1554224145Sdim 1555245431Sdim assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ"); 1556224145Sdim 1557245431Sdim // We have overlapping values, or possibly a kill of Other. 1558245431Sdim // Recursively compute assignments up the dominator tree. 1559245431Sdim Other.computeAssignment(V.OtherVNI->id, *this); 1560252723Sdim Val &OtherV = Other.Vals[V.OtherVNI->id]; 1561224145Sdim 1562252723Sdim // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block. 1563252723Sdim // This shouldn't normally happen, but ProcessImplicitDefs can leave such 1564252723Sdim // IMPLICIT_DEF instructions behind, and there is nothing wrong with it 1565252723Sdim // technically. 1566252723Sdim // 1567252723Sdim // WHen it happens, treat that IMPLICIT_DEF as a normal value, and don't try 1568252723Sdim // to erase the IMPLICIT_DEF instruction. 1569252723Sdim if (OtherV.ErasableImplicitDef && DefMI && 1570252723Sdim DefMI->getParent() != Indexes->getMBBFromIndex(V.OtherVNI->def)) { 1571252723Sdim DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def 1572252723Sdim << " extends into BB#" << DefMI->getParent()->getNumber() 1573252723Sdim << ", keeping it.\n"); 1574252723Sdim OtherV.ErasableImplicitDef = false; 1575252723Sdim } 1576252723Sdim 1577245431Sdim // Allow overlapping PHI values. Any real interference would show up in a 1578245431Sdim // predecessor, the PHI itself can't introduce any conflicts. 1579245431Sdim if (VNI->isPHIDef()) 1580245431Sdim return CR_Replace; 1581224145Sdim 1582245431Sdim // Check for simple erasable conflicts. 1583245431Sdim if (DefMI->isImplicitDef()) 1584245431Sdim return CR_Erase; 1585224145Sdim 1586245431Sdim // Include the non-conflict where DefMI is a coalescable copy that kills 1587245431Sdim // OtherVNI. We still want the copy erased and value numbers merged. 1588245431Sdim if (CP.isCoalescable(DefMI)) { 1589245431Sdim // Some of the lanes copied from OtherVNI may be undef, making them undef 1590245431Sdim // here too. 1591245431Sdim V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes; 1592245431Sdim return CR_Erase; 1593224145Sdim } 1594224145Sdim 1595245431Sdim // This may not be a real conflict if DefMI simply kills Other and defines 1596245431Sdim // VNI. 1597245431Sdim if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def) 1598245431Sdim return CR_Keep; 1599224145Sdim 1600245431Sdim // Handle the case where VNI and OtherVNI can be proven to be identical: 1601245431Sdim // 1602245431Sdim // %other = COPY %ext 1603245431Sdim // %this = COPY %ext <-- Erase this copy 1604245431Sdim // 1605245431Sdim if (DefMI->isFullCopy() && !CP.isPartial() && 1606245431Sdim stripCopies(VNI) == stripCopies(V.OtherVNI)) 1607245431Sdim return CR_Erase; 1608224145Sdim 1609245431Sdim // If the lanes written by this instruction were all undef in OtherVNI, it is 1610245431Sdim // still safe to join the live ranges. This can't be done with a simple value 1611245431Sdim // mapping, though - OtherVNI will map to multiple values: 1612245431Sdim // 1613245431Sdim // 1 %dst:ssub0 = FOO <-- OtherVNI 1614245431Sdim // 2 %src = BAR <-- VNI 1615245431Sdim // 3 %dst:ssub1 = COPY %src<kill> <-- Eliminate this copy. 1616245431Sdim // 4 BAZ %dst<kill> 1617245431Sdim // 5 QUUX %src<kill> 1618245431Sdim // 1619245431Sdim // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace 1620245431Sdim // handles this complex value mapping. 1621245431Sdim if ((V.WriteLanes & OtherV.ValidLanes) == 0) 1622245431Sdim return CR_Replace; 1623224145Sdim 1624245431Sdim // If the other live range is killed by DefMI and the live ranges are still 1625245431Sdim // overlapping, it must be because we're looking at an early clobber def: 1626245431Sdim // 1627245431Sdim // %dst<def,early-clobber> = ASM %src<kill> 1628245431Sdim // 1629245431Sdim // In this case, it is illegal to merge the two live ranges since the early 1630245431Sdim // clobber def would clobber %src before it was read. 1631245431Sdim if (OtherLRQ.isKill()) { 1632245431Sdim // This case where the def doesn't overlap the kill is handled above. 1633245431Sdim assert(VNI->def.isEarlyClobber() && 1634245431Sdim "Only early clobber defs can overlap a kill"); 1635245431Sdim return CR_Impossible; 1636224145Sdim } 1637224145Sdim 1638245431Sdim // VNI is clobbering live lanes in OtherVNI, but there is still the 1639245431Sdim // possibility that no instructions actually read the clobbered lanes. 1640245431Sdim // If we're clobbering all the lanes in OtherVNI, at least one must be read. 1641245431Sdim // Otherwise Other.LI wouldn't be live here. 1642245431Sdim if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes) == 0) 1643245431Sdim return CR_Impossible; 1644224145Sdim 1645245431Sdim // We need to verify that no instructions are reading the clobbered lanes. To 1646245431Sdim // save compile time, we'll only check that locally. Don't allow the tainted 1647245431Sdim // value to escape the basic block. 1648245431Sdim MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1649245431Sdim if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB)) 1650245431Sdim return CR_Impossible; 1651245431Sdim 1652245431Sdim // There are still some things that could go wrong besides clobbered lanes 1653245431Sdim // being read, for example OtherVNI may be only partially redefined in MBB, 1654245431Sdim // and some clobbered lanes could escape the block. Save this analysis for 1655245431Sdim // resolveConflicts() when all values have been mapped. We need to know 1656245431Sdim // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute 1657245431Sdim // that now - the recursive analyzeValue() calls must go upwards in the 1658245431Sdim // dominator tree. 1659245431Sdim return CR_Unresolved; 1660245431Sdim} 1661245431Sdim 1662245431Sdim/// Compute the value assignment for ValNo in LI. 1663245431Sdim/// This may be called recursively by analyzeValue(), but never for a ValNo on 1664245431Sdim/// the stack. 1665245431Sdimvoid JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) { 1666245431Sdim Val &V = Vals[ValNo]; 1667245431Sdim if (V.isAnalyzed()) { 1668245431Sdim // Recursion should always move up the dominator tree, so ValNo is not 1669245431Sdim // supposed to reappear before it has been assigned. 1670245431Sdim assert(Assignments[ValNo] != -1 && "Bad recursion?"); 1671245431Sdim return; 1672224145Sdim } 1673245431Sdim switch ((V.Resolution = analyzeValue(ValNo, Other))) { 1674245431Sdim case CR_Erase: 1675245431Sdim case CR_Merge: 1676245431Sdim // Merge this ValNo into OtherVNI. 1677245431Sdim assert(V.OtherVNI && "OtherVNI not assigned, can't merge."); 1678245431Sdim assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion"); 1679245431Sdim Assignments[ValNo] = Other.Assignments[V.OtherVNI->id]; 1680245431Sdim DEBUG(dbgs() << "\t\tmerge " << PrintReg(LI.reg) << ':' << ValNo << '@' 1681245431Sdim << LI.getValNumInfo(ValNo)->def << " into " 1682245431Sdim << PrintReg(Other.LI.reg) << ':' << V.OtherVNI->id << '@' 1683245431Sdim << V.OtherVNI->def << " --> @" 1684245431Sdim << NewVNInfo[Assignments[ValNo]]->def << '\n'); 1685245431Sdim break; 1686245431Sdim case CR_Replace: 1687245431Sdim case CR_Unresolved: 1688245431Sdim // The other value is going to be pruned if this join is successful. 1689245431Sdim assert(V.OtherVNI && "OtherVNI not assigned, can't prune"); 1690245431Sdim Other.Vals[V.OtherVNI->id].Pruned = true; 1691245431Sdim // Fall through. 1692245431Sdim default: 1693245431Sdim // This value number needs to go in the final joined live range. 1694245431Sdim Assignments[ValNo] = NewVNInfo.size(); 1695245431Sdim NewVNInfo.push_back(LI.getValNumInfo(ValNo)); 1696245431Sdim break; 1697245431Sdim } 1698245431Sdim} 1699245431Sdim 1700245431Sdimbool JoinVals::mapValues(JoinVals &Other) { 1701245431Sdim for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1702245431Sdim computeAssignment(i, Other); 1703245431Sdim if (Vals[i].Resolution == CR_Impossible) { 1704245431Sdim DEBUG(dbgs() << "\t\tinterference at " << PrintReg(LI.reg) << ':' << i 1705245431Sdim << '@' << LI.getValNumInfo(i)->def << '\n'); 1706245431Sdim return false; 1707224145Sdim } 1708224145Sdim } 1709245431Sdim return true; 1710245431Sdim} 1711224145Sdim 1712245431Sdim/// Assuming ValNo is going to clobber some valid lanes in Other.LI, compute 1713245431Sdim/// the extent of the tainted lanes in the block. 1714245431Sdim/// 1715245431Sdim/// Multiple values in Other.LI can be affected since partial redefinitions can 1716245431Sdim/// preserve previously tainted lanes. 1717245431Sdim/// 1718245431Sdim/// 1 %dst = VLOAD <-- Define all lanes in %dst 1719245431Sdim/// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0 1720245431Sdim/// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0 1721245431Sdim/// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read 1722245431Sdim/// 1723245431Sdim/// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes) 1724245431Sdim/// entry to TaintedVals. 1725245431Sdim/// 1726245431Sdim/// Returns false if the tainted lanes extend beyond the basic block. 1727245431Sdimbool JoinVals:: 1728245431SdimtaintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other, 1729245431Sdim SmallVectorImpl<std::pair<SlotIndex, unsigned> > &TaintExtent) { 1730245431Sdim VNInfo *VNI = LI.getValNumInfo(ValNo); 1731245431Sdim MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1732245431Sdim SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB); 1733224145Sdim 1734245431Sdim // Scan Other.LI from VNI.def to MBBEnd. 1735245431Sdim LiveInterval::iterator OtherI = Other.LI.find(VNI->def); 1736245431Sdim assert(OtherI != Other.LI.end() && "No conflict?"); 1737245431Sdim do { 1738245431Sdim // OtherI is pointing to a tainted value. Abort the join if the tainted 1739245431Sdim // lanes escape the block. 1740245431Sdim SlotIndex End = OtherI->end; 1741245431Sdim if (End >= MBBEnd) { 1742245431Sdim DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.LI.reg) << ':' 1743245431Sdim << OtherI->valno->id << '@' << OtherI->start << '\n'); 1744245431Sdim return false; 1745224145Sdim } 1746245431Sdim DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.LI.reg) << ':' 1747245431Sdim << OtherI->valno->id << '@' << OtherI->start 1748245431Sdim << " to " << End << '\n'); 1749245431Sdim // A dead def is not a problem. 1750245431Sdim if (End.isDead()) 1751245431Sdim break; 1752245431Sdim TaintExtent.push_back(std::make_pair(End, TaintedLanes)); 1753245431Sdim 1754245431Sdim // Check for another def in the MBB. 1755245431Sdim if (++OtherI == Other.LI.end() || OtherI->start >= MBBEnd) 1756245431Sdim break; 1757245431Sdim 1758245431Sdim // Lanes written by the new def are no longer tainted. 1759245431Sdim const Val &OV = Other.Vals[OtherI->valno->id]; 1760245431Sdim TaintedLanes &= ~OV.WriteLanes; 1761245431Sdim if (!OV.RedefVNI) 1762245431Sdim break; 1763245431Sdim } while (TaintedLanes); 1764245431Sdim return true; 1765245431Sdim} 1766245431Sdim 1767245431Sdim/// Return true if MI uses any of the given Lanes from Reg. 1768245431Sdim/// This does not include partial redefinitions of Reg. 1769245431Sdimbool JoinVals::usesLanes(MachineInstr *MI, unsigned Reg, unsigned SubIdx, 1770245431Sdim unsigned Lanes) { 1771245431Sdim if (MI->isDebugValue()) 1772245431Sdim return false; 1773245431Sdim for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { 1774245431Sdim if (!MO->isReg() || MO->isDef() || MO->getReg() != Reg) 1775245431Sdim continue; 1776245431Sdim if (!MO->readsReg()) 1777245431Sdim continue; 1778245431Sdim if (Lanes & TRI->getSubRegIndexLaneMask( 1779245431Sdim TRI->composeSubRegIndices(SubIdx, MO->getSubReg()))) 1780245431Sdim return true; 1781224145Sdim } 1782245431Sdim return false; 1783245431Sdim} 1784224145Sdim 1785245431Sdimbool JoinVals::resolveConflicts(JoinVals &Other) { 1786245431Sdim for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1787245431Sdim Val &V = Vals[i]; 1788245431Sdim assert (V.Resolution != CR_Impossible && "Unresolvable conflict"); 1789245431Sdim if (V.Resolution != CR_Unresolved) 1790245431Sdim continue; 1791245431Sdim DEBUG(dbgs() << "\t\tconflict at " << PrintReg(LI.reg) << ':' << i 1792245431Sdim << '@' << LI.getValNumInfo(i)->def << '\n'); 1793245431Sdim ++NumLaneConflicts; 1794245431Sdim assert(V.OtherVNI && "Inconsistent conflict resolution."); 1795245431Sdim VNInfo *VNI = LI.getValNumInfo(i); 1796245431Sdim const Val &OtherV = Other.Vals[V.OtherVNI->id]; 1797245431Sdim 1798245431Sdim // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the 1799245431Sdim // join, those lanes will be tainted with a wrong value. Get the extent of 1800245431Sdim // the tainted lanes. 1801245431Sdim unsigned TaintedLanes = V.WriteLanes & OtherV.ValidLanes; 1802245431Sdim SmallVector<std::pair<SlotIndex, unsigned>, 8> TaintExtent; 1803245431Sdim if (!taintExtent(i, TaintedLanes, Other, TaintExtent)) 1804245431Sdim // Tainted lanes would extend beyond the basic block. 1805245431Sdim return false; 1806245431Sdim 1807245431Sdim assert(!TaintExtent.empty() && "There should be at least one conflict."); 1808245431Sdim 1809245431Sdim // Now look at the instructions from VNI->def to TaintExtent (inclusive). 1810245431Sdim MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1811245431Sdim MachineBasicBlock::iterator MI = MBB->begin(); 1812245431Sdim if (!VNI->isPHIDef()) { 1813245431Sdim MI = Indexes->getInstructionFromIndex(VNI->def); 1814245431Sdim // No need to check the instruction defining VNI for reads. 1815245431Sdim ++MI; 1816224145Sdim } 1817245431Sdim assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) && 1818245431Sdim "Interference ends on VNI->def. Should have been handled earlier"); 1819245431Sdim MachineInstr *LastMI = 1820245431Sdim Indexes->getInstructionFromIndex(TaintExtent.front().first); 1821245431Sdim assert(LastMI && "Range must end at a proper instruction"); 1822245431Sdim unsigned TaintNum = 0; 1823245431Sdim for(;;) { 1824245431Sdim assert(MI != MBB->end() && "Bad LastMI"); 1825245431Sdim if (usesLanes(MI, Other.LI.reg, Other.SubIdx, TaintedLanes)) { 1826245431Sdim DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI); 1827224145Sdim return false; 1828245431Sdim } 1829245431Sdim // LastMI is the last instruction to use the current value. 1830245431Sdim if (&*MI == LastMI) { 1831245431Sdim if (++TaintNum == TaintExtent.size()) 1832245431Sdim break; 1833245431Sdim LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first); 1834245431Sdim assert(LastMI && "Range must end at a proper instruction"); 1835245431Sdim TaintedLanes = TaintExtent[TaintNum].second; 1836245431Sdim } 1837245431Sdim ++MI; 1838224145Sdim } 1839224145Sdim 1840245431Sdim // The tainted lanes are unused. 1841245431Sdim V.Resolution = CR_Replace; 1842245431Sdim ++NumLaneResolves; 1843224145Sdim } 1844245431Sdim return true; 1845245431Sdim} 1846224145Sdim 1847245431Sdim// Determine if ValNo is a copy of a value number in LI or Other.LI that will 1848245431Sdim// be pruned: 1849245431Sdim// 1850245431Sdim// %dst = COPY %src 1851245431Sdim// %src = COPY %dst <-- This value to be pruned. 1852245431Sdim// %dst = COPY %src <-- This value is a copy of a pruned value. 1853245431Sdim// 1854245431Sdimbool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) { 1855245431Sdim Val &V = Vals[ValNo]; 1856245431Sdim if (V.Pruned || V.PrunedComputed) 1857245431Sdim return V.Pruned; 1858245431Sdim 1859245431Sdim if (V.Resolution != CR_Erase && V.Resolution != CR_Merge) 1860245431Sdim return V.Pruned; 1861245431Sdim 1862245431Sdim // Follow copies up the dominator tree and check if any intermediate value 1863245431Sdim // has been pruned. 1864245431Sdim V.PrunedComputed = true; 1865245431Sdim V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this); 1866245431Sdim return V.Pruned; 1867245431Sdim} 1868245431Sdim 1869245431Sdimvoid JoinVals::pruneValues(JoinVals &Other, 1870245431Sdim SmallVectorImpl<SlotIndex> &EndPoints) { 1871245431Sdim for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1872245431Sdim SlotIndex Def = LI.getValNumInfo(i)->def; 1873245431Sdim switch (Vals[i].Resolution) { 1874245431Sdim case CR_Keep: 1875245431Sdim break; 1876245431Sdim case CR_Replace: { 1877245431Sdim // This value takes precedence over the value in Other.LI. 1878245431Sdim LIS->pruneValue(&Other.LI, Def, &EndPoints); 1879245431Sdim // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF 1880245431Sdim // instructions are only inserted to provide a live-out value for PHI 1881245431Sdim // predecessors, so the instruction should simply go away once its value 1882245431Sdim // has been replaced. 1883245431Sdim Val &OtherV = Other.Vals[Vals[i].OtherVNI->id]; 1884252723Sdim bool EraseImpDef = OtherV.ErasableImplicitDef && 1885252723Sdim OtherV.Resolution == CR_Keep; 1886245431Sdim if (!Def.isBlock()) { 1887245431Sdim // Remove <def,read-undef> flags. This def is now a partial redef. 1888245431Sdim // Also remove <def,dead> flags since the joined live range will 1889245431Sdim // continue past this instruction. 1890245431Sdim for (MIOperands MO(Indexes->getInstructionFromIndex(Def)); 1891245431Sdim MO.isValid(); ++MO) 1892245431Sdim if (MO->isReg() && MO->isDef() && MO->getReg() == LI.reg) { 1893245431Sdim MO->setIsUndef(EraseImpDef); 1894245431Sdim MO->setIsDead(false); 1895245431Sdim } 1896245431Sdim // This value will reach instructions below, but we need to make sure 1897245431Sdim // the live range also reaches the instruction at Def. 1898245431Sdim if (!EraseImpDef) 1899245431Sdim EndPoints.push_back(Def); 1900245431Sdim } 1901245431Sdim DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.LI.reg) << " at " << Def 1902245431Sdim << ": " << Other.LI << '\n'); 1903245431Sdim break; 1904245431Sdim } 1905245431Sdim case CR_Erase: 1906245431Sdim case CR_Merge: 1907245431Sdim if (isPrunedValue(i, Other)) { 1908245431Sdim // This value is ultimately a copy of a pruned value in LI or Other.LI. 1909245431Sdim // We can no longer trust the value mapping computed by 1910245431Sdim // computeAssignment(), the value that was originally copied could have 1911245431Sdim // been replaced. 1912245431Sdim LIS->pruneValue(&LI, Def, &EndPoints); 1913245431Sdim DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(LI.reg) << " at " 1914245431Sdim << Def << ": " << LI << '\n'); 1915245431Sdim } 1916245431Sdim break; 1917245431Sdim case CR_Unresolved: 1918245431Sdim case CR_Impossible: 1919245431Sdim llvm_unreachable("Unresolved conflicts"); 1920245431Sdim } 1921224145Sdim } 1922245431Sdim} 1923224145Sdim 1924245431Sdimvoid JoinVals::eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1925245431Sdim SmallVectorImpl<unsigned> &ShrinkRegs) { 1926245431Sdim for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1927245431Sdim // Get the def location before markUnused() below invalidates it. 1928245431Sdim SlotIndex Def = LI.getValNumInfo(i)->def; 1929245431Sdim switch (Vals[i].Resolution) { 1930245431Sdim case CR_Keep: 1931245431Sdim // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any 1932245431Sdim // longer. The IMPLICIT_DEF instructions are only inserted by 1933245431Sdim // PHIElimination to guarantee that all PHI predecessors have a value. 1934252723Sdim if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned) 1935245431Sdim break; 1936245431Sdim // Remove value number i from LI. Note that this VNInfo is still present 1937245431Sdim // in NewVNInfo, so it will appear as an unused value number in the final 1938245431Sdim // joined interval. 1939245431Sdim LI.getValNumInfo(i)->markUnused(); 1940245431Sdim LI.removeValNo(LI.getValNumInfo(i)); 1941245431Sdim DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LI << '\n'); 1942245431Sdim // FALL THROUGH. 1943245431Sdim 1944245431Sdim case CR_Erase: { 1945245431Sdim MachineInstr *MI = Indexes->getInstructionFromIndex(Def); 1946245431Sdim assert(MI && "No instruction to erase"); 1947245431Sdim if (MI->isCopy()) { 1948245431Sdim unsigned Reg = MI->getOperand(1).getReg(); 1949245431Sdim if (TargetRegisterInfo::isVirtualRegister(Reg) && 1950245431Sdim Reg != CP.getSrcReg() && Reg != CP.getDstReg()) 1951245431Sdim ShrinkRegs.push_back(Reg); 1952245431Sdim } 1953245431Sdim ErasedInstrs.insert(MI); 1954245431Sdim DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI); 1955245431Sdim LIS->RemoveMachineInstrFromMaps(MI); 1956245431Sdim MI->eraseFromParent(); 1957245431Sdim break; 1958245431Sdim } 1959245431Sdim default: 1960245431Sdim break; 1961245431Sdim } 1962224145Sdim } 1963245431Sdim} 1964224145Sdim 1965245431Sdimbool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { 1966245431Sdim SmallVector<VNInfo*, 16> NewVNInfo; 1967245431Sdim LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1968245431Sdim LiveInterval &LHS = LIS->getInterval(CP.getDstReg()); 1969245431Sdim JoinVals RHSVals(RHS, CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI); 1970245431Sdim JoinVals LHSVals(LHS, CP.getDstIdx(), NewVNInfo, CP, LIS, TRI); 1971224145Sdim 1972263509Sdim DEBUG(dbgs() << "\t\tRHS = " << RHS 1973263509Sdim << "\n\t\tLHS = " << LHS 1974245431Sdim << '\n'); 1975224145Sdim 1976245431Sdim // First compute NewVNInfo and the simple value mappings. 1977245431Sdim // Detect impossible conflicts early. 1978245431Sdim if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) 1979245431Sdim return false; 1980224145Sdim 1981245431Sdim // Some conflicts can only be resolved after all values have been mapped. 1982245431Sdim if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals)) 1983245431Sdim return false; 1984224145Sdim 1985245431Sdim // All clear, the live ranges can be merged. 1986224145Sdim 1987245431Sdim // The merging algorithm in LiveInterval::join() can't handle conflicting 1988245431Sdim // value mappings, so we need to remove any live ranges that overlap a 1989245431Sdim // CR_Replace resolution. Collect a set of end points that can be used to 1990245431Sdim // restore the live range after joining. 1991245431Sdim SmallVector<SlotIndex, 8> EndPoints; 1992245431Sdim LHSVals.pruneValues(RHSVals, EndPoints); 1993245431Sdim RHSVals.pruneValues(LHSVals, EndPoints); 1994245431Sdim 1995245431Sdim // Erase COPY and IMPLICIT_DEF instructions. This may cause some external 1996245431Sdim // registers to require trimming. 1997245431Sdim SmallVector<unsigned, 8> ShrinkRegs; 1998245431Sdim LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 1999245431Sdim RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 2000245431Sdim while (!ShrinkRegs.empty()) 2001245431Sdim LIS->shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val())); 2002245431Sdim 2003245431Sdim // Join RHS into LHS. 2004263509Sdim LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo); 2005245431Sdim 2006245431Sdim // Kill flags are going to be wrong if the live ranges were overlapping. 2007245431Sdim // Eventually, we should simply clear all kill flags when computing live 2008245431Sdim // ranges. They are reinserted after register allocation. 2009245431Sdim MRI->clearKillFlags(LHS.reg); 2010245431Sdim MRI->clearKillFlags(RHS.reg); 2011245431Sdim 2012245431Sdim if (EndPoints.empty()) 2013245431Sdim return true; 2014245431Sdim 2015245431Sdim // Recompute the parts of the live range we had to remove because of 2016245431Sdim // CR_Replace conflicts. 2017245431Sdim DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size() 2018245431Sdim << " points: " << LHS << '\n'); 2019263509Sdim LIS->extendToIndices(LHS, EndPoints); 2020224145Sdim return true; 2021224145Sdim} 2022224145Sdim 2023245431Sdim/// joinIntervals - Attempt to join these two intervals. On failure, this 2024245431Sdim/// returns false. 2025245431Sdimbool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 2026245431Sdim return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP); 2027245431Sdim} 2028245431Sdim 2029224145Sdimnamespace { 2030252723Sdim// Information concerning MBB coalescing priority. 2031252723Sdimstruct MBBPriorityInfo { 2032252723Sdim MachineBasicBlock *MBB; 2033252723Sdim unsigned Depth; 2034252723Sdim bool IsSplit; 2035224145Sdim 2036252723Sdim MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit) 2037252723Sdim : MBB(mbb), Depth(depth), IsSplit(issplit) {} 2038252723Sdim}; 2039252723Sdim} 2040224145Sdim 2041252723Sdim// C-style comparator that sorts first based on the loop depth of the basic 2042252723Sdim// block (the unsigned), and then on the MBB number. 2043252723Sdim// 2044252723Sdim// EnableGlobalCopies assumes that the primary sort key is loop depth. 2045263509Sdimstatic int compareMBBPriority(const MBBPriorityInfo *LHS, 2046263509Sdim const MBBPriorityInfo *RHS) { 2047252723Sdim // Deeper loops first 2048252723Sdim if (LHS->Depth != RHS->Depth) 2049252723Sdim return LHS->Depth > RHS->Depth ? -1 : 1; 2050252723Sdim 2051252723Sdim // Try to unsplit critical edges next. 2052252723Sdim if (LHS->IsSplit != RHS->IsSplit) 2053252723Sdim return LHS->IsSplit ? -1 : 1; 2054252723Sdim 2055252723Sdim // Prefer blocks that are more connected in the CFG. This takes care of 2056252723Sdim // the most difficult copies first while intervals are short. 2057252723Sdim unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size(); 2058252723Sdim unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size(); 2059252723Sdim if (cl != cr) 2060252723Sdim return cl > cr ? -1 : 1; 2061252723Sdim 2062252723Sdim // As a last resort, sort by block number. 2063252723Sdim return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1; 2064224145Sdim} 2065224145Sdim 2066252723Sdim/// \returns true if the given copy uses or defines a local live range. 2067252723Sdimstatic bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) { 2068252723Sdim if (!Copy->isCopy()) 2069252723Sdim return false; 2070252723Sdim 2071263509Sdim if (Copy->getOperand(1).isUndef()) 2072263509Sdim return false; 2073263509Sdim 2074252723Sdim unsigned SrcReg = Copy->getOperand(1).getReg(); 2075252723Sdim unsigned DstReg = Copy->getOperand(0).getReg(); 2076252723Sdim if (TargetRegisterInfo::isPhysicalRegister(SrcReg) 2077252723Sdim || TargetRegisterInfo::isPhysicalRegister(DstReg)) 2078252723Sdim return false; 2079252723Sdim 2080252723Sdim return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg)) 2081252723Sdim || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg)); 2082252723Sdim} 2083252723Sdim 2084245431Sdim// Try joining WorkList copies starting from index From. 2085245431Sdim// Null out any successful joins. 2086252723Sdimbool RegisterCoalescer:: 2087252723SdimcopyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) { 2088245431Sdim bool Progress = false; 2089252723Sdim for (unsigned i = 0, e = CurrList.size(); i != e; ++i) { 2090252723Sdim if (!CurrList[i]) 2091245431Sdim continue; 2092245431Sdim // Skip instruction pointers that have already been erased, for example by 2093245431Sdim // dead code elimination. 2094252723Sdim if (ErasedInstrs.erase(CurrList[i])) { 2095252723Sdim CurrList[i] = 0; 2096245431Sdim continue; 2097245431Sdim } 2098245431Sdim bool Again = false; 2099252723Sdim bool Success = joinCopy(CurrList[i], Again); 2100245431Sdim Progress |= Success; 2101245431Sdim if (Success || !Again) 2102252723Sdim CurrList[i] = 0; 2103245431Sdim } 2104245431Sdim return Progress; 2105245431Sdim} 2106245431Sdim 2107245431Sdimvoid 2108245431SdimRegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { 2109224145Sdim DEBUG(dbgs() << MBB->getName() << ":\n"); 2110224145Sdim 2111245431Sdim // Collect all copy-like instructions in MBB. Don't start coalescing anything 2112245431Sdim // yet, it might invalidate the iterator. 2113245431Sdim const unsigned PrevSize = WorkList.size(); 2114252723Sdim if (JoinGlobalCopies) { 2115252723Sdim // Coalesce copies bottom-up to coalesce local defs before local uses. They 2116252723Sdim // are not inherently easier to resolve, but slightly preferable until we 2117252723Sdim // have local live range splitting. In particular this is required by 2118252723Sdim // cmp+jmp macro fusion. 2119263509Sdim for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 2120263509Sdim MII != E; ++MII) { 2121252723Sdim if (!MII->isCopyLike()) 2122252723Sdim continue; 2123252723Sdim if (isLocalCopy(&(*MII), LIS)) 2124252723Sdim LocalWorkList.push_back(&(*MII)); 2125252723Sdim else 2126252723Sdim WorkList.push_back(&(*MII)); 2127252723Sdim } 2128252723Sdim } 2129252723Sdim else { 2130252723Sdim for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 2131252723Sdim MII != E; ++MII) 2132252723Sdim if (MII->isCopyLike()) 2133252723Sdim WorkList.push_back(MII); 2134252723Sdim } 2135245431Sdim // Try coalescing the collected copies immediately, and remove the nulls. 2136245431Sdim // This prevents the WorkList from getting too large since most copies are 2137245431Sdim // joinable on the first attempt. 2138252723Sdim MutableArrayRef<MachineInstr*> 2139252723Sdim CurrList(WorkList.begin() + PrevSize, WorkList.end()); 2140252723Sdim if (copyCoalesceWorkList(CurrList)) 2141245431Sdim WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), 2142245431Sdim (MachineInstr*)0), WorkList.end()); 2143224145Sdim} 2144224145Sdim 2145252723Sdimvoid RegisterCoalescer::coalesceLocals() { 2146252723Sdim copyCoalesceWorkList(LocalWorkList); 2147252723Sdim for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) { 2148252723Sdim if (LocalWorkList[j]) 2149252723Sdim WorkList.push_back(LocalWorkList[j]); 2150252723Sdim } 2151252723Sdim LocalWorkList.clear(); 2152252723Sdim} 2153252723Sdim 2154245431Sdimvoid RegisterCoalescer::joinAllIntervals() { 2155224145Sdim DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 2156252723Sdim assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around."); 2157224145Sdim 2158252723Sdim std::vector<MBBPriorityInfo> MBBs; 2159252723Sdim MBBs.reserve(MF->size()); 2160252723Sdim for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 2161252723Sdim MachineBasicBlock *MBB = I; 2162252723Sdim MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB), 2163252723Sdim JoinSplitEdges && isSplitEdge(MBB))); 2164252723Sdim } 2165252723Sdim array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority); 2166224145Sdim 2167252723Sdim // Coalesce intervals in MBB priority order. 2168252723Sdim unsigned CurrDepth = UINT_MAX; 2169252723Sdim for (unsigned i = 0, e = MBBs.size(); i != e; ++i) { 2170252723Sdim // Try coalescing the collected local copies for deeper loops. 2171252723Sdim if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) { 2172252723Sdim coalesceLocals(); 2173252723Sdim CurrDepth = MBBs[i].Depth; 2174224145Sdim } 2175252723Sdim copyCoalesceInMBB(MBBs[i].MBB); 2176224145Sdim } 2177252723Sdim coalesceLocals(); 2178224145Sdim 2179224145Sdim // Joining intervals can allow other intervals to be joined. Iteratively join 2180224145Sdim // until we make no progress. 2181252723Sdim while (copyCoalesceWorkList(WorkList)) 2182245431Sdim /* empty */ ; 2183224145Sdim} 2184224145Sdim 2185224145Sdimvoid RegisterCoalescer::releaseMemory() { 2186245431Sdim ErasedInstrs.clear(); 2187245431Sdim WorkList.clear(); 2188245431Sdim DeadDefs.clear(); 2189245431Sdim InflateRegs.clear(); 2190224145Sdim} 2191224145Sdim 2192224145Sdimbool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 2193226890Sdim MF = &fn; 2194226890Sdim MRI = &fn.getRegInfo(); 2195226890Sdim TM = &fn.getTarget(); 2196226890Sdim TRI = TM->getRegisterInfo(); 2197226890Sdim TII = TM->getInstrInfo(); 2198226890Sdim LIS = &getAnalysis<LiveIntervals>(); 2199224145Sdim AA = &getAnalysis<AliasAnalysis>(); 2200226890Sdim Loops = &getAnalysis<MachineLoopInfo>(); 2201224145Sdim 2202252723Sdim const TargetSubtargetInfo &ST = TM->getSubtarget<TargetSubtargetInfo>(); 2203252723Sdim if (EnableGlobalCopies == cl::BOU_UNSET) 2204263509Sdim JoinGlobalCopies = ST.useMachineScheduler(); 2205252723Sdim else 2206252723Sdim JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE); 2207252723Sdim 2208252723Sdim // The MachineScheduler does not currently require JoinSplitEdges. This will 2209252723Sdim // either be enabled unconditionally or replaced by a more general live range 2210252723Sdim // splitting optimization. 2211252723Sdim JoinSplitEdges = EnableJoinSplits; 2212252723Sdim 2213224145Sdim DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 2214245431Sdim << "********** Function: " << MF->getName() << '\n'); 2215224145Sdim 2216224145Sdim if (VerifyCoalescing) 2217226890Sdim MF->verify(this, "Before register coalescing"); 2218224145Sdim 2219224145Sdim RegClassInfo.runOnMachineFunction(fn); 2220224145Sdim 2221224145Sdim // Join (coalesce) intervals if requested. 2222245431Sdim if (EnableJoining) 2223245431Sdim joinAllIntervals(); 2224224145Sdim 2225226890Sdim // After deleting a lot of copies, register classes may be less constrained. 2226245431Sdim // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 -> 2227226890Sdim // DPR inflation. 2228226890Sdim array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 2229226890Sdim InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 2230226890Sdim InflateRegs.end()); 2231226890Sdim DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 2232226890Sdim for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 2233226890Sdim unsigned Reg = InflateRegs[i]; 2234226890Sdim if (MRI->reg_nodbg_empty(Reg)) 2235226890Sdim continue; 2236226890Sdim if (MRI->recomputeRegClass(Reg, *TM)) { 2237226890Sdim DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 2238226890Sdim << MRI->getRegClass(Reg)->getName() << '\n'); 2239226890Sdim ++NumInflated; 2240226890Sdim } 2241226890Sdim } 2242226890Sdim 2243224145Sdim DEBUG(dump()); 2244224145Sdim if (VerifyCoalescing) 2245226890Sdim MF->verify(this, "After register coalescing"); 2246224145Sdim return true; 2247224145Sdim} 2248224145Sdim 2249224145Sdim/// print - Implement the dump method. 2250224145Sdimvoid RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 2251226890Sdim LIS->print(O, m); 2252224145Sdim} 2253