brintos / llvm-project-archived public Read only

1//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface ------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the generic RegisterCoalescer interface which10// is used as the common interface used by all clients and11// implementations of register coalescing.12//13//===----------------------------------------------------------------------===//14 15#include "RegisterCoalescer.h"16#include "llvm/ADT/ArrayRef.h"17#include "llvm/ADT/BitVector.h"18#include "llvm/ADT/DenseSet.h"19#include "llvm/ADT/STLExtras.h"20#include "llvm/ADT/SmallPtrSet.h"21#include "llvm/ADT/SmallVector.h"22#include "llvm/ADT/Statistic.h"23#include "llvm/CodeGen/CalcSpillWeights.h"24#include "llvm/CodeGen/LiveInterval.h"25#include "llvm/CodeGen/LiveIntervals.h"26#include "llvm/CodeGen/LiveRangeEdit.h"27#include "llvm/CodeGen/MachineBasicBlock.h"28#include "llvm/CodeGen/MachineDominators.h"29#include "llvm/CodeGen/MachineFunction.h"30#include "llvm/CodeGen/MachineFunctionPass.h"31#include "llvm/CodeGen/MachineInstr.h"32#include "llvm/CodeGen/MachineInstrBuilder.h"33#include "llvm/CodeGen/MachineLoopInfo.h"34#include "llvm/CodeGen/MachineOperand.h"35#include "llvm/CodeGen/MachinePassManager.h"36#include "llvm/CodeGen/MachineRegisterInfo.h"37#include "llvm/CodeGen/Passes.h"38#include "llvm/CodeGen/RegisterClassInfo.h"39#include "llvm/CodeGen/RegisterCoalescerPass.h"40#include "llvm/CodeGen/SlotIndexes.h"41#include "llvm/CodeGen/TargetInstrInfo.h"42#include "llvm/CodeGen/TargetOpcodes.h"43#include "llvm/CodeGen/TargetRegisterInfo.h"44#include "llvm/CodeGen/TargetSubtargetInfo.h"45#include "llvm/IR/DebugLoc.h"46#include "llvm/InitializePasses.h"47#include "llvm/MC/LaneBitmask.h"48#include "llvm/MC/MCInstrDesc.h"49#include "llvm/MC/MCRegisterInfo.h"50#include "llvm/Pass.h"51#include "llvm/Support/CommandLine.h"52#include "llvm/Support/Compiler.h"53#include "llvm/Support/Debug.h"54#include "llvm/Support/ErrorHandling.h"55#include "llvm/Support/raw_ostream.h"56#include <algorithm>57#include <cassert>58#include <iterator>59#include <limits>60#include <tuple>61#include <utility>62#include <vector>63 64using namespace llvm;65 66#define DEBUG_TYPE "regalloc"67 68STATISTIC(numJoins, "Number of interval joins performed");69STATISTIC(numCrossRCs, "Number of cross class joins performed");70STATISTIC(numCommutes, "Number of instruction commuting performed");71STATISTIC(numExtends, "Number of copies extended");72STATISTIC(NumReMats, "Number of instructions re-materialized");73STATISTIC(NumInflated, "Number of register classes inflated");74STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested");75STATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved");76STATISTIC(NumShrinkToUses, "Number of shrinkToUses called");77 78static cl::opt<bool> EnableJoining("join-liveintervals",79                                   cl::desc("Coalesce copies (default=true)"),80                                   cl::init(true), cl::Hidden);81 82static cl::opt<bool> UseTerminalRule("terminal-rule",83                                     cl::desc("Apply the terminal rule"),84                                     cl::init(true), cl::Hidden);85 86/// Temporary flag to test critical edge unsplitting.87static cl::opt<bool> EnableJoinSplits(88    "join-splitedges",89    cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden);90 91/// Temporary flag to test global copy optimization.92static cl::opt<cl::boolOrDefault> EnableGlobalCopies(93    "join-globalcopies",94    cl::desc("Coalesce copies that span blocks (default=subtarget)"),95    cl::init(cl::BOU_UNSET), cl::Hidden);96 97static cl::opt<bool> VerifyCoalescing(98    "verify-coalescing",99    cl::desc("Verify machine instrs before and after register coalescing"),100    cl::Hidden);101 102static cl::opt<unsigned> LateRematUpdateThreshold(103    "late-remat-update-threshold", cl::Hidden,104    cl::desc("During rematerialization for a copy, if the def instruction has "105             "many other copy uses to be rematerialized, delay the multiple "106             "separate live interval update work and do them all at once after "107             "all those rematerialization are done. It will save a lot of "108             "repeated work. "),109    cl::init(100));110 111static cl::opt<unsigned> LargeIntervalSizeThreshold(112    "large-interval-size-threshold", cl::Hidden,113    cl::desc("If the valnos size of an interval is larger than the threshold, "114             "it is regarded as a large interval. "),115    cl::init(100));116 117static cl::opt<unsigned> LargeIntervalFreqThreshold(118    "large-interval-freq-threshold", cl::Hidden,119    cl::desc("For a large interval, if it is coalesced with other live "120             "intervals many times more than the threshold, stop its "121             "coalescing to control the compile time. "),122    cl::init(256));123 124namespace {125 126class JoinVals;127 128class RegisterCoalescer : private LiveRangeEdit::Delegate {129  MachineFunction *MF = nullptr;130  MachineRegisterInfo *MRI = nullptr;131  const TargetRegisterInfo *TRI = nullptr;132  const TargetInstrInfo *TII = nullptr;133  LiveIntervals *LIS = nullptr;134  SlotIndexes *SI = nullptr;135  const MachineLoopInfo *Loops = nullptr;136  RegisterClassInfo RegClassInfo;137 138  /// Position and VReg of a PHI instruction during coalescing.139  struct PHIValPos {140    SlotIndex SI;    ///< Slot where this PHI occurs.141    Register Reg;    ///< VReg the PHI occurs in.142    unsigned SubReg; ///< Qualifying subregister for Reg.143  };144 145  /// Map from debug instruction number to PHI position during coalescing.146  DenseMap<unsigned, PHIValPos> PHIValToPos;147  /// Index of, for each VReg, which debug instruction numbers and148  /// corresponding PHIs are sensitive to coalescing. Each VReg may have149  /// multiple PHI defs, at different positions.150  DenseMap<Register, SmallVector<unsigned, 2>> RegToPHIIdx;151 152  /// Debug variable location tracking -- for each VReg, maintain an153  /// ordered-by-slot-index set of DBG_VALUEs, to help quick154  /// identification of whether coalescing may change location validity.155  using DbgValueLoc = std::pair<SlotIndex, MachineInstr *>;156  DenseMap<Register, std::vector<DbgValueLoc>> DbgVRegToValues;157 158  /// A LaneMask to remember on which subregister live ranges we need to call159  /// shrinkToUses() later.160  LaneBitmask ShrinkMask;161 162  /// True if the main range of the currently coalesced intervals should be163  /// checked for smaller live intervals.164  bool ShrinkMainRange = false;165 166  /// True if the coalescer should aggressively coalesce global copies167  /// in favor of keeping local copies.168  bool JoinGlobalCopies = false;169 170  /// True if the coalescer should aggressively coalesce fall-thru171  /// blocks exclusively containing copies.172  bool JoinSplitEdges = false;173 174  /// Copy instructions yet to be coalesced.175  SmallVector<MachineInstr *, 8> WorkList;176  SmallVector<MachineInstr *, 8> LocalWorkList;177 178  /// Set of instruction pointers that have been erased, and179  /// that may be present in WorkList.180  SmallPtrSet<MachineInstr *, 8> ErasedInstrs;181 182  /// Dead instructions that are about to be deleted.183  SmallVector<MachineInstr *, 8> DeadDefs;184 185  /// Virtual registers to be considered for register class inflation.186  SmallVector<Register, 8> InflateRegs;187 188  /// The collection of live intervals which should have been updated189  /// immediately after rematerialiation but delayed until190  /// lateLiveIntervalUpdate is called.191  DenseSet<Register> ToBeUpdated;192 193  /// Record how many times the large live interval with many valnos194  /// has been tried to join with other live interval.195  DenseMap<Register, unsigned long> LargeLIVisitCounter;196 197  /// Recursively eliminate dead defs in DeadDefs.198  void eliminateDeadDefs(LiveRangeEdit *Edit = nullptr);199 200  /// LiveRangeEdit callback for eliminateDeadDefs().201  void LRE_WillEraseInstruction(MachineInstr *MI) override;202 203  /// Coalesce the LocalWorkList.204  void coalesceLocals();205 206  /// Join compatible live intervals207  void joinAllIntervals();208 209  /// Coalesce copies in the specified MBB, putting210  /// copies that cannot yet be coalesced into WorkList.211  void copyCoalesceInMBB(MachineBasicBlock *MBB);212 213  /// Tries to coalesce all copies in CurrList. Returns true if any progress214  /// was made.215  bool copyCoalesceWorkList(MutableArrayRef<MachineInstr *> CurrList);216 217  /// If one def has many copy like uses, and those copy uses are all218  /// rematerialized, the live interval update needed for those219  /// rematerializations will be delayed and done all at once instead220  /// of being done multiple times. This is to save compile cost because221  /// live interval update is costly.222  void lateLiveIntervalUpdate();223 224  /// Check if the incoming value defined by a COPY at \p SLRQ in the subrange225  /// has no value defined in the predecessors. If the incoming value is the226  /// same as defined by the copy itself, the value is considered undefined.227  bool copyValueUndefInPredecessors(LiveRange &S, const MachineBasicBlock *MBB,228                                    LiveQueryResult SLRQ);229 230  /// Set necessary undef flags on subregister uses after pruning out undef231  /// lane segments from the subrange.232  void setUndefOnPrunedSubRegUses(LiveInterval &LI, Register Reg,233                                  LaneBitmask PrunedLanes);234 235  /// Attempt to join intervals corresponding to SrcReg/DstReg, which are the236  /// src/dst of the copy instruction CopyMI.  This returns true if the copy237  /// was successfully coalesced away. If it is not currently possible to238  /// coalesce this interval, but it may be possible if other things get239  /// coalesced, then it returns true by reference in 'Again'.240  bool joinCopy(MachineInstr *CopyMI, bool &Again,241                SmallPtrSetImpl<MachineInstr *> &CurrentErasedInstrs);242 243  /// Attempt to join these two intervals.  On failure, this244  /// returns false.  The output "SrcInt" will not have been modified, so we245  /// can use this information below to update aliases.246  bool joinIntervals(CoalescerPair &CP);247 248  /// Attempt joining two virtual registers. Return true on success.249  bool joinVirtRegs(CoalescerPair &CP);250 251  /// If a live interval has many valnos and is coalesced with other252  /// live intervals many times, we regard such live interval as having253  /// high compile time cost.254  bool isHighCostLiveInterval(LiveInterval &LI);255 256  /// Attempt joining with a reserved physreg.257  bool joinReservedPhysReg(CoalescerPair &CP);258 259  /// Add the LiveRange @p ToMerge as a subregister liverange of @p LI.260  /// Subranges in @p LI which only partially interfere with the desired261  /// LaneMask are split as necessary. @p LaneMask are the lanes that262  /// @p ToMerge will occupy in the coalescer register. @p LI has its subrange263  /// lanemasks already adjusted to the coalesced register.264  void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,265                         LaneBitmask LaneMask, CoalescerPair &CP,266                         unsigned DstIdx);267 268  /// Join the liveranges of two subregisters. Joins @p RRange into269  /// @p LRange, @p RRange may be invalid afterwards.270  void joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,271                        LaneBitmask LaneMask, const CoalescerPair &CP);272 273  /// We found a non-trivially-coalescable copy. If the source value number is274  /// defined by a copy from the destination reg see if we can merge these two275  /// destination reg valno# into a single value number, eliminating a copy.276  /// This returns true if an interval was modified.277  bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI);278 279  /// Return true if there are definitions of IntB280  /// other than BValNo val# that can reach uses of AValno val# of IntA.281  bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB,282                            VNInfo *AValNo, VNInfo *BValNo);283 284  /// We found a non-trivially-coalescable copy.285  /// If the source value number is defined by a commutable instruction and286  /// its other operand is coalesced to the copy dest register, see if we287  /// can transform the copy into a noop by commuting the definition.288  /// This returns a pair of two flags:289  /// - the first element is true if an interval was modified,290  /// - the second element is true if the destination interval needs291  ///   to be shrunk after deleting the copy.292  std::pair<bool, bool> removeCopyByCommutingDef(const CoalescerPair &CP,293                                                 MachineInstr *CopyMI);294 295  /// We found a copy which can be moved to its less frequent predecessor.296  bool removePartialRedundancy(const CoalescerPair &CP, MachineInstr &CopyMI);297 298  /// If the source of a copy is defined by a CheapAsAMove computation,299  /// replace the copy by rematerialize the definition.300  bool reMaterializeDef(const CoalescerPair &CP, MachineInstr *CopyMI,301                        bool &IsDefCopy);302 303  /// Return true if a copy involving a physreg should be joined.304  bool canJoinPhys(const CoalescerPair &CP);305 306  /// Replace all defs and uses of SrcReg to DstReg and update the subregister307  /// number if it is not zero. If DstReg is a physical register and the308  /// existing subregister number of the def / use being updated is not zero,309  /// make sure to set it to the correct physical subregister.310  void updateRegDefsUses(Register SrcReg, Register DstReg, unsigned SubIdx);311 312  /// If the given machine operand reads only undefined lanes add an undef313  /// flag.314  /// This can happen when undef uses were previously concealed by a copy315  /// which we coalesced. Example:316  ///    %0:sub0<def,read-undef> = ...317  ///    %1 = COPY %0           <-- Coalescing COPY reveals undef318  ///       = use %1:sub1       <-- hidden undef use319  void addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,320                    MachineOperand &MO, unsigned SubRegIdx);321 322  /// Handle copies of undef values. If the undef value is an incoming323  /// PHI value, it will convert @p CopyMI to an IMPLICIT_DEF.324  /// Returns nullptr if @p CopyMI was not in any way eliminable. Otherwise,325  /// it returns @p CopyMI (which could be an IMPLICIT_DEF at this point).326  MachineInstr *eliminateUndefCopy(MachineInstr *CopyMI);327 328  /// Check whether or not we should apply the terminal rule on the329  /// destination (Dst) of \p Copy.330  /// When the terminal rule applies, Copy is not profitable to331  /// coalesce.332  /// Dst is terminal if it has exactly one affinity (Dst, Src) and333  /// at least one interference (Dst, Dst2). If Dst is terminal, the334  /// terminal rule consists in checking that at least one of335  /// interfering node, say Dst2, has an affinity of equal or greater336  /// weight with Src.337  /// In that case, Dst2 and Dst will not be able to be both coalesced338  /// with Src. Since Dst2 exposes more coalescing opportunities than339  /// Dst, we can drop \p Copy.340  bool applyTerminalRule(const MachineInstr &Copy) const;341 342  /// Wrapper method for \see LiveIntervals::shrinkToUses.343  /// This method does the proper fixing of the live-ranges when the afore344  /// mentioned method returns true.345  void shrinkToUses(LiveInterval *LI,346                    SmallVectorImpl<MachineInstr *> *Dead = nullptr) {347    NumShrinkToUses++;348    if (LIS->shrinkToUses(LI, Dead)) {349      /// Check whether or not \p LI is composed by multiple connected350      /// components and if that is the case, fix that.351      SmallVector<LiveInterval *, 8> SplitLIs;352      LIS->splitSeparateComponents(*LI, SplitLIs);353    }354  }355 356  /// Wrapper Method to do all the necessary work when an Instruction is357  /// deleted.358  /// Optimizations should use this to make sure that deleted instructions359  /// are always accounted for.360  void deleteInstr(MachineInstr *MI) {361    ErasedInstrs.insert(MI);362    LIS->RemoveMachineInstrFromMaps(*MI);363    MI->eraseFromParent();364  }365 366  /// Walk over function and initialize the DbgVRegToValues map.367  void buildVRegToDbgValueMap(MachineFunction &MF);368 369  /// Test whether, after merging, any DBG_VALUEs would refer to a370  /// different value number than before merging, and whether this can371  /// be resolved. If not, mark the DBG_VALUE as being undef.372  void checkMergingChangesDbgValues(CoalescerPair &CP, LiveRange &LHS,373                                    JoinVals &LHSVals, LiveRange &RHS,374                                    JoinVals &RHSVals);375 376  void checkMergingChangesDbgValuesImpl(Register Reg, LiveRange &OtherRange,377                                        LiveRange &RegRange, JoinVals &Vals2);378 379public:380  // For legacy pass only.381  RegisterCoalescer() = default;382  RegisterCoalescer &operator=(RegisterCoalescer &&Other) = default;383 384  RegisterCoalescer(LiveIntervals *LIS, SlotIndexes *SI,385                    const MachineLoopInfo *Loops)386      : LIS(LIS), SI(SI), Loops(Loops) {}387 388  bool run(MachineFunction &MF);389};390 391class RegisterCoalescerLegacy : public MachineFunctionPass {392public:393  static char ID; ///< Class identification, replacement for typeinfo394 395  RegisterCoalescerLegacy() : MachineFunctionPass(ID) {396    initializeRegisterCoalescerLegacyPass(*PassRegistry::getPassRegistry());397  }398 399  void getAnalysisUsage(AnalysisUsage &AU) const override;400 401  MachineFunctionProperties getClearedProperties() const override {402    return MachineFunctionProperties().setIsSSA();403  }404 405  /// This is the pass entry point.406  bool runOnMachineFunction(MachineFunction &) override;407};408 409} // end anonymous namespace410 411char RegisterCoalescerLegacy::ID = 0;412 413char &llvm::RegisterCoalescerID = RegisterCoalescerLegacy::ID;414 415INITIALIZE_PASS_BEGIN(RegisterCoalescerLegacy, "register-coalescer",416                      "Register Coalescer", false, false)417INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)418INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)419INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)420INITIALIZE_PASS_END(RegisterCoalescerLegacy, "register-coalescer",421                    "Register Coalescer", false, false)422 423[[nodiscard]] static bool isMoveInstr(const TargetRegisterInfo &tri,424                                      const MachineInstr *MI, Register &Src,425                                      Register &Dst, unsigned &SrcSub,426                                      unsigned &DstSub) {427  if (MI->isCopy()) {428    Dst = MI->getOperand(0).getReg();429    DstSub = MI->getOperand(0).getSubReg();430    Src = MI->getOperand(1).getReg();431    SrcSub = MI->getOperand(1).getSubReg();432  } else if (MI->isSubregToReg()) {433    Dst = MI->getOperand(0).getReg();434    DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(),435                                      MI->getOperand(3).getImm());436    Src = MI->getOperand(2).getReg();437    SrcSub = MI->getOperand(2).getSubReg();438  } else439    return false;440  return true;441}442 443/// Return true if this block should be vacated by the coalescer to eliminate444/// branches. The important cases to handle in the coalescer are critical edges445/// split during phi elimination which contain only copies. Simple blocks that446/// contain non-branches should also be vacated, but this can be handled by an447/// earlier pass similar to early if-conversion.448static bool isSplitEdge(const MachineBasicBlock *MBB) {449  if (MBB->pred_size() != 1 || MBB->succ_size() != 1)450    return false;451 452  for (const auto &MI : *MBB) {453    if (!MI.isCopyLike() && !MI.isUnconditionalBranch())454      return false;455  }456  return true;457}458 459bool CoalescerPair::setRegisters(const MachineInstr *MI) {460  SrcReg = DstReg = Register();461  SrcIdx = DstIdx = 0;462  NewRC = nullptr;463  Flipped = CrossClass = false;464 465  Register Src, Dst;466  unsigned SrcSub = 0, DstSub = 0;467  if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub))468    return false;469  Partial = SrcSub || DstSub;470 471  // If one register is a physreg, it must be Dst.472  if (Src.isPhysical()) {473    if (Dst.isPhysical())474      return false;475    std::swap(Src, Dst);476    std::swap(SrcSub, DstSub);477    Flipped = true;478  }479 480  const MachineRegisterInfo &MRI = MI->getMF()->getRegInfo();481  const TargetRegisterClass *SrcRC = MRI.getRegClass(Src);482 483  if (Dst.isPhysical()) {484    // Eliminate DstSub on a physreg.485    if (DstSub) {486      Dst = TRI.getSubReg(Dst, DstSub);487      if (!Dst)488        return false;489      DstSub = 0;490    }491 492    // Eliminate SrcSub by picking a corresponding Dst superregister.493    if (SrcSub) {494      Dst = TRI.getMatchingSuperReg(Dst, SrcSub, SrcRC);495      if (!Dst)496        return false;497    } else if (!SrcRC->contains(Dst)) {498      return false;499    }500  } else {501    // Both registers are virtual.502    const TargetRegisterClass *DstRC = MRI.getRegClass(Dst);503 504    // Both registers have subreg indices.505    if (SrcSub && DstSub) {506      // Copies between different sub-registers are never coalescable.507      if (Src == Dst && SrcSub != DstSub)508        return false;509 510      NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, SrcIdx,511                                         DstIdx);512      if (!NewRC)513        return false;514    } else if (DstSub) {515      // SrcReg will be merged with a sub-register of DstReg.516      SrcIdx = DstSub;517      NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub);518    } else if (SrcSub) {519      // DstReg will be merged with a sub-register of SrcReg.520      DstIdx = SrcSub;521      NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub);522    } else {523      // This is a straight copy without sub-registers.524      NewRC = TRI.getCommonSubClass(DstRC, SrcRC);525    }526 527    // The combined constraint may be impossible to satisfy.528    if (!NewRC)529      return false;530 531    // Prefer SrcReg to be a sub-register of DstReg.532    // FIXME: Coalescer should support subregs symmetrically.533    if (DstIdx && !SrcIdx) {534      std::swap(Src, Dst);535      std::swap(SrcIdx, DstIdx);536      Flipped = !Flipped;537    }538 539    CrossClass = NewRC != DstRC || NewRC != SrcRC;540  }541  // Check our invariants542  assert(Src.isVirtual() && "Src must be virtual");543  assert(!(Dst.isPhysical() && DstSub) && "Cannot have a physical SubIdx");544  SrcReg = Src;545  DstReg = Dst;546  return true;547}548 549bool CoalescerPair::flip() {550  if (DstReg.isPhysical())551    return false;552  std::swap(SrcReg, DstReg);553  std::swap(SrcIdx, DstIdx);554  Flipped = !Flipped;555  return true;556}557 558bool CoalescerPair::isCoalescable(const MachineInstr *MI) const {559  if (!MI)560    return false;561  Register Src, Dst;562  unsigned SrcSub = 0, DstSub = 0;563  if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub))564    return false;565 566  // Find the virtual register that is SrcReg.567  if (Dst == SrcReg) {568    std::swap(Src, Dst);569    std::swap(SrcSub, DstSub);570  } else if (Src != SrcReg) {571    return false;572  }573 574  // Now check that Dst matches DstReg.575  if (DstReg.isPhysical()) {576    if (!Dst.isPhysical())577      return false;578    assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state.");579    // DstSub could be set for a physreg from INSERT_SUBREG.580    if (DstSub)581      Dst = TRI.getSubReg(Dst, DstSub);582    // Full copy of Src.583    if (!SrcSub)584      return DstReg == Dst;585    // This is a partial register copy. Check that the parts match.586    return Register(TRI.getSubReg(DstReg, SrcSub)) == Dst;587  }588 589  // DstReg is virtual.590  if (DstReg != Dst)591    return false;592  // Registers match, do the subregisters line up?593  return TRI.composeSubRegIndices(SrcIdx, SrcSub) ==594         TRI.composeSubRegIndices(DstIdx, DstSub);595}596 597void RegisterCoalescerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {598  AU.setPreservesCFG();599  AU.addUsedIfAvailable<SlotIndexesWrapperPass>();600  AU.addRequired<LiveIntervalsWrapperPass>();601  AU.addPreserved<LiveIntervalsWrapperPass>();602  AU.addPreserved<SlotIndexesWrapperPass>();603  AU.addRequired<MachineLoopInfoWrapperPass>();604  AU.addPreserved<MachineLoopInfoWrapperPass>();605  AU.addPreservedID(MachineDominatorsID);606  MachineFunctionPass::getAnalysisUsage(AU);607}608 609void RegisterCoalescer::eliminateDeadDefs(LiveRangeEdit *Edit) {610  if (Edit) {611    Edit->eliminateDeadDefs(DeadDefs);612    return;613  }614  SmallVector<Register, 8> NewRegs;615  LiveRangeEdit(nullptr, NewRegs, *MF, *LIS, nullptr, this)616      .eliminateDeadDefs(DeadDefs);617}618 619void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) {620  // MI may be in WorkList. Make sure we don't visit it.621  ErasedInstrs.insert(MI);622}623 624bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,625                                             MachineInstr *CopyMI) {626  assert(!CP.isPartial() && "This doesn't work for partial copies.");627  assert(!CP.isPhys() && "This doesn't work for physreg copies.");628 629  LiveInterval &IntA =630      LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());631  LiveInterval &IntB =632      LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());633  SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();634 635  // We have a non-trivially-coalescable copy with IntA being the source and636  // IntB being the dest, thus this defines a value number in IntB.  If the637  // source value number (in IntA) is defined by a copy from B, see if we can638  // merge these two pieces of B into a single value number, eliminating a copy.639  // For example:640  //641  //  A3 = B0642  //    ...643  //  B1 = A3      <- this copy644  //645  // In this case, B0 can be extended to where the B1 copy lives, allowing the646  // B1 value number to be replaced with B0 (which simplifies the B647  // liveinterval).648 649  // BValNo is a value number in B that is defined by a copy from A.  'B1' in650  // the example above.651  LiveInterval::iterator BS = IntB.FindSegmentContaining(CopyIdx);652  if (BS == IntB.end())653    return false;654  VNInfo *BValNo = BS->valno;655 656  // Get the location that B is defined at.  Two options: either this value has657  // an unknown definition point or it is defined at CopyIdx.  If unknown, we658  // can't process it.659  if (BValNo->def != CopyIdx)660    return false;661 662  // AValNo is the value number in A that defines the copy, A3 in the example.663  SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true);664  LiveInterval::iterator AS = IntA.FindSegmentContaining(CopyUseIdx);665  // The live segment might not exist after fun with physreg coalescing.666  if (AS == IntA.end())667    return false;668  VNInfo *AValNo = AS->valno;669 670  // If AValNo is defined as a copy from IntB, we can potentially process this.671  // Get the instruction that defines this value number.672  MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def);673  // Don't allow any partial copies, even if isCoalescable() allows them.674  if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy())675    return false;676 677  // Get the Segment in IntB that this value number starts with.678  LiveInterval::iterator ValS =679      IntB.FindSegmentContaining(AValNo->def.getPrevSlot());680  if (ValS == IntB.end())681    return false;682 683  // Make sure that the end of the live segment is inside the same block as684  // CopyMI.685  MachineInstr *ValSEndInst =686      LIS->getInstructionFromIndex(ValS->end.getPrevSlot());687  if (!ValSEndInst || ValSEndInst->getParent() != CopyMI->getParent())688    return false;689 690  // Okay, we now know that ValS ends in the same block that the CopyMI691  // live-range starts.  If there are no intervening live segments between them692  // in IntB, we can merge them.693  if (ValS + 1 != BS)694    return false;695 696  LLVM_DEBUG(dbgs() << "Extending: " << printReg(IntB.reg(), TRI));697 698  SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;699  // We are about to delete CopyMI, so need to remove it as the 'instruction700  // that defines this value #'. Update the valnum with the new defining701  // instruction #.702  BValNo->def = FillerStart;703 704  // Okay, we can merge them.  We need to insert a new liverange:705  // [ValS.end, BS.begin) of either value number, then we merge the706  // two value numbers.707  IntB.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, BValNo));708 709  // Okay, merge "B1" into the same value number as "B0".710  if (BValNo != ValS->valno)711    IntB.MergeValueNumberInto(BValNo, ValS->valno);712 713  // Do the same for the subregister segments.714  for (LiveInterval::SubRange &S : IntB.subranges()) {715    // Check for SubRange Segments of the form [1234r,1234d:0) which can be716    // removed to prevent creating bogus SubRange Segments.717    LiveInterval::iterator SS = S.FindSegmentContaining(CopyIdx);718    if (SS != S.end() && SlotIndex::isSameInstr(SS->start, SS->end)) {719      S.removeSegment(*SS, true);720      continue;721    }722    // The subrange may have ended before FillerStart. If so, extend it.723    if (!S.getVNInfoAt(FillerStart)) {724      SlotIndex BBStart =725          LIS->getMBBStartIdx(LIS->getMBBFromIndex(FillerStart));726      S.extendInBlock(BBStart, FillerStart);727    }728    VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);729    S.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo));730    VNInfo *SubValSNo = S.getVNInfoAt(AValNo->def.getPrevSlot());731    if (SubBValNo != SubValSNo)732      S.MergeValueNumberInto(SubBValNo, SubValSNo);733  }734 735  LLVM_DEBUG(dbgs() << "   result = " << IntB << '\n');736 737  // If the source instruction was killing the source register before the738  // merge, unset the isKill marker given the live range has been extended.739  int UIdx =740      ValSEndInst->findRegisterUseOperandIdx(IntB.reg(), /*TRI=*/nullptr, true);741  if (UIdx != -1) {742    ValSEndInst->getOperand(UIdx).setIsKill(false);743  }744 745  // Rewrite the copy.746  CopyMI->substituteRegister(IntA.reg(), IntB.reg(), 0, *TRI);747  // If the copy instruction was killing the destination register or any748  // subrange before the merge trim the live range.749  bool RecomputeLiveRange = AS->end == CopyIdx;750  if (!RecomputeLiveRange) {751    for (LiveInterval::SubRange &S : IntA.subranges()) {752      LiveInterval::iterator SS = S.FindSegmentContaining(CopyUseIdx);753      if (SS != S.end() && SS->end == CopyIdx) {754        RecomputeLiveRange = true;755        break;756      }757    }758  }759  if (RecomputeLiveRange)760    shrinkToUses(&IntA);761 762  ++numExtends;763  return true;764}765 766bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA,767                                             LiveInterval &IntB, VNInfo *AValNo,768                                             VNInfo *BValNo) {769  // If AValNo has PHI kills, conservatively assume that IntB defs can reach770  // the PHI values.771  if (LIS->hasPHIKill(IntA, AValNo))772    return true;773 774  for (LiveRange::Segment &ASeg : IntA.segments) {775    if (ASeg.valno != AValNo)776      continue;777    LiveInterval::iterator BI = llvm::upper_bound(IntB, ASeg.start);778    if (BI != IntB.begin())779      --BI;780    for (; BI != IntB.end() && ASeg.end >= BI->start; ++BI) {781      if (BI->valno == BValNo)782        continue;783      if (BI->start <= ASeg.start && BI->end > ASeg.start)784        return true;785      if (BI->start > ASeg.start && BI->start < ASeg.end)786        return true;787    }788  }789  return false;790}791 792/// Copy segments with value number @p SrcValNo from liverange @p Src to live793/// range @Dst and use value number @p DstValNo there.794static std::pair<bool, bool> addSegmentsWithValNo(LiveRange &Dst,795                                                  VNInfo *DstValNo,796                                                  const LiveRange &Src,797                                                  const VNInfo *SrcValNo) {798  bool Changed = false;799  bool MergedWithDead = false;800  for (const LiveRange::Segment &S : Src.segments) {801    if (S.valno != SrcValNo)802      continue;803    // This is adding a segment from Src that ends in a copy that is about804    // to be removed. This segment is going to be merged with a pre-existing805    // segment in Dst. This works, except in cases when the corresponding806    // segment in Dst is dead. For example: adding [192r,208r:1) from Src807    // to [208r,208d:1) in Dst would create [192r,208d:1) in Dst.808    // Recognized such cases, so that the segments can be shrunk.809    LiveRange::Segment Added = LiveRange::Segment(S.start, S.end, DstValNo);810    LiveRange::Segment &Merged = *Dst.addSegment(Added);811    if (Merged.end.isDead())812      MergedWithDead = true;813    Changed = true;814  }815  return std::make_pair(Changed, MergedWithDead);816}817 818std::pair<bool, bool>819RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP,820                                            MachineInstr *CopyMI) {821  assert(!CP.isPhys());822 823  LiveInterval &IntA =824      LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());825  LiveInterval &IntB =826      LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());827 828  // We found a non-trivially-coalescable copy with IntA being the source and829  // IntB being the dest, thus this defines a value number in IntB.  If the830  // source value number (in IntA) is defined by a commutable instruction and831  // its other operand is coalesced to the copy dest register, see if we can832  // transform the copy into a noop by commuting the definition. For example,833  //834  //  A3 = op A2 killed B0835  //    ...836  //  B1 = A3      <- this copy837  //    ...838  //     = op A3   <- more uses839  //840  // ==>841  //842  //  B2 = op B0 killed A2843  //    ...844  //  B1 = B2      <- now an identity copy845  //    ...846  //     = op B2   <- more uses847 848  // BValNo is a value number in B that is defined by a copy from A. 'B1' in849  // the example above.850  SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();851  VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx);852  assert(BValNo != nullptr && BValNo->def == CopyIdx);853 854  // AValNo is the value number in A that defines the copy, A3 in the example.855  VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true));856  assert(AValNo && !AValNo->isUnused() && "COPY source not live");857  if (AValNo->isPHIDef())858    return {false, false};859  MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def);860  if (!DefMI)861    return {false, false};862  if (!DefMI->isCommutable())863    return {false, false};864  // If DefMI is a two-address instruction then commuting it will change the865  // destination register.866  int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg(), /*TRI=*/nullptr);867  assert(DefIdx != -1);868  unsigned UseOpIdx;869  if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx))870    return {false, false};871 872  // FIXME: The code below tries to commute 'UseOpIdx' operand with some other873  // commutable operand which is expressed by 'CommuteAnyOperandIndex'value874  // passed to the method. That _other_ operand is chosen by875  // the findCommutedOpIndices() method.876  //877  // That is obviously an area for improvement in case of instructions having878  // more than 2 operands. For example, if some instruction has 3 commutable879  // operands then all possible variants (i.e. op#1<->op#2, op#1<->op#3,880  // op#2<->op#3) of commute transformation should be considered/tried here.881  unsigned NewDstIdx = TargetInstrInfo::CommuteAnyOperandIndex;882  if (!TII->findCommutedOpIndices(*DefMI, UseOpIdx, NewDstIdx))883    return {false, false};884 885  MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);886  Register NewReg = NewDstMO.getReg();887  if (NewReg != IntB.reg() || !IntB.Query(AValNo->def).isKill())888    return {false, false};889 890  // Make sure there are no other definitions of IntB that would reach the891  // uses which the new definition can reach.892  if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo))893    return {false, false};894 895  // If some of the uses of IntA.reg is already coalesced away, return false.896  // It's not possible to determine whether it's safe to perform the coalescing.897  for (MachineOperand &MO : MRI->use_nodbg_operands(IntA.reg())) {898    MachineInstr *UseMI = MO.getParent();899    unsigned OpNo = &MO - &UseMI->getOperand(0);900    SlotIndex UseIdx = LIS->getInstructionIndex(*UseMI);901    LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx);902    if (US == IntA.end() || US->valno != AValNo)903      continue;904    // If this use is tied to a def, we can't rewrite the register.905    if (UseMI->isRegTiedToDefOperand(OpNo))906      return {false, false};907  }908 909  LLVM_DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t'910                    << *DefMI);911 912  // At this point we have decided that it is legal to do this913  // transformation.  Start by commuting the instruction.914  MachineBasicBlock *MBB = DefMI->getParent();915  MachineInstr *NewMI =916      TII->commuteInstruction(*DefMI, false, UseOpIdx, NewDstIdx);917  if (!NewMI)918    return {false, false};919  if (IntA.reg().isVirtual() && IntB.reg().isVirtual() &&920      !MRI->constrainRegClass(IntB.reg(), MRI->getRegClass(IntA.reg())))921    return {false, false};922  if (NewMI != DefMI) {923    LIS->ReplaceMachineInstrInMaps(*DefMI, *NewMI);924    MachineBasicBlock::iterator Pos = DefMI;925    MBB->insert(Pos, NewMI);926    MBB->erase(DefMI);927  }928 929  // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.930  // A = or A, B931  // ...932  // B = A933  // ...934  // C = killed A935  // ...936  //   = B937 938  // Update uses of IntA of the specific Val# with IntB.939  for (MachineOperand &UseMO :940       llvm::make_early_inc_range(MRI->use_operands(IntA.reg()))) {941    if (UseMO.isUndef())942      continue;943    MachineInstr *UseMI = UseMO.getParent();944    if (UseMI->isDebugInstr()) {945      // FIXME These don't have an instruction index.  Not clear we have enough946      // info to decide whether to do this replacement or not.  For now do it.947      UseMO.setReg(NewReg);948      continue;949    }950    SlotIndex UseIdx = LIS->getInstructionIndex(*UseMI).getRegSlot(true);951    LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx);952    assert(US != IntA.end() && "Use must be live");953    if (US->valno != AValNo)954      continue;955    // Kill flags are no longer accurate. They are recomputed after RA.956    UseMO.setIsKill(false);957    if (NewReg.isPhysical())958      UseMO.substPhysReg(NewReg, *TRI);959    else960      UseMO.setReg(NewReg);961    if (UseMI == CopyMI)962      continue;963    if (!UseMI->isCopy())964      continue;965    if (UseMI->getOperand(0).getReg() != IntB.reg() ||966        UseMI->getOperand(0).getSubReg())967      continue;968 969    // This copy will become a noop. If it's defining a new val#, merge it into970    // BValNo.971    SlotIndex DefIdx = UseIdx.getRegSlot();972    VNInfo *DVNI = IntB.getVNInfoAt(DefIdx);973    if (!DVNI)974      continue;975    LLVM_DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI);976    assert(DVNI->def == DefIdx);977    BValNo = IntB.MergeValueNumberInto(DVNI, BValNo);978    for (LiveInterval::SubRange &S : IntB.subranges()) {979      VNInfo *SubDVNI = S.getVNInfoAt(DefIdx);980      if (!SubDVNI)981        continue;982      VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);983      assert(SubBValNo->def == CopyIdx);984      S.MergeValueNumberInto(SubDVNI, SubBValNo);985    }986 987    deleteInstr(UseMI);988  }989 990  // Extend BValNo by merging in IntA live segments of AValNo. Val# definition991  // is updated.992  bool ShrinkB = false;993  BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();994  if (IntA.hasSubRanges() || IntB.hasSubRanges()) {995    if (!IntA.hasSubRanges()) {996      LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntA.reg());997      IntA.createSubRangeFrom(Allocator, Mask, IntA);998    } else if (!IntB.hasSubRanges()) {999      LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntB.reg());1000      IntB.createSubRangeFrom(Allocator, Mask, IntB);1001    }1002    SlotIndex AIdx = CopyIdx.getRegSlot(true);1003    LaneBitmask MaskA;1004    const SlotIndexes &Indexes = *LIS->getSlotIndexes();1005    for (LiveInterval::SubRange &SA : IntA.subranges()) {1006      VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);1007      // Even if we are dealing with a full copy, some lanes can1008      // still be undefined.1009      // E.g.,1010      // undef A.subLow = ...1011      // B = COPY A <== A.subHigh is undefined here and does1012      //                not have a value number.1013      if (!ASubValNo)1014        continue;1015      MaskA |= SA.LaneMask;1016 1017      IntB.refineSubRanges(1018          Allocator, SA.LaneMask,1019          [&Allocator, &SA, CopyIdx, ASubValNo,1020           &ShrinkB](LiveInterval::SubRange &SR) {1021            VNInfo *BSubValNo = SR.empty() ? SR.getNextValue(CopyIdx, Allocator)1022                                           : SR.getVNInfoAt(CopyIdx);1023            assert(BSubValNo != nullptr);1024            auto P = addSegmentsWithValNo(SR, BSubValNo, SA, ASubValNo);1025            ShrinkB |= P.second;1026            if (P.first)1027              BSubValNo->def = ASubValNo->def;1028          },1029          Indexes, *TRI);1030    }1031    // Go over all subranges of IntB that have not been covered by IntA,1032    // and delete the segments starting at CopyIdx. This can happen if1033    // IntA has undef lanes that are defined in IntB.1034    for (LiveInterval::SubRange &SB : IntB.subranges()) {1035      if ((SB.LaneMask & MaskA).any())1036        continue;1037      if (LiveRange::Segment *S = SB.getSegmentContaining(CopyIdx))1038        if (S->start.getBaseIndex() == CopyIdx.getBaseIndex())1039          SB.removeSegment(*S, true);1040    }1041  }1042 1043  BValNo->def = AValNo->def;1044  auto P = addSegmentsWithValNo(IntB, BValNo, IntA, AValNo);1045  ShrinkB |= P.second;1046  LLVM_DEBUG(dbgs() << "\t\textended: " << IntB << '\n');1047 1048  LIS->removeVRegDefAt(IntA, AValNo->def);1049 1050  LLVM_DEBUG(dbgs() << "\t\ttrimmed:  " << IntA << '\n');1051  ++numCommutes;1052  return {true, ShrinkB};1053}1054 1055/// For copy B = A in BB2, if A is defined by A = B in BB0 which is a1056/// predecessor of BB2, and if B is not redefined on the way from A = B1057/// in BB0 to B = A in BB2, B = A in BB2 is partially redundant if the1058/// execution goes through the path from BB0 to BB2. We may move B = A1059/// to the predecessor without such reversed copy.1060/// So we will transform the program from:1061///   BB0:1062///      A = B;    BB1:1063///       ...         ...1064///     /     \      /1065///             BB2:1066///               ...1067///               B = A;1068///1069/// to:1070///1071///   BB0:         BB1:1072///      A = B;        ...1073///       ...          B = A;1074///     /     \       /1075///             BB2:1076///               ...1077///1078/// A special case is when BB0 and BB2 are the same BB which is the only1079/// BB in a loop:1080///   BB1:1081///        ...1082///   BB0/BB2:  ----1083///        B = A;   |1084///        ...      |1085///        A = B;   |1086///          |-------1087///          |1088/// We may hoist B = A from BB0/BB2 to BB1.1089///1090/// The major preconditions for correctness to remove such partial1091/// redundancy include:1092/// 1. A in B = A in BB2 is defined by a PHI in BB2, and one operand of1093///    the PHI is defined by the reversed copy A = B in BB0.1094/// 2. No B is referenced from the start of BB2 to B = A.1095/// 3. No B is defined from A = B to the end of BB0.1096/// 4. BB1 has only one successor.1097///1098/// 2 and 4 implicitly ensure B is not live at the end of BB1.1099/// 4 guarantees BB2 is hotter than BB1, so we can only move a copy to a1100/// colder place, which not only prevent endless loop, but also make sure1101/// the movement of copy is beneficial.1102bool RegisterCoalescer::removePartialRedundancy(const CoalescerPair &CP,1103                                                MachineInstr &CopyMI) {1104  assert(!CP.isPhys());1105  if (!CopyMI.isFullCopy())1106    return false;1107 1108  MachineBasicBlock &MBB = *CopyMI.getParent();1109  // If this block is the target of an invoke/inlineasm_br, moving the copy into1110  // the predecessor is tricker, and we don't handle it.1111  if (MBB.isEHPad() || MBB.isInlineAsmBrIndirectTarget())1112    return false;1113 1114  if (MBB.pred_size() != 2)1115    return false;1116 1117  LiveInterval &IntA =1118      LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());1119  LiveInterval &IntB =1120      LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());1121 1122  // A is defined by PHI at the entry of MBB.1123  SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true);1124  VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx);1125  assert(AValNo && !AValNo->isUnused() && "COPY source not live");1126  if (!AValNo->isPHIDef())1127    return false;1128 1129  // No B is referenced before CopyMI in MBB.1130  if (IntB.overlaps(LIS->getMBBStartIdx(&MBB), CopyIdx))1131    return false;1132 1133  // MBB has two predecessors: one contains A = B so no copy will be inserted1134  // for it. The other one will have a copy moved from MBB.1135  bool FoundReverseCopy = false;1136  MachineBasicBlock *CopyLeftBB = nullptr;1137  for (MachineBasicBlock *Pred : MBB.predecessors()) {1138    VNInfo *PVal = IntA.getVNInfoBefore(LIS->getMBBEndIdx(Pred));1139    MachineInstr *DefMI = LIS->getInstructionFromIndex(PVal->def);1140    if (!DefMI || !DefMI->isFullCopy()) {1141      CopyLeftBB = Pred;1142      continue;1143    }1144    // Check DefMI is a reverse copy and it is in BB Pred.1145    if (DefMI->getOperand(0).getReg() != IntA.reg() ||1146        DefMI->getOperand(1).getReg() != IntB.reg() ||1147        DefMI->getParent() != Pred) {1148      CopyLeftBB = Pred;1149      continue;1150    }1151    // If there is any other def of B after DefMI and before the end of Pred,1152    // we need to keep the copy of B = A at the end of Pred if we remove1153    // B = A from MBB.1154    bool ValB_Changed = false;1155    for (auto *VNI : IntB.valnos) {1156      if (VNI->isUnused())1157        continue;1158      if (PVal->def < VNI->def && VNI->def < LIS->getMBBEndIdx(Pred)) {1159        ValB_Changed = true;1160        break;1161      }1162    }1163    if (ValB_Changed) {1164      CopyLeftBB = Pred;1165      continue;1166    }1167    FoundReverseCopy = true;1168  }1169 1170  // If no reverse copy is found in predecessors, nothing to do.1171  if (!FoundReverseCopy)1172    return false;1173 1174  // If CopyLeftBB is nullptr, it means every predecessor of MBB contains1175  // reverse copy, CopyMI can be removed trivially if only IntA/IntB is updated.1176  // If CopyLeftBB is not nullptr, move CopyMI from MBB to CopyLeftBB and1177  // update IntA/IntB.1178  //1179  // If CopyLeftBB is not nullptr, ensure CopyLeftBB has a single succ so1180  // MBB is hotter than CopyLeftBB.1181  if (CopyLeftBB && CopyLeftBB->succ_size() > 1)1182    return false;1183 1184  // Now (almost sure it's) ok to move copy.1185  if (CopyLeftBB) {1186    // Position in CopyLeftBB where we should insert new copy.1187    auto InsPos = CopyLeftBB->getFirstTerminator();1188 1189    // Make sure that B isn't referenced in the terminators (if any) at the end1190    // of the predecessor since we're about to insert a new definition of B1191    // before them.1192    if (InsPos != CopyLeftBB->end()) {1193      SlotIndex InsPosIdx = LIS->getInstructionIndex(*InsPos).getRegSlot(true);1194      if (IntB.overlaps(InsPosIdx, LIS->getMBBEndIdx(CopyLeftBB)))1195        return false;1196    }1197 1198    LLVM_DEBUG(dbgs() << "\tremovePartialRedundancy: Move the copy to "1199                      << printMBBReference(*CopyLeftBB) << '\t' << CopyMI);1200 1201    // Insert new copy to CopyLeftBB.1202    MachineInstr *NewCopyMI = BuildMI(*CopyLeftBB, InsPos, CopyMI.getDebugLoc(),1203                                      TII->get(TargetOpcode::COPY), IntB.reg())1204                                  .addReg(IntA.reg());1205    SlotIndex NewCopyIdx =1206        LIS->InsertMachineInstrInMaps(*NewCopyMI).getRegSlot();1207    IntB.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());1208    for (LiveInterval::SubRange &SR : IntB.subranges())1209      SR.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());1210 1211    // If the newly created Instruction has an address of an instruction that1212    // was deleted before (object recycled by the allocator) it needs to be1213    // removed from the deleted list.1214    ErasedInstrs.erase(NewCopyMI);1215  } else {1216    LLVM_DEBUG(dbgs() << "\tremovePartialRedundancy: Remove the copy from "1217                      << printMBBReference(MBB) << '\t' << CopyMI);1218  }1219 1220  const bool IsUndefCopy = CopyMI.getOperand(1).isUndef();1221 1222  // Remove CopyMI.1223  // Note: This is fine to remove the copy before updating the live-ranges.1224  // While updating the live-ranges, we only look at slot indices and1225  // never go back to the instruction.1226  // Mark instructions as deleted.1227  deleteInstr(&CopyMI);1228 1229  // Update the liveness.1230  SmallVector<SlotIndex, 8> EndPoints;1231  VNInfo *BValNo = IntB.Query(CopyIdx).valueOutOrDead();1232  LIS->pruneValue(*static_cast<LiveRange *>(&IntB), CopyIdx.getRegSlot(),1233                  &EndPoints);1234  BValNo->markUnused();1235 1236  if (IsUndefCopy) {1237    // We're introducing an undef phi def, and need to set undef on any users of1238    // the previously local def to avoid artifically extending the lifetime1239    // through the block.1240    for (MachineOperand &MO : MRI->use_nodbg_operands(IntB.reg())) {1241      const MachineInstr &MI = *MO.getParent();1242      SlotIndex UseIdx = LIS->getInstructionIndex(MI);1243      if (!IntB.liveAt(UseIdx))1244        MO.setIsUndef(true);1245    }1246  }1247 1248  // Extend IntB to the EndPoints of its original live interval.1249  LIS->extendToIndices(IntB, EndPoints);1250 1251  // Now, do the same for its subranges.1252  for (LiveInterval::SubRange &SR : IntB.subranges()) {1253    EndPoints.clear();1254    VNInfo *BValNo = SR.Query(CopyIdx).valueOutOrDead();1255    assert(BValNo && "All sublanes should be live");1256    LIS->pruneValue(SR, CopyIdx.getRegSlot(), &EndPoints);1257    BValNo->markUnused();1258    // We can have a situation where the result of the original copy is live,1259    // but is immediately dead in this subrange, e.g. [336r,336d:0). That makes1260    // the copy appear as an endpoint from pruneValue(), but we don't want it1261    // to because the copy has been removed.  We can go ahead and remove that1262    // endpoint; there is no other situation here that there could be a use at1263    // the same place as we know that the copy is a full copy.1264    for (unsigned I = 0; I != EndPoints.size();) {1265      if (SlotIndex::isSameInstr(EndPoints[I], CopyIdx)) {1266        EndPoints[I] = EndPoints.back();1267        EndPoints.pop_back();1268        continue;1269      }1270      ++I;1271    }1272    SmallVector<SlotIndex, 8> Undefs;1273    IntB.computeSubRangeUndefs(Undefs, SR.LaneMask, *MRI,1274                               *LIS->getSlotIndexes());1275    LIS->extendToIndices(SR, EndPoints, Undefs);1276  }1277  // If any dead defs were extended, truncate them.1278  shrinkToUses(&IntB);1279 1280  // Finally, update the live-range of IntA.1281  shrinkToUses(&IntA);1282  return true;1283}1284 1285/// Returns true if @p MI defines the full vreg @p Reg, as opposed to just1286/// defining a subregister.1287static bool definesFullReg(const MachineInstr &MI, Register Reg) {1288  assert(!Reg.isPhysical() && "This code cannot handle physreg aliasing");1289 1290  for (const MachineOperand &Op : MI.all_defs()) {1291    if (Op.getReg() != Reg)1292      continue;1293    // Return true if we define the full register or don't care about the value1294    // inside other subregisters.1295    if (Op.getSubReg() == 0 || Op.isUndef())1296      return true;1297  }1298  return false;1299}1300 1301bool RegisterCoalescer::reMaterializeDef(const CoalescerPair &CP,1302                                         MachineInstr *CopyMI,1303                                         bool &IsDefCopy) {1304  IsDefCopy = false;1305  Register SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg();1306  unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx();1307  Register DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();1308  unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx();1309  if (SrcReg.isPhysical())1310    return false;1311 1312  LiveInterval &SrcInt = LIS->getInterval(SrcReg);1313  SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);1314  VNInfo *ValNo = SrcInt.Query(CopyIdx).valueIn();1315  if (!ValNo)1316    return false;1317  if (ValNo->isPHIDef() || ValNo->isUnused())1318    return false;1319  MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def);1320  if (!DefMI)1321    return false;1322  if (DefMI->isCopyLike()) {1323    IsDefCopy = true;1324    return false;1325  }1326  if (!TII->isAsCheapAsAMove(*DefMI))1327    return false;1328 1329  if (!TII->isReMaterializable(*DefMI))1330    return false;1331 1332  if (!definesFullReg(*DefMI, SrcReg))1333    return false;1334  bool SawStore = false;1335  if (!DefMI->isSafeToMove(SawStore))1336    return false;1337  const MCInstrDesc &MCID = DefMI->getDesc();1338  if (MCID.getNumDefs() != 1)1339    return false;1340 1341  // If both SrcIdx and DstIdx are set, correct rematerialization would widen1342  // the register substantially (beyond both source and dest size). This is bad1343  // for performance since it can cascade through a function, introducing many1344  // extra spills and fills (e.g. ARM can easily end up copying QQQQPR registers1345  // around after a few subreg copies).1346  if (SrcIdx && DstIdx)1347    return false;1348 1349  // Only support subregister destinations when the def is read-undef.1350  MachineOperand &DstOperand = CopyMI->getOperand(0);1351  Register CopyDstReg = DstOperand.getReg();1352  if (DstOperand.getSubReg() && !DstOperand.isUndef())1353    return false;1354 1355  // In the physical register case, checking that the def is read-undef is not1356  // enough. We're widening the def and need to avoid clobbering other live1357  // values in the unused register pieces.1358  //1359  // TODO: Targets may support rewriting the rematerialized instruction to only1360  // touch relevant lanes, in which case we don't need any liveness check.1361  if (CopyDstReg.isPhysical() && CP.isPartial()) {1362    for (MCRegUnit Unit : TRI->regunits(DstReg)) {1363      // Ignore the register units we are writing anyway.1364      if (is_contained(TRI->regunits(CopyDstReg), Unit))1365        continue;1366 1367      // Check if the other lanes we are defining are live at the1368      // rematerialization point.1369      LiveRange &LR = LIS->getRegUnit(Unit);1370      if (LR.liveAt(CopyIdx))1371        return false;1372    }1373  }1374 1375  const unsigned DefSubIdx = DefMI->getOperand(0).getSubReg();1376  const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0);1377  if (!DefMI->isImplicitDef()) {1378    if (DstReg.isPhysical()) {1379      Register NewDstReg = DstReg;1380 1381      unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(), DefSubIdx);1382      if (NewDstIdx)1383        NewDstReg = TRI->getSubReg(DstReg, NewDstIdx);1384 1385      // Finally, make sure that the physical subregister that will be1386      // constructed later is permitted for the instruction.1387      if (!DefRC->contains(NewDstReg))1388        return false;1389    } else {1390      // Theoretically, some stack frame reference could exist. Just make sure1391      // it hasn't actually happened.1392      assert(DstReg.isVirtual() &&1393             "Only expect to deal with virtual or physical registers");1394    }1395  }1396 1397  if (!VirtRegAuxInfo::allUsesAvailableAt(DefMI, CopyIdx, *LIS, *MRI, *TII))1398    return false;1399 1400  DebugLoc DL = CopyMI->getDebugLoc();1401  MachineBasicBlock *MBB = CopyMI->getParent();1402  MachineBasicBlock::iterator MII =1403      std::next(MachineBasicBlock::iterator(CopyMI));1404  LiveRangeEdit::Remat RM(ValNo);1405  RM.OrigMI = DefMI;1406  SmallVector<Register, 8> NewRegs;1407  LiveRangeEdit Edit(&SrcInt, NewRegs, *MF, *LIS, nullptr, this);1408  Edit.rematerializeAt(*MBB, MII, DstReg, RM, *TRI, false, SrcIdx, CopyMI);1409  MachineInstr &NewMI = *std::prev(MII);1410  NewMI.setDebugLoc(DL);1411 1412  // In a situation like the following:1413  //     %0:subreg = instr              ; DefMI, subreg = DstIdx1414  //     %1        = copy %0:subreg ; CopyMI, SrcIdx = 01415  // instead of widening %1 to the register class of %0 simply do:1416  //     %1 = instr1417  const TargetRegisterClass *NewRC = CP.getNewRC();1418  if (DstIdx != 0) {1419    MachineOperand &DefMO = NewMI.getOperand(0);1420    if (DefMO.getSubReg() == DstIdx) {1421      assert(SrcIdx == 0 && CP.isFlipped() &&1422             "Shouldn't have SrcIdx+DstIdx at this point");1423      const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);1424      const TargetRegisterClass *CommonRC =1425          TRI->getCommonSubClass(DefRC, DstRC);1426      if (CommonRC != nullptr) {1427        NewRC = CommonRC;1428 1429        // Instruction might contain "undef %0:subreg" as use operand:1430        //   %0:subreg = instr op_1, ..., op_N, undef %0:subreg, op_N+2, ...1431        //1432        // Need to check all operands.1433        for (MachineOperand &MO : NewMI.operands()) {1434          if (MO.isReg() && MO.getReg() == DstReg && MO.getSubReg() == DstIdx) {1435            MO.setSubReg(0);1436          }1437        }1438 1439        DstIdx = 0;1440        DefMO.setIsUndef(false); // Only subregs can have def+undef.1441      }1442    }1443  }1444 1445  // CopyMI may have implicit operands, save them so that we can transfer them1446  // over to the newly materialized instruction after CopyMI is removed.1447  SmallVector<MachineOperand, 4> ImplicitOps;1448  ImplicitOps.reserve(CopyMI->getNumOperands() -1449                      CopyMI->getDesc().getNumOperands());1450  for (unsigned I = CopyMI->getDesc().getNumOperands(),1451                E = CopyMI->getNumOperands();1452       I != E; ++I) {1453    MachineOperand &MO = CopyMI->getOperand(I);1454    if (MO.isReg()) {1455      assert(MO.isImplicit() &&1456             "No explicit operands after implicit operands.");1457      assert((MO.getReg().isPhysical() ||1458              (MO.getSubReg() == 0 && MO.getReg() == DstOperand.getReg())) &&1459             "unexpected implicit virtual register def");1460      ImplicitOps.push_back(MO);1461    }1462  }1463 1464  CopyMI->eraseFromParent();1465  ErasedInstrs.insert(CopyMI);1466 1467  // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86).1468  // We need to remember these so we can add intervals once we insert1469  // NewMI into SlotIndexes.1470  //1471  // We also expect to have tied implicit-defs of super registers originating1472  // from SUBREG_TO_REG, such as:1473  // $edi = MOV32r0 implicit-def dead $eflags, implicit-def $rdi1474  // undef %0.sub_32bit = MOV32r0 implicit-def dead $eflags, implicit-def %01475  //1476  // The implicit-def of the super register may have been reduced to1477  // subregisters depending on the uses.1478  SmallVector<std::pair<unsigned, Register>, 4> NewMIImplDefs;1479  for (unsigned i = NewMI.getDesc().getNumOperands(),1480                e = NewMI.getNumOperands();1481       i != e; ++i) {1482    MachineOperand &MO = NewMI.getOperand(i);1483    if (MO.isReg() && MO.isDef()) {1484      assert(MO.isImplicit());1485      if (MO.getReg().isPhysical()) {1486        assert(MO.isImplicit() && MO.getReg().isPhysical() &&1487               (MO.isDead() ||1488                (DefSubIdx &&1489                 ((TRI->getSubReg(MO.getReg(), DefSubIdx) ==1490                   MCRegister((unsigned)NewMI.getOperand(0).getReg())) ||1491                  TRI->isSubRegisterEq(NewMI.getOperand(0).getReg(),1492                                       MO.getReg())))));1493        NewMIImplDefs.push_back({i, MO.getReg()});1494      } else {1495        assert(MO.getReg() == NewMI.getOperand(0).getReg());1496 1497        // We're only expecting another def of the main output, so the range1498        // should get updated with the regular output range.1499        //1500        // FIXME: The range updating below probably needs updating to look at1501        // the super register if subranges are tracked.1502        assert(!MRI->shouldTrackSubRegLiveness(DstReg) &&1503               "subrange update for implicit-def of super register may not be "1504               "properly handled");1505      }1506    }1507  }1508 1509  if (DstReg.isVirtual()) {1510    unsigned NewIdx = NewMI.getOperand(0).getSubReg();1511 1512    if (DefRC != nullptr) {1513      if (NewIdx)1514        NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);1515      else1516        NewRC = TRI->getCommonSubClass(NewRC, DefRC);1517      assert(NewRC && "subreg chosen for remat incompatible with instruction");1518    }1519 1520    // Remap subranges to new lanemask and change register class.1521    LiveInterval &DstInt = LIS->getInterval(DstReg);1522    for (LiveInterval::SubRange &SR : DstInt.subranges()) {1523      SR.LaneMask = TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask);1524    }1525    MRI->setRegClass(DstReg, NewRC);1526 1527    // Update machine operands and add flags.1528    updateRegDefsUses(DstReg, DstReg, DstIdx);1529    NewMI.getOperand(0).setSubReg(NewIdx);1530    // updateRegDefUses can add an "undef" flag to the definition, since1531    // it will replace DstReg with DstReg.DstIdx. If NewIdx is 0, make1532    // sure that "undef" is not set.1533    if (NewIdx == 0)1534      NewMI.getOperand(0).setIsUndef(false);1535 1536    // In a situation like the following:1537    //1538    //    undef %2.subreg:reg = INST %1:reg    ; DefMI (rematerializable),1539    //                                         ; Defines only some of lanes,1540    //                                         ; so DefSubIdx = NewIdx = subreg1541    //    %3:reg = COPY %2                     ; Copy full reg1542    //    .... = SOMEINSTR %3:reg              ; Use full reg1543    //1544    // there are no subranges for %3 so after rematerialization we need1545    // to explicitly create them. Undefined subranges are removed later on.1546    if (NewIdx && !DstInt.hasSubRanges() &&1547        MRI->shouldTrackSubRegLiveness(DstReg)) {1548      LaneBitmask FullMask = MRI->getMaxLaneMaskForVReg(DstReg);1549      LaneBitmask UsedLanes = TRI->getSubRegIndexLaneMask(NewIdx);1550      LaneBitmask UnusedLanes = FullMask & ~UsedLanes;1551      VNInfo::Allocator &Alloc = LIS->getVNInfoAllocator();1552      DstInt.createSubRangeFrom(Alloc, UsedLanes, DstInt);1553      DstInt.createSubRangeFrom(Alloc, UnusedLanes, DstInt);1554    }1555 1556    // Add dead subregister definitions if we are defining the whole register1557    // but only part of it is live.1558    // This could happen if the rematerialization instruction is rematerializing1559    // more than actually is used in the register.1560    // An example would be:1561    // %1 = LOAD CONSTANTS 5, 8 ; Loading both 5 and 8 in different subregs1562    // ; Copying only part of the register here, but the rest is undef.1563    // %2:sub_16bit<def, read-undef> = COPY %1:sub_16bit1564    // ==>1565    // ; Materialize all the constants but only using one1566    // %2 = LOAD_CONSTANTS 5, 81567    //1568    // at this point for the part that wasn't defined before we could have1569    // subranges missing the definition.1570    if (NewIdx == 0 && DstInt.hasSubRanges()) {1571      SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);1572      SlotIndex DefIndex =1573          CurrIdx.getRegSlot(NewMI.getOperand(0).isEarlyClobber());1574      LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(DstReg);1575      VNInfo::Allocator &Alloc = LIS->getVNInfoAllocator();1576      for (LiveInterval::SubRange &SR : DstInt.subranges()) {1577        if (!SR.liveAt(DefIndex))1578          SR.createDeadDef(DefIndex, Alloc);1579        MaxMask &= ~SR.LaneMask;1580      }1581      if (MaxMask.any()) {1582        LiveInterval::SubRange *SR = DstInt.createSubRange(Alloc, MaxMask);1583        SR->createDeadDef(DefIndex, Alloc);1584      }1585    }1586 1587    // Make sure that the subrange for resultant undef is removed1588    // For example:1589    //   %1:sub1<def,read-undef> = LOAD CONSTANT 11590    //   %2 = COPY %11591    // ==>1592    //   %2:sub1<def, read-undef> = LOAD CONSTANT 11593    //     ; Correct but need to remove the subrange for %2:sub01594    //     ; as it is now undef1595    if (NewIdx != 0 && DstInt.hasSubRanges()) {1596      // The affected subregister segments can be removed.1597      SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);1598      LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(NewIdx);1599      bool UpdatedSubRanges = false;1600      SlotIndex DefIndex =1601          CurrIdx.getRegSlot(NewMI.getOperand(0).isEarlyClobber());1602      VNInfo::Allocator &Alloc = LIS->getVNInfoAllocator();1603 1604      // Refine the subranges that are now defined by the remat.1605      // This will split existing subranges if necessary.1606      DstInt.refineSubRanges(1607          Alloc, DstMask,1608          [&DefIndex, &Alloc](LiveInterval::SubRange &SR) {1609            // We know that this lane is defined by this instruction,1610            // but at this point it might not be live because it was not defined1611            // by the original instruction. This happens when the1612            // rematerialization widens the defined register. Assign that lane a1613            // dead def so that the interferences are properly modeled.1614            if (!SR.liveAt(DefIndex))1615              SR.createDeadDef(DefIndex, Alloc);1616          },1617          *LIS->getSlotIndexes(), *TRI);1618 1619      for (LiveInterval::SubRange &SR : DstInt.subranges()) {1620        if ((SR.LaneMask & DstMask).none()) {1621          LLVM_DEBUG(dbgs()1622                     << "Removing undefined SubRange "1623                     << PrintLaneMask(SR.LaneMask) << " : " << SR << "\n");1624 1625          if (VNInfo *RmValNo = SR.getVNInfoAt(CurrIdx.getRegSlot())) {1626            // VNI is in ValNo - remove any segments in this SubRange that have1627            // this ValNo1628            SR.removeValNo(RmValNo);1629          }1630 1631          // We may not have a defined value at this point, but still need to1632          // clear out any empty subranges tentatively created by1633          // updateRegDefUses. The original subrange def may have only undefed1634          // some lanes.1635          UpdatedSubRanges = true;1636        }1637      }1638      if (UpdatedSubRanges)1639        DstInt.removeEmptySubRanges();1640    }1641  } else if (NewMI.getOperand(0).getReg() != CopyDstReg) {1642    // The New instruction may be defining a sub-register of what's actually1643    // been asked for. If so it must implicitly define the whole thing.1644    assert(DstReg.isPhysical() &&1645           "Only expect virtual or physical registers in remat");1646 1647    // When we're rematerializing into a not-quite-right register we already add1648    // the real definition as an implicit-def, but we should also be marking the1649    // "official" register as dead, since nothing else is going to use it as a1650    // result of this remat. Not doing this can affect pressure tracking.1651    NewMI.getOperand(0).setIsDead(true);1652 1653    bool HasDefMatchingCopy = false;1654    for (auto [OpIndex, Reg] : NewMIImplDefs) {1655      if (Reg != DstReg)1656        continue;1657      // Also, if CopyDstReg is a sub-register of DstReg (and it is defined), we1658      // must mark DstReg as dead since it is not going to used as a result of1659      // this remat.1660      if (DstReg != CopyDstReg)1661        NewMI.getOperand(OpIndex).setIsDead(true);1662      else1663        HasDefMatchingCopy = true;1664    }1665 1666    // If NewMI does not already have an implicit-def CopyDstReg add one now.1667    if (!HasDefMatchingCopy)1668      NewMI.addOperand(MachineOperand::CreateReg(1669          CopyDstReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/));1670 1671    // Record small dead def live-ranges for all the subregisters1672    // of the destination register.1673    // Otherwise, variables that live through may miss some1674    // interferences, thus creating invalid allocation.1675    // E.g., i386 code:1676    // %1 = somedef ; %1 GR81677    // %2 = remat ; %2 GR321678    // CL = COPY %2.sub_8bit1679    // = somedef %1 ; %1 GR81680    // =>1681    // %1 = somedef ; %1 GR81682    // dead ECX = remat ; implicit-def CL1683    // = somedef %1 ; %1 GR81684    // %1 will see the interferences with CL but not with CH since1685    // no live-ranges would have been created for ECX.1686    // Fix that!1687    SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);1688    for (MCRegUnit Unit : TRI->regunits(NewMI.getOperand(0).getReg()))1689      if (LiveRange *LR = LIS->getCachedRegUnit(Unit))1690        LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());1691  }1692 1693  NewMI.setRegisterDefReadUndef(NewMI.getOperand(0).getReg());1694 1695  // Transfer over implicit operands to the rematerialized instruction.1696  for (MachineOperand &MO : ImplicitOps)1697    NewMI.addOperand(MO);1698 1699  SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);1700  for (Register Reg : make_second_range(NewMIImplDefs)) {1701    for (MCRegUnit Unit : TRI->regunits(Reg.asMCReg()))1702      if (LiveRange *LR = LIS->getCachedRegUnit(Unit))1703        LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());1704  }1705 1706  LLVM_DEBUG(dbgs() << "Remat: " << NewMI);1707  ++NumReMats;1708 1709  // If the virtual SrcReg is completely eliminated, update all DBG_VALUEs1710  // to describe DstReg instead.1711  if (MRI->use_nodbg_empty(SrcReg)) {1712    for (MachineOperand &UseMO :1713         llvm::make_early_inc_range(MRI->use_operands(SrcReg))) {1714      MachineInstr *UseMI = UseMO.getParent();1715      if (UseMI->isDebugInstr()) {1716        if (DstReg.isPhysical())1717          UseMO.substPhysReg(DstReg, *TRI);1718        else1719          UseMO.setReg(DstReg);1720        // Move the debug value directly after the def of the rematerialized1721        // value in DstReg.1722        MBB->splice(std::next(NewMI.getIterator()), UseMI->getParent(), UseMI);1723        LLVM_DEBUG(dbgs() << "\t\tupdated: " << *UseMI);1724      }1725    }1726  }1727 1728  if (ToBeUpdated.count(SrcReg))1729    return true;1730 1731  unsigned NumCopyUses = 0;1732  for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) {1733    if (UseMO.getParent()->isCopyLike())1734      NumCopyUses++;1735  }1736  if (NumCopyUses < LateRematUpdateThreshold) {1737    // The source interval can become smaller because we removed a use.1738    shrinkToUses(&SrcInt, &DeadDefs);1739    if (!DeadDefs.empty())1740      eliminateDeadDefs(&Edit);1741  } else {1742    ToBeUpdated.insert(SrcReg);1743  }1744  return true;1745}1746 1747MachineInstr *RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI) {1748  // ProcessImplicitDefs may leave some copies of <undef> values, it only1749  // removes local variables. When we have a copy like:1750  //1751  //   %1 = COPY undef %21752  //1753  // We delete the copy and remove the corresponding value number from %1.1754  // Any uses of that value number are marked as <undef>.1755 1756  // Note that we do not query CoalescerPair here but redo isMoveInstr as the1757  // CoalescerPair may have a new register class with adjusted subreg indices1758  // at this point.1759  Register SrcReg, DstReg;1760  unsigned SrcSubIdx = 0, DstSubIdx = 0;1761  if (!isMoveInstr(*TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))1762    return nullptr;1763 1764  SlotIndex Idx = LIS->getInstructionIndex(*CopyMI);1765  const LiveInterval &SrcLI = LIS->getInterval(SrcReg);1766  // CopyMI is undef iff SrcReg is not live before the instruction.1767  if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) {1768    LaneBitmask SrcMask = TRI->getSubRegIndexLaneMask(SrcSubIdx);1769    for (const LiveInterval::SubRange &SR : SrcLI.subranges()) {1770      if ((SR.LaneMask & SrcMask).none())1771        continue;1772      if (SR.liveAt(Idx))1773        return nullptr;1774    }1775  } else if (SrcLI.liveAt(Idx))1776    return nullptr;1777 1778  // If the undef copy defines a live-out value (i.e. an input to a PHI def),1779  // then replace it with an IMPLICIT_DEF.1780  LiveInterval &DstLI = LIS->getInterval(DstReg);1781  SlotIndex RegIndex = Idx.getRegSlot();1782  LiveRange::Segment *Seg = DstLI.getSegmentContaining(RegIndex);1783  assert(Seg != nullptr && "No segment for defining instruction");1784  VNInfo *V = DstLI.getVNInfoAt(Seg->end);1785 1786  // The source interval may also have been on an undef use, in which case the1787  // copy introduced a live value.1788  if (((V && V->isPHIDef()) || (!V && !DstLI.liveAt(Idx)))) {1789    for (unsigned i = CopyMI->getNumOperands(); i != 0; --i) {1790      MachineOperand &MO = CopyMI->getOperand(i - 1);1791      if (MO.isReg()) {1792        if (MO.isUse())1793          CopyMI->removeOperand(i - 1);1794      } else {1795        assert(MO.isImm() &&1796               CopyMI->getOpcode() == TargetOpcode::SUBREG_TO_REG);1797        CopyMI->removeOperand(i - 1);1798      }1799    }1800 1801    CopyMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));1802    LLVM_DEBUG(dbgs() << "\tReplaced copy of <undef> value with an "1803                         "implicit def\n");1804    return CopyMI;1805  }1806 1807  // Remove any DstReg segments starting at the instruction.1808  LLVM_DEBUG(dbgs() << "\tEliminating copy of <undef> value\n");1809 1810  // Remove value or merge with previous one in case of a subregister def.1811  if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {1812    VNInfo *VNI = DstLI.getVNInfoAt(RegIndex);1813    DstLI.MergeValueNumberInto(VNI, PrevVNI);1814 1815    // The affected subregister segments can be removed.1816    LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx);1817    for (LiveInterval::SubRange &SR : DstLI.subranges()) {1818      if ((SR.LaneMask & DstMask).none())1819        continue;1820 1821      VNInfo *SVNI = SR.getVNInfoAt(RegIndex);1822      assert(SVNI != nullptr && SlotIndex::isSameInstr(SVNI->def, RegIndex));1823      SR.removeValNo(SVNI);1824    }1825    DstLI.removeEmptySubRanges();1826  } else1827    LIS->removeVRegDefAt(DstLI, RegIndex);1828 1829  // Mark uses as undef.1830  for (MachineOperand &MO : MRI->reg_nodbg_operands(DstReg)) {1831    if (MO.isDef() /*|| MO.isUndef()*/)1832      continue;1833    const MachineInstr &MI = *MO.getParent();1834    SlotIndex UseIdx = LIS->getInstructionIndex(MI);1835    LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());1836    bool isLive;1837    if (!UseMask.all() && DstLI.hasSubRanges()) {1838      isLive = false;1839      for (const LiveInterval::SubRange &SR : DstLI.subranges()) {1840        if ((SR.LaneMask & UseMask).none())1841          continue;1842        if (SR.liveAt(UseIdx)) {1843          isLive = true;1844          break;1845        }1846      }1847    } else1848      isLive = DstLI.liveAt(UseIdx);1849    if (isLive)1850      continue;1851    MO.setIsUndef(true);1852    LLVM_DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI);1853  }1854 1855  // A def of a subregister may be a use of the other subregisters, so1856  // deleting a def of a subregister may also remove uses. Since CopyMI1857  // is still part of the function (but about to be erased), mark all1858  // defs of DstReg in it as <undef>, so that shrinkToUses would1859  // ignore them.1860  for (MachineOperand &MO : CopyMI->all_defs())1861    if (MO.getReg() == DstReg)1862      MO.setIsUndef(true);1863  LIS->shrinkToUses(&DstLI);1864 1865  return CopyMI;1866}1867 1868void RegisterCoalescer::addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,1869                                     MachineOperand &MO, unsigned SubRegIdx) {1870  LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubRegIdx);1871  if (MO.isDef())1872    Mask = ~Mask;1873  bool IsUndef = true;1874  for (const LiveInterval::SubRange &S : Int.subranges()) {1875    if ((S.LaneMask & Mask).none())1876      continue;1877    if (S.liveAt(UseIdx)) {1878      IsUndef = false;1879      break;1880    }1881  }1882  if (IsUndef) {1883    MO.setIsUndef(true);1884    // We found out some subregister use is actually reading an undefined1885    // value. In some cases the whole vreg has become undefined at this1886    // point so we have to potentially shrink the main range if the1887    // use was ending a live segment there.1888    LiveQueryResult Q = Int.Query(UseIdx);1889    if (Q.valueOut() == nullptr)1890      ShrinkMainRange = true;1891  }1892}1893 1894void RegisterCoalescer::updateRegDefsUses(Register SrcReg, Register DstReg,1895                                          unsigned SubIdx) {1896  bool DstIsPhys = DstReg.isPhysical();1897  LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg);1898 1899  if (DstInt && DstInt->hasSubRanges() && DstReg != SrcReg) {1900    for (MachineOperand &MO : MRI->reg_operands(DstReg)) {1901      if (MO.isUndef())1902        continue;1903      unsigned SubReg = MO.getSubReg();1904      if (SubReg == 0 && MO.isDef())1905        continue;1906 1907      MachineInstr &MI = *MO.getParent();1908      if (MI.isDebugInstr())1909        continue;1910      SlotIndex UseIdx = LIS->getInstructionIndex(MI).getRegSlot(true);1911      addUndefFlag(*DstInt, UseIdx, MO, SubReg);1912    }1913  }1914 1915  SmallPtrSet<MachineInstr *, 8> Visited;1916  for (MachineRegisterInfo::reg_instr_iterator I = MRI->reg_instr_begin(SrcReg),1917                                               E = MRI->reg_instr_end();1918       I != E;) {1919    MachineInstr *UseMI = &*(I++);1920 1921    // Each instruction can only be rewritten once because sub-register1922    // composition is not always idempotent. When SrcReg != DstReg, rewriting1923    // the UseMI operands removes them from the SrcReg use-def chain, but when1924    // SrcReg is DstReg we could encounter UseMI twice if it has multiple1925    // operands mentioning the virtual register.1926    if (SrcReg == DstReg && !Visited.insert(UseMI).second)1927      continue;1928 1929    SmallVector<unsigned, 8> Ops;1930    bool Reads, Writes;1931    std::tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);1932 1933    // If SrcReg wasn't read, it may still be the case that DstReg is live-in1934    // because SrcReg is a sub-register.1935    if (DstInt && !Reads && SubIdx && !UseMI->isDebugInstr())1936      Reads = DstInt->liveAt(LIS->getInstructionIndex(*UseMI));1937 1938    // Replace SrcReg with DstReg in all UseMI operands.1939    for (unsigned Op : Ops) {1940      MachineOperand &MO = UseMI->getOperand(Op);1941 1942      // Adjust <undef> flags in case of sub-register joins. We don't want to1943      // turn a full def into a read-modify-write sub-register def and vice1944      // versa.1945      if (SubIdx && MO.isDef())1946        MO.setIsUndef(!Reads);1947 1948      // A subreg use of a partially undef (super) register may be a complete1949      // undef use now and then has to be marked that way.1950      if (MO.isUse() && !MO.isUndef() && !DstIsPhys) {1951        unsigned SubUseIdx = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());1952        if (SubUseIdx != 0 && MRI->shouldTrackSubRegLiveness(DstReg)) {1953          if (!DstInt->hasSubRanges()) {1954            BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();1955            LaneBitmask FullMask = MRI->getMaxLaneMaskForVReg(DstInt->reg());1956            LaneBitmask UsedLanes = TRI->getSubRegIndexLaneMask(SubIdx);1957            LaneBitmask UnusedLanes = FullMask & ~UsedLanes;1958            DstInt->createSubRangeFrom(Allocator, UsedLanes, *DstInt);1959            // The unused lanes are just empty live-ranges at this point.1960            // It is the caller responsibility to set the proper1961            // dead segments if there is an actual dead def of the1962            // unused lanes. This may happen with rematerialization.1963            DstInt->createSubRange(Allocator, UnusedLanes);1964          }1965          SlotIndex MIIdx = UseMI->isDebugInstr()1966                                ? LIS->getSlotIndexes()->getIndexBefore(*UseMI)1967                                : LIS->getInstructionIndex(*UseMI);1968          SlotIndex UseIdx = MIIdx.getRegSlot(true);1969          addUndefFlag(*DstInt, UseIdx, MO, SubUseIdx);1970        }1971      }1972 1973      if (DstIsPhys)1974        MO.substPhysReg(DstReg, *TRI);1975      else1976        MO.substVirtReg(DstReg, SubIdx, *TRI);1977    }1978 1979    LLVM_DEBUG({1980      dbgs() << "\t\tupdated: ";1981      if (!UseMI->isDebugInstr())1982        dbgs() << LIS->getInstructionIndex(*UseMI) << "\t";1983      dbgs() << *UseMI;1984    });1985  }1986}1987 1988bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {1989  // Always join simple intervals that are defined by a single copy from a1990  // reserved register. This doesn't increase register pressure, so it is1991  // always beneficial.1992  if (!MRI->isReserved(CP.getDstReg())) {1993    LLVM_DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");1994    return false;1995  }1996 1997  LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg());1998  if (JoinVInt.containsOneValue())1999    return true;2000 2001  LLVM_DEBUG(2002      dbgs() << "\tCannot join complex intervals into reserved register.\n");2003  return false;2004}2005 2006bool RegisterCoalescer::copyValueUndefInPredecessors(2007    LiveRange &S, const MachineBasicBlock *MBB, LiveQueryResult SLRQ) {2008  for (const MachineBasicBlock *Pred : MBB->predecessors()) {2009    SlotIndex PredEnd = LIS->getMBBEndIdx(Pred);2010    if (VNInfo *V = S.getVNInfoAt(PredEnd.getPrevSlot())) {2011      // If this is a self loop, we may be reading the same value.2012      if (V->id != SLRQ.valueOutOrDead()->id)2013        return false;2014    }2015  }2016 2017  return true;2018}2019 2020void RegisterCoalescer::setUndefOnPrunedSubRegUses(LiveInterval &LI,2021                                                   Register Reg,2022                                                   LaneBitmask PrunedLanes) {2023  // If we had other instructions in the segment reading the undef sublane2024  // value, we need to mark them with undef.2025  for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {2026    unsigned SubRegIdx = MO.getSubReg();2027    if (SubRegIdx == 0 || MO.isUndef())2028      continue;2029 2030    LaneBitmask SubRegMask = TRI->getSubRegIndexLaneMask(SubRegIdx);2031    SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());2032    for (LiveInterval::SubRange &S : LI.subranges()) {2033      if (!S.liveAt(Pos) && (PrunedLanes & SubRegMask).any()) {2034        MO.setIsUndef();2035        break;2036      }2037    }2038  }2039 2040  LI.removeEmptySubRanges();2041 2042  // A def of a subregister may be a use of other register lanes. Replacing2043  // such a def with a def of a different register will eliminate the use,2044  // and may cause the recorded live range to be larger than the actual2045  // liveness in the program IR.2046  LIS->shrinkToUses(&LI);2047}2048 2049bool RegisterCoalescer::joinCopy(2050    MachineInstr *CopyMI, bool &Again,2051    SmallPtrSetImpl<MachineInstr *> &CurrentErasedInstrs) {2052  Again = false;2053  LLVM_DEBUG(dbgs() << LIS->getInstructionIndex(*CopyMI) << '\t' << *CopyMI);2054 2055  CoalescerPair CP(*TRI);2056  if (!CP.setRegisters(CopyMI)) {2057    LLVM_DEBUG(dbgs() << "\tNot coalescable.\n");2058    return false;2059  }2060 2061  if (CP.getNewRC()) {2062    if (RegClassInfo.getNumAllocatableRegs(CP.getNewRC()) == 0) {2063      LLVM_DEBUG(dbgs() << "\tNo " << TRI->getRegClassName(CP.getNewRC())2064                        << "are available for allocation\n");2065      return false;2066    }2067 2068    auto SrcRC = MRI->getRegClass(CP.getSrcReg());2069    auto DstRC = MRI->getRegClass(CP.getDstReg());2070    unsigned SrcIdx = CP.getSrcIdx();2071    unsigned DstIdx = CP.getDstIdx();2072    if (CP.isFlipped()) {2073      std::swap(SrcIdx, DstIdx);2074      std::swap(SrcRC, DstRC);2075    }2076    if (!TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,2077                             CP.getNewRC(), *LIS)) {2078      LLVM_DEBUG(dbgs() << "\tSubtarget bailed on coalescing.\n");2079      return false;2080    }2081  }2082 2083  // Dead code elimination. This really should be handled by MachineDCE, but2084  // sometimes dead copies slip through, and we can't generate invalid live2085  // ranges.2086  if (!CP.isPhys() && CopyMI->allDefsAreDead()) {2087    LLVM_DEBUG(dbgs() << "\tCopy is dead.\n");2088    DeadDefs.push_back(CopyMI);2089    eliminateDeadDefs();2090    return true;2091  }2092 2093  // Eliminate undefs.2094  if (!CP.isPhys()) {2095    // If this is an IMPLICIT_DEF, leave it alone, but don't try to coalesce.2096    if (MachineInstr *UndefMI = eliminateUndefCopy(CopyMI)) {2097      if (UndefMI->isImplicitDef())2098        return false;2099      deleteInstr(CopyMI);2100      return false; // Not coalescable.2101    }2102  }2103 2104  // Coalesced copies are normally removed immediately, but transformations2105  // like removeCopyByCommutingDef() can inadvertently create identity copies.2106  // When that happens, just join the values and remove the copy.2107  if (CP.getSrcReg() == CP.getDstReg()) {2108    LiveInterval &LI = LIS->getInterval(CP.getSrcReg());2109    LLVM_DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n');2110    const SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);2111    LiveQueryResult LRQ = LI.Query(CopyIdx);2112    if (VNInfo *DefVNI = LRQ.valueDefined()) {2113      VNInfo *ReadVNI = LRQ.valueIn();2114      assert(ReadVNI && "No value before copy and no <undef> flag.");2115      assert(ReadVNI != DefVNI && "Cannot read and define the same value.");2116 2117      // Track incoming undef lanes we need to eliminate from the subrange.2118      LaneBitmask PrunedLanes;2119      MachineBasicBlock *MBB = CopyMI->getParent();2120 2121      // Process subregister liveranges.2122      for (LiveInterval::SubRange &S : LI.subranges()) {2123        LiveQueryResult SLRQ = S.Query(CopyIdx);2124        if (VNInfo *SDefVNI = SLRQ.valueDefined()) {2125          if (VNInfo *SReadVNI = SLRQ.valueIn())2126            SDefVNI = S.MergeValueNumberInto(SDefVNI, SReadVNI);2127 2128          // If this copy introduced an undef subrange from an incoming value,2129          // we need to eliminate the undef live in values from the subrange.2130          if (copyValueUndefInPredecessors(S, MBB, SLRQ)) {2131            LLVM_DEBUG(dbgs() << "Incoming sublane value is undef at copy\n");2132            PrunedLanes |= S.LaneMask;2133            S.removeValNo(SDefVNI);2134          }2135        }2136      }2137 2138      LI.MergeValueNumberInto(DefVNI, ReadVNI);2139      if (PrunedLanes.any()) {2140        LLVM_DEBUG(dbgs() << "Pruning undef incoming lanes: " << PrunedLanes2141                          << '\n');2142        setUndefOnPrunedSubRegUses(LI, CP.getSrcReg(), PrunedLanes);2143      }2144 2145      LLVM_DEBUG(dbgs() << "\tMerged values:          " << LI << '\n');2146    }2147    deleteInstr(CopyMI);2148    return true;2149  }2150 2151  // Enforce policies.2152  if (CP.isPhys()) {2153    LLVM_DEBUG(dbgs() << "\tConsidering merging "2154                      << printReg(CP.getSrcReg(), TRI) << " with "2155                      << printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n');2156    if (!canJoinPhys(CP)) {2157      // Before giving up coalescing, try rematerializing the source of2158      // the copy instead if it is cheap.2159      bool IsDefCopy = false;2160      if (reMaterializeDef(CP, CopyMI, IsDefCopy))2161        return true;2162      if (IsDefCopy)2163        Again = true; // May be possible to coalesce later.2164      return false;2165    }2166  } else {2167    // When possible, let DstReg be the larger interval.2168    if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() >2169                               LIS->getInterval(CP.getDstReg()).size())2170      CP.flip();2171 2172    LLVM_DEBUG({2173      dbgs() << "\tConsidering merging to "2174             << TRI->getRegClassName(CP.getNewRC()) << " with ";2175      if (CP.getDstIdx() && CP.getSrcIdx())2176        dbgs() << printReg(CP.getDstReg()) << " in "2177               << TRI->getSubRegIndexName(CP.getDstIdx()) << " and "2178               << printReg(CP.getSrcReg()) << " in "2179               << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n';2180      else2181        dbgs() << printReg(CP.getSrcReg(), TRI) << " in "2182               << printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n';2183    });2184  }2185 2186  ShrinkMask = LaneBitmask::getNone();2187  ShrinkMainRange = false;2188 2189  // Okay, attempt to join these two intervals.  On failure, this returns false.2190  // Otherwise, if one of the intervals being joined is a physreg, this method2191  // always canonicalizes DstInt to be it.  The output "SrcInt" will not have2192  // been modified, so we can use this information below to update aliases.2193  if (!joinIntervals(CP)) {2194    // Coalescing failed.2195 2196    // Try rematerializing the definition of the source if it is cheap.2197    bool IsDefCopy = false;2198    if (reMaterializeDef(CP, CopyMI, IsDefCopy))2199      return true;2200 2201    // If we can eliminate the copy without merging the live segments, do so2202    // now.2203    if (!CP.isPartial() && !CP.isPhys()) {2204      bool Changed = adjustCopiesBackFrom(CP, CopyMI);2205      bool Shrink = false;2206      if (!Changed)2207        std::tie(Changed, Shrink) = removeCopyByCommutingDef(CP, CopyMI);2208      if (Changed) {2209        deleteInstr(CopyMI);2210        if (Shrink) {2211          Register DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();2212          LiveInterval &DstLI = LIS->getInterval(DstReg);2213          shrinkToUses(&DstLI);2214          LLVM_DEBUG(dbgs() << "\t\tshrunk:   " << DstLI << '\n');2215        }2216        LLVM_DEBUG(dbgs() << "\tTrivial!\n");2217        return true;2218      }2219    }2220 2221    // Try and see if we can partially eliminate the copy by moving the copy to2222    // its predecessor.2223    if (!CP.isPartial() && !CP.isPhys())2224      if (removePartialRedundancy(CP, *CopyMI))2225        return true;2226 2227    // Otherwise, we are unable to join the intervals.2228    LLVM_DEBUG(dbgs() << "\tInterference!\n");2229    Again = true; // May be possible to coalesce later.2230    return false;2231  }2232 2233  // Coalescing to a virtual register that is of a sub-register class of the2234  // other. Make sure the resulting register is set to the right register class.2235  if (CP.isCrossClass()) {2236    ++numCrossRCs;2237    MRI->setRegClass(CP.getDstReg(), CP.getNewRC());2238  }2239 2240  // Removing sub-register copies can ease the register class constraints.2241  // Make sure we attempt to inflate the register class of DstReg.2242  if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC()))2243    InflateRegs.push_back(CP.getDstReg());2244 2245  // CopyMI has been erased by joinIntervals at this point. Remove it from2246  // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back2247  // to the work list. This keeps ErasedInstrs from growing needlessly.2248  if (ErasedInstrs.erase(CopyMI))2249    // But we may encounter the instruction again in this iteration.2250    CurrentErasedInstrs.insert(CopyMI);2251 2252  // Rewrite all SrcReg operands to DstReg.2253  // Also update DstReg operands to include DstIdx if it is set.2254  if (CP.getDstIdx())2255    updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx());2256  updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx());2257 2258  // Shrink subregister ranges if necessary.2259  if (ShrinkMask.any()) {2260    LiveInterval &LI = LIS->getInterval(CP.getDstReg());2261    for (LiveInterval::SubRange &S : LI.subranges()) {2262      if ((S.LaneMask & ShrinkMask).none())2263        continue;2264      LLVM_DEBUG(dbgs() << "Shrink LaneUses (Lane " << PrintLaneMask(S.LaneMask)2265                        << ")\n");2266      LIS->shrinkToUses(S, LI.reg());2267      ShrinkMainRange = true;2268    }2269    LI.removeEmptySubRanges();2270  }2271 2272  // CP.getSrcReg()'s live interval has been merged into CP.getDstReg's live2273  // interval. Since CP.getSrcReg() is in ToBeUpdated set and its live interval2274  // is not up-to-date, need to update the merged live interval here.2275  if (ToBeUpdated.count(CP.getSrcReg()))2276    ShrinkMainRange = true;2277 2278  if (ShrinkMainRange) {2279    LiveInterval &LI = LIS->getInterval(CP.getDstReg());2280    shrinkToUses(&LI);2281  }2282 2283  // SrcReg is guaranteed to be the register whose live interval that is2284  // being merged.2285  LIS->removeInterval(CP.getSrcReg());2286 2287  // Update regalloc hint.2288  TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);2289 2290  LLVM_DEBUG({2291    dbgs() << "\tSuccess: " << printReg(CP.getSrcReg(), TRI, CP.getSrcIdx())2292           << " -> " << printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';2293    dbgs() << "\tResult = ";2294    if (CP.isPhys())2295      dbgs() << printReg(CP.getDstReg(), TRI);2296    else2297      dbgs() << LIS->getInterval(CP.getDstReg());2298    dbgs() << '\n';2299  });2300 2301  ++numJoins;2302  return true;2303}2304 2305bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {2306  Register DstReg = CP.getDstReg();2307  Register SrcReg = CP.getSrcReg();2308  assert(CP.isPhys() && "Must be a physreg copy");2309  assert(MRI->isReserved(DstReg) && "Not a reserved register");2310  LiveInterval &RHS = LIS->getInterval(SrcReg);2311  LLVM_DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n');2312 2313  assert(RHS.containsOneValue() && "Invalid join with reserved register");2314 2315  // Optimization for reserved registers like ESP. We can only merge with a2316  // reserved physreg if RHS has a single value that is a copy of DstReg.2317  // The live range of the reserved register will look like a set of dead defs2318  // - we don't properly track the live range of reserved registers.2319 2320  // Deny any overlapping intervals.  This depends on all the reserved2321  // register live ranges to look like dead defs.2322  if (!MRI->isConstantPhysReg(DstReg)) {2323    for (MCRegUnit Unit : TRI->regunits(DstReg)) {2324      // Abort if not all the regunits are reserved.2325      for (MCRegUnitRootIterator RI(Unit, TRI); RI.isValid(); ++RI) {2326        if (!MRI->isReserved(*RI))2327          return false;2328      }2329      if (RHS.overlaps(LIS->getRegUnit(Unit))) {2330        LLVM_DEBUG(dbgs() << "\t\tInterference: " << printRegUnit(Unit, TRI)2331                          << '\n');2332        return false;2333      }2334    }2335 2336    // We must also check for overlaps with regmask clobbers.2337    BitVector RegMaskUsable;2338    if (LIS->checkRegMaskInterference(RHS, RegMaskUsable) &&2339        !RegMaskUsable.test(DstReg.id())) {2340      LLVM_DEBUG(dbgs() << "\t\tRegMask interference\n");2341      return false;2342    }2343  }2344 2345  // Skip any value computations, we are not adding new values to the2346  // reserved register.  Also skip merging the live ranges, the reserved2347  // register live range doesn't need to be accurate as long as all the2348  // defs are there.2349 2350  // Delete the identity copy.2351  MachineInstr *CopyMI;2352  if (CP.isFlipped()) {2353    // Physreg is copied into vreg2354    //   %y = COPY %physreg_x2355    //   ...  //< no other def of %physreg_x here2356    //   use %y2357    // =>2358    //   ...2359    //   use %physreg_x2360    CopyMI = MRI->getVRegDef(SrcReg);2361    deleteInstr(CopyMI);2362  } else {2363    // VReg is copied into physreg:2364    //   %y = def2365    //   ... //< no other def or use of %physreg_x here2366    //   %physreg_x = COPY %y2367    // =>2368    //   %physreg_x = def2369    //   ...2370    if (!MRI->hasOneNonDBGUse(SrcReg)) {2371      LLVM_DEBUG(dbgs() << "\t\tMultiple vreg uses!\n");2372      return false;2373    }2374 2375    if (!LIS->intervalIsInOneMBB(RHS)) {2376      LLVM_DEBUG(dbgs() << "\t\tComplex control flow!\n");2377      return false;2378    }2379 2380    MachineInstr &DestMI = *MRI->getVRegDef(SrcReg);2381    CopyMI = &*MRI->use_instr_nodbg_begin(SrcReg);2382    SlotIndex CopyRegIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();2383    SlotIndex DestRegIdx = LIS->getInstructionIndex(DestMI).getRegSlot();2384 2385    if (!MRI->isConstantPhysReg(DstReg)) {2386      // We checked above that there are no interfering defs of the physical2387      // register. However, for this case, where we intend to move up the def of2388      // the physical register, we also need to check for interfering uses.2389      SlotIndexes *Indexes = LIS->getSlotIndexes();2390      for (SlotIndex SI = Indexes->getNextNonNullIndex(DestRegIdx);2391           SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(SI)) {2392        MachineInstr *MI = LIS->getInstructionFromIndex(SI);2393        if (MI->readsRegister(DstReg, TRI)) {2394          LLVM_DEBUG(dbgs() << "\t\tInterference (read): " << *MI);2395          return false;2396        }2397      }2398    }2399 2400    // We're going to remove the copy which defines a physical reserved2401    // register, so remove its valno, etc.2402    LLVM_DEBUG(dbgs() << "\t\tRemoving phys reg def of "2403                      << printReg(DstReg, TRI) << " at " << CopyRegIdx << "\n");2404 2405    LIS->removePhysRegDefAt(DstReg.asMCReg(), CopyRegIdx);2406    deleteInstr(CopyMI);2407 2408    // Create a new dead def at the new def location.2409    for (MCRegUnit Unit : TRI->regunits(DstReg)) {2410      LiveRange &LR = LIS->getRegUnit(Unit);2411      LR.createDeadDef(DestRegIdx, LIS->getVNInfoAllocator());2412    }2413  }2414 2415  // We don't track kills for reserved registers.2416  MRI->clearKillFlags(CP.getSrcReg());2417 2418  return true;2419}2420 2421//===----------------------------------------------------------------------===//2422//                 Interference checking and interval joining2423//===----------------------------------------------------------------------===//2424//2425// In the easiest case, the two live ranges being joined are disjoint, and2426// there is no interference to consider. It is quite common, though, to have2427// overlapping live ranges, and we need to check if the interference can be2428// resolved.2429//2430// The live range of a single SSA value forms a sub-tree of the dominator tree.2431// This means that two SSA values overlap if and only if the def of one value2432// is contained in the live range of the other value. As a special case, the2433// overlapping values can be defined at the same index.2434//2435// The interference from an overlapping def can be resolved in these cases:2436//2437// 1. Coalescable copies. The value is defined by a copy that would become an2438//    identity copy after joining SrcReg and DstReg. The copy instruction will2439//    be removed, and the value will be merged with the source value.2440//2441//    There can be several copies back and forth, causing many values to be2442//    merged into one. We compute a list of ultimate values in the joined live2443//    range as well as a mappings from the old value numbers.2444//2445// 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI2446//    predecessors have a live out value. It doesn't cause real interference,2447//    and can be merged into the value it overlaps. Like a coalescable copy, it2448//    can be erased after joining.2449//2450// 3. Copy of external value. The overlapping def may be a copy of a value that2451//    is already in the other register. This is like a coalescable copy, but2452//    the live range of the source register must be trimmed after erasing the2453//    copy instruction:2454//2455//      %src = COPY %ext2456//      %dst = COPY %ext  <-- Remove this COPY, trim the live range of %ext.2457//2458// 4. Clobbering undefined lanes. Vector registers are sometimes built by2459//    defining one lane at a time:2460//2461//      %dst:ssub0<def,read-undef> = FOO2462//      %src = BAR2463//      %dst:ssub1 = COPY %src2464//2465//    The live range of %src overlaps the %dst value defined by FOO, but2466//    merging %src into %dst:ssub1 is only going to clobber the ssub1 lane2467//    which was undef anyway.2468//2469//    The value mapping is more complicated in this case. The final live range2470//    will have different value numbers for both FOO and BAR, but there is no2471//    simple mapping from old to new values. It may even be necessary to add2472//    new PHI values.2473//2474// 5. Clobbering dead lanes. A def may clobber a lane of a vector register that2475//    is live, but never read. This can happen because we don't compute2476//    individual live ranges per lane.2477//2478//      %dst = FOO2479//      %src = BAR2480//      %dst:ssub1 = COPY %src2481//2482//    This kind of interference is only resolved locally. If the clobbered2483//    lane value escapes the block, the join is aborted.2484 2485namespace {2486 2487/// Track information about values in a single virtual register about to be2488/// joined. Objects of this class are always created in pairs - one for each2489/// side of the CoalescerPair (or one for each lane of a side of the coalescer2490/// pair)2491class JoinVals {2492  /// Live range we work on.2493  LiveRange &LR;2494 2495  /// (Main) register we work on.2496  const Register Reg;2497 2498  /// Reg (and therefore the values in this liverange) will end up as2499  /// subregister SubIdx in the coalesced register. Either CP.DstIdx or2500  /// CP.SrcIdx.2501  const unsigned SubIdx;2502 2503  /// The LaneMask that this liverange will occupy the coalesced register. May2504  /// be smaller than the lanemask produced by SubIdx when merging subranges.2505  const LaneBitmask LaneMask;2506 2507  /// This is true when joining sub register ranges, false when joining main2508  /// ranges.2509  const bool SubRangeJoin;2510 2511  /// Whether the current LiveInterval tracks subregister liveness.2512  const bool TrackSubRegLiveness;2513 2514  /// Values that will be present in the final live range.2515  SmallVectorImpl<VNInfo *> &NewVNInfo;2516 2517  const CoalescerPair &CP;2518  LiveIntervals *LIS;2519  SlotIndexes *Indexes;2520  const TargetRegisterInfo *TRI;2521 2522  /// Value number assignments. Maps value numbers in LI to entries in2523  /// NewVNInfo. This is suitable for passing to LiveInterval::join().2524  SmallVector<int, 8> Assignments;2525 2526public:2527  /// Conflict resolution for overlapping values.2528  enum ConflictResolution {2529    /// No overlap, simply keep this value.2530    CR_Keep,2531 2532    /// Merge this value into OtherVNI and erase the defining instruction.2533    /// Used for IMPLICIT_DEF, coalescable copies, and copies from external2534    /// values.2535    CR_Erase,2536 2537    /// Merge this value into OtherVNI but keep the defining instruction.2538    /// This is for the special case where OtherVNI is defined by the same2539    /// instruction.2540    CR_Merge,2541 2542    /// Keep this value, and have it replace OtherVNI where possible. This2543    /// complicates value mapping since OtherVNI maps to two different values2544    /// before and after this def.2545    /// Used when clobbering undefined or dead lanes.2546    CR_Replace,2547 2548    /// Unresolved conflict. Visit later when all values have been mapped.2549    CR_Unresolved,2550 2551    /// Unresolvable conflict. Abort the join.2552    CR_Impossible2553  };2554 2555private:2556  /// Per-value info for LI. The lane bit masks are all relative to the final2557  /// joined register, so they can be compared directly between SrcReg and2558  /// DstReg.2559  struct Val {2560    ConflictResolution Resolution = CR_Keep;2561 2562    /// Lanes written by this def, 0 for unanalyzed values.2563    LaneBitmask WriteLanes;2564 2565    /// Lanes with defined values in this register. Other lanes are undef and2566    /// safe to clobber.2567    LaneBitmask ValidLanes;2568 2569    /// Value in LI being redefined by this def.2570    VNInfo *RedefVNI = nullptr;2571 2572    /// Value in the other live range that overlaps this def, if any.2573    VNInfo *OtherVNI = nullptr;2574 2575    /// Is this value an IMPLICIT_DEF that can be erased?2576    ///2577    /// IMPLICIT_DEF values should only exist at the end of a basic block that2578    /// is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be2579    /// safely erased if they are overlapping a live value in the other live2580    /// interval.2581    ///2582    /// Weird control flow graphs and incomplete PHI handling in2583    /// ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with2584    /// longer live ranges. Such IMPLICIT_DEF values should be treated like2585    /// normal values.2586    bool ErasableImplicitDef = false;2587 2588    /// True when the live range of this value will be pruned because of an2589    /// overlapping CR_Replace value in the other live range.2590    bool Pruned = false;2591 2592    /// True once Pruned above has been computed.2593    bool PrunedComputed = false;2594 2595    /// True if this value is determined to be identical to OtherVNI2596    /// (in valuesIdentical). This is used with CR_Erase where the erased2597    /// copy is redundant, i.e. the source value is already the same as2598    /// the destination. In such cases the subranges need to be updated2599    /// properly. See comment at pruneSubRegValues for more info.2600    bool Identical = false;2601 2602    Val() = default;2603 2604    bool isAnalyzed() const { return WriteLanes.any(); }2605 2606    /// Mark this value as an IMPLICIT_DEF which must be kept as if it were an2607    /// ordinary value.2608    void mustKeepImplicitDef(const TargetRegisterInfo &TRI,2609                             const MachineInstr &ImpDef) {2610      assert(ImpDef.isImplicitDef());2611      ErasableImplicitDef = false;2612      ValidLanes = TRI.getSubRegIndexLaneMask(ImpDef.getOperand(0).getSubReg());2613    }2614  };2615 2616  /// One entry per value number in LI.2617  SmallVector<Val, 8> Vals;2618 2619  /// Compute the bitmask of lanes actually written by DefMI.2620  /// Set Redef if there are any partial register definitions that depend on the2621  /// previous value of the register.2622  LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;2623 2624  /// Find the ultimate value that VNI was copied from.2625  std::pair<const VNInfo *, Register> followCopyChain(const VNInfo *VNI) const;2626 2627  bool valuesIdentical(VNInfo *Value0, VNInfo *Value1,2628                       const JoinVals &Other) const;2629 2630  /// Analyze ValNo in this live range, and set all fields of Vals[ValNo].2631  /// Return a conflict resolution when possible, but leave the hard cases as2632  /// CR_Unresolved.2633  /// Recursively calls computeAssignment() on this and Other, guaranteeing that2634  /// both OtherVNI and RedefVNI have been analyzed and mapped before returning.2635  /// The recursion always goes upwards in the dominator tree, making loops2636  /// impossible.2637  ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other);2638 2639  /// Compute the value assignment for ValNo in RI.2640  /// This may be called recursively by analyzeValue(), but never for a ValNo on2641  /// the stack.2642  void computeAssignment(unsigned ValNo, JoinVals &Other);2643 2644  /// Assuming ValNo is going to clobber some valid lanes in Other.LR, compute2645  /// the extent of the tainted lanes in the block.2646  ///2647  /// Multiple values in Other.LR can be affected since partial redefinitions2648  /// can preserve previously tainted lanes.2649  ///2650  ///   1 %dst = VLOAD           <-- Define all lanes in %dst2651  ///   2 %src = FOO             <-- ValNo to be joined with %dst:ssub02652  ///   3 %dst:ssub1 = BAR       <-- Partial redef doesn't clear taint in ssub02653  ///   4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read2654  ///2655  /// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes)2656  /// entry to TaintedVals.2657  ///2658  /// Returns false if the tainted lanes extend beyond the basic block.2659  bool2660  taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,2661              SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent);2662 2663  /// Return true if MI uses any of the given Lanes from Reg.2664  /// This does not include partial redefinitions of Reg.2665  bool usesLanes(const MachineInstr &MI, Register, unsigned, LaneBitmask) const;2666 2667  /// Determine if ValNo is a copy of a value number in LR or Other.LR that will2668  /// be pruned:2669  ///2670  ///   %dst = COPY %src2671  ///   %src = COPY %dst  <-- This value to be pruned.2672  ///   %dst = COPY %src  <-- This value is a copy of a pruned value.2673  bool isPrunedValue(unsigned ValNo, JoinVals &Other);2674 2675public:2676  JoinVals(LiveRange &LR, Register Reg, unsigned SubIdx, LaneBitmask LaneMask,2677           SmallVectorImpl<VNInfo *> &newVNInfo, const CoalescerPair &cp,2678           LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin,2679           bool TrackSubRegLiveness)2680      : LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask),2681        SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),2682        NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),2683        TRI(TRI), Assignments(LR.getNumValNums(), -1),2684        Vals(LR.getNumValNums()) {}2685 2686  /// Analyze defs in LR and compute a value mapping in NewVNInfo.2687  /// Returns false if any conflicts were impossible to resolve.2688  bool mapValues(JoinVals &Other);2689 2690  /// Try to resolve conflicts that require all values to be mapped.2691  /// Returns false if any conflicts were impossible to resolve.2692  bool resolveConflicts(JoinVals &Other);2693 2694  /// Prune the live range of values in Other.LR where they would conflict with2695  /// CR_Replace values in LR. Collect end points for restoring the live range2696  /// after joining.2697  void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints,2698                   bool changeInstrs);2699 2700  /// Removes subranges starting at copies that get removed. This sometimes2701  /// happens when undefined subranges are copied around. These ranges contain2702  /// no useful information and can be removed.2703  void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);2704 2705  /// Pruning values in subranges can lead to removing segments in these2706  /// subranges started by IMPLICIT_DEFs. The corresponding segments in2707  /// the main range also need to be removed. This function will mark2708  /// the corresponding values in the main range as pruned, so that2709  /// eraseInstrs can do the final cleanup.2710  /// The parameter @p LI must be the interval whose main range is the2711  /// live range LR.2712  void pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange);2713 2714  /// Erase any machine instructions that have been coalesced away.2715  /// Add erased instructions to ErasedInstrs.2716  /// Add foreign virtual registers to ShrinkRegs if their live range ended at2717  /// the erased instrs.2718  void eraseInstrs(SmallPtrSetImpl<MachineInstr *> &ErasedInstrs,2719                   SmallVectorImpl<Register> &ShrinkRegs,2720                   LiveInterval *LI = nullptr);2721 2722  /// Remove liverange defs at places where implicit defs will be removed.2723  void removeImplicitDefs();2724 2725  /// Get the value assignments suitable for passing to LiveInterval::join.2726  const int *getAssignments() const { return Assignments.data(); }2727 2728  /// Get the conflict resolution for a value number.2729  ConflictResolution getResolution(unsigned Num) const {2730    return Vals[Num].Resolution;2731  }2732};2733 2734} // end anonymous namespace2735 2736LaneBitmask JoinVals::computeWriteLanes(const MachineInstr *DefMI,2737                                        bool &Redef) const {2738  LaneBitmask L;2739  for (const MachineOperand &MO : DefMI->all_defs()) {2740    if (MO.getReg() != Reg)2741      continue;2742    L |= TRI->getSubRegIndexLaneMask(2743        TRI->composeSubRegIndices(SubIdx, MO.getSubReg()));2744    if (MO.readsReg())2745      Redef = true;2746  }2747  return L;2748}2749 2750std::pair<const VNInfo *, Register>2751JoinVals::followCopyChain(const VNInfo *VNI) const {2752  Register TrackReg = Reg;2753 2754  while (!VNI->isPHIDef()) {2755    SlotIndex Def = VNI->def;2756    MachineInstr *MI = Indexes->getInstructionFromIndex(Def);2757    assert(MI && "No defining instruction");2758    if (!MI->isFullCopy())2759      return std::make_pair(VNI, TrackReg);2760    Register SrcReg = MI->getOperand(1).getReg();2761    if (!SrcReg.isVirtual())2762      return std::make_pair(VNI, TrackReg);2763 2764    const LiveInterval &LI = LIS->getInterval(SrcReg);2765    const VNInfo *ValueIn;2766    // No subrange involved.2767    if (!SubRangeJoin || !LI.hasSubRanges()) {2768      LiveQueryResult LRQ = LI.Query(Def);2769      ValueIn = LRQ.valueIn();2770    } else {2771      // Query subranges. Ensure that all matching ones take us to the same def2772      // (allowing some of them to be undef).2773      ValueIn = nullptr;2774      for (const LiveInterval::SubRange &S : LI.subranges()) {2775        // Transform lanemask to a mask in the joined live interval.2776        LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);2777        if ((SMask & LaneMask).none())2778          continue;2779        LiveQueryResult LRQ = S.Query(Def);2780        if (!ValueIn) {2781          ValueIn = LRQ.valueIn();2782          continue;2783        }2784        if (LRQ.valueIn() && ValueIn != LRQ.valueIn())2785          return std::make_pair(VNI, TrackReg);2786      }2787    }2788    if (ValueIn == nullptr) {2789      // Reaching an undefined value is legitimate, for example:2790      //2791      // 1   undef %0.sub1 = ...  ;; %0.sub0 == undef2792      // 2   %1 = COPY %0         ;; %1 is defined here.2793      // 3   %0 = COPY %1         ;; Now %0.sub0 has a definition,2794      //                          ;; but it's equivalent to "undef".2795      return std::make_pair(nullptr, SrcReg);2796    }2797    VNI = ValueIn;2798    TrackReg = SrcReg;2799  }2800  return std::make_pair(VNI, TrackReg);2801}2802 2803bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1,2804                               const JoinVals &Other) const {2805  const VNInfo *Orig0;2806  Register Reg0;2807  std::tie(Orig0, Reg0) = followCopyChain(Value0);2808  if (Orig0 == Value1 && Reg0 == Other.Reg)2809    return true;2810 2811  const VNInfo *Orig1;2812  Register Reg1;2813  std::tie(Orig1, Reg1) = Other.followCopyChain(Value1);2814  // If both values are undefined, and the source registers are the same2815  // register, the values are identical. Filter out cases where only one2816  // value is defined.2817  if (Orig0 == nullptr || Orig1 == nullptr)2818    return Orig0 == Orig1 && Reg0 == Reg1;2819 2820  // The values are equal if they are defined at the same place and use the2821  // same register. Note that we cannot compare VNInfos directly as some of2822  // them might be from a copy created in mergeSubRangeInto()  while the other2823  // is from the original LiveInterval.2824  return Orig0->def == Orig1->def && Reg0 == Reg1;2825}2826 2827JoinVals::ConflictResolution JoinVals::analyzeValue(unsigned ValNo,2828                                                    JoinVals &Other) {2829  Val &V = Vals[ValNo];2830  assert(!V.isAnalyzed() && "Value has already been analyzed!");2831  VNInfo *VNI = LR.getValNumInfo(ValNo);2832  if (VNI->isUnused()) {2833    V.WriteLanes = LaneBitmask::getAll();2834    return CR_Keep;2835  }2836 2837  // Get the instruction defining this value, compute the lanes written.2838  const MachineInstr *DefMI = nullptr;2839  if (VNI->isPHIDef()) {2840    // Conservatively assume that all lanes in a PHI are valid.2841    LaneBitmask Lanes = SubRangeJoin ? LaneBitmask::getLane(0)2842                                     : TRI->getSubRegIndexLaneMask(SubIdx);2843    V.ValidLanes = V.WriteLanes = Lanes;2844  } else {2845    DefMI = Indexes->getInstructionFromIndex(VNI->def);2846    assert(DefMI != nullptr);2847    if (SubRangeJoin) {2848      // We don't care about the lanes when joining subregister ranges.2849      V.WriteLanes = V.ValidLanes = LaneBitmask::getLane(0);2850      if (DefMI->isImplicitDef()) {2851        V.ValidLanes = LaneBitmask::getNone();2852        V.ErasableImplicitDef = true;2853      }2854    } else {2855      bool Redef = false;2856      V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef);2857 2858      // If this is a read-modify-write instruction, there may be more valid2859      // lanes than the ones written by this instruction.2860      // This only covers partial redef operands. DefMI may have normal use2861      // operands reading the register. They don't contribute valid lanes.2862      //2863      // This adds ssub1 to the set of valid lanes in %src:2864      //2865      //   %src:ssub1 = FOO2866      //2867      // This leaves only ssub1 valid, making any other lanes undef:2868      //2869      //   %src:ssub1<def,read-undef> = FOO %src:ssub22870      //2871      // The <read-undef> flag on the def operand means that old lane values are2872      // not important.2873      if (Redef) {2874        V.RedefVNI = LR.Query(VNI->def).valueIn();2875        assert((TrackSubRegLiveness || V.RedefVNI) &&2876               "Instruction is reading nonexistent value");2877        if (V.RedefVNI != nullptr) {2878          computeAssignment(V.RedefVNI->id, Other);2879          V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;2880        }2881      }2882 2883      // An IMPLICIT_DEF writes undef values.2884      if (DefMI->isImplicitDef()) {2885        // We normally expect IMPLICIT_DEF values to be live only until the end2886        // of their block. If the value is really live longer and gets pruned in2887        // another block, this flag is cleared again.2888        //2889        // Clearing the valid lanes is deferred until it is sure this can be2890        // erased.2891        V.ErasableImplicitDef = true;2892      }2893    }2894  }2895 2896  // Find the value in Other that overlaps VNI->def, if any.2897  LiveQueryResult OtherLRQ = Other.LR.Query(VNI->def);2898 2899  // It is possible that both values are defined by the same instruction, or2900  // the values are PHIs defined in the same block. When that happens, the two2901  // values should be merged into one, but not into any preceding value.2902  // The first value defined or visited gets CR_Keep, the other gets CR_Merge.2903  if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) {2904    assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ");2905 2906    // One value stays, the other is merged. Keep the earlier one, or the first2907    // one we see.2908    if (OtherVNI->def < VNI->def)2909      Other.computeAssignment(OtherVNI->id, *this);2910    else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) {2911      // This is an early-clobber def overlapping a live-in value in the other2912      // register. Not mergeable.2913      V.OtherVNI = OtherLRQ.valueIn();2914      return CR_Impossible;2915    }2916    V.OtherVNI = OtherVNI;2917    Val &OtherV = Other.Vals[OtherVNI->id];2918    // Keep this value, check for conflicts when analyzing OtherVNI. Avoid2919    // revisiting OtherVNI->id in JoinVals::computeAssignment() below before it2920    // is assigned.2921    if (!OtherV.isAnalyzed() || Other.Assignments[OtherVNI->id] == -1)2922      return CR_Keep;2923    // Both sides have been analyzed now.2924    // Allow overlapping PHI values. Any real interference would show up in a2925    // predecessor, the PHI itself can't introduce any conflicts.2926    if (VNI->isPHIDef())2927      return CR_Merge;2928    if ((V.ValidLanes & OtherV.ValidLanes).any())2929      // Overlapping lanes can't be resolved.2930      return CR_Impossible;2931    return CR_Merge;2932  }2933 2934  // No simultaneous def. Is Other live at the def?2935  V.OtherVNI = OtherLRQ.valueIn();2936  if (!V.OtherVNI)2937    // No overlap, no conflict.2938    return CR_Keep;2939 2940  assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ");2941 2942  // We have overlapping values, or possibly a kill of Other.2943  // Recursively compute assignments up the dominator tree.2944  Other.computeAssignment(V.OtherVNI->id, *this);2945  Val &OtherV = Other.Vals[V.OtherVNI->id];2946 2947  if (OtherV.ErasableImplicitDef) {2948    // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block.2949    // This shouldn't normally happen, but ProcessImplicitDefs can leave such2950    // IMPLICIT_DEF instructions behind, and there is nothing wrong with it2951    // technically.2952    //2953    // When it happens, treat that IMPLICIT_DEF as a normal value, and don't try2954    // to erase the IMPLICIT_DEF instruction.2955    //2956    // Additionally we must keep an IMPLICIT_DEF if we're redefining an incoming2957    // value.2958 2959    MachineInstr *OtherImpDef =2960        Indexes->getInstructionFromIndex(V.OtherVNI->def);2961    MachineBasicBlock *OtherMBB = OtherImpDef->getParent();2962    if (DefMI &&2963        (DefMI->getParent() != OtherMBB || LIS->isLiveInToMBB(LR, OtherMBB))) {2964      LLVM_DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def2965                        << " extends into "2966                        << printMBBReference(*DefMI->getParent())2967                        << ", keeping it.\n");2968      OtherV.mustKeepImplicitDef(*TRI, *OtherImpDef);2969    } else if (OtherMBB->hasEHPadSuccessor()) {2970      // If OtherV is defined in a basic block that has EH pad successors then2971      // we get the same problem not just if OtherV is live beyond its basic2972      // block, but beyond the last call instruction in its basic block. Handle2973      // this case conservatively.2974      LLVM_DEBUG(2975          dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def2976                 << " may be live into EH pad successors, keeping it.\n");2977      OtherV.mustKeepImplicitDef(*TRI, *OtherImpDef);2978    } else {2979      // We deferred clearing these lanes in case we needed to save them2980      OtherV.ValidLanes &= ~OtherV.WriteLanes;2981    }2982  }2983 2984  // Allow overlapping PHI values. Any real interference would show up in a2985  // predecessor, the PHI itself can't introduce any conflicts.2986  if (VNI->isPHIDef())2987    return CR_Replace;2988 2989  // Check for simple erasable conflicts.2990  if (DefMI->isImplicitDef())2991    return CR_Erase;2992 2993  // Include the non-conflict where DefMI is a coalescable copy that kills2994  // OtherVNI. We still want the copy erased and value numbers merged.2995  if (CP.isCoalescable(DefMI)) {2996    // Some of the lanes copied from OtherVNI may be undef, making them undef2997    // here too.2998    V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;2999    return CR_Erase;3000  }3001 3002  // This may not be a real conflict if DefMI simply kills Other and defines3003  // VNI.3004  if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def)3005    return CR_Keep;3006 3007  // Handle the case where VNI and OtherVNI can be proven to be identical:3008  //3009  //   %other = COPY %ext3010  //   %this  = COPY %ext <-- Erase this copy3011  //3012  if (DefMI->isFullCopy() && !CP.isPartial() &&3013      valuesIdentical(VNI, V.OtherVNI, Other)) {3014    V.Identical = true;3015    return CR_Erase;3016  }3017 3018  // The remaining checks apply to the lanes, which aren't tracked here.  This3019  // was already decided to be OK via the following CR_Replace condition.3020  // CR_Replace.3021  if (SubRangeJoin)3022    return CR_Replace;3023 3024  // If the lanes written by this instruction were all undef in OtherVNI, it is3025  // still safe to join the live ranges. This can't be done with a simple value3026  // mapping, though - OtherVNI will map to multiple values:3027  //3028  //   1 %dst:ssub0 = FOO                <-- OtherVNI3029  //   2 %src = BAR                      <-- VNI3030  //   3 %dst:ssub1 = COPY killed %src    <-- Eliminate this copy.3031  //   4 BAZ killed %dst3032  //   5 QUUX killed %src3033  //3034  // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace3035  // handles this complex value mapping.3036  if ((V.WriteLanes & OtherV.ValidLanes).none())3037    return CR_Replace;3038 3039  // If the other live range is killed by DefMI and the live ranges are still3040  // overlapping, it must be because we're looking at an early clobber def:3041  //3042  //   %dst<def,early-clobber> = ASM killed %src3043  //3044  // In this case, it is illegal to merge the two live ranges since the early3045  // clobber def would clobber %src before it was read.3046  if (OtherLRQ.isKill()) {3047    // This case where the def doesn't overlap the kill is handled above.3048    assert(VNI->def.isEarlyClobber() &&3049           "Only early clobber defs can overlap a kill");3050    return CR_Impossible;3051  }3052 3053  // VNI is clobbering live lanes in OtherVNI, but there is still the3054  // possibility that no instructions actually read the clobbered lanes.3055  // If we're clobbering all the lanes in OtherVNI, at least one must be read.3056  // Otherwise Other.RI wouldn't be live here.3057  if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes).none())3058    return CR_Impossible;3059 3060  if (TrackSubRegLiveness) {3061    auto &OtherLI = LIS->getInterval(Other.Reg);3062    // If OtherVNI does not have subranges, it means all the lanes of OtherVNI3063    // share the same live range, so we just need to check whether they have3064    // any conflict bit in their LaneMask.3065    if (!OtherLI.hasSubRanges()) {3066      LaneBitmask OtherMask = TRI->getSubRegIndexLaneMask(Other.SubIdx);3067      return (OtherMask & V.WriteLanes).none() ? CR_Replace : CR_Impossible;3068    }3069 3070    // If we are clobbering some active lanes of OtherVNI at VNI->def, it is3071    // impossible to resolve the conflict. Otherwise, we can just replace3072    // OtherVNI because of no real conflict.3073    for (LiveInterval::SubRange &OtherSR : OtherLI.subranges()) {3074      LaneBitmask OtherMask =3075          TRI->composeSubRegIndexLaneMask(Other.SubIdx, OtherSR.LaneMask);3076      if ((OtherMask & V.WriteLanes).none())3077        continue;3078 3079      auto OtherSRQ = OtherSR.Query(VNI->def);3080      if (OtherSRQ.valueIn() && OtherSRQ.endPoint() > VNI->def) {3081        // VNI is clobbering some lanes of OtherVNI, they have real conflict.3082        return CR_Impossible;3083      }3084    }3085 3086    // VNI is NOT clobbering any lane of OtherVNI, just replace OtherVNI.3087    return CR_Replace;3088  }3089 3090  // We need to verify that no instructions are reading the clobbered lanes.3091  // To save compile time, we'll only check that locally. Don't allow the3092  // tainted value to escape the basic block.3093  MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);3094  if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB))3095    return CR_Impossible;3096 3097  // There are still some things that could go wrong besides clobbered lanes3098  // being read, for example OtherVNI may be only partially redefined in MBB,3099  // and some clobbered lanes could escape the block. Save this analysis for3100  // resolveConflicts() when all values have been mapped. We need to know3101  // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute3102  // that now - the recursive analyzeValue() calls must go upwards in the3103  // dominator tree.3104  return CR_Unresolved;3105}3106 3107void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) {3108  Val &V = Vals[ValNo];3109  if (V.isAnalyzed()) {3110    // Recursion should always move up the dominator tree, so ValNo is not3111    // supposed to reappear before it has been assigned.3112    assert(Assignments[ValNo] != -1 && "Bad recursion?");3113    return;3114  }3115  switch ((V.Resolution = analyzeValue(ValNo, Other))) {3116  case CR_Erase:3117  case CR_Merge:3118    // Merge this ValNo into OtherVNI.3119    assert(V.OtherVNI && "OtherVNI not assigned, can't merge.");3120    assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion");3121    Assignments[ValNo] = Other.Assignments[V.OtherVNI->id];3122    LLVM_DEBUG(dbgs() << "\t\tmerge " << printReg(Reg) << ':' << ValNo << '@'3123                      << LR.getValNumInfo(ValNo)->def << " into "3124                      << printReg(Other.Reg) << ':' << V.OtherVNI->id << '@'3125                      << V.OtherVNI->def << " --> @"3126                      << NewVNInfo[Assignments[ValNo]]->def << '\n');3127    break;3128  case CR_Replace:3129  case CR_Unresolved: {3130    // The other value is going to be pruned if this join is successful.3131    assert(V.OtherVNI && "OtherVNI not assigned, can't prune");3132    Val &OtherV = Other.Vals[V.OtherVNI->id];3133    OtherV.Pruned = true;3134    [[fallthrough]];3135  }3136  default:3137    // This value number needs to go in the final joined live range.3138    Assignments[ValNo] = NewVNInfo.size();3139    NewVNInfo.push_back(LR.getValNumInfo(ValNo));3140    break;3141  }3142}3143 3144bool JoinVals::mapValues(JoinVals &Other) {3145  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {3146    computeAssignment(i, Other);3147    if (Vals[i].Resolution == CR_Impossible) {3148      LLVM_DEBUG(dbgs() << "\t\tinterference at " << printReg(Reg) << ':' << i3149                        << '@' << LR.getValNumInfo(i)->def << '\n');3150      return false;3151    }3152  }3153  return true;3154}3155 3156bool JoinVals::taintExtent(3157    unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,3158    SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent) {3159  VNInfo *VNI = LR.getValNumInfo(ValNo);3160  MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);3161  SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB);3162 3163  // Scan Other.LR from VNI.def to MBBEnd.3164  LiveInterval::iterator OtherI = Other.LR.find(VNI->def);3165  assert(OtherI != Other.LR.end() && "No conflict?");3166  do {3167    // OtherI is pointing to a tainted value. Abort the join if the tainted3168    // lanes escape the block.3169    SlotIndex End = OtherI->end;3170    if (End >= MBBEnd) {3171      LLVM_DEBUG(dbgs() << "\t\ttaints global " << printReg(Other.Reg) << ':'3172                        << OtherI->valno->id << '@' << OtherI->start << '\n');3173      return false;3174    }3175    LLVM_DEBUG(dbgs() << "\t\ttaints local " << printReg(Other.Reg) << ':'3176                      << OtherI->valno->id << '@' << OtherI->start << " to "3177                      << End << '\n');3178    // A dead def is not a problem.3179    if (End.isDead())3180      break;3181    TaintExtent.push_back(std::make_pair(End, TaintedLanes));3182 3183    // Check for another def in the MBB.3184    if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd)3185      break;3186 3187    // Lanes written by the new def are no longer tainted.3188    const Val &OV = Other.Vals[OtherI->valno->id];3189    TaintedLanes &= ~OV.WriteLanes;3190    if (!OV.RedefVNI)3191      break;3192  } while (TaintedLanes.any());3193  return true;3194}3195 3196bool JoinVals::usesLanes(const MachineInstr &MI, Register Reg, unsigned SubIdx,3197                         LaneBitmask Lanes) const {3198  if (MI.isDebugOrPseudoInstr())3199    return false;3200  for (const MachineOperand &MO : MI.all_uses()) {3201    if (MO.getReg() != Reg)3202      continue;3203    if (!MO.readsReg())3204      continue;3205    unsigned S = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());3206    if ((Lanes & TRI->getSubRegIndexLaneMask(S)).any())3207      return true;3208  }3209  return false;3210}3211 3212bool JoinVals::resolveConflicts(JoinVals &Other) {3213  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {3214    Val &V = Vals[i];3215    assert(V.Resolution != CR_Impossible && "Unresolvable conflict");3216    if (V.Resolution != CR_Unresolved)3217      continue;3218    LLVM_DEBUG(dbgs() << "\t\tconflict at " << printReg(Reg) << ':' << i << '@'3219                      << LR.getValNumInfo(i)->def << ' '3220                      << PrintLaneMask(LaneMask) << '\n');3221    if (SubRangeJoin)3222      return false;3223 3224    ++NumLaneConflicts;3225    assert(V.OtherVNI && "Inconsistent conflict resolution.");3226    VNInfo *VNI = LR.getValNumInfo(i);3227    const Val &OtherV = Other.Vals[V.OtherVNI->id];3228 3229    // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the3230    // join, those lanes will be tainted with a wrong value. Get the extent of3231    // the tainted lanes.3232    LaneBitmask TaintedLanes = V.WriteLanes & OtherV.ValidLanes;3233    SmallVector<std::pair<SlotIndex, LaneBitmask>, 8> TaintExtent;3234    if (!taintExtent(i, TaintedLanes, Other, TaintExtent))3235      // Tainted lanes would extend beyond the basic block.3236      return false;3237 3238    assert(!TaintExtent.empty() && "There should be at least one conflict.");3239 3240    // Now look at the instructions from VNI->def to TaintExtent (inclusive).3241    MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);3242    MachineBasicBlock::iterator MI = MBB->begin();3243    if (!VNI->isPHIDef()) {3244      MI = Indexes->getInstructionFromIndex(VNI->def);3245      if (!VNI->def.isEarlyClobber()) {3246        // No need to check the instruction defining VNI for reads.3247        ++MI;3248      }3249    }3250    assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) &&3251           "Interference ends on VNI->def. Should have been handled earlier");3252    MachineInstr *LastMI =3253        Indexes->getInstructionFromIndex(TaintExtent.front().first);3254    assert(LastMI && "Range must end at a proper instruction");3255    unsigned TaintNum = 0;3256    while (true) {3257      assert(MI != MBB->end() && "Bad LastMI");3258      if (usesLanes(*MI, Other.Reg, Other.SubIdx, TaintedLanes)) {3259        LLVM_DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI);3260        return false;3261      }3262      // LastMI is the last instruction to use the current value.3263      if (&*MI == LastMI) {3264        if (++TaintNum == TaintExtent.size())3265          break;3266        LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first);3267        assert(LastMI && "Range must end at a proper instruction");3268        TaintedLanes = TaintExtent[TaintNum].second;3269      }3270      ++MI;3271    }3272 3273    // The tainted lanes are unused.3274    V.Resolution = CR_Replace;3275    ++NumLaneResolves;3276  }3277  return true;3278}3279 3280bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) {3281  Val &V = Vals[ValNo];3282  if (V.Pruned || V.PrunedComputed)3283    return V.Pruned;3284 3285  if (V.Resolution != CR_Erase && V.Resolution != CR_Merge)3286    return V.Pruned;3287 3288  // Follow copies up the dominator tree and check if any intermediate value3289  // has been pruned.3290  V.PrunedComputed = true;3291  V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this);3292  return V.Pruned;3293}3294 3295void JoinVals::pruneValues(JoinVals &Other,3296                           SmallVectorImpl<SlotIndex> &EndPoints,3297                           bool changeInstrs) {3298  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {3299    SlotIndex Def = LR.getValNumInfo(i)->def;3300    switch (Vals[i].Resolution) {3301    case CR_Keep:3302      break;3303    case CR_Replace: {3304      // This value takes precedence over the value in Other.LR.3305      LIS->pruneValue(Other.LR, Def, &EndPoints);3306      // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF3307      // instructions are only inserted to provide a live-out value for PHI3308      // predecessors, so the instruction should simply go away once its value3309      // has been replaced.3310      Val &OtherV = Other.Vals[Vals[i].OtherVNI->id];3311      bool EraseImpDef =3312          OtherV.ErasableImplicitDef && OtherV.Resolution == CR_Keep;3313      if (!Def.isBlock()) {3314        if (changeInstrs) {3315          // Remove <def,read-undef> flags. This def is now a partial redef.3316          // Also remove dead flags since the joined live range will3317          // continue past this instruction.3318          for (MachineOperand &MO :3319               Indexes->getInstructionFromIndex(Def)->all_defs()) {3320            if (MO.getReg() == Reg) {3321              if (MO.getSubReg() != 0 && MO.isUndef() && !EraseImpDef)3322                MO.setIsUndef(false);3323              MO.setIsDead(false);3324            }3325          }3326        }3327        // This value will reach instructions below, but we need to make sure3328        // the live range also reaches the instruction at Def.3329        if (!EraseImpDef)3330          EndPoints.push_back(Def);3331      }3332      LLVM_DEBUG(dbgs() << "\t\tpruned " << printReg(Other.Reg) << " at " << Def3333                        << ": " << Other.LR << '\n');3334      break;3335    }3336    case CR_Erase:3337    case CR_Merge:3338      if (isPrunedValue(i, Other)) {3339        // This value is ultimately a copy of a pruned value in LR or Other.LR.3340        // We can no longer trust the value mapping computed by3341        // computeAssignment(), the value that was originally copied could have3342        // been replaced.3343        LIS->pruneValue(LR, Def, &EndPoints);3344        LLVM_DEBUG(dbgs() << "\t\tpruned all of " << printReg(Reg) << " at "3345                          << Def << ": " << LR << '\n');3346      }3347      break;3348    case CR_Unresolved:3349    case CR_Impossible:3350      llvm_unreachable("Unresolved conflicts");3351    }3352  }3353}3354 3355// Check if the segment consists of a copied live-through value (i.e. the copy3356// in the block only extended the liveness, of an undef value which we may need3357// to handle).3358static bool isLiveThrough(const LiveQueryResult Q) {3359  return Q.valueIn() && Q.valueIn()->isPHIDef() && Q.valueIn() == Q.valueOut();3360}3361 3362/// Consider the following situation when coalescing the copy between3363/// %31 and %45 at 800. (The vertical lines represent live range segments.)3364///3365///                              Main range         Subrange 0004 (sub2)3366///                              %31    %45           %31    %453367///  544    %45 = COPY %28               +                    +3368///                                      | v1                 | v13369///  560B bb.1:                          +                    +3370///  624        = %45.sub2               | v2                 | v23371///  800    %31 = COPY %45        +      +             +      +3372///                               | v0                 | v03373///  816    %31.sub1 = ...        +                    |3374///  880    %30 = COPY %31        | v1                 +3375///  928    %45 = COPY %30        |      +                    +3376///                               |      | v0                 | v0  <--+3377///  992B   ; backedge -> bb.1    |      +                    +        |3378/// 1040        = %31.sub0        +                                    |3379///                                                 This value must remain3380///                                                 live-out!3381///3382/// Assuming that %31 is coalesced into %45, the copy at 928 becomes3383/// redundant, since it copies the value from %45 back into it. The3384/// conflict resolution for the main range determines that %45.v0 is3385/// to be erased, which is ok since %31.v1 is identical to it.3386/// The problem happens with the subrange for sub2: it has to be live3387/// on exit from the block, but since 928 was actually a point of3388/// definition of %45.sub2, %45.sub2 was not live immediately prior3389/// to that definition. As a result, when 928 was erased, the value v03390/// for %45.sub2 was pruned in pruneSubRegValues. Consequently, an3391/// IMPLICIT_DEF was inserted as a "backedge" definition for %45.sub2,3392/// providing an incorrect value to the use at 624.3393///3394/// Since the main-range values %31.v1 and %45.v0 were proved to be3395/// identical, the corresponding values in subranges must also be the3396/// same. A redundant copy is removed because it's not needed, and not3397/// because it copied an undefined value, so any liveness that originated3398/// from that copy cannot disappear. When pruning a value that started3399/// at the removed copy, the corresponding identical value must be3400/// extended to replace it.3401void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) {3402  // Look for values being erased.3403  bool DidPrune = false;3404  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {3405    Val &V = Vals[i];3406    // We should trigger in all cases in which eraseInstrs() does something.3407    // match what eraseInstrs() is doing, print a message so3408    if (V.Resolution != CR_Erase &&3409        (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned))3410      continue;3411 3412    // Check subranges at the point where the copy will be removed.3413    SlotIndex Def = LR.getValNumInfo(i)->def;3414    SlotIndex OtherDef;3415    if (V.Identical)3416      OtherDef = V.OtherVNI->def;3417 3418    // Print message so mismatches with eraseInstrs() can be diagnosed.3419    LLVM_DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def3420                      << '\n');3421    for (LiveInterval::SubRange &S : LI.subranges()) {3422      LiveQueryResult Q = S.Query(Def);3423 3424      // If a subrange starts at the copy then an undefined value has been3425      // copied and we must remove that subrange value as well.3426      VNInfo *ValueOut = Q.valueOutOrDead();3427      if (ValueOut != nullptr &&3428          (Q.valueIn() == nullptr ||3429           (V.Identical && V.Resolution == CR_Erase && ValueOut->def == Def))) {3430        LLVM_DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask)3431                          << " at " << Def << "\n");3432        SmallVector<SlotIndex, 8> EndPoints;3433        LIS->pruneValue(S, Def, &EndPoints);3434        DidPrune = true;3435        // Mark value number as unused.3436        ValueOut->markUnused();3437 3438        if (V.Identical && S.Query(OtherDef).valueOutOrDead()) {3439          // If V is identical to V.OtherVNI (and S was live at OtherDef),3440          // then we can't simply prune V from S. V needs to be replaced3441          // with V.OtherVNI.3442          LIS->extendToIndices(S, EndPoints);3443        }3444 3445        // We may need to eliminate the subrange if the copy introduced a live3446        // out undef value.3447        if (ValueOut->isPHIDef())3448          ShrinkMask |= S.LaneMask;3449        continue;3450      }3451 3452      // If a subrange ends at the copy, then a value was copied but only3453      // partially used later. Shrink the subregister range appropriately.3454      //3455      // Ultimately this calls shrinkToUses, so assuming ShrinkMask is3456      // conservatively correct.3457      if ((Q.valueIn() != nullptr && Q.valueOut() == nullptr) ||3458          (V.Resolution == CR_Erase && isLiveThrough(Q))) {3459        LLVM_DEBUG(dbgs() << "\t\tDead uses at sublane "3460                          << PrintLaneMask(S.LaneMask) << " at " << Def3461                          << "\n");3462        ShrinkMask |= S.LaneMask;3463      }3464    }3465  }3466  if (DidPrune)3467    LI.removeEmptySubRanges();3468}3469 3470/// Check if any of the subranges of @p LI contain a definition at @p Def.3471static bool isDefInSubRange(LiveInterval &LI, SlotIndex Def) {3472  for (LiveInterval::SubRange &SR : LI.subranges()) {3473    if (VNInfo *VNI = SR.Query(Def).valueOutOrDead())3474      if (VNI->def == Def)3475        return true;3476  }3477  return false;3478}3479 3480void JoinVals::pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange) {3481  assert(&static_cast<LiveRange &>(LI) == &LR);3482 3483  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {3484    if (Vals[i].Resolution != CR_Keep)3485      continue;3486    VNInfo *VNI = LR.getValNumInfo(i);3487    if (VNI->isUnused() || VNI->isPHIDef() || isDefInSubRange(LI, VNI->def))3488      continue;3489    Vals[i].Pruned = true;3490    ShrinkMainRange = true;3491  }3492}3493 3494void JoinVals::removeImplicitDefs() {3495  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {3496    Val &V = Vals[i];3497    if (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned)3498      continue;3499 3500    VNInfo *VNI = LR.getValNumInfo(i);3501    VNI->markUnused();3502    LR.removeValNo(VNI);3503  }3504}3505 3506void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr *> &ErasedInstrs,3507                           SmallVectorImpl<Register> &ShrinkRegs,3508                           LiveInterval *LI) {3509  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {3510    // Get the def location before markUnused() below invalidates it.3511    VNInfo *VNI = LR.getValNumInfo(i);3512    SlotIndex Def = VNI->def;3513    switch (Vals[i].Resolution) {3514    case CR_Keep: {3515      // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any3516      // longer. The IMPLICIT_DEF instructions are only inserted by3517      // PHIElimination to guarantee that all PHI predecessors have a value.3518      if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)3519        break;3520      // Remove value number i from LR.3521      // For intervals with subranges, removing a segment from the main range3522      // may require extending the previous segment: for each definition of3523      // a subregister, there will be a corresponding def in the main range.3524      // That def may fall in the middle of a segment from another subrange.3525      // In such cases, removing this def from the main range must be3526      // complemented by extending the main range to account for the liveness3527      // of the other subrange.3528      // The new end point of the main range segment to be extended.3529      SlotIndex NewEnd;3530      if (LI != nullptr) {3531        LiveRange::iterator I = LR.FindSegmentContaining(Def);3532        assert(I != LR.end());3533        // Do not extend beyond the end of the segment being removed.3534        // The segment may have been pruned in preparation for joining3535        // live ranges.3536        NewEnd = I->end;3537      }3538 3539      LR.removeValNo(VNI);3540      // Note that this VNInfo is reused and still referenced in NewVNInfo,3541      // make it appear like an unused value number.3542      VNI->markUnused();3543 3544      if (LI != nullptr && LI->hasSubRanges()) {3545        assert(static_cast<LiveRange *>(LI) == &LR);3546        // Determine the end point based on the subrange information:3547        // minimum of (earliest def of next segment,3548        //             latest end point of containing segment)3549        SlotIndex ED, LE;3550        for (LiveInterval::SubRange &SR : LI->subranges()) {3551          LiveRange::iterator I = SR.find(Def);3552          if (I == SR.end())3553            continue;3554          if (I->start > Def)3555            ED = ED.isValid() ? std::min(ED, I->start) : I->start;3556          else3557            LE = LE.isValid() ? std::max(LE, I->end) : I->end;3558        }3559        if (LE.isValid())3560          NewEnd = std::min(NewEnd, LE);3561        if (ED.isValid())3562          NewEnd = std::min(NewEnd, ED);3563 3564        // We only want to do the extension if there was a subrange that3565        // was live across Def.3566        if (LE.isValid()) {3567          LiveRange::iterator S = LR.find(Def);3568          if (S != LR.begin())3569            std::prev(S)->end = NewEnd;3570        }3571      }3572      LLVM_DEBUG({3573        dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n';3574        if (LI != nullptr)3575          dbgs() << "\t\t  LHS = " << *LI << '\n';3576      });3577      [[fallthrough]];3578    }3579 3580    case CR_Erase: {3581      MachineInstr *MI = Indexes->getInstructionFromIndex(Def);3582      assert(MI && "No instruction to erase");3583      if (MI->isCopy()) {3584        Register Reg = MI->getOperand(1).getReg();3585        if (Reg.isVirtual() && Reg != CP.getSrcReg() && Reg != CP.getDstReg())3586          ShrinkRegs.push_back(Reg);3587      }3588      ErasedInstrs.insert(MI);3589      LLVM_DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI);3590      LIS->RemoveMachineInstrFromMaps(*MI);3591      MI->eraseFromParent();3592      break;3593    }3594    default:3595      break;3596    }3597  }3598}3599 3600void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,3601                                         LaneBitmask LaneMask,3602                                         const CoalescerPair &CP) {3603  SmallVector<VNInfo *, 16> NewVNInfo;3604  JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask, NewVNInfo,3605                   CP, LIS, TRI, true, true);3606  JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask, NewVNInfo,3607                   CP, LIS, TRI, true, true);3608 3609  // Compute NewVNInfo and resolve conflicts (see also joinVirtRegs())3610  // We should be able to resolve all conflicts here as we could successfully do3611  // it on the mainrange already. There is however a problem when multiple3612  // ranges get mapped to the "overflow" lane mask bit which creates unexpected3613  // interferences.3614  if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {3615    // We already determined that it is legal to merge the intervals, so this3616    // should never fail.3617    llvm_unreachable("*** Couldn't join subrange!\n");3618  }3619  if (!LHSVals.resolveConflicts(RHSVals) ||3620      !RHSVals.resolveConflicts(LHSVals)) {3621    // We already determined that it is legal to merge the intervals, so this3622    // should never fail.3623    llvm_unreachable("*** Couldn't join subrange!\n");3624  }3625 3626  // The merging algorithm in LiveInterval::join() can't handle conflicting3627  // value mappings, so we need to remove any live ranges that overlap a3628  // CR_Replace resolution. Collect a set of end points that can be used to3629  // restore the live range after joining.3630  SmallVector<SlotIndex, 8> EndPoints;3631  LHSVals.pruneValues(RHSVals, EndPoints, false);3632  RHSVals.pruneValues(LHSVals, EndPoints, false);3633 3634  LHSVals.removeImplicitDefs();3635  RHSVals.removeImplicitDefs();3636 3637  assert(LRange.verify() && RRange.verify());3638 3639  // Join RRange into LHS.3640  LRange.join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),3641              NewVNInfo);3642 3643  LLVM_DEBUG(dbgs() << "\t\tjoined lanes: " << PrintLaneMask(LaneMask) << ' '3644                    << LRange << "\n");3645  if (EndPoints.empty())3646    return;3647 3648  // Recompute the parts of the live range we had to remove because of3649  // CR_Replace conflicts.3650  LLVM_DEBUG({3651    dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";3652    for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {3653      dbgs() << EndPoints[i];3654      if (i != n - 1)3655        dbgs() << ',';3656    }3657    dbgs() << ":  " << LRange << '\n';3658  });3659  LIS->extendToIndices(LRange, EndPoints);3660}3661 3662void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,3663                                          const LiveRange &ToMerge,3664                                          LaneBitmask LaneMask,3665                                          CoalescerPair &CP,3666                                          unsigned ComposeSubRegIdx) {3667  BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();3668  LI.refineSubRanges(3669      Allocator, LaneMask,3670      [this, &Allocator, &ToMerge, &CP](LiveInterval::SubRange &SR) {3671        if (SR.empty()) {3672          SR.assign(ToMerge, Allocator);3673        } else {3674          // joinSubRegRange() destroys the merged range, so we need a copy.3675          LiveRange RangeCopy(ToMerge, Allocator);3676          joinSubRegRanges(SR, RangeCopy, SR.LaneMask, CP);3677        }3678      },3679      *LIS->getSlotIndexes(), *TRI, ComposeSubRegIdx);3680}3681 3682bool RegisterCoalescer::isHighCostLiveInterval(LiveInterval &LI) {3683  if (LI.valnos.size() < LargeIntervalSizeThreshold)3684    return false;3685  auto &Counter = LargeLIVisitCounter[LI.reg()];3686  if (Counter < LargeIntervalFreqThreshold) {3687    Counter++;3688    return false;3689  }3690  return true;3691}3692 3693bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {3694  SmallVector<VNInfo *, 16> NewVNInfo;3695  LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());3696  LiveInterval &LHS = LIS->getInterval(CP.getDstReg());3697  bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC());3698  JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), LaneBitmask::getNone(),3699                   NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);3700  JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), LaneBitmask::getNone(),3701                   NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);3702 3703  LLVM_DEBUG(dbgs() << "\t\tRHS = " << RHS << "\n\t\tLHS = " << LHS << '\n');3704 3705  if (isHighCostLiveInterval(LHS) || isHighCostLiveInterval(RHS))3706    return false;3707 3708  // First compute NewVNInfo and the simple value mappings.3709  // Detect impossible conflicts early.3710  if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))3711    return false;3712 3713  // Some conflicts can only be resolved after all values have been mapped.3714  if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))3715    return false;3716 3717  // All clear, the live ranges can be merged.3718  if (RHS.hasSubRanges() || LHS.hasSubRanges()) {3719    BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();3720 3721    // Transform lanemasks from the LHS to masks in the coalesced register and3722    // create initial subranges if necessary.3723    unsigned DstIdx = CP.getDstIdx();3724    if (!LHS.hasSubRanges()) {3725      LaneBitmask Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask()3726                                     : TRI->getSubRegIndexLaneMask(DstIdx);3727      // LHS must support subregs or we wouldn't be in this codepath.3728      assert(Mask.any());3729      LHS.createSubRangeFrom(Allocator, Mask, LHS);3730    } else if (DstIdx != 0) {3731      // Transform LHS lanemasks to new register class if necessary.3732      for (LiveInterval::SubRange &R : LHS.subranges()) {3733        LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask);3734        R.LaneMask = Mask;3735      }3736    }3737    LLVM_DEBUG(dbgs() << "\t\tLHST = " << printReg(CP.getDstReg()) << ' ' << LHS3738                      << '\n');3739 3740    // Determine lanemasks of RHS in the coalesced register and merge subranges.3741    unsigned SrcIdx = CP.getSrcIdx();3742    if (!RHS.hasSubRanges()) {3743      LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()3744                                     : TRI->getSubRegIndexLaneMask(SrcIdx);3745      mergeSubRangeInto(LHS, RHS, Mask, CP, DstIdx);3746    } else {3747      // Pair up subranges and merge.3748      for (LiveInterval::SubRange &R : RHS.subranges()) {3749        LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);3750        mergeSubRangeInto(LHS, R, Mask, CP, DstIdx);3751      }3752    }3753    LLVM_DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n");3754 3755    // Pruning implicit defs from subranges may result in the main range3756    // having stale segments.3757    LHSVals.pruneMainSegments(LHS, ShrinkMainRange);3758 3759    LHSVals.pruneSubRegValues(LHS, ShrinkMask);3760    RHSVals.pruneSubRegValues(LHS, ShrinkMask);3761  } else if (TrackSubRegLiveness && !CP.getDstIdx() && CP.getSrcIdx()) {3762    LHS.createSubRangeFrom(LIS->getVNInfoAllocator(),3763                           CP.getNewRC()->getLaneMask(), LHS);3764    mergeSubRangeInto(LHS, RHS, TRI->getSubRegIndexLaneMask(CP.getSrcIdx()), CP,3765                      CP.getDstIdx());3766    LHSVals.pruneMainSegments(LHS, ShrinkMainRange);3767    LHSVals.pruneSubRegValues(LHS, ShrinkMask);3768  }3769 3770  // The merging algorithm in LiveInterval::join() can't handle conflicting3771  // value mappings, so we need to remove any live ranges that overlap a3772  // CR_Replace resolution. Collect a set of end points that can be used to3773  // restore the live range after joining.3774  SmallVector<SlotIndex, 8> EndPoints;3775  LHSVals.pruneValues(RHSVals, EndPoints, true);3776  RHSVals.pruneValues(LHSVals, EndPoints, true);3777 3778  // Erase COPY and IMPLICIT_DEF instructions. This may cause some external3779  // registers to require trimming.3780  SmallVector<Register, 8> ShrinkRegs;3781  LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &LHS);3782  RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);3783  while (!ShrinkRegs.empty())3784    shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));3785 3786  // Scan and mark undef any DBG_VALUEs that would refer to a different value.3787  checkMergingChangesDbgValues(CP, LHS, LHSVals, RHS, RHSVals);3788 3789  // If the RHS covers any PHI locations that were tracked for debug-info, we3790  // must update tracking information to reflect the join.3791  auto RegIt = RegToPHIIdx.find(CP.getSrcReg());3792  if (RegIt != RegToPHIIdx.end()) {3793    // Iterate over all the debug instruction numbers assigned this register.3794    for (unsigned InstID : RegIt->second) {3795      auto PHIIt = PHIValToPos.find(InstID);3796      assert(PHIIt != PHIValToPos.end());3797      const SlotIndex &SI = PHIIt->second.SI;3798 3799      // Does the RHS cover the position of this PHI?3800      auto LII = RHS.find(SI);3801      if (LII == RHS.end() || LII->start > SI)3802        continue;3803 3804      // Accept two kinds of subregister movement:3805      //  * When we merge from one register class into a larger register:3806      //        %1:gr16 = some-inst3807      //                ->3808      //        %2:gr32.sub_16bit = some-inst3809      //  * When the PHI is already in a subregister, and the larger class3810      //    is coalesced:3811      //        %2:gr32.sub_16bit = some-inst3812      //        %3:gr32 = COPY %23813      //                ->3814      //        %3:gr32.sub_16bit = some-inst3815      // Test for subregister move:3816      if (CP.getSrcIdx() != 0 || CP.getDstIdx() != 0)3817        // If we're moving between different subregisters, ignore this join.3818        // The PHI will not get a location, dropping variable locations.3819        if (PHIIt->second.SubReg && PHIIt->second.SubReg != CP.getSrcIdx())3820          continue;3821 3822      // Update our tracking of where the PHI is.3823      PHIIt->second.Reg = CP.getDstReg();3824 3825      // If we merge into a sub-register of a larger class (test above),3826      // update SubReg.3827      if (CP.getSrcIdx() != 0)3828        PHIIt->second.SubReg = CP.getSrcIdx();3829    }3830 3831    // Rebuild the register index in RegToPHIIdx to account for PHIs tracking3832    // different VRegs now. Copy old collection of debug instruction numbers and3833    // erase the old one:3834    auto InstrNums = RegIt->second;3835    RegToPHIIdx.erase(RegIt);3836 3837    // There might already be PHIs being tracked in the destination VReg. Insert3838    // into an existing tracking collection, or insert a new one.3839    RegIt = RegToPHIIdx.find(CP.getDstReg());3840    if (RegIt != RegToPHIIdx.end())3841      llvm::append_range(RegIt->second, InstrNums);3842    else3843      RegToPHIIdx.insert({CP.getDstReg(), InstrNums});3844  }3845 3846  // Join RHS into LHS.3847  LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);3848 3849  // Kill flags are going to be wrong if the live ranges were overlapping.3850  // Eventually, we should simply clear all kill flags when computing live3851  // ranges. They are reinserted after register allocation.3852  MRI->clearKillFlags(LHS.reg());3853  MRI->clearKillFlags(RHS.reg());3854 3855  if (!EndPoints.empty()) {3856    // Recompute the parts of the live range we had to remove because of3857    // CR_Replace conflicts.3858    LLVM_DEBUG({3859      dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";3860      for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {3861        dbgs() << EndPoints[i];3862        if (i != n - 1)3863          dbgs() << ',';3864      }3865      dbgs() << ":  " << LHS << '\n';3866    });3867    LIS->extendToIndices((LiveRange &)LHS, EndPoints);3868  }3869 3870  return true;3871}3872 3873bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {3874  return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);3875}3876 3877void RegisterCoalescer::buildVRegToDbgValueMap(MachineFunction &MF) {3878  const SlotIndexes &Slots = *LIS->getSlotIndexes();3879  SmallVector<MachineInstr *, 8> ToInsert;3880 3881  // After collecting a block of DBG_VALUEs into ToInsert, enter them into the3882  // vreg => DbgValueLoc map.3883  auto CloseNewDVRange = [this, &ToInsert](SlotIndex Slot) {3884    for (auto *X : ToInsert) {3885      for (const auto &Op : X->debug_operands()) {3886        if (Op.isReg() && Op.getReg().isVirtual())3887          DbgVRegToValues[Op.getReg()].push_back({Slot, X});3888      }3889    }3890 3891    ToInsert.clear();3892  };3893 3894  // Iterate over all instructions, collecting them into the ToInsert vector.3895  // Once a non-debug instruction is found, record the slot index of the3896  // collected DBG_VALUEs.3897  for (auto &MBB : MF) {3898    SlotIndex CurrentSlot = Slots.getMBBStartIdx(&MBB);3899 3900    for (auto &MI : MBB) {3901      if (MI.isDebugValue()) {3902        if (any_of(MI.debug_operands(), [](const MachineOperand &MO) {3903              return MO.isReg() && MO.getReg().isVirtual();3904            }))3905          ToInsert.push_back(&MI);3906      } else if (!MI.isDebugOrPseudoInstr()) {3907        CurrentSlot = Slots.getInstructionIndex(MI);3908        CloseNewDVRange(CurrentSlot);3909      }3910    }3911 3912    // Close range of DBG_VALUEs at the end of blocks.3913    CloseNewDVRange(Slots.getMBBEndIdx(&MBB));3914  }3915 3916  // Sort all DBG_VALUEs we've seen by slot number.3917  for (auto &Pair : DbgVRegToValues)3918    llvm::sort(Pair.second);3919}3920 3921void RegisterCoalescer::checkMergingChangesDbgValues(CoalescerPair &CP,3922                                                     LiveRange &LHS,3923                                                     JoinVals &LHSVals,3924                                                     LiveRange &RHS,3925                                                     JoinVals &RHSVals) {3926  auto ScanForDstReg = [&](Register Reg) {3927    checkMergingChangesDbgValuesImpl(Reg, RHS, LHS, LHSVals);3928  };3929 3930  auto ScanForSrcReg = [&](Register Reg) {3931    checkMergingChangesDbgValuesImpl(Reg, LHS, RHS, RHSVals);3932  };3933 3934  // Scan for unsound updates of both the source and destination register.3935  ScanForSrcReg(CP.getSrcReg());3936  ScanForDstReg(CP.getDstReg());3937}3938 3939void RegisterCoalescer::checkMergingChangesDbgValuesImpl(Register Reg,3940                                                         LiveRange &OtherLR,3941                                                         LiveRange &RegLR,3942                                                         JoinVals &RegVals) {3943  // Are there any DBG_VALUEs to examine?3944  auto VRegMapIt = DbgVRegToValues.find(Reg);3945  if (VRegMapIt == DbgVRegToValues.end())3946    return;3947 3948  auto &DbgValueSet = VRegMapIt->second;3949  auto DbgValueSetIt = DbgValueSet.begin();3950  auto SegmentIt = OtherLR.begin();3951 3952  bool LastUndefResult = false;3953  SlotIndex LastUndefIdx;3954 3955  // If the "Other" register is live at a slot Idx, test whether Reg can3956  // safely be merged with it, or should be marked undef.3957  auto ShouldUndef = [&RegVals, &RegLR, &LastUndefResult,3958                      &LastUndefIdx](SlotIndex Idx) -> bool {3959    // Our worst-case performance typically happens with asan, causing very3960    // many DBG_VALUEs of the same location. Cache a copy of the most recent3961    // result for this edge-case.3962    if (LastUndefIdx == Idx)3963      return LastUndefResult;3964 3965    // If the other range was live, and Reg's was not, the register coalescer3966    // will not have tried to resolve any conflicts. We don't know whether3967    // the DBG_VALUE will refer to the same value number, so it must be made3968    // undef.3969    auto OtherIt = RegLR.find(Idx);3970    if (OtherIt == RegLR.end())3971      return true;3972 3973    // Both the registers were live: examine the conflict resolution record for3974    // the value number Reg refers to. CR_Keep meant that this value number3975    // "won" and the merged register definitely refers to that value. CR_Erase3976    // means the value number was a redundant copy of the other value, which3977    // was coalesced and Reg deleted. It's safe to refer to the other register3978    // (which will be the source of the copy).3979    auto Resolution = RegVals.getResolution(OtherIt->valno->id);3980    LastUndefResult =3981        Resolution != JoinVals::CR_Keep && Resolution != JoinVals::CR_Erase;3982    LastUndefIdx = Idx;3983    return LastUndefResult;3984  };3985 3986  // Iterate over both the live-range of the "Other" register, and the set of3987  // DBG_VALUEs for Reg at the same time. Advance whichever one has the lowest3988  // slot index. This relies on the DbgValueSet being ordered.3989  while (DbgValueSetIt != DbgValueSet.end() && SegmentIt != OtherLR.end()) {3990    if (DbgValueSetIt->first < SegmentIt->end) {3991      // "Other" is live and there is a DBG_VALUE of Reg: test if we should3992      // set it undef.3993      if (DbgValueSetIt->first >= SegmentIt->start) {3994        bool HasReg = DbgValueSetIt->second->hasDebugOperandForReg(Reg);3995        bool ShouldUndefReg = ShouldUndef(DbgValueSetIt->first);3996        if (HasReg && ShouldUndefReg) {3997          // Mark undef, erase record of this DBG_VALUE to avoid revisiting.3998          DbgValueSetIt->second->setDebugValueUndef();3999          continue;4000        }4001      }4002      ++DbgValueSetIt;4003    } else {4004      ++SegmentIt;4005    }4006  }4007}4008 4009namespace {4010 4011/// Information concerning MBB coalescing priority.4012struct MBBPriorityInfo {4013  MachineBasicBlock *MBB;4014  unsigned Depth;4015  bool IsSplit;4016 4017  MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit)4018      : MBB(mbb), Depth(depth), IsSplit(issplit) {}4019};4020 4021} // end anonymous namespace4022 4023/// C-style comparator that sorts first based on the loop depth of the basic4024/// block (the unsigned), and then on the MBB number.4025///4026/// EnableGlobalCopies assumes that the primary sort key is loop depth.4027static int compareMBBPriority(const MBBPriorityInfo *LHS,4028                              const MBBPriorityInfo *RHS) {4029  // Deeper loops first4030  if (LHS->Depth != RHS->Depth)4031    return LHS->Depth > RHS->Depth ? -1 : 1;4032 4033  // Try to unsplit critical edges next.4034  if (LHS->IsSplit != RHS->IsSplit)4035    return LHS->IsSplit ? -1 : 1;4036 4037  // Prefer blocks that are more connected in the CFG. This takes care of4038  // the most difficult copies first while intervals are short.4039  unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size();4040  unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size();4041  if (cl != cr)4042    return cl > cr ? -1 : 1;4043 4044  // As a last resort, sort by block number.4045  return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1;4046}4047 4048/// \returns true if the given copy uses or defines a local live range.4049static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) {4050  if (!Copy->isCopy())4051    return false;4052 4053  if (Copy->getOperand(1).isUndef())4054    return false;4055 4056  Register SrcReg = Copy->getOperand(1).getReg();4057  Register DstReg = Copy->getOperand(0).getReg();4058  if (SrcReg.isPhysical() || DstReg.isPhysical())4059    return false;4060 4061  return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg)) ||4062         LIS->intervalIsInOneMBB(LIS->getInterval(DstReg));4063}4064 4065void RegisterCoalescer::lateLiveIntervalUpdate() {4066  for (Register reg : ToBeUpdated) {4067    if (!LIS->hasInterval(reg))4068      continue;4069    LiveInterval &LI = LIS->getInterval(reg);4070    shrinkToUses(&LI, &DeadDefs);4071    if (!DeadDefs.empty())4072      eliminateDeadDefs();4073  }4074  ToBeUpdated.clear();4075}4076 4077bool RegisterCoalescer::copyCoalesceWorkList(4078    MutableArrayRef<MachineInstr *> CurrList) {4079  bool Progress = false;4080  SmallPtrSet<MachineInstr *, 4> CurrentErasedInstrs;4081  for (MachineInstr *&MI : CurrList) {4082    if (!MI)4083      continue;4084    // Skip instruction pointers that have already been erased, for example by4085    // dead code elimination.4086    if (ErasedInstrs.count(MI) || CurrentErasedInstrs.count(MI)) {4087      MI = nullptr;4088      continue;4089    }4090    bool Again = false;4091    bool Success = joinCopy(MI, Again, CurrentErasedInstrs);4092    Progress |= Success;4093    if (Success || !Again)4094      MI = nullptr;4095  }4096  // Clear instructions not recorded in `ErasedInstrs` but erased.4097  if (!CurrentErasedInstrs.empty()) {4098    for (MachineInstr *&MI : CurrList) {4099      if (MI && CurrentErasedInstrs.count(MI))4100        MI = nullptr;4101    }4102    for (MachineInstr *&MI : WorkList) {4103      if (MI && CurrentErasedInstrs.count(MI))4104        MI = nullptr;4105    }4106  }4107  return Progress;4108}4109 4110/// Check if DstReg is a terminal node.4111/// I.e., it does not have any affinity other than \p Copy.4112static bool isTerminalReg(Register DstReg, const MachineInstr &Copy,4113                          const MachineRegisterInfo *MRI) {4114  assert(Copy.isCopyLike());4115  // Check if the destination of this copy as any other affinity.4116  for (const MachineInstr &MI : MRI->reg_nodbg_instructions(DstReg))4117    if (&MI != &Copy && MI.isCopyLike())4118      return false;4119  return true;4120}4121 4122bool RegisterCoalescer::applyTerminalRule(const MachineInstr &Copy) const {4123  assert(Copy.isCopyLike());4124  if (!UseTerminalRule)4125    return false;4126  Register SrcReg, DstReg;4127  unsigned SrcSubReg = 0, DstSubReg = 0;4128  if (!isMoveInstr(*TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg))4129    return false;4130  // Check if the destination of this copy has any other affinity.4131  if (DstReg.isPhysical() ||4132      // If SrcReg is a physical register, the copy won't be coalesced.4133      // Ignoring it may have other side effect (like missing4134      // rematerialization). So keep it.4135      SrcReg.isPhysical() || !isTerminalReg(DstReg, Copy, MRI))4136    return false;4137 4138  // DstReg is a terminal node. Check if it interferes with any other4139  // copy involving SrcReg.4140  const MachineBasicBlock *OrigBB = Copy.getParent();4141  const LiveInterval &DstLI = LIS->getInterval(DstReg);4142  for (const MachineInstr &MI : MRI->reg_nodbg_instructions(SrcReg)) {4143    // Technically we should check if the weight of the new copy is4144    // interesting compared to the other one and update the weight4145    // of the copies accordingly. However, this would only work if4146    // we would gather all the copies first then coalesce, whereas4147    // right now we interleave both actions.4148    // For now, just consider the copies that are in the same block.4149    if (&MI == &Copy || !MI.isCopyLike() || MI.getParent() != OrigBB)4150      continue;4151    Register OtherSrcReg, OtherReg;4152    unsigned OtherSrcSubReg = 0, OtherSubReg = 0;4153    if (!isMoveInstr(*TRI, &MI, OtherSrcReg, OtherReg, OtherSrcSubReg,4154                     OtherSubReg))4155      return false;4156    if (OtherReg == SrcReg)4157      OtherReg = OtherSrcReg;4158    // Check if OtherReg is a non-terminal.4159    if (OtherReg.isPhysical() || isTerminalReg(OtherReg, MI, MRI))4160      continue;4161    // Check that OtherReg interfere with DstReg.4162    if (LIS->getInterval(OtherReg).overlaps(DstLI)) {4163      LLVM_DEBUG(dbgs() << "Apply terminal rule for: " << printReg(DstReg)4164                        << '\n');4165      return true;4166    }4167  }4168  return false;4169}4170 4171void RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) {4172  LLVM_DEBUG(dbgs() << MBB->getName() << ":\n");4173 4174  // Collect all copy-like instructions in MBB. Don't start coalescing anything4175  // yet, it might invalidate the iterator.4176  const unsigned PrevSize = WorkList.size();4177  if (JoinGlobalCopies) {4178    SmallVector<MachineInstr *, 2> LocalTerminals;4179    SmallVector<MachineInstr *, 2> GlobalTerminals;4180    // Coalesce copies top-down to propagate coalescing and rematerialization4181    // forward.4182    for (MachineInstr &MI : *MBB) {4183      if (!MI.isCopyLike())4184        continue;4185      bool ApplyTerminalRule = applyTerminalRule(MI);4186      if (isLocalCopy(&MI, LIS)) {4187        if (ApplyTerminalRule)4188          LocalTerminals.push_back(&MI);4189        else4190          LocalWorkList.push_back(&MI);4191      } else {4192        if (ApplyTerminalRule)4193          GlobalTerminals.push_back(&MI);4194        else4195          WorkList.push_back(&MI);4196      }4197    }4198    // Append the copies evicted by the terminal rule at the end of the list.4199    LocalWorkList.append(LocalTerminals.begin(), LocalTerminals.end());4200    WorkList.append(GlobalTerminals.begin(), GlobalTerminals.end());4201  } else {4202    SmallVector<MachineInstr *, 2> Terminals;4203    // Coalesce copies top-down to propagate coalescing and rematerialization4204    // forward.4205    for (MachineInstr &MII : *MBB)4206      if (MII.isCopyLike()) {4207        if (applyTerminalRule(MII))4208          Terminals.push_back(&MII);4209        else4210          WorkList.push_back(&MII);4211      }4212    // Append the copies evicted by the terminal rule at the end of the list.4213    WorkList.append(Terminals.begin(), Terminals.end());4214  }4215  // Try coalescing the collected copies immediately, and remove the nulls.4216  // This prevents the WorkList from getting too large since most copies are4217  // joinable on the first attempt.4218  MutableArrayRef<MachineInstr *> CurrList(WorkList.begin() + PrevSize,4219                                           WorkList.end());4220  if (copyCoalesceWorkList(CurrList))4221    WorkList.erase(4222        std::remove(WorkList.begin() + PrevSize, WorkList.end(), nullptr),4223        WorkList.end());4224}4225 4226void RegisterCoalescer::coalesceLocals() {4227  copyCoalesceWorkList(LocalWorkList);4228  for (MachineInstr *MI : LocalWorkList) {4229    if (MI)4230      WorkList.push_back(MI);4231  }4232  LocalWorkList.clear();4233}4234 4235void RegisterCoalescer::joinAllIntervals() {4236  LLVM_DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n");4237  assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around.");4238 4239  std::vector<MBBPriorityInfo> MBBs;4240  MBBs.reserve(MF->size());4241  for (MachineBasicBlock &MBB : *MF) {4242    MBBs.push_back(MBBPriorityInfo(&MBB, Loops->getLoopDepth(&MBB),4243                                   JoinSplitEdges && isSplitEdge(&MBB)));4244  }4245  array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority);4246 4247  // Coalesce intervals in MBB priority order.4248  unsigned CurrDepth = std::numeric_limits<unsigned>::max();4249  for (MBBPriorityInfo &MBB : MBBs) {4250    // Try coalescing the collected local copies for deeper loops.4251    if (JoinGlobalCopies && MBB.Depth < CurrDepth) {4252      coalesceLocals();4253      CurrDepth = MBB.Depth;4254    }4255    copyCoalesceInMBB(MBB.MBB);4256  }4257  lateLiveIntervalUpdate();4258  coalesceLocals();4259 4260  // Joining intervals can allow other intervals to be joined.  Iteratively join4261  // until we make no progress.4262  while (copyCoalesceWorkList(WorkList))4263    /* empty */;4264  lateLiveIntervalUpdate();4265}4266 4267PreservedAnalyses4268RegisterCoalescerPass::run(MachineFunction &MF,4269                           MachineFunctionAnalysisManager &MFAM) {4270  MFPropsModifier _(*this, MF);4271  auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(MF);4272  auto &Loops = MFAM.getResult<MachineLoopAnalysis>(MF);4273  auto *SI = MFAM.getCachedResult<SlotIndexesAnalysis>(MF);4274  RegisterCoalescer Impl(&LIS, SI, &Loops);4275  if (!Impl.run(MF))4276    return PreservedAnalyses::all();4277  auto PA = getMachineFunctionPassPreservedAnalyses();4278  PA.preserveSet<CFGAnalyses>();4279  PA.preserve<LiveIntervalsAnalysis>();4280  PA.preserve<SlotIndexesAnalysis>();4281  PA.preserve<MachineLoopAnalysis>();4282  PA.preserve<MachineDominatorTreeAnalysis>();4283  return PA;4284}4285 4286bool RegisterCoalescerLegacy::runOnMachineFunction(MachineFunction &MF) {4287  auto *LIS = &getAnalysis<LiveIntervalsWrapperPass>().getLIS();4288  auto *Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();4289  auto *SIWrapper = getAnalysisIfAvailable<SlotIndexesWrapperPass>();4290  SlotIndexes *SI = SIWrapper ? &SIWrapper->getSI() : nullptr;4291  RegisterCoalescer Impl(LIS, SI, Loops);4292  return Impl.run(MF);4293}4294 4295bool RegisterCoalescer::run(MachineFunction &fn) {4296  LLVM_DEBUG(dbgs() << "********** REGISTER COALESCER **********\n"4297                    << "********** Function: " << fn.getName() << '\n');4298 4299  // Variables changed between a setjmp and a longjump can have undefined value4300  // after the longjmp. This behaviour can be observed if such a variable is4301  // spilled, so longjmp won't restore the value in the spill slot.4302  // RegisterCoalescer should not run in functions with a setjmp to avoid4303  // merging such undefined variables with predictable ones.4304  //4305  // TODO: Could specifically disable coalescing registers live across setjmp4306  // calls4307  if (fn.exposesReturnsTwice()) {4308    LLVM_DEBUG(4309        dbgs() << "* Skipped as it exposes functions that returns twice.\n");4310    return false;4311  }4312 4313  MF = &fn;4314  MRI = &fn.getRegInfo();4315  const TargetSubtargetInfo &STI = fn.getSubtarget();4316  TRI = STI.getRegisterInfo();4317  TII = STI.getInstrInfo();4318  if (EnableGlobalCopies == cl::BOU_UNSET)4319    JoinGlobalCopies = STI.enableJoinGlobalCopies();4320  else4321    JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE);4322 4323  // If there are PHIs tracked by debug-info, they will need updating during4324  // coalescing. Build an index of those PHIs to ease updating.4325  SlotIndexes *Slots = LIS->getSlotIndexes();4326  for (const auto &DebugPHI : MF->DebugPHIPositions) {4327    MachineBasicBlock *MBB = DebugPHI.second.MBB;4328    Register Reg = DebugPHI.second.Reg;4329    unsigned SubReg = DebugPHI.second.SubReg;4330    SlotIndex SI = Slots->getMBBStartIdx(MBB);4331    PHIValPos P = {SI, Reg, SubReg};4332    PHIValToPos.insert(std::make_pair(DebugPHI.first, P));4333    RegToPHIIdx[Reg].push_back(DebugPHI.first);4334  }4335 4336  // The MachineScheduler does not currently require JoinSplitEdges. This will4337  // either be enabled unconditionally or replaced by a more general live range4338  // splitting optimization.4339  JoinSplitEdges = EnableJoinSplits;4340 4341  if (VerifyCoalescing)4342    MF->verify(LIS, SI, "Before register coalescing", &errs());4343 4344  DbgVRegToValues.clear();4345  buildVRegToDbgValueMap(fn);4346 4347  RegClassInfo.runOnMachineFunction(fn);4348 4349  // Join (coalesce) intervals if requested.4350  if (EnableJoining)4351    joinAllIntervals();4352 4353  // After deleting a lot of copies, register classes may be less constrained.4354  // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 ->4355  // DPR inflation.4356  array_pod_sort(InflateRegs.begin(), InflateRegs.end());4357  InflateRegs.erase(llvm::unique(InflateRegs), InflateRegs.end());4358  LLVM_DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size()4359                    << " regs.\n");4360  for (Register Reg : InflateRegs) {4361    if (MRI->reg_nodbg_empty(Reg))4362      continue;4363    if (MRI->recomputeRegClass(Reg)) {4364      LLVM_DEBUG(dbgs() << printReg(Reg) << " inflated to "4365                        << TRI->getRegClassName(MRI->getRegClass(Reg)) << '\n');4366      ++NumInflated;4367 4368      LiveInterval &LI = LIS->getInterval(Reg);4369      if (LI.hasSubRanges()) {4370        // If the inflated register class does not support subregisters anymore4371        // remove the subranges.4372        if (!MRI->shouldTrackSubRegLiveness(Reg)) {4373          LI.clearSubRanges();4374        } else {4375#ifndef NDEBUG4376          LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);4377          // If subranges are still supported, then the same subregs4378          // should still be supported.4379          for (LiveInterval::SubRange &S : LI.subranges()) {4380            assert((S.LaneMask & ~MaxMask).none());4381          }4382#endif4383        }4384      }4385    }4386  }4387 4388  // After coalescing, update any PHIs that are being tracked by debug-info4389  // with their new VReg locations.4390  for (auto &p : MF->DebugPHIPositions) {4391    auto it = PHIValToPos.find(p.first);4392    assert(it != PHIValToPos.end());4393    p.second.Reg = it->second.Reg;4394    p.second.SubReg = it->second.SubReg;4395  }4396 4397  PHIValToPos.clear();4398  RegToPHIIdx.clear();4399 4400  LLVM_DEBUG(LIS->dump());4401 4402  if (VerifyCoalescing)4403    MF->verify(LIS, SI, "After register coalescing", &errs());4404  return true;4405}4406