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