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