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