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