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