llvm/lib/CodeGen/LiveRangeEdit.cpp

   1 //===-- LiveRangeEdit.cpp - Basic tools for editing a register live range -===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // The LiveRangeEdit class represents changes done to a virtual register when it
  10 // is spilled or split.
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/CodeGen/LiveRangeEdit.h"
  14 #include "llvm/ADT/Statistic.h"
  15 #include "llvm/CodeGen/CalcSpillWeights.h"
  16 #include "llvm/CodeGen/LiveIntervals.h"
  17 #include "llvm/CodeGen/MachineRegisterInfo.h"
  18 #include "llvm/CodeGen/TargetInstrInfo.h"
  19 #include "llvm/CodeGen/VirtRegMap.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/raw_ostream.h"
  22
  23 using namespace llvm;
  24
  25 #define DEBUG_TYPE "regalloc"
  26
  27 STATISTIC(NumDCEDeleted,        "Number of instructions deleted by DCE");
  28 STATISTIC(NumDCEFoldedLoads,    "Number of single use loads folded after DCE");
  29 STATISTIC(NumFracRanges,        "Number of live ranges fractured by DCE");
  30 STATISTIC(NumReMaterialization, "Number of instructions rematerialized");
  31
  32 void LiveRangeEdit::Delegate::anchor() { }
  33
  34 LiveInterval &LiveRangeEdit::createEmptyIntervalFrom(Register OldReg,
  35                                                      bool createSubRanges) {
  36   Register VReg = MRI.cloneVirtualRegister(OldReg);
  37   if (VRM)
  38     VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
  39
  40   LiveInterval &LI = LIS.createEmptyInterval(VReg);
  41   if (Parent && !Parent->isSpillable())
  42     LI.markNotSpillable();
  43   if (createSubRanges) {
  44     // Create empty subranges if the OldReg's interval has them. Do not create
  45     // the main range here---it will be constructed later after the subranges
  46     // have been finalized.
  47     LiveInterval &OldLI = LIS.getInterval(OldReg);
  48     VNInfo::Allocator &Alloc = LIS.getVNInfoAllocator();
  49     for (LiveInterval::SubRange &S : OldLI.subranges())
  50       LI.createSubRange(Alloc, S.LaneMask);
  51   }
  52   return LI;
  53 }
  54
  55 Register LiveRangeEdit::createFrom(Register OldReg) {
  56   Register VReg = MRI.cloneVirtualRegister(OldReg);
  57   if (VRM) {
  58     VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));
  59   }
  60   // FIXME: Getting the interval here actually computes it.
  61   // In theory, this may not be what we want, but in practice
  62   // the createEmptyIntervalFrom API is used when this is not
  63   // the case. Generally speaking we just want to annotate the
  64   // LiveInterval when it gets created but we cannot do that at
  65   // the moment.
  66   if (Parent && !Parent->isSpillable())
  67     LIS.getInterval(VReg).markNotSpillable();
  68   return VReg;
  69 }
  70
  71 bool LiveRangeEdit::checkRematerializable(VNInfo *VNI,
  72                                           const MachineInstr *DefMI) {
  73   assert(DefMI && "Missing instruction");
  74   ScannedRemattable = true;
  75   if (!TII.isTriviallyReMaterializable(*DefMI))
  76     return false;
  77   Remattable.insert(VNI);
  78   return true;
  79 }
  80
  81 void LiveRangeEdit::scanRemattable() {
  82   for (VNInfo *VNI : getParent().valnos) {
  83     if (VNI->isUnused())
  84       continue;
  85     Register Original = VRM->getOriginal(getReg());
  86     LiveInterval &OrigLI = LIS.getInterval(Original);
  87     VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
  88     if (!OrigVNI)
  89       continue;
  90     MachineInstr *DefMI = LIS.getInstructionFromIndex(OrigVNI->def);
  91     if (!DefMI)
  92       continue;
  93     checkRematerializable(OrigVNI, DefMI);
  94   }
  95   ScannedRemattable = true;
  96 }
  97
  98 bool LiveRangeEdit::anyRematerializable() {
  99   if (!ScannedRemattable)
 100     scanRemattable();
 101   return !Remattable.empty();
 102 }
 103
 104 /// allUsesAvailableAt - Return true if all registers used by OrigMI at
 105 /// OrigIdx are also available with the same value at UseIdx.
 106 bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
 107                                        SlotIndex OrigIdx,
 108                                        SlotIndex UseIdx) const {
 109   OrigIdx = OrigIdx.getRegSlot(true);
 110   UseIdx = std::max(UseIdx, UseIdx.getRegSlot(true));
 111   for (const MachineOperand &MO : OrigMI->operands()) {
 112     if (!MO.isReg() || !MO.getReg() || !MO.readsReg())
 113       continue;
 114
 115     // We can't remat physreg uses, unless it is a constant or target wants
 116     // to ignore this use.
 117     if (MO.getReg().isPhysical()) {
 118       if (MRI.isConstantPhysReg(MO.getReg()) || TII.isIgnorableUse(MO))
 119         continue;
 120       return false;
 121     }
 122
 123     LiveInterval &li = LIS.getInterval(MO.getReg());
 124     const VNInfo *OVNI = li.getVNInfoAt(OrigIdx);
 125     if (!OVNI)
 126       continue;
 127
 128     // Don't allow rematerialization immediately after the original def.
 129     // It would be incorrect if OrigMI redefines the register.
 130     // See PR14098.
 131     if (SlotIndex::isSameInstr(OrigIdx, UseIdx))
 132       return false;
 133
 134     if (OVNI != li.getVNInfoAt(UseIdx))
 135       return false;
 136
 137     // Check that subrange is live at UseIdx.
 138     if (li.hasSubRanges()) {
 139       const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
 140       unsigned SubReg = MO.getSubReg();
 141       LaneBitmask LM = SubReg ? TRI->getSubRegIndexLaneMask(SubReg)
 142                               : MRI.getMaxLaneMaskForVReg(MO.getReg());
 143       for (LiveInterval::SubRange &SR : li.subranges()) {
 144         if ((SR.LaneMask & LM).none())
 145           continue;
 146         if (!SR.liveAt(UseIdx))
 147           return false;
 148         // Early exit if all used lanes are checked. No need to continue.
 149         LM &= ~SR.LaneMask;
 150         if (LM.none())
 151           break;
 152       }
 153     }
 154   }
 155   return true;
 156 }
 157
 158 bool LiveRangeEdit::canRematerializeAt(Remat &RM, VNInfo *OrigVNI,
 159                                        SlotIndex UseIdx, bool cheapAsAMove) {
 160   assert(ScannedRemattable && "Call anyRematerializable first");
 161
 162   // Use scanRemattable info.
 163   if (!Remattable.count(OrigVNI))
 164     return false;
 165
 166   // No defining instruction provided.
 167   SlotIndex DefIdx;
 168   assert(RM.OrigMI && "No defining instruction for remattable value");
 169   DefIdx = LIS.getInstructionIndex(*RM.OrigMI);
 170
 171   // If only cheap remats were requested, bail out early.
 172   if (cheapAsAMove && !TII.isAsCheapAsAMove(*RM.OrigMI))
 173     return false;
 174
 175   // Verify that all used registers are available with the same values.
 176   if (!allUsesAvailableAt(RM.OrigMI, DefIdx, UseIdx))
 177     return false;
 178
 179   return true;
 180 }
 181
 182 SlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB,
 183                                          MachineBasicBlock::iterator MI,
 184                                          Register DestReg, const Remat &RM,
 185                                          const TargetRegisterInfo &tri,
 186                                          bool Late, unsigned SubIdx,
 187                                          MachineInstr *ReplaceIndexMI) {
 188   assert(RM.OrigMI && "Invalid remat");
 189   TII.reMaterialize(MBB, MI, DestReg, SubIdx, *RM.OrigMI, tri);
 190   // DestReg of the cloned instruction cannot be Dead. Set isDead of DestReg
 191   // to false anyway in case the isDead flag of RM.OrigMI's dest register
 192   // is true.
 193   (*--MI).clearRegisterDeads(DestReg);
 194   Rematted.insert(RM.ParentVNI);
 195   ++NumReMaterialization;
 196
 197   if (ReplaceIndexMI)
 198     return LIS.ReplaceMachineInstrInMaps(*ReplaceIndexMI, *MI).getRegSlot();
 199   return LIS.getSlotIndexes()->insertMachineInstrInMaps(*MI, Late).getRegSlot();
 200 }
 201
 202 void LiveRangeEdit::eraseVirtReg(Register Reg) {
 203   if (TheDelegate && TheDelegate->LRE_CanEraseVirtReg(Reg))
 204     LIS.removeInterval(Reg);
 205 }
 206
 207 bool LiveRangeEdit::foldAsLoad(LiveInterval *LI,
 208                                SmallVectorImpl<MachineInstr*> &Dead) {
 209   MachineInstr *DefMI = nullptr, *UseMI = nullptr;
 210
 211   // Check that there is a single def and a single use.
 212   for (MachineOperand &MO : MRI.reg_nodbg_operands(LI->reg())) {
 213     MachineInstr *MI = MO.getParent();
 214     if (MO.isDef()) {
 215       if (DefMI && DefMI != MI)
 216         return false;
 217       if (!MI->canFoldAsLoad())
 218         return false;
 219       DefMI = MI;
 220     } else if (!MO.isUndef()) {
 221       if (UseMI && UseMI != MI)
 222         return false;
 223       // FIXME: Targets don't know how to fold subreg uses.
 224       if (MO.getSubReg())
 225         return false;
 226       UseMI = MI;
 227     }
 228   }
 229   if (!DefMI || !UseMI)
 230     return false;
 231
 232   // Since we're moving the DefMI load, make sure we're not extending any live
 233   // ranges.
 234   if (!allUsesAvailableAt(DefMI, LIS.getInstructionIndex(*DefMI),
 235                           LIS.getInstructionIndex(*UseMI)))
 236     return false;
 237
 238   // We also need to make sure it is safe to move the load.
 239   // Assume there are stores between DefMI and UseMI.
 240   bool SawStore = true;
 241   if (!DefMI->isSafeToMove(nullptr, SawStore))
 242     return false;
 243
 244   LLVM_DEBUG(dbgs() << "Try to fold single def: " << *DefMI
 245                     << "       into single use: " << *UseMI);
 246
 247   SmallVector<unsigned, 8> Ops;
 248   if (UseMI->readsWritesVirtualRegister(LI->reg(), &Ops).second)
 249     return false;
 250
 251   MachineInstr *FoldMI = TII.foldMemoryOperand(*UseMI, Ops, *DefMI, &LIS);
 252   if (!FoldMI)
 253     return false;
 254   LLVM_DEBUG(dbgs() << "                folded: " << *FoldMI);
 255   LIS.ReplaceMachineInstrInMaps(*UseMI, *FoldMI);
 256   // Update the call site info.
 257   if (UseMI->shouldUpdateCallSiteInfo())
 258     UseMI->getMF()->moveCallSiteInfo(UseMI, FoldMI);
 259   UseMI->eraseFromParent();
 260   DefMI->addRegisterDead(LI->reg(), nullptr);
 261   Dead.push_back(DefMI);
 262   ++NumDCEFoldedLoads;
 263   return true;
 264 }
 265
 266 bool LiveRangeEdit::useIsKill(const LiveInterval &LI,
 267                               const MachineOperand &MO) const {
 268   const MachineInstr &MI = *MO.getParent();
 269   SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot();
 270   if (LI.Query(Idx).isKill())
 271     return true;
 272   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 273   unsigned SubReg = MO.getSubReg();
 274   LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubReg);
 275   for (const LiveInterval::SubRange &S : LI.subranges()) {
 276     if ((S.LaneMask & LaneMask).any() && S.Query(Idx).isKill())
 277       return true;
 278   }
 279   return false;
 280 }
 281
 282 /// Find all live intervals that need to shrink, then remove the instruction.
 283 void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink) {
 284   assert(MI->allDefsAreDead() && "Def isn't really dead");
 285   SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
 286
 287   // Never delete a bundled instruction.
 288   if (MI->isBundled()) {
 289     // TODO: Handle deleting copy bundles
 290     LLVM_DEBUG(dbgs() << "Won't delete dead bundled inst: " << Idx << '\t'
 291                       << *MI);
 292     return;
 293   }
 294
 295   // Never delete inline asm.
 296   if (MI->isInlineAsm()) {
 297     LLVM_DEBUG(dbgs() << "Won't delete: " << Idx << '\t' << *MI);
 298     return;
 299   }
 300
 301   // Use the same criteria as DeadMachineInstructionElim.
 302   bool SawStore = false;
 303   if (!MI->isSafeToMove(nullptr, SawStore)) {
 304     LLVM_DEBUG(dbgs() << "Can't delete: " << Idx << '\t' << *MI);
 305     return;
 306   }
 307
 308   LLVM_DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI);
 309
 310   // Collect virtual registers to be erased after MI is gone.
 311   SmallVector<Register, 8> RegsToErase;
 312   bool ReadsPhysRegs = false;
 313   bool isOrigDef = false;
 314   Register Dest;
 315   unsigned DestSubReg;
 316   // Only optimize rematerialize case when the instruction has one def, since
 317   // otherwise we could leave some dead defs in the code.  This case is
 318   // extremely rare.
 319   if (VRM && MI->getOperand(0).isReg() && MI->getOperand(0).isDef() &&
 320       MI->getDesc().getNumDefs() == 1) {
 321     Dest = MI->getOperand(0).getReg();
 322     DestSubReg = MI->getOperand(0).getSubReg();
 323     Register Original = VRM->getOriginal(Dest);
 324     LiveInterval &OrigLI = LIS.getInterval(Original);
 325     VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
 326     // The original live-range may have been shrunk to
 327     // an empty live-range. It happens when it is dead, but
 328     // we still keep it around to be able to rematerialize
 329     // other values that depend on it.
 330     if (OrigVNI)
 331       isOrigDef = SlotIndex::isSameInstr(OrigVNI->def, Idx);
 332   }
 333
 334   bool HasLiveVRegUses = false;
 335
 336   // Check for live intervals that may shrink
 337   for (const MachineOperand &MO : MI->operands()) {
 338     if (!MO.isReg())
 339       continue;
 340     Register Reg = MO.getReg();
 341     if (!Reg.isVirtual()) {
 342       // Check if MI reads any unreserved physregs.
 343       if (Reg && MO.readsReg() && !MRI.isReserved(Reg))
 344         ReadsPhysRegs = true;
 345       else if (MO.isDef())
 346         LIS.removePhysRegDefAt(Reg.asMCReg(), Idx);
 347       continue;
 348     }
 349     LiveInterval &LI = LIS.getInterval(Reg);
 350
 351     // Shrink read registers, unless it is likely to be expensive and
 352     // unlikely to change anything. We typically don't want to shrink the
 353     // PIC base register that has lots of uses everywhere.
 354     // Always shrink COPY uses that probably come from live range splitting.
 355     if ((MI->readsVirtualRegister(Reg) &&
 356          (MO.isDef() || TII.isCopyInstr(*MI))) ||
 357         (MO.readsReg() && (MRI.hasOneNonDBGUse(Reg) || useIsKill(LI, MO))))
 358       ToShrink.insert(&LI);
 359     else if (MO.readsReg())
 360       HasLiveVRegUses = true;
 361
 362     // Remove defined value.
 363     if (MO.isDef()) {
 364       if (TheDelegate && LI.getVNInfoAt(Idx) != nullptr)
 365         TheDelegate->LRE_WillShrinkVirtReg(LI.reg());
 366       LIS.removeVRegDefAt(LI, Idx);
 367       if (LI.empty())
 368         RegsToErase.push_back(Reg);
 369     }
 370   }
 371
 372   // Currently, we don't support DCE of physreg live ranges. If MI reads
 373   // any unreserved physregs, don't erase the instruction, but turn it into
 374   // a KILL instead. This way, the physreg live ranges don't end up
 375   // dangling.
 376   // FIXME: It would be better to have something like shrinkToUses() for
 377   // physregs. That could potentially enable more DCE and it would free up
 378   // the physreg. It would not happen often, though.
 379   if (ReadsPhysRegs) {
 380     MI->setDesc(TII.get(TargetOpcode::KILL));
 381     // Remove all operands that aren't physregs.
 382     for (unsigned i = MI->getNumOperands(); i; --i) {
 383       const MachineOperand &MO = MI->getOperand(i-1);
 384       if (MO.isReg() && MO.getReg().isPhysical())
 385         continue;
 386       MI->removeOperand(i-1);
 387     }
 388     LLVM_DEBUG(dbgs() << "Converted physregs to:\t" << *MI);
 389   } else {
 390     // If the dest of MI is an original reg and MI is reMaterializable,
 391     // don't delete the inst. Replace the dest with a new reg, and keep
 392     // the inst for remat of other siblings. The inst is saved in
 393     // LiveRangeEdit::DeadRemats and will be deleted after all the
 394     // allocations of the func are done.
 395     // However, immediately delete instructions which have unshrunk virtual
 396     // register uses. That may provoke RA to split an interval at the KILL
 397     // and later result in an invalid live segment end.
 398     if (isOrigDef && DeadRemats && !HasLiveVRegUses &&
 399         TII.isTriviallyReMaterializable(*MI)) {
 400       LiveInterval &NewLI = createEmptyIntervalFrom(Dest, false);
 401       VNInfo::Allocator &Alloc = LIS.getVNInfoAllocator();
 402       VNInfo *VNI = NewLI.getNextValue(Idx, Alloc);
 403       NewLI.addSegment(LiveInterval::Segment(Idx, Idx.getDeadSlot(), VNI));
 404
 405       if (DestSubReg) {
 406         const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
 407         auto *SR = NewLI.createSubRange(
 408             Alloc, TRI->getSubRegIndexLaneMask(DestSubReg));
 409         SR->addSegment(LiveInterval::Segment(Idx, Idx.getDeadSlot(),
 410                                              SR->getNextValue(Idx, Alloc)));
 411       }
 412
 413       pop_back();
 414       DeadRemats->insert(MI);
 415       const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
 416       MI->substituteRegister(Dest, NewLI.reg(), 0, TRI);
 417       MI->getOperand(0).setIsDead(true);
 418     } else {
 419       if (TheDelegate)
 420         TheDelegate->LRE_WillEraseInstruction(MI);
 421       LIS.RemoveMachineInstrFromMaps(*MI);
 422       MI->eraseFromParent();
 423       ++NumDCEDeleted;
 424     }
 425   }
 426
 427   // Erase any virtregs that are now empty and unused. There may be <undef>
 428   // uses around. Keep the empty live range in that case.
 429   for (Register Reg : RegsToErase) {
 430     if (LIS.hasInterval(Reg) && MRI.reg_nodbg_empty(Reg)) {
 431       ToShrink.remove(&LIS.getInterval(Reg));
 432       eraseVirtReg(Reg);
 433     }
 434   }
 435 }
 436
 437 void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr *> &Dead,
 438                                       ArrayRef<Register> RegsBeingSpilled) {
 439   ToShrinkSet ToShrink;
 440
 441   for (;;) {
 442     // Erase all dead defs.
 443     while (!Dead.empty())
 444       eliminateDeadDef(Dead.pop_back_val(), ToShrink);
 445
 446     if (ToShrink.empty())
 447       break;
 448
 449     // Shrink just one live interval. Then delete new dead defs.
 450     LiveInterval *LI = ToShrink.pop_back_val();
 451     if (foldAsLoad(LI, Dead))
 452       continue;
 453     Register VReg = LI->reg();
 454     if (TheDelegate)
 455       TheDelegate->LRE_WillShrinkVirtReg(VReg);
 456     if (!LIS.shrinkToUses(LI, &Dead))
 457       continue;
 458
 459     // Don't create new intervals for a register being spilled.
 460     // The new intervals would have to be spilled anyway so its not worth it.
 461     // Also they currently aren't spilled so creating them and not spilling
 462     // them results in incorrect code.
 463     if (llvm::is_contained(RegsBeingSpilled, VReg))
 464       continue;
 465
 466     // LI may have been separated, create new intervals.
 467     LI->RenumberValues();
 468     SmallVector<LiveInterval*, 8> SplitLIs;
 469     LIS.splitSeparateComponents(*LI, SplitLIs);
 470     if (!SplitLIs.empty())
 471       ++NumFracRanges;
 472
 473     Register Original = VRM ? VRM->getOriginal(VReg) : Register();
 474     for (const LiveInterval *SplitLI : SplitLIs) {
 475       // If LI is an original interval that hasn't been split yet, make the new
 476       // intervals their own originals instead of referring to LI. The original
 477       // interval must contain all the split products, and LI doesn't.
 478       if (Original != VReg && Original != 0)
 479         VRM->setIsSplitFromReg(SplitLI->reg(), Original);
 480       if (TheDelegate)
 481         TheDelegate->LRE_DidCloneVirtReg(SplitLI->reg(), VReg);
 482     }
 483   }
 484 }
 485
 486 // Keep track of new virtual registers created via
 487 // MachineRegisterInfo::createVirtualRegister.
 488 void
 489 LiveRangeEdit::MRI_NoteNewVirtualRegister(Register VReg) {
 490   if (VRM)
 491     VRM->grow();
 492
 493   NewRegs.push_back(VReg);
 494 }
 495
 496 void LiveRangeEdit::calculateRegClassAndHint(MachineFunction &MF,
 497                                              VirtRegAuxInfo &VRAI) {
 498   for (unsigned I = 0, Size = size(); I < Size; ++I) {
 499     LiveInterval &LI = LIS.getInterval(get(I));
 500     if (MRI.recomputeRegClass(LI.reg()))
 501       LLVM_DEBUG({
 502         const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
 503         dbgs() << "Inflated " << printReg(LI.reg()) << " to "
 504                << TRI->getRegClassName(MRI.getRegClass(LI.reg())) << '\n';
 505       });
 506     VRAI.calculateSpillWeightAndHint(LI);
 507   }
 508 }