lib/CodeGen/RegisterCoalescer.cpp

   1 //===- RegisterCoalescer.cpp - Generic Register Coalescing Interface -------==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the generic RegisterCoalescer interface which
  11 // is used as the common interface used by all clients and
  12 // implementations of register coalescing.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "regalloc"
  17 #include "RegisterCoalescer.h"
  18 #include "LiveDebugVariables.h"
  19 #include "VirtRegMap.h"
  20
  21 #include "llvm/Pass.h"
  22 #include "llvm/Value.h"
  23 #include "llvm/ADT/OwningPtr.h"
  24 #include "llvm/ADT/STLExtras.h"
  25 #include "llvm/ADT/SmallSet.h"
  26 #include "llvm/ADT/Statistic.h"
  27 #include "llvm/Analysis/AliasAnalysis.h"
  28 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  29 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  30 #include "llvm/CodeGen/LiveRangeEdit.h"
  31 #include "llvm/CodeGen/MachineFrameInfo.h"
  32 #include "llvm/CodeGen/MachineInstr.h"
  33 #include "llvm/CodeGen/MachineInstr.h"
  34 #include "llvm/CodeGen/MachineLoopInfo.h"
  35 #include "llvm/CodeGen/MachineRegisterInfo.h"
  36 #include "llvm/CodeGen/MachineRegisterInfo.h"
  37 #include "llvm/CodeGen/Passes.h"
  38 #include "llvm/CodeGen/RegisterClassInfo.h"
  39 #include "llvm/Support/CommandLine.h"
  40 #include "llvm/Support/Debug.h"
  41 #include "llvm/Support/ErrorHandling.h"
  42 #include "llvm/Support/raw_ostream.h"
  43 #include "llvm/Target/TargetInstrInfo.h"
  44 #include "llvm/Target/TargetInstrInfo.h"
  45 #include "llvm/Target/TargetMachine.h"
  46 #include "llvm/Target/TargetOptions.h"
  47 #include "llvm/Target/TargetRegisterInfo.h"
  48 #include <algorithm>
  49 #include <cmath>
  50 using namespace llvm;
  51
  52 STATISTIC(numJoins    , "Number of interval joins performed");
  53 STATISTIC(numCrossRCs , "Number of cross class joins performed");
  54 STATISTIC(numCommutes , "Number of instruction commuting performed");
  55 STATISTIC(numExtends  , "Number of copies extended");
  56 STATISTIC(NumReMats   , "Number of instructions re-materialized");
  57 STATISTIC(NumInflated , "Number of register classes inflated");
  58 STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested");
  59 STATISTIC(NumLaneResolves,  "Number of dead lane conflicts resolved");
  60
  61 static cl::opt<bool>
  62 EnableJoining("join-liveintervals",
  63               cl::desc("Coalesce copies (default=true)"),
  64               cl::init(true));
  65
  66 static cl::opt<bool>
  67 VerifyCoalescing("verify-coalescing",
  68          cl::desc("Verify machine instrs before and after register coalescing"),
  69          cl::Hidden);
  70
  71 namespace {
  72   class RegisterCoalescer : public MachineFunctionPass,
  73                             private LiveRangeEdit::Delegate {
  74     MachineFunction* MF;
  75     MachineRegisterInfo* MRI;
  76     const TargetMachine* TM;
  77     const TargetRegisterInfo* TRI;
  78     const TargetInstrInfo* TII;
  79     LiveIntervals *LIS;
  80     LiveDebugVariables *LDV;
  81     const MachineLoopInfo* Loops;
  82     AliasAnalysis *AA;
  83     RegisterClassInfo RegClassInfo;
  84
  85     /// WorkList - Copy instructions yet to be coalesced.
  86     SmallVector<MachineInstr*, 8> WorkList;
  87
  88     /// ErasedInstrs - Set of instruction pointers that have been erased, and
  89     /// that may be present in WorkList.
  90     SmallPtrSet<MachineInstr*, 8> ErasedInstrs;
  91
  92     /// Dead instructions that are about to be deleted.
  93     SmallVector<MachineInstr*, 8> DeadDefs;
  94
  95     /// Virtual registers to be considered for register class inflation.
  96     SmallVector<unsigned, 8> InflateRegs;
  97
  98     /// Recursively eliminate dead defs in DeadDefs.
  99     void eliminateDeadDefs();
 100
 101     /// LiveRangeEdit callback.
 102     void LRE_WillEraseInstruction(MachineInstr *MI);
 103
 104     /// joinAllIntervals - join compatible live intervals
 105     void joinAllIntervals();
 106
 107     /// copyCoalesceInMBB - Coalesce copies in the specified MBB, putting
 108     /// copies that cannot yet be coalesced into WorkList.
 109     void copyCoalesceInMBB(MachineBasicBlock *MBB);
 110
 111     /// copyCoalesceWorkList - Try to coalesce all copies in WorkList after
 112     /// position From. Return true if any progress was made.
 113     bool copyCoalesceWorkList(unsigned From = 0);
 114
 115     /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 116     /// which are the src/dst of the copy instruction CopyMI.  This returns
 117     /// true if the copy was successfully coalesced away. If it is not
 118     /// currently possible to coalesce this interval, but it may be possible if
 119     /// other things get coalesced, then it returns true by reference in
 120     /// 'Again'.
 121     bool joinCopy(MachineInstr *TheCopy, bool &Again);
 122
 123     /// joinIntervals - Attempt to join these two intervals.  On failure, this
 124     /// returns false.  The output "SrcInt" will not have been modified, so we
 125     /// can use this information below to update aliases.
 126     bool joinIntervals(CoalescerPair &CP);
 127
 128     /// Attempt joining two virtual registers. Return true on success.
 129     bool joinVirtRegs(CoalescerPair &CP);
 130
 131     /// Attempt joining with a reserved physreg.
 132     bool joinReservedPhysReg(CoalescerPair &CP);
 133
 134     /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy. If
 135     /// the source value number is defined by a copy from the destination reg
 136     /// see if we can merge these two destination reg valno# into a single
 137     /// value number, eliminating a copy.
 138     bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI);
 139
 140     /// hasOtherReachingDefs - Return true if there are definitions of IntB
 141     /// other than BValNo val# that can reach uses of AValno val# of IntA.
 142     bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB,
 143                               VNInfo *AValNo, VNInfo *BValNo);
 144
 145     /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy.
 146     /// If the source value number is defined by a commutable instruction and
 147     /// its other operand is coalesced to the copy dest register, see if we
 148     /// can transform the copy into a noop by commuting the definition.
 149     bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI);
 150
 151     /// reMaterializeTrivialDef - If the source of a copy is defined by a
 152     /// trivial computation, replace the copy by rematerialize the definition.
 153     bool reMaterializeTrivialDef(LiveInterval &SrcInt, unsigned DstReg,
 154                                  MachineInstr *CopyMI);
 155
 156     /// canJoinPhys - Return true if a physreg copy should be joined.
 157     bool canJoinPhys(CoalescerPair &CP);
 158
 159     /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and
 160     /// update the subregister number if it is not zero. If DstReg is a
 161     /// physical register and the existing subregister number of the def / use
 162     /// being updated is not zero, make sure to set it to the correct physical
 163     /// subregister.
 164     void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx);
 165
 166     /// eliminateUndefCopy - Handle copies of undef values.
 167     bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP);
 168
 169   public:
 170     static char ID; // Class identification, replacement for typeinfo
 171     RegisterCoalescer() : MachineFunctionPass(ID) {
 172       initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
 173     }
 174
 175     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 176
 177     virtual void releaseMemory();
 178
 179     /// runOnMachineFunction - pass entry point
 180     virtual bool runOnMachineFunction(MachineFunction&);
 181
 182     /// print - Implement the dump method.
 183     virtual void print(raw_ostream &O, const Module* = 0) const;
 184   };
 185 } /// end anonymous namespace
 186
 187 char &llvm::RegisterCoalescerID = RegisterCoalescer::ID;
 188
 189 INITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing",
 190                       "Simple Register Coalescing", false, false)
 191 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
 192 INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
 193 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
 194 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 195 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 196 INITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing",
 197                     "Simple Register Coalescing", false, false)
 198
 199 char RegisterCoalescer::ID = 0;
 200
 201 static unsigned compose(const TargetRegisterInfo &tri, unsigned a, unsigned b) {
 202   if (!a) return b;
 203   if (!b) return a;
 204   return tri.composeSubRegIndices(a, b);
 205 }
 206
 207 static bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI,
 208                         unsigned &Src, unsigned &Dst,
 209                         unsigned &SrcSub, unsigned &DstSub) {
 210   if (MI->isCopy()) {
 211     Dst = MI->getOperand(0).getReg();
 212     DstSub = MI->getOperand(0).getSubReg();
 213     Src = MI->getOperand(1).getReg();
 214     SrcSub = MI->getOperand(1).getSubReg();
 215   } else if (MI->isSubregToReg()) {
 216     Dst = MI->getOperand(0).getReg();
 217     DstSub = compose(tri, MI->getOperand(0).getSubReg(),
 218                      MI->getOperand(3).getImm());
 219     Src = MI->getOperand(2).getReg();
 220     SrcSub = MI->getOperand(2).getSubReg();
 221   } else
 222     return false;
 223   return true;
 224 }
 225
 226 bool CoalescerPair::setRegisters(const MachineInstr *MI) {
 227   SrcReg = DstReg = 0;
 228   SrcIdx = DstIdx = 0;
 229   NewRC = 0;
 230   Flipped = CrossClass = false;
 231
 232   unsigned Src, Dst, SrcSub, DstSub;
 233   if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub))
 234     return false;
 235   Partial = SrcSub || DstSub;
 236
 237   // If one register is a physreg, it must be Dst.
 238   if (TargetRegisterInfo::isPhysicalRegister(Src)) {
 239     if (TargetRegisterInfo::isPhysicalRegister(Dst))
 240       return false;
 241     std::swap(Src, Dst);
 242     std::swap(SrcSub, DstSub);
 243     Flipped = true;
 244   }
 245
 246   const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo();
 247
 248   if (TargetRegisterInfo::isPhysicalRegister(Dst)) {
 249     // Eliminate DstSub on a physreg.
 250     if (DstSub) {
 251       Dst = TRI.getSubReg(Dst, DstSub);
 252       if (!Dst) return false;
 253       DstSub = 0;
 254     }
 255
 256     // Eliminate SrcSub by picking a corresponding Dst superregister.
 257     if (SrcSub) {
 258       Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src));
 259       if (!Dst) return false;
 260       SrcSub = 0;
 261     } else if (!MRI.getRegClass(Src)->contains(Dst)) {
 262       return false;
 263     }
 264   } else {
 265     // Both registers are virtual.
 266     const TargetRegisterClass *SrcRC = MRI.getRegClass(Src);
 267     const TargetRegisterClass *DstRC = MRI.getRegClass(Dst);
 268
 269     // Both registers have subreg indices.
 270     if (SrcSub && DstSub) {
 271       // Copies between different sub-registers are never coalescable.
 272       if (Src == Dst && SrcSub != DstSub)
 273         return false;
 274
 275       NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub,
 276                                          SrcIdx, DstIdx);
 277       if (!NewRC)
 278         return false;
 279     } else if (DstSub) {
 280       // SrcReg will be merged with a sub-register of DstReg.
 281       SrcIdx = DstSub;
 282       NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub);
 283     } else if (SrcSub) {
 284       // DstReg will be merged with a sub-register of SrcReg.
 285       DstIdx = SrcSub;
 286       NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub);
 287     } else {
 288       // This is a straight copy without sub-registers.
 289       NewRC = TRI.getCommonSubClass(DstRC, SrcRC);
 290     }
 291
 292     // The combined constraint may be impossible to satisfy.
 293     if (!NewRC)
 294       return false;
 295
 296     // Prefer SrcReg to be a sub-register of DstReg.
 297     // FIXME: Coalescer should support subregs symmetrically.
 298     if (DstIdx && !SrcIdx) {
 299       std::swap(Src, Dst);
 300       std::swap(SrcIdx, DstIdx);
 301       Flipped = !Flipped;
 302     }
 303
 304     CrossClass = NewRC != DstRC || NewRC != SrcRC;
 305   }
 306   // Check our invariants
 307   assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual");
 308   assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) &&
 309          "Cannot have a physical SubIdx");
 310   SrcReg = Src;
 311   DstReg = Dst;
 312   return true;
 313 }
 314
 315 bool CoalescerPair::flip() {
 316   if (TargetRegisterInfo::isPhysicalRegister(DstReg))
 317     return false;
 318   std::swap(SrcReg, DstReg);
 319   std::swap(SrcIdx, DstIdx);
 320   Flipped = !Flipped;
 321   return true;
 322 }
 323
 324 bool CoalescerPair::isCoalescable(const MachineInstr *MI) const {
 325   if (!MI)
 326     return false;
 327   unsigned Src, Dst, SrcSub, DstSub;
 328   if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub))
 329     return false;
 330
 331   // Find the virtual register that is SrcReg.
 332   if (Dst == SrcReg) {
 333     std::swap(Src, Dst);
 334     std::swap(SrcSub, DstSub);
 335   } else if (Src != SrcReg) {
 336     return false;
 337   }
 338
 339   // Now check that Dst matches DstReg.
 340   if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
 341     if (!TargetRegisterInfo::isPhysicalRegister(Dst))
 342       return false;
 343     assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state.");
 344     // DstSub could be set for a physreg from INSERT_SUBREG.
 345     if (DstSub)
 346       Dst = TRI.getSubReg(Dst, DstSub);
 347     // Full copy of Src.
 348     if (!SrcSub)
 349       return DstReg == Dst;
 350     // This is a partial register copy. Check that the parts match.
 351     return TRI.getSubReg(DstReg, SrcSub) == Dst;
 352   } else {
 353     // DstReg is virtual.
 354     if (DstReg != Dst)
 355       return false;
 356     // Registers match, do the subregisters line up?
 357     return compose(TRI, SrcIdx, SrcSub) == compose(TRI, DstIdx, DstSub);
 358   }
 359 }
 360
 361 void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const {
 362   AU.setPreservesCFG();
 363   AU.addRequired<AliasAnalysis>();
 364   AU.addRequired<LiveIntervals>();
 365   AU.addPreserved<LiveIntervals>();
 366   AU.addRequired<LiveDebugVariables>();
 367   AU.addPreserved<LiveDebugVariables>();
 368   AU.addPreserved<SlotIndexes>();
 369   AU.addRequired<MachineLoopInfo>();
 370   AU.addPreserved<MachineLoopInfo>();
 371   AU.addPreservedID(MachineDominatorsID);
 372   MachineFunctionPass::getAnalysisUsage(AU);
 373 }
 374
 375 void RegisterCoalescer::eliminateDeadDefs() {
 376   SmallVector<LiveInterval*, 8> NewRegs;
 377   LiveRangeEdit(0, NewRegs, *MF, *LIS, 0, this).eliminateDeadDefs(DeadDefs);
 378 }
 379
 380 // Callback from eliminateDeadDefs().
 381 void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) {
 382   // MI may be in WorkList. Make sure we don't visit it.
 383   ErasedInstrs.insert(MI);
 384 }
 385
 386 /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA
 387 /// being the source and IntB being the dest, thus this defines a value number
 388 /// in IntB.  If the source value number (in IntA) is defined by a copy from B,
 389 /// see if we can merge these two pieces of B into a single value number,
 390 /// eliminating a copy.  For example:
 391 ///
 392 ///  A3 = B0
 393 ///    ...
 394 ///  B1 = A3      <- this copy
 395 ///
 396 /// In this case, B0 can be extended to where the B1 copy lives, allowing the B1
 397 /// value number to be replaced with B0 (which simplifies the B liveinterval).
 398 ///
 399 /// This returns true if an interval was modified.
 400 ///
 401 bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,
 402                                              MachineInstr *CopyMI) {
 403   assert(!CP.isPartial() && "This doesn't work for partial copies.");
 404   assert(!CP.isPhys() && "This doesn't work for physreg copies.");
 405
 406   LiveInterval &IntA =
 407     LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
 408   LiveInterval &IntB =
 409     LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
 410   SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot();
 411
 412   // BValNo is a value number in B that is defined by a copy from A.  'B3' in
 413   // the example above.
 414   LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
 415   if (BLR == IntB.end()) return false;
 416   VNInfo *BValNo = BLR->valno;
 417
 418   // Get the location that B is defined at.  Two options: either this value has
 419   // an unknown definition point or it is defined at CopyIdx.  If unknown, we
 420   // can't process it.
 421   if (BValNo->def != CopyIdx) return false;
 422
 423   // AValNo is the value number in A that defines the copy, A3 in the example.
 424   SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true);
 425   LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx);
 426   // The live range might not exist after fun with physreg coalescing.
 427   if (ALR == IntA.end()) return false;
 428   VNInfo *AValNo = ALR->valno;
 429
 430   // If AValNo is defined as a copy from IntB, we can potentially process this.
 431   // Get the instruction that defines this value number.
 432   MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def);
 433   if (!CP.isCoalescable(ACopyMI))
 434     return false;
 435
 436   // Get the LiveRange in IntB that this value number starts with.
 437   LiveInterval::iterator ValLR =
 438     IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot());
 439   if (ValLR == IntB.end())
 440     return false;
 441
 442   // Make sure that the end of the live range is inside the same block as
 443   // CopyMI.
 444   MachineInstr *ValLREndInst =
 445     LIS->getInstructionFromIndex(ValLR->end.getPrevSlot());
 446   if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent())
 447     return false;
 448
 449   // Okay, we now know that ValLR ends in the same block that the CopyMI
 450   // live-range starts.  If there are no intervening live ranges between them in
 451   // IntB, we can merge them.
 452   if (ValLR+1 != BLR) return false;
 453
 454   DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI));
 455
 456   SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start;
 457   // We are about to delete CopyMI, so need to remove it as the 'instruction
 458   // that defines this value #'. Update the valnum with the new defining
 459   // instruction #.
 460   BValNo->def = FillerStart;
 461
 462   // Okay, we can merge them.  We need to insert a new liverange:
 463   // [ValLR.end, BLR.begin) of either value number, then we merge the
 464   // two value numbers.
 465   IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));
 466
 467   // Okay, merge "B1" into the same value number as "B0".
 468   if (BValNo != ValLR->valno)
 469     IntB.MergeValueNumberInto(BValNo, ValLR->valno);
 470   DEBUG(dbgs() << "   result = " << IntB << '\n');
 471
 472   // If the source instruction was killing the source register before the
 473   // merge, unset the isKill marker given the live range has been extended.
 474   int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true);
 475   if (UIdx != -1) {
 476     ValLREndInst->getOperand(UIdx).setIsKill(false);
 477   }
 478
 479   // Rewrite the copy. If the copy instruction was killing the destination
 480   // register before the merge, find the last use and trim the live range. That
 481   // will also add the isKill marker.
 482   CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI);
 483   if (ALR->end == CopyIdx)
 484     LIS->shrinkToUses(&IntA);
 485
 486   ++numExtends;
 487   return true;
 488 }
 489
 490 /// hasOtherReachingDefs - Return true if there are definitions of IntB
 491 /// other than BValNo val# that can reach uses of AValno val# of IntA.
 492 bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA,
 493                                              LiveInterval &IntB,
 494                                              VNInfo *AValNo,
 495                                              VNInfo *BValNo) {
 496   // If AValNo has PHI kills, conservatively assume that IntB defs can reach
 497   // the PHI values.
 498   if (LIS->hasPHIKill(IntA, AValNo))
 499     return true;
 500
 501   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
 502        AI != AE; ++AI) {
 503     if (AI->valno != AValNo) continue;
 504     LiveInterval::Ranges::iterator BI =
 505       std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start);
 506     if (BI != IntB.ranges.begin())
 507       --BI;
 508     for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) {
 509       if (BI->valno == BValNo)
 510         continue;
 511       if (BI->start <= AI->start && BI->end > AI->start)
 512         return true;
 513       if (BI->start > AI->start && BI->start < AI->end)
 514         return true;
 515     }
 516   }
 517   return false;
 518 }
 519
 520 /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with
 521 /// IntA being the source and IntB being the dest, thus this defines a value
 522 /// number in IntB.  If the source value number (in IntA) is defined by a
 523 /// commutable instruction and its other operand is coalesced to the copy dest
 524 /// register, see if we can transform the copy into a noop by commuting the
 525 /// definition. For example,
 526 ///
 527 ///  A3 = op A2 B0<kill>
 528 ///    ...
 529 ///  B1 = A3      <- this copy
 530 ///    ...
 531 ///     = op A3   <- more uses
 532 ///
 533 /// ==>
 534 ///
 535 ///  B2 = op B0 A2<kill>
 536 ///    ...
 537 ///  B1 = B2      <- now an identify copy
 538 ///    ...
 539 ///     = op B2   <- more uses
 540 ///
 541 /// This returns true if an interval was modified.
 542 ///
 543 bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP,
 544                                                  MachineInstr *CopyMI) {
 545   assert (!CP.isPhys());
 546
 547   SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot();
 548
 549   LiveInterval &IntA =
 550     LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
 551   LiveInterval &IntB =
 552     LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
 553
 554   // BValNo is a value number in B that is defined by a copy from A. 'B3' in
 555   // the example above.
 556   VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx);
 557   if (!BValNo || BValNo->def != CopyIdx)
 558     return false;
 559
 560   assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
 561
 562   // AValNo is the value number in A that defines the copy, A3 in the example.
 563   VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true));
 564   assert(AValNo && "COPY source not live");
 565   if (AValNo->isPHIDef() || AValNo->isUnused())
 566     return false;
 567   MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def);
 568   if (!DefMI)
 569     return false;
 570   if (!DefMI->isCommutable())
 571     return false;
 572   // If DefMI is a two-address instruction then commuting it will change the
 573   // destination register.
 574   int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg);
 575   assert(DefIdx != -1);
 576   unsigned UseOpIdx;
 577   if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx))
 578     return false;
 579   unsigned Op1, Op2, NewDstIdx;
 580   if (!TII->findCommutedOpIndices(DefMI, Op1, Op2))
 581     return false;
 582   if (Op1 == UseOpIdx)
 583     NewDstIdx = Op2;
 584   else if (Op2 == UseOpIdx)
 585     NewDstIdx = Op1;
 586   else
 587     return false;
 588
 589   MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
 590   unsigned NewReg = NewDstMO.getReg();
 591   if (NewReg != IntB.reg || !LiveRangeQuery(IntB, AValNo->def).isKill())
 592     return false;
 593
 594   // Make sure there are no other definitions of IntB that would reach the
 595   // uses which the new definition can reach.
 596   if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
 597     return false;
 598
 599   // If some of the uses of IntA.reg is already coalesced away, return false.
 600   // It's not possible to determine whether it's safe to perform the coalescing.
 601   for (MachineRegisterInfo::use_nodbg_iterator UI =
 602          MRI->use_nodbg_begin(IntA.reg),
 603        UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
 604     MachineInstr *UseMI = &*UI;
 605     SlotIndex UseIdx = LIS->getInstructionIndex(UseMI);
 606     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
 607     if (ULR == IntA.end() || ULR->valno != AValNo)
 608       continue;
 609     // If this use is tied to a def, we can't rewrite the register.
 610     if (UseMI->isRegTiedToDefOperand(UI.getOperandNo()))
 611       return false;
 612   }
 613
 614   DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t'
 615                << *DefMI);
 616
 617   // At this point we have decided that it is legal to do this
 618   // transformation.  Start by commuting the instruction.
 619   MachineBasicBlock *MBB = DefMI->getParent();
 620   MachineInstr *NewMI = TII->commuteInstruction(DefMI);
 621   if (!NewMI)
 622     return false;
 623   if (TargetRegisterInfo::isVirtualRegister(IntA.reg) &&
 624       TargetRegisterInfo::isVirtualRegister(IntB.reg) &&
 625       !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg)))
 626     return false;
 627   if (NewMI != DefMI) {
 628     LIS->ReplaceMachineInstrInMaps(DefMI, NewMI);
 629     MachineBasicBlock::iterator Pos = DefMI;
 630     MBB->insert(Pos, NewMI);
 631     MBB->erase(DefMI);
 632   }
 633   unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false);
 634   NewMI->getOperand(OpIdx).setIsKill();
 635
 636   // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
 637   // A = or A, B
 638   // ...
 639   // B = A
 640   // ...
 641   // C = A<kill>
 642   // ...
 643   //   = B
 644
 645   // Update uses of IntA of the specific Val# with IntB.
 646   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg),
 647          UE = MRI->use_end(); UI != UE;) {
 648     MachineOperand &UseMO = UI.getOperand();
 649     MachineInstr *UseMI = &*UI;
 650     ++UI;
 651     if (UseMI->isDebugValue()) {
 652       // FIXME These don't have an instruction index.  Not clear we have enough
 653       // info to decide whether to do this replacement or not.  For now do it.
 654       UseMO.setReg(NewReg);
 655       continue;
 656     }
 657     SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true);
 658     LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
 659     if (ULR == IntA.end() || ULR->valno != AValNo)
 660       continue;
 661     // Kill flags are no longer accurate. They are recomputed after RA.
 662     UseMO.setIsKill(false);
 663     if (TargetRegisterInfo::isPhysicalRegister(NewReg))
 664       UseMO.substPhysReg(NewReg, *TRI);
 665     else
 666       UseMO.setReg(NewReg);
 667     if (UseMI == CopyMI)
 668       continue;
 669     if (!UseMI->isCopy())
 670       continue;
 671     if (UseMI->getOperand(0).getReg() != IntB.reg ||
 672         UseMI->getOperand(0).getSubReg())
 673       continue;
 674
 675     // This copy will become a noop. If it's defining a new val#, merge it into
 676     // BValNo.
 677     SlotIndex DefIdx = UseIdx.getRegSlot();
 678     VNInfo *DVNI = IntB.getVNInfoAt(DefIdx);
 679     if (!DVNI)
 680       continue;
 681     DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI);
 682     assert(DVNI->def == DefIdx);
 683     BValNo = IntB.MergeValueNumberInto(BValNo, DVNI);
 684     ErasedInstrs.insert(UseMI);
 685     LIS->RemoveMachineInstrFromMaps(UseMI);
 686     UseMI->eraseFromParent();
 687   }
 688
 689   // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition
 690   // is updated.
 691   VNInfo *ValNo = BValNo;
 692   ValNo->def = AValNo->def;
 693   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
 694        AI != AE; ++AI) {
 695     if (AI->valno != AValNo) continue;
 696     IntB.addRange(LiveRange(AI->start, AI->end, ValNo));
 697   }
 698   DEBUG(dbgs() << "\t\textended: " << IntB << '\n');
 699
 700   IntA.removeValNo(AValNo);
 701   DEBUG(dbgs() << "\t\ttrimmed:  " << IntA << '\n');
 702   ++numCommutes;
 703   return true;
 704 }
 705
 706 /// reMaterializeTrivialDef - If the source of a copy is defined by a trivial
 707 /// computation, replace the copy by rematerialize the definition.
 708 bool RegisterCoalescer::reMaterializeTrivialDef(LiveInterval &SrcInt,
 709                                                 unsigned DstReg,
 710                                                 MachineInstr *CopyMI) {
 711   SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true);
 712   LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx);
 713   assert(SrcLR != SrcInt.end() && "Live range not found!");
 714   VNInfo *ValNo = SrcLR->valno;
 715   if (ValNo->isPHIDef() || ValNo->isUnused())
 716     return false;
 717   MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def);
 718   if (!DefMI)
 719     return false;
 720   assert(DefMI && "Defining instruction disappeared");
 721   if (!DefMI->isAsCheapAsAMove())
 722     return false;
 723   if (!TII->isTriviallyReMaterializable(DefMI, AA))
 724     return false;
 725   bool SawStore = false;
 726   if (!DefMI->isSafeToMove(TII, AA, SawStore))
 727     return false;
 728   const MCInstrDesc &MCID = DefMI->getDesc();
 729   if (MCID.getNumDefs() != 1)
 730     return false;
 731   if (!DefMI->isImplicitDef()) {
 732     // Make sure the copy destination register class fits the instruction
 733     // definition register class. The mismatch can happen as a result of earlier
 734     // extract_subreg, insert_subreg, subreg_to_reg coalescing.
 735     const TargetRegisterClass *RC = TII->getRegClass(MCID, 0, TRI, *MF);
 736     if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
 737       if (MRI->getRegClass(DstReg) != RC)
 738         return false;
 739     } else if (!RC->contains(DstReg))
 740       return false;
 741   }
 742
 743   MachineBasicBlock *MBB = CopyMI->getParent();
 744   MachineBasicBlock::iterator MII =
 745     llvm::next(MachineBasicBlock::iterator(CopyMI));
 746   TII->reMaterialize(*MBB, MII, DstReg, 0, DefMI, *TRI);
 747   MachineInstr *NewMI = prior(MII);
 748
 749   // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86).
 750   // We need to remember these so we can add intervals once we insert
 751   // NewMI into SlotIndexes.
 752   SmallVector<unsigned, 4> NewMIImplDefs;
 753   for (unsigned i = NewMI->getDesc().getNumOperands(),
 754          e = NewMI->getNumOperands(); i != e; ++i) {
 755     MachineOperand &MO = NewMI->getOperand(i);
 756     if (MO.isReg()) {
 757       assert(MO.isDef() && MO.isImplicit() && MO.isDead() &&
 758              TargetRegisterInfo::isPhysicalRegister(MO.getReg()));
 759       NewMIImplDefs.push_back(MO.getReg());
 760     }
 761   }
 762
 763   // CopyMI may have implicit operands, transfer them over to the newly
 764   // rematerialized instruction. And update implicit def interval valnos.
 765   for (unsigned i = CopyMI->getDesc().getNumOperands(),
 766          e = CopyMI->getNumOperands(); i != e; ++i) {
 767     MachineOperand &MO = CopyMI->getOperand(i);
 768     if (MO.isReg()) {
 769       assert(MO.isImplicit() && "No explicit operands after implict operands.");
 770       // Discard VReg implicit defs.
 771       if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) {
 772         NewMI->addOperand(MO);
 773       }
 774     }
 775   }
 776
 777   LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI);
 778
 779   SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
 780   for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) {
 781     unsigned Reg = NewMIImplDefs[i];
 782     for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
 783       if (LiveInterval *LI = LIS->getCachedRegUnit(*Units))
 784         LI->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
 785   }
 786
 787   CopyMI->eraseFromParent();
 788   ErasedInstrs.insert(CopyMI);
 789   DEBUG(dbgs() << "Remat: " << *NewMI);
 790   ++NumReMats;
 791
 792   // The source interval can become smaller because we removed a use.
 793   LIS->shrinkToUses(&SrcInt, &DeadDefs);
 794   if (!DeadDefs.empty())
 795     eliminateDeadDefs();
 796
 797   return true;
 798 }
 799
 800 /// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef>
 801 /// values, it only removes local variables. When we have a copy like:
 802 ///
 803 ///   %vreg1 = COPY %vreg2<undef>
 804 ///
 805 /// We delete the copy and remove the corresponding value number from %vreg1.
 806 /// Any uses of that value number are marked as <undef>.
 807 bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI,
 808                                            const CoalescerPair &CP) {
 809   SlotIndex Idx = LIS->getInstructionIndex(CopyMI);
 810   LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg());
 811   if (SrcInt->liveAt(Idx))
 812     return false;
 813   LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg());
 814   if (DstInt->liveAt(Idx))
 815     return false;
 816
 817   // No intervals are live-in to CopyMI - it is undef.
 818   if (CP.isFlipped())
 819     DstInt = SrcInt;
 820   SrcInt = 0;
 821
 822   VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot());
 823   assert(DeadVNI && "No value defined in DstInt");
 824   DstInt->removeValNo(DeadVNI);
 825
 826   // Find new undef uses.
 827   for (MachineRegisterInfo::reg_nodbg_iterator
 828          I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end();
 829        I != E; ++I) {
 830     MachineOperand &MO = I.getOperand();
 831     if (MO.isDef() || MO.isUndef())
 832       continue;
 833     MachineInstr *MI = MO.getParent();
 834     SlotIndex Idx = LIS->getInstructionIndex(MI);
 835     if (DstInt->liveAt(Idx))
 836       continue;
 837     MO.setIsUndef(true);
 838     DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI);
 839   }
 840   return true;
 841 }
 842
 843 /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and
 844 /// update the subregister number if it is not zero. If DstReg is a
 845 /// physical register and the existing subregister number of the def / use
 846 /// being updated is not zero, make sure to set it to the correct physical
 847 /// subregister.
 848 void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg,
 849                                           unsigned DstReg,
 850                                           unsigned SubIdx) {
 851   bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
 852   LiveInterval *DstInt = DstIsPhys ? 0 : &LIS->getInterval(DstReg);
 853
 854   // Update LiveDebugVariables.
 855   LDV->renameRegister(SrcReg, DstReg, SubIdx);
 856
 857   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg);
 858        MachineInstr *UseMI = I.skipInstruction();) {
 859     SmallVector<unsigned,8> Ops;
 860     bool Reads, Writes;
 861     tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);
 862
 863     // If SrcReg wasn't read, it may still be the case that DstReg is live-in
 864     // because SrcReg is a sub-register.
 865     if (DstInt && !Reads && SubIdx)
 866       Reads = DstInt->liveAt(LIS->getInstructionIndex(UseMI));
 867
 868     // Replace SrcReg with DstReg in all UseMI operands.
 869     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
 870       MachineOperand &MO = UseMI->getOperand(Ops[i]);
 871
 872       // Adjust <undef> flags in case of sub-register joins. We don't want to
 873       // turn a full def into a read-modify-write sub-register def and vice
 874       // versa.
 875       if (SubIdx && MO.isDef())
 876         MO.setIsUndef(!Reads);
 877
 878       if (DstIsPhys)
 879         MO.substPhysReg(DstReg, *TRI);
 880       else
 881         MO.substVirtReg(DstReg, SubIdx, *TRI);
 882     }
 883
 884     DEBUG({
 885         dbgs() << "\t\tupdated: ";
 886         if (!UseMI->isDebugValue())
 887           dbgs() << LIS->getInstructionIndex(UseMI) << "\t";
 888         dbgs() << *UseMI;
 889       });
 890   }
 891 }
 892
 893 /// canJoinPhys - Return true if a copy involving a physreg should be joined.
 894 bool RegisterCoalescer::canJoinPhys(CoalescerPair &CP) {
 895   /// Always join simple intervals that are defined by a single copy from a
 896   /// reserved register. This doesn't increase register pressure, so it is
 897   /// always beneficial.
 898   if (!RegClassInfo.isReserved(CP.getDstReg())) {
 899     DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
 900     return false;
 901   }
 902
 903   LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg());
 904   if (CP.isFlipped() && JoinVInt.containsOneValue())
 905     return true;
 906
 907   DEBUG(dbgs() << "\tCannot join defs into reserved register.\n");
 908   return false;
 909 }
 910
 911 /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 912 /// which are the src/dst of the copy instruction CopyMI.  This returns true
 913 /// if the copy was successfully coalesced away. If it is not currently
 914 /// possible to coalesce this interval, but it may be possible if other
 915 /// things get coalesced, then it returns true by reference in 'Again'.
 916 bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
 917
 918   Again = false;
 919   DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI);
 920
 921   CoalescerPair CP(*TRI);
 922   if (!CP.setRegisters(CopyMI)) {
 923     DEBUG(dbgs() << "\tNot coalescable.\n");
 924     return false;
 925   }
 926
 927   // Dead code elimination. This really should be handled by MachineDCE, but
 928   // sometimes dead copies slip through, and we can't generate invalid live
 929   // ranges.
 930   if (!CP.isPhys() && CopyMI->allDefsAreDead()) {
 931     DEBUG(dbgs() << "\tCopy is dead.\n");
 932     DeadDefs.push_back(CopyMI);
 933     eliminateDeadDefs();
 934     return true;
 935   }
 936
 937   // Eliminate undefs.
 938   if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) {
 939     DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n");
 940     LIS->RemoveMachineInstrFromMaps(CopyMI);
 941     CopyMI->eraseFromParent();
 942     return false;  // Not coalescable.
 943   }
 944
 945   // Coalesced copies are normally removed immediately, but transformations
 946   // like removeCopyByCommutingDef() can inadvertently create identity copies.
 947   // When that happens, just join the values and remove the copy.
 948   if (CP.getSrcReg() == CP.getDstReg()) {
 949     LiveInterval &LI = LIS->getInterval(CP.getSrcReg());
 950     DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n');
 951     LiveRangeQuery LRQ(LI, LIS->getInstructionIndex(CopyMI));
 952     if (VNInfo *DefVNI = LRQ.valueDefined()) {
 953       VNInfo *ReadVNI = LRQ.valueIn();
 954       assert(ReadVNI && "No value before copy and no <undef> flag.");
 955       assert(ReadVNI != DefVNI && "Cannot read and define the same value.");
 956       LI.MergeValueNumberInto(DefVNI, ReadVNI);
 957       DEBUG(dbgs() << "\tMerged values:          " << LI << '\n');
 958     }
 959     LIS->RemoveMachineInstrFromMaps(CopyMI);
 960     CopyMI->eraseFromParent();
 961     return true;
 962   }
 963
 964   // Enforce policies.
 965   if (CP.isPhys()) {
 966     DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI)
 967                  << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx())
 968                  << '\n');
 969     if (!canJoinPhys(CP)) {
 970       // Before giving up coalescing, if definition of source is defined by
 971       // trivial computation, try rematerializing it.
 972       if (!CP.isFlipped() &&
 973           reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()),
 974                                   CP.getDstReg(), CopyMI))
 975         return true;
 976       return false;
 977     }
 978   } else {
 979     DEBUG({
 980       dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName()
 981              << " with ";
 982       if (CP.getDstIdx() && CP.getSrcIdx())
 983         dbgs() << PrintReg(CP.getDstReg()) << " in "
 984                << TRI->getSubRegIndexName(CP.getDstIdx()) << " and "
 985                << PrintReg(CP.getSrcReg()) << " in "
 986                << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n';
 987       else
 988         dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in "
 989                << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n';
 990     });
 991
 992     // When possible, let DstReg be the larger interval.
 993     if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).ranges.size() >
 994                            LIS->getInterval(CP.getDstReg()).ranges.size())
 995       CP.flip();
 996   }
 997
 998   // Okay, attempt to join these two intervals.  On failure, this returns false.
 999   // Otherwise, if one of the intervals being joined is a physreg, this method
1000   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
1001   // been modified, so we can use this information below to update aliases.
1002   if (!joinIntervals(CP)) {
1003     // Coalescing failed.
1004
1005     // If definition of source is defined by trivial computation, try
1006     // rematerializing it.
1007     if (!CP.isFlipped() &&
1008         reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()),
1009                                 CP.getDstReg(), CopyMI))
1010       return true;
1011
1012     // If we can eliminate the copy without merging the live ranges, do so now.
1013     if (!CP.isPartial() && !CP.isPhys()) {
1014       if (adjustCopiesBackFrom(CP, CopyMI) ||
1015           removeCopyByCommutingDef(CP, CopyMI)) {
1016         LIS->RemoveMachineInstrFromMaps(CopyMI);
1017         CopyMI->eraseFromParent();
1018         DEBUG(dbgs() << "\tTrivial!\n");
1019         return true;
1020       }
1021     }
1022
1023     // Otherwise, we are unable to join the intervals.
1024     DEBUG(dbgs() << "\tInterference!\n");
1025     Again = true;  // May be possible to coalesce later.
1026     return false;
1027   }
1028
1029   // Coalescing to a virtual register that is of a sub-register class of the
1030   // other. Make sure the resulting register is set to the right register class.
1031   if (CP.isCrossClass()) {
1032     ++numCrossRCs;
1033     MRI->setRegClass(CP.getDstReg(), CP.getNewRC());
1034   }
1035
1036   // Removing sub-register copies can ease the register class constraints.
1037   // Make sure we attempt to inflate the register class of DstReg.
1038   if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC()))
1039     InflateRegs.push_back(CP.getDstReg());
1040
1041   // CopyMI has been erased by joinIntervals at this point. Remove it from
1042   // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back
1043   // to the work list. This keeps ErasedInstrs from growing needlessly.
1044   ErasedInstrs.erase(CopyMI);
1045
1046   // Rewrite all SrcReg operands to DstReg.
1047   // Also update DstReg operands to include DstIdx if it is set.
1048   if (CP.getDstIdx())
1049     updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx());
1050   updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx());
1051
1052   // SrcReg is guaranteed to be the register whose live interval that is
1053   // being merged.
1054   LIS->removeInterval(CP.getSrcReg());
1055
1056   // Update regalloc hint.
1057   TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);
1058
1059   DEBUG({
1060     dbgs() << "\tJoined. Result = " << PrintReg(CP.getDstReg(), TRI);
1061     if (!CP.isPhys())
1062       dbgs() << LIS->getInterval(CP.getDstReg());
1063      dbgs() << '\n';
1064   });
1065
1066   ++numJoins;
1067   return true;
1068 }
1069
1070 /// Attempt joining with a reserved physreg.
1071 bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
1072   assert(CP.isPhys() && "Must be a physreg copy");
1073   assert(RegClassInfo.isReserved(CP.getDstReg()) && "Not a reserved register");
1074   LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
1075   DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS
1076                << '\n');
1077
1078   assert(CP.isFlipped() && RHS.containsOneValue() &&
1079          "Invalid join with reserved register");
1080
1081   // Optimization for reserved registers like ESP. We can only merge with a
1082   // reserved physreg if RHS has a single value that is a copy of CP.DstReg().
1083   // The live range of the reserved register will look like a set of dead defs
1084   // - we don't properly track the live range of reserved registers.
1085
1086   // Deny any overlapping intervals.  This depends on all the reserved
1087   // register live ranges to look like dead defs.
1088   for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI)
1089     if (RHS.overlaps(LIS->getRegUnit(*UI))) {
1090       DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n');
1091       return false;
1092     }
1093
1094   // Skip any value computations, we are not adding new values to the
1095   // reserved register.  Also skip merging the live ranges, the reserved
1096   // register live range doesn't need to be accurate as long as all the
1097   // defs are there.
1098
1099   // Delete the identity copy.
1100   MachineInstr *CopyMI = MRI->getVRegDef(RHS.reg);
1101   LIS->RemoveMachineInstrFromMaps(CopyMI);
1102   CopyMI->eraseFromParent();
1103
1104   // We don't track kills for reserved registers.
1105   MRI->clearKillFlags(CP.getSrcReg());
1106
1107   return true;
1108 }
1109
1110 //===----------------------------------------------------------------------===//
1111 //                 Interference checking and interval joining
1112 //===----------------------------------------------------------------------===//
1113 //
1114 // In the easiest case, the two live ranges being joined are disjoint, and
1115 // there is no interference to consider. It is quite common, though, to have
1116 // overlapping live ranges, and we need to check if the interference can be
1117 // resolved.
1118 //
1119 // The live range of a single SSA value forms a sub-tree of the dominator tree.
1120 // This means that two SSA values overlap if and only if the def of one value
1121 // is contained in the live range of the other value. As a special case, the
1122 // overlapping values can be defined at the same index.
1123 //
1124 // The interference from an overlapping def can be resolved in these cases:
1125 //
1126 // 1. Coalescable copies. The value is defined by a copy that would become an
1127 //    identity copy after joining SrcReg and DstReg. The copy instruction will
1128 //    be removed, and the value will be merged with the source value.
1129 //
1130 //    There can be several copies back and forth, causing many values to be
1131 //    merged into one. We compute a list of ultimate values in the joined live
1132 //    range as well as a mappings from the old value numbers.
1133 //
1134 // 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI
1135 //    predecessors have a live out value. It doesn't cause real interference,
1136 //    and can be merged into the value it overlaps. Like a coalescable copy, it
1137 //    can be erased after joining.
1138 //
1139 // 3. Copy of external value. The overlapping def may be a copy of a value that
1140 //    is already in the other register. This is like a coalescable copy, but
1141 //    the live range of the source register must be trimmed after erasing the
1142 //    copy instruction:
1143 //
1144 //      %src = COPY %ext
1145 //      %dst = COPY %ext  <-- Remove this COPY, trim the live range of %ext.
1146 //
1147 // 4. Clobbering undefined lanes. Vector registers are sometimes built by
1148 //    defining one lane at a time:
1149 //
1150 //      %dst:ssub0<def,read-undef> = FOO
1151 //      %src = BAR
1152 //      %dst:ssub1<def> = COPY %src
1153 //
1154 //    The live range of %src overlaps the %dst value defined by FOO, but
1155 //    merging %src into %dst:ssub1 is only going to clobber the ssub1 lane
1156 //    which was undef anyway.
1157 //
1158 //    The value mapping is more complicated in this case. The final live range
1159 //    will have different value numbers for both FOO and BAR, but there is no
1160 //    simple mapping from old to new values. It may even be necessary to add
1161 //    new PHI values.
1162 //
1163 // 5. Clobbering dead lanes. A def may clobber a lane of a vector register that
1164 //    is live, but never read. This can happen because we don't compute
1165 //    individual live ranges per lane.
1166 //
1167 //      %dst<def> = FOO
1168 //      %src = BAR
1169 //      %dst:ssub1<def> = COPY %src
1170 //
1171 //    This kind of interference is only resolved locally. If the clobbered
1172 //    lane value escapes the block, the join is aborted.
1173
1174 namespace {
1175 /// Track information about values in a single virtual register about to be
1176 /// joined. Objects of this class are always created in pairs - one for each
1177 /// side of the CoalescerPair.
1178 class JoinVals {
1179   LiveInterval &LI;
1180
1181   // Location of this register in the final joined register.
1182   // Either CP.DstIdx or CP.SrcIdx.
1183   unsigned SubIdx;
1184
1185   // Values that will be present in the final live range.
1186   SmallVectorImpl<VNInfo*> &NewVNInfo;
1187
1188   const CoalescerPair &CP;
1189   LiveIntervals *LIS;
1190   SlotIndexes *Indexes;
1191   const TargetRegisterInfo *TRI;
1192
1193   // Value number assignments. Maps value numbers in LI to entries in NewVNInfo.
1194   // This is suitable for passing to LiveInterval::join().
1195   SmallVector<int, 8> Assignments;
1196
1197   // Conflict resolution for overlapping values.
1198   enum ConflictResolution {
1199     // No overlap, simply keep this value.
1200     CR_Keep,
1201
1202     // Merge this value into OtherVNI and erase the defining instruction.
1203     // Used for IMPLICIT_DEF, coalescable copies, and copies from external
1204     // values.
1205     CR_Erase,
1206
1207     // Merge this value into OtherVNI but keep the defining instruction.
1208     // This is for the special case where OtherVNI is defined by the same
1209     // instruction.
1210     CR_Merge,
1211
1212     // Keep this value, and have it replace OtherVNI where possible. This
1213     // complicates value mapping since OtherVNI maps to two different values
1214     // before and after this def.
1215     // Used when clobbering undefined or dead lanes.
1216     CR_Replace,
1217
1218     // Unresolved conflict. Visit later when all values have been mapped.
1219     CR_Unresolved,
1220
1221     // Unresolvable conflict. Abort the join.
1222     CR_Impossible
1223   };
1224
1225   // Per-value info for LI. The lane bit masks are all relative to the final
1226   // joined register, so they can be compared directly between SrcReg and
1227   // DstReg.
1228   struct Val {
1229     ConflictResolution Resolution;
1230
1231     // Lanes written by this def, 0 for unanalyzed values.
1232     unsigned WriteLanes;
1233
1234     // Lanes with defined values in this register. Other lanes are undef and
1235     // safe to clobber.
1236     unsigned ValidLanes;
1237
1238     // Value in LI being redefined by this def.
1239     VNInfo *RedefVNI;
1240
1241     // Value in the other live range that overlaps this def, if any.
1242     VNInfo *OtherVNI;
1243
1244     // True when the live range of this value will be pruned because of an
1245     // overlapping CR_Replace value in the other live range.
1246     bool Pruned;
1247
1248     // True once Pruned above has been computed.
1249     bool PrunedComputed;
1250
1251     Val() : Resolution(CR_Keep), WriteLanes(0), ValidLanes(0),
1252             RedefVNI(0), OtherVNI(0), Pruned(false), PrunedComputed(false) {}
1253
1254     bool isAnalyzed() const { return WriteLanes != 0; }
1255   };
1256
1257   // One entry per value number in LI.
1258   SmallVector<Val, 8> Vals;
1259
1260   unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef);
1261   VNInfo *stripCopies(VNInfo *VNI);
1262   ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other);
1263   void computeAssignment(unsigned ValNo, JoinVals &Other);
1264   bool taintExtent(unsigned, unsigned, JoinVals&,
1265                    SmallVectorImpl<std::pair<SlotIndex, unsigned> >&);
1266   bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned);
1267   bool isPrunedValue(unsigned ValNo, JoinVals &Other);
1268
1269 public:
1270   JoinVals(LiveInterval &li, unsigned subIdx,
1271            SmallVectorImpl<VNInfo*> &newVNInfo,
1272            const CoalescerPair &cp,
1273            LiveIntervals *lis,
1274            const TargetRegisterInfo *tri)
1275     : LI(li), SubIdx(subIdx), NewVNInfo(newVNInfo), CP(cp), LIS(lis),
1276       Indexes(LIS->getSlotIndexes()), TRI(tri),
1277       Assignments(LI.getNumValNums(), -1), Vals(LI.getNumValNums())
1278   {}
1279
1280   /// Analyze defs in LI and compute a value mapping in NewVNInfo.
1281   /// Returns false if any conflicts were impossible to resolve.
1282   bool mapValues(JoinVals &Other);
1283
1284   /// Try to resolve conflicts that require all values to be mapped.
1285   /// Returns false if any conflicts were impossible to resolve.
1286   bool resolveConflicts(JoinVals &Other);
1287
1288   /// Prune the live range of values in Other.LI where they would conflict with
1289   /// CR_Replace values in LI. Collect end points for restoring the live range
1290   /// after joining.
1291   void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints);
1292
1293   /// Erase any machine instructions that have been coalesced away.
1294   /// Add erased instructions to ErasedInstrs.
1295   /// Add foreign virtual registers to ShrinkRegs if their live range ended at
1296   /// the erased instrs.
1297   void eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs,
1298                    SmallVectorImpl<unsigned> &ShrinkRegs);
1299
1300   /// Get the value assignments suitable for passing to LiveInterval::join.
1301   const int *getAssignments() const { return &Assignments[0]; }
1302 };
1303 } // end anonymous namespace
1304
1305 /// Compute the bitmask of lanes actually written by DefMI.
1306 /// Set Redef if there are any partial register definitions that depend on the
1307 /// previous value of the register.
1308 unsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) {
1309   unsigned L = 0;
1310   for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) {
1311     if (!MO->isReg() || MO->getReg() != LI.reg || !MO->isDef())
1312       continue;
1313     L |= TRI->getSubRegIndexLaneMask(compose(*TRI, SubIdx, MO->getSubReg()));
1314     if (MO->readsReg())
1315       Redef = true;
1316   }
1317   return L;
1318 }
1319
1320 /// Find the ultimate value that VNI was copied from.
1321 VNInfo *JoinVals::stripCopies(VNInfo *VNI) {
1322   while (!VNI->isPHIDef()) {
1323     MachineInstr *MI = Indexes->getInstructionFromIndex(VNI->def);
1324     assert(MI && "No defining instruction");
1325     if (!MI->isFullCopy())
1326       break;
1327     unsigned Reg = MI->getOperand(1).getReg();
1328     if (!TargetRegisterInfo::isVirtualRegister(Reg))
1329       break;
1330     LiveRangeQuery LRQ(LIS->getInterval(Reg), VNI->def);
1331     if (!LRQ.valueIn())
1332       break;
1333     VNI = LRQ.valueIn();
1334   }
1335   return VNI;
1336 }
1337
1338 /// Analyze ValNo in this live range, and set all fields of Vals[ValNo].
1339 /// Return a conflict resolution when possible, but leave the hard cases as
1340 /// CR_Unresolved.
1341 /// Recursively calls computeAssignment() on this and Other, guaranteeing that
1342 /// both OtherVNI and RedefVNI have been analyzed and mapped before returning.
1343 /// The recursion always goes upwards in the dominator tree, making loops
1344 /// impossible.
1345 JoinVals::ConflictResolution
1346 JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) {
1347   Val &V = Vals[ValNo];
1348   assert(!V.isAnalyzed() && "Value has already been analyzed!");
1349   VNInfo *VNI = LI.getValNumInfo(ValNo);
1350   if (VNI->isUnused()) {
1351     V.WriteLanes = ~0u;
1352     return CR_Keep;
1353   }
1354
1355   // Get the instruction defining this value, compute the lanes written.
1356   const MachineInstr *DefMI = 0;
1357   if (VNI->isPHIDef()) {
1358     // Conservatively assume that all lanes in a PHI are valid.
1359     V.ValidLanes = V.WriteLanes = TRI->getSubRegIndexLaneMask(SubIdx);
1360   } else {
1361     DefMI = Indexes->getInstructionFromIndex(VNI->def);
1362     bool Redef = false;
1363     V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef);
1364
1365     // If this is a read-modify-write instruction, there may be more valid
1366     // lanes than the ones written by this instruction.
1367     // This only covers partial redef operands. DefMI may have normal use
1368     // operands reading the register. They don't contribute valid lanes.
1369     //
1370     // This adds ssub1 to the set of valid lanes in %src:
1371     //
1372     //   %src:ssub1<def> = FOO
1373     //
1374     // This leaves only ssub1 valid, making any other lanes undef:
1375     //
1376     //   %src:ssub1<def,read-undef> = FOO %src:ssub2
1377     //
1378     // The <read-undef> flag on the def operand means that old lane values are
1379     // not important.
1380     if (Redef) {
1381       V.RedefVNI = LiveRangeQuery(LI, VNI->def).valueIn();
1382       assert(V.RedefVNI && "Instruction is reading nonexistent value");
1383       computeAssignment(V.RedefVNI->id, Other);
1384       V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;
1385     }
1386
1387     // An IMPLICIT_DEF writes undef values.
1388     if (DefMI->isImplicitDef())
1389       V.ValidLanes &= ~V.WriteLanes;
1390   }
1391
1392   // Find the value in Other that overlaps VNI->def, if any.
1393   LiveRangeQuery OtherLRQ(Other.LI, VNI->def);
1394
1395   // It is possible that both values are defined by the same instruction, or
1396   // the values are PHIs defined in the same block. When that happens, the two
1397   // values should be merged into one, but not into any preceding value.
1398   // The first value defined or visited gets CR_Keep, the other gets CR_Merge.
1399   if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) {
1400     assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ");
1401
1402     // One value stays, the other is merged. Keep the earlier one, or the first
1403     // one we see.
1404     if (OtherVNI->def < VNI->def)
1405       Other.computeAssignment(OtherVNI->id, *this);
1406     else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) {
1407       // This is an early-clobber def overlapping a live-in value in the other
1408       // register. Not mergeable.
1409       V.OtherVNI = OtherLRQ.valueIn();
1410       return CR_Impossible;
1411     }
1412     V.OtherVNI = OtherVNI;
1413     Val &OtherV = Other.Vals[OtherVNI->id];
1414     // Keep this value, check for conflicts when analyzing OtherVNI.
1415     if (!OtherV.isAnalyzed())
1416       return CR_Keep;
1417     // Both sides have been analyzed now.
1418     // Allow overlapping PHI values. Any real interference would show up in a
1419     // predecessor, the PHI itself can't introduce any conflicts.
1420     if (VNI->isPHIDef())
1421       return CR_Merge;
1422     if (V.ValidLanes & OtherV.ValidLanes)
1423       // Overlapping lanes can't be resolved.
1424       return CR_Impossible;
1425     else
1426       return CR_Merge;
1427   }
1428
1429   // No simultaneous def. Is Other live at the def?
1430   V.OtherVNI = OtherLRQ.valueIn();
1431   if (!V.OtherVNI)
1432     // No overlap, no conflict.
1433     return CR_Keep;
1434
1435   assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ");
1436
1437   // We have overlapping values, or possibly a kill of Other.
1438   // Recursively compute assignments up the dominator tree.
1439   Other.computeAssignment(V.OtherVNI->id, *this);
1440   const Val &OtherV = Other.Vals[V.OtherVNI->id];
1441
1442   // Allow overlapping PHI values. Any real interference would show up in a
1443   // predecessor, the PHI itself can't introduce any conflicts.
1444   if (VNI->isPHIDef())
1445     return CR_Replace;
1446
1447   // Check for simple erasable conflicts.
1448   if (DefMI->isImplicitDef())
1449     return CR_Erase;
1450
1451   // Include the non-conflict where DefMI is a coalescable copy that kills
1452   // OtherVNI. We still want the copy erased and value numbers merged.
1453   if (CP.isCoalescable(DefMI)) {
1454     // Some of the lanes copied from OtherVNI may be undef, making them undef
1455     // here too.
1456     V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;
1457     return CR_Erase;
1458   }
1459
1460   // This may not be a real conflict if DefMI simply kills Other and defines
1461   // VNI.
1462   if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def)
1463     return CR_Keep;
1464
1465   // Handle the case where VNI and OtherVNI can be proven to be identical:
1466   //
1467   //   %other = COPY %ext
1468   //   %this  = COPY %ext <-- Erase this copy
1469   //
1470   if (DefMI->isFullCopy() && !CP.isPartial() &&
1471       stripCopies(VNI) == stripCopies(V.OtherVNI))
1472     return CR_Erase;
1473
1474   // If the lanes written by this instruction were all undef in OtherVNI, it is
1475   // still safe to join the live ranges. This can't be done with a simple value
1476   // mapping, though - OtherVNI will map to multiple values:
1477   //
1478   //   1 %dst:ssub0 = FOO                <-- OtherVNI
1479   //   2 %src = BAR                      <-- VNI
1480   //   3 %dst:ssub1 = COPY %src<kill>    <-- Eliminate this copy.
1481   //   4 BAZ %dst<kill>
1482   //   5 QUUX %src<kill>
1483   //
1484   // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace
1485   // handles this complex value mapping.
1486   if ((V.WriteLanes & OtherV.ValidLanes) == 0)
1487     return CR_Replace;
1488
1489   // VNI is clobbering live lanes in OtherVNI, but there is still the
1490   // possibility that no instructions actually read the clobbered lanes.
1491   // If we're clobbering all the lanes in OtherVNI, at least one must be read.
1492   // Otherwise Other.LI wouldn't be live here.
1493   if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes) == 0)
1494     return CR_Impossible;
1495
1496   // We need to verify that no instructions are reading the clobbered lanes. To
1497   // save compile time, we'll only check that locally. Don't allow the tainted
1498   // value to escape the basic block.
1499   MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
1500   if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB))
1501     return CR_Impossible;
1502
1503   // There are still some things that could go wrong besides clobbered lanes
1504   // being read, for example OtherVNI may be only partially redefined in MBB,
1505   // and some clobbered lanes could escape the block. Save this analysis for
1506   // resolveConflicts() when all values have been mapped. We need to know
1507   // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute
1508   // that now - the recursive analyzeValue() calls must go upwards in the
1509   // dominator tree.
1510   return CR_Unresolved;
1511 }
1512
1513 /// Compute the value assignment for ValNo in LI.
1514 /// This may be called recursively by analyzeValue(), but never for a ValNo on
1515 /// the stack.
1516 void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) {
1517   Val &V = Vals[ValNo];
1518   if (V.isAnalyzed()) {
1519     // Recursion should always move up the dominator tree, so ValNo is not
1520     // supposed to reappear before it has been assigned.
1521     assert(Assignments[ValNo] != -1 && "Bad recursion?");
1522     return;
1523   }
1524   switch ((V.Resolution = analyzeValue(ValNo, Other))) {
1525   case CR_Erase:
1526   case CR_Merge:
1527     // Merge this ValNo into OtherVNI.
1528     assert(V.OtherVNI && "OtherVNI not assigned, can't merge.");
1529     assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion");
1530     Assignments[ValNo] = Other.Assignments[V.OtherVNI->id];
1531     DEBUG(dbgs() << "\t\tmerge " << PrintReg(LI.reg) << ':' << ValNo << '@'
1532                  << LI.getValNumInfo(ValNo)->def << " into "
1533                  << PrintReg(Other.LI.reg) << ':' << V.OtherVNI->id << '@'
1534                  << V.OtherVNI->def << " --> @"
1535                  << NewVNInfo[Assignments[ValNo]]->def << '\n');
1536     break;
1537   case CR_Replace:
1538   case CR_Unresolved:
1539     // The other value is going to be pruned if this join is successful.
1540     assert(V.OtherVNI && "OtherVNI not assigned, can't prune");
1541     Other.Vals[V.OtherVNI->id].Pruned = true;
1542     // Fall through.
1543   default:
1544     // This value number needs to go in the final joined live range.
1545     Assignments[ValNo] = NewVNInfo.size();
1546     NewVNInfo.push_back(LI.getValNumInfo(ValNo));
1547     break;
1548   }
1549 }
1550
1551 bool JoinVals::mapValues(JoinVals &Other) {
1552   for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
1553     computeAssignment(i, Other);
1554     if (Vals[i].Resolution == CR_Impossible) {
1555       DEBUG(dbgs() << "\t\tinterference at " << PrintReg(LI.reg) << ':' << i
1556                    << '@' << LI.getValNumInfo(i)->def << '\n');
1557       return false;
1558     }
1559   }
1560   return true;
1561 }
1562
1563 /// Assuming ValNo is going to clobber some valid lanes in Other.LI, compute
1564 /// the extent of the tainted lanes in the block.
1565 ///
1566 /// Multiple values in Other.LI can be affected since partial redefinitions can
1567 /// preserve previously tainted lanes.
1568 ///
1569 ///   1 %dst = VLOAD           <-- Define all lanes in %dst
1570 ///   2 %src = FOO             <-- ValNo to be joined with %dst:ssub0
1571 ///   3 %dst:ssub1 = BAR       <-- Partial redef doesn't clear taint in ssub0
1572 ///   4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read
1573 ///
1574 /// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes)
1575 /// entry to TaintedVals.
1576 ///
1577 /// Returns false if the tainted lanes extend beyond the basic block.
1578 bool JoinVals::
1579 taintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other,
1580             SmallVectorImpl<std::pair<SlotIndex, unsigned> > &TaintExtent) {
1581   VNInfo *VNI = LI.getValNumInfo(ValNo);
1582   MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
1583   SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB);
1584
1585   // Scan Other.LI from VNI.def to MBBEnd.
1586   LiveInterval::iterator OtherI = Other.LI.find(VNI->def);
1587   assert(OtherI != Other.LI.end() && "No conflict?");
1588   do {
1589     // OtherI is pointing to a tainted value. Abort the join if the tainted
1590     // lanes escape the block.
1591     SlotIndex End = OtherI->end;
1592     if (End >= MBBEnd) {
1593       DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.LI.reg) << ':'
1594                    << OtherI->valno->id << '@' << OtherI->start << '\n');
1595       return false;
1596     }
1597     DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.LI.reg) << ':'
1598                  << OtherI->valno->id << '@' << OtherI->start
1599                  << " to " << End << '\n');
1600     // A dead def is not a problem.
1601     if (End.isDead())
1602       break;
1603     TaintExtent.push_back(std::make_pair(End, TaintedLanes));
1604
1605     // Check for another def in the MBB.
1606     if (++OtherI == Other.LI.end() || OtherI->start >= MBBEnd)
1607       break;
1608
1609     // Lanes written by the new def are no longer tainted.
1610     const Val &OV = Other.Vals[OtherI->valno->id];
1611     TaintedLanes &= ~OV.WriteLanes;
1612     if (!OV.RedefVNI)
1613       break;
1614   } while (TaintedLanes);
1615   return true;
1616 }
1617
1618 /// Return true if MI uses any of the given Lanes from Reg.
1619 /// This does not include partial redefinitions of Reg.
1620 bool JoinVals::usesLanes(MachineInstr *MI, unsigned Reg, unsigned SubIdx,
1621                          unsigned Lanes) {
1622   if (MI->isDebugValue())
1623     return false;
1624   for (ConstMIOperands MO(MI); MO.isValid(); ++MO) {
1625     if (!MO->isReg() || MO->isDef() || MO->getReg() != Reg)
1626       continue;
1627     if (!MO->readsReg())
1628       continue;
1629     if (Lanes &
1630         TRI->getSubRegIndexLaneMask(compose(*TRI, SubIdx, MO->getSubReg())))
1631       return true;
1632   }
1633   return false;
1634 }
1635
1636 bool JoinVals::resolveConflicts(JoinVals &Other) {
1637   for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
1638     Val &V = Vals[i];
1639     assert (V.Resolution != CR_Impossible && "Unresolvable conflict");
1640     if (V.Resolution != CR_Unresolved)
1641       continue;
1642     DEBUG(dbgs() << "\t\tconflict at " << PrintReg(LI.reg) << ':' << i
1643                  << '@' << LI.getValNumInfo(i)->def << '\n');
1644     ++NumLaneConflicts;
1645     assert(V.OtherVNI && "Inconsistent conflict resolution.");
1646     VNInfo *VNI = LI.getValNumInfo(i);
1647     const Val &OtherV = Other.Vals[V.OtherVNI->id];
1648
1649     // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the
1650     // join, those lanes will be tainted with a wrong value. Get the extent of
1651     // the tainted lanes.
1652     unsigned TaintedLanes = V.WriteLanes & OtherV.ValidLanes;
1653     SmallVector<std::pair<SlotIndex, unsigned>, 8> TaintExtent;
1654     if (!taintExtent(i, TaintedLanes, Other, TaintExtent))
1655       // Tainted lanes would extend beyond the basic block.
1656       return false;
1657
1658     assert(!TaintExtent.empty() && "There should be at least one conflict.");
1659
1660     // Now look at the instructions from VNI->def to TaintExtent (inclusive).
1661     MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
1662     MachineBasicBlock::iterator MI = MBB->begin();
1663     if (!VNI->isPHIDef()) {
1664       MI = Indexes->getInstructionFromIndex(VNI->def);
1665       // No need to check the instruction defining VNI for reads.
1666       ++MI;
1667     }
1668     assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) &&
1669            "Interference ends on VNI->def. Should have been handled earlier");
1670     MachineInstr *LastMI =
1671       Indexes->getInstructionFromIndex(TaintExtent.front().first);
1672     assert(LastMI && "Range must end at a proper instruction");
1673     unsigned TaintNum = 0;
1674     for(;;) {
1675       assert(MI != MBB->end() && "Bad LastMI");
1676       if (usesLanes(MI, Other.LI.reg, Other.SubIdx, TaintedLanes)) {
1677         DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI);
1678         return false;
1679       }
1680       // LastMI is the last instruction to use the current value.
1681       if (&*MI == LastMI) {
1682         if (++TaintNum == TaintExtent.size())
1683           break;
1684         LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first);
1685         assert(LastMI && "Range must end at a proper instruction");
1686         TaintedLanes = TaintExtent[TaintNum].second;
1687       }
1688       ++MI;
1689     }
1690
1691     // The tainted lanes are unused.
1692     V.Resolution = CR_Replace;
1693     ++NumLaneResolves;
1694   }
1695   return true;
1696 }
1697
1698 // Determine if ValNo is a copy of a value number in LI or Other.LI that will
1699 // be pruned:
1700 //
1701 //   %dst = COPY %src
1702 //   %src = COPY %dst  <-- This value to be pruned.
1703 //   %dst = COPY %src  <-- This value is a copy of a pruned value.
1704 //
1705 bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) {
1706   Val &V = Vals[ValNo];
1707   if (V.Pruned || V.PrunedComputed)
1708     return V.Pruned;
1709
1710   if (V.Resolution != CR_Erase && V.Resolution != CR_Merge)
1711     return V.Pruned;
1712
1713   // Follow copies up the dominator tree and check if any intermediate value
1714   // has been pruned.
1715   V.PrunedComputed = true;
1716   V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this);
1717   return V.Pruned;
1718 }
1719
1720 void JoinVals::pruneValues(JoinVals &Other,
1721                            SmallVectorImpl<SlotIndex> &EndPoints) {
1722   for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
1723     SlotIndex Def = LI.getValNumInfo(i)->def;
1724     switch (Vals[i].Resolution) {
1725     case CR_Keep:
1726       break;
1727     case CR_Replace:
1728       // This value takes precedence over the value in Other.LI.
1729       LIS->pruneValue(&Other.LI, Def, &EndPoints);
1730       // Remove <def,read-undef> flags. This def is now a partial redef.
1731       if (!Def.isBlock()) {
1732         for (MIOperands MO(Indexes->getInstructionFromIndex(Def));
1733              MO.isValid(); ++MO)
1734           if (MO->isReg() && MO->isDef() && MO->getReg() == LI.reg)
1735             MO->setIsUndef(false);
1736         // This value will reach instructions below, but we need to make sure
1737         // the live range also reaches the instruction at Def.
1738         EndPoints.push_back(Def);
1739       }
1740       DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.LI.reg) << " at " << Def
1741                    << ": " << Other.LI << '\n');
1742       break;
1743     case CR_Erase:
1744     case CR_Merge:
1745       if (isPrunedValue(i, Other)) {
1746         // This value is ultimately a copy of a pruned value in LI or Other.LI.
1747         // We can no longer trust the value mapping computed by
1748         // computeAssignment(), the value that was originally copied could have
1749         // been replaced.
1750         LIS->pruneValue(&LI, Def, &EndPoints);
1751         DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(LI.reg) << " at "
1752                      << Def << ": " << LI << '\n');
1753       }
1754       break;
1755     case CR_Unresolved:
1756     case CR_Impossible:
1757       llvm_unreachable("Unresolved conflicts");
1758     }
1759   }
1760 }
1761
1762 void JoinVals::eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs,
1763                            SmallVectorImpl<unsigned> &ShrinkRegs) {
1764   for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
1765     if (Vals[i].Resolution != CR_Erase)
1766       continue;
1767     SlotIndex Def = LI.getValNumInfo(i)->def;
1768     MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
1769     assert(MI && "No instruction to erase");
1770     if (MI->isCopy()) {
1771       unsigned Reg = MI->getOperand(1).getReg();
1772       if (TargetRegisterInfo::isVirtualRegister(Reg) &&
1773           Reg != CP.getSrcReg() && Reg != CP.getDstReg())
1774         ShrinkRegs.push_back(Reg);
1775     }
1776     ErasedInstrs.insert(MI);
1777     DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI);
1778     LIS->RemoveMachineInstrFromMaps(MI);
1779     MI->eraseFromParent();
1780   }
1781 }
1782
1783 bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
1784   SmallVector<VNInfo*, 16> NewVNInfo;
1785   LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
1786   LiveInterval &LHS = LIS->getInterval(CP.getDstReg());
1787   JoinVals RHSVals(RHS, CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI);
1788   JoinVals LHSVals(LHS, CP.getDstIdx(), NewVNInfo, CP, LIS, TRI);
1789
1790   DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS
1791                << "\n\t\tLHS = " << PrintReg(CP.getDstReg()) << ' ' << LHS
1792                << '\n');
1793
1794   // First compute NewVNInfo and the simple value mappings.
1795   // Detect impossible conflicts early.
1796   if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))
1797     return false;
1798
1799   // Some conflicts can only be resolved after all values have been mapped.
1800   if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))
1801     return false;
1802
1803   // All clear, the live ranges can be merged.
1804
1805   // The merging algorithm in LiveInterval::join() can't handle conflicting
1806   // value mappings, so we need to remove any live ranges that overlap a
1807   // CR_Replace resolution. Collect a set of end points that can be used to
1808   // restore the live range after joining.
1809   SmallVector<SlotIndex, 8> EndPoints;
1810   LHSVals.pruneValues(RHSVals, EndPoints);
1811   RHSVals.pruneValues(LHSVals, EndPoints);
1812
1813   // Erase COPY and IMPLICIT_DEF instructions. This may cause some external
1814   // registers to require trimming.
1815   SmallVector<unsigned, 8> ShrinkRegs;
1816   LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
1817   RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
1818   while (!ShrinkRegs.empty())
1819     LIS->shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
1820
1821   // Join RHS into LHS.
1822   LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo,
1823            MRI);
1824
1825   // Kill flags are going to be wrong if the live ranges were overlapping.
1826   // Eventually, we should simply clear all kill flags when computing live
1827   // ranges. They are reinserted after register allocation.
1828   MRI->clearKillFlags(LHS.reg);
1829   MRI->clearKillFlags(RHS.reg);
1830
1831   if (EndPoints.empty())
1832     return true;
1833
1834   // Recompute the parts of the live range we had to remove because of
1835   // CR_Replace conflicts.
1836   DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size()
1837                << " points: " << LHS << '\n');
1838   LIS->extendToIndices(&LHS, EndPoints);
1839   return true;
1840 }
1841
1842 /// joinIntervals - Attempt to join these two intervals.  On failure, this
1843 /// returns false.
1844 bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
1845   return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
1846 }
1847
1848 namespace {
1849   // DepthMBBCompare - Comparison predicate that sort first based on the loop
1850   // depth of the basic block (the unsigned), and then on the MBB number.
1851   struct DepthMBBCompare {
1852     typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
1853     bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
1854       // Deeper loops first
1855       if (LHS.first != RHS.first)
1856         return LHS.first > RHS.first;
1857
1858       // Prefer blocks that are more connected in the CFG. This takes care of
1859       // the most difficult copies first while intervals are short.
1860       unsigned cl = LHS.second->pred_size() + LHS.second->succ_size();
1861       unsigned cr = RHS.second->pred_size() + RHS.second->succ_size();
1862       if (cl != cr)
1863         return cl > cr;
1864
1865       // As a last resort, sort by block number.
1866       return LHS.second->getNumber() < RHS.second->getNumber();
1867     }
1868   };
1869 }
1870
1871 // Try joining WorkList copies starting from index From.
1872 // Null out any successful joins.
1873 bool RegisterCoalescer::copyCoalesceWorkList(unsigned From) {
1874   assert(From <= WorkList.size() && "Out of range");
1875   bool Progress = false;
1876   for (unsigned i = From, e = WorkList.size(); i != e; ++i) {
1877     if (!WorkList[i])
1878       continue;
1879     // Skip instruction pointers that have already been erased, for example by
1880     // dead code elimination.
1881     if (ErasedInstrs.erase(WorkList[i])) {
1882       WorkList[i] = 0;
1883       continue;
1884     }
1885     bool Again = false;
1886     bool Success = joinCopy(WorkList[i], Again);
1887     Progress |= Success;
1888     if (Success || !Again)
1889       WorkList[i] = 0;
1890   }
1891   return Progress;
1892 }
1893
1894 void
1895 RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) {
1896   DEBUG(dbgs() << MBB->getName() << ":\n");
1897
1898   // Collect all copy-like instructions in MBB. Don't start coalescing anything
1899   // yet, it might invalidate the iterator.
1900   const unsigned PrevSize = WorkList.size();
1901   for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
1902        MII != E; ++MII)
1903     if (MII->isCopyLike())
1904       WorkList.push_back(MII);
1905
1906   // Try coalescing the collected copies immediately, and remove the nulls.
1907   // This prevents the WorkList from getting too large since most copies are
1908   // joinable on the first attempt.
1909   if (copyCoalesceWorkList(PrevSize))
1910     WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(),
1911                                (MachineInstr*)0), WorkList.end());
1912 }
1913
1914 void RegisterCoalescer::joinAllIntervals() {
1915   DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n");
1916   assert(WorkList.empty() && "Old data still around.");
1917
1918   if (Loops->empty()) {
1919     // If there are no loops in the function, join intervals in function order.
1920     for (MachineFunction::iterator I = MF->begin(), E = MF->end();
1921          I != E; ++I)
1922       copyCoalesceInMBB(I);
1923   } else {
1924     // Otherwise, join intervals in inner loops before other intervals.
1925     // Unfortunately we can't just iterate over loop hierarchy here because
1926     // there may be more MBB's than BB's.  Collect MBB's for sorting.
1927
1928     // Join intervals in the function prolog first. We want to join physical
1929     // registers with virtual registers before the intervals got too long.
1930     std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
1931     for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){
1932       MachineBasicBlock *MBB = I;
1933       MBBs.push_back(std::make_pair(Loops->getLoopDepth(MBB), I));
1934     }
1935
1936     // Sort by loop depth.
1937     std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
1938
1939     // Finally, join intervals in loop nest order.
1940     for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
1941       copyCoalesceInMBB(MBBs[i].second);
1942   }
1943
1944   // Joining intervals can allow other intervals to be joined.  Iteratively join
1945   // until we make no progress.
1946   while (copyCoalesceWorkList())
1947     /* empty */ ;
1948 }
1949
1950 void RegisterCoalescer::releaseMemory() {
1951   ErasedInstrs.clear();
1952   WorkList.clear();
1953   DeadDefs.clear();
1954   InflateRegs.clear();
1955 }
1956
1957 bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) {
1958   MF = &fn;
1959   MRI = &fn.getRegInfo();
1960   TM = &fn.getTarget();
1961   TRI = TM->getRegisterInfo();
1962   TII = TM->getInstrInfo();
1963   LIS = &getAnalysis<LiveIntervals>();
1964   LDV = &getAnalysis<LiveDebugVariables>();
1965   AA = &getAnalysis<AliasAnalysis>();
1966   Loops = &getAnalysis<MachineLoopInfo>();
1967
1968   DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"
1969                << "********** Function: " << MF->getName() << '\n');
1970
1971   if (VerifyCoalescing)
1972     MF->verify(this, "Before register coalescing");
1973
1974   RegClassInfo.runOnMachineFunction(fn);
1975
1976   // Join (coalesce) intervals if requested.
1977   if (EnableJoining)
1978     joinAllIntervals();
1979
1980   // After deleting a lot of copies, register classes may be less constrained.
1981   // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 ->
1982   // DPR inflation.
1983   array_pod_sort(InflateRegs.begin(), InflateRegs.end());
1984   InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()),
1985                     InflateRegs.end());
1986   DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n");
1987   for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) {
1988     unsigned Reg = InflateRegs[i];
1989     if (MRI->reg_nodbg_empty(Reg))
1990       continue;
1991     if (MRI->recomputeRegClass(Reg, *TM)) {
1992       DEBUG(dbgs() << PrintReg(Reg) << " inflated to "
1993                    << MRI->getRegClass(Reg)->getName() << '\n');
1994       ++NumInflated;
1995     }
1996   }
1997
1998   DEBUG(dump());
1999   DEBUG(LDV->dump());
2000   if (VerifyCoalescing)
2001     MF->verify(this, "After register coalescing");
2002   return true;
2003 }
2004
2005 /// print - Implement the dump method.
2006 void RegisterCoalescer::print(raw_ostream &O, const Module* m) const {
2007    LIS->print(O, m);
2008 }