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