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