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