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