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