LLVM 20.0.0git
HexagonGenMux.cpp
Go to the documentation of this file.
1//===- HexagonGenMux.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// During instruction selection, MUX instructions are generated for
10// conditional assignments. Since such assignments often present an
11// opportunity to predicate instructions, HexagonExpandCondsets
12// expands MUXes into pairs of conditional transfers, and then proceeds
13// with predication of the producers/consumers of the registers involved.
14// This happens after exiting from the SSA form, but before the machine
15// instruction scheduler. After the scheduler and after the register
16// allocation there can be cases of pairs of conditional transfers
17// resulting from a MUX where neither of them was further predicated. If
18// these transfers are now placed far enough from the instruction defining
19// the predicate register, they cannot use the .new form. In such cases it
20// is better to collapse them back to a single MUX instruction.
21
22#include "HexagonInstrInfo.h"
23#include "HexagonRegisterInfo.h"
24#include "HexagonSubtarget.h"
25#include "llvm/ADT/BitVector.h"
26#include "llvm/ADT/DenseMap.h"
28#include "llvm/ADT/StringRef.h"
36#include "llvm/IR/DebugLoc.h"
37#include "llvm/MC/MCInstrDesc.h"
38#include "llvm/Pass.h"
41#include <algorithm>
42#include <cassert>
43#include <iterator>
44#include <limits>
45#include <utility>
46
47#define DEBUG_TYPE "hexmux"
48
49using namespace llvm;
50
51namespace llvm {
52
55
56} // end namespace llvm
57
58// Initialize this to 0 to always prefer generating mux by default.
59static cl::opt<unsigned> MinPredDist("hexagon-gen-mux-threshold", cl::Hidden,
60 cl::init(0), cl::desc("Minimum distance between predicate definition and "
61 "farther of the two predicated uses"));
62
63namespace {
64
65 class HexagonGenMux : public MachineFunctionPass {
66 public:
67 static char ID;
68
69 HexagonGenMux() : MachineFunctionPass(ID) {}
70
71 StringRef getPassName() const override {
72 return "Hexagon generate mux instructions";
73 }
74
75 void getAnalysisUsage(AnalysisUsage &AU) const override {
77 }
78
79 bool runOnMachineFunction(MachineFunction &MF) override;
80
83 MachineFunctionProperties::Property::NoVRegs);
84 }
85
86 private:
87 const HexagonInstrInfo *HII = nullptr;
88 const HexagonRegisterInfo *HRI = nullptr;
89
90 struct CondsetInfo {
91 unsigned PredR = 0;
92 unsigned TrueX = std::numeric_limits<unsigned>::max();
93 unsigned FalseX = std::numeric_limits<unsigned>::max();
94
95 CondsetInfo() = default;
96 };
97
98 struct DefUseInfo {
99 BitVector Defs, Uses;
100
101 DefUseInfo() = default;
102 DefUseInfo(const BitVector &D, const BitVector &U) : Defs(D), Uses(U) {}
103 };
104
105 struct MuxInfo {
107 unsigned DefR, PredR;
108 MachineOperand *SrcT, *SrcF;
109 MachineInstr *Def1, *Def2;
110
111 MuxInfo(MachineBasicBlock::iterator It, unsigned DR, unsigned PR,
113 MachineInstr &D2)
114 : At(It), DefR(DR), PredR(PR), SrcT(TOp), SrcF(FOp), Def1(&D1),
115 Def2(&D2) {}
116 };
117
118 using InstrIndexMap = DenseMap<MachineInstr *, unsigned>;
119 using DefUseInfoMap = DenseMap<unsigned, DefUseInfo>;
120 using MuxInfoList = SmallVector<MuxInfo, 4>;
121
122 bool isRegPair(unsigned Reg) const {
123 return Hexagon::DoubleRegsRegClass.contains(Reg);
124 }
125
126 void getSubRegs(unsigned Reg, BitVector &SRs) const;
127 void expandReg(unsigned Reg, BitVector &Set) const;
128 void getDefsUses(const MachineInstr *MI, BitVector &Defs,
129 BitVector &Uses) const;
130 void buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X,
131 DefUseInfoMap &DUM);
132 bool isCondTransfer(unsigned Opc) const;
133 unsigned getMuxOpcode(const MachineOperand &Src1,
134 const MachineOperand &Src2) const;
135 bool genMuxInBlock(MachineBasicBlock &B);
136 };
137
138} // end anonymous namespace
139
140char HexagonGenMux::ID = 0;
141
142INITIALIZE_PASS(HexagonGenMux, "hexagon-gen-mux",
143 "Hexagon generate mux instructions", false, false)
144
145void HexagonGenMux::getSubRegs(unsigned Reg, BitVector &SRs) const {
146 for (MCPhysReg I : HRI->subregs(Reg))
147 SRs[I] = true;
148}
149
150void HexagonGenMux::expandReg(unsigned Reg, BitVector &Set) const {
151 if (isRegPair(Reg))
152 getSubRegs(Reg, Set);
153 else
154 Set[Reg] = true;
155}
156
157void HexagonGenMux::getDefsUses(const MachineInstr *MI, BitVector &Defs,
158 BitVector &Uses) const {
159 // First, get the implicit defs and uses for this instruction.
160 unsigned Opc = MI->getOpcode();
161 const MCInstrDesc &D = HII->get(Opc);
162 for (MCPhysReg R : D.implicit_defs())
163 expandReg(R, Defs);
164 for (MCPhysReg R : D.implicit_uses())
165 expandReg(R, Uses);
166
167 // Look over all operands, and collect explicit defs and uses.
168 for (const MachineOperand &MO : MI->operands()) {
169 if (!MO.isReg() || MO.isImplicit())
170 continue;
171 Register R = MO.getReg();
172 BitVector &Set = MO.isDef() ? Defs : Uses;
173 expandReg(R, Set);
174 }
175}
176
177void HexagonGenMux::buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X,
178 DefUseInfoMap &DUM) {
179 unsigned Index = 0;
180 unsigned NR = HRI->getNumRegs();
181 BitVector Defs(NR), Uses(NR);
182
183 for (MachineInstr &MI : B) {
184 I2X.insert(std::make_pair(&MI, Index));
185 Defs.reset();
186 Uses.reset();
187 getDefsUses(&MI, Defs, Uses);
188 DUM.insert(std::make_pair(Index, DefUseInfo(Defs, Uses)));
189 Index++;
190 }
191}
192
193bool HexagonGenMux::isCondTransfer(unsigned Opc) const {
194 switch (Opc) {
195 case Hexagon::A2_tfrt:
196 case Hexagon::A2_tfrf:
197 case Hexagon::C2_cmoveit:
198 case Hexagon::C2_cmoveif:
199 return true;
200 }
201 return false;
202}
203
204unsigned HexagonGenMux::getMuxOpcode(const MachineOperand &Src1,
205 const MachineOperand &Src2) const {
206 bool IsReg1 = Src1.isReg(), IsReg2 = Src2.isReg();
207 if (IsReg1)
208 return IsReg2 ? Hexagon::C2_mux : Hexagon::C2_muxir;
209 if (IsReg2)
210 return Hexagon::C2_muxri;
211
212 // Neither is a register. The first source is extendable, but the second
213 // is not (s8).
214 if (Src2.isImm() && isInt<8>(Src2.getImm()))
215 return Hexagon::C2_muxii;
216
217 return 0;
218}
219
220bool HexagonGenMux::genMuxInBlock(MachineBasicBlock &B) {
221 bool Changed = false;
222 InstrIndexMap I2X;
223 DefUseInfoMap DUM;
224 buildMaps(B, I2X, DUM);
225
226 using CondsetMap = DenseMap<unsigned, CondsetInfo>;
227
228 CondsetMap CM;
229 MuxInfoList ML;
230
232 unsigned Opc = MI.getOpcode();
233 if (!isCondTransfer(Opc))
234 continue;
235 Register DR = MI.getOperand(0).getReg();
236 if (isRegPair(DR))
237 continue;
238 MachineOperand &PredOp = MI.getOperand(1);
239 if (PredOp.isUndef())
240 continue;
241
242 Register PR = PredOp.getReg();
243 unsigned Idx = I2X.lookup(&MI);
244 CondsetMap::iterator F = CM.find(DR);
245 bool IfTrue = HII->isPredicatedTrue(Opc);
246
247 // If there is no record of a conditional transfer for this register,
248 // or the predicate register differs, create a new record for it.
249 if (F != CM.end() && F->second.PredR != PR) {
250 CM.erase(F);
251 F = CM.end();
252 }
253 if (F == CM.end()) {
254 auto It = CM.insert(std::make_pair(DR, CondsetInfo()));
255 F = It.first;
256 F->second.PredR = PR;
257 }
258 CondsetInfo &CI = F->second;
259 if (IfTrue)
260 CI.TrueX = Idx;
261 else
262 CI.FalseX = Idx;
263 if (CI.TrueX == std::numeric_limits<unsigned>::max() ||
264 CI.FalseX == std::numeric_limits<unsigned>::max())
265 continue;
266
267 // There is now a complete definition of DR, i.e. we have the predicate
268 // register, the definition if-true, and definition if-false.
269
270 // First, check if the definitions are far enough from the definition
271 // of the predicate register.
272 unsigned MinX = std::min(CI.TrueX, CI.FalseX);
273 unsigned MaxX = std::max(CI.TrueX, CI.FalseX);
274 // Specifically, check if the predicate definition is within a prescribed
275 // distance from the farther of the two predicated instructions.
276 unsigned SearchX = (MaxX >= MinPredDist) ? MaxX-MinPredDist : 0;
277 bool NearDef = false;
278 for (unsigned X = SearchX; X < MaxX; ++X) {
279 const DefUseInfo &DU = DUM.lookup(X);
280 if (!DU.Defs[PR])
281 continue;
282 NearDef = true;
283 break;
284 }
285 if (NearDef)
286 continue;
287
288 // The predicate register is not defined in the last few instructions.
289 // Check if the conversion to MUX is possible (either "up", i.e. at the
290 // place of the earlier partial definition, or "down", where the later
291 // definition is located). Examine all defs and uses between these two
292 // definitions.
293 // SR1, SR2 - source registers from the first and the second definition.
294 MachineBasicBlock::iterator It1 = B.begin(), It2 = B.begin();
295 std::advance(It1, MinX);
296 std::advance(It2, MaxX);
297 MachineInstr &Def1 = *It1, &Def2 = *It2;
298 MachineOperand *Src1 = &Def1.getOperand(2), *Src2 = &Def2.getOperand(2);
299 Register SR1 = Src1->isReg() ? Src1->getReg() : Register();
300 Register SR2 = Src2->isReg() ? Src2->getReg() : Register();
301 bool Failure = false, CanUp = true, CanDown = true;
302 for (unsigned X = MinX+1; X < MaxX; X++) {
303 const DefUseInfo &DU = DUM.lookup(X);
304 if (DU.Defs[PR] || DU.Defs[DR] || DU.Uses[DR]) {
305 Failure = true;
306 break;
307 }
308 if (CanDown && DU.Defs[SR1])
309 CanDown = false;
310 if (CanUp && DU.Defs[SR2])
311 CanUp = false;
312 }
313 if (Failure || (!CanUp && !CanDown))
314 continue;
315
316 MachineOperand *SrcT = (MinX == CI.TrueX) ? Src1 : Src2;
317 MachineOperand *SrcF = (MinX == CI.FalseX) ? Src1 : Src2;
318 // Prefer "down", since this will move the MUX farther away from the
319 // predicate definition.
320 MachineBasicBlock::iterator At = CanDown ? Def2 : Def1;
321 ML.push_back(MuxInfo(At, DR, PR, SrcT, SrcF, Def1, Def2));
322 }
323
324 for (MuxInfo &MX : ML) {
325 unsigned MxOpc = getMuxOpcode(*MX.SrcT, *MX.SrcF);
326 if (!MxOpc)
327 continue;
328 // Basic correctness check: since we are deleting instructions, validate the
329 // iterators. There is a possibility that one of Def1 or Def2 is translated
330 // to "mux" and being considered for other "mux" instructions.
331 if (!MX.At->getParent() || !MX.Def1->getParent() || !MX.Def2->getParent())
332 continue;
333
334 MachineBasicBlock &B = *MX.At->getParent();
335 const DebugLoc &DL = B.findDebugLoc(MX.At);
336 auto NewMux = BuildMI(B, MX.At, DL, HII->get(MxOpc), MX.DefR)
337 .addReg(MX.PredR)
338 .add(*MX.SrcT)
339 .add(*MX.SrcF);
340 NewMux->clearKillInfo();
341 B.remove(MX.Def1);
342 B.remove(MX.Def2);
343 Changed = true;
344 }
345
346 // Fix up kill flags.
347
348 LiveRegUnits LPR(*HRI);
349 LPR.addLiveOuts(B);
350 for (MachineInstr &I : llvm::reverse(B)) {
351 if (I.isDebugInstr())
352 continue;
353 // This isn't 100% accurate, but it's safe.
354 // It won't detect (as a kill) a case like this
355 // r0 = add r0, 1 <-- r0 should be "killed"
356 // ... = r0
357 for (MachineOperand &Op : I.operands()) {
358 if (!Op.isReg() || !Op.isUse())
359 continue;
360 assert(Op.getSubReg() == 0 && "Should have physical registers only");
361 bool Live = !LPR.available(Op.getReg());
362 Op.setIsKill(!Live);
363 }
364 LPR.stepBackward(I);
365 }
366
367 return Changed;
368}
369
370bool HexagonGenMux::runOnMachineFunction(MachineFunction &MF) {
371 if (skipFunction(MF.getFunction()))
372 return false;
373 HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
374 HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
375 bool Changed = false;
376 for (auto &I : MF)
377 Changed |= genMuxInBlock(I);
378 return Changed;
379}
380
382 return new HexagonGenMux();
383}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
This file defines the DenseMap class.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static cl::opt< unsigned > MinPredDist("hexagon-gen-mux-threshold", cl::Hidden, cl::init(0), cl::desc("Minimum distance between predicate definition and " "farther of the two predicated uses"))
IRTranslator LLVM IR MI
A set of register units.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
Remove Loads Into Fake Uses
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
Represent the analysis usage information of a pass.
BitVector & reset()
Definition: BitVector.h:392
This class represents an Operation in the Expression.
A debug info location.
Definition: DebugLoc.h:33
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:310
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:30
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineInstrBuilder & add(const MachineOperand &MO) const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
Definition: MachineInstr.h:69
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:585
void clearKillInfo()
Clears kill flags on all operands.
MachineOperand class - Representation of each machine instruction operand.
int64_t getImm() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
Register getReg() const
getReg - Returns the register number.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:37
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:51
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:657
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:420
FunctionPass * createHexagonGenMux()
void initializeHexagonGenMuxPass(PassRegistry &Registry)