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