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