1//===- AArch64SRLTDefineSuperRegs.cpp -------------------------------------===//
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// When SubRegister Liveness Tracking (SRLT) is enabled, this pass adds
10// extra implicit-def's to instructions that define the low N bits of
11// a GPR/FPR register to also define the top bits, because all AArch64
12// instructions that write the low bits of a GPR/FPR also implicitly zero
13// the top bits. For example, 'mov w0, w1' writes zeroes to the top 32-bits of
14// x0, so this pass adds a `implicit-def $x0` after register allocation.
15//
16// These semantics are originally represented in the MIR using `SUBREG_TO_REG`
17// which expresses that the top bits have been defined by the preceding
18// instructions, but during register coalescing this information is lost and in
19// contrast to when SRTL is disabled, when rewriting virtual -> physical
20// registers the implicit-defs are not added to the instruction.
21//
22// There have been several attempts to fix this in the coalescer [1], but each
23// iteration has exposed new bugs and the patch had to be reverted.
24// Additionally, the concept of adding 'implicit-def' of a virtual register is
25// particularly fragile and many places don't expect it (for example in
26// `X86::commuteInstructionImpl` the code only looks at specific operands and
27// does not consider implicit-defs. Similar in `SplitEditor::addDeadDef` where
28// it traverses operand 'defs' rather than 'all_defs').
29//
30// We want a temporary solution that doesn't impact other targets and is simpler
31// and less intrusive than the patch proposed for the register coalescer [1], so
32// that we can enable SRLT for AArch64.
33//
34// The approach here is to just add the 'implicit-def' manually after rewriting
35// virtual regs -> physical regs. This still means that during the register
36// allocation process the dependences are not accurately represented in the MIR
37// and LiveIntervals, but there are several reasons why we believe this isn't a
38// problem in practice:
39// (A) The register allocator only spills entire virtual registers.
40// This is additionally guarded by code in
41// AArch64InstrInfo::storeRegToStackSlot/loadRegFromStackSlot
42// where it checks if a register matches the expected register class.
43// (B) Rematerialization only happens when the instruction writes the full
44// register.
45// (C) The high bits of the AArch64 register cannot be written independently.
46// (D) Instructions that write only part of a register always take that same
47// register as a tied input operand, to indicate it's a merging operation.
48//
49// (A) means that for two virtual registers of regclass GPR32 and GPR64, if the
50// GPR32 register is coalesced into the GPR64 vreg then the full GPR64 would
51// be spilled/filled even if only the low 32-bits would be required for the
52// given liverange. (B) means that the top bits of a GPR64 would never be
53// overwritten by rematerialising a GPR32 sub-register for a given liverange.
54// (C-D) means that we can assume that the MIR as input to the register
55// allocator correctly expresses the instruction behaviour and dependences
56// between values, so unless the register allocator would violate (A) or (B),
57// the MIR is otherwise sound.
58//
59// Alternative approaches have also been considered, such as:
60// (1) Changing the AArch64 instruction definitions to write all bits and
61// extract the low N bits for the result.
62// (2) Disabling coalescing of SUBREG_TO_REG and using regalloc hints to tell
63// the register allocator to favour the same register for the input/output.
64// (3) Adding a new coalescer guard node with a tied-operand constraint, such
65// that when the SUBREG_TO_REG is removed, something still represents that
66// the top bits are defined. The node would get removed before rewriting
67// virtregs.
68// (4) Using an explicit INSERT_SUBREG into a zero value and try to optimize
69// away the INSERT_SUBREG (this is a more explicit variant of (2) and (3))
70// (5) Adding a new MachineOperand flag that represents the top bits would be
71// defined, but are not read nor undef.
72//
73// (1) would be the best approach but would be a significant effort as it
74// requires rewriting most/all instruction definitions and fixing MIR passes
75// that rely on the current definitions, whereas (2-4) result in sub-optimal
76// code that can't really be avoided because the explicit nodes would stop
77// rematerialization. (5) might be a way to mitigate the
78// fragility of implicit-def's of virtual registers if we want to pursue
79// landing [1], but then we'd rather choose approach (1) to avoid using
80// SUBREG_TO_REG entirely.
81//
82// [1] https://github.com/llvm/llvm-project/pull/168353
83//===----------------------------------------------------------------------===//
84
85#include "AArch64.h"
86#include "AArch64InstrInfo.h"
87#include "AArch64MachineFunctionInfo.h"
88#include "AArch64Subtarget.h"
89#include "MCTargetDesc/AArch64AddressingModes.h"
90#include "llvm/ADT/BitVector.h"
91#include "llvm/ADT/SmallSet.h"
92#include "llvm/CodeGen/MachineBasicBlock.h"
93#include "llvm/CodeGen/MachineDominators.h"
94#include "llvm/CodeGen/MachineFunctionPass.h"
95#include "llvm/CodeGen/MachineLoopInfo.h"
96#include "llvm/CodeGen/MachineRegisterInfo.h"
97#include "llvm/CodeGen/RegisterClassInfo.h"
98#include "llvm/CodeGen/TargetRegisterInfo.h"
99#include "llvm/Support/Debug.h"
100
101using namespace llvm;
102
103#define DEBUG_TYPE "aarch64-srlt-define-superregs"
104#define PASS_NAME "AArch64 SRLT Define Super-Regs Pass"
105
106namespace {
107
108class AArch64SRLTDefineSuperRegsImpl {
109private:
110 const AArch64Subtarget *Subtarget = nullptr;
111 const AArch64RegisterInfo *TRI = nullptr;
112
113 Register getWidestSuperReg(Register R, const BitVector &RequiredBaseRegUnits,
114 const BitVector &QHiRegUnits);
115
116public:
117 bool run(MachineFunction &MF);
118};
119
120class AArch64SRLTDefineSuperRegsLegacy : public MachineFunctionPass {
121public:
122 inline static char ID = 0;
123
124 AArch64SRLTDefineSuperRegsLegacy() : MachineFunctionPass(ID) {}
125
126 bool runOnMachineFunction(MachineFunction &MF) override {
127 return AArch64SRLTDefineSuperRegsImpl().run(MF);
128 }
129
130 StringRef getPassName() const override { return PASS_NAME; }
131
132 void getAnalysisUsage(AnalysisUsage &AU) const override {
133 AU.setPreservesCFG();
134 MachineFunctionPass::getAnalysisUsage(AU);
135 }
136};
137
138} // end anonymous namespace
139
140INITIALIZE_PASS(AArch64SRLTDefineSuperRegsLegacy, DEBUG_TYPE, PASS_NAME, false,
141 false)
142
143// Returns the widest super-reg for a given reg, or NoRegister if no suitable
144// wider super-reg has been found. For example:
145// W0 -> X0
146// B1 -> Q1 (without SVE)
147// -> Z1 (with SVE)
148// W1_W2 -> X1_X2
149// D0_D1 -> Q0_Q1 (without SVE)
150// -> Z0_Z1 (with SVE)
151Register AArch64SRLTDefineSuperRegsImpl::getWidestSuperReg(
152 Register R, const BitVector &RequiredBaseRegUnits,
153 const BitVector &QHiRegUnits) {
154 assert(R.isPhysical() &&
155 "Expected to be run straight after virtregrewriter!");
156
157 BitVector Units(TRI->getNumRegUnits());
158 for (MCRegUnit U : TRI->regunits(Reg: R))
159 Units.set((unsigned)U);
160
161 auto IsSuitableSuperReg = [&](Register SR) {
162 for (MCRegUnit U : TRI->regunits(Reg: SR)) {
163 // Avoid choosing z1 as super-reg of d1 if SVE is not available.
164 // Q*_HI registers are only set for SVE registers, as those consist
165 // of the Q* register for the low 128 bits and the Q*_HI (artificial)
166 // register for the top (vscale-1) * 128 bits.
167 if (QHiRegUnits.test(Idx: (unsigned)U) &&
168 !Subtarget->isSVEorStreamingSVEAvailable())
169 return false;
170 // We consider a super-reg as unsuitable if any of its reg units is not
171 // artificial and not shared, as that would imply that U is a unit for a
172 // different register, which means the candidate super-reg is likely
173 // a register tuple.
174 if (!TRI->isArtificialRegUnit(Unit: U) &&
175 (!Units.test(Idx: (unsigned)U) || !RequiredBaseRegUnits.test(Idx: (unsigned)U)))
176 return false;
177 }
178 return true;
179 };
180
181 Register LargestSuperReg = AArch64::NoRegister;
182 for (Register SR : TRI->superregs(Reg: R))
183 if (IsSuitableSuperReg(SR) && (LargestSuperReg == AArch64::NoRegister ||
184 TRI->isSuperRegister(RegA: LargestSuperReg, RegB: SR)))
185 LargestSuperReg = SR;
186
187 return LargestSuperReg;
188}
189
190bool AArch64SRLTDefineSuperRegsImpl::run(MachineFunction &MF) {
191 Subtarget = &MF.getSubtarget<AArch64Subtarget>();
192 TRI = Subtarget->getRegisterInfo();
193 const MachineRegisterInfo *MRI = &MF.getRegInfo();
194
195 if (!MRI->subRegLivenessEnabled())
196 return false;
197
198 assert(!MRI->isSSA() && "Expected to be run after breaking down SSA form!");
199
200 auto XRegs = seq_inclusive<unsigned>(Begin: AArch64::X0, End: AArch64::X28);
201 auto ZRegs = seq_inclusive<unsigned>(Begin: AArch64::Z0, End: AArch64::Z31);
202 constexpr unsigned FixedRegs[] = {AArch64::FP, AArch64::LR, AArch64::SP};
203
204 BitVector RequiredBaseRegUnits(TRI->getNumRegUnits());
205 for (Register R : concat<unsigned>(Ranges&: XRegs, Ranges&: ZRegs, Ranges: FixedRegs))
206 for (MCRegUnit U : TRI->regunits(Reg: R))
207 RequiredBaseRegUnits.set((unsigned)U);
208
209 BitVector QHiRegUnits(TRI->getNumRegUnits());
210 for (Register R : seq_inclusive<unsigned>(Begin: AArch64::Q0_HI, End: AArch64::Q31_HI))
211 for (MCRegUnit U : TRI->regunits(Reg: R))
212 QHiRegUnits.set((unsigned)U);
213
214 bool Changed = false;
215 for (MachineBasicBlock &MBB : MF) {
216 for (MachineInstr &MI : MBB) {
217 // PATCHPOINT may have a 'def' that's not a register, avoid this.
218 if (MI.getOpcode() == TargetOpcode::PATCHPOINT)
219 continue;
220 // For each partial register write, also add an implicit-def for top bits
221 // of the register (e.g. for w0 add a def of x0).
222 SmallSet<Register, 8> SuperRegs;
223 for (const MachineOperand &DefOp : MI.defs())
224 if (Register R = getWidestSuperReg(R: DefOp.getReg(), RequiredBaseRegUnits,
225 QHiRegUnits);
226 R != AArch64::NoRegister)
227 SuperRegs.insert(V: R);
228
229 if (!SuperRegs.size())
230 continue;
231
232 LLVM_DEBUG(dbgs() << "Adding implicit-defs to: " << MI);
233 for (Register R : SuperRegs) {
234 LLVM_DEBUG(dbgs() << " " << printReg(R, TRI) << "\n");
235 bool IsRenamable = any_of(Range: MI.defs(), P: [&](const MachineOperand &MO) {
236 return MO.isRenamable() && TRI->regsOverlap(RegA: MO.getReg(), RegB: R);
237 });
238 bool IsDead = any_of(Range: MI.defs(), P: [&](const MachineOperand &MO) {
239 return MO.isDead() && TRI->regsOverlap(RegA: MO.getReg(), RegB: R);
240 });
241 MachineOperand DefOp = MachineOperand::CreateReg(
242 Reg: R, /*isDef=*/true, /*isImp=*/true, /*isKill=*/false,
243 /*isDead=*/IsDead, /*isUndef=*/false, /*isEarlyClobber=*/false,
244 /*SubReg=*/0, /*isDebug=*/false, /*isInternalRead=*/false,
245 /*isRenamable=*/IsRenamable);
246 MI.addOperand(Op: DefOp);
247 }
248 Changed = true;
249 }
250 }
251
252 return Changed;
253}
254
255FunctionPass *llvm::createAArch64SRLTDefineSuperRegsLegacyPass() {
256 return new AArch64SRLTDefineSuperRegsLegacy();
257}
258
259PreservedAnalyses
260AArch64SRLTDefineSuperRegsPass::run(MachineFunction &MF,
261 MachineFunctionAnalysisManager &MFAM) {
262 const bool Changed = AArch64SRLTDefineSuperRegsImpl().run(MF);
263 if (!Changed)
264 return PreservedAnalyses::all();
265 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
266 PA.preserveSet<CFGAnalyses>();
267 return PA;
268}
269