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  /// \brief True if the coalescer should aggressively coalesce global copies
119  /// in favor of keeping local copies.
120  bool JoinGlobalCopies;
121 
122  /// \brief True if the coalescer should aggressively coalesce fall-thru
123  /// blocks exclusively containing copies.
124  bool JoinSplitEdges;
125 
126  /// Copy instructions yet to be coalesced.
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  DEBUG(dbgs() << "Extending: " << printReg(IntB.reg, TRI));
572 
573  SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;
574  // We are about to delete CopyMI, so need to remove it as the 'instruction
575  // that defines this value #'. Update the valnum with the new defining
576  // instruction #.
577  BValNo->def = FillerStart;
578 
579  // Okay, we can merge them. We need to insert a new liverange:
580  // [ValS.end, BS.begin) of either value number, then we merge the
581  // two value numbers.
582  IntB.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, BValNo));
583 
584  // Okay, merge "B1" into the same value number as "B0".
585  if (BValNo != ValS->valno)
586  IntB.MergeValueNumberInto(BValNo, ValS->valno);
587 
588  // Do the same for the subregister segments.
589  for (LiveInterval::SubRange &S : IntB.subranges()) {
590  VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
591  S.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo));
592  VNInfo *SubValSNo = S.getVNInfoAt(AValNo->def.getPrevSlot());
593  if (SubBValNo != SubValSNo)
594  S.MergeValueNumberInto(SubBValNo, SubValSNo);
595  }
596 
597  DEBUG(dbgs() << " result = " << IntB << '\n');
598 
599  // If the source instruction was killing the source register before the
600  // merge, unset the isKill marker given the live range has been extended.
601  int UIdx = ValSEndInst->findRegisterUseOperandIdx(IntB.reg, true);
602  if (UIdx != -1) {
603  ValSEndInst->getOperand(UIdx).setIsKill(false);
604  }
605 
606  // Rewrite the copy. If the copy instruction was killing the destination
607  // register before the merge, find the last use and trim the live range. That
608  // will also add the isKill marker.
609  CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI);
610  if (AS->end == CopyIdx)
611  shrinkToUses(&IntA);
612 
613  ++numExtends;
614  return true;
615 }
616 
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  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  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  DEBUG(dbgs() << "\t\textended: " << IntB << '\n');
857 
858  LIS->removeVRegDefAt(IntA, AValNo->def);
859 
860  DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n');
861  ++numCommutes;
862  return true;
863 }
864 
865 /// For copy B = A in BB2, if A is defined by A = B in BB0 which is a
866 /// predecessor of BB2, and if B is not redefined on the way from A = B
867 /// in BB2 to B = A in BB2, B = A in BB2 is partially redundant if the
868 /// execution goes through the path from BB0 to BB2. We may move B = A
869 /// to the predecessor without such reversed copy.
870 /// So we will transform the program from:
871 /// BB0:
872 /// A = B; BB1:
873 /// ... ...
874 /// / \ /
875 /// BB2:
876 /// ...
877 /// B = A;
878 ///
879 /// to:
880 ///
881 /// BB0: BB1:
882 /// A = B; ...
883 /// ... B = A;
884 /// / \ /
885 /// BB2:
886 /// ...
887 ///
888 /// A special case is when BB0 and BB2 are the same BB which is the only
889 /// BB in a loop:
890 /// BB1:
891 /// ...
892 /// BB0/BB2: ----
893 /// B = A; |
894 /// ... |
895 /// A = B; |
896 /// |-------
897 /// |
898 /// We may hoist B = A from BB0/BB2 to BB1.
899 ///
900 /// The major preconditions for correctness to remove such partial
901 /// redundancy include:
902 /// 1. A in B = A in BB2 is defined by a PHI in BB2, and one operand of
903 /// the PHI is defined by the reversed copy A = B in BB0.
904 /// 2. No B is referenced from the start of BB2 to B = A.
905 /// 3. No B is defined from A = B to the end of BB0.
906 /// 4. BB1 has only one successor.
907 ///
908 /// 2 and 4 implicitly ensure B is not live at the end of BB1.
909 /// 4 guarantees BB2 is hotter than BB1, so we can only move a copy to a
910 /// colder place, which not only prevent endless loop, but also make sure
911 /// the movement of copy is beneficial.
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 ok to move copy.
993  if (CopyLeftBB) {
994  DEBUG(dbgs() << "\tremovePartialRedundancy: Move the copy to "
995  << printMBBReference(*CopyLeftBB) << '\t' << CopyMI);
996 
997  // Insert new copy to CopyLeftBB.
998  auto InsPos = CopyLeftBB->getFirstTerminator();
999  MachineInstr *NewCopyMI = BuildMI(*CopyLeftBB, InsPos, CopyMI.getDebugLoc(),
1000  TII->get(TargetOpcode::COPY), IntB.reg)
1001  .addReg(IntA.reg);
1002  SlotIndex NewCopyIdx =
1003  LIS->InsertMachineInstrInMaps(*NewCopyMI).getRegSlot();
1004  IntB.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
1005  for (LiveInterval::SubRange &SR : IntB.subranges())
1006  SR.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
1007 
1008  // If the newly created Instruction has an address of an instruction that was
1009  // deleted before (object recycled by the allocator) it needs to be removed from
1010  // the deleted list.
1011  ErasedInstrs.erase(NewCopyMI);
1012  } else {
1013  DEBUG(dbgs() << "\tremovePartialRedundancy: Remove the copy from "
1014  << printMBBReference(MBB) << '\t' << CopyMI);
1015  }
1016 
1017  // Remove CopyMI.
1018  // Note: This is fine to remove the copy before updating the live-ranges.
1019  // While updating the live-ranges, we only look at slot indices and
1020  // never go back to the instruction.
1021  // Mark instructions as deleted.
1022  deleteInstr(&CopyMI);
1023 
1024  // Update the liveness.
1025  SmallVector<SlotIndex, 8> EndPoints;
1026  VNInfo *BValNo = IntB.Query(CopyIdx).valueOutOrDead();
1027  LIS->pruneValue(*static_cast<LiveRange *>(&IntB), CopyIdx.getRegSlot(),
1028  &EndPoints);
1029  BValNo->markUnused();
1030  // Extend IntB to the EndPoints of its original live interval.
1031  LIS->extendToIndices(IntB, EndPoints);
1032 
1033  // Now, do the same for its subranges.
1034  for (LiveInterval::SubRange &SR : IntB.subranges()) {
1035  EndPoints.clear();
1036  VNInfo *BValNo = SR.Query(CopyIdx).valueOutOrDead();
1037  assert(BValNo && "All sublanes should be live");
1038  LIS->pruneValue(SR, CopyIdx.getRegSlot(), &EndPoints);
1039  BValNo->markUnused();
1040  LIS->extendToIndices(SR, EndPoints);
1041  }
1042 
1043  // Finally, update the live-range of IntA.
1044  shrinkToUses(&IntA);
1045  return true;
1046 }
1047 
1048 /// Returns true if @p MI defines the full vreg @p Reg, as opposed to just
1049 /// defining a subregister.
1050 static bool definesFullReg(const MachineInstr &MI, unsigned Reg) {
1052  "This code cannot handle physreg aliasing");
1053  for (const MachineOperand &Op : MI.operands()) {
1054  if (!Op.isReg() || !Op.isDef() || Op.getReg() != Reg)
1055  continue;
1056  // Return true if we define the full register or don't care about the value
1057  // inside other subregisters.
1058  if (Op.getSubReg() == 0 || Op.isUndef())
1059  return true;
1060  }
1061  return false;
1062 }
1063 
1064 bool RegisterCoalescer::reMaterializeTrivialDef(const CoalescerPair &CP,
1065  MachineInstr *CopyMI,
1066  bool &IsDefCopy) {
1067  IsDefCopy = false;
1068  unsigned SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg();
1069  unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx();
1070  unsigned DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();
1071  unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx();
1073  return false;
1074 
1075  LiveInterval &SrcInt = LIS->getInterval(SrcReg);
1076  SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);
1077  VNInfo *ValNo = SrcInt.Query(CopyIdx).valueIn();
1078  assert(ValNo && "CopyMI input register not live");
1079  if (ValNo->isPHIDef() || ValNo->isUnused())
1080  return false;
1082  if (!DefMI)
1083  return false;
1084  if (DefMI->isCopyLike()) {
1085  IsDefCopy = true;
1086  return false;
1087  }
1088  if (!TII->isAsCheapAsAMove(*DefMI))
1089  return false;
1090  if (!TII->isTriviallyReMaterializable(*DefMI, AA))
1091  return false;
1092  if (!definesFullReg(*DefMI, SrcReg))
1093  return false;
1094  bool SawStore = false;
1095  if (!DefMI->isSafeToMove(AA, SawStore))
1096  return false;
1097  const MCInstrDesc &MCID = DefMI->getDesc();
1098  if (MCID.getNumDefs() != 1)
1099  return false;
1100  // Only support subregister destinations when the def is read-undef.
1101  MachineOperand &DstOperand = CopyMI->getOperand(0);
1102  unsigned CopyDstReg = DstOperand.getReg();
1103  if (DstOperand.getSubReg() && !DstOperand.isUndef())
1104  return false;
1105 
1106  // If both SrcIdx and DstIdx are set, correct rematerialization would widen
1107  // the register substantially (beyond both source and dest size). This is bad
1108  // for performance since it can cascade through a function, introducing many
1109  // extra spills and fills (e.g. ARM can easily end up copying QQQQPR registers
1110  // around after a few subreg copies).
1111  if (SrcIdx && DstIdx)
1112  return false;
1113 
1114  const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF);
1115  if (!DefMI->isImplicitDef()) {
1117  unsigned NewDstReg = DstReg;
1118 
1119  unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(),
1120  DefMI->getOperand(0).getSubReg());
1121  if (NewDstIdx)
1122  NewDstReg = TRI->getSubReg(DstReg, NewDstIdx);
1123 
1124  // Finally, make sure that the physical subregister that will be
1125  // constructed later is permitted for the instruction.
1126  if (!DefRC->contains(NewDstReg))
1127  return false;
1128  } else {
1129  // Theoretically, some stack frame reference could exist. Just make sure
1130  // it hasn't actually happened.
1132  "Only expect to deal with virtual or physical registers");
1133  }
1134  }
1135 
1136  DebugLoc DL = CopyMI->getDebugLoc();
1137  MachineBasicBlock *MBB = CopyMI->getParent();
1139  std::next(MachineBasicBlock::iterator(CopyMI));
1140  TII->reMaterialize(*MBB, MII, DstReg, SrcIdx, *DefMI, *TRI);
1141  MachineInstr &NewMI = *std::prev(MII);
1142  NewMI.setDebugLoc(DL);
1143 
1144  // In a situation like the following:
1145  // %0:subreg = instr ; DefMI, subreg = DstIdx
1146  // %1 = copy %0:subreg ; CopyMI, SrcIdx = 0
1147  // instead of widening %1 to the register class of %0 simply do:
1148  // %1 = instr
1149  const TargetRegisterClass *NewRC = CP.getNewRC();
1150  if (DstIdx != 0) {
1151  MachineOperand &DefMO = NewMI.getOperand(0);
1152  if (DefMO.getSubReg() == DstIdx) {
1153  assert(SrcIdx == 0 && CP.isFlipped()
1154  && "Shouldn't have SrcIdx+DstIdx at this point");
1155  const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
1156  const TargetRegisterClass *CommonRC =
1157  TRI->getCommonSubClass(DefRC, DstRC);
1158  if (CommonRC != nullptr) {
1159  NewRC = CommonRC;
1160  DstIdx = 0;
1161  DefMO.setSubReg(0);
1162  DefMO.setIsUndef(false); // Only subregs can have def+undef.
1163  }
1164  }
1165  }
1166 
1167  // CopyMI may have implicit operands, save them so that we can transfer them
1168  // over to the newly materialized instruction after CopyMI is removed.
1169  SmallVector<MachineOperand, 4> ImplicitOps;
1170  ImplicitOps.reserve(CopyMI->getNumOperands() -
1171  CopyMI->getDesc().getNumOperands());
1172  for (unsigned I = CopyMI->getDesc().getNumOperands(),
1173  E = CopyMI->getNumOperands();
1174  I != E; ++I) {
1175  MachineOperand &MO = CopyMI->getOperand(I);
1176  if (MO.isReg()) {
1177  assert(MO.isImplicit() && "No explicit operands after implict operands.");
1178  // Discard VReg implicit defs.
1180  ImplicitOps.push_back(MO);
1181  }
1182  }
1183 
1184  LIS->ReplaceMachineInstrInMaps(*CopyMI, NewMI);
1185  CopyMI->eraseFromParent();
1186  ErasedInstrs.insert(CopyMI);
1187 
1188  // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86).
1189  // We need to remember these so we can add intervals once we insert
1190  // NewMI into SlotIndexes.
1191  SmallVector<unsigned, 4> NewMIImplDefs;
1192  for (unsigned i = NewMI.getDesc().getNumOperands(),
1193  e = NewMI.getNumOperands();
1194  i != e; ++i) {
1195  MachineOperand &MO = NewMI.getOperand(i);
1196  if (MO.isReg() && MO.isDef()) {
1197  assert(MO.isImplicit() && MO.isDead() &&
1199  NewMIImplDefs.push_back(MO.getReg());
1200  }
1201  }
1202 
1204  unsigned NewIdx = NewMI.getOperand(0).getSubReg();
1205 
1206  if (DefRC != nullptr) {
1207  if (NewIdx)
1208  NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);
1209  else
1210  NewRC = TRI->getCommonSubClass(NewRC, DefRC);
1211  assert(NewRC && "subreg chosen for remat incompatible with instruction");
1212  }
1213  // Remap subranges to new lanemask and change register class.
1214  LiveInterval &DstInt = LIS->getInterval(DstReg);
1215  for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1216  SR.LaneMask = TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask);
1217  }
1218  MRI->setRegClass(DstReg, NewRC);
1219 
1220  // Update machine operands and add flags.
1221  updateRegDefsUses(DstReg, DstReg, DstIdx);
1222  NewMI.getOperand(0).setSubReg(NewIdx);
1223  // Add dead subregister definitions if we are defining the whole register
1224  // but only part of it is live.
1225  // This could happen if the rematerialization instruction is rematerializing
1226  // more than actually is used in the register.
1227  // An example would be:
1228  // %1 = LOAD CONSTANTS 5, 8 ; Loading both 5 and 8 in different subregs
1229  // ; Copying only part of the register here, but the rest is undef.
1230  // %2:sub_16bit<def, read-undef> = COPY %1:sub_16bit
1231  // ==>
1232  // ; Materialize all the constants but only using one
1233  // %2 = LOAD_CONSTANTS 5, 8
1234  //
1235  // at this point for the part that wasn't defined before we could have
1236  // subranges missing the definition.
1237  if (NewIdx == 0 && DstInt.hasSubRanges()) {
1238  SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);
1239  SlotIndex DefIndex =
1240  CurrIdx.getRegSlot(NewMI.getOperand(0).isEarlyClobber());
1241  LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(DstReg);
1242  VNInfo::Allocator& Alloc = LIS->getVNInfoAllocator();
1243  for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1244  if (!SR.liveAt(DefIndex))
1245  SR.createDeadDef(DefIndex, Alloc);
1246  MaxMask &= ~SR.LaneMask;
1247  }
1248  if (MaxMask.any()) {
1249  LiveInterval::SubRange *SR = DstInt.createSubRange(Alloc, MaxMask);
1250  SR->createDeadDef(DefIndex, Alloc);
1251  }
1252  }
1253 
1254  // Make sure that the subrange for resultant undef is removed
1255  // For example:
1256  // %1:sub1<def,read-undef> = LOAD CONSTANT 1
1257  // %2 = COPY %1
1258  // ==>
1259  // %2:sub1<def, read-undef> = LOAD CONSTANT 1
1260  // ; Correct but need to remove the subrange for %2:sub0
1261  // ; as it is now undef
1262  if (NewIdx != 0 && DstInt.hasSubRanges()) {
1263  // The affected subregister segments can be removed.
1264  SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);
1265  LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(NewIdx);
1266  bool UpdatedSubRanges = false;
1267  for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1268  if ((SR.LaneMask & DstMask).none()) {
1269  DEBUG(dbgs() << "Removing undefined SubRange "
1270  << PrintLaneMask(SR.LaneMask) << " : " << SR << "\n");
1271  // VNI is in ValNo - remove any segments in this SubRange that have this ValNo
1272  if (VNInfo *RmValNo = SR.getVNInfoAt(CurrIdx.getRegSlot())) {
1273  SR.removeValNo(RmValNo);
1274  UpdatedSubRanges = true;
1275  }
1276  }
1277  }
1278  if (UpdatedSubRanges)
1279  DstInt.removeEmptySubRanges();
1280  }
1281  } else if (NewMI.getOperand(0).getReg() != CopyDstReg) {
1282  // The New instruction may be defining a sub-register of what's actually
1283  // been asked for. If so it must implicitly define the whole thing.
1285  "Only expect virtual or physical registers in remat");
1286  NewMI.getOperand(0).setIsDead(true);
1288  CopyDstReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/));
1289  // Record small dead def live-ranges for all the subregisters
1290  // of the destination register.
1291  // Otherwise, variables that live through may miss some
1292  // interferences, thus creating invalid allocation.
1293  // E.g., i386 code:
1294  // %1 = somedef ; %1 GR8
1295  // %2 = remat ; %2 GR32
1296  // CL = COPY %2.sub_8bit
1297  // = somedef %1 ; %1 GR8
1298  // =>
1299  // %1 = somedef ; %1 GR8
1300  // dead ECX = remat ; implicit-def CL
1301  // = somedef %1 ; %1 GR8
1302  // %1 will see the inteferences with CL but not with CH since
1303  // no live-ranges would have been created for ECX.
1304  // Fix that!
1305  SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
1306  for (MCRegUnitIterator Units(NewMI.getOperand(0).getReg(), TRI);
1307  Units.isValid(); ++Units)
1308  if (LiveRange *LR = LIS->getCachedRegUnit(*Units))
1309  LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
1310  }
1311 
1312  if (NewMI.getOperand(0).getSubReg())
1313  NewMI.getOperand(0).setIsUndef();
1314 
1315  // Transfer over implicit operands to the rematerialized instruction.
1316  for (MachineOperand &MO : ImplicitOps)
1317  NewMI.addOperand(MO);
1318 
1319  SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
1320  for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) {
1321  unsigned Reg = NewMIImplDefs[i];
1322  for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
1323  if (LiveRange *LR = LIS->getCachedRegUnit(*Units))
1324  LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
1325  }
1326 
1327  DEBUG(dbgs() << "Remat: " << NewMI);
1328  ++NumReMats;
1329 
1330  // The source interval can become smaller because we removed a use.
1331  shrinkToUses(&SrcInt, &DeadDefs);
1332  if (!DeadDefs.empty()) {
1333  // If the virtual SrcReg is completely eliminated, update all DBG_VALUEs
1334  // to describe DstReg instead.
1335  for (MachineOperand &UseMO : MRI->use_operands(SrcReg)) {
1336  MachineInstr *UseMI = UseMO.getParent();
1337  if (UseMI->isDebugValue()) {
1338  UseMO.setReg(DstReg);
1339  // Move the debug value directly after the def of the rematerialized
1340  // value in DstReg.
1341  MBB->splice(std::next(NewMI.getIterator()), UseMI->getParent(), UseMI);
1342  DEBUG(dbgs() << "\t\tupdated: " << *UseMI);
1343  }
1344  }
1345  eliminateDeadDefs();
1346  }
1347 
1348  return true;
1349 }
1350 
1351 bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI) {
1352  // ProcessImpicitDefs may leave some copies of <undef> values, it only removes
1353  // local variables. When we have a copy like:
1354  //
1355  // %1 = COPY undef %2
1356  //
1357  // We delete the copy and remove the corresponding value number from %1.
1358  // Any uses of that value number are marked as <undef>.
1359 
1360  // Note that we do not query CoalescerPair here but redo isMoveInstr as the
1361  // CoalescerPair may have a new register class with adjusted subreg indices
1362  // at this point.
1363  unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1364  isMoveInstr(*TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx);
1365 
1366  SlotIndex Idx = LIS->getInstructionIndex(*CopyMI);
1367  const LiveInterval &SrcLI = LIS->getInterval(SrcReg);
1368  // CopyMI is undef iff SrcReg is not live before the instruction.
1369  if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) {
1370  LaneBitmask SrcMask = TRI->getSubRegIndexLaneMask(SrcSubIdx);
1371  for (const LiveInterval::SubRange &SR : SrcLI.subranges()) {
1372  if ((SR.LaneMask & SrcMask).none())
1373  continue;
1374  if (SR.liveAt(Idx))
1375  return false;
1376  }
1377  } else if (SrcLI.liveAt(Idx))
1378  return false;
1379 
1380  DEBUG(dbgs() << "\tEliminating copy of <undef> value\n");
1381 
1382  // Remove any DstReg segments starting at the instruction.
1383  LiveInterval &DstLI = LIS->getInterval(DstReg);
1384  SlotIndex RegIndex = Idx.getRegSlot();
1385  // Remove value or merge with previous one in case of a subregister def.
1386  if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {
1387  VNInfo *VNI = DstLI.getVNInfoAt(RegIndex);
1388  DstLI.MergeValueNumberInto(VNI, PrevVNI);
1389 
1390  // The affected subregister segments can be removed.
1391  LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx);
1392  for (LiveInterval::SubRange &SR : DstLI.subranges()) {
1393  if ((SR.LaneMask & DstMask).none())
1394  continue;
1395 
1396  VNInfo *SVNI = SR.getVNInfoAt(RegIndex);
1397  assert(SVNI != nullptr && SlotIndex::isSameInstr(SVNI->def, RegIndex));
1398  SR.removeValNo(SVNI);
1399  }
1400  DstLI.removeEmptySubRanges();
1401  } else
1402  LIS->removeVRegDefAt(DstLI, RegIndex);
1403 
1404  // Mark uses as undef.
1405  for (MachineOperand &MO : MRI->reg_nodbg_operands(DstReg)) {
1406  if (MO.isDef() /*|| MO.isUndef()*/)
1407  continue;
1408  const MachineInstr &MI = *MO.getParent();
1409  SlotIndex UseIdx = LIS->getInstructionIndex(MI);
1410  LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
1411  bool isLive;
1412  if (!UseMask.all() && DstLI.hasSubRanges()) {
1413  isLive = false;
1414  for (const LiveInterval::SubRange &SR : DstLI.subranges()) {
1415  if ((SR.LaneMask & UseMask).none())
1416  continue;
1417  if (SR.liveAt(UseIdx)) {
1418  isLive = true;
1419  break;
1420  }
1421  }
1422  } else
1423  isLive = DstLI.liveAt(UseIdx);
1424  if (isLive)
1425  continue;
1426  MO.setIsUndef(true);
1427  DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI);
1428  }
1429 
1430  // A def of a subregister may be a use of the other subregisters, so
1431  // deleting a def of a subregister may also remove uses. Since CopyMI
1432  // is still part of the function (but about to be erased), mark all
1433  // defs of DstReg in it as <undef>, so that shrinkToUses would
1434  // ignore them.
1435  for (MachineOperand &MO : CopyMI->operands())
1436  if (MO.isReg() && MO.isDef() && MO.getReg() == DstReg)
1437  MO.setIsUndef(true);
1438  LIS->shrinkToUses(&DstLI);
1439 
1440  return true;
1441 }
1442 
1443 void RegisterCoalescer::addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
1444  MachineOperand &MO, unsigned SubRegIdx) {
1445  LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubRegIdx);
1446  if (MO.isDef())
1447  Mask = ~Mask;
1448  bool IsUndef = true;
1449  for (const LiveInterval::SubRange &S : Int.subranges()) {
1450  if ((S.LaneMask & Mask).none())
1451  continue;
1452  if (S.liveAt(UseIdx)) {
1453  IsUndef = false;
1454  break;
1455  }
1456  }
1457  if (IsUndef) {
1458  MO.setIsUndef(true);
1459  // We found out some subregister use is actually reading an undefined
1460  // value. In some cases the whole vreg has become undefined at this
1461  // point so we have to potentially shrink the main range if the
1462  // use was ending a live segment there.
1463  LiveQueryResult Q = Int.Query(UseIdx);
1464  if (Q.valueOut() == nullptr)
1465  ShrinkMainRange = true;
1466  }
1467 }
1468 
1469 void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg,
1470  unsigned DstReg,
1471  unsigned SubIdx) {
1472  bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
1473  LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg);
1474 
1475  if (DstInt && DstInt->hasSubRanges() && DstReg != SrcReg) {
1476  for (MachineOperand &MO : MRI->reg_operands(DstReg)) {
1477  unsigned SubReg = MO.getSubReg();
1478  if (SubReg == 0 || MO.isUndef())
1479  continue;
1480  MachineInstr &MI = *MO.getParent();
1481  if (MI.isDebugValue())
1482  continue;
1483  SlotIndex UseIdx = LIS->getInstructionIndex(MI).getRegSlot(true);
1484  addUndefFlag(*DstInt, UseIdx, MO, SubReg);
1485  }
1486  }
1487 
1490  I = MRI->reg_instr_begin(SrcReg), E = MRI->reg_instr_end();
1491  I != E; ) {
1492  MachineInstr *UseMI = &*(I++);
1493 
1494  // Each instruction can only be rewritten once because sub-register
1495  // composition is not always idempotent. When SrcReg != DstReg, rewriting
1496  // the UseMI operands removes them from the SrcReg use-def chain, but when
1497  // SrcReg is DstReg we could encounter UseMI twice if it has multiple
1498  // operands mentioning the virtual register.
1499  if (SrcReg == DstReg && !Visited.insert(UseMI).second)
1500  continue;
1501 
1503  bool Reads, Writes;
1504  std::tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);
1505 
1506  // If SrcReg wasn't read, it may still be the case that DstReg is live-in
1507  // because SrcReg is a sub-register.
1508  if (DstInt && !Reads && SubIdx && !UseMI->isDebugValue())
1509  Reads = DstInt->liveAt(LIS->getInstructionIndex(*UseMI));
1510 
1511  // Replace SrcReg with DstReg in all UseMI operands.
1512  for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1513  MachineOperand &MO = UseMI->getOperand(Ops[i]);
1514 
1515  // Adjust <undef> flags in case of sub-register joins. We don't want to
1516  // turn a full def into a read-modify-write sub-register def and vice
1517  // versa.
1518  if (SubIdx && MO.isDef())
1519  MO.setIsUndef(!Reads);
1520 
1521  // A subreg use of a partially undef (super) register may be a complete
1522  // undef use now and then has to be marked that way.
1523  if (SubIdx != 0 && MO.isUse() && MRI->shouldTrackSubRegLiveness(DstReg)) {
1524  if (!DstInt->hasSubRanges()) {
1526  LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(DstInt->reg);
1527  DstInt->createSubRangeFrom(Allocator, Mask, *DstInt);
1528  }
1529  SlotIndex MIIdx = UseMI->isDebugValue()
1530  ? LIS->getSlotIndexes()->getIndexBefore(*UseMI)
1531  : LIS->getInstructionIndex(*UseMI);
1532  SlotIndex UseIdx = MIIdx.getRegSlot(true);
1533  addUndefFlag(*DstInt, UseIdx, MO, SubIdx);
1534  }
1535 
1536  if (DstIsPhys)
1537  MO.substPhysReg(DstReg, *TRI);
1538  else
1539  MO.substVirtReg(DstReg, SubIdx, *TRI);
1540  }
1541 
1542  DEBUG({
1543  dbgs() << "\t\tupdated: ";
1544  if (!UseMI->isDebugValue())
1545  dbgs() << LIS->getInstructionIndex(*UseMI) << "\t";
1546  dbgs() << *UseMI;
1547  });
1548  }
1549 }
1550 
1551 bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
1552  // Always join simple intervals that are defined by a single copy from a
1553  // reserved register. This doesn't increase register pressure, so it is
1554  // always beneficial.
1555  if (!MRI->isReserved(CP.getDstReg())) {
1556  DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
1557  return false;
1558  }
1559 
1560  LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg());
1561  if (JoinVInt.containsOneValue())
1562  return true;
1563 
1564  DEBUG(dbgs() << "\tCannot join complex intervals into reserved register.\n");
1565  return false;
1566 }
1567 
1568 bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
1569  Again = false;
1570  DEBUG(dbgs() << LIS->getInstructionIndex(*CopyMI) << '\t' << *CopyMI);
1571 
1572  CoalescerPair CP(*TRI);
1573  if (!CP.setRegisters(CopyMI)) {
1574  DEBUG(dbgs() << "\tNot coalescable.\n");
1575  return false;
1576  }
1577 
1578  if (CP.getNewRC()) {
1579  auto SrcRC = MRI->getRegClass(CP.getSrcReg());
1580  auto DstRC = MRI->getRegClass(CP.getDstReg());
1581  unsigned SrcIdx = CP.getSrcIdx();
1582  unsigned DstIdx = CP.getDstIdx();
1583  if (CP.isFlipped()) {
1584  std::swap(SrcIdx, DstIdx);
1585  std::swap(SrcRC, DstRC);
1586  }
1587  if (!TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,
1588  CP.getNewRC(), *LIS)) {
1589  DEBUG(dbgs() << "\tSubtarget bailed on coalescing.\n");
1590  return false;
1591  }
1592  }
1593 
1594  // Dead code elimination. This really should be handled by MachineDCE, but
1595  // sometimes dead copies slip through, and we can't generate invalid live
1596  // ranges.
1597  if (!CP.isPhys() && CopyMI->allDefsAreDead()) {
1598  DEBUG(dbgs() << "\tCopy is dead.\n");
1599  DeadDefs.push_back(CopyMI);
1600  eliminateDeadDefs();
1601  return true;
1602  }
1603 
1604  // Eliminate undefs.
1605  if (!CP.isPhys() && eliminateUndefCopy(CopyMI)) {
1606  deleteInstr(CopyMI);
1607  return false; // Not coalescable.
1608  }
1609 
1610  // Coalesced copies are normally removed immediately, but transformations
1611  // like removeCopyByCommutingDef() can inadvertently create identity copies.
1612  // When that happens, just join the values and remove the copy.
1613  if (CP.getSrcReg() == CP.getDstReg()) {
1614  LiveInterval &LI = LIS->getInterval(CP.getSrcReg());
1615  DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n');
1616  const SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);
1617  LiveQueryResult LRQ = LI.Query(CopyIdx);
1618  if (VNInfo *DefVNI = LRQ.valueDefined()) {
1619  VNInfo *ReadVNI = LRQ.valueIn();
1620  assert(ReadVNI && "No value before copy and no <undef> flag.");
1621  assert(ReadVNI != DefVNI && "Cannot read and define the same value.");
1622  LI.MergeValueNumberInto(DefVNI, ReadVNI);
1623 
1624  // Process subregister liveranges.
1625  for (LiveInterval::SubRange &S : LI.subranges()) {
1626  LiveQueryResult SLRQ = S.Query(CopyIdx);
1627  if (VNInfo *SDefVNI = SLRQ.valueDefined()) {
1628  VNInfo *SReadVNI = SLRQ.valueIn();
1629  S.MergeValueNumberInto(SDefVNI, SReadVNI);
1630  }
1631  }
1632  DEBUG(dbgs() << "\tMerged values: " << LI << '\n');
1633  }
1634  deleteInstr(CopyMI);
1635  return true;
1636  }
1637 
1638  // Enforce policies.
1639  if (CP.isPhys()) {
1640  DEBUG(dbgs() << "\tConsidering merging " << printReg(CP.getSrcReg(), TRI)
1641  << " with " << printReg(CP.getDstReg(), TRI, CP.getSrcIdx())
1642  << '\n');
1643  if (!canJoinPhys(CP)) {
1644  // Before giving up coalescing, if definition of source is defined by
1645  // trivial computation, try rematerializing it.
1646  bool IsDefCopy;
1647  if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
1648  return true;
1649  if (IsDefCopy)
1650  Again = true; // May be possible to coalesce later.
1651  return false;
1652  }
1653  } else {
1654  // When possible, let DstReg be the larger interval.
1655  if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() >
1656  LIS->getInterval(CP.getDstReg()).size())
1657  CP.flip();
1658 
1659  DEBUG({
1660  dbgs() << "\tConsidering merging to "
1661  << TRI->getRegClassName(CP.getNewRC()) << " with ";
1662  if (CP.getDstIdx() && CP.getSrcIdx())
1663  dbgs() << printReg(CP.getDstReg()) << " in "
1664  << TRI->getSubRegIndexName(CP.getDstIdx()) << " and "
1665  << printReg(CP.getSrcReg()) << " in "
1666  << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n';
1667  else
1668  dbgs() << printReg(CP.getSrcReg(), TRI) << " in "
1669  << printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n';
1670  });
1671  }
1672 
1673  ShrinkMask = LaneBitmask::getNone();
1674  ShrinkMainRange = false;
1675 
1676  // Okay, attempt to join these two intervals. On failure, this returns false.
1677  // Otherwise, if one of the intervals being joined is a physreg, this method
1678  // always canonicalizes DstInt to be it. The output "SrcInt" will not have
1679  // been modified, so we can use this information below to update aliases.
1680  if (!joinIntervals(CP)) {
1681  // Coalescing failed.
1682 
1683  // If definition of source is defined by trivial computation, try
1684  // rematerializing it.
1685  bool IsDefCopy;
1686  if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
1687  return true;
1688 
1689  // If we can eliminate the copy without merging the live segments, do so
1690  // now.
1691  if (!CP.isPartial() && !CP.isPhys()) {
1692  if (adjustCopiesBackFrom(CP, CopyMI) ||
1693  removeCopyByCommutingDef(CP, CopyMI)) {
1694  deleteInstr(CopyMI);
1695  DEBUG(dbgs() << "\tTrivial!\n");
1696  return true;
1697  }
1698  }
1699 
1700  // Try and see if we can partially eliminate the copy by moving the copy to
1701  // its predecessor.
1702  if (!CP.isPartial() && !CP.isPhys())
1703  if (removePartialRedundancy(CP, *CopyMI))
1704  return true;
1705 
1706  // Otherwise, we are unable to join the intervals.
1707  DEBUG(dbgs() << "\tInterference!\n");
1708  Again = true; // May be possible to coalesce later.
1709  return false;
1710  }
1711 
1712  // Coalescing to a virtual register that is of a sub-register class of the
1713  // other. Make sure the resulting register is set to the right register class.
1714  if (CP.isCrossClass()) {
1715  ++numCrossRCs;
1716  MRI->setRegClass(CP.getDstReg(), CP.getNewRC());
1717  }
1718 
1719  // Removing sub-register copies can ease the register class constraints.
1720  // Make sure we attempt to inflate the register class of DstReg.
1721  if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC()))
1722  InflateRegs.push_back(CP.getDstReg());
1723 
1724  // CopyMI has been erased by joinIntervals at this point. Remove it from
1725  // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back
1726  // to the work list. This keeps ErasedInstrs from growing needlessly.
1727  ErasedInstrs.erase(CopyMI);
1728 
1729  // Rewrite all SrcReg operands to DstReg.
1730  // Also update DstReg operands to include DstIdx if it is set.
1731  if (CP.getDstIdx())
1732  updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx());
1733  updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx());
1734 
1735  // Shrink subregister ranges if necessary.
1736  if (ShrinkMask.any()) {
1737  LiveInterval &LI = LIS->getInterval(CP.getDstReg());
1738  for (LiveInterval::SubRange &S : LI.subranges()) {
1739  if ((S.LaneMask & ShrinkMask).none())
1740  continue;
1741  DEBUG(dbgs() << "Shrink LaneUses (Lane " << PrintLaneMask(S.LaneMask)
1742  << ")\n");
1743  LIS->shrinkToUses(S, LI.reg);
1744  }
1745  LI.removeEmptySubRanges();
1746  }
1747  if (ShrinkMainRange) {
1748  LiveInterval &LI = LIS->getInterval(CP.getDstReg());
1749  shrinkToUses(&LI);
1750  }
1751 
1752  // SrcReg is guaranteed to be the register whose live interval that is
1753  // being merged.
1754  LIS->removeInterval(CP.getSrcReg());
1755 
1756  // Update regalloc hint.
1757  TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);
1758 
1759  DEBUG({
1760  dbgs() << "\tSuccess: " << printReg(CP.getSrcReg(), TRI, CP.getSrcIdx())
1761  << " -> " << printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
1762  dbgs() << "\tResult = ";
1763  if (CP.isPhys())
1764  dbgs() << printReg(CP.getDstReg(), TRI);
1765  else
1766  dbgs() << LIS->getInterval(CP.getDstReg());
1767  dbgs() << '\n';
1768  });
1769 
1770  ++numJoins;
1771  return true;
1772 }
1773 
1774 bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
1775  unsigned DstReg = CP.getDstReg();
1776  unsigned SrcReg = CP.getSrcReg();
1777  assert(CP.isPhys() && "Must be a physreg copy");
1778  assert(MRI->isReserved(DstReg) && "Not a reserved register");
1779  LiveInterval &RHS = LIS->getInterval(SrcReg);
1780  DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n');
1781 
1782  assert(RHS.containsOneValue() && "Invalid join with reserved register");
1783 
1784  // Optimization for reserved registers like ESP. We can only merge with a
1785  // reserved physreg if RHS has a single value that is a copy of DstReg.
1786  // The live range of the reserved register will look like a set of dead defs
1787  // - we don't properly track the live range of reserved registers.
1788 
1789  // Deny any overlapping intervals. This depends on all the reserved
1790  // register live ranges to look like dead defs.
1791  if (!MRI->isConstantPhysReg(DstReg)) {
1792  for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) {
1793  // Abort if not all the regunits are reserved.
1794  for (MCRegUnitRootIterator RI(*UI, TRI); RI.isValid(); ++RI) {
1795  if (!MRI->isReserved(*RI))
1796  return false;
1797  }
1798  if (RHS.overlaps(LIS->getRegUnit(*UI))) {
1799  DEBUG(dbgs() << "\t\tInterference: " << printRegUnit(*UI, TRI) << '\n');
1800  return false;
1801  }
1802  }
1803 
1804  // We must also check for overlaps with regmask clobbers.
1805  BitVector RegMaskUsable;
1806  if (LIS->checkRegMaskInterference(RHS, RegMaskUsable) &&
1807  !RegMaskUsable.test(DstReg)) {
1808  DEBUG(dbgs() << "\t\tRegMask interference\n");
1809  return false;
1810  }
1811  }
1812 
1813  // Skip any value computations, we are not adding new values to the
1814  // reserved register. Also skip merging the live ranges, the reserved
1815  // register live range doesn't need to be accurate as long as all the
1816  // defs are there.
1817 
1818  // Delete the identity copy.
1819  MachineInstr *CopyMI;
1820  if (CP.isFlipped()) {
1821  // Physreg is copied into vreg
1822  // %y = COPY %physreg_x
1823  // ... //< no other def of %x here
1824  // use %y
1825  // =>
1826  // ...
1827  // use %x
1828  CopyMI = MRI->getVRegDef(SrcReg);
1829  } else {
1830  // VReg is copied into physreg:
1831  // %y = def
1832  // ... //< no other def or use of %y here
1833  // %y = COPY %physreg_x
1834  // =>
1835  // %y = def
1836  // ...
1837  if (!MRI->hasOneNonDBGUse(SrcReg)) {
1838  DEBUG(dbgs() << "\t\tMultiple vreg uses!\n");
1839  return false;
1840  }
1841 
1842  if (!LIS->intervalIsInOneMBB(RHS)) {
1843  DEBUG(dbgs() << "\t\tComplex control flow!\n");
1844  return false;
1845  }
1846 
1847  MachineInstr &DestMI = *MRI->getVRegDef(SrcReg);
1848  CopyMI = &*MRI->use_instr_nodbg_begin(SrcReg);
1849  SlotIndex CopyRegIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
1850  SlotIndex DestRegIdx = LIS->getInstructionIndex(DestMI).getRegSlot();
1851 
1852  if (!MRI->isConstantPhysReg(DstReg)) {
1853  // We checked above that there are no interfering defs of the physical
1854  // register. However, for this case, where we intend to move up the def of
1855  // the physical register, we also need to check for interfering uses.
1856  SlotIndexes *Indexes = LIS->getSlotIndexes();
1857  for (SlotIndex SI = Indexes->getNextNonNullIndex(DestRegIdx);
1858  SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(SI)) {
1860  if (MI->readsRegister(DstReg, TRI)) {
1861  DEBUG(dbgs() << "\t\tInterference (read): " << *MI);
1862  return false;
1863  }
1864  }
1865  }
1866 
1867  // We're going to remove the copy which defines a physical reserved
1868  // register, so remove its valno, etc.
1869  DEBUG(dbgs() << "\t\tRemoving phys reg def of " << printReg(DstReg, TRI)
1870  << " at " << CopyRegIdx << "\n");
1871 
1872  LIS->removePhysRegDefAt(DstReg, CopyRegIdx);
1873  // Create a new dead def at the new def location.
1874  for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) {
1875  LiveRange &LR = LIS->getRegUnit(*UI);
1876  LR.createDeadDef(DestRegIdx, LIS->getVNInfoAllocator());
1877  }
1878  }
1879 
1880  deleteInstr(CopyMI);
1881 
1882  // We don't track kills for reserved registers.
1883  MRI->clearKillFlags(CP.getSrcReg());
1884 
1885  return true;
1886 }
1887 
1888 //===----------------------------------------------------------------------===//
1889 // Interference checking and interval joining
1890 //===----------------------------------------------------------------------===//
1891 //
1892 // In the easiest case, the two live ranges being joined are disjoint, and
1893 // there is no interference to consider. It is quite common, though, to have
1894 // overlapping live ranges, and we need to check if the interference can be
1895 // resolved.
1896 //
1897 // The live range of a single SSA value forms a sub-tree of the dominator tree.
1898 // This means that two SSA values overlap if and only if the def of one value
1899 // is contained in the live range of the other value. As a special case, the
1900 // overlapping values can be defined at the same index.
1901 //
1902 // The interference from an overlapping def can be resolved in these cases:
1903 //
1904 // 1. Coalescable copies. The value is defined by a copy that would become an
1905 // identity copy after joining SrcReg and DstReg. The copy instruction will
1906 // be removed, and the value will be merged with the source value.
1907 //
1908 // There can be several copies back and forth, causing many values to be
1909 // merged into one. We compute a list of ultimate values in the joined live
1910 // range as well as a mappings from the old value numbers.
1911 //
1912 // 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI
1913 // predecessors have a live out value. It doesn't cause real interference,
1914 // and can be merged into the value it overlaps. Like a coalescable copy, it
1915 // can be erased after joining.
1916 //
1917 // 3. Copy of external value. The overlapping def may be a copy of a value that
1918 // is already in the other register. This is like a coalescable copy, but
1919 // the live range of the source register must be trimmed after erasing the
1920 // copy instruction:
1921 //
1922 // %src = COPY %ext
1923 // %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext.
1924 //
1925 // 4. Clobbering undefined lanes. Vector registers are sometimes built by
1926 // defining one lane at a time:
1927 //
1928 // %dst:ssub0<def,read-undef> = FOO
1929 // %src = BAR
1930 // %dst:ssub1 = COPY %src
1931 //
1932 // The live range of %src overlaps the %dst value defined by FOO, but
1933 // merging %src into %dst:ssub1 is only going to clobber the ssub1 lane
1934 // which was undef anyway.
1935 //
1936 // The value mapping is more complicated in this case. The final live range
1937 // will have different value numbers for both FOO and BAR, but there is no
1938 // simple mapping from old to new values. It may even be necessary to add
1939 // new PHI values.
1940 //
1941 // 5. Clobbering dead lanes. A def may clobber a lane of a vector register that
1942 // is live, but never read. This can happen because we don't compute
1943 // individual live ranges per lane.
1944 //
1945 // %dst = FOO
1946 // %src = BAR
1947 // %dst:ssub1 = COPY %src
1948 //
1949 // This kind of interference is only resolved locally. If the clobbered
1950 // lane value escapes the block, the join is aborted.
1951 
1952 namespace {
1953 
1954 /// Track information about values in a single virtual register about to be
1955 /// joined. Objects of this class are always created in pairs - one for each
1956 /// side of the CoalescerPair (or one for each lane of a side of the coalescer
1957 /// pair)
1958 class JoinVals {
1959  /// Live range we work on.
1960  LiveRange &LR;
1961 
1962  /// (Main) register we work on.
1963  const unsigned Reg;
1964 
1965  /// Reg (and therefore the values in this liverange) will end up as
1966  /// subregister SubIdx in the coalesced register. Either CP.DstIdx or
1967  /// CP.SrcIdx.
1968  const unsigned SubIdx;
1969 
1970  /// The LaneMask that this liverange will occupy the coalesced register. May
1971  /// be smaller than the lanemask produced by SubIdx when merging subranges.
1972  const LaneBitmask LaneMask;
1973 
1974  /// This is true when joining sub register ranges, false when joining main
1975  /// ranges.
1976  const bool SubRangeJoin;
1977 
1978  /// Whether the current LiveInterval tracks subregister liveness.
1979  const bool TrackSubRegLiveness;
1980 
1981  /// Values that will be present in the final live range.
1982  SmallVectorImpl<VNInfo*> &NewVNInfo;
1983 
1984  const CoalescerPair &CP;
1985  LiveIntervals *LIS;
1986  SlotIndexes *Indexes;
1987  const TargetRegisterInfo *TRI;
1988 
1989  /// Value number assignments. Maps value numbers in LI to entries in
1990  /// NewVNInfo. This is suitable for passing to LiveInterval::join().
1991  SmallVector<int, 8> Assignments;
1992 
1993  /// Conflict resolution for overlapping values.
1994  enum ConflictResolution {
1995  /// No overlap, simply keep this value.
1996  CR_Keep,
1997 
1998  /// Merge this value into OtherVNI and erase the defining instruction.
1999  /// Used for IMPLICIT_DEF, coalescable copies, and copies from external
2000  /// values.
2001  CR_Erase,
2002 
2003  /// Merge this value into OtherVNI but keep the defining instruction.
2004  /// This is for the special case where OtherVNI is defined by the same
2005  /// instruction.
2006  CR_Merge,
2007 
2008  /// Keep this value, and have it replace OtherVNI where possible. This
2009  /// complicates value mapping since OtherVNI maps to two different values
2010  /// before and after this def.
2011  /// Used when clobbering undefined or dead lanes.
2012  CR_Replace,
2013 
2014  /// Unresolved conflict. Visit later when all values have been mapped.
2015  CR_Unresolved,
2016 
2017  /// Unresolvable conflict. Abort the join.
2018  CR_Impossible
2019  };
2020 
2021  /// Per-value info for LI. The lane bit masks are all relative to the final
2022  /// joined register, so they can be compared directly between SrcReg and
2023  /// DstReg.
2024  struct Val {
2025  ConflictResolution Resolution = CR_Keep;
2026 
2027  /// Lanes written by this def, 0 for unanalyzed values.
2028  LaneBitmask WriteLanes;
2029 
2030  /// Lanes with defined values in this register. Other lanes are undef and
2031  /// safe to clobber.
2032  LaneBitmask ValidLanes;
2033 
2034  /// Value in LI being redefined by this def.
2035  VNInfo *RedefVNI = nullptr;
2036 
2037  /// Value in the other live range that overlaps this def, if any.
2038  VNInfo *OtherVNI = nullptr;
2039 
2040  /// Is this value an IMPLICIT_DEF that can be erased?
2041  ///
2042  /// IMPLICIT_DEF values should only exist at the end of a basic block that
2043  /// is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be
2044  /// safely erased if they are overlapping a live value in the other live
2045  /// interval.
2046  ///
2047  /// Weird control flow graphs and incomplete PHI handling in
2048  /// ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with
2049  /// longer live ranges. Such IMPLICIT_DEF values should be treated like
2050  /// normal values.
2051  bool ErasableImplicitDef = false;
2052 
2053  /// True when the live range of this value will be pruned because of an
2054  /// overlapping CR_Replace value in the other live range.
2055  bool Pruned = false;
2056 
2057  /// True once Pruned above has been computed.
2058  bool PrunedComputed = false;
2059 
2060  Val() = default;
2061 
2062  bool isAnalyzed() const { return WriteLanes.any(); }
2063  };
2064 
2065  /// One entry per value number in LI.
2066  SmallVector<Val, 8> Vals;
2067 
2068  /// Compute the bitmask of lanes actually written by DefMI.
2069  /// Set Redef if there are any partial register definitions that depend on the
2070  /// previous value of the register.
2071  LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;
2072 
2073  /// Find the ultimate value that VNI was copied from.
2074  std::pair<const VNInfo*,unsigned> followCopyChain(const VNInfo *VNI) const;
2075 
2076  bool valuesIdentical(VNInfo *Val0, VNInfo *Val1, const JoinVals &Other) const;
2077 
2078  /// Analyze ValNo in this live range, and set all fields of Vals[ValNo].
2079  /// Return a conflict resolution when possible, but leave the hard cases as
2080  /// CR_Unresolved.
2081  /// Recursively calls computeAssignment() on this and Other, guaranteeing that
2082  /// both OtherVNI and RedefVNI have been analyzed and mapped before returning.
2083  /// The recursion always goes upwards in the dominator tree, making loops
2084  /// impossible.
2085  ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other);
2086 
2087  /// Compute the value assignment for ValNo in RI.
2088  /// This may be called recursively by analyzeValue(), but never for a ValNo on
2089  /// the stack.
2090  void computeAssignment(unsigned ValNo, JoinVals &Other);
2091 
2092  /// Assuming ValNo is going to clobber some valid lanes in Other.LR, compute
2093  /// the extent of the tainted lanes in the block.
2094  ///
2095  /// Multiple values in Other.LR can be affected since partial redefinitions
2096  /// can preserve previously tainted lanes.
2097  ///
2098  /// 1 %dst = VLOAD <-- Define all lanes in %dst
2099  /// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0
2100  /// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0
2101  /// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read
2102  ///
2103  /// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes)
2104  /// entry to TaintedVals.
2105  ///
2106  /// Returns false if the tainted lanes extend beyond the basic block.
2107  bool
2108  taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
2109  SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent);
2110 
2111  /// Return true if MI uses any of the given Lanes from Reg.
2112  /// This does not include partial redefinitions of Reg.
2113  bool usesLanes(const MachineInstr &MI, unsigned, unsigned, LaneBitmask) const;
2114 
2115  /// Determine if ValNo is a copy of a value number in LR or Other.LR that will
2116  /// be pruned:
2117  ///
2118  /// %dst = COPY %src
2119  /// %src = COPY %dst <-- This value to be pruned.
2120  /// %dst = COPY %src <-- This value is a copy of a pruned value.
2121  bool isPrunedValue(unsigned ValNo, JoinVals &Other);
2122 
2123 public:
2124  JoinVals(LiveRange &LR, unsigned Reg, unsigned SubIdx, LaneBitmask LaneMask,
2125  SmallVectorImpl<VNInfo*> &newVNInfo, const CoalescerPair &cp,
2126  LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin,
2127  bool TrackSubRegLiveness)
2128  : LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask),
2129  SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),
2130  NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
2131  TRI(TRI), Assignments(LR.getNumValNums(), -1), Vals(LR.getNumValNums()) {}
2132 
2133  /// Analyze defs in LR and compute a value mapping in NewVNInfo.
2134  /// Returns false if any conflicts were impossible to resolve.
2135  bool mapValues(JoinVals &Other);
2136 
2137  /// Try to resolve conflicts that require all values to be mapped.
2138  /// Returns false if any conflicts were impossible to resolve.
2139  bool resolveConflicts(JoinVals &Other);
2140 
2141  /// Prune the live range of values in Other.LR where they would conflict with
2142  /// CR_Replace values in LR. Collect end points for restoring the live range
2143  /// after joining.
2144  void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints,
2145  bool changeInstrs);
2146 
2147  /// Removes subranges starting at copies that get removed. This sometimes
2148  /// happens when undefined subranges are copied around. These ranges contain
2149  /// no useful information and can be removed.
2150  void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);
2151 
2152  /// Pruning values in subranges can lead to removing segments in these
2153  /// subranges started by IMPLICIT_DEFs. The corresponding segments in
2154  /// the main range also need to be removed. This function will mark
2155  /// the corresponding values in the main range as pruned, so that
2156  /// eraseInstrs can do the final cleanup.
2157  /// The parameter @p LI must be the interval whose main range is the
2158  /// live range LR.
2159  void pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange);
2160 
2161  /// Erase any machine instructions that have been coalesced away.
2162  /// Add erased instructions to ErasedInstrs.
2163  /// Add foreign virtual registers to ShrinkRegs if their live range ended at
2164  /// the erased instrs.
2165  void eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
2166  SmallVectorImpl<unsigned> &ShrinkRegs,
2167  LiveInterval *LI = nullptr);
2168 
2169  /// Remove liverange defs at places where implicit defs will be removed.
2170  void removeImplicitDefs();
2171 
2172  /// Get the value assignments suitable for passing to LiveInterval::join.
2173  const int *getAssignments() const { return Assignments.data(); }
2174 };
2175 
2176 } // end anonymous namespace
2177 
2178 LaneBitmask JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef)
2179  const {
2180  LaneBitmask L;
2181  for (const MachineOperand &MO : DefMI->operands()) {
2182  if (!MO.isReg() || MO.getReg() != Reg || !MO.isDef())
2183  continue;
2184  L |= TRI->getSubRegIndexLaneMask(
2185  TRI->composeSubRegIndices(SubIdx, MO.getSubReg()));
2186  if (MO.readsReg())
2187  Redef = true;
2188  }
2189  return L;
2190 }
2191 
2192 std::pair<const VNInfo*, unsigned> JoinVals::followCopyChain(
2193  const VNInfo *VNI) const {
2194  unsigned Reg = this->Reg;
2195 
2196  while (!VNI->isPHIDef()) {
2197  SlotIndex Def = VNI->def;
2198  MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
2199  assert(MI && "No defining instruction");
2200  if (!MI->isFullCopy())
2201  return std::make_pair(VNI, Reg);
2202  unsigned SrcReg = MI->getOperand(1).getReg();
2204  return std::make_pair(VNI, Reg);
2205 
2206  const LiveInterval &LI = LIS->getInterval(SrcReg);
2207  const VNInfo *ValueIn;
2208  // No subrange involved.
2209  if (!SubRangeJoin || !LI.hasSubRanges()) {
2210  LiveQueryResult LRQ = LI.Query(Def);
2211  ValueIn = LRQ.valueIn();
2212  } else {
2213  // Query subranges. Pick the first matching one.
2214  ValueIn = nullptr;
2215  for (const LiveInterval::SubRange &S : LI.subranges()) {
2216  // Transform lanemask to a mask in the joined live interval.
2217  LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
2218  if ((SMask & LaneMask).none())
2219  continue;
2220  LiveQueryResult LRQ = S.Query(Def);
2221  ValueIn = LRQ.valueIn();
2222  break;
2223  }
2224  }
2225  if (ValueIn == nullptr)
2226  break;
2227  VNI = ValueIn;
2228  Reg = SrcReg;
2229  }
2230  return std::make_pair(VNI, Reg);
2231 }
2232 
2233 bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1,
2234  const JoinVals &Other) const {
2235  const VNInfo *Orig0;
2236  unsigned Reg0;
2237  std::tie(Orig0, Reg0) = followCopyChain(Value0);
2238  if (Orig0 == Value1)
2239  return true;
2240 
2241  const VNInfo *Orig1;
2242  unsigned Reg1;
2243  std::tie(Orig1, Reg1) = Other.followCopyChain(Value1);
2244 
2245  // The values are equal if they are defined at the same place and use the
2246  // same register. Note that we cannot compare VNInfos directly as some of
2247  // them might be from a copy created in mergeSubRangeInto() while the other
2248  // is from the original LiveInterval.
2249  return Orig0->def == Orig1->def && Reg0 == Reg1;
2250 }
2251 
2252 JoinVals::ConflictResolution
2253 JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) {
2254  Val &V = Vals[ValNo];
2255  assert(!V.isAnalyzed() && "Value has already been analyzed!");
2256  VNInfo *VNI = LR.getValNumInfo(ValNo);
2257  if (VNI->isUnused()) {
2258  V.WriteLanes = LaneBitmask::getAll();
2259  return CR_Keep;
2260  }
2261 
2262  // Get the instruction defining this value, compute the lanes written.
2263  const MachineInstr *DefMI = nullptr;
2264  if (VNI->isPHIDef()) {
2265  // Conservatively assume that all lanes in a PHI are valid.
2266  LaneBitmask Lanes = SubRangeJoin ? LaneBitmask::getLane(0)
2267  : TRI->getSubRegIndexLaneMask(SubIdx);
2268  V.ValidLanes = V.WriteLanes = Lanes;
2269  } else {
2270  DefMI = Indexes->getInstructionFromIndex(VNI->def);
2271  assert(DefMI != nullptr);
2272  if (SubRangeJoin) {
2273  // We don't care about the lanes when joining subregister ranges.
2274  V.WriteLanes = V.ValidLanes = LaneBitmask::getLane(0);
2275  if (DefMI->isImplicitDef()) {
2276  V.ValidLanes = LaneBitmask::getNone();
2277  V.ErasableImplicitDef = true;
2278  }
2279  } else {
2280  bool Redef = false;
2281  V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef);
2282 
2283  // If this is a read-modify-write instruction, there may be more valid
2284  // lanes than the ones written by this instruction.
2285  // This only covers partial redef operands. DefMI may have normal use
2286  // operands reading the register. They don't contribute valid lanes.
2287  //
2288  // This adds ssub1 to the set of valid lanes in %src:
2289  //
2290  // %src:ssub1 = FOO
2291  //
2292  // This leaves only ssub1 valid, making any other lanes undef:
2293  //
2294  // %src:ssub1<def,read-undef> = FOO %src:ssub2
2295  //
2296  // The <read-undef> flag on the def operand means that old lane values are
2297  // not important.
2298  if (Redef) {
2299  V.RedefVNI = LR.Query(VNI->def).valueIn();
2300  assert((TrackSubRegLiveness || V.RedefVNI) &&
2301  "Instruction is reading nonexistent value");
2302  if (V.RedefVNI != nullptr) {
2303  computeAssignment(V.RedefVNI->id, Other);
2304  V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;
2305  }
2306  }
2307 
2308  // An IMPLICIT_DEF writes undef values.
2309  if (DefMI->isImplicitDef()) {
2310  // We normally expect IMPLICIT_DEF values to be live only until the end
2311  // of their block. If the value is really live longer and gets pruned in
2312  // another block, this flag is cleared again.
2313  V.ErasableImplicitDef = true;
2314  V.ValidLanes &= ~V.WriteLanes;
2315  }
2316  }
2317  }
2318 
2319  // Find the value in Other that overlaps VNI->def, if any.
2320  LiveQueryResult OtherLRQ = Other.LR.Query(VNI->def);
2321 
2322  // It is possible that both values are defined by the same instruction, or
2323  // the values are PHIs defined in the same block. When that happens, the two
2324  // values should be merged into one, but not into any preceding value.
2325  // The first value defined or visited gets CR_Keep, the other gets CR_Merge.
2326  if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) {
2327  assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ");
2328 
2329  // One value stays, the other is merged. Keep the earlier one, or the first
2330  // one we see.
2331  if (OtherVNI->def < VNI->def)
2332  Other.computeAssignment(OtherVNI->id, *this);
2333  else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) {
2334  // This is an early-clobber def overlapping a live-in value in the other
2335  // register. Not mergeable.
2336  V.OtherVNI = OtherLRQ.valueIn();
2337  return CR_Impossible;
2338  }
2339  V.OtherVNI = OtherVNI;
2340  Val &OtherV = Other.Vals[OtherVNI->id];
2341  // Keep this value, check for conflicts when analyzing OtherVNI.
2342  if (!OtherV.isAnalyzed())
2343  return CR_Keep;
2344  // Both sides have been analyzed now.
2345  // Allow overlapping PHI values. Any real interference would show up in a
2346  // predecessor, the PHI itself can't introduce any conflicts.
2347  if (VNI->isPHIDef())
2348  return CR_Merge;
2349  if ((V.ValidLanes & OtherV.ValidLanes).any())
2350  // Overlapping lanes can't be resolved.
2351  return CR_Impossible;
2352  else
2353  return CR_Merge;
2354  }
2355 
2356  // No simultaneous def. Is Other live at the def?
2357  V.OtherVNI = OtherLRQ.valueIn();
2358  if (!V.OtherVNI)
2359  // No overlap, no conflict.
2360  return CR_Keep;
2361 
2362  assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ");
2363 
2364  // We have overlapping values, or possibly a kill of Other.
2365  // Recursively compute assignments up the dominator tree.
2366  Other.computeAssignment(V.OtherVNI->id, *this);
2367  Val &OtherV = Other.Vals[V.OtherVNI->id];
2368 
2369  // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block.
2370  // This shouldn't normally happen, but ProcessImplicitDefs can leave such
2371  // IMPLICIT_DEF instructions behind, and there is nothing wrong with it
2372  // technically.
2373  //
2374  // When it happens, treat that IMPLICIT_DEF as a normal value, and don't try
2375  // to erase the IMPLICIT_DEF instruction.
2376  if (OtherV.ErasableImplicitDef && DefMI &&
2377  DefMI->getParent() != Indexes->getMBBFromIndex(V.OtherVNI->def)) {
2378  DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def
2379  << " extends into " << printMBBReference(*DefMI->getParent())
2380  << ", keeping it.\n");
2381  OtherV.ErasableImplicitDef = false;
2382  }
2383 
2384  // Allow overlapping PHI values. Any real interference would show up in a
2385  // predecessor, the PHI itself can't introduce any conflicts.
2386  if (VNI->isPHIDef())
2387  return CR_Replace;
2388 
2389  // Check for simple erasable conflicts.
2390  if (DefMI->isImplicitDef()) {
2391  // We need the def for the subregister if there is nothing else live at the
2392  // subrange at this point.
2393  if (TrackSubRegLiveness
2394  && (V.WriteLanes & (OtherV.ValidLanes | OtherV.WriteLanes)).none())
2395  return CR_Replace;
2396  return CR_Erase;
2397  }
2398 
2399  // Include the non-conflict where DefMI is a coalescable copy that kills
2400  // OtherVNI. We still want the copy erased and value numbers merged.
2401  if (CP.isCoalescable(DefMI)) {
2402  // Some of the lanes copied from OtherVNI may be undef, making them undef
2403  // here too.
2404  V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;
2405  return CR_Erase;
2406  }
2407 
2408  // This may not be a real conflict if DefMI simply kills Other and defines
2409  // VNI.
2410  if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def)
2411  return CR_Keep;
2412 
2413  // Handle the case where VNI and OtherVNI can be proven to be identical:
2414  //
2415  // %other = COPY %ext
2416  // %this = COPY %ext <-- Erase this copy
2417  //
2418  if (DefMI->isFullCopy() && !CP.isPartial()
2419  && valuesIdentical(VNI, V.OtherVNI, Other))
2420  return CR_Erase;
2421 
2422  // If the lanes written by this instruction were all undef in OtherVNI, it is
2423  // still safe to join the live ranges. This can't be done with a simple value
2424  // mapping, though - OtherVNI will map to multiple values:
2425  //
2426  // 1 %dst:ssub0 = FOO <-- OtherVNI
2427  // 2 %src = BAR <-- VNI
2428  // 3 %dst:ssub1 = COPY killed %src <-- Eliminate this copy.
2429  // 4 BAZ killed %dst
2430  // 5 QUUX killed %src
2431  //
2432  // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace
2433  // handles this complex value mapping.
2434  if ((V.WriteLanes & OtherV.ValidLanes).none())
2435  return CR_Replace;
2436 
2437  // If the other live range is killed by DefMI and the live ranges are still
2438  // overlapping, it must be because we're looking at an early clobber def:
2439  //
2440  // %dst<def,early-clobber> = ASM killed %src
2441  //
2442  // In this case, it is illegal to merge the two live ranges since the early
2443  // clobber def would clobber %src before it was read.
2444  if (OtherLRQ.isKill()) {
2445  // This case where the def doesn't overlap the kill is handled above.
2446  assert(VNI->def.isEarlyClobber() &&
2447  "Only early clobber defs can overlap a kill");
2448  return CR_Impossible;
2449  }
2450 
2451  // VNI is clobbering live lanes in OtherVNI, but there is still the
2452  // possibility that no instructions actually read the clobbered lanes.
2453  // If we're clobbering all the lanes in OtherVNI, at least one must be read.
2454  // Otherwise Other.RI wouldn't be live here.
2455  if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes).none())
2456  return CR_Impossible;
2457 
2458  // We need to verify that no instructions are reading the clobbered lanes. To
2459  // save compile time, we'll only check that locally. Don't allow the tainted
2460  // value to escape the basic block.
2461  MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
2462  if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB))
2463  return CR_Impossible;
2464 
2465  // There are still some things that could go wrong besides clobbered lanes
2466  // being read, for example OtherVNI may be only partially redefined in MBB,
2467  // and some clobbered lanes could escape the block. Save this analysis for
2468  // resolveConflicts() when all values have been mapped. We need to know
2469  // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute
2470  // that now - the recursive analyzeValue() calls must go upwards in the
2471  // dominator tree.
2472  return CR_Unresolved;
2473 }
2474 
2475 void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) {
2476  Val &V = Vals[ValNo];
2477  if (V.isAnalyzed()) {
2478  // Recursion should always move up the dominator tree, so ValNo is not
2479  // supposed to reappear before it has been assigned.
2480  assert(Assignments[ValNo] != -1 && "Bad recursion?");
2481  return;
2482  }
2483  switch ((V.Resolution = analyzeValue(ValNo, Other))) {
2484  case CR_Erase:
2485  case CR_Merge:
2486  // Merge this ValNo into OtherVNI.
2487  assert(V.OtherVNI && "OtherVNI not assigned, can't merge.");
2488  assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion");
2489  Assignments[ValNo] = Other.Assignments[V.OtherVNI->id];
2490  DEBUG(dbgs() << "\t\tmerge " << printReg(Reg) << ':' << ValNo << '@'
2491  << LR.getValNumInfo(ValNo)->def << " into "
2492  << printReg(Other.Reg) << ':' << V.OtherVNI->id << '@'
2493  << V.OtherVNI->def << " --> @"
2494  << NewVNInfo[Assignments[ValNo]]->def << '\n');
2495  break;
2496  case CR_Replace:
2497  case CR_Unresolved: {
2498  // The other value is going to be pruned if this join is successful.
2499  assert(V.OtherVNI && "OtherVNI not assigned, can't prune");
2500  Val &OtherV = Other.Vals[V.OtherVNI->id];
2501  // We cannot erase an IMPLICIT_DEF if we don't have valid values for all
2502  // its lanes.
2503  if ((OtherV.WriteLanes & ~V.ValidLanes).any() && TrackSubRegLiveness)
2504  OtherV.ErasableImplicitDef = false;
2505  OtherV.Pruned = true;
2507  }
2508  default:
2509  // This value number needs to go in the final joined live range.
2510  Assignments[ValNo] = NewVNInfo.size();
2511  NewVNInfo.push_back(LR.getValNumInfo(ValNo));
2512  break;
2513  }
2514 }
2515 
2516 bool JoinVals::mapValues(JoinVals &Other) {
2517  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2518  computeAssignment(i, Other);
2519  if (Vals[i].Resolution == CR_Impossible) {
2520  DEBUG(dbgs() << "\t\tinterference at " << printReg(Reg) << ':' << i
2521  << '@' << LR.getValNumInfo(i)->def << '\n');
2522  return false;
2523  }
2524  }
2525  return true;
2526 }
2527 
2528 bool JoinVals::
2529 taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
2530  SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent) {
2531  VNInfo *VNI = LR.getValNumInfo(ValNo);
2532  MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
2533  SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB);
2534 
2535  // Scan Other.LR from VNI.def to MBBEnd.
2536  LiveInterval::iterator OtherI = Other.LR.find(VNI->def);
2537  assert(OtherI != Other.LR.end() && "No conflict?");
2538  do {
2539  // OtherI is pointing to a tainted value. Abort the join if the tainted
2540  // lanes escape the block.
2541  SlotIndex End = OtherI->end;
2542  if (End >= MBBEnd) {
2543  DEBUG(dbgs() << "\t\ttaints global " << printReg(Other.Reg) << ':'
2544  << OtherI->valno->id << '@' << OtherI->start << '\n');
2545  return false;
2546  }
2547  DEBUG(dbgs() << "\t\ttaints local " << printReg(Other.Reg) << ':'
2548  << OtherI->valno->id << '@' << OtherI->start
2549  << " to " << End << '\n');
2550  // A dead def is not a problem.
2551  if (End.isDead())
2552  break;
2553  TaintExtent.push_back(std::make_pair(End, TaintedLanes));
2554 
2555  // Check for another def in the MBB.
2556  if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd)
2557  break;
2558 
2559  // Lanes written by the new def are no longer tainted.
2560  const Val &OV = Other.Vals[OtherI->valno->id];
2561  TaintedLanes &= ~OV.WriteLanes;
2562  if (!OV.RedefVNI)
2563  break;
2564  } while (TaintedLanes.any());
2565  return true;
2566 }
2567 
2568 bool JoinVals::usesLanes(const MachineInstr &MI, unsigned Reg, unsigned SubIdx,
2569  LaneBitmask Lanes) const {
2570  if (MI.isDebugValue())
2571  return false;
2572  for (const MachineOperand &MO : MI.operands()) {
2573  if (!MO.isReg() || MO.isDef() || MO.getReg() != Reg)
2574  continue;
2575  if (!MO.readsReg())
2576  continue;
2577  unsigned S = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());
2578  if ((Lanes & TRI->getSubRegIndexLaneMask(S)).any())
2579  return true;
2580  }
2581  return false;
2582 }
2583 
2584 bool JoinVals::resolveConflicts(JoinVals &Other) {
2585  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2586  Val &V = Vals[i];
2587  assert(V.Resolution != CR_Impossible && "Unresolvable conflict");
2588  if (V.Resolution != CR_Unresolved)
2589  continue;
2590  DEBUG(dbgs() << "\t\tconflict at " << printReg(Reg) << ':' << i
2591  << '@' << LR.getValNumInfo(i)->def << '\n');
2592  if (SubRangeJoin)
2593  return false;
2594 
2595  ++NumLaneConflicts;
2596  assert(V.OtherVNI && "Inconsistent conflict resolution.");
2597  VNInfo *VNI = LR.getValNumInfo(i);
2598  const Val &OtherV = Other.Vals[V.OtherVNI->id];
2599 
2600  // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the
2601  // join, those lanes will be tainted with a wrong value. Get the extent of
2602  // the tainted lanes.
2603  LaneBitmask TaintedLanes = V.WriteLanes & OtherV.ValidLanes;
2605  if (!taintExtent(i, TaintedLanes, Other, TaintExtent))
2606  // Tainted lanes would extend beyond the basic block.
2607  return false;
2608 
2609  assert(!TaintExtent.empty() && "There should be at least one conflict.");
2610 
2611  // Now look at the instructions from VNI->def to TaintExtent (inclusive).
2612  MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
2613  MachineBasicBlock::iterator MI = MBB->begin();
2614  if (!VNI->isPHIDef()) {
2615  MI = Indexes->getInstructionFromIndex(VNI->def);
2616  // No need to check the instruction defining VNI for reads.
2617  ++MI;
2618  }
2619  assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) &&
2620  "Interference ends on VNI->def. Should have been handled earlier");
2621  MachineInstr *LastMI =
2622  Indexes->getInstructionFromIndex(TaintExtent.front().first);
2623  assert(LastMI && "Range must end at a proper instruction");
2624  unsigned TaintNum = 0;
2625  while (true) {
2626  assert(MI != MBB->end() && "Bad LastMI");
2627  if (usesLanes(*MI, Other.Reg, Other.SubIdx, TaintedLanes)) {
2628  DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI);
2629  return false;
2630  }
2631  // LastMI is the last instruction to use the current value.
2632  if (&*MI == LastMI) {
2633  if (++TaintNum == TaintExtent.size())
2634  break;
2635  LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first);
2636  assert(LastMI && "Range must end at a proper instruction");
2637  TaintedLanes = TaintExtent[TaintNum].second;
2638  }
2639  ++MI;
2640  }
2641 
2642  // The tainted lanes are unused.
2643  V.Resolution = CR_Replace;
2644  ++NumLaneResolves;
2645  }
2646  return true;
2647 }
2648 
2649 bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) {
2650  Val &V = Vals[ValNo];
2651  if (V.Pruned || V.PrunedComputed)
2652  return V.Pruned;
2653 
2654  if (V.Resolution != CR_Erase && V.Resolution != CR_Merge)
2655  return V.Pruned;
2656 
2657  // Follow copies up the dominator tree and check if any intermediate value
2658  // has been pruned.
2659  V.PrunedComputed = true;
2660  V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this);
2661  return V.Pruned;
2662 }
2663 
2664 void JoinVals::pruneValues(JoinVals &Other,
2665  SmallVectorImpl<SlotIndex> &EndPoints,
2666  bool changeInstrs) {
2667  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2668  SlotIndex Def = LR.getValNumInfo(i)->def;
2669  switch (Vals[i].Resolution) {
2670  case CR_Keep:
2671  break;
2672  case CR_Replace: {
2673  // This value takes precedence over the value in Other.LR.
2674  LIS->pruneValue(Other.LR, Def, &EndPoints);
2675  // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF
2676  // instructions are only inserted to provide a live-out value for PHI
2677  // predecessors, so the instruction should simply go away once its value
2678  // has been replaced.
2679  Val &OtherV = Other.Vals[Vals[i].OtherVNI->id];
2680  bool EraseImpDef = OtherV.ErasableImplicitDef &&
2681  OtherV.Resolution == CR_Keep;
2682  if (!Def.isBlock()) {
2683  if (changeInstrs) {
2684  // Remove <def,read-undef> flags. This def is now a partial redef.
2685  // Also remove dead flags since the joined live range will
2686  // continue past this instruction.
2687  for (MachineOperand &MO :
2688  Indexes->getInstructionFromIndex(Def)->operands()) {
2689  if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) {
2690  if (MO.getSubReg() != 0 && MO.isUndef() && !EraseImpDef)
2691  MO.setIsUndef(false);
2692  MO.setIsDead(false);
2693  }
2694  }
2695  }
2696  // This value will reach instructions below, but we need to make sure
2697  // the live range also reaches the instruction at Def.
2698  if (!EraseImpDef)
2699  EndPoints.push_back(Def);
2700  }
2701  DEBUG(dbgs() << "\t\tpruned " << printReg(Other.Reg) << " at " << Def
2702  << ": " << Other.LR << '\n');
2703  break;
2704  }
2705  case CR_Erase:
2706  case CR_Merge:
2707  if (isPrunedValue(i, Other)) {
2708  // This value is ultimately a copy of a pruned value in LR or Other.LR.
2709  // We can no longer trust the value mapping computed by
2710  // computeAssignment(), the value that was originally copied could have
2711  // been replaced.
2712  LIS->pruneValue(LR, Def, &EndPoints);
2713  DEBUG(dbgs() << "\t\tpruned all of " << printReg(Reg) << " at "
2714  << Def << ": " << LR << '\n');
2715  }
2716  break;
2717  case CR_Unresolved:
2718  case CR_Impossible:
2719  llvm_unreachable("Unresolved conflicts");
2720  }
2721  }
2722 }
2723 
2724 void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) {
2725  // Look for values being erased.
2726  bool DidPrune = false;
2727  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2728  // We should trigger in all cases in which eraseInstrs() does something.
2729  // match what eraseInstrs() is doing, print a message so
2730  if (Vals[i].Resolution != CR_Erase &&
2731  (Vals[i].Resolution != CR_Keep || !Vals[i].ErasableImplicitDef ||
2732  !Vals[i].Pruned))
2733  continue;
2734 
2735  // Check subranges at the point where the copy will be removed.
2736  SlotIndex Def = LR.getValNumInfo(i)->def;
2737  // Print message so mismatches with eraseInstrs() can be diagnosed.
2738  DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def << '\n');
2739  for (LiveInterval::SubRange &S : LI.subranges()) {
2740  LiveQueryResult Q = S.Query(Def);
2741 
2742  // If a subrange starts at the copy then an undefined value has been
2743  // copied and we must remove that subrange value as well.
2744  VNInfo *ValueOut = Q.valueOutOrDead();
2745  if (ValueOut != nullptr && Q.valueIn() == nullptr) {
2746  DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask)
2747  << " at " << Def << "\n");
2748  LIS->pruneValue(S, Def, nullptr);
2749  DidPrune = true;
2750  // Mark value number as unused.
2751  ValueOut->markUnused();
2752  continue;
2753  }
2754  // If a subrange ends at the copy, then a value was copied but only
2755  // partially used later. Shrink the subregister range appropriately.
2756  if (Q.valueIn() != nullptr && Q.valueOut() == nullptr) {
2757  DEBUG(dbgs() << "\t\tDead uses at sublane " << PrintLaneMask(S.LaneMask)
2758  << " at " << Def << "\n");
2759  ShrinkMask |= S.LaneMask;
2760  }
2761  }
2762  }
2763  if (DidPrune)
2764  LI.removeEmptySubRanges();
2765 }
2766 
2767 /// Check if any of the subranges of @p LI contain a definition at @p Def.
2769  for (LiveInterval::SubRange &SR : LI.subranges()) {
2770  if (VNInfo *VNI = SR.Query(Def).valueOutOrDead())
2771  if (VNI->def == Def)
2772  return true;
2773  }
2774  return false;
2775 }
2776 
2777 void JoinVals::pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange) {
2778  assert(&static_cast<LiveRange&>(LI) == &LR);
2779 
2780  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2781  if (Vals[i].Resolution != CR_Keep)
2782  continue;
2783  VNInfo *VNI = LR.getValNumInfo(i);
2784  if (VNI->isUnused() || VNI->isPHIDef() || isDefInSubRange(LI, VNI->def))
2785  continue;
2786  Vals[i].Pruned = true;
2787  ShrinkMainRange = true;
2788  }
2789 }
2790 
2791 void JoinVals::removeImplicitDefs() {
2792  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2793  Val &V = Vals[i];
2794  if (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned)
2795  continue;
2796 
2797  VNInfo *VNI = LR.getValNumInfo(i);
2798  VNI->markUnused();
2799  LR.removeValNo(VNI);
2800  }
2801 }
2802 
2803 void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
2804  SmallVectorImpl<unsigned> &ShrinkRegs,
2805  LiveInterval *LI) {
2806  for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2807  // Get the def location before markUnused() below invalidates it.
2808  SlotIndex Def = LR.getValNumInfo(i)->def;
2809  switch (Vals[i].Resolution) {
2810  case CR_Keep: {
2811  // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any
2812  // longer. The IMPLICIT_DEF instructions are only inserted by
2813  // PHIElimination to guarantee that all PHI predecessors have a value.
2814  if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)
2815  break;
2816  // Remove value number i from LR.
2817  // For intervals with subranges, removing a segment from the main range
2818  // may require extending the previous segment: for each definition of
2819  // a subregister, there will be a corresponding def in the main range.
2820  // That def may fall in the middle of a segment from another subrange.
2821  // In such cases, removing this def from the main range must be
2822  // complemented by extending the main range to account for the liveness
2823  // of the other subrange.
2824  VNInfo *VNI = LR.getValNumInfo(i);
2825  SlotIndex Def = VNI->def;
2826  // The new end point of the main range segment to be extended.
2827  SlotIndex NewEnd;
2828  if (LI != nullptr) {
2829  LiveRange::iterator I = LR.FindSegmentContaining(Def);
2830  assert(I != LR.end());
2831  // Do not extend beyond the end of the segment being removed.
2832  // The segment may have been pruned in preparation for joining
2833  // live ranges.
2834  NewEnd = I->end;
2835  }
2836 
2837  LR.removeValNo(VNI);
2838  // Note that this VNInfo is reused and still referenced in NewVNInfo,
2839  // make it appear like an unused value number.
2840  VNI->markUnused();
2841 
2842  if (LI != nullptr && LI->hasSubRanges()) {
2843  assert(static_cast<LiveRange*>(LI) == &LR);
2844  // Determine the end point based on the subrange information:
2845  // minimum of (earliest def of next segment,
2846  // latest end point of containing segment)
2847  SlotIndex ED, LE;
2848  for (LiveInterval::SubRange &SR : LI->subranges()) {
2849  LiveRange::iterator I = SR.find(Def);
2850  if (I == SR.end())
2851  continue;
2852  if (I->start > Def)
2853  ED = ED.isValid() ? std::min(ED, I->start) : I->start;
2854  else
2855  LE = LE.isValid() ? std::max(LE, I->end) : I->end;
2856  }
2857  if (LE.isValid())
2858  NewEnd = std::min(NewEnd, LE);
2859  if (ED.isValid())
2860  NewEnd = std::min(NewEnd, ED);
2861 
2862  // We only want to do the extension if there was a subrange that
2863  // was live across Def.
2864  if (LE.isValid()) {
2865  LiveRange::iterator S = LR.find(Def);
2866  if (S != LR.begin())
2867  std::prev(S)->end = NewEnd;
2868  }
2869  }
2870  DEBUG({
2871  dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n';
2872  if (LI != nullptr)
2873  dbgs() << "\t\t LHS = " << *LI << '\n';
2874  });
2876  }
2877 
2878  case CR_Erase: {
2879  MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
2880  assert(MI && "No instruction to erase");
2881  if (MI->isCopy()) {
2882  unsigned Reg = MI->getOperand(1).getReg();
2884  Reg != CP.getSrcReg() && Reg != CP.getDstReg())
2885  ShrinkRegs.push_back(Reg);
2886  }
2887  ErasedInstrs.insert(MI);
2888  DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI);
2889  LIS->RemoveMachineInstrFromMaps(*MI);
2890  MI->eraseFromParent();
2891  break;
2892  }
2893  default:
2894  break;
2895  }
2896  }
2897 }
2898 
2899 void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
2900  LaneBitmask LaneMask,
2901  const CoalescerPair &CP) {
2902  SmallVector<VNInfo*, 16> NewVNInfo;
2903  JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask,
2904  NewVNInfo, CP, LIS, TRI, true, true);
2905  JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask,
2906  NewVNInfo, CP, LIS, TRI, true, true);
2907 
2908  // Compute NewVNInfo and resolve conflicts (see also joinVirtRegs())
2909  // We should be able to resolve all conflicts here as we could successfully do
2910  // it on the mainrange already. There is however a problem when multiple
2911  // ranges get mapped to the "overflow" lane mask bit which creates unexpected
2912  // interferences.
2913  if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {
2914  // We already determined that it is legal to merge the intervals, so this
2915  // should never fail.
2916  llvm_unreachable("*** Couldn't join subrange!\n");
2917  }
2918  if (!LHSVals.resolveConflicts(RHSVals) ||
2919  !RHSVals.resolveConflicts(LHSVals)) {
2920  // We already determined that it is legal to merge the intervals, so this
2921  // should never fail.
2922  llvm_unreachable("*** Couldn't join subrange!\n");
2923  }
2924 
2925  // The merging algorithm in LiveInterval::join() can't handle conflicting
2926  // value mappings, so we need to remove any live ranges that overlap a
2927  // CR_Replace resolution. Collect a set of end points that can be used to
2928  // restore the live range after joining.
2929  SmallVector<SlotIndex, 8> EndPoints;
2930  LHSVals.pruneValues(RHSVals, EndPoints, false);
2931  RHSVals.pruneValues(LHSVals, EndPoints, false);
2932 
2933  LHSVals.removeImplicitDefs();
2934  RHSVals.removeImplicitDefs();
2935 
2936  LRange.verify();
2937  RRange.verify();
2938 
2939  // Join RRange into LHS.
2940  LRange.join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),
2941  NewVNInfo);
2942 
2943  DEBUG(dbgs() << "\t\tjoined lanes: " << LRange << "\n");
2944  if (EndPoints.empty())
2945  return;
2946 
2947  // Recompute the parts of the live range we had to remove because of
2948  // CR_Replace conflicts.
2949  DEBUG({
2950  dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";
2951  for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {
2952  dbgs() << EndPoints[i];
2953  if (i != n-1)
2954  dbgs() << ',';
2955  }
2956  dbgs() << ": " << LRange << '\n';
2957  });
2958  LIS->extendToIndices(LRange, EndPoints);
2959 }
2960 
2961 void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
2962  const LiveRange &ToMerge,
2963  LaneBitmask LaneMask,
2964  CoalescerPair &CP) {
2966  LI.refineSubRanges(Allocator, LaneMask,
2967  [this,&Allocator,&ToMerge,&CP](LiveInterval::SubRange &SR) {
2968  if (SR.empty()) {
2969  SR.assign(ToMerge, Allocator);
2970  } else {
2971  // joinSubRegRange() destroys the merged range, so we need a copy.
2972  LiveRange RangeCopy(ToMerge, Allocator);
2973  joinSubRegRanges(SR, RangeCopy, SR.LaneMask, CP);
2974  }
2975  });
2976 }
2977 
2978 bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
2979  SmallVector<VNInfo*, 16> NewVNInfo;
2980  LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
2981  LiveInterval &LHS = LIS->getInterval(CP.getDstReg());
2982  bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC());
2983  JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), LaneBitmask::getNone(),
2984  NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
2985  JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), LaneBitmask::getNone(),
2986  NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
2987 
2988  DEBUG(dbgs() << "\t\tRHS = " << RHS
2989  << "\n\t\tLHS = " << LHS
2990  << '\n');
2991 
2992  // First compute NewVNInfo and the simple value mappings.
2993  // Detect impossible conflicts early.
2994  if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))
2995  return false;
2996 
2997  // Some conflicts can only be resolved after all values have been mapped.
2998  if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))
2999  return false;
3000 
3001  // All clear, the live ranges can be merged.
3002  if (RHS.hasSubRanges() || LHS.hasSubRanges()) {
3003  BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
3004 
3005  // Transform lanemasks from the LHS to masks in the coalesced register and
3006  // create initial subranges if necessary.
3007  unsigned DstIdx = CP.getDstIdx();
3008  if (!LHS.hasSubRanges()) {
3009  LaneBitmask Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask()
3010  : TRI->getSubRegIndexLaneMask(DstIdx);
3011  // LHS must support subregs or we wouldn't be in this codepath.
3012  assert(Mask.any());
3013  LHS.createSubRangeFrom(Allocator, Mask, LHS);
3014  } else if (DstIdx != 0) {
3015  // Transform LHS lanemasks to new register class if necessary.
3016  for (LiveInterval::SubRange &R : LHS.subranges()) {
3017  LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask);
3018  R.LaneMask = Mask;
3019  }
3020  }
3021  DEBUG(dbgs() << "\t\tLHST = " << printReg(CP.getDstReg())
3022  << ' ' << LHS << '\n');
3023 
3024  // Determine lanemasks of RHS in the coalesced register and merge subranges.
3025  unsigned SrcIdx = CP.getSrcIdx();
3026  if (!RHS.hasSubRanges()) {
3027  LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
3028  : TRI->getSubRegIndexLaneMask(SrcIdx);
3029  mergeSubRangeInto(LHS, RHS, Mask, CP);
3030  } else {
3031  // Pair up subranges and merge.
3032  for (LiveInterval::SubRange &R : RHS.subranges()) {
3033  LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);
3034  mergeSubRangeInto(LHS, R, Mask, CP);
3035  }
3036  }
3037  DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n");
3038 
3039  // Pruning implicit defs from subranges may result in the main range
3040  // having stale segments.
3041  LHSVals.pruneMainSegments(LHS, ShrinkMainRange);
3042 
3043  LHSVals.pruneSubRegValues(LHS, ShrinkMask);
3044  RHSVals.pruneSubRegValues(LHS, ShrinkMask);
3045  }
3046 
3047  // The merging algorithm in LiveInterval::join() can't handle conflicting
3048  // value mappings, so we need to remove any live ranges that overlap a
3049  // CR_Replace resolution. Collect a set of end points that can be used to
3050  // restore the live range after joining.
3051  SmallVector<SlotIndex, 8> EndPoints;
3052  LHSVals.pruneValues(RHSVals, EndPoints, true);
3053  RHSVals.pruneValues(LHSVals, EndPoints, true);
3054 
3055  // Erase COPY and IMPLICIT_DEF instructions. This may cause some external
3056  // registers to require trimming.
3057  SmallVector<unsigned, 8> ShrinkRegs;
3058  LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &LHS);
3059  RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
3060  while (!ShrinkRegs.empty())
3061  shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
3062 
3063  // Join RHS into LHS.
3064  LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
3065 
3066  // Kill flags are going to be wrong if the live ranges were overlapping.
3067  // Eventually, we should simply clear all kill flags when computing live
3068  // ranges. They are reinserted after register allocation.
3069  MRI->clearKillFlags(LHS.reg);
3070  MRI->clearKillFlags(RHS.reg);
3071 
3072  if (!EndPoints.empty()) {
3073  // Recompute the parts of the live range we had to remove because of
3074  // CR_Replace conflicts.
3075  DEBUG({
3076  dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";
3077  for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {
3078  dbgs() << EndPoints[i];
3079  if (i != n-1)
3080  dbgs() << ',';
3081  }
3082  dbgs() << ": " << LHS << '\n';
3083  });
3084  LIS->extendToIndices((LiveRange&)LHS, EndPoints);
3085  }
3086 
3087  return true;
3088 }
3089 
3090 bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
3091  return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
3092 }
3093 
3094 namespace {
3095 
3096 /// Information concerning MBB coalescing priority.
3097 struct MBBPriorityInfo {
3098  MachineBasicBlock *MBB;
3099  unsigned Depth;
3100  bool IsSplit;
3101 
3102  MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit)
3103  : MBB(mbb), Depth(depth), IsSplit(issplit) {}
3104 };
3105 
3106 } // end anonymous namespace
3107 
3108 /// C-style comparator that sorts first based on the loop depth of the basic
3109 /// block (the unsigned), and then on the MBB number.
3110 ///
3111 /// EnableGlobalCopies assumes that the primary sort key is loop depth.
3112 static int compareMBBPriority(const MBBPriorityInfo *LHS,
3113  const MBBPriorityInfo *RHS) {
3114  // Deeper loops first
3115  if (LHS->Depth != RHS->Depth)
3116  return LHS->Depth > RHS->Depth ? -1 : 1;
3117 
3118  // Try to unsplit critical edges next.
3119  if (LHS->IsSplit != RHS->IsSplit)
3120  return LHS->IsSplit ? -1 : 1;
3121 
3122  // Prefer blocks that are more connected in the CFG. This takes care of
3123  // the most difficult copies first while intervals are short.
3124  unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size();
3125  unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size();
3126  if (cl != cr)
3127  return cl > cr ? -1 : 1;
3128 
3129  // As a last resort, sort by block number.
3130  return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1;
3131 }
3132 
3133 /// \returns true if the given copy uses or defines a local live range.
3134 static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) {
3135  if (!Copy->isCopy())
3136  return false;
3137 
3138  if (Copy->getOperand(1).isUndef())
3139  return false;
3140 
3141  unsigned SrcReg = Copy->getOperand(1).getReg();
3142  unsigned DstReg = Copy->getOperand(0).getReg();
3145  return false;
3146 
3147  return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg))
3148  || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg));
3149 }
3150 
3151 bool RegisterCoalescer::
3152 copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) {
3153  bool Progress = false;
3154  for (unsigned i = 0, e = CurrList.size(); i != e; ++i) {
3155  if (!CurrList[i])
3156  continue;
3157  // Skip instruction pointers that have already been erased, for example by
3158  // dead code elimination.
3159  if (ErasedInstrs.count(CurrList[i])) {
3160  CurrList[i] = nullptr;
3161  continue;
3162  }
3163  bool Again = false;
3164  bool Success = joinCopy(CurrList[i], Again);
3165  Progress |= Success;
3166  if (Success || !Again)
3167  CurrList[i] = nullptr;
3168  }
3169  return Progress;
3170 }
3171 
3172 /// Check if DstReg is a terminal node.
3173 /// I.e., it does not have any affinity other than \p Copy.
3174 static bool isTerminalReg(unsigned DstReg, const MachineInstr &Copy,
3175  const MachineRegisterInfo *MRI) {
3176  assert(Copy.isCopyLike());
3177  // Check if the destination of this copy as any other affinity.
3178  for (const MachineInstr &MI : MRI->reg_nodbg_instructions(DstReg))
3179  if (&MI != &Copy && MI.isCopyLike())
3180  return false;
3181  return true;
3182 }
3183 
3184 bool RegisterCoalescer::applyTerminalRule(const MachineInstr &Copy) const {
3185  assert(Copy.isCopyLike());
3186  if (!UseTerminalRule)
3187  return false;
3188  unsigned DstReg, DstSubReg, SrcReg, SrcSubReg;
3189  isMoveInstr(*TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg);
3190  // Check if the destination of this copy has any other affinity.
3192  // If SrcReg is a physical register, the copy won't be coalesced.
3193  // Ignoring it may have other side effect (like missing
3194  // rematerialization). So keep it.
3196  !isTerminalReg(DstReg, Copy, MRI))
3197  return false;
3198 
3199  // DstReg is a terminal node. Check if it interferes with any other
3200  // copy involving SrcReg.
3201  const MachineBasicBlock *OrigBB = Copy.getParent();
3202  const LiveInterval &DstLI = LIS->getInterval(DstReg);
3203  for (const MachineInstr &MI : MRI->reg_nodbg_instructions(SrcReg)) {
3204  // Technically we should check if the weight of the new copy is
3205  // interesting compared to the other one and update the weight
3206  // of the copies accordingly. However, this would only work if
3207  // we would gather all the copies first then coalesce, whereas
3208  // right now we interleave both actions.
3209  // For now, just consider the copies that are in the same block.
3210  if (&MI == &Copy || !MI.isCopyLike() || MI.getParent() != OrigBB)
3211  continue;
3212  unsigned OtherReg, OtherSubReg, OtherSrcReg, OtherSrcSubReg;
3213  isMoveInstr(*TRI, &Copy, OtherSrcReg, OtherReg, OtherSrcSubReg,
3214  OtherSubReg);
3215  if (OtherReg == SrcReg)
3216  OtherReg = OtherSrcReg;
3217  // Check if OtherReg is a non-terminal.
3219  isTerminalReg(OtherReg, MI, MRI))
3220  continue;
3221  // Check that OtherReg interfere with DstReg.
3222  if (LIS->getInterval(OtherReg).overlaps(DstLI)) {
3223  DEBUG(dbgs() << "Apply terminal rule for: " << printReg(DstReg) << '\n');
3224  return true;
3225  }
3226  }
3227  return false;
3228 }
3229 
3230 void
3231 RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) {
3232  DEBUG(dbgs() << MBB->getName() << ":\n");
3233 
3234  // Collect all copy-like instructions in MBB. Don't start coalescing anything
3235  // yet, it might invalidate the iterator.
3236  const unsigned PrevSize = WorkList.size();
3237  if (JoinGlobalCopies) {
3238  SmallVector<MachineInstr*, 2> LocalTerminals;
3239  SmallVector<MachineInstr*, 2> GlobalTerminals;
3240  // Coalesce copies bottom-up to coalesce local defs before local uses. They
3241  // are not inherently easier to resolve, but slightly preferable until we
3242  // have local live range splitting. In particular this is required by
3243  // cmp+jmp macro fusion.
3244  for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
3245  MII != E; ++MII) {
3246  if (!MII->isCopyLike())
3247  continue;
3248  bool ApplyTerminalRule = applyTerminalRule(*MII);
3249  if (isLocalCopy(&(*MII), LIS)) {
3250  if (ApplyTerminalRule)
3251  LocalTerminals.push_back(&(*MII));
3252  else
3253  LocalWorkList.push_back(&(*MII));
3254  } else {
3255  if (ApplyTerminalRule)
3256  GlobalTerminals.push_back(&(*MII));
3257  else
3258  WorkList.push_back(&(*MII));
3259  }
3260  }
3261  // Append the copies evicted by the terminal rule at the end of the list.
3262  LocalWorkList.append(LocalTerminals.begin(), LocalTerminals.end());
3263  WorkList.append(GlobalTerminals.begin(), GlobalTerminals.end());
3264  }
3265  else {
3267  for (MachineInstr &MII : *MBB)
3268  if (MII.isCopyLike()) {
3269  if (applyTerminalRule(MII))
3270  Terminals.push_back(&MII);
3271  else
3272  WorkList.push_back(&MII);
3273  }
3274  // Append the copies evicted by the terminal rule at the end of the list.
3275  WorkList.append(Terminals.begin(), Terminals.end());
3276  }
3277  // Try coalescing the collected copies immediately, and remove the nulls.
3278  // This prevents the WorkList from getting too large since most copies are
3279  // joinable on the first attempt.
3281  CurrList(WorkList.begin() + PrevSize, WorkList.end());
3282  if (copyCoalesceWorkList(CurrList))
3283  WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(),
3284  nullptr), WorkList.end());
3285 }
3286 
3287 void RegisterCoalescer::coalesceLocals() {
3288  copyCoalesceWorkList(LocalWorkList);
3289  for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) {
3290  if (LocalWorkList[j])
3291  WorkList.push_back(LocalWorkList[j]);
3292  }
3293  LocalWorkList.clear();
3294 }
3295 
3296 void RegisterCoalescer::joinAllIntervals() {
3297  DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n");
3298  assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around.");
3299 
3300  std::vector<MBBPriorityInfo> MBBs;
3301  MBBs.reserve(MF->size());
3302  for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I) {
3303  MachineBasicBlock *MBB = &*I;
3304  MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB),
3305  JoinSplitEdges && isSplitEdge(MBB)));
3306  }
3307  array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority);
3308 
3309  // Coalesce intervals in MBB priority order.
3310  unsigned CurrDepth = std::numeric_limits<unsigned>::max();
3311  for (unsigned i = 0, e = MBBs.size(); i != e; ++i) {
3312  // Try coalescing the collected local copies for deeper loops.
3313  if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) {
3314  coalesceLocals();
3315  CurrDepth = MBBs[i].Depth;
3316  }
3317  copyCoalesceInMBB(MBBs[i].MBB);
3318  }
3319  coalesceLocals();
3320 
3321  // Joining intervals can allow other intervals to be joined. Iteratively join
3322  // until we make no progress.
3323  while (copyCoalesceWorkList(WorkList))
3324  /* empty */ ;
3325 }
3326 
3327 void RegisterCoalescer::releaseMemory() {
3328  ErasedInstrs.clear();
3329  WorkList.clear();
3330  DeadDefs.clear();
3331  InflateRegs.clear();
3332 }
3333 
3334 bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) {
3335  MF = &fn;
3336  MRI = &fn.getRegInfo();
3337  const TargetSubtargetInfo &STI = fn.getSubtarget();
3338  TRI = STI.getRegisterInfo();
3339  TII = STI.getInstrInfo();
3340  LIS = &getAnalysis<LiveIntervals>();
3341  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3342  Loops = &getAnalysis<MachineLoopInfo>();
3344  JoinGlobalCopies = STI.enableJoinGlobalCopies();
3345  else
3346  JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE);
3347 
3348  // The MachineScheduler does not currently require JoinSplitEdges. This will
3349  // either be enabled unconditionally or replaced by a more general live range
3350  // splitting optimization.
3351  JoinSplitEdges = EnableJoinSplits;
3352 
3353  DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"
3354  << "********** Function: " << MF->getName() << '\n');
3355 
3356  if (VerifyCoalescing)
3357  MF->verify(this, "Before register coalescing");
3358 
3359  RegClassInfo.runOnMachineFunction(fn);
3360 
3361  // Join (coalesce) intervals if requested.
3362  if (EnableJoining)
3363  joinAllIntervals();
3364 
3365  // After deleting a lot of copies, register classes may be less constrained.
3366  // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 ->
3367  // DPR inflation.
3368  array_pod_sort(InflateRegs.begin(), InflateRegs.end());
3369  InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()),
3370  InflateRegs.end());
3371  DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n");
3372  for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) {
3373  unsigned Reg = InflateRegs[i];
3374  if (MRI->reg_nodbg_empty(Reg))
3375  continue;
3376  if (MRI->recomputeRegClass(Reg)) {
3377  DEBUG(dbgs() << printReg(Reg) << " inflated to "
3378  << TRI->getRegClassName(MRI->getRegClass(Reg)) << '\n');
3379  ++NumInflated;
3380 
3381  LiveInterval &LI = LIS->getInterval(Reg);
3382  if (LI.hasSubRanges()) {
3383  // If the inflated register class does not support subregisters anymore
3384  // remove the subranges.
3385  if (!MRI->shouldTrackSubRegLiveness(Reg)) {
3386  LI.clearSubRanges();
3387  } else {
3388 #ifndef NDEBUG
3389  LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
3390  // If subranges are still supported, then the same subregs
3391  // should still be supported.
3392  for (LiveInterval::SubRange &S : LI.subranges()) {
3393  assert((S.LaneMask & ~MaxMask).none());
3394  }
3395 #endif
3396  }
3397  }
3398  }
3399  }
3400 
3401  DEBUG(dump());
3402  if (VerifyCoalescing)
3403  MF->verify(this, "After register coalescing");
3404  return true;
3405 }
3406 
3407 void RegisterCoalescer::print(raw_ostream &O, const Module* m) const {
3408  LIS->print(O, m);
3409 }
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
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:271
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:163
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
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")
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:335
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:874
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:210
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:296
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
Reg
All possible values of the reg field in the ModR/M byte.
bool hasSubRanges() const
Returns true if subregister liveness information is available.
Definition: LiveInterval.h:751
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:766
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.
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
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:290
bool isFullCopy() const
Definition: MachineInstr.h:864
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:406
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:760
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
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:860
bool isImplicitDef() const
Definition: MachineInstr.h:834
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...
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
void substituteRegister(unsigned FromReg, unsigned ToReg, unsigned SubIdx, const TargetRegisterInfo &RegInfo, bool ClearIsRenamable=false)
Replace all occurrences of FromReg with ToReg:SubIdx, properly composing subreg indices where necessa...
virtual bool shouldCoalesce(MachineInstr *MI, const TargetRegisterClass *SrcRC, unsigned SubReg, const TargetRegisterClass *DstRC, unsigned DstSubReg, const TargetRegisterClass *NewRC, LiveIntervals &LIS) const
Subtarget Hooks.
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:819
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:225
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
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:132
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:923
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:932
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:507
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:142
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
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:235
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
#define DEBUG(X)
Definition: Debug.h:118
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...
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:298
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:670
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...