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