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