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