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