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