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