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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the generic RegisterCoalescer interface which
10 // is used as the common interface used by all clients and
11 // 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/Analysis/AliasAnalysis.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/MachineFunction.h"
29 #include "llvm/CodeGen/MachineFunctionPass.h"
30 #include "llvm/CodeGen/MachineInstr.h"
31 #include "llvm/CodeGen/MachineInstrBuilder.h"
32 #include "llvm/CodeGen/MachineLoopInfo.h"
33 #include "llvm/CodeGen/MachineOperand.h"
34 #include "llvm/CodeGen/MachineRegisterInfo.h"
35 #include "llvm/CodeGen/Passes.h"
36 #include "llvm/CodeGen/RegisterClassInfo.h"
37 #include "llvm/CodeGen/SlotIndexes.h"
38 #include "llvm/CodeGen/TargetInstrInfo.h"
39 #include "llvm/CodeGen/TargetOpcodes.h"
40 #include "llvm/CodeGen/TargetRegisterInfo.h"
41 #include "llvm/CodeGen/TargetSubtargetInfo.h"
42 #include "llvm/IR/DebugLoc.h"
43 #include "llvm/InitializePasses.h"
44 #include "llvm/MC/LaneBitmask.h"
45 #include "llvm/MC/MCInstrDesc.h"
46 #include "llvm/MC/MCRegisterInfo.h"
47 #include "llvm/Pass.h"
48 #include "llvm/Support/CommandLine.h"
49 #include "llvm/Support/Compiler.h"
50 #include "llvm/Support/Debug.h"
51 #include "llvm/Support/ErrorHandling.h"
52 #include "llvm/Support/raw_ostream.h"
53 #include <algorithm>
54 #include <cassert>
55 #include <iterator>
56 #include <limits>
57 #include <tuple>
58 #include <utility>
59 #include <vector>
60 
61 using namespace llvm;
62 
63 #define DEBUG_TYPE "regalloc"
64 
65 STATISTIC(numJoins    , "Number of interval joins performed");
66 STATISTIC(numCrossRCs , "Number of cross class joins performed");
67 STATISTIC(numCommutes , "Number of instruction commuting performed");
68 STATISTIC(numExtends  , "Number of copies extended");
69 STATISTIC(NumReMats   , "Number of instructions re-materialized");
70 STATISTIC(NumInflated , "Number of register classes inflated");
71 STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested");
72 STATISTIC(NumLaneResolves,  "Number of dead lane conflicts resolved");
73 STATISTIC(NumShrinkToUses,  "Number of shrinkToUses called");
74 
75 static cl::opt<bool> EnableJoining("join-liveintervals",
76                                    cl::desc("Coalesce copies (default=true)"),
77                                    cl::init(true), cl::Hidden);
78 
79 static cl::opt<bool> UseTerminalRule("terminal-rule",
80                                      cl::desc("Apply the terminal rule"),
81                                      cl::init(false), cl::Hidden);
82 
83 /// Temporary flag to test critical edge unsplitting.
84 static cl::opt<bool>
85 EnableJoinSplits("join-splitedges",
86   cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden);
87 
88 /// Temporary flag to test global copy optimization.
89 static cl::opt<cl::boolOrDefault>
90 EnableGlobalCopies("join-globalcopies",
91   cl::desc("Coalesce copies that span blocks (default=subtarget)"),
92   cl::init(cl::BOU_UNSET), cl::Hidden);
93 
94 static cl::opt<bool>
95 VerifyCoalescing("verify-coalescing",
96          cl::desc("Verify machine instrs before and after register coalescing"),
97          cl::Hidden);
98 
99 static cl::opt<unsigned> LateRematUpdateThreshold(
100     "late-remat-update-threshold", cl::Hidden,
101     cl::desc("During rematerialization for a copy, if the def instruction has "
102              "many other copy uses to be rematerialized, delay the multiple "
103              "separate live interval update work and do them all at once after "
104              "all those rematerialization are done. It will save a lot of "
105              "repeated work. "),
106     cl::init(100));
107 
108 static cl::opt<unsigned> LargeIntervalSizeThreshold(
109     "large-interval-size-threshold", cl::Hidden,
110     cl::desc("If the valnos size of an interval is larger than the threshold, "
111              "it is regarded as a large interval. "),
112     cl::init(100));
113 
114 static cl::opt<unsigned> LargeIntervalFreqThreshold(
115     "large-interval-freq-threshold", cl::Hidden,
116     cl::desc("For a large interval, if it is coalesed with other live "
117              "intervals many times more than the threshold, stop its "
118              "coalescing to control the compile time. "),
119     cl::init(256));
120 
121 namespace {
122 
123   class JoinVals;
124 
125   class RegisterCoalescer : public MachineFunctionPass,
126                             private LiveRangeEdit::Delegate {
127     MachineFunction* MF = nullptr;
128     MachineRegisterInfo* MRI = nullptr;
129     const TargetRegisterInfo* TRI = nullptr;
130     const TargetInstrInfo* TII = nullptr;
131     LiveIntervals *LIS = nullptr;
132     const MachineLoopInfo* Loops = nullptr;
133     AliasAnalysis *AA = nullptr;
134     RegisterClassInfo RegClassInfo;
135 
136     /// Position and VReg of a PHI instruction during coalescing.
137     struct PHIValPos {
138       SlotIndex SI;    ///< Slot where this PHI occurs.
139       Register Reg;    ///< VReg the PHI occurs in.
140       unsigned SubReg; ///< Qualifying subregister for Reg.
141     };
142 
143     /// Map from debug instruction number to PHI position during coalescing.
144     DenseMap<unsigned, PHIValPos> PHIValToPos;
145     /// Index of, for each VReg, which debug instruction numbers and
146     /// corresponding PHIs are sensitive to coalescing. Each VReg may have
147     /// multiple PHI defs, at different positions.
148     DenseMap<Register, SmallVector<unsigned, 2>> RegToPHIIdx;
149 
150     /// Debug variable location tracking -- for each VReg, maintain an
151     /// ordered-by-slot-index set of DBG_VALUEs, to help quick
152     /// identification of whether coalescing may change location validity.
153     using DbgValueLoc = std::pair<SlotIndex, MachineInstr*>;
154     DenseMap<Register, std::vector<DbgValueLoc>> DbgVRegToValues;
155 
156     /// A LaneMask to remember on which subregister live ranges we need to call
157     /// shrinkToUses() later.
158     LaneBitmask ShrinkMask;
159 
160     /// True if the main range of the currently coalesced intervals should be
161     /// checked for smaller live intervals.
162     bool ShrinkMainRange = false;
163 
164     /// True if the coalescer should aggressively coalesce global copies
165     /// in favor of keeping local copies.
166     bool JoinGlobalCopies = false;
167 
168     /// True if the coalescer should aggressively coalesce fall-thru
169     /// blocks exclusively containing copies.
170     bool JoinSplitEdges = false;
171 
172     /// Copy instructions yet to be coalesced.
173     SmallVector<MachineInstr*, 8> WorkList;
174     SmallVector<MachineInstr*, 8> LocalWorkList;
175 
176     /// Set of instruction pointers that have been erased, and
177     /// that may be present in WorkList.
178     SmallPtrSet<MachineInstr*, 8> ErasedInstrs;
179 
180     /// Dead instructions that are about to be deleted.
181     SmallVector<MachineInstr*, 8> DeadDefs;
182 
183     /// Virtual registers to be considered for register class inflation.
184     SmallVector<Register, 8> InflateRegs;
185 
186     /// The collection of live intervals which should have been updated
187     /// immediately after rematerialiation but delayed until
188     /// lateLiveIntervalUpdate is called.
189     DenseSet<Register> ToBeUpdated;
190 
191     /// Record how many times the large live interval with many valnos
192     /// has been tried to join with other live interval.
193     DenseMap<Register, unsigned long> LargeLIVisitCounter;
194 
195     /// Recursively eliminate dead defs in DeadDefs.
196     void eliminateDeadDefs(LiveRangeEdit *Edit = nullptr);
197 
198     /// LiveRangeEdit callback for eliminateDeadDefs().
199     void LRE_WillEraseInstruction(MachineInstr *MI) override;
200 
201     /// Coalesce the LocalWorkList.
202     void coalesceLocals();
203 
204     /// Join compatible live intervals
205     void joinAllIntervals();
206 
207     /// Coalesce copies in the specified MBB, putting
208     /// copies that cannot yet be coalesced into WorkList.
209     void copyCoalesceInMBB(MachineBasicBlock *MBB);
210 
211     /// Tries to coalesce all copies in CurrList. Returns true if any progress
212     /// was made.
213     bool copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList);
214 
215     /// If one def has many copy like uses, and those copy uses are all
216     /// rematerialized, the live interval update needed for those
217     /// rematerializations will be delayed and done all at once instead
218     /// of being done multiple times. This is to save compile cost because
219     /// live interval update is costly.
220     void lateLiveIntervalUpdate();
221 
222     /// Check if the incoming value defined by a COPY at \p SLRQ in the subrange
223     /// has no value defined in the predecessors. If the incoming value is the
224     /// same as defined by the copy itself, the value is considered undefined.
225     bool copyValueUndefInPredecessors(LiveRange &S,
226                                       const MachineBasicBlock *MBB,
227                                       LiveQueryResult SLRQ);
228 
229     /// Set necessary undef flags on subregister uses after pruning out undef
230     /// lane segments from the subrange.
231     void setUndefOnPrunedSubRegUses(LiveInterval &LI, Register Reg,
232                                     LaneBitmask PrunedLanes);
233 
234     /// Attempt to join intervals corresponding to SrcReg/DstReg, which are the
235     /// src/dst of the copy instruction CopyMI.  This returns true if the copy
236     /// was successfully coalesced away. If it is not currently possible to
237     /// coalesce this interval, but it may be possible if other things get
238     /// coalesced, then it returns true by reference in 'Again'.
239     bool joinCopy(MachineInstr *CopyMI, bool &Again);
240 
241     /// Attempt to join these two intervals.  On failure, this
242     /// returns false.  The output "SrcInt" will not have been modified, so we
243     /// can use this information below to update aliases.
244     bool joinIntervals(CoalescerPair &CP);
245 
246     /// Attempt joining two virtual registers. Return true on success.
247     bool joinVirtRegs(CoalescerPair &CP);
248 
249     /// If a live interval has many valnos and is coalesced with other
250     /// live intervals many times, we regard such live interval as having
251     /// high compile time cost.
252     bool isHighCostLiveInterval(LiveInterval &LI);
253 
254     /// Attempt joining with a reserved physreg.
255     bool joinReservedPhysReg(CoalescerPair &CP);
256 
257     /// Add the LiveRange @p ToMerge as a subregister liverange of @p LI.
258     /// Subranges in @p LI which only partially interfere with the desired
259     /// LaneMask are split as necessary. @p LaneMask are the lanes that
260     /// @p ToMerge will occupy in the coalescer register. @p LI has its subrange
261     /// lanemasks already adjusted to the coalesced register.
262     void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,
263                            LaneBitmask LaneMask, CoalescerPair &CP,
264                            unsigned DstIdx);
265 
266     /// Join the liveranges of two subregisters. Joins @p RRange into
267     /// @p LRange, @p RRange may be invalid afterwards.
268     void joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
269                           LaneBitmask LaneMask, const CoalescerPair &CP);
270 
271     /// We found a non-trivially-coalescable copy. If the source value number is
272     /// defined by a copy from the destination reg see if we can merge these two
273     /// destination reg valno# into a single value number, eliminating a copy.
274     /// This returns true if an interval was modified.
275     bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI);
276 
277     /// Return true if there are definitions of IntB
278     /// other than BValNo val# that can reach uses of AValno val# of IntA.
279     bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB,
280                               VNInfo *AValNo, VNInfo *BValNo);
281 
282     /// We found a non-trivially-coalescable copy.
283     /// If the source value number is defined by a commutable instruction and
284     /// its other operand is coalesced to the copy dest register, see if we
285     /// can transform the copy into a noop by commuting the definition.
286     /// This returns a pair of two flags:
287     /// - the first element is true if an interval was modified,
288     /// - the second element is true if the destination interval needs
289     ///   to be shrunk after deleting the copy.
290     std::pair<bool,bool> removeCopyByCommutingDef(const CoalescerPair &CP,
291                                                   MachineInstr *CopyMI);
292 
293     /// We found a copy which can be moved to its less frequent predecessor.
294     bool removePartialRedundancy(const CoalescerPair &CP, MachineInstr &CopyMI);
295 
296     /// If the source of a copy is defined by a
297     /// trivial computation, replace the copy by rematerialize the definition.
298     bool reMaterializeTrivialDef(const CoalescerPair &CP, MachineInstr *CopyMI,
299                                  bool &IsDefCopy);
300 
301     /// Return true if a copy involving a physreg should be joined.
302     bool canJoinPhys(const CoalescerPair &CP);
303 
304     /// Replace all defs and uses of SrcReg to DstReg and update the subregister
305     /// number if it is not zero. If DstReg is a physical register and the
306     /// existing subregister number of the def / use being updated is not zero,
307     /// make sure to set it to the correct physical subregister.
308     void updateRegDefsUses(Register SrcReg, Register DstReg, unsigned SubIdx);
309 
310     /// If the given machine operand reads only undefined lanes add an undef
311     /// flag.
312     /// This can happen when undef uses were previously concealed by a copy
313     /// which we coalesced. Example:
314     ///    %0:sub0<def,read-undef> = ...
315     ///    %1 = COPY %0           <-- Coalescing COPY reveals undef
316     ///       = use %1:sub1       <-- hidden undef use
317     void addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
318                       MachineOperand &MO, unsigned SubRegIdx);
319 
320     /// Handle copies of undef values. If the undef value is an incoming
321     /// PHI value, it will convert @p CopyMI to an IMPLICIT_DEF.
322     /// Returns nullptr if @p CopyMI was not in any way eliminable. Otherwise,
323     /// it returns @p CopyMI (which could be an IMPLICIT_DEF at this point).
324     MachineInstr *eliminateUndefCopy(MachineInstr *CopyMI);
325 
326     /// Check whether or not we should apply the terminal rule on the
327     /// destination (Dst) of \p Copy.
328     /// When the terminal rule applies, Copy is not profitable to
329     /// coalesce.
330     /// Dst is terminal if it has exactly one affinity (Dst, Src) and
331     /// at least one interference (Dst, Dst2). If Dst is terminal, the
332     /// terminal rule consists in checking that at least one of
333     /// interfering node, say Dst2, has an affinity of equal or greater
334     /// weight with Src.
335     /// In that case, Dst2 and Dst will not be able to be both coalesced
336     /// with Src. Since Dst2 exposes more coalescing opportunities than
337     /// Dst, we can drop \p Copy.
338     bool applyTerminalRule(const MachineInstr &Copy) const;
339 
340     /// Wrapper method for \see LiveIntervals::shrinkToUses.
341     /// This method does the proper fixing of the live-ranges when the afore
342     /// mentioned method returns true.
343     void shrinkToUses(LiveInterval *LI,
344                       SmallVectorImpl<MachineInstr * > *Dead = nullptr) {
345       NumShrinkToUses++;
346       if (LIS->shrinkToUses(LI, Dead)) {
347         /// Check whether or not \p LI is composed by multiple connected
348         /// components and if that is the case, fix that.
349         SmallVector<LiveInterval*, 8> SplitLIs;
350         LIS->splitSeparateComponents(*LI, SplitLIs);
351       }
352     }
353 
354     /// Wrapper Method to do all the necessary work when an Instruction is
355     /// deleted.
356     /// Optimizations should use this to make sure that deleted instructions
357     /// are always accounted for.
358     void deleteInstr(MachineInstr* MI) {
359       ErasedInstrs.insert(MI);
360       LIS->RemoveMachineInstrFromMaps(*MI);
361       MI->eraseFromParent();
362     }
363 
364     /// Walk over function and initialize the DbgVRegToValues map.
365     void buildVRegToDbgValueMap(MachineFunction &MF);
366 
367     /// Test whether, after merging, any DBG_VALUEs would refer to a
368     /// different value number than before merging, and whether this can
369     /// be resolved. If not, mark the DBG_VALUE as being undef.
370     void checkMergingChangesDbgValues(CoalescerPair &CP, LiveRange &LHS,
371                                       JoinVals &LHSVals, LiveRange &RHS,
372                                       JoinVals &RHSVals);
373 
374     void checkMergingChangesDbgValuesImpl(Register Reg, LiveRange &OtherRange,
375                                           LiveRange &RegRange, JoinVals &Vals2);
376 
377   public:
378     static char ID; ///< Class identification, replacement for typeinfo
379 
380     RegisterCoalescer() : MachineFunctionPass(ID) {
381       initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
382     }
383 
384     void getAnalysisUsage(AnalysisUsage &AU) const override;
385 
386     void releaseMemory() override;
387 
388     /// This is the pass entry point.
389     bool runOnMachineFunction(MachineFunction&) override;
390 
391     /// Implement the dump method.
392     void print(raw_ostream &O, const Module* = nullptr) const override;
393   };
394 
395 } // end anonymous namespace
396 
397 char RegisterCoalescer::ID = 0;
398 
399 char &llvm::RegisterCoalescerID = RegisterCoalescer::ID;
400 
401 INITIALIZE_PASS_BEGIN(RegisterCoalescer, "register-coalescer",
402                       "Register Coalescer", false, false)
403 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
404 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
405 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
406 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
407 INITIALIZE_PASS_END(RegisterCoalescer, "register-coalescer",
408                     "Register Coalescer", false, false)
409 
410 [[nodiscard]] static bool isMoveInstr(const TargetRegisterInfo &tri,
411                                       const MachineInstr *MI, Register &Src,
412                                       Register &Dst, unsigned &SrcSub,
413                                       unsigned &DstSub) {
414     if (MI->isCopy()) {
415       Dst = MI->getOperand(0).getReg();
416       DstSub = MI->getOperand(0).getSubReg();
417       Src = MI->getOperand(1).getReg();
418       SrcSub = MI->getOperand(1).getSubReg();
419     } else if (MI->isSubregToReg()) {
420       Dst = MI->getOperand(0).getReg();
421       DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(),
422                                         MI->getOperand(3).getImm());
423       Src = MI->getOperand(2).getReg();
424       SrcSub = MI->getOperand(2).getSubReg();
425     } else
426       return false;
427     return true;
428 }
429 
430 /// Return true if this block should be vacated by the coalescer to eliminate
431 /// branches. The important cases to handle in the coalescer are critical edges
432 /// split during phi elimination which contain only copies. Simple blocks that
433 /// contain non-branches should also be vacated, but this can be handled by an
434 /// earlier pass similar to early if-conversion.
435 static bool isSplitEdge(const MachineBasicBlock *MBB) {
436   if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
437     return false;
438 
439   for (const auto &MI : *MBB) {
440     if (!MI.isCopyLike() && !MI.isUnconditionalBranch())
441       return false;
442   }
443   return true;
444 }
445 
446 bool CoalescerPair::setRegisters(const MachineInstr *MI) {
447   SrcReg = DstReg = Register();
448   SrcIdx = DstIdx = 0;
449   NewRC = nullptr;
450   Flipped = CrossClass = false;
451 
452   Register Src, Dst;
453   unsigned SrcSub = 0, DstSub = 0;
454   if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub))
455     return false;
456   Partial = SrcSub || DstSub;
457 
458   // If one register is a physreg, it must be Dst.
459   if (Src.isPhysical()) {
460     if (Dst.isPhysical())
461       return false;
462     std::swap(Src, Dst);
463     std::swap(SrcSub, DstSub);
464     Flipped = true;
465   }
466 
467   const MachineRegisterInfo &MRI = MI->getMF()->getRegInfo();
468 
469   if (Dst.isPhysical()) {
470     // Eliminate DstSub on a physreg.
471     if (DstSub) {
472       Dst = TRI.getSubReg(Dst, DstSub);
473       if (!Dst) return false;
474       DstSub = 0;
475     }
476 
477     // Eliminate SrcSub by picking a corresponding Dst superregister.
478     if (SrcSub) {
479       Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src));
480       if (!Dst) return false;
481     } else if (!MRI.getRegClass(Src)->contains(Dst)) {
482       return false;
483     }
484   } else {
485     // Both registers are virtual.
486     const TargetRegisterClass *SrcRC = MRI.getRegClass(Src);
487     const TargetRegisterClass *DstRC = MRI.getRegClass(Dst);
488 
489     // Both registers have subreg indices.
490     if (SrcSub && DstSub) {
491       // Copies between different sub-registers are never coalescable.
492       if (Src == Dst && SrcSub != DstSub)
493         return false;
494 
495       NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub,
496                                          SrcIdx, DstIdx);
497       if (!NewRC)
498         return false;
499     } else if (DstSub) {
500       // SrcReg will be merged with a sub-register of DstReg.
501       SrcIdx = DstSub;
502       NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub);
503     } else if (SrcSub) {
504       // DstReg will be merged with a sub-register of SrcReg.
505       DstIdx = SrcSub;
506       NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub);
507     } else {
508       // This is a straight copy without sub-registers.
509       NewRC = TRI.getCommonSubClass(DstRC, SrcRC);
510     }
511 
512     // The combined constraint may be impossible to satisfy.
513     if (!NewRC)
514       return false;
515 
516     // Prefer SrcReg to be a sub-register of DstReg.
517     // FIXME: Coalescer should support subregs symmetrically.
518     if (DstIdx && !SrcIdx) {
519       std::swap(Src, Dst);
520       std::swap(SrcIdx, DstIdx);
521       Flipped = !Flipped;
522     }
523 
524     CrossClass = NewRC != DstRC || NewRC != SrcRC;
525   }
526   // Check our invariants
527   assert(Src.isVirtual() && "Src must be virtual");
528   assert(!(Dst.isPhysical() && DstSub) && "Cannot have a physical SubIdx");
529   SrcReg = Src;
530   DstReg = Dst;
531   return true;
532 }
533 
534 bool CoalescerPair::flip() {
535   if (DstReg.isPhysical())
536     return false;
537   std::swap(SrcReg, DstReg);
538   std::swap(SrcIdx, DstIdx);
539   Flipped = !Flipped;
540   return true;
541 }
542 
543 bool CoalescerPair::isCoalescable(const MachineInstr *MI) const {
544   if (!MI)
545     return false;
546   Register Src, Dst;
547   unsigned SrcSub = 0, DstSub = 0;
548   if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub))
549     return false;
550 
551   // Find the virtual register that is SrcReg.
552   if (Dst == SrcReg) {
553     std::swap(Src, Dst);
554     std::swap(SrcSub, DstSub);
555   } else if (Src != SrcReg) {
556     return false;
557   }
558 
559   // Now check that Dst matches DstReg.
560   if (DstReg.isPhysical()) {
561     if (!Dst.isPhysical())
562       return false;
563     assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state.");
564     // DstSub could be set for a physreg from INSERT_SUBREG.
565     if (DstSub)
566       Dst = TRI.getSubReg(Dst, DstSub);
567     // Full copy of Src.
568     if (!SrcSub)
569       return DstReg == Dst;
570     // This is a partial register copy. Check that the parts match.
571     return Register(TRI.getSubReg(DstReg, SrcSub)) == Dst;
572   } else {
573     // DstReg is virtual.
574     if (DstReg != Dst)
575       return false;
576     // Registers match, do the subregisters line up?
577     return TRI.composeSubRegIndices(SrcIdx, SrcSub) ==
578            TRI.composeSubRegIndices(DstIdx, DstSub);
579   }
580 }
581 
582 void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const {
583   AU.setPreservesCFG();
584   AU.addRequired<AAResultsWrapperPass>();
585   AU.addRequired<LiveIntervals>();
586   AU.addPreserved<LiveIntervals>();
587   AU.addPreserved<SlotIndexes>();
588   AU.addRequired<MachineLoopInfo>();
589   AU.addPreserved<MachineLoopInfo>();
590   AU.addPreservedID(MachineDominatorsID);
591   MachineFunctionPass::getAnalysisUsage(AU);
592 }
593 
594 void RegisterCoalescer::eliminateDeadDefs(LiveRangeEdit *Edit) {
595   if (Edit) {
596     Edit->eliminateDeadDefs(DeadDefs);
597     return;
598   }
599   SmallVector<Register, 8> NewRegs;
600   LiveRangeEdit(nullptr, NewRegs, *MF, *LIS,
601                 nullptr, this).eliminateDeadDefs(DeadDefs);
602 }
603 
604 void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) {
605   // MI may be in WorkList. Make sure we don't visit it.
606   ErasedInstrs.insert(MI);
607 }
608 
609 bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,
610                                              MachineInstr *CopyMI) {
611   assert(!CP.isPartial() && "This doesn't work for partial copies.");
612   assert(!CP.isPhys() && "This doesn't work for physreg copies.");
613 
614   LiveInterval &IntA =
615     LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
616   LiveInterval &IntB =
617     LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
618   SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
619 
620   // We have a non-trivially-coalescable copy with IntA being the source and
621   // IntB being the dest, thus this defines a value number in IntB.  If the
622   // source value number (in IntA) is defined by a copy from B, see if we can
623   // merge these two pieces of B into a single value number, eliminating a copy.
624   // For example:
625   //
626   //  A3 = B0
627   //    ...
628   //  B1 = A3      <- this copy
629   //
630   // In this case, B0 can be extended to where the B1 copy lives, allowing the
631   // B1 value number to be replaced with B0 (which simplifies the B
632   // liveinterval).
633 
634   // BValNo is a value number in B that is defined by a copy from A.  'B1' in
635   // the example above.
636   LiveInterval::iterator BS = IntB.FindSegmentContaining(CopyIdx);
637   if (BS == IntB.end()) return false;
638   VNInfo *BValNo = BS->valno;
639 
640   // Get the location that B is defined at.  Two options: either this value has
641   // an unknown definition point or it is defined at CopyIdx.  If unknown, we
642   // can't process it.
643   if (BValNo->def != CopyIdx) return false;
644 
645   // AValNo is the value number in A that defines the copy, A3 in the example.
646   SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true);
647   LiveInterval::iterator AS = IntA.FindSegmentContaining(CopyUseIdx);
648   // The live segment might not exist after fun with physreg coalescing.
649   if (AS == IntA.end()) return false;
650   VNInfo *AValNo = AS->valno;
651 
652   // If AValNo is defined as a copy from IntB, we can potentially process this.
653   // Get the instruction that defines this value number.
654   MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def);
655   // Don't allow any partial copies, even if isCoalescable() allows them.
656   if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy())
657     return false;
658 
659   // Get the Segment in IntB that this value number starts with.
660   LiveInterval::iterator ValS =
661     IntB.FindSegmentContaining(AValNo->def.getPrevSlot());
662   if (ValS == IntB.end())
663     return false;
664 
665   // Make sure that the end of the live segment is inside the same block as
666   // CopyMI.
667   MachineInstr *ValSEndInst =
668     LIS->getInstructionFromIndex(ValS->end.getPrevSlot());
669   if (!ValSEndInst || ValSEndInst->getParent() != CopyMI->getParent())
670     return false;
671 
672   // Okay, we now know that ValS ends in the same block that the CopyMI
673   // live-range starts.  If there are no intervening live segments between them
674   // in IntB, we can merge them.
675   if (ValS+1 != BS) return false;
676 
677   LLVM_DEBUG(dbgs() << "Extending: " << printReg(IntB.reg(), TRI));
678 
679   SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;
680   // We are about to delete CopyMI, so need to remove it as the 'instruction
681   // that defines this value #'. Update the valnum with the new defining
682   // instruction #.
683   BValNo->def = FillerStart;
684 
685   // Okay, we can merge them.  We need to insert a new liverange:
686   // [ValS.end, BS.begin) of either value number, then we merge the
687   // two value numbers.
688   IntB.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, BValNo));
689 
690   // Okay, merge "B1" into the same value number as "B0".
691   if (BValNo != ValS->valno)
692     IntB.MergeValueNumberInto(BValNo, ValS->valno);
693 
694   // Do the same for the subregister segments.
695   for (LiveInterval::SubRange &S : IntB.subranges()) {
696     // Check for SubRange Segments of the form [1234r,1234d:0) which can be
697     // removed to prevent creating bogus SubRange Segments.
698     LiveInterval::iterator SS = S.FindSegmentContaining(CopyIdx);
699     if (SS != S.end() && SlotIndex::isSameInstr(SS->start, SS->end)) {
700       S.removeSegment(*SS, true);
701       continue;
702     }
703     // The subrange may have ended before FillerStart. If so, extend it.
704     if (!S.getVNInfoAt(FillerStart)) {
705       SlotIndex BBStart =
706           LIS->getMBBStartIdx(LIS->getMBBFromIndex(FillerStart));
707       S.extendInBlock(BBStart, FillerStart);
708     }
709     VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
710     S.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo));
711     VNInfo *SubValSNo = S.getVNInfoAt(AValNo->def.getPrevSlot());
712     if (SubBValNo != SubValSNo)
713       S.MergeValueNumberInto(SubBValNo, SubValSNo);
714   }
715 
716   LLVM_DEBUG(dbgs() << "   result = " << IntB << '\n');
717 
718   // If the source instruction was killing the source register before the
719   // merge, unset the isKill marker given the live range has been extended.
720   int UIdx = ValSEndInst->findRegisterUseOperandIdx(IntB.reg(), true);
721   if (UIdx != -1) {
722     ValSEndInst->getOperand(UIdx).setIsKill(false);
723   }
724 
725   // Rewrite the copy.
726   CopyMI->substituteRegister(IntA.reg(), IntB.reg(), 0, *TRI);
727   // If the copy instruction was killing the destination register or any
728   // subrange before the merge trim the live range.
729   bool RecomputeLiveRange = AS->end == CopyIdx;
730   if (!RecomputeLiveRange) {
731     for (LiveInterval::SubRange &S : IntA.subranges()) {
732       LiveInterval::iterator SS = S.FindSegmentContaining(CopyUseIdx);
733       if (SS != S.end() && SS->end == CopyIdx) {
734         RecomputeLiveRange = true;
735         break;
736       }
737     }
738   }
739   if (RecomputeLiveRange)
740     shrinkToUses(&IntA);
741 
742   ++numExtends;
743   return true;
744 }
745 
746 bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA,
747                                              LiveInterval &IntB,
748                                              VNInfo *AValNo,
749                                              VNInfo *BValNo) {
750   // If AValNo has PHI kills, conservatively assume that IntB defs can reach
751   // the PHI values.
752   if (LIS->hasPHIKill(IntA, AValNo))
753     return true;
754 
755   for (LiveRange::Segment &ASeg : IntA.segments) {
756     if (ASeg.valno != AValNo) continue;
757     LiveInterval::iterator BI = llvm::upper_bound(IntB, ASeg.start);
758     if (BI != IntB.begin())
759       --BI;
760     for (; BI != IntB.end() && ASeg.end >= BI->start; ++BI) {
761       if (BI->valno == BValNo)
762         continue;
763       if (BI->start <= ASeg.start && BI->end > ASeg.start)
764         return true;
765       if (BI->start > ASeg.start && BI->start < ASeg.end)
766         return true;
767     }
768   }
769   return false;
770 }
771 
772 /// Copy segments with value number @p SrcValNo from liverange @p Src to live
773 /// range @Dst and use value number @p DstValNo there.
774 static std::pair<bool,bool>
775 addSegmentsWithValNo(LiveRange &Dst, VNInfo *DstValNo, const LiveRange &Src,
776                      const VNInfo *SrcValNo) {
777   bool Changed = false;
778   bool MergedWithDead = false;
779   for (const LiveRange::Segment &S : Src.segments) {
780     if (S.valno != SrcValNo)
781       continue;
782     // This is adding a segment from Src that ends in a copy that is about
783     // to be removed. This segment is going to be merged with a pre-existing
784     // segment in Dst. This works, except in cases when the corresponding
785     // segment in Dst is dead. For example: adding [192r,208r:1) from Src
786     // to [208r,208d:1) in Dst would create [192r,208d:1) in Dst.
787     // Recognized such cases, so that the segments can be shrunk.
788     LiveRange::Segment Added = LiveRange::Segment(S.start, S.end, DstValNo);
789     LiveRange::Segment &Merged = *Dst.addSegment(Added);
790     if (Merged.end.isDead())
791       MergedWithDead = true;
792     Changed = true;
793   }
794   return std::make_pair(Changed, MergedWithDead);
795 }
796 
797 std::pair<bool,bool>
798 RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP,
799                                             MachineInstr *CopyMI) {
800   assert(!CP.isPhys());
801 
802   LiveInterval &IntA =
803       LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
804   LiveInterval &IntB =
805       LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
806 
807   // We found a non-trivially-coalescable copy with IntA being the source and
808   // IntB being the dest, thus this defines a value number in IntB.  If the
809   // source value number (in IntA) is defined by a commutable instruction and
810   // its other operand is coalesced to the copy dest register, see if we can
811   // transform the copy into a noop by commuting the definition. For example,
812   //
813   //  A3 = op A2 killed B0
814   //    ...
815   //  B1 = A3      <- this copy
816   //    ...
817   //     = op A3   <- more uses
818   //
819   // ==>
820   //
821   //  B2 = op B0 killed A2
822   //    ...
823   //  B1 = B2      <- now an identity copy
824   //    ...
825   //     = op B2   <- more uses
826 
827   // BValNo is a value number in B that is defined by a copy from A. 'B1' in
828   // the example above.
829   SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
830   VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx);
831   assert(BValNo != nullptr && BValNo->def == CopyIdx);
832 
833   // AValNo is the value number in A that defines the copy, A3 in the example.
834   VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true));
835   assert(AValNo && !AValNo->isUnused() && "COPY source not live");
836   if (AValNo->isPHIDef())
837     return { false, false };
838   MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def);
839   if (!DefMI)
840     return { false, false };
841   if (!DefMI->isCommutable())
842     return { false, false };
843   // If DefMI is a two-address instruction then commuting it will change the
844   // destination register.
845   int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg());
846   assert(DefIdx != -1);
847   unsigned UseOpIdx;
848   if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx))
849     return { false, false };
850 
851   // FIXME: The code below tries to commute 'UseOpIdx' operand with some other
852   // commutable operand which is expressed by 'CommuteAnyOperandIndex'value
853   // passed to the method. That _other_ operand is chosen by
854   // the findCommutedOpIndices() method.
855   //
856   // That is obviously an area for improvement in case of instructions having
857   // more than 2 operands. For example, if some instruction has 3 commutable
858   // operands then all possible variants (i.e. op#1<->op#2, op#1<->op#3,
859   // op#2<->op#3) of commute transformation should be considered/tried here.
860   unsigned NewDstIdx = TargetInstrInfo::CommuteAnyOperandIndex;
861   if (!TII->findCommutedOpIndices(*DefMI, UseOpIdx, NewDstIdx))
862     return { false, false };
863 
864   MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
865   Register NewReg = NewDstMO.getReg();
866   if (NewReg != IntB.reg() || !IntB.Query(AValNo->def).isKill())
867     return { false, false };
868 
869   // Make sure there are no other definitions of IntB that would reach the
870   // uses which the new definition can reach.
871   if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
872     return { false, false };
873 
874   // If some of the uses of IntA.reg is already coalesced away, return false.
875   // It's not possible to determine whether it's safe to perform the coalescing.
876   for (MachineOperand &MO : MRI->use_nodbg_operands(IntA.reg())) {
877     MachineInstr *UseMI = MO.getParent();
878     unsigned OpNo = &MO - &UseMI->getOperand(0);
879     SlotIndex UseIdx = LIS->getInstructionIndex(*UseMI);
880     LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx);
881     if (US == IntA.end() || US->valno != AValNo)
882       continue;
883     // If this use is tied to a def, we can't rewrite the register.
884     if (UseMI->isRegTiedToDefOperand(OpNo))
885       return { false, false };
886   }
887 
888   LLVM_DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t'
889                     << *DefMI);
890 
891   // At this point we have decided that it is legal to do this
892   // transformation.  Start by commuting the instruction.
893   MachineBasicBlock *MBB = DefMI->getParent();
894   MachineInstr *NewMI =
895       TII->commuteInstruction(*DefMI, false, UseOpIdx, NewDstIdx);
896   if (!NewMI)
897     return { false, false };
898   if (IntA.reg().isVirtual() && IntB.reg().isVirtual() &&
899       !MRI->constrainRegClass(IntB.reg(), MRI->getRegClass(IntA.reg())))
900     return { false, false };
901   if (NewMI != DefMI) {
902     LIS->ReplaceMachineInstrInMaps(*DefMI, *NewMI);
903     MachineBasicBlock::iterator Pos = DefMI;
904     MBB->insert(Pos, NewMI);
905     MBB->erase(DefMI);
906   }
907 
908   // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
909   // A = or A, B
910   // ...
911   // B = A
912   // ...
913   // C = killed A
914   // ...
915   //   = B
916 
917   // Update uses of IntA of the specific Val# with IntB.
918   for (MachineOperand &UseMO :
919        llvm::make_early_inc_range(MRI->use_operands(IntA.reg()))) {
920     if (UseMO.isUndef())
921       continue;
922     MachineInstr *UseMI = UseMO.getParent();
923     if (UseMI->isDebugInstr()) {
924       // FIXME These don't have an instruction index.  Not clear we have enough
925       // info to decide whether to do this replacement or not.  For now do it.
926       UseMO.setReg(NewReg);
927       continue;
928     }
929     SlotIndex UseIdx = LIS->getInstructionIndex(*UseMI).getRegSlot(true);
930     LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx);
931     assert(US != IntA.end() && "Use must be live");
932     if (US->valno != AValNo)
933       continue;
934     // Kill flags are no longer accurate. They are recomputed after RA.
935     UseMO.setIsKill(false);
936     if (NewReg.isPhysical())
937       UseMO.substPhysReg(NewReg, *TRI);
938     else
939       UseMO.setReg(NewReg);
940     if (UseMI == CopyMI)
941       continue;
942     if (!UseMI->isCopy())
943       continue;
944     if (UseMI->getOperand(0).getReg() != IntB.reg() ||
945         UseMI->getOperand(0).getSubReg())
946       continue;
947 
948     // This copy will become a noop. If it's defining a new val#, merge it into
949     // BValNo.
950     SlotIndex DefIdx = UseIdx.getRegSlot();
951     VNInfo *DVNI = IntB.getVNInfoAt(DefIdx);
952     if (!DVNI)
953       continue;
954     LLVM_DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI);
955     assert(DVNI->def == DefIdx);
956     BValNo = IntB.MergeValueNumberInto(DVNI, BValNo);
957     for (LiveInterval::SubRange &S : IntB.subranges()) {
958       VNInfo *SubDVNI = S.getVNInfoAt(DefIdx);
959       if (!SubDVNI)
960         continue;
961       VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
962       assert(SubBValNo->def == CopyIdx);
963       S.MergeValueNumberInto(SubDVNI, SubBValNo);
964     }
965 
966     deleteInstr(UseMI);
967   }
968 
969   // Extend BValNo by merging in IntA live segments of AValNo. Val# definition
970   // is updated.
971   bool ShrinkB = false;
972   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
973   if (IntA.hasSubRanges() || IntB.hasSubRanges()) {
974     if (!IntA.hasSubRanges()) {
975       LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntA.reg());
976       IntA.createSubRangeFrom(Allocator, Mask, IntA);
977     } else if (!IntB.hasSubRanges()) {
978       LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntB.reg());
979       IntB.createSubRangeFrom(Allocator, Mask, IntB);
980     }
981     SlotIndex AIdx = CopyIdx.getRegSlot(true);
982     LaneBitmask MaskA;
983     const SlotIndexes &Indexes = *LIS->getSlotIndexes();
984     for (LiveInterval::SubRange &SA : IntA.subranges()) {
985       VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);
986       // Even if we are dealing with a full copy, some lanes can
987       // still be undefined.
988       // E.g.,
989       // undef A.subLow = ...
990       // B = COPY A <== A.subHigh is undefined here and does
991       //                not have a value number.
992       if (!ASubValNo)
993         continue;
994       MaskA |= SA.LaneMask;
995 
996       IntB.refineSubRanges(
997           Allocator, SA.LaneMask,
998           [&Allocator, &SA, CopyIdx, ASubValNo,
999            &ShrinkB](LiveInterval::SubRange &SR) {
1000             VNInfo *BSubValNo = SR.empty() ? SR.getNextValue(CopyIdx, Allocator)
1001                                            : SR.getVNInfoAt(CopyIdx);
1002             assert(BSubValNo != nullptr);
1003             auto P = addSegmentsWithValNo(SR, BSubValNo, SA, ASubValNo);
1004             ShrinkB |= P.second;
1005             if (P.first)
1006               BSubValNo->def = ASubValNo->def;
1007           },
1008           Indexes, *TRI);
1009     }
1010     // Go over all subranges of IntB that have not been covered by IntA,
1011     // and delete the segments starting at CopyIdx. This can happen if
1012     // IntA has undef lanes that are defined in IntB.
1013     for (LiveInterval::SubRange &SB : IntB.subranges()) {
1014       if ((SB.LaneMask & MaskA).any())
1015         continue;
1016       if (LiveRange::Segment *S = SB.getSegmentContaining(CopyIdx))
1017         if (S->start.getBaseIndex() == CopyIdx.getBaseIndex())
1018           SB.removeSegment(*S, true);
1019     }
1020   }
1021 
1022   BValNo->def = AValNo->def;
1023   auto P = addSegmentsWithValNo(IntB, BValNo, IntA, AValNo);
1024   ShrinkB |= P.second;
1025   LLVM_DEBUG(dbgs() << "\t\textended: " << IntB << '\n');
1026 
1027   LIS->removeVRegDefAt(IntA, AValNo->def);
1028 
1029   LLVM_DEBUG(dbgs() << "\t\ttrimmed:  " << IntA << '\n');
1030   ++numCommutes;
1031   return { true, ShrinkB };
1032 }
1033 
1034 /// For copy B = A in BB2, if A is defined by A = B in BB0 which is a
1035 /// predecessor of BB2, and if B is not redefined on the way from A = B
1036 /// in BB0 to B = A in BB2, B = A in BB2 is partially redundant if the
1037 /// execution goes through the path from BB0 to BB2. We may move B = A
1038 /// to the predecessor without such reversed copy.
1039 /// So we will transform the program from:
1040 ///   BB0:
1041 ///      A = B;    BB1:
1042 ///       ...         ...
1043 ///     /     \      /
1044 ///             BB2:
1045 ///               ...
1046 ///               B = A;
1047 ///
1048 /// to:
1049 ///
1050 ///   BB0:         BB1:
1051 ///      A = B;        ...
1052 ///       ...          B = A;
1053 ///     /     \       /
1054 ///             BB2:
1055 ///               ...
1056 ///
1057 /// A special case is when BB0 and BB2 are the same BB which is the only
1058 /// BB in a loop:
1059 ///   BB1:
1060 ///        ...
1061 ///   BB0/BB2:  ----
1062 ///        B = A;   |
1063 ///        ...      |
1064 ///        A = B;   |
1065 ///          |-------
1066 ///          |
1067 /// We may hoist B = A from BB0/BB2 to BB1.
1068 ///
1069 /// The major preconditions for correctness to remove such partial
1070 /// redundancy include:
1071 /// 1. A in B = A in BB2 is defined by a PHI in BB2, and one operand of
1072 ///    the PHI is defined by the reversed copy A = B in BB0.
1073 /// 2. No B is referenced from the start of BB2 to B = A.
1074 /// 3. No B is defined from A = B to the end of BB0.
1075 /// 4. BB1 has only one successor.
1076 ///
1077 /// 2 and 4 implicitly ensure B is not live at the end of BB1.
1078 /// 4 guarantees BB2 is hotter than BB1, so we can only move a copy to a
1079 /// colder place, which not only prevent endless loop, but also make sure
1080 /// the movement of copy is beneficial.
1081 bool RegisterCoalescer::removePartialRedundancy(const CoalescerPair &CP,
1082                                                 MachineInstr &CopyMI) {
1083   assert(!CP.isPhys());
1084   if (!CopyMI.isFullCopy())
1085     return false;
1086 
1087   MachineBasicBlock &MBB = *CopyMI.getParent();
1088   // If this block is the target of an invoke/inlineasm_br, moving the copy into
1089   // the predecessor is tricker, and we don't handle it.
1090   if (MBB.isEHPad() || MBB.isInlineAsmBrIndirectTarget())
1091     return false;
1092 
1093   if (MBB.pred_size() != 2)
1094     return false;
1095 
1096   LiveInterval &IntA =
1097       LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
1098   LiveInterval &IntB =
1099       LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
1100 
1101   // A is defined by PHI at the entry of MBB.
1102   SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true);
1103   VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx);
1104   assert(AValNo && !AValNo->isUnused() && "COPY source not live");
1105   if (!AValNo->isPHIDef())
1106     return false;
1107 
1108   // No B is referenced before CopyMI in MBB.
1109   if (IntB.overlaps(LIS->getMBBStartIdx(&MBB), CopyIdx))
1110     return false;
1111 
1112   // MBB has two predecessors: one contains A = B so no copy will be inserted
1113   // for it. The other one will have a copy moved from MBB.
1114   bool FoundReverseCopy = false;
1115   MachineBasicBlock *CopyLeftBB = nullptr;
1116   for (MachineBasicBlock *Pred : MBB.predecessors()) {
1117     VNInfo *PVal = IntA.getVNInfoBefore(LIS->getMBBEndIdx(Pred));
1118     MachineInstr *DefMI = LIS->getInstructionFromIndex(PVal->def);
1119     if (!DefMI || !DefMI->isFullCopy()) {
1120       CopyLeftBB = Pred;
1121       continue;
1122     }
1123     // Check DefMI is a reverse copy and it is in BB Pred.
1124     if (DefMI->getOperand(0).getReg() != IntA.reg() ||
1125         DefMI->getOperand(1).getReg() != IntB.reg() ||
1126         DefMI->getParent() != Pred) {
1127       CopyLeftBB = Pred;
1128       continue;
1129     }
1130     // If there is any other def of B after DefMI and before the end of Pred,
1131     // we need to keep the copy of B = A at the end of Pred if we remove
1132     // B = A from MBB.
1133     bool ValB_Changed = false;
1134     for (auto *VNI : IntB.valnos) {
1135       if (VNI->isUnused())
1136         continue;
1137       if (PVal->def < VNI->def && VNI->def < LIS->getMBBEndIdx(Pred)) {
1138         ValB_Changed = true;
1139         break;
1140       }
1141     }
1142     if (ValB_Changed) {
1143       CopyLeftBB = Pred;
1144       continue;
1145     }
1146     FoundReverseCopy = true;
1147   }
1148 
1149   // If no reverse copy is found in predecessors, nothing to do.
1150   if (!FoundReverseCopy)
1151     return false;
1152 
1153   // If CopyLeftBB is nullptr, it means every predecessor of MBB contains
1154   // reverse copy, CopyMI can be removed trivially if only IntA/IntB is updated.
1155   // If CopyLeftBB is not nullptr, move CopyMI from MBB to CopyLeftBB and
1156   // update IntA/IntB.
1157   //
1158   // If CopyLeftBB is not nullptr, ensure CopyLeftBB has a single succ so
1159   // MBB is hotter than CopyLeftBB.
1160   if (CopyLeftBB && CopyLeftBB->succ_size() > 1)
1161     return false;
1162 
1163   // Now (almost sure it's) ok to move copy.
1164   if (CopyLeftBB) {
1165     // Position in CopyLeftBB where we should insert new copy.
1166     auto InsPos = CopyLeftBB->getFirstTerminator();
1167 
1168     // Make sure that B isn't referenced in the terminators (if any) at the end
1169     // of the predecessor since we're about to insert a new definition of B
1170     // before them.
1171     if (InsPos != CopyLeftBB->end()) {
1172       SlotIndex InsPosIdx = LIS->getInstructionIndex(*InsPos).getRegSlot(true);
1173       if (IntB.overlaps(InsPosIdx, LIS->getMBBEndIdx(CopyLeftBB)))
1174         return false;
1175     }
1176 
1177     LLVM_DEBUG(dbgs() << "\tremovePartialRedundancy: Move the copy to "
1178                       << printMBBReference(*CopyLeftBB) << '\t' << CopyMI);
1179 
1180     // Insert new copy to CopyLeftBB.
1181     MachineInstr *NewCopyMI = BuildMI(*CopyLeftBB, InsPos, CopyMI.getDebugLoc(),
1182                                       TII->get(TargetOpcode::COPY), IntB.reg())
1183                                   .addReg(IntA.reg());
1184     SlotIndex NewCopyIdx =
1185         LIS->InsertMachineInstrInMaps(*NewCopyMI).getRegSlot();
1186     IntB.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
1187     for (LiveInterval::SubRange &SR : IntB.subranges())
1188       SR.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
1189 
1190     // If the newly created Instruction has an address of an instruction that was
1191     // deleted before (object recycled by the allocator) it needs to be removed from
1192     // the deleted list.
1193     ErasedInstrs.erase(NewCopyMI);
1194   } else {
1195     LLVM_DEBUG(dbgs() << "\tremovePartialRedundancy: Remove the copy from "
1196                       << printMBBReference(MBB) << '\t' << CopyMI);
1197   }
1198 
1199   // Remove CopyMI.
1200   // Note: This is fine to remove the copy before updating the live-ranges.
1201   // While updating the live-ranges, we only look at slot indices and
1202   // never go back to the instruction.
1203   // Mark instructions as deleted.
1204   deleteInstr(&CopyMI);
1205 
1206   // Update the liveness.
1207   SmallVector<SlotIndex, 8> EndPoints;
1208   VNInfo *BValNo = IntB.Query(CopyIdx).valueOutOrDead();
1209   LIS->pruneValue(*static_cast<LiveRange *>(&IntB), CopyIdx.getRegSlot(),
1210                   &EndPoints);
1211   BValNo->markUnused();
1212   // Extend IntB to the EndPoints of its original live interval.
1213   LIS->extendToIndices(IntB, EndPoints);
1214 
1215   // Now, do the same for its subranges.
1216   for (LiveInterval::SubRange &SR : IntB.subranges()) {
1217     EndPoints.clear();
1218     VNInfo *BValNo = SR.Query(CopyIdx).valueOutOrDead();
1219     assert(BValNo && "All sublanes should be live");
1220     LIS->pruneValue(SR, CopyIdx.getRegSlot(), &EndPoints);
1221     BValNo->markUnused();
1222     // We can have a situation where the result of the original copy is live,
1223     // but is immediately dead in this subrange, e.g. [336r,336d:0). That makes
1224     // the copy appear as an endpoint from pruneValue(), but we don't want it
1225     // to because the copy has been removed.  We can go ahead and remove that
1226     // endpoint; there is no other situation here that there could be a use at
1227     // the same place as we know that the copy is a full copy.
1228     for (unsigned I = 0; I != EndPoints.size(); ) {
1229       if (SlotIndex::isSameInstr(EndPoints[I], CopyIdx)) {
1230         EndPoints[I] = EndPoints.back();
1231         EndPoints.pop_back();
1232         continue;
1233       }
1234       ++I;
1235     }
1236     SmallVector<SlotIndex, 8> Undefs;
1237     IntB.computeSubRangeUndefs(Undefs, SR.LaneMask, *MRI,
1238                                *LIS->getSlotIndexes());
1239     LIS->extendToIndices(SR, EndPoints, Undefs);
1240   }
1241   // If any dead defs were extended, truncate them.
1242   shrinkToUses(&IntB);
1243 
1244   // Finally, update the live-range of IntA.
1245   shrinkToUses(&IntA);
1246   return true;
1247 }
1248 
1249 /// Returns true if @p MI defines the full vreg @p Reg, as opposed to just
1250 /// defining a subregister.
1251 static bool definesFullReg(const MachineInstr &MI, Register Reg) {
1252   assert(!Reg.isPhysical() && "This code cannot handle physreg aliasing");
1253 
1254   for (const MachineOperand &Op : MI.all_defs()) {
1255     if (Op.getReg() != Reg)
1256       continue;
1257     // Return true if we define the full register or don't care about the value
1258     // inside other subregisters.
1259     if (Op.getSubReg() == 0 || Op.isUndef())
1260       return true;
1261   }
1262   return false;
1263 }
1264 
1265 bool RegisterCoalescer::reMaterializeTrivialDef(const CoalescerPair &CP,
1266                                                 MachineInstr *CopyMI,
1267                                                 bool &IsDefCopy) {
1268   IsDefCopy = false;
1269   Register SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg();
1270   unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx();
1271   Register DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();
1272   unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx();
1273   if (SrcReg.isPhysical())
1274     return false;
1275 
1276   LiveInterval &SrcInt = LIS->getInterval(SrcReg);
1277   SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);
1278   VNInfo *ValNo = SrcInt.Query(CopyIdx).valueIn();
1279   if (!ValNo)
1280     return false;
1281   if (ValNo->isPHIDef() || ValNo->isUnused())
1282     return false;
1283   MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def);
1284   if (!DefMI)
1285     return false;
1286   if (DefMI->isCopyLike()) {
1287     IsDefCopy = true;
1288     return false;
1289   }
1290   if (!TII->isAsCheapAsAMove(*DefMI))
1291     return false;
1292 
1293   SmallVector<Register, 8> NewRegs;
1294   LiveRangeEdit Edit(&SrcInt, NewRegs, *MF, *LIS, nullptr, this);
1295   if (!Edit.checkRematerializable(ValNo, DefMI))
1296     return false;
1297 
1298   if (!definesFullReg(*DefMI, SrcReg))
1299     return false;
1300   bool SawStore = false;
1301   if (!DefMI->isSafeToMove(AA, SawStore))
1302     return false;
1303   const MCInstrDesc &MCID = DefMI->getDesc();
1304   if (MCID.getNumDefs() != 1)
1305     return false;
1306   // Only support subregister destinations when the def is read-undef.
1307   MachineOperand &DstOperand = CopyMI->getOperand(0);
1308   Register CopyDstReg = DstOperand.getReg();
1309   if (DstOperand.getSubReg() && !DstOperand.isUndef())
1310     return false;
1311 
1312   // If both SrcIdx and DstIdx are set, correct rematerialization would widen
1313   // the register substantially (beyond both source and dest size). This is bad
1314   // for performance since it can cascade through a function, introducing many
1315   // extra spills and fills (e.g. ARM can easily end up copying QQQQPR registers
1316   // around after a few subreg copies).
1317   if (SrcIdx && DstIdx)
1318     return false;
1319 
1320   const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF);
1321   if (!DefMI->isImplicitDef()) {
1322     if (DstReg.isPhysical()) {
1323       Register NewDstReg = DstReg;
1324 
1325       unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(),
1326                                               DefMI->getOperand(0).getSubReg());
1327       if (NewDstIdx)
1328         NewDstReg = TRI->getSubReg(DstReg, NewDstIdx);
1329 
1330       // Finally, make sure that the physical subregister that will be
1331       // constructed later is permitted for the instruction.
1332       if (!DefRC->contains(NewDstReg))
1333         return false;
1334     } else {
1335       // Theoretically, some stack frame reference could exist. Just make sure
1336       // it hasn't actually happened.
1337       assert(DstReg.isVirtual() &&
1338              "Only expect to deal with virtual or physical registers");
1339     }
1340   }
1341 
1342   LiveRangeEdit::Remat RM(ValNo);
1343   RM.OrigMI = DefMI;
1344   if (!Edit.canRematerializeAt(RM, ValNo, CopyIdx, true))
1345     return false;
1346 
1347   DebugLoc DL = CopyMI->getDebugLoc();
1348   MachineBasicBlock *MBB = CopyMI->getParent();
1349   MachineBasicBlock::iterator MII =
1350     std::next(MachineBasicBlock::iterator(CopyMI));
1351   Edit.rematerializeAt(*MBB, MII, DstReg, RM, *TRI, false, SrcIdx, CopyMI);
1352   MachineInstr &NewMI = *std::prev(MII);
1353   NewMI.setDebugLoc(DL);
1354 
1355   // In a situation like the following:
1356   //     %0:subreg = instr              ; DefMI, subreg = DstIdx
1357   //     %1        = copy %0:subreg ; CopyMI, SrcIdx = 0
1358   // instead of widening %1 to the register class of %0 simply do:
1359   //     %1 = instr
1360   const TargetRegisterClass *NewRC = CP.getNewRC();
1361   if (DstIdx != 0) {
1362     MachineOperand &DefMO = NewMI.getOperand(0);
1363     if (DefMO.getSubReg() == DstIdx) {
1364       assert(SrcIdx == 0 && CP.isFlipped()
1365              && "Shouldn't have SrcIdx+DstIdx at this point");
1366       const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
1367       const TargetRegisterClass *CommonRC =
1368         TRI->getCommonSubClass(DefRC, DstRC);
1369       if (CommonRC != nullptr) {
1370         NewRC = CommonRC;
1371 
1372         // Instruction might contain "undef %0:subreg" as use operand:
1373         //   %0:subreg = instr op_1, ..., op_N, undef %0:subreg, op_N+2, ...
1374         //
1375         // Need to check all operands.
1376         for (MachineOperand &MO : NewMI.operands()) {
1377           if (MO.isReg() && MO.getReg() == DstReg && MO.getSubReg() == DstIdx) {
1378             MO.setSubReg(0);
1379           }
1380         }
1381 
1382         DstIdx = 0;
1383         DefMO.setIsUndef(false); // Only subregs can have def+undef.
1384       }
1385     }
1386   }
1387 
1388   // CopyMI may have implicit operands, save them so that we can transfer them
1389   // over to the newly materialized instruction after CopyMI is removed.
1390   SmallVector<MachineOperand, 4> ImplicitOps;
1391   ImplicitOps.reserve(CopyMI->getNumOperands() -
1392                       CopyMI->getDesc().getNumOperands());
1393   for (unsigned I = CopyMI->getDesc().getNumOperands(),
1394                 E = CopyMI->getNumOperands();
1395        I != E; ++I) {
1396     MachineOperand &MO = CopyMI->getOperand(I);
1397     if (MO.isReg()) {
1398       assert(MO.isImplicit() && "No explicit operands after implicit operands.");
1399       // Discard VReg implicit defs.
1400       if (MO.getReg().isPhysical())
1401         ImplicitOps.push_back(MO);
1402     }
1403   }
1404 
1405   CopyMI->eraseFromParent();
1406   ErasedInstrs.insert(CopyMI);
1407 
1408   // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86).
1409   // We need to remember these so we can add intervals once we insert
1410   // NewMI into SlotIndexes.
1411   SmallVector<MCRegister, 4> NewMIImplDefs;
1412   for (unsigned i = NewMI.getDesc().getNumOperands(),
1413                 e = NewMI.getNumOperands();
1414        i != e; ++i) {
1415     MachineOperand &MO = NewMI.getOperand(i);
1416     if (MO.isReg() && MO.isDef()) {
1417       assert(MO.isImplicit() && MO.isDead() && MO.getReg().isPhysical());
1418       NewMIImplDefs.push_back(MO.getReg().asMCReg());
1419     }
1420   }
1421 
1422   if (DstReg.isVirtual()) {
1423     unsigned NewIdx = NewMI.getOperand(0).getSubReg();
1424 
1425     if (DefRC != nullptr) {
1426       if (NewIdx)
1427         NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);
1428       else
1429         NewRC = TRI->getCommonSubClass(NewRC, DefRC);
1430       assert(NewRC && "subreg chosen for remat incompatible with instruction");
1431     }
1432     // Remap subranges to new lanemask and change register class.
1433     LiveInterval &DstInt = LIS->getInterval(DstReg);
1434     for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1435       SR.LaneMask = TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask);
1436     }
1437     MRI->setRegClass(DstReg, NewRC);
1438 
1439     // Update machine operands and add flags.
1440     updateRegDefsUses(DstReg, DstReg, DstIdx);
1441     NewMI.getOperand(0).setSubReg(NewIdx);
1442     // updateRegDefUses can add an "undef" flag to the definition, since
1443     // it will replace DstReg with DstReg.DstIdx. If NewIdx is 0, make
1444     // sure that "undef" is not set.
1445     if (NewIdx == 0)
1446       NewMI.getOperand(0).setIsUndef(false);
1447     // Add dead subregister definitions if we are defining the whole register
1448     // but only part of it is live.
1449     // This could happen if the rematerialization instruction is rematerializing
1450     // more than actually is used in the register.
1451     // An example would be:
1452     // %1 = LOAD CONSTANTS 5, 8 ; Loading both 5 and 8 in different subregs
1453     // ; Copying only part of the register here, but the rest is undef.
1454     // %2:sub_16bit<def, read-undef> = COPY %1:sub_16bit
1455     // ==>
1456     // ; Materialize all the constants but only using one
1457     // %2 = LOAD_CONSTANTS 5, 8
1458     //
1459     // at this point for the part that wasn't defined before we could have
1460     // subranges missing the definition.
1461     if (NewIdx == 0 && DstInt.hasSubRanges()) {
1462       SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);
1463       SlotIndex DefIndex =
1464           CurrIdx.getRegSlot(NewMI.getOperand(0).isEarlyClobber());
1465       LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(DstReg);
1466       VNInfo::Allocator& Alloc = LIS->getVNInfoAllocator();
1467       for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1468         if (!SR.liveAt(DefIndex))
1469           SR.createDeadDef(DefIndex, Alloc);
1470         MaxMask &= ~SR.LaneMask;
1471       }
1472       if (MaxMask.any()) {
1473         LiveInterval::SubRange *SR = DstInt.createSubRange(Alloc, MaxMask);
1474         SR->createDeadDef(DefIndex, Alloc);
1475       }
1476     }
1477 
1478     // Make sure that the subrange for resultant undef is removed
1479     // For example:
1480     //   %1:sub1<def,read-undef> = LOAD CONSTANT 1
1481     //   %2 = COPY %1
1482     // ==>
1483     //   %2:sub1<def, read-undef> = LOAD CONSTANT 1
1484     //     ; Correct but need to remove the subrange for %2:sub0
1485     //     ; as it is now undef
1486     if (NewIdx != 0 && DstInt.hasSubRanges()) {
1487       // The affected subregister segments can be removed.
1488       SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);
1489       LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(NewIdx);
1490       bool UpdatedSubRanges = false;
1491       SlotIndex DefIndex =
1492           CurrIdx.getRegSlot(NewMI.getOperand(0).isEarlyClobber());
1493       VNInfo::Allocator &Alloc = LIS->getVNInfoAllocator();
1494       for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1495         if ((SR.LaneMask & DstMask).none()) {
1496           LLVM_DEBUG(dbgs()
1497                      << "Removing undefined SubRange "
1498                      << PrintLaneMask(SR.LaneMask) << " : " << SR << "\n");
1499 
1500           if (VNInfo *RmValNo = SR.getVNInfoAt(CurrIdx.getRegSlot())) {
1501             // VNI is in ValNo - remove any segments in this SubRange that have
1502             // this ValNo
1503             SR.removeValNo(RmValNo);
1504           }
1505 
1506           // We may not have a defined value at this point, but still need to
1507           // clear out any empty subranges tentatively created by
1508           // updateRegDefUses. The original subrange def may have only undefed
1509           // some lanes.
1510           UpdatedSubRanges = true;
1511         } else {
1512           // We know that this lane is defined by this instruction,
1513           // but at this point it may be empty because it is not used by
1514           // anything. This happens when updateRegDefUses adds the missing
1515           // lanes. Assign that lane a dead def so that the interferences
1516           // are properly modeled.
1517           if (SR.empty())
1518             SR.createDeadDef(DefIndex, Alloc);
1519         }
1520       }
1521       if (UpdatedSubRanges)
1522         DstInt.removeEmptySubRanges();
1523     }
1524   } else if (NewMI.getOperand(0).getReg() != CopyDstReg) {
1525     // The New instruction may be defining a sub-register of what's actually
1526     // been asked for. If so it must implicitly define the whole thing.
1527     assert(DstReg.isPhysical() &&
1528            "Only expect virtual or physical registers in remat");
1529     NewMI.getOperand(0).setIsDead(true);
1530     NewMI.addOperand(MachineOperand::CreateReg(
1531         CopyDstReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/));
1532     // Record small dead def live-ranges for all the subregisters
1533     // of the destination register.
1534     // Otherwise, variables that live through may miss some
1535     // interferences, thus creating invalid allocation.
1536     // E.g., i386 code:
1537     // %1 = somedef ; %1 GR8
1538     // %2 = remat ; %2 GR32
1539     // CL = COPY %2.sub_8bit
1540     // = somedef %1 ; %1 GR8
1541     // =>
1542     // %1 = somedef ; %1 GR8
1543     // dead ECX = remat ; implicit-def CL
1544     // = somedef %1 ; %1 GR8
1545     // %1 will see the interferences with CL but not with CH since
1546     // no live-ranges would have been created for ECX.
1547     // Fix that!
1548     SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
1549     for (MCRegUnit Unit : TRI->regunits(NewMI.getOperand(0).getReg()))
1550       if (LiveRange *LR = LIS->getCachedRegUnit(Unit))
1551         LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
1552   }
1553 
1554   if (NewMI.getOperand(0).getSubReg())
1555     NewMI.getOperand(0).setIsUndef();
1556 
1557   // Transfer over implicit operands to the rematerialized instruction.
1558   for (MachineOperand &MO : ImplicitOps)
1559     NewMI.addOperand(MO);
1560 
1561   SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
1562   for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) {
1563     MCRegister Reg = NewMIImplDefs[i];
1564     for (MCRegUnit Unit : TRI->regunits(Reg))
1565       if (LiveRange *LR = LIS->getCachedRegUnit(Unit))
1566         LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
1567   }
1568 
1569   LLVM_DEBUG(dbgs() << "Remat: " << NewMI);
1570   ++NumReMats;
1571 
1572   // If the virtual SrcReg is completely eliminated, update all DBG_VALUEs
1573   // to describe DstReg instead.
1574   if (MRI->use_nodbg_empty(SrcReg)) {
1575     for (MachineOperand &UseMO :
1576          llvm::make_early_inc_range(MRI->use_operands(SrcReg))) {
1577       MachineInstr *UseMI = UseMO.getParent();
1578       if (UseMI->isDebugInstr()) {
1579         if (DstReg.isPhysical())
1580           UseMO.substPhysReg(DstReg, *TRI);
1581         else
1582           UseMO.setReg(DstReg);
1583         // Move the debug value directly after the def of the rematerialized
1584         // value in DstReg.
1585         MBB->splice(std::next(NewMI.getIterator()), UseMI->getParent(), UseMI);
1586         LLVM_DEBUG(dbgs() << "\t\tupdated: " << *UseMI);
1587       }
1588     }
1589   }
1590 
1591   if (ToBeUpdated.count(SrcReg))
1592     return true;
1593 
1594   unsigned NumCopyUses = 0;
1595   for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) {
1596     if (UseMO.getParent()->isCopyLike())
1597       NumCopyUses++;
1598   }
1599   if (NumCopyUses < LateRematUpdateThreshold) {
1600     // The source interval can become smaller because we removed a use.
1601     shrinkToUses(&SrcInt, &DeadDefs);
1602     if (!DeadDefs.empty())
1603       eliminateDeadDefs(&Edit);
1604   } else {
1605     ToBeUpdated.insert(SrcReg);
1606   }
1607   return true;
1608 }
1609 
1610 MachineInstr *RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI) {
1611   // ProcessImplicitDefs may leave some copies of <undef> values, it only
1612   // removes local variables. When we have a copy like:
1613   //
1614   //   %1 = COPY undef %2
1615   //
1616   // We delete the copy and remove the corresponding value number from %1.
1617   // Any uses of that value number are marked as <undef>.
1618 
1619   // Note that we do not query CoalescerPair here but redo isMoveInstr as the
1620   // CoalescerPair may have a new register class with adjusted subreg indices
1621   // at this point.
1622   Register SrcReg, DstReg;
1623   unsigned SrcSubIdx = 0, DstSubIdx = 0;
1624   if(!isMoveInstr(*TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
1625     return nullptr;
1626 
1627   SlotIndex Idx = LIS->getInstructionIndex(*CopyMI);
1628   const LiveInterval &SrcLI = LIS->getInterval(SrcReg);
1629   // CopyMI is undef iff SrcReg is not live before the instruction.
1630   if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) {
1631     LaneBitmask SrcMask = TRI->getSubRegIndexLaneMask(SrcSubIdx);
1632     for (const LiveInterval::SubRange &SR : SrcLI.subranges()) {
1633       if ((SR.LaneMask & SrcMask).none())
1634         continue;
1635       if (SR.liveAt(Idx))
1636         return nullptr;
1637     }
1638   } else if (SrcLI.liveAt(Idx))
1639     return nullptr;
1640 
1641   // If the undef copy defines a live-out value (i.e. an input to a PHI def),
1642   // then replace it with an IMPLICIT_DEF.
1643   LiveInterval &DstLI = LIS->getInterval(DstReg);
1644   SlotIndex RegIndex = Idx.getRegSlot();
1645   LiveRange::Segment *Seg = DstLI.getSegmentContaining(RegIndex);
1646   assert(Seg != nullptr && "No segment for defining instruction");
1647   VNInfo *V = DstLI.getVNInfoAt(Seg->end);
1648 
1649   // The source interval may also have been on an undef use, in which case the
1650   // copy introduced a live value.
1651   if (((V && V->isPHIDef()) || (!V && !DstLI.liveAt(Idx)))) {
1652     CopyMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
1653     for (unsigned i = CopyMI->getNumOperands(); i != 0; --i) {
1654       MachineOperand &MO = CopyMI->getOperand(i-1);
1655       if (MO.isReg() && MO.isUse())
1656         CopyMI->removeOperand(i-1);
1657     }
1658     LLVM_DEBUG(dbgs() << "\tReplaced copy of <undef> value with an "
1659                "implicit def\n");
1660     return CopyMI;
1661   }
1662 
1663   // Remove any DstReg segments starting at the instruction.
1664   LLVM_DEBUG(dbgs() << "\tEliminating copy of <undef> value\n");
1665 
1666   // Remove value or merge with previous one in case of a subregister def.
1667   if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {
1668     VNInfo *VNI = DstLI.getVNInfoAt(RegIndex);
1669     DstLI.MergeValueNumberInto(VNI, PrevVNI);
1670 
1671     // The affected subregister segments can be removed.
1672     LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx);
1673     for (LiveInterval::SubRange &SR : DstLI.subranges()) {
1674       if ((SR.LaneMask & DstMask).none())
1675         continue;
1676 
1677       VNInfo *SVNI = SR.getVNInfoAt(RegIndex);
1678       assert(SVNI != nullptr && SlotIndex::isSameInstr(SVNI->def, RegIndex));
1679       SR.removeValNo(SVNI);
1680     }
1681     DstLI.removeEmptySubRanges();
1682   } else
1683     LIS->removeVRegDefAt(DstLI, RegIndex);
1684 
1685   // Mark uses as undef.
1686   for (MachineOperand &MO : MRI->reg_nodbg_operands(DstReg)) {
1687     if (MO.isDef() /*|| MO.isUndef()*/)
1688       continue;
1689     const MachineInstr &MI = *MO.getParent();
1690     SlotIndex UseIdx = LIS->getInstructionIndex(MI);
1691     LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
1692     bool isLive;
1693     if (!UseMask.all() && DstLI.hasSubRanges()) {
1694       isLive = false;
1695       for (const LiveInterval::SubRange &SR : DstLI.subranges()) {
1696         if ((SR.LaneMask & UseMask).none())
1697           continue;
1698         if (SR.liveAt(UseIdx)) {
1699           isLive = true;
1700           break;
1701         }
1702       }
1703     } else
1704       isLive = DstLI.liveAt(UseIdx);
1705     if (isLive)
1706       continue;
1707     MO.setIsUndef(true);
1708     LLVM_DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI);
1709   }
1710 
1711   // A def of a subregister may be a use of the other subregisters, so
1712   // deleting a def of a subregister may also remove uses. Since CopyMI
1713   // is still part of the function (but about to be erased), mark all
1714   // defs of DstReg in it as <undef>, so that shrinkToUses would
1715   // ignore them.
1716   for (MachineOperand &MO : CopyMI->all_defs())
1717     if (MO.getReg() == DstReg)
1718       MO.setIsUndef(true);
1719   LIS->shrinkToUses(&DstLI);
1720 
1721   return CopyMI;
1722 }
1723 
1724 void RegisterCoalescer::addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
1725                                      MachineOperand &MO, unsigned SubRegIdx) {
1726   LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubRegIdx);
1727   if (MO.isDef())
1728     Mask = ~Mask;
1729   bool IsUndef = true;
1730   for (const LiveInterval::SubRange &S : Int.subranges()) {
1731     if ((S.LaneMask & Mask).none())
1732       continue;
1733     if (S.liveAt(UseIdx)) {
1734       IsUndef = false;
1735       break;
1736     }
1737   }
1738   if (IsUndef) {
1739     MO.setIsUndef(true);
1740     // We found out some subregister use is actually reading an undefined
1741     // value. In some cases the whole vreg has become undefined at this
1742     // point so we have to potentially shrink the main range if the
1743     // use was ending a live segment there.
1744     LiveQueryResult Q = Int.Query(UseIdx);
1745     if (Q.valueOut() == nullptr)
1746       ShrinkMainRange = true;
1747   }
1748 }
1749 
1750 void RegisterCoalescer::updateRegDefsUses(Register SrcReg, Register DstReg,
1751                                           unsigned SubIdx) {
1752   bool DstIsPhys = DstReg.isPhysical();
1753   LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg);
1754 
1755   if (DstInt && DstInt->hasSubRanges() && DstReg != SrcReg) {
1756     for (MachineOperand &MO : MRI->reg_operands(DstReg)) {
1757       unsigned SubReg = MO.getSubReg();
1758       if (SubReg == 0 || MO.isUndef())
1759         continue;
1760       MachineInstr &MI = *MO.getParent();
1761       if (MI.isDebugInstr())
1762         continue;
1763       SlotIndex UseIdx = LIS->getInstructionIndex(MI).getRegSlot(true);
1764       addUndefFlag(*DstInt, UseIdx, MO, SubReg);
1765     }
1766   }
1767 
1768   SmallPtrSet<MachineInstr*, 8> Visited;
1769   for (MachineRegisterInfo::reg_instr_iterator
1770        I = MRI->reg_instr_begin(SrcReg), E = MRI->reg_instr_end();
1771        I != E; ) {
1772     MachineInstr *UseMI = &*(I++);
1773 
1774     // Each instruction can only be rewritten once because sub-register
1775     // composition is not always idempotent. When SrcReg != DstReg, rewriting
1776     // the UseMI operands removes them from the SrcReg use-def chain, but when
1777     // SrcReg is DstReg we could encounter UseMI twice if it has multiple
1778     // operands mentioning the virtual register.
1779     if (SrcReg == DstReg && !Visited.insert(UseMI).second)
1780       continue;
1781 
1782     SmallVector<unsigned,8> Ops;
1783     bool Reads, Writes;
1784     std::tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);
1785 
1786     // If SrcReg wasn't read, it may still be the case that DstReg is live-in
1787     // because SrcReg is a sub-register.
1788     if (DstInt && !Reads && SubIdx && !UseMI->isDebugInstr())
1789       Reads = DstInt->liveAt(LIS->getInstructionIndex(*UseMI));
1790 
1791     // Replace SrcReg with DstReg in all UseMI operands.
1792     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1793       MachineOperand &MO = UseMI->getOperand(Ops[i]);
1794 
1795       // Adjust <undef> flags in case of sub-register joins. We don't want to
1796       // turn a full def into a read-modify-write sub-register def and vice
1797       // versa.
1798       if (SubIdx && MO.isDef())
1799         MO.setIsUndef(!Reads);
1800 
1801       // A subreg use of a partially undef (super) register may be a complete
1802       // undef use now and then has to be marked that way.
1803       if (MO.isUse() && !DstIsPhys) {
1804         unsigned SubUseIdx = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());
1805         if (SubUseIdx != 0 && MRI->shouldTrackSubRegLiveness(DstReg)) {
1806           if (!DstInt->hasSubRanges()) {
1807             BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
1808             LaneBitmask FullMask = MRI->getMaxLaneMaskForVReg(DstInt->reg());
1809             LaneBitmask UsedLanes = TRI->getSubRegIndexLaneMask(SubIdx);
1810             LaneBitmask UnusedLanes = FullMask & ~UsedLanes;
1811             DstInt->createSubRangeFrom(Allocator, UsedLanes, *DstInt);
1812             // The unused lanes are just empty live-ranges at this point.
1813             // It is the caller responsibility to set the proper
1814             // dead segments if there is an actual dead def of the
1815             // unused lanes. This may happen with rematerialization.
1816             DstInt->createSubRange(Allocator, UnusedLanes);
1817           }
1818           SlotIndex MIIdx = UseMI->isDebugInstr()
1819             ? LIS->getSlotIndexes()->getIndexBefore(*UseMI)
1820             : LIS->getInstructionIndex(*UseMI);
1821           SlotIndex UseIdx = MIIdx.getRegSlot(true);
1822           addUndefFlag(*DstInt, UseIdx, MO, SubUseIdx);
1823         }
1824       }
1825 
1826       if (DstIsPhys)
1827         MO.substPhysReg(DstReg, *TRI);
1828       else
1829         MO.substVirtReg(DstReg, SubIdx, *TRI);
1830     }
1831 
1832     LLVM_DEBUG({
1833       dbgs() << "\t\tupdated: ";
1834       if (!UseMI->isDebugInstr())
1835         dbgs() << LIS->getInstructionIndex(*UseMI) << "\t";
1836       dbgs() << *UseMI;
1837     });
1838   }
1839 }
1840 
1841 bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
1842   // Always join simple intervals that are defined by a single copy from a
1843   // reserved register. This doesn't increase register pressure, so it is
1844   // always beneficial.
1845   if (!MRI->isReserved(CP.getDstReg())) {
1846     LLVM_DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
1847     return false;
1848   }
1849 
1850   LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg());
1851   if (JoinVInt.containsOneValue())
1852     return true;
1853 
1854   LLVM_DEBUG(
1855       dbgs() << "\tCannot join complex intervals into reserved register.\n");
1856   return false;
1857 }
1858 
1859 bool RegisterCoalescer::copyValueUndefInPredecessors(
1860     LiveRange &S, const MachineBasicBlock *MBB, LiveQueryResult SLRQ) {
1861   for (const MachineBasicBlock *Pred : MBB->predecessors()) {
1862     SlotIndex PredEnd = LIS->getMBBEndIdx(Pred);
1863     if (VNInfo *V = S.getVNInfoAt(PredEnd.getPrevSlot())) {
1864       // If this is a self loop, we may be reading the same value.
1865       if (V->id != SLRQ.valueOutOrDead()->id)
1866         return false;
1867     }
1868   }
1869 
1870   return true;
1871 }
1872 
1873 void RegisterCoalescer::setUndefOnPrunedSubRegUses(LiveInterval &LI,
1874                                                    Register Reg,
1875                                                    LaneBitmask PrunedLanes) {
1876   // If we had other instructions in the segment reading the undef sublane
1877   // value, we need to mark them with undef.
1878   for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
1879     unsigned SubRegIdx = MO.getSubReg();
1880     if (SubRegIdx == 0 || MO.isUndef())
1881       continue;
1882 
1883     LaneBitmask SubRegMask = TRI->getSubRegIndexLaneMask(SubRegIdx);
1884     SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
1885     for (LiveInterval::SubRange &S : LI.subranges()) {
1886       if (!S.liveAt(Pos) && (PrunedLanes & SubRegMask).any()) {
1887         MO.setIsUndef();
1888         break;
1889       }
1890     }
1891   }
1892 
1893   LI.removeEmptySubRanges();
1894 
1895   // A def of a subregister may be a use of other register lanes. Replacing
1896   // such a def with a def of a different register will eliminate the use,
1897   // and may cause the recorded live range to be larger than the actual
1898   // liveness in the program IR.
1899   LIS->shrinkToUses(&LI);
1900 }
1901 
1902 bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
1903   Again = false;
1904   LLVM_DEBUG(dbgs() << LIS->getInstructionIndex(*CopyMI) << '\t' << *CopyMI);
1905 
1906   CoalescerPair CP(*TRI);
1907   if (!CP.setRegisters(CopyMI)) {
1908     LLVM_DEBUG(dbgs() << "\tNot coalescable.\n");
1909     return false;
1910   }
1911 
1912   if (CP.getNewRC()) {
1913     auto SrcRC = MRI->getRegClass(CP.getSrcReg());
1914     auto DstRC = MRI->getRegClass(CP.getDstReg());
1915     unsigned SrcIdx = CP.getSrcIdx();
1916     unsigned DstIdx = CP.getDstIdx();
1917     if (CP.isFlipped()) {
1918       std::swap(SrcIdx, DstIdx);
1919       std::swap(SrcRC, DstRC);
1920     }
1921     if (!TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,
1922                              CP.getNewRC(), *LIS)) {
1923       LLVM_DEBUG(dbgs() << "\tSubtarget bailed on coalescing.\n");
1924       return false;
1925     }
1926   }
1927 
1928   // Dead code elimination. This really should be handled by MachineDCE, but
1929   // sometimes dead copies slip through, and we can't generate invalid live
1930   // ranges.
1931   if (!CP.isPhys() && CopyMI->allDefsAreDead()) {
1932     LLVM_DEBUG(dbgs() << "\tCopy is dead.\n");
1933     DeadDefs.push_back(CopyMI);
1934     eliminateDeadDefs();
1935     return true;
1936   }
1937 
1938   // Eliminate undefs.
1939   if (!CP.isPhys()) {
1940     // If this is an IMPLICIT_DEF, leave it alone, but don't try to coalesce.
1941     if (MachineInstr *UndefMI = eliminateUndefCopy(CopyMI)) {
1942       if (UndefMI->isImplicitDef())
1943         return false;
1944       deleteInstr(CopyMI);
1945       return false;  // Not coalescable.
1946     }
1947   }
1948 
1949   // Coalesced copies are normally removed immediately, but transformations
1950   // like removeCopyByCommutingDef() can inadvertently create identity copies.
1951   // When that happens, just join the values and remove the copy.
1952   if (CP.getSrcReg() == CP.getDstReg()) {
1953     LiveInterval &LI = LIS->getInterval(CP.getSrcReg());
1954     LLVM_DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n');
1955     const SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);
1956     LiveQueryResult LRQ = LI.Query(CopyIdx);
1957     if (VNInfo *DefVNI = LRQ.valueDefined()) {
1958       VNInfo *ReadVNI = LRQ.valueIn();
1959       assert(ReadVNI && "No value before copy and no <undef> flag.");
1960       assert(ReadVNI != DefVNI && "Cannot read and define the same value.");
1961 
1962       // Track incoming undef lanes we need to eliminate from the subrange.
1963       LaneBitmask PrunedLanes;
1964       MachineBasicBlock *MBB = CopyMI->getParent();
1965 
1966       // Process subregister liveranges.
1967       for (LiveInterval::SubRange &S : LI.subranges()) {
1968         LiveQueryResult SLRQ = S.Query(CopyIdx);
1969         if (VNInfo *SDefVNI = SLRQ.valueDefined()) {
1970           if (VNInfo *SReadVNI = SLRQ.valueIn())
1971             SDefVNI = S.MergeValueNumberInto(SDefVNI, SReadVNI);
1972 
1973           // If this copy introduced an undef subrange from an incoming value,
1974           // we need to eliminate the undef live in values from the subrange.
1975           if (copyValueUndefInPredecessors(S, MBB, SLRQ)) {
1976             LLVM_DEBUG(dbgs() << "Incoming sublane value is undef at copy\n");
1977             PrunedLanes |= S.LaneMask;
1978             S.removeValNo(SDefVNI);
1979           }
1980         }
1981       }
1982 
1983       LI.MergeValueNumberInto(DefVNI, ReadVNI);
1984       if (PrunedLanes.any()) {
1985         LLVM_DEBUG(dbgs() << "Pruning undef incoming lanes: "
1986                           << PrunedLanes << '\n');
1987         setUndefOnPrunedSubRegUses(LI, CP.getSrcReg(), PrunedLanes);
1988       }
1989 
1990       LLVM_DEBUG(dbgs() << "\tMerged values:          " << LI << '\n');
1991     }
1992     deleteInstr(CopyMI);
1993     return true;
1994   }
1995 
1996   // Enforce policies.
1997   if (CP.isPhys()) {
1998     LLVM_DEBUG(dbgs() << "\tConsidering merging "
1999                       << printReg(CP.getSrcReg(), TRI) << " with "
2000                       << printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n');
2001     if (!canJoinPhys(CP)) {
2002       // Before giving up coalescing, if definition of source is defined by
2003       // trivial computation, try rematerializing it.
2004       bool IsDefCopy = false;
2005       if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
2006         return true;
2007       if (IsDefCopy)
2008         Again = true;  // May be possible to coalesce later.
2009       return false;
2010     }
2011   } else {
2012     // When possible, let DstReg be the larger interval.
2013     if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() >
2014                            LIS->getInterval(CP.getDstReg()).size())
2015       CP.flip();
2016 
2017     LLVM_DEBUG({
2018       dbgs() << "\tConsidering merging to "
2019              << TRI->getRegClassName(CP.getNewRC()) << " with ";
2020       if (CP.getDstIdx() && CP.getSrcIdx())
2021         dbgs() << printReg(CP.getDstReg()) << " in "
2022                << TRI->getSubRegIndexName(CP.getDstIdx()) << " and "
2023                << printReg(CP.getSrcReg()) << " in "
2024                << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n';
2025       else
2026         dbgs() << printReg(CP.getSrcReg(), TRI) << " in "
2027                << printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n';
2028     });
2029   }
2030 
2031   ShrinkMask = LaneBitmask::getNone();
2032   ShrinkMainRange = false;
2033 
2034   // Okay, attempt to join these two intervals.  On failure, this returns false.
2035   // Otherwise, if one of the intervals being joined is a physreg, this method
2036   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
2037   // been modified, so we can use this information below to update aliases.
2038   if (!joinIntervals(CP)) {
2039     // Coalescing failed.
2040 
2041     // If definition of source is defined by trivial computation, try
2042     // rematerializing it.
2043     bool IsDefCopy = false;
2044     if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
2045       return true;
2046 
2047     // If we can eliminate the copy without merging the live segments, do so
2048     // now.
2049     if (!CP.isPartial() && !CP.isPhys()) {
2050       bool Changed = adjustCopiesBackFrom(CP, CopyMI);
2051       bool Shrink = false;
2052       if (!Changed)
2053         std::tie(Changed, Shrink) = removeCopyByCommutingDef(CP, CopyMI);
2054       if (Changed) {
2055         deleteInstr(CopyMI);
2056         if (Shrink) {
2057           Register DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();
2058           LiveInterval &DstLI = LIS->getInterval(DstReg);
2059           shrinkToUses(&DstLI);
2060           LLVM_DEBUG(dbgs() << "\t\tshrunk:   " << DstLI << '\n');
2061         }
2062         LLVM_DEBUG(dbgs() << "\tTrivial!\n");
2063         return true;
2064       }
2065     }
2066 
2067     // Try and see if we can partially eliminate the copy by moving the copy to
2068     // its predecessor.
2069     if (!CP.isPartial() && !CP.isPhys())
2070       if (removePartialRedundancy(CP, *CopyMI))
2071         return true;
2072 
2073     // Otherwise, we are unable to join the intervals.
2074     LLVM_DEBUG(dbgs() << "\tInterference!\n");
2075     Again = true;  // May be possible to coalesce later.
2076     return false;
2077   }
2078 
2079   // Coalescing to a virtual register that is of a sub-register class of the
2080   // other. Make sure the resulting register is set to the right register class.
2081   if (CP.isCrossClass()) {
2082     ++numCrossRCs;
2083     MRI->setRegClass(CP.getDstReg(), CP.getNewRC());
2084   }
2085 
2086   // Removing sub-register copies can ease the register class constraints.
2087   // Make sure we attempt to inflate the register class of DstReg.
2088   if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC()))
2089     InflateRegs.push_back(CP.getDstReg());
2090 
2091   // CopyMI has been erased by joinIntervals at this point. Remove it from
2092   // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back
2093   // to the work list. This keeps ErasedInstrs from growing needlessly.
2094   ErasedInstrs.erase(CopyMI);
2095 
2096   // Rewrite all SrcReg operands to DstReg.
2097   // Also update DstReg operands to include DstIdx if it is set.
2098   if (CP.getDstIdx())
2099     updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx());
2100   updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx());
2101 
2102   // Shrink subregister ranges if necessary.
2103   if (ShrinkMask.any()) {
2104     LiveInterval &LI = LIS->getInterval(CP.getDstReg());
2105     for (LiveInterval::SubRange &S : LI.subranges()) {
2106       if ((S.LaneMask & ShrinkMask).none())
2107         continue;
2108       LLVM_DEBUG(dbgs() << "Shrink LaneUses (Lane " << PrintLaneMask(S.LaneMask)
2109                         << ")\n");
2110       LIS->shrinkToUses(S, LI.reg());
2111       ShrinkMainRange = true;
2112     }
2113     LI.removeEmptySubRanges();
2114   }
2115 
2116   // CP.getSrcReg()'s live interval has been merged into CP.getDstReg's live
2117   // interval. Since CP.getSrcReg() is in ToBeUpdated set and its live interval
2118   // is not up-to-date, need to update the merged live interval here.
2119   if (ToBeUpdated.count(CP.getSrcReg()))
2120     ShrinkMainRange = true;
2121 
2122   if (ShrinkMainRange) {
2123     LiveInterval &LI = LIS->getInterval(CP.getDstReg());
2124     shrinkToUses(&LI);
2125   }
2126 
2127   // SrcReg is guaranteed to be the register whose live interval that is
2128   // being merged.
2129   LIS->removeInterval(CP.getSrcReg());
2130 
2131   // Update regalloc hint.
2132   TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);
2133 
2134   LLVM_DEBUG({
2135     dbgs() << "\tSuccess: " << printReg(CP.getSrcReg(), TRI, CP.getSrcIdx())
2136            << " -> " << printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
2137     dbgs() << "\tResult = ";
2138     if (CP.isPhys())
2139       dbgs() << printReg(CP.getDstReg(), TRI);
2140     else
2141       dbgs() << LIS->getInterval(CP.getDstReg());
2142     dbgs() << '\n';
2143   });
2144 
2145   ++numJoins;
2146   return true;
2147 }
2148 
2149 bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
2150   Register DstReg = CP.getDstReg();
2151   Register SrcReg = CP.getSrcReg();
2152   assert(CP.isPhys() && "Must be a physreg copy");
2153   assert(MRI->isReserved(DstReg) && "Not a reserved register");
2154   LiveInterval &RHS = LIS->getInterval(SrcReg);
2155   LLVM_DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n');
2156 
2157   assert(RHS.containsOneValue() && "Invalid join with reserved register");
2158 
2159   // Optimization for reserved registers like ESP. We can only merge with a
2160   // reserved physreg if RHS has a single value that is a copy of DstReg.
2161   // The live range of the reserved register will look like a set of dead defs
2162   // - we don't properly track the live range of reserved registers.
2163 
2164   // Deny any overlapping intervals.  This depends on all the reserved
2165   // register live ranges to look like dead defs.
2166   if (!MRI->isConstantPhysReg(DstReg)) {
2167     for (MCRegUnit Unit : TRI->regunits(DstReg)) {
2168       // Abort if not all the regunits are reserved.
2169       for (MCRegUnitRootIterator RI(Unit, TRI); RI.isValid(); ++RI) {
2170         if (!MRI->isReserved(*RI))
2171           return false;
2172       }
2173       if (RHS.overlaps(LIS->getRegUnit(Unit))) {
2174         LLVM_DEBUG(dbgs() << "\t\tInterference: " << printRegUnit(Unit, TRI)
2175                           << '\n');
2176         return false;
2177       }
2178     }
2179 
2180     // We must also check for overlaps with regmask clobbers.
2181     BitVector RegMaskUsable;
2182     if (LIS->checkRegMaskInterference(RHS, RegMaskUsable) &&
2183         !RegMaskUsable.test(DstReg)) {
2184       LLVM_DEBUG(dbgs() << "\t\tRegMask interference\n");
2185       return false;
2186     }
2187   }
2188 
2189   // Skip any value computations, we are not adding new values to the
2190   // reserved register.  Also skip merging the live ranges, the reserved
2191   // register live range doesn't need to be accurate as long as all the
2192   // defs are there.
2193 
2194   // Delete the identity copy.
2195   MachineInstr *CopyMI;
2196   if (CP.isFlipped()) {
2197     // Physreg is copied into vreg
2198     //   %y = COPY %physreg_x
2199     //   ...  //< no other def of %physreg_x here
2200     //   use %y
2201     // =>
2202     //   ...
2203     //   use %physreg_x
2204     CopyMI = MRI->getVRegDef(SrcReg);
2205     deleteInstr(CopyMI);
2206   } else {
2207     // VReg is copied into physreg:
2208     //   %y = def
2209     //   ... //< no other def or use of %physreg_x here
2210     //   %physreg_x = COPY %y
2211     // =>
2212     //   %physreg_x = def
2213     //   ...
2214     if (!MRI->hasOneNonDBGUse(SrcReg)) {
2215       LLVM_DEBUG(dbgs() << "\t\tMultiple vreg uses!\n");
2216       return false;
2217     }
2218 
2219     if (!LIS->intervalIsInOneMBB(RHS)) {
2220       LLVM_DEBUG(dbgs() << "\t\tComplex control flow!\n");
2221       return false;
2222     }
2223 
2224     MachineInstr &DestMI = *MRI->getVRegDef(SrcReg);
2225     CopyMI = &*MRI->use_instr_nodbg_begin(SrcReg);
2226     SlotIndex CopyRegIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
2227     SlotIndex DestRegIdx = LIS->getInstructionIndex(DestMI).getRegSlot();
2228 
2229     if (!MRI->isConstantPhysReg(DstReg)) {
2230       // We checked above that there are no interfering defs of the physical
2231       // register. However, for this case, where we intend to move up the def of
2232       // the physical register, we also need to check for interfering uses.
2233       SlotIndexes *Indexes = LIS->getSlotIndexes();
2234       for (SlotIndex SI = Indexes->getNextNonNullIndex(DestRegIdx);
2235            SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(SI)) {
2236         MachineInstr *MI = LIS->getInstructionFromIndex(SI);
2237         if (MI->readsRegister(DstReg, TRI)) {
2238           LLVM_DEBUG(dbgs() << "\t\tInterference (read): " << *MI);
2239           return false;
2240         }
2241       }
2242     }
2243 
2244     // We're going to remove the copy which defines a physical reserved
2245     // register, so remove its valno, etc.
2246     LLVM_DEBUG(dbgs() << "\t\tRemoving phys reg def of "
2247                       << printReg(DstReg, TRI) << " at " << CopyRegIdx << "\n");
2248 
2249     LIS->removePhysRegDefAt(DstReg.asMCReg(), CopyRegIdx);
2250     deleteInstr(CopyMI);
2251 
2252     // Create a new dead def at the new def location.
2253     for (MCRegUnit Unit : TRI->regunits(DstReg)) {
2254       LiveRange &LR = LIS->getRegUnit(Unit);
2255       LR.createDeadDef(DestRegIdx, LIS->getVNInfoAllocator());
2256     }
2257   }
2258 
2259   // We don't track kills for reserved registers.
2260   MRI->clearKillFlags(CP.getSrcReg());
2261 
2262   return true;
2263 }
2264 
2265 //===----------------------------------------------------------------------===//
2266 //                 Interference checking and interval joining
2267 //===----------------------------------------------------------------------===//
2268 //
2269 // In the easiest case, the two live ranges being joined are disjoint, and
2270 // there is no interference to consider. It is quite common, though, to have
2271 // overlapping live ranges, and we need to check if the interference can be
2272 // resolved.
2273 //
2274 // The live range of a single SSA value forms a sub-tree of the dominator tree.
2275 // This means that two SSA values overlap if and only if the def of one value
2276 // is contained in the live range of the other value. As a special case, the
2277 // overlapping values can be defined at the same index.
2278 //
2279 // The interference from an overlapping def can be resolved in these cases:
2280 //
2281 // 1. Coalescable copies. The value is defined by a copy that would become an
2282 //    identity copy after joining SrcReg and DstReg. The copy instruction will
2283 //    be removed, and the value will be merged with the source value.
2284 //
2285 //    There can be several copies back and forth, causing many values to be
2286 //    merged into one. We compute a list of ultimate values in the joined live
2287 //    range as well as a mappings from the old value numbers.
2288 //
2289 // 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI
2290 //    predecessors have a live out value. It doesn't cause real interference,
2291 //    and can be merged into the value it overlaps. Like a coalescable copy, it
2292 //    can be erased after joining.
2293 //
2294 // 3. Copy of external value. The overlapping def may be a copy of a value that
2295 //    is already in the other register. This is like a coalescable copy, but
2296 //    the live range of the source register must be trimmed after erasing the
2297 //    copy instruction:
2298 //
2299 //      %src = COPY %ext
2300 //      %dst = COPY %ext  <-- Remove this COPY, trim the live range of %ext.
2301 //
2302 // 4. Clobbering undefined lanes. Vector registers are sometimes built by
2303 //    defining one lane at a time:
2304 //
2305 //      %dst:ssub0<def,read-undef> = FOO
2306 //      %src = BAR
2307 //      %dst:ssub1 = COPY %src
2308 //
2309 //    The live range of %src overlaps the %dst value defined by FOO, but
2310 //    merging %src into %dst:ssub1 is only going to clobber the ssub1 lane
2311 //    which was undef anyway.
2312 //
2313 //    The value mapping is more complicated in this case. The final live range
2314 //    will have different value numbers for both FOO and BAR, but there is no
2315 //    simple mapping from old to new values. It may even be necessary to add
2316 //    new PHI values.
2317 //
2318 // 5. Clobbering dead lanes. A def may clobber a lane of a vector register that
2319 //    is live, but never read. This can happen because we don't compute
2320 //    individual live ranges per lane.
2321 //
2322 //      %dst = FOO
2323 //      %src = BAR
2324 //      %dst:ssub1 = COPY %src
2325 //
2326 //    This kind of interference is only resolved locally. If the clobbered
2327 //    lane value escapes the block, the join is aborted.
2328 
2329 namespace {
2330 
2331 /// Track information about values in a single virtual register about to be
2332 /// joined. Objects of this class are always created in pairs - one for each
2333 /// side of the CoalescerPair (or one for each lane of a side of the coalescer
2334 /// pair)
2335 class JoinVals {
2336   /// Live range we work on.
2337   LiveRange &LR;
2338 
2339   /// (Main) register we work on.
2340   const Register Reg;
2341 
2342   /// Reg (and therefore the values in this liverange) will end up as
2343   /// subregister SubIdx in the coalesced register. Either CP.DstIdx or
2344   /// CP.SrcIdx.
2345   const unsigned SubIdx;
2346 
2347   /// The LaneMask that this liverange will occupy the coalesced register. May
2348   /// be smaller than the lanemask produced by SubIdx when merging subranges.
2349   const LaneBitmask LaneMask;
2350 
2351   /// This is true when joining sub register ranges, false when joining main
2352   /// ranges.
2353   const bool SubRangeJoin;
2354 
2355   /// Whether the current LiveInterval tracks subregister liveness.
2356   const bool TrackSubRegLiveness;
2357 
2358   /// Values that will be present in the final live range.
2359   SmallVectorImpl<VNInfo*> &NewVNInfo;
2360 
2361   const CoalescerPair &CP;
2362   LiveIntervals *LIS;
2363   SlotIndexes *Indexes;
2364   const TargetRegisterInfo *TRI;
2365 
2366   /// Value number assignments. Maps value numbers in LI to entries in
2367   /// NewVNInfo. This is suitable for passing to LiveInterval::join().
2368   SmallVector<int, 8> Assignments;
2369 
2370   public:
2371   /// Conflict resolution for overlapping values.
2372   enum ConflictResolution {
2373     /// No overlap, simply keep this value.
2374     CR_Keep,
2375 
2376     /// Merge this value into OtherVNI and erase the defining instruction.
2377     /// Used for IMPLICIT_DEF, coalescable copies, and copies from external
2378     /// values.
2379     CR_Erase,
2380 
2381     /// Merge this value into OtherVNI but keep the defining instruction.
2382     /// This is for the special case where OtherVNI is defined by the same
2383     /// instruction.
2384     CR_Merge,
2385 
2386     /// Keep this value, and have it replace OtherVNI where possible. This
2387     /// complicates value mapping since OtherVNI maps to two different values
2388     /// before and after this def.
2389     /// Used when clobbering undefined or dead lanes.
2390     CR_Replace,
2391 
2392     /// Unresolved conflict. Visit later when all values have been mapped.
2393     CR_Unresolved,
2394 
2395     /// Unresolvable conflict. Abort the join.
2396     CR_Impossible
2397   };
2398 
2399   private:
2400   /// Per-value info for LI. The lane bit masks are all relative to the final
2401   /// joined register, so they can be compared directly between SrcReg and
2402   /// DstReg.
2403   struct Val {
2404     ConflictResolution Resolution = CR_Keep;
2405 
2406     /// Lanes written by this def, 0 for unanalyzed values.
2407     LaneBitmask WriteLanes;
2408 
2409     /// Lanes with defined values in this register. Other lanes are undef and
2410     /// safe to clobber.
2411     LaneBitmask ValidLanes;
2412 
2413     /// Value in LI being redefined by this def.
2414     VNInfo *RedefVNI = nullptr;
2415 
2416     /// Value in the other live range that overlaps this def, if any.
2417     VNInfo *OtherVNI = nullptr;
2418 
2419     /// Is this value an IMPLICIT_DEF that can be erased?
2420     ///
2421     /// IMPLICIT_DEF values should only exist at the end of a basic block that
2422     /// is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be
2423     /// safely erased if they are overlapping a live value in the other live
2424     /// interval.
2425     ///
2426     /// Weird control flow graphs and incomplete PHI handling in
2427     /// ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with
2428     /// longer live ranges. Such IMPLICIT_DEF values should be treated like
2429     /// normal values.
2430     bool ErasableImplicitDef = false;
2431 
2432     /// True when the live range of this value will be pruned because of an
2433     /// overlapping CR_Replace value in the other live range.
2434     bool Pruned = false;
2435 
2436     /// True once Pruned above has been computed.
2437     bool PrunedComputed = false;
2438 
2439     /// True if this value is determined to be identical to OtherVNI
2440     /// (in valuesIdentical). This is used with CR_Erase where the erased
2441     /// copy is redundant, i.e. the source value is already the same as
2442     /// the destination. In such cases the subranges need to be updated
2443     /// properly. See comment at pruneSubRegValues for more info.
2444     bool Identical = false;
2445 
2446     Val() = default;
2447 
2448     bool isAnalyzed() const { return WriteLanes.any(); }
2449   };
2450 
2451   /// One entry per value number in LI.
2452   SmallVector<Val, 8> Vals;
2453 
2454   /// Compute the bitmask of lanes actually written by DefMI.
2455   /// Set Redef if there are any partial register definitions that depend on the
2456   /// previous value of the register.
2457   LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;
2458 
2459   /// Find the ultimate value that VNI was copied from.
2460   std::pair<const VNInfo *, Register> followCopyChain(const VNInfo *VNI) const;
2461 
2462   bool valuesIdentical(VNInfo *Value0, VNInfo *Value1, const JoinVals &Other) const;
2463 
2464   /// Analyze ValNo in this live range, and set all fields of Vals[ValNo].
2465   /// Return a conflict resolution when possible, but leave the hard cases as
2466   /// CR_Unresolved.
2467   /// Recursively calls computeAssignment() on this and Other, guaranteeing that
2468   /// both OtherVNI and RedefVNI have been analyzed and mapped before returning.
2469   /// The recursion always goes upwards in the dominator tree, making loops
2470   /// impossible.
2471   ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other);
2472 
2473   /// Compute the value assignment for ValNo in RI.
2474   /// This may be called recursively by analyzeValue(), but never for a ValNo on
2475   /// the stack.
2476   void computeAssignment(unsigned ValNo, JoinVals &Other);
2477 
2478   /// Assuming ValNo is going to clobber some valid lanes in Other.LR, compute
2479   /// the extent of the tainted lanes in the block.
2480   ///
2481   /// Multiple values in Other.LR can be affected since partial redefinitions
2482   /// can preserve previously tainted lanes.
2483   ///
2484   ///   1 %dst = VLOAD           <-- Define all lanes in %dst
2485   ///   2 %src = FOO             <-- ValNo to be joined with %dst:ssub0
2486   ///   3 %dst:ssub1 = BAR       <-- Partial redef doesn't clear taint in ssub0
2487   ///   4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read
2488   ///
2489   /// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes)
2490   /// entry to TaintedVals.
2491   ///
2492   /// Returns false if the tainted lanes extend beyond the basic block.
2493   bool
2494   taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
2495               SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent);
2496 
2497   /// Return true if MI uses any of the given Lanes from Reg.
2498   /// This does not include partial redefinitions of Reg.
2499   bool usesLanes(const MachineInstr &MI, Register, unsigned, LaneBitmask) const;
2500 
2501   /// Determine if ValNo is a copy of a value number in LR or Other.LR that will
2502   /// be pruned:
2503   ///
2504   ///   %dst = COPY %src
2505   ///   %src = COPY %dst  <-- This value to be pruned.
2506   ///   %dst = COPY %src  <-- This value is a copy of a pruned value.
2507   bool isPrunedValue(unsigned ValNo, JoinVals &Other);
2508 
2509 public:
2510   JoinVals(LiveRange &LR, Register Reg, unsigned SubIdx, LaneBitmask LaneMask,
2511            SmallVectorImpl<VNInfo *> &newVNInfo, const CoalescerPair &cp,
2512            LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin,
2513            bool TrackSubRegLiveness)
2514       : LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask),
2515         SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),
2516         NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
2517         TRI(TRI), Assignments(LR.getNumValNums(), -1),
2518         Vals(LR.getNumValNums()) {}
2519 
2520   /// Analyze defs in LR and compute a value mapping in NewVNInfo.
2521   /// Returns false if any conflicts were impossible to resolve.
2522   bool mapValues(JoinVals &Other);
2523 
2524   /// Try to resolve conflicts that require all values to be mapped.
2525   /// Returns false if any conflicts were impossible to resolve.
2526   bool resolveConflicts(JoinVals &Other);
2527 
2528   /// Prune the live range of values in Other.LR where they would conflict with
2529   /// CR_Replace values in LR. Collect end points for restoring the live range
2530   /// after joining.
2531   void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints,
2532                    bool changeInstrs);
2533 
2534   /// Removes subranges starting at copies that get removed. This sometimes
2535   /// happens when undefined subranges are copied around. These ranges contain
2536   /// no useful information and can be removed.
2537   void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);
2538 
2539   /// Pruning values in subranges can lead to removing segments in these
2540   /// subranges started by IMPLICIT_DEFs. The corresponding segments in
2541   /// the main range also need to be removed. This function will mark
2542   /// the corresponding values in the main range as pruned, so that
2543   /// eraseInstrs can do the final cleanup.
2544   /// The parameter @p LI must be the interval whose main range is the
2545   /// live range LR.
2546   void pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange);
2547 
2548   /// Erase any machine instructions that have been coalesced away.
2549   /// Add erased instructions to ErasedInstrs.
2550   /// Add foreign virtual registers to ShrinkRegs if their live range ended at
2551   /// the erased instrs.
2552   void eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
2553                    SmallVectorImpl<Register> &ShrinkRegs,
2554                    LiveInterval *LI = nullptr);
2555 
2556   /// Remove liverange defs at places where implicit defs will be removed.
2557   void removeImplicitDefs();
2558 
2559   /// Get the value assignments suitable for passing to LiveInterval::join.
2560   const int *getAssignments() const { return Assignments.data(); }
2561 
2562   /// Get the conflict resolution for a value number.
2563   ConflictResolution getResolution(unsigned Num) const {
2564     return Vals[Num].Resolution;
2565   }
2566 };
2567 
2568 } // end anonymous namespace
2569 
2570 LaneBitmask JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef)
2571   const {
2572   LaneBitmask L;
2573   for (const MachineOperand &MO : DefMI->all_defs()) {
2574     if (MO.getReg() != Reg)
2575       continue;
2576     L |= TRI->getSubRegIndexLaneMask(
2577            TRI->composeSubRegIndices(SubIdx, MO.getSubReg()));
2578     if (MO.readsReg())
2579       Redef = true;
2580   }
2581   return L;
2582 }
2583 
2584 std::pair<const VNInfo *, Register>
2585 JoinVals::followCopyChain(const VNInfo *VNI) const {
2586   Register TrackReg = Reg;
2587 
2588   while (!VNI->isPHIDef()) {
2589     SlotIndex Def = VNI->def;
2590     MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
2591     assert(MI && "No defining instruction");
2592     if (!MI->isFullCopy())
2593       return std::make_pair(VNI, TrackReg);
2594     Register SrcReg = MI->getOperand(1).getReg();
2595     if (!SrcReg.isVirtual())
2596       return std::make_pair(VNI, TrackReg);
2597 
2598     const LiveInterval &LI = LIS->getInterval(SrcReg);
2599     const VNInfo *ValueIn;
2600     // No subrange involved.
2601     if (!SubRangeJoin || !LI.hasSubRanges()) {
2602       LiveQueryResult LRQ = LI.Query(Def);
2603       ValueIn = LRQ.valueIn();
2604     } else {
2605       // Query subranges. Ensure that all matching ones take us to the same def
2606       // (allowing some of them to be undef).
2607       ValueIn = nullptr;
2608       for (const LiveInterval::SubRange &S : LI.subranges()) {
2609         // Transform lanemask to a mask in the joined live interval.
2610         LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
2611         if ((SMask & LaneMask).none())
2612           continue;
2613         LiveQueryResult LRQ = S.Query(Def);
2614         if (!ValueIn) {
2615           ValueIn = LRQ.valueIn();
2616           continue;
2617         }
2618         if (LRQ.valueIn() && ValueIn != LRQ.valueIn())
2619           return std::make_pair(VNI, TrackReg);
2620       }
2621     }
2622     if (ValueIn == nullptr) {
2623       // Reaching an undefined value is legitimate, for example:
2624       //
2625       // 1   undef %0.sub1 = ...  ;; %0.sub0 == undef
2626       // 2   %1 = COPY %0         ;; %1 is defined here.
2627       // 3   %0 = COPY %1         ;; Now %0.sub0 has a definition,
2628       //                          ;; but it's equivalent to "undef".
2629       return std::make_pair(nullptr, SrcReg);
2630     }
2631     VNI = ValueIn;
2632     TrackReg = SrcReg;
2633   }
2634   return std::make_pair(VNI, TrackReg);
2635 }
2636 
2637 bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1,
2638                                const JoinVals &Other) const {
2639   const VNInfo *Orig0;
2640   Register Reg0;
2641   std::tie(Orig0, Reg0) = followCopyChain(Value0);
2642   if (Orig0 == Value1 && Reg0 == Other.Reg)
2643     return true;
2644 
2645   const VNInfo *Orig1;
2646   Register Reg1;
2647   std::tie(Orig1, Reg1) = Other.followCopyChain(Value1);
2648   // If both values are undefined, and the source registers are the same
2649   // register, the values are identical. Filter out cases where only one
2650   // value is defined.
2651   if (Orig0 == nullptr || Orig1 == nullptr)
2652     return Orig0 == Orig1 && Reg0 == Reg1;
2653 
2654   // The values are equal if they are defined at the same place and use the
2655   // same register. Note that we cannot compare VNInfos directly as some of
2656   // them might be from a copy created in mergeSubRangeInto()  while the other
2657   // is from the original LiveInterval.
2658   return Orig0->def == Orig1->def && Reg0 == Reg1;
2659 }
2660 
2661 JoinVals::ConflictResolution
2662 JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) {
2663   Val &V = Vals[ValNo];
2664   assert(!V.isAnalyzed() && "Value has already been analyzed!");
2665   VNInfo *VNI = LR.getValNumInfo(ValNo);
2666   if (VNI->isUnused()) {
2667     V.WriteLanes = LaneBitmask::getAll();
2668     return CR_Keep;
2669   }
2670 
2671   // Get the instruction defining this value, compute the lanes written.
2672   const MachineInstr *DefMI = nullptr;
2673   if (VNI->isPHIDef()) {
2674     // Conservatively assume that all lanes in a PHI are valid.
2675     LaneBitmask Lanes = SubRangeJoin ? LaneBitmask::getLane(0)
2676                                      : TRI->getSubRegIndexLaneMask(SubIdx);
2677     V.ValidLanes = V.WriteLanes = Lanes;
2678   } else {
2679     DefMI = Indexes->getInstructionFromIndex(VNI->def);
2680     assert(DefMI != nullptr);
2681     if (SubRangeJoin) {
2682       // We don't care about the lanes when joining subregister ranges.
2683       V.WriteLanes = V.ValidLanes = LaneBitmask::getLane(0);
2684       if (DefMI->isImplicitDef()) {
2685         V.ValidLanes = LaneBitmask::getNone();
2686         V.ErasableImplicitDef = true;
2687       }
2688     } else {
2689       bool Redef = false;
2690       V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef);
2691 
2692       // If this is a read-modify-write instruction, there may be more valid
2693       // lanes than the ones written by this instruction.
2694       // This only covers partial redef operands. DefMI may have normal use
2695       // operands reading the register. They don't contribute valid lanes.
2696       //
2697       // This adds ssub1 to the set of valid lanes in %src:
2698       //
2699       //   %src:ssub1 = FOO
2700       //
2701       // This leaves only ssub1 valid, making any other lanes undef:
2702       //
2703       //   %src:ssub1<def,read-undef> = FOO %src:ssub2
2704       //
2705       // The <read-undef> flag on the def operand means that old lane values are
2706       // not important.
2707       if (Redef) {
2708         V.RedefVNI = LR.Query(VNI->def).valueIn();
2709         assert((TrackSubRegLiveness || V.RedefVNI) &&
2710                "Instruction is reading nonexistent value");
2711         if (V.RedefVNI != nullptr) {
2712           computeAssignment(V.RedefVNI->id, Other);
2713           V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;
2714         }
2715       }
2716 
2717       // An IMPLICIT_DEF writes undef values.
2718       if (DefMI->isImplicitDef()) {
2719         // We normally expect IMPLICIT_DEF values to be live only until the end
2720         // of their block. If the value is really live longer and gets pruned in
2721         // another block, this flag is cleared again.
2722         //
2723         // Clearing the valid lanes is deferred until it is sure this can be
2724         // erased.
2725         V.ErasableImplicitDef = true;
2726       }
2727     }
2728   }
2729 
2730   // Find the value in Other that overlaps VNI->def, if any.
2731   LiveQueryResult OtherLRQ = Other.LR.Query(VNI->def);
2732 
2733   // It is possible that both values are defined by the same instruction, or
2734   // the values are PHIs defined in the same block. When that happens, the two
2735   // values should be merged into one, but not into any preceding value.
2736   // The first value defined or visited gets CR_Keep, the other gets CR_Merge.
2737   if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) {
2738     assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ");
2739 
2740     // One value stays, the other is merged. Keep the earlier one, or the first
2741     // one we see.
2742     if (OtherVNI->def < VNI->def)
2743       Other.computeAssignment(OtherVNI->id, *this);
2744     else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) {
2745       // This is an early-clobber def overlapping a live-in value in the other
2746       // register. Not mergeable.
2747       V.OtherVNI = OtherLRQ.valueIn();
2748       return CR_Impossible;
2749     }
2750     V.OtherVNI = OtherVNI;
2751     Val &OtherV = Other.Vals[OtherVNI->id];
2752     // Keep this value, check for conflicts when analyzing OtherVNI. Avoid
2753     // revisiting OtherVNI->id in JoinVals::computeAssignment() below before it
2754     // is assigned.
2755     if (!OtherV.isAnalyzed() || Other.Assignments[OtherVNI->id] == -1)
2756       return CR_Keep;
2757     // Both sides have been analyzed now.
2758     // Allow overlapping PHI values. Any real interference would show up in a
2759     // predecessor, the PHI itself can't introduce any conflicts.
2760     if (VNI->isPHIDef())
2761       return CR_Merge;
2762     if ((V.ValidLanes & OtherV.ValidLanes).any())
2763       // Overlapping lanes can't be resolved.
2764       return CR_Impossible;
2765     else
2766       return CR_Merge;
2767   }
2768 
2769   // No simultaneous def. Is Other live at the def?
2770   V.OtherVNI = OtherLRQ.valueIn();
2771   if (!V.OtherVNI)
2772     // No overlap, no conflict.
2773     return CR_Keep;
2774 
2775   assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ");
2776 
2777   // We have overlapping values, or possibly a kill of Other.
2778   // Recursively compute assignments up the dominator tree.
2779   Other.computeAssignment(V.OtherVNI->id, *this);
2780   Val &OtherV = Other.Vals[V.OtherVNI->id];
2781 
2782   if (OtherV.ErasableImplicitDef) {
2783     // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block.
2784     // This shouldn't normally happen, but ProcessImplicitDefs can leave such
2785     // IMPLICIT_DEF instructions behind, and there is nothing wrong with it
2786     // technically.
2787     //
2788     // When it happens, treat that IMPLICIT_DEF as a normal value, and don't try
2789     // to erase the IMPLICIT_DEF instruction.
2790     MachineBasicBlock *OtherMBB = Indexes->getMBBFromIndex(V.OtherVNI->def);
2791     if (DefMI && DefMI->getParent() != OtherMBB) {
2792       LLVM_DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
2793                  << " extends into "
2794                  << printMBBReference(*DefMI->getParent())
2795                  << ", keeping it.\n");
2796       OtherV.ErasableImplicitDef = false;
2797     } else if (OtherMBB->hasEHPadSuccessor()) {
2798       // If OtherV is defined in a basic block that has EH pad successors then
2799       // we get the same problem not just if OtherV is live beyond its basic
2800       // block, but beyond the last call instruction in its basic block. Handle
2801       // this case conservatively.
2802       LLVM_DEBUG(
2803           dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
2804                  << " may be live into EH pad successors, keeping it.\n");
2805       OtherV.ErasableImplicitDef = false;
2806     } else {
2807       // We deferred clearing these lanes in case we needed to save them
2808       OtherV.ValidLanes &= ~OtherV.WriteLanes;
2809     }
2810   }
2811 
2812   // Allow overlapping PHI values. Any real interference would show up in a
2813   // predecessor, the PHI itself can't introduce any conflicts.
2814   if (VNI->isPHIDef())
2815     return CR_Replace;
2816 
2817   // Check for simple erasable conflicts.
2818   if (DefMI->isImplicitDef())
2819     return CR_Erase;
2820 
2821   // Include the non-conflict where DefMI is a coalescable copy that kills
2822   // OtherVNI. We still want the copy erased and value numbers merged.
2823   if (CP.isCoalescable(DefMI)) {
2824     // Some of the lanes copied from OtherVNI may be undef, making them undef
2825     // here too.
2826     V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;
2827     return CR_Erase;
2828   }
2829 
2830   // This may not be a real conflict if DefMI simply kills Other and defines
2831   // VNI.
2832   if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def)
2833     return CR_Keep;
2834 
2835   // Handle the case where VNI and OtherVNI can be proven to be identical:
2836   //
2837   //   %other = COPY %ext
2838   //   %this  = COPY %ext <-- Erase this copy
2839   //
2840   if (DefMI->isFullCopy() && !CP.isPartial() &&
2841       valuesIdentical(VNI, V.OtherVNI, Other)) {
2842     V.Identical = true;
2843     return CR_Erase;
2844   }
2845 
2846   // The remaining checks apply to the lanes, which aren't tracked here.  This
2847   // was already decided to be OK via the following CR_Replace condition.
2848   // CR_Replace.
2849   if (SubRangeJoin)
2850     return CR_Replace;
2851 
2852   // If the lanes written by this instruction were all undef in OtherVNI, it is
2853   // still safe to join the live ranges. This can't be done with a simple value
2854   // mapping, though - OtherVNI will map to multiple values:
2855   //
2856   //   1 %dst:ssub0 = FOO                <-- OtherVNI
2857   //   2 %src = BAR                      <-- VNI
2858   //   3 %dst:ssub1 = COPY killed %src    <-- Eliminate this copy.
2859   //   4 BAZ killed %dst
2860   //   5 QUUX killed %src
2861   //
2862   // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace
2863   // handles this complex value mapping.
2864   if ((V.WriteLanes & OtherV.ValidLanes).none())
2865     return CR_Replace;
2866 
2867   // If the other live range is killed by DefMI and the live ranges are still
2868   // overlapping, it must be because we're looking at an early clobber def:
2869   //
2870   //   %dst<def,early-clobber> = ASM killed %src
2871   //
2872   // In this case, it is illegal to merge the two live ranges since the early
2873   // clobber def would clobber %src before it was read.
2874   if (OtherLRQ.isKill()) {
2875     // This case where the def doesn't overlap the kill is handled above.
2876     assert(VNI->def.isEarlyClobber() &&
2877            "Only early clobber defs can overlap a kill");
2878     return CR_Impossible;
2879   }
2880 
2881   // VNI is clobbering live lanes in OtherVNI, but there is still the
2882   // possibility that no instructions actually read the clobbered lanes.
2883   // If we're clobbering all the lanes in OtherVNI, at least one must be read.
2884   // Otherwise Other.RI wouldn't be live here.
2885   if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes).none())
2886     return CR_Impossible;
2887 
2888   if (TrackSubRegLiveness) {
2889     auto &OtherLI = LIS->getInterval(Other.Reg);
2890     // If OtherVNI does not have subranges, it means all the lanes of OtherVNI
2891     // share the same live range, so we just need to check whether they have
2892     // any conflict bit in their LaneMask.
2893     if (!OtherLI.hasSubRanges()) {
2894       LaneBitmask OtherMask = TRI->getSubRegIndexLaneMask(Other.SubIdx);
2895       return (OtherMask & V.WriteLanes).none() ? CR_Replace : CR_Impossible;
2896     }
2897 
2898     // If we are clobbering some active lanes of OtherVNI at VNI->def, it is
2899     // impossible to resolve the conflict. Otherwise, we can just replace
2900     // OtherVNI because of no real conflict.
2901     for (LiveInterval::SubRange &OtherSR : OtherLI.subranges()) {
2902       LaneBitmask OtherMask =
2903           TRI->composeSubRegIndexLaneMask(Other.SubIdx, OtherSR.LaneMask);
2904       if ((OtherMask & V.WriteLanes).none())
2905         continue;
2906 
2907       auto OtherSRQ = OtherSR.Query(VNI->def);
2908       if (OtherSRQ.valueIn() && OtherSRQ.endPoint() > VNI->def) {
2909         // VNI is clobbering some lanes of OtherVNI, they have real conflict.
2910         return CR_Impossible;
2911       }
2912     }
2913 
2914     // VNI is NOT clobbering any lane of OtherVNI, just replace OtherVNI.
2915     return CR_Replace;
2916   }
2917 
2918   // We need to verify that no instructions are reading the clobbered lanes.
2919   // To save compile time, we'll only check that locally. Don't allow the
2920   // tainted value to escape the basic block.
2921   MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
2922   if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB))
2923     return CR_Impossible;
2924 
2925   // There are still some things that could go wrong besides clobbered lanes
2926   // being read, for example OtherVNI may be only partially redefined in MBB,
2927   // and some clobbered lanes could escape the block. Save this analysis for
2928   // resolveConflicts() when all values have been mapped. We need to know
2929   // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute
2930   // that now - the recursive analyzeValue() calls must go upwards in the
2931   // dominator tree.
2932   return CR_Unresolved;
2933 }
2934 
2935 void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) {
2936   Val &V = Vals[ValNo];
2937   if (V.isAnalyzed()) {
2938     // Recursion should always move up the dominator tree, so ValNo is not
2939     // supposed to reappear before it has been assigned.
2940     assert(Assignments[ValNo] != -1 && "Bad recursion?");
2941     return;
2942   }
2943   switch ((V.Resolution = analyzeValue(ValNo, Other))) {
2944   case CR_Erase:
2945   case CR_Merge:
2946     // Merge this ValNo into OtherVNI.
2947     assert(V.OtherVNI && "OtherVNI not assigned, can't merge.");
2948     assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion");
2949     Assignments[ValNo] = Other.Assignments[V.OtherVNI->id];
2950     LLVM_DEBUG(dbgs() << "\t\tmerge " << printReg(Reg) << ':' << ValNo << '@'
2951                       << LR.getValNumInfo(ValNo)->def << " into "
2952                       << printReg(Other.Reg) << ':' << V.OtherVNI->id << '@'
2953                       << V.OtherVNI->def << " --> @"
2954                       << NewVNInfo[Assignments[ValNo]]->def << '\n');
2955     break;
2956   case CR_Replace:
2957   case CR_Unresolved: {
2958     // The other value is going to be pruned if this join is successful.
2959     assert(V.OtherVNI && "OtherVNI not assigned, can't prune");
2960     Val &OtherV = Other.Vals[V.OtherVNI->id];
2961     // We cannot erase an IMPLICIT_DEF if we don't have valid values for all
2962     // its lanes.
2963     if (OtherV.ErasableImplicitDef &&
2964         TrackSubRegLiveness &&
2965         (OtherV.ValidLanes & ~V.ValidLanes).any()) {
2966       LLVM_DEBUG(dbgs() << "Cannot erase implicit_def with missing values\n");
2967 
2968       OtherV.ErasableImplicitDef = false;
2969       // The valid lanes written by the implicit_def were speculatively cleared
2970       // before, so make this more conservative. It may be better to track this,
2971       // I haven't found a testcase where it matters.
2972       OtherV.ValidLanes = LaneBitmask::getAll();
2973     }
2974 
2975     OtherV.Pruned = true;
2976     [[fallthrough]];
2977   }
2978   default:
2979     // This value number needs to go in the final joined live range.
2980     Assignments[ValNo] = NewVNInfo.size();
2981     NewVNInfo.push_back(LR.getValNumInfo(ValNo));
2982     break;
2983   }
2984 }
2985 
2986 bool JoinVals::mapValues(JoinVals &Other) {
2987   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2988     computeAssignment(i, Other);
2989     if (Vals[i].Resolution == CR_Impossible) {
2990       LLVM_DEBUG(dbgs() << "\t\tinterference at " << printReg(Reg) << ':' << i
2991                         << '@' << LR.getValNumInfo(i)->def << '\n');
2992       return false;
2993     }
2994   }
2995   return true;
2996 }
2997 
2998 bool JoinVals::
2999 taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
3000             SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent) {
3001   VNInfo *VNI = LR.getValNumInfo(ValNo);
3002   MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
3003   SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB);
3004 
3005   // Scan Other.LR from VNI.def to MBBEnd.
3006   LiveInterval::iterator OtherI = Other.LR.find(VNI->def);
3007   assert(OtherI != Other.LR.end() && "No conflict?");
3008   do {
3009     // OtherI is pointing to a tainted value. Abort the join if the tainted
3010     // lanes escape the block.
3011     SlotIndex End = OtherI->end;
3012     if (End >= MBBEnd) {
3013       LLVM_DEBUG(dbgs() << "\t\ttaints global " << printReg(Other.Reg) << ':'
3014                         << OtherI->valno->id << '@' << OtherI->start << '\n');
3015       return false;
3016     }
3017     LLVM_DEBUG(dbgs() << "\t\ttaints local " << printReg(Other.Reg) << ':'
3018                       << OtherI->valno->id << '@' << OtherI->start << " to "
3019                       << End << '\n');
3020     // A dead def is not a problem.
3021     if (End.isDead())
3022       break;
3023     TaintExtent.push_back(std::make_pair(End, TaintedLanes));
3024 
3025     // Check for another def in the MBB.
3026     if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd)
3027       break;
3028 
3029     // Lanes written by the new def are no longer tainted.
3030     const Val &OV = Other.Vals[OtherI->valno->id];
3031     TaintedLanes &= ~OV.WriteLanes;
3032     if (!OV.RedefVNI)
3033       break;
3034   } while (TaintedLanes.any());
3035   return true;
3036 }
3037 
3038 bool JoinVals::usesLanes(const MachineInstr &MI, Register Reg, unsigned SubIdx,
3039                          LaneBitmask Lanes) const {
3040   if (MI.isDebugOrPseudoInstr())
3041     return false;
3042   for (const MachineOperand &MO : MI.all_uses()) {
3043     if (MO.getReg() != Reg)
3044       continue;
3045     if (!MO.readsReg())
3046       continue;
3047     unsigned S = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());
3048     if ((Lanes & TRI->getSubRegIndexLaneMask(S)).any())
3049       return true;
3050   }
3051   return false;
3052 }
3053 
3054 bool JoinVals::resolveConflicts(JoinVals &Other) {
3055   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3056     Val &V = Vals[i];
3057     assert(V.Resolution != CR_Impossible && "Unresolvable conflict");
3058     if (V.Resolution != CR_Unresolved)
3059       continue;
3060     LLVM_DEBUG(dbgs() << "\t\tconflict at " << printReg(Reg) << ':' << i << '@'
3061                       << LR.getValNumInfo(i)->def
3062                       << ' ' << PrintLaneMask(LaneMask) << '\n');
3063     if (SubRangeJoin)
3064       return false;
3065 
3066     ++NumLaneConflicts;
3067     assert(V.OtherVNI && "Inconsistent conflict resolution.");
3068     VNInfo *VNI = LR.getValNumInfo(i);
3069     const Val &OtherV = Other.Vals[V.OtherVNI->id];
3070 
3071     // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the
3072     // join, those lanes will be tainted with a wrong value. Get the extent of
3073     // the tainted lanes.
3074     LaneBitmask TaintedLanes = V.WriteLanes & OtherV.ValidLanes;
3075     SmallVector<std::pair<SlotIndex, LaneBitmask>, 8> TaintExtent;
3076     if (!taintExtent(i, TaintedLanes, Other, TaintExtent))
3077       // Tainted lanes would extend beyond the basic block.
3078       return false;
3079 
3080     assert(!TaintExtent.empty() && "There should be at least one conflict.");
3081 
3082     // Now look at the instructions from VNI->def to TaintExtent (inclusive).
3083     MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
3084     MachineBasicBlock::iterator MI = MBB->begin();
3085     if (!VNI->isPHIDef()) {
3086       MI = Indexes->getInstructionFromIndex(VNI->def);
3087       if (!VNI->def.isEarlyClobber()) {
3088         // No need to check the instruction defining VNI for reads.
3089         ++MI;
3090       }
3091     }
3092     assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) &&
3093            "Interference ends on VNI->def. Should have been handled earlier");
3094     MachineInstr *LastMI =
3095       Indexes->getInstructionFromIndex(TaintExtent.front().first);
3096     assert(LastMI && "Range must end at a proper instruction");
3097     unsigned TaintNum = 0;
3098     while (true) {
3099       assert(MI != MBB->end() && "Bad LastMI");
3100       if (usesLanes(*MI, Other.Reg, Other.SubIdx, TaintedLanes)) {
3101         LLVM_DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI);
3102         return false;
3103       }
3104       // LastMI is the last instruction to use the current value.
3105       if (&*MI == LastMI) {
3106         if (++TaintNum == TaintExtent.size())
3107           break;
3108         LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first);
3109         assert(LastMI && "Range must end at a proper instruction");
3110         TaintedLanes = TaintExtent[TaintNum].second;
3111       }
3112       ++MI;
3113     }
3114 
3115     // The tainted lanes are unused.
3116     V.Resolution = CR_Replace;
3117     ++NumLaneResolves;
3118   }
3119   return true;
3120 }
3121 
3122 bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) {
3123   Val &V = Vals[ValNo];
3124   if (V.Pruned || V.PrunedComputed)
3125     return V.Pruned;
3126 
3127   if (V.Resolution != CR_Erase && V.Resolution != CR_Merge)
3128     return V.Pruned;
3129 
3130   // Follow copies up the dominator tree and check if any intermediate value
3131   // has been pruned.
3132   V.PrunedComputed = true;
3133   V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this);
3134   return V.Pruned;
3135 }
3136 
3137 void JoinVals::pruneValues(JoinVals &Other,
3138                            SmallVectorImpl<SlotIndex> &EndPoints,
3139                            bool changeInstrs) {
3140   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3141     SlotIndex Def = LR.getValNumInfo(i)->def;
3142     switch (Vals[i].Resolution) {
3143     case CR_Keep:
3144       break;
3145     case CR_Replace: {
3146       // This value takes precedence over the value in Other.LR.
3147       LIS->pruneValue(Other.LR, Def, &EndPoints);
3148       // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF
3149       // instructions are only inserted to provide a live-out value for PHI
3150       // predecessors, so the instruction should simply go away once its value
3151       // has been replaced.
3152       Val &OtherV = Other.Vals[Vals[i].OtherVNI->id];
3153       bool EraseImpDef = OtherV.ErasableImplicitDef &&
3154                          OtherV.Resolution == CR_Keep;
3155       if (!Def.isBlock()) {
3156         if (changeInstrs) {
3157           // Remove <def,read-undef> flags. This def is now a partial redef.
3158           // Also remove dead flags since the joined live range will
3159           // continue past this instruction.
3160           for (MachineOperand &MO :
3161                Indexes->getInstructionFromIndex(Def)->operands()) {
3162             if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) {
3163               if (MO.getSubReg() != 0 && MO.isUndef() && !EraseImpDef)
3164                 MO.setIsUndef(false);
3165               MO.setIsDead(false);
3166             }
3167           }
3168         }
3169         // This value will reach instructions below, but we need to make sure
3170         // the live range also reaches the instruction at Def.
3171         if (!EraseImpDef)
3172           EndPoints.push_back(Def);
3173       }
3174       LLVM_DEBUG(dbgs() << "\t\tpruned " << printReg(Other.Reg) << " at " << Def
3175                         << ": " << Other.LR << '\n');
3176       break;
3177     }
3178     case CR_Erase:
3179     case CR_Merge:
3180       if (isPrunedValue(i, Other)) {
3181         // This value is ultimately a copy of a pruned value in LR or Other.LR.
3182         // We can no longer trust the value mapping computed by
3183         // computeAssignment(), the value that was originally copied could have
3184         // been replaced.
3185         LIS->pruneValue(LR, Def, &EndPoints);
3186         LLVM_DEBUG(dbgs() << "\t\tpruned all of " << printReg(Reg) << " at "
3187                           << Def << ": " << LR << '\n');
3188       }
3189       break;
3190     case CR_Unresolved:
3191     case CR_Impossible:
3192       llvm_unreachable("Unresolved conflicts");
3193     }
3194   }
3195 }
3196 
3197 // Check if the segment consists of a copied live-through value (i.e. the copy
3198 // in the block only extended the liveness, of an undef value which we may need
3199 // to handle).
3200 static bool isLiveThrough(const LiveQueryResult Q) {
3201   return Q.valueIn() && Q.valueIn()->isPHIDef() && Q.valueIn() == Q.valueOut();
3202 }
3203 
3204 /// Consider the following situation when coalescing the copy between
3205 /// %31 and %45 at 800. (The vertical lines represent live range segments.)
3206 ///
3207 ///                              Main range         Subrange 0004 (sub2)
3208 ///                              %31    %45           %31    %45
3209 ///  544    %45 = COPY %28               +                    +
3210 ///                                      | v1                 | v1
3211 ///  560B bb.1:                          +                    +
3212 ///  624        = %45.sub2               | v2                 | v2
3213 ///  800    %31 = COPY %45        +      +             +      +
3214 ///                               | v0                 | v0
3215 ///  816    %31.sub1 = ...        +                    |
3216 ///  880    %30 = COPY %31        | v1                 +
3217 ///  928    %45 = COPY %30        |      +                    +
3218 ///                               |      | v0                 | v0  <--+
3219 ///  992B   ; backedge -> bb.1    |      +                    +        |
3220 /// 1040        = %31.sub0        +                                    |
3221 ///                                                 This value must remain
3222 ///                                                 live-out!
3223 ///
3224 /// Assuming that %31 is coalesced into %45, the copy at 928 becomes
3225 /// redundant, since it copies the value from %45 back into it. The
3226 /// conflict resolution for the main range determines that %45.v0 is
3227 /// to be erased, which is ok since %31.v1 is identical to it.
3228 /// The problem happens with the subrange for sub2: it has to be live
3229 /// on exit from the block, but since 928 was actually a point of
3230 /// definition of %45.sub2, %45.sub2 was not live immediately prior
3231 /// to that definition. As a result, when 928 was erased, the value v0
3232 /// for %45.sub2 was pruned in pruneSubRegValues. Consequently, an
3233 /// IMPLICIT_DEF was inserted as a "backedge" definition for %45.sub2,
3234 /// providing an incorrect value to the use at 624.
3235 ///
3236 /// Since the main-range values %31.v1 and %45.v0 were proved to be
3237 /// identical, the corresponding values in subranges must also be the
3238 /// same. A redundant copy is removed because it's not needed, and not
3239 /// because it copied an undefined value, so any liveness that originated
3240 /// from that copy cannot disappear. When pruning a value that started
3241 /// at the removed copy, the corresponding identical value must be
3242 /// extended to replace it.
3243 void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) {
3244   // Look for values being erased.
3245   bool DidPrune = false;
3246   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3247     Val &V = Vals[i];
3248     // We should trigger in all cases in which eraseInstrs() does something.
3249     // match what eraseInstrs() is doing, print a message so
3250     if (V.Resolution != CR_Erase &&
3251         (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned))
3252       continue;
3253 
3254     // Check subranges at the point where the copy will be removed.
3255     SlotIndex Def = LR.getValNumInfo(i)->def;
3256     SlotIndex OtherDef;
3257     if (V.Identical)
3258       OtherDef = V.OtherVNI->def;
3259 
3260     // Print message so mismatches with eraseInstrs() can be diagnosed.
3261     LLVM_DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def
3262                       << '\n');
3263     for (LiveInterval::SubRange &S : LI.subranges()) {
3264       LiveQueryResult Q = S.Query(Def);
3265 
3266       // If a subrange starts at the copy then an undefined value has been
3267       // copied and we must remove that subrange value as well.
3268       VNInfo *ValueOut = Q.valueOutOrDead();
3269       if (ValueOut != nullptr && (Q.valueIn() == nullptr ||
3270                                   (V.Identical && V.Resolution == CR_Erase &&
3271                                    ValueOut->def == Def))) {
3272         LLVM_DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask)
3273                           << " at " << Def << "\n");
3274         SmallVector<SlotIndex,8> EndPoints;
3275         LIS->pruneValue(S, Def, &EndPoints);
3276         DidPrune = true;
3277         // Mark value number as unused.
3278         ValueOut->markUnused();
3279 
3280         if (V.Identical && S.Query(OtherDef).valueOutOrDead()) {
3281           // If V is identical to V.OtherVNI (and S was live at OtherDef),
3282           // then we can't simply prune V from S. V needs to be replaced
3283           // with V.OtherVNI.
3284           LIS->extendToIndices(S, EndPoints);
3285         }
3286 
3287         // We may need to eliminate the subrange if the copy introduced a live
3288         // out undef value.
3289         if (ValueOut->isPHIDef())
3290           ShrinkMask |= S.LaneMask;
3291         continue;
3292       }
3293 
3294       // If a subrange ends at the copy, then a value was copied but only
3295       // partially used later. Shrink the subregister range appropriately.
3296       //
3297       // Ultimately this calls shrinkToUses, so assuming ShrinkMask is
3298       // conservatively correct.
3299       if ((Q.valueIn() != nullptr && Q.valueOut() == nullptr) ||
3300           (V.Resolution == CR_Erase && isLiveThrough(Q))) {
3301         LLVM_DEBUG(dbgs() << "\t\tDead uses at sublane "
3302                           << PrintLaneMask(S.LaneMask) << " at " << Def
3303                           << "\n");
3304         ShrinkMask |= S.LaneMask;
3305       }
3306     }
3307   }
3308   if (DidPrune)
3309     LI.removeEmptySubRanges();
3310 }
3311 
3312 /// Check if any of the subranges of @p LI contain a definition at @p Def.
3313 static bool isDefInSubRange(LiveInterval &LI, SlotIndex Def) {
3314   for (LiveInterval::SubRange &SR : LI.subranges()) {
3315     if (VNInfo *VNI = SR.Query(Def).valueOutOrDead())
3316       if (VNI->def == Def)
3317         return true;
3318   }
3319   return false;
3320 }
3321 
3322 void JoinVals::pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange) {
3323   assert(&static_cast<LiveRange&>(LI) == &LR);
3324 
3325   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3326     if (Vals[i].Resolution != CR_Keep)
3327       continue;
3328     VNInfo *VNI = LR.getValNumInfo(i);
3329     if (VNI->isUnused() || VNI->isPHIDef() || isDefInSubRange(LI, VNI->def))
3330       continue;
3331     Vals[i].Pruned = true;
3332     ShrinkMainRange = true;
3333   }
3334 }
3335 
3336 void JoinVals::removeImplicitDefs() {
3337   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3338     Val &V = Vals[i];
3339     if (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned)
3340       continue;
3341 
3342     VNInfo *VNI = LR.getValNumInfo(i);
3343     VNI->markUnused();
3344     LR.removeValNo(VNI);
3345   }
3346 }
3347 
3348 void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
3349                            SmallVectorImpl<Register> &ShrinkRegs,
3350                            LiveInterval *LI) {
3351   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
3352     // Get the def location before markUnused() below invalidates it.
3353     VNInfo *VNI = LR.getValNumInfo(i);
3354     SlotIndex Def = VNI->def;
3355     switch (Vals[i].Resolution) {
3356     case CR_Keep: {
3357       // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any
3358       // longer. The IMPLICIT_DEF instructions are only inserted by
3359       // PHIElimination to guarantee that all PHI predecessors have a value.
3360       if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)
3361         break;
3362       // Remove value number i from LR.
3363       // For intervals with subranges, removing a segment from the main range
3364       // may require extending the previous segment: for each definition of
3365       // a subregister, there will be a corresponding def in the main range.
3366       // That def may fall in the middle of a segment from another subrange.
3367       // In such cases, removing this def from the main range must be
3368       // complemented by extending the main range to account for the liveness
3369       // of the other subrange.
3370       // The new end point of the main range segment to be extended.
3371       SlotIndex NewEnd;
3372       if (LI != nullptr) {
3373         LiveRange::iterator I = LR.FindSegmentContaining(Def);
3374         assert(I != LR.end());
3375         // Do not extend beyond the end of the segment being removed.
3376         // The segment may have been pruned in preparation for joining
3377         // live ranges.
3378         NewEnd = I->end;
3379       }
3380 
3381       LR.removeValNo(VNI);
3382       // Note that this VNInfo is reused and still referenced in NewVNInfo,
3383       // make it appear like an unused value number.
3384       VNI->markUnused();
3385 
3386       if (LI != nullptr && LI->hasSubRanges()) {
3387         assert(static_cast<LiveRange*>(LI) == &LR);
3388         // Determine the end point based on the subrange information:
3389         // minimum of (earliest def of next segment,
3390         //             latest end point of containing segment)
3391         SlotIndex ED, LE;
3392         for (LiveInterval::SubRange &SR : LI->subranges()) {
3393           LiveRange::iterator I = SR.find(Def);
3394           if (I == SR.end())
3395             continue;
3396           if (I->start > Def)
3397             ED = ED.isValid() ? std::min(ED, I->start) : I->start;
3398           else
3399             LE = LE.isValid() ? std::max(LE, I->end) : I->end;
3400         }
3401         if (LE.isValid())
3402           NewEnd = std::min(NewEnd, LE);
3403         if (ED.isValid())
3404           NewEnd = std::min(NewEnd, ED);
3405 
3406         // We only want to do the extension if there was a subrange that
3407         // was live across Def.
3408         if (LE.isValid()) {
3409           LiveRange::iterator S = LR.find(Def);
3410           if (S != LR.begin())
3411             std::prev(S)->end = NewEnd;
3412         }
3413       }
3414       LLVM_DEBUG({
3415         dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n';
3416         if (LI != nullptr)
3417           dbgs() << "\t\t  LHS = " << *LI << '\n';
3418       });
3419       [[fallthrough]];
3420     }
3421 
3422     case CR_Erase: {
3423       MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
3424       assert(MI && "No instruction to erase");
3425       if (MI->isCopy()) {
3426         Register Reg = MI->getOperand(1).getReg();
3427         if (Reg.isVirtual() && Reg != CP.getSrcReg() && Reg != CP.getDstReg())
3428           ShrinkRegs.push_back(Reg);
3429       }
3430       ErasedInstrs.insert(MI);
3431       LLVM_DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI);
3432       LIS->RemoveMachineInstrFromMaps(*MI);
3433       MI->eraseFromParent();
3434       break;
3435     }
3436     default:
3437       break;
3438     }
3439   }
3440 }
3441 
3442 void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
3443                                          LaneBitmask LaneMask,
3444                                          const CoalescerPair &CP) {
3445   SmallVector<VNInfo*, 16> NewVNInfo;
3446   JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask,
3447                    NewVNInfo, CP, LIS, TRI, true, true);
3448   JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask,
3449                    NewVNInfo, CP, LIS, TRI, true, true);
3450 
3451   // Compute NewVNInfo and resolve conflicts (see also joinVirtRegs())
3452   // We should be able to resolve all conflicts here as we could successfully do
3453   // it on the mainrange already. There is however a problem when multiple
3454   // ranges get mapped to the "overflow" lane mask bit which creates unexpected
3455   // interferences.
3456   if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {
3457     // We already determined that it is legal to merge the intervals, so this
3458     // should never fail.
3459     llvm_unreachable("*** Couldn't join subrange!\n");
3460   }
3461   if (!LHSVals.resolveConflicts(RHSVals) ||
3462       !RHSVals.resolveConflicts(LHSVals)) {
3463     // We already determined that it is legal to merge the intervals, so this
3464     // should never fail.
3465     llvm_unreachable("*** Couldn't join subrange!\n");
3466   }
3467 
3468   // The merging algorithm in LiveInterval::join() can't handle conflicting
3469   // value mappings, so we need to remove any live ranges that overlap a
3470   // CR_Replace resolution. Collect a set of end points that can be used to
3471   // restore the live range after joining.
3472   SmallVector<SlotIndex, 8> EndPoints;
3473   LHSVals.pruneValues(RHSVals, EndPoints, false);
3474   RHSVals.pruneValues(LHSVals, EndPoints, false);
3475 
3476   LHSVals.removeImplicitDefs();
3477   RHSVals.removeImplicitDefs();
3478 
3479   LRange.verify();
3480   RRange.verify();
3481 
3482   // Join RRange into LHS.
3483   LRange.join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),
3484               NewVNInfo);
3485 
3486   LLVM_DEBUG(dbgs() << "\t\tjoined lanes: " << PrintLaneMask(LaneMask)
3487                     << ' ' << LRange << "\n");
3488   if (EndPoints.empty())
3489     return;
3490 
3491   // Recompute the parts of the live range we had to remove because of
3492   // CR_Replace conflicts.
3493   LLVM_DEBUG({
3494     dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";
3495     for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {
3496       dbgs() << EndPoints[i];
3497       if (i != n-1)
3498         dbgs() << ',';
3499     }
3500     dbgs() << ":  " << LRange << '\n';
3501   });
3502   LIS->extendToIndices(LRange, EndPoints);
3503 }
3504 
3505 void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
3506                                           const LiveRange &ToMerge,
3507                                           LaneBitmask LaneMask,
3508                                           CoalescerPair &CP,
3509                                           unsigned ComposeSubRegIdx) {
3510   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
3511   LI.refineSubRanges(
3512       Allocator, LaneMask,
3513       [this, &Allocator, &ToMerge, &CP](LiveInterval::SubRange &SR) {
3514         if (SR.empty()) {
3515           SR.assign(ToMerge, Allocator);
3516         } else {
3517           // joinSubRegRange() destroys the merged range, so we need a copy.
3518           LiveRange RangeCopy(ToMerge, Allocator);
3519           joinSubRegRanges(SR, RangeCopy, SR.LaneMask, CP);
3520         }
3521       },
3522       *LIS->getSlotIndexes(), *TRI, ComposeSubRegIdx);
3523 }
3524 
3525 bool RegisterCoalescer::isHighCostLiveInterval(LiveInterval &LI) {
3526   if (LI.valnos.size() < LargeIntervalSizeThreshold)
3527     return false;
3528   auto &Counter = LargeLIVisitCounter[LI.reg()];
3529   if (Counter < LargeIntervalFreqThreshold) {
3530     Counter++;
3531     return false;
3532   }
3533   return true;
3534 }
3535 
3536 bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
3537   SmallVector<VNInfo*, 16> NewVNInfo;
3538   LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
3539   LiveInterval &LHS = LIS->getInterval(CP.getDstReg());
3540   bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC());
3541   JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), LaneBitmask::getNone(),
3542                    NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
3543   JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), LaneBitmask::getNone(),
3544                    NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
3545 
3546   LLVM_DEBUG(dbgs() << "\t\tRHS = " << RHS << "\n\t\tLHS = " << LHS << '\n');
3547 
3548   if (isHighCostLiveInterval(LHS) || isHighCostLiveInterval(RHS))
3549     return false;
3550 
3551   // First compute NewVNInfo and the simple value mappings.
3552   // Detect impossible conflicts early.
3553   if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))
3554     return false;
3555 
3556   // Some conflicts can only be resolved after all values have been mapped.
3557   if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))
3558     return false;
3559 
3560   // All clear, the live ranges can be merged.
3561   if (RHS.hasSubRanges() || LHS.hasSubRanges()) {
3562     BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
3563 
3564     // Transform lanemasks from the LHS to masks in the coalesced register and
3565     // create initial subranges if necessary.
3566     unsigned DstIdx = CP.getDstIdx();
3567     if (!LHS.hasSubRanges()) {
3568       LaneBitmask Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask()
3569                                      : TRI->getSubRegIndexLaneMask(DstIdx);
3570       // LHS must support subregs or we wouldn't be in this codepath.
3571       assert(Mask.any());
3572       LHS.createSubRangeFrom(Allocator, Mask, LHS);
3573     } else if (DstIdx != 0) {
3574       // Transform LHS lanemasks to new register class if necessary.
3575       for (LiveInterval::SubRange &R : LHS.subranges()) {
3576         LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask);
3577         R.LaneMask = Mask;
3578       }
3579     }
3580     LLVM_DEBUG(dbgs() << "\t\tLHST = " << printReg(CP.getDstReg()) << ' ' << LHS
3581                       << '\n');
3582 
3583     // Determine lanemasks of RHS in the coalesced register and merge subranges.
3584     unsigned SrcIdx = CP.getSrcIdx();
3585     if (!RHS.hasSubRanges()) {
3586       LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
3587                                      : TRI->getSubRegIndexLaneMask(SrcIdx);
3588       mergeSubRangeInto(LHS, RHS, Mask, CP, DstIdx);
3589     } else {
3590       // Pair up subranges and merge.
3591       for (LiveInterval::SubRange &R : RHS.subranges()) {
3592         LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);
3593         mergeSubRangeInto(LHS, R, Mask, CP, DstIdx);
3594       }
3595     }
3596     LLVM_DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n");
3597 
3598     // Pruning implicit defs from subranges may result in the main range
3599     // having stale segments.
3600     LHSVals.pruneMainSegments(LHS, ShrinkMainRange);
3601 
3602     LHSVals.pruneSubRegValues(LHS, ShrinkMask);
3603     RHSVals.pruneSubRegValues(LHS, ShrinkMask);
3604   }
3605 
3606   // The merging algorithm in LiveInterval::join() can't handle conflicting
3607   // value mappings, so we need to remove any live ranges that overlap a
3608   // CR_Replace resolution. Collect a set of end points that can be used to
3609   // restore the live range after joining.
3610   SmallVector<SlotIndex, 8> EndPoints;
3611   LHSVals.pruneValues(RHSVals, EndPoints, true);
3612   RHSVals.pruneValues(LHSVals, EndPoints, true);
3613 
3614   // Erase COPY and IMPLICIT_DEF instructions. This may cause some external
3615   // registers to require trimming.
3616   SmallVector<Register, 8> ShrinkRegs;
3617   LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &LHS);
3618   RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
3619   while (!ShrinkRegs.empty())
3620     shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
3621 
3622   // Scan and mark undef any DBG_VALUEs that would refer to a different value.
3623   checkMergingChangesDbgValues(CP, LHS, LHSVals, RHS, RHSVals);
3624 
3625   // If the RHS covers any PHI locations that were tracked for debug-info, we
3626   // must update tracking information to reflect the join.
3627   auto RegIt = RegToPHIIdx.find(CP.getSrcReg());
3628   if (RegIt != RegToPHIIdx.end()) {
3629     // Iterate over all the debug instruction numbers assigned this register.
3630     for (unsigned InstID : RegIt->second) {
3631       auto PHIIt = PHIValToPos.find(InstID);
3632       assert(PHIIt != PHIValToPos.end());
3633       const SlotIndex &SI = PHIIt->second.SI;
3634 
3635       // Does the RHS cover the position of this PHI?
3636       auto LII = RHS.find(SI);
3637       if (LII == RHS.end() || LII->start > SI)
3638         continue;
3639 
3640       // Accept two kinds of subregister movement:
3641       //  * When we merge from one register class into a larger register:
3642       //        %1:gr16 = some-inst
3643       //                ->
3644       //        %2:gr32.sub_16bit = some-inst
3645       //  * When the PHI is already in a subregister, and the larger class
3646       //    is coalesced:
3647       //        %2:gr32.sub_16bit = some-inst
3648       //        %3:gr32 = COPY %2
3649       //                ->
3650       //        %3:gr32.sub_16bit = some-inst
3651       // Test for subregister move:
3652       if (CP.getSrcIdx() != 0 || CP.getDstIdx() != 0)
3653         // If we're moving between different subregisters, ignore this join.
3654         // The PHI will not get a location, dropping variable locations.
3655         if (PHIIt->second.SubReg && PHIIt->second.SubReg != CP.getSrcIdx())
3656           continue;
3657 
3658       // Update our tracking of where the PHI is.
3659       PHIIt->second.Reg = CP.getDstReg();
3660 
3661       // If we merge into a sub-register of a larger class (test above),
3662       // update SubReg.
3663       if (CP.getSrcIdx() != 0)
3664         PHIIt->second.SubReg = CP.getSrcIdx();
3665     }
3666 
3667     // Rebuild the register index in RegToPHIIdx to account for PHIs tracking
3668     // different VRegs now. Copy old collection of debug instruction numbers and
3669     // erase the old one:
3670     auto InstrNums = RegIt->second;
3671     RegToPHIIdx.erase(RegIt);
3672 
3673     // There might already be PHIs being tracked in the destination VReg. Insert
3674     // into an existing tracking collection, or insert a new one.
3675     RegIt = RegToPHIIdx.find(CP.getDstReg());
3676     if (RegIt != RegToPHIIdx.end())
3677       RegIt->second.insert(RegIt->second.end(), InstrNums.begin(),
3678                            InstrNums.end());
3679     else
3680       RegToPHIIdx.insert({CP.getDstReg(), InstrNums});
3681   }
3682 
3683   // Join RHS into LHS.
3684   LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
3685 
3686   // Kill flags are going to be wrong if the live ranges were overlapping.
3687   // Eventually, we should simply clear all kill flags when computing live
3688   // ranges. They are reinserted after register allocation.
3689   MRI->clearKillFlags(LHS.reg());
3690   MRI->clearKillFlags(RHS.reg());
3691 
3692   if (!EndPoints.empty()) {
3693     // Recompute the parts of the live range we had to remove because of
3694     // CR_Replace conflicts.
3695     LLVM_DEBUG({
3696       dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";
3697       for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {
3698         dbgs() << EndPoints[i];
3699         if (i != n-1)
3700           dbgs() << ',';
3701       }
3702       dbgs() << ":  " << LHS << '\n';
3703     });
3704     LIS->extendToIndices((LiveRange&)LHS, EndPoints);
3705   }
3706 
3707   return true;
3708 }
3709 
3710 bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
3711   return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
3712 }
3713 
3714 void RegisterCoalescer::buildVRegToDbgValueMap(MachineFunction &MF)
3715 {
3716   const SlotIndexes &Slots = *LIS->getSlotIndexes();
3717   SmallVector<MachineInstr *, 8> ToInsert;
3718 
3719   // After collecting a block of DBG_VALUEs into ToInsert, enter them into the
3720   // vreg => DbgValueLoc map.
3721   auto CloseNewDVRange = [this, &ToInsert](SlotIndex Slot) {
3722     for (auto *X : ToInsert) {
3723       for (const auto &Op : X->debug_operands()) {
3724         if (Op.isReg() && Op.getReg().isVirtual())
3725           DbgVRegToValues[Op.getReg()].push_back({Slot, X});
3726       }
3727     }
3728 
3729     ToInsert.clear();
3730   };
3731 
3732   // Iterate over all instructions, collecting them into the ToInsert vector.
3733   // Once a non-debug instruction is found, record the slot index of the
3734   // collected DBG_VALUEs.
3735   for (auto &MBB : MF) {
3736     SlotIndex CurrentSlot = Slots.getMBBStartIdx(&MBB);
3737 
3738     for (auto &MI : MBB) {
3739       if (MI.isDebugValue()) {
3740         if (any_of(MI.debug_operands(), [](const MachineOperand &MO) {
3741               return MO.isReg() && MO.getReg().isVirtual();
3742             }))
3743           ToInsert.push_back(&MI);
3744       } else if (!MI.isDebugOrPseudoInstr()) {
3745         CurrentSlot = Slots.getInstructionIndex(MI);
3746         CloseNewDVRange(CurrentSlot);
3747       }
3748     }
3749 
3750     // Close range of DBG_VALUEs at the end of blocks.
3751     CloseNewDVRange(Slots.getMBBEndIdx(&MBB));
3752   }
3753 
3754   // Sort all DBG_VALUEs we've seen by slot number.
3755   for (auto &Pair : DbgVRegToValues)
3756     llvm::sort(Pair.second);
3757 }
3758 
3759 void RegisterCoalescer::checkMergingChangesDbgValues(CoalescerPair &CP,
3760                                                      LiveRange &LHS,
3761                                                      JoinVals &LHSVals,
3762                                                      LiveRange &RHS,
3763                                                      JoinVals &RHSVals) {
3764   auto ScanForDstReg = [&](Register Reg) {
3765     checkMergingChangesDbgValuesImpl(Reg, RHS, LHS, LHSVals);
3766   };
3767 
3768   auto ScanForSrcReg = [&](Register Reg) {
3769     checkMergingChangesDbgValuesImpl(Reg, LHS, RHS, RHSVals);
3770   };
3771 
3772   // Scan for unsound updates of both the source and destination register.
3773   ScanForSrcReg(CP.getSrcReg());
3774   ScanForDstReg(CP.getDstReg());
3775 }
3776 
3777 void RegisterCoalescer::checkMergingChangesDbgValuesImpl(Register Reg,
3778                                                          LiveRange &OtherLR,
3779                                                          LiveRange &RegLR,
3780                                                          JoinVals &RegVals) {
3781   // Are there any DBG_VALUEs to examine?
3782   auto VRegMapIt = DbgVRegToValues.find(Reg);
3783   if (VRegMapIt == DbgVRegToValues.end())
3784     return;
3785 
3786   auto &DbgValueSet = VRegMapIt->second;
3787   auto DbgValueSetIt = DbgValueSet.begin();
3788   auto SegmentIt = OtherLR.begin();
3789 
3790   bool LastUndefResult = false;
3791   SlotIndex LastUndefIdx;
3792 
3793   // If the "Other" register is live at a slot Idx, test whether Reg can
3794   // safely be merged with it, or should be marked undef.
3795   auto ShouldUndef = [&RegVals, &RegLR, &LastUndefResult,
3796                       &LastUndefIdx](SlotIndex Idx) -> bool {
3797     // Our worst-case performance typically happens with asan, causing very
3798     // many DBG_VALUEs of the same location. Cache a copy of the most recent
3799     // result for this edge-case.
3800     if (LastUndefIdx == Idx)
3801       return LastUndefResult;
3802 
3803     // If the other range was live, and Reg's was not, the register coalescer
3804     // will not have tried to resolve any conflicts. We don't know whether
3805     // the DBG_VALUE will refer to the same value number, so it must be made
3806     // undef.
3807     auto OtherIt = RegLR.find(Idx);
3808     if (OtherIt == RegLR.end())
3809       return true;
3810 
3811     // Both the registers were live: examine the conflict resolution record for
3812     // the value number Reg refers to. CR_Keep meant that this value number
3813     // "won" and the merged register definitely refers to that value. CR_Erase
3814     // means the value number was a redundant copy of the other value, which
3815     // was coalesced and Reg deleted. It's safe to refer to the other register
3816     // (which will be the source of the copy).
3817     auto Resolution = RegVals.getResolution(OtherIt->valno->id);
3818     LastUndefResult = Resolution != JoinVals::CR_Keep &&
3819                       Resolution != JoinVals::CR_Erase;
3820     LastUndefIdx = Idx;
3821     return LastUndefResult;
3822   };
3823 
3824   // Iterate over both the live-range of the "Other" register, and the set of
3825   // DBG_VALUEs for Reg at the same time. Advance whichever one has the lowest
3826   // slot index. This relies on the DbgValueSet being ordered.
3827   while (DbgValueSetIt != DbgValueSet.end() && SegmentIt != OtherLR.end()) {
3828     if (DbgValueSetIt->first < SegmentIt->end) {
3829       // "Other" is live and there is a DBG_VALUE of Reg: test if we should
3830       // set it undef.
3831       if (DbgValueSetIt->first >= SegmentIt->start) {
3832         bool HasReg = DbgValueSetIt->second->hasDebugOperandForReg(Reg);
3833         bool ShouldUndefReg = ShouldUndef(DbgValueSetIt->first);
3834         if (HasReg && ShouldUndefReg) {
3835           // Mark undef, erase record of this DBG_VALUE to avoid revisiting.
3836           DbgValueSetIt->second->setDebugValueUndef();
3837           continue;
3838         }
3839       }
3840       ++DbgValueSetIt;
3841     } else {
3842       ++SegmentIt;
3843     }
3844   }
3845 }
3846 
3847 namespace {
3848 
3849 /// Information concerning MBB coalescing priority.
3850 struct MBBPriorityInfo {
3851   MachineBasicBlock *MBB;
3852   unsigned Depth;
3853   bool IsSplit;
3854 
3855   MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit)
3856     : MBB(mbb), Depth(depth), IsSplit(issplit) {}
3857 };
3858 
3859 } // end anonymous namespace
3860 
3861 /// C-style comparator that sorts first based on the loop depth of the basic
3862 /// block (the unsigned), and then on the MBB number.
3863 ///
3864 /// EnableGlobalCopies assumes that the primary sort key is loop depth.
3865 static int compareMBBPriority(const MBBPriorityInfo *LHS,
3866                               const MBBPriorityInfo *RHS) {
3867   // Deeper loops first
3868   if (LHS->Depth != RHS->Depth)
3869     return LHS->Depth > RHS->Depth ? -1 : 1;
3870 
3871   // Try to unsplit critical edges next.
3872   if (LHS->IsSplit != RHS->IsSplit)
3873     return LHS->IsSplit ? -1 : 1;
3874 
3875   // Prefer blocks that are more connected in the CFG. This takes care of
3876   // the most difficult copies first while intervals are short.
3877   unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size();
3878   unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size();
3879   if (cl != cr)
3880     return cl > cr ? -1 : 1;
3881 
3882   // As a last resort, sort by block number.
3883   return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1;
3884 }
3885 
3886 /// \returns true if the given copy uses or defines a local live range.
3887 static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) {
3888   if (!Copy->isCopy())
3889     return false;
3890 
3891   if (Copy->getOperand(1).isUndef())
3892     return false;
3893 
3894   Register SrcReg = Copy->getOperand(1).getReg();
3895   Register DstReg = Copy->getOperand(0).getReg();
3896   if (SrcReg.isPhysical() || DstReg.isPhysical())
3897     return false;
3898 
3899   return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg))
3900     || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg));
3901 }
3902 
3903 void RegisterCoalescer::lateLiveIntervalUpdate() {
3904   for (Register reg : ToBeUpdated) {
3905     if (!LIS->hasInterval(reg))
3906       continue;
3907     LiveInterval &LI = LIS->getInterval(reg);
3908     shrinkToUses(&LI, &DeadDefs);
3909     if (!DeadDefs.empty())
3910       eliminateDeadDefs();
3911   }
3912   ToBeUpdated.clear();
3913 }
3914 
3915 bool RegisterCoalescer::
3916 copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) {
3917   bool Progress = false;
3918   for (MachineInstr *&MI : CurrList) {
3919     if (!MI)
3920       continue;
3921     // Skip instruction pointers that have already been erased, for example by
3922     // dead code elimination.
3923     if (ErasedInstrs.count(MI)) {
3924       MI = nullptr;
3925       continue;
3926     }
3927     bool Again = false;
3928     bool Success = joinCopy(MI, Again);
3929     Progress |= Success;
3930     if (Success || !Again)
3931       MI = nullptr;
3932   }
3933   return Progress;
3934 }
3935 
3936 /// Check if DstReg is a terminal node.
3937 /// I.e., it does not have any affinity other than \p Copy.
3938 static bool isTerminalReg(Register DstReg, const MachineInstr &Copy,
3939                           const MachineRegisterInfo *MRI) {
3940   assert(Copy.isCopyLike());
3941   // Check if the destination of this copy as any other affinity.
3942   for (const MachineInstr &MI : MRI->reg_nodbg_instructions(DstReg))
3943     if (&MI != &Copy && MI.isCopyLike())
3944       return false;
3945   return true;
3946 }
3947 
3948 bool RegisterCoalescer::applyTerminalRule(const MachineInstr &Copy) const {
3949   assert(Copy.isCopyLike());
3950   if (!UseTerminalRule)
3951     return false;
3952   Register SrcReg, DstReg;
3953   unsigned SrcSubReg = 0, DstSubReg = 0;
3954   if (!isMoveInstr(*TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg))
3955     return false;
3956   // Check if the destination of this copy has any other affinity.
3957   if (DstReg.isPhysical() ||
3958       // If SrcReg is a physical register, the copy won't be coalesced.
3959       // Ignoring it may have other side effect (like missing
3960       // rematerialization). So keep it.
3961       SrcReg.isPhysical() || !isTerminalReg(DstReg, Copy, MRI))
3962     return false;
3963 
3964   // DstReg is a terminal node. Check if it interferes with any other
3965   // copy involving SrcReg.
3966   const MachineBasicBlock *OrigBB = Copy.getParent();
3967   const LiveInterval &DstLI = LIS->getInterval(DstReg);
3968   for (const MachineInstr &MI : MRI->reg_nodbg_instructions(SrcReg)) {
3969     // Technically we should check if the weight of the new copy is
3970     // interesting compared to the other one and update the weight
3971     // of the copies accordingly. However, this would only work if
3972     // we would gather all the copies first then coalesce, whereas
3973     // right now we interleave both actions.
3974     // For now, just consider the copies that are in the same block.
3975     if (&MI == &Copy || !MI.isCopyLike() || MI.getParent() != OrigBB)
3976       continue;
3977     Register OtherSrcReg, OtherReg;
3978     unsigned OtherSrcSubReg = 0, OtherSubReg = 0;
3979     if (!isMoveInstr(*TRI, &Copy, OtherSrcReg, OtherReg, OtherSrcSubReg,
3980                 OtherSubReg))
3981       return false;
3982     if (OtherReg == SrcReg)
3983       OtherReg = OtherSrcReg;
3984     // Check if OtherReg is a non-terminal.
3985     if (OtherReg.isPhysical() || isTerminalReg(OtherReg, MI, MRI))
3986       continue;
3987     // Check that OtherReg interfere with DstReg.
3988     if (LIS->getInterval(OtherReg).overlaps(DstLI)) {
3989       LLVM_DEBUG(dbgs() << "Apply terminal rule for: " << printReg(DstReg)
3990                         << '\n');
3991       return true;
3992     }
3993   }
3994   return false;
3995 }
3996 
3997 void
3998 RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) {
3999   LLVM_DEBUG(dbgs() << MBB->getName() << ":\n");
4000 
4001   // Collect all copy-like instructions in MBB. Don't start coalescing anything
4002   // yet, it might invalidate the iterator.
4003   const unsigned PrevSize = WorkList.size();
4004   if (JoinGlobalCopies) {
4005     SmallVector<MachineInstr*, 2> LocalTerminals;
4006     SmallVector<MachineInstr*, 2> GlobalTerminals;
4007     // Coalesce copies bottom-up to coalesce local defs before local uses. They
4008     // are not inherently easier to resolve, but slightly preferable until we
4009     // have local live range splitting. In particular this is required by
4010     // cmp+jmp macro fusion.
4011     for (MachineInstr &MI : *MBB) {
4012       if (!MI.isCopyLike())
4013         continue;
4014       bool ApplyTerminalRule = applyTerminalRule(MI);
4015       if (isLocalCopy(&MI, LIS)) {
4016         if (ApplyTerminalRule)
4017           LocalTerminals.push_back(&MI);
4018         else
4019           LocalWorkList.push_back(&MI);
4020       } else {
4021         if (ApplyTerminalRule)
4022           GlobalTerminals.push_back(&MI);
4023         else
4024           WorkList.push_back(&MI);
4025       }
4026     }
4027     // Append the copies evicted by the terminal rule at the end of the list.
4028     LocalWorkList.append(LocalTerminals.begin(), LocalTerminals.end());
4029     WorkList.append(GlobalTerminals.begin(), GlobalTerminals.end());
4030   }
4031   else {
4032     SmallVector<MachineInstr*, 2> Terminals;
4033     for (MachineInstr &MII : *MBB)
4034       if (MII.isCopyLike()) {
4035         if (applyTerminalRule(MII))
4036           Terminals.push_back(&MII);
4037         else
4038           WorkList.push_back(&MII);
4039       }
4040     // Append the copies evicted by the terminal rule at the end of the list.
4041     WorkList.append(Terminals.begin(), Terminals.end());
4042   }
4043   // Try coalescing the collected copies immediately, and remove the nulls.
4044   // This prevents the WorkList from getting too large since most copies are
4045   // joinable on the first attempt.
4046   MutableArrayRef<MachineInstr*>
4047     CurrList(WorkList.begin() + PrevSize, WorkList.end());
4048   if (copyCoalesceWorkList(CurrList))
4049     WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(),
4050                                nullptr), WorkList.end());
4051 }
4052 
4053 void RegisterCoalescer::coalesceLocals() {
4054   copyCoalesceWorkList(LocalWorkList);
4055   for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) {
4056     if (LocalWorkList[j])
4057       WorkList.push_back(LocalWorkList[j]);
4058   }
4059   LocalWorkList.clear();
4060 }
4061 
4062 void RegisterCoalescer::joinAllIntervals() {
4063   LLVM_DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n");
4064   assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around.");
4065 
4066   std::vector<MBBPriorityInfo> MBBs;
4067   MBBs.reserve(MF->size());
4068   for (MachineBasicBlock &MBB : *MF) {
4069     MBBs.push_back(MBBPriorityInfo(&MBB, Loops->getLoopDepth(&MBB),
4070                                    JoinSplitEdges && isSplitEdge(&MBB)));
4071   }
4072   array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority);
4073 
4074   // Coalesce intervals in MBB priority order.
4075   unsigned CurrDepth = std::numeric_limits<unsigned>::max();
4076   for (MBBPriorityInfo &MBB : MBBs) {
4077     // Try coalescing the collected local copies for deeper loops.
4078     if (JoinGlobalCopies && MBB.Depth < CurrDepth) {
4079       coalesceLocals();
4080       CurrDepth = MBB.Depth;
4081     }
4082     copyCoalesceInMBB(MBB.MBB);
4083   }
4084   lateLiveIntervalUpdate();
4085   coalesceLocals();
4086 
4087   // Joining intervals can allow other intervals to be joined.  Iteratively join
4088   // until we make no progress.
4089   while (copyCoalesceWorkList(WorkList))
4090     /* empty */ ;
4091   lateLiveIntervalUpdate();
4092 }
4093 
4094 void RegisterCoalescer::releaseMemory() {
4095   ErasedInstrs.clear();
4096   WorkList.clear();
4097   DeadDefs.clear();
4098   InflateRegs.clear();
4099   LargeLIVisitCounter.clear();
4100 }
4101 
4102 bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) {
4103   LLVM_DEBUG(dbgs() << "********** REGISTER COALESCER **********\n"
4104                     << "********** Function: " << fn.getName() << '\n');
4105 
4106   // Variables changed between a setjmp and a longjump can have undefined value
4107   // after the longjmp. This behaviour can be observed if such a variable is
4108   // spilled, so longjmp won't restore the value in the spill slot.
4109   // RegisterCoalescer should not run in functions with a setjmp to avoid
4110   // merging such undefined variables with predictable ones.
4111   //
4112   // TODO: Could specifically disable coalescing registers live across setjmp
4113   // calls
4114   if (fn.exposesReturnsTwice()) {
4115     LLVM_DEBUG(
4116         dbgs() << "* Skipped as it exposes functions that returns twice.\n");
4117     return false;
4118   }
4119 
4120   MF = &fn;
4121   MRI = &fn.getRegInfo();
4122   const TargetSubtargetInfo &STI = fn.getSubtarget();
4123   TRI = STI.getRegisterInfo();
4124   TII = STI.getInstrInfo();
4125   LIS = &getAnalysis<LiveIntervals>();
4126   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
4127   Loops = &getAnalysis<MachineLoopInfo>();
4128   if (EnableGlobalCopies == cl::BOU_UNSET)
4129     JoinGlobalCopies = STI.enableJoinGlobalCopies();
4130   else
4131     JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE);
4132 
4133   // If there are PHIs tracked by debug-info, they will need updating during
4134   // coalescing. Build an index of those PHIs to ease updating.
4135   SlotIndexes *Slots = LIS->getSlotIndexes();
4136   for (const auto &DebugPHI : MF->DebugPHIPositions) {
4137     MachineBasicBlock *MBB = DebugPHI.second.MBB;
4138     Register Reg = DebugPHI.second.Reg;
4139     unsigned SubReg = DebugPHI.second.SubReg;
4140     SlotIndex SI = Slots->getMBBStartIdx(MBB);
4141     PHIValPos P = {SI, Reg, SubReg};
4142     PHIValToPos.insert(std::make_pair(DebugPHI.first, P));
4143     RegToPHIIdx[Reg].push_back(DebugPHI.first);
4144   }
4145 
4146   // The MachineScheduler does not currently require JoinSplitEdges. This will
4147   // either be enabled unconditionally or replaced by a more general live range
4148   // splitting optimization.
4149   JoinSplitEdges = EnableJoinSplits;
4150 
4151   if (VerifyCoalescing)
4152     MF->verify(this, "Before register coalescing");
4153 
4154   DbgVRegToValues.clear();
4155   buildVRegToDbgValueMap(fn);
4156 
4157   RegClassInfo.runOnMachineFunction(fn);
4158 
4159   // Join (coalesce) intervals if requested.
4160   if (EnableJoining)
4161     joinAllIntervals();
4162 
4163   // After deleting a lot of copies, register classes may be less constrained.
4164   // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 ->
4165   // DPR inflation.
4166   array_pod_sort(InflateRegs.begin(), InflateRegs.end());
4167   InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()),
4168                     InflateRegs.end());
4169   LLVM_DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size()
4170                     << " regs.\n");
4171   for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) {
4172     Register Reg = InflateRegs[i];
4173     if (MRI->reg_nodbg_empty(Reg))
4174       continue;
4175     if (MRI->recomputeRegClass(Reg)) {
4176       LLVM_DEBUG(dbgs() << printReg(Reg) << " inflated to "
4177                         << TRI->getRegClassName(MRI->getRegClass(Reg)) << '\n');
4178       ++NumInflated;
4179 
4180       LiveInterval &LI = LIS->getInterval(Reg);
4181       if (LI.hasSubRanges()) {
4182         // If the inflated register class does not support subregisters anymore
4183         // remove the subranges.
4184         if (!MRI->shouldTrackSubRegLiveness(Reg)) {
4185           LI.clearSubRanges();
4186         } else {
4187 #ifndef NDEBUG
4188           LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
4189           // If subranges are still supported, then the same subregs
4190           // should still be supported.
4191           for (LiveInterval::SubRange &S : LI.subranges()) {
4192             assert((S.LaneMask & ~MaxMask).none());
4193           }
4194 #endif
4195         }
4196       }
4197     }
4198   }
4199 
4200   // After coalescing, update any PHIs that are being tracked by debug-info
4201   // with their new VReg locations.
4202   for (auto &p : MF->DebugPHIPositions) {
4203     auto it = PHIValToPos.find(p.first);
4204     assert(it != PHIValToPos.end());
4205     p.second.Reg = it->second.Reg;
4206     p.second.SubReg = it->second.SubReg;
4207   }
4208 
4209   PHIValToPos.clear();
4210   RegToPHIIdx.clear();
4211 
4212   LLVM_DEBUG(dump());
4213   if (VerifyCoalescing)
4214     MF->verify(this, "After register coalescing");
4215   return true;
4216 }
4217 
4218 void RegisterCoalescer::print(raw_ostream &O, const Module* m) const {
4219    LIS->print(O, m);
4220 }
4221