LLVM 19.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"
39#include "llvm/Pass.h"
42#include <algorithm>
43#include <cassert>
44#include <iterator>
45#include <limits>
46#include <utility>
47
48#define DEBUG_TYPE "hexmux"
49
50using namespace llvm;
51
52namespace llvm {
53
56
57} // end namespace llvm
58
59// Initialize this to 0 to always prefer generating mux by default.
60static cl::opt<unsigned> MinPredDist("hexagon-gen-mux-threshold", cl::Hidden,
61 cl::init(0), cl::desc("Minimum distance between predicate definition and "
62 "farther of the two predicated uses"));
63
64namespace {
65
66 class HexagonGenMux : public MachineFunctionPass {
67 public:
68 static char ID;
69
70 HexagonGenMux() : MachineFunctionPass(ID) {}
71
72 StringRef getPassName() const override {
73 return "Hexagon generate mux instructions";
74 }
75
76 void getAnalysisUsage(AnalysisUsage &AU) const override {
78 }
79
80 bool runOnMachineFunction(MachineFunction &MF) override;
81
84 MachineFunctionProperties::Property::NoVRegs);
85 }
86
87 private:
88 const HexagonInstrInfo *HII = nullptr;
89 const HexagonRegisterInfo *HRI = nullptr;
90
91 struct CondsetInfo {
92 unsigned PredR = 0;
93 unsigned TrueX = std::numeric_limits<unsigned>::max();
94 unsigned FalseX = std::numeric_limits<unsigned>::max();
95
96 CondsetInfo() = default;
97 };
98
99 struct DefUseInfo {
100 BitVector Defs, Uses;
101
102 DefUseInfo() = default;
103 DefUseInfo(const BitVector &D, const BitVector &U) : Defs(D), Uses(U) {}
104 };
105
106 struct MuxInfo {
108 unsigned DefR, PredR;
109 MachineOperand *SrcT, *SrcF;
110 MachineInstr *Def1, *Def2;
111
112 MuxInfo(MachineBasicBlock::iterator It, unsigned DR, unsigned PR,
114 MachineInstr &D2)
115 : At(It), DefR(DR), PredR(PR), SrcT(TOp), SrcF(FOp), Def1(&D1),
116 Def2(&D2) {}
117 };
118
119 using InstrIndexMap = DenseMap<MachineInstr *, unsigned>;
120 using DefUseInfoMap = DenseMap<unsigned, DefUseInfo>;
121 using MuxInfoList = SmallVector<MuxInfo, 4>;
122
123 bool isRegPair(unsigned Reg) const {
124 return Hexagon::DoubleRegsRegClass.contains(Reg);
125 }
126
127 void getSubRegs(unsigned Reg, BitVector &SRs) const;
128 void expandReg(unsigned Reg, BitVector &Set) const;
129 void getDefsUses(const MachineInstr *MI, BitVector &Defs,
130 BitVector &Uses) const;
131 void buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X,
132 DefUseInfoMap &DUM);
133 bool isCondTransfer(unsigned Opc) const;
134 unsigned getMuxOpcode(const MachineOperand &Src1,
135 const MachineOperand &Src2) const;
136 bool genMuxInBlock(MachineBasicBlock &B);
137 };
138
139} // end anonymous namespace
140
141char HexagonGenMux::ID = 0;
142
143INITIALIZE_PASS(HexagonGenMux, "hexagon-gen-mux",
144 "Hexagon generate mux instructions", false, false)
145
146void HexagonGenMux::getSubRegs(unsigned Reg, BitVector &SRs) const {
147 for (MCPhysReg I : HRI->subregs(Reg))
148 SRs[I] = true;
149}
150
151void HexagonGenMux::expandReg(unsigned Reg, BitVector &Set) const {
152 if (isRegPair(Reg))
153 getSubRegs(Reg, Set);
154 else
155 Set[Reg] = true;
156}
157
158void HexagonGenMux::getDefsUses(const MachineInstr *MI, BitVector &Defs,
159 BitVector &Uses) const {
160 // First, get the implicit defs and uses for this instruction.
161 unsigned Opc = MI->getOpcode();
162 const MCInstrDesc &D = HII->get(Opc);
163 for (MCPhysReg R : D.implicit_defs())
164 expandReg(R, Defs);
165 for (MCPhysReg R : D.implicit_uses())
166 expandReg(R, Uses);
167
168 // Look over all operands, and collect explicit defs and uses.
169 for (const MachineOperand &MO : MI->operands()) {
170 if (!MO.isReg() || MO.isImplicit())
171 continue;
172 Register R = MO.getReg();
173 BitVector &Set = MO.isDef() ? Defs : Uses;
174 expandReg(R, Set);
175 }
176}
177
178void HexagonGenMux::buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X,
179 DefUseInfoMap &DUM) {
180 unsigned Index = 0;
181 unsigned NR = HRI->getNumRegs();
182 BitVector Defs(NR), Uses(NR);
183
184 for (MachineInstr &MI : B) {
185 I2X.insert(std::make_pair(&MI, Index));
186 Defs.reset();
187 Uses.reset();
188 getDefsUses(&MI, Defs, Uses);
189 DUM.insert(std::make_pair(Index, DefUseInfo(Defs, Uses)));
190 Index++;
191 }
192}
193
194bool HexagonGenMux::isCondTransfer(unsigned Opc) const {
195 switch (Opc) {
196 case Hexagon::A2_tfrt:
197 case Hexagon::A2_tfrf:
198 case Hexagon::C2_cmoveit:
199 case Hexagon::C2_cmoveif:
200 return true;
201 }
202 return false;
203}
204
205unsigned HexagonGenMux::getMuxOpcode(const MachineOperand &Src1,
206 const MachineOperand &Src2) const {
207 bool IsReg1 = Src1.isReg(), IsReg2 = Src2.isReg();
208 if (IsReg1)
209 return IsReg2 ? Hexagon::C2_mux : Hexagon::C2_muxir;
210 if (IsReg2)
211 return Hexagon::C2_muxri;
212
213 // Neither is a register. The first source is extendable, but the second
214 // is not (s8).
215 if (Src2.isImm() && isInt<8>(Src2.getImm()))
216 return Hexagon::C2_muxii;
217
218 return 0;
219}
220
221bool HexagonGenMux::genMuxInBlock(MachineBasicBlock &B) {
222 bool Changed = false;
223 InstrIndexMap I2X;
224 DefUseInfoMap DUM;
225 buildMaps(B, I2X, DUM);
226
227 using CondsetMap = DenseMap<unsigned, CondsetInfo>;
228
229 CondsetMap CM;
230 MuxInfoList ML;
231
233 unsigned Opc = MI.getOpcode();
234 if (!isCondTransfer(Opc))
235 continue;
236 Register DR = MI.getOperand(0).getReg();
237 if (isRegPair(DR))
238 continue;
239 MachineOperand &PredOp = MI.getOperand(1);
240 if (PredOp.isUndef())
241 continue;
242
243 Register PR = PredOp.getReg();
244 unsigned Idx = I2X.lookup(&MI);
245 CondsetMap::iterator F = CM.find(DR);
246 bool IfTrue = HII->isPredicatedTrue(Opc);
247
248 // If there is no record of a conditional transfer for this register,
249 // or the predicate register differs, create a new record for it.
250 if (F != CM.end() && F->second.PredR != PR) {
251 CM.erase(F);
252 F = CM.end();
253 }
254 if (F == CM.end()) {
255 auto It = CM.insert(std::make_pair(DR, CondsetInfo()));
256 F = It.first;
257 F->second.PredR = PR;
258 }
259 CondsetInfo &CI = F->second;
260 if (IfTrue)
261 CI.TrueX = Idx;
262 else
263 CI.FalseX = Idx;
264 if (CI.TrueX == std::numeric_limits<unsigned>::max() ||
265 CI.FalseX == std::numeric_limits<unsigned>::max())
266 continue;
267
268 // There is now a complete definition of DR, i.e. we have the predicate
269 // register, the definition if-true, and definition if-false.
270
271 // First, check if the definitions are far enough from the definition
272 // of the predicate register.
273 unsigned MinX = std::min(CI.TrueX, CI.FalseX);
274 unsigned MaxX = std::max(CI.TrueX, CI.FalseX);
275 // Specifically, check if the predicate definition is within a prescribed
276 // distance from the farther of the two predicated instructions.
277 unsigned SearchX = (MaxX >= MinPredDist) ? MaxX-MinPredDist : 0;
278 bool NearDef = false;
279 for (unsigned X = SearchX; X < MaxX; ++X) {
280 const DefUseInfo &DU = DUM.lookup(X);
281 if (!DU.Defs[PR])
282 continue;
283 NearDef = true;
284 break;
285 }
286 if (NearDef)
287 continue;
288
289 // The predicate register is not defined in the last few instructions.
290 // Check if the conversion to MUX is possible (either "up", i.e. at the
291 // place of the earlier partial definition, or "down", where the later
292 // definition is located). Examine all defs and uses between these two
293 // definitions.
294 // SR1, SR2 - source registers from the first and the second definition.
295 MachineBasicBlock::iterator It1 = B.begin(), It2 = B.begin();
296 std::advance(It1, MinX);
297 std::advance(It2, MaxX);
298 MachineInstr &Def1 = *It1, &Def2 = *It2;
299 MachineOperand *Src1 = &Def1.getOperand(2), *Src2 = &Def2.getOperand(2);
300 Register SR1 = Src1->isReg() ? Src1->getReg() : Register();
301 Register SR2 = Src2->isReg() ? Src2->getReg() : Register();
302 bool Failure = false, CanUp = true, CanDown = true;
303 for (unsigned X = MinX+1; X < MaxX; X++) {
304 const DefUseInfo &DU = DUM.lookup(X);
305 if (DU.Defs[PR] || DU.Defs[DR] || DU.Uses[DR]) {
306 Failure = true;
307 break;
308 }
309 if (CanDown && DU.Defs[SR1])
310 CanDown = false;
311 if (CanUp && DU.Defs[SR2])
312 CanUp = false;
313 }
314 if (Failure || (!CanUp && !CanDown))
315 continue;
316
317 MachineOperand *SrcT = (MinX == CI.TrueX) ? Src1 : Src2;
318 MachineOperand *SrcF = (MinX == CI.FalseX) ? Src1 : Src2;
319 // Prefer "down", since this will move the MUX farther away from the
320 // predicate definition.
321 MachineBasicBlock::iterator At = CanDown ? Def2 : Def1;
322 ML.push_back(MuxInfo(At, DR, PR, SrcT, SrcF, Def1, Def2));
323 }
324
325 for (MuxInfo &MX : ML) {
326 unsigned MxOpc = getMuxOpcode(*MX.SrcT, *MX.SrcF);
327 if (!MxOpc)
328 continue;
329 // Basic correctness check: since we are deleting instructions, validate the
330 // iterators. There is a possibility that one of Def1 or Def2 is translated
331 // to "mux" and being considered for other "mux" instructions.
332 if (!MX.At->getParent() || !MX.Def1->getParent() || !MX.Def2->getParent())
333 continue;
334
335 MachineBasicBlock &B = *MX.At->getParent();
336 const DebugLoc &DL = B.findDebugLoc(MX.At);
337 auto NewMux = BuildMI(B, MX.At, DL, HII->get(MxOpc), MX.DefR)
338 .addReg(MX.PredR)
339 .add(*MX.SrcT)
340 .add(*MX.SrcF);
341 NewMux->clearKillInfo();
342 B.remove(MX.Def1);
343 B.remove(MX.Def2);
344 Changed = true;
345 }
346
347 // Fix up kill flags.
348
349 LiveRegUnits LPR(*HRI);
350 LPR.addLiveOuts(B);
351 for (MachineInstr &I : llvm::reverse(B)) {
352 if (I.isDebugInstr())
353 continue;
354 // This isn't 100% accurate, but it's safe.
355 // It won't detect (as a kill) a case like this
356 // r0 = add r0, 1 <-- r0 should be "killed"
357 // ... = r0
358 for (MachineOperand &Op : I.operands()) {
359 if (!Op.isReg() || !Op.isUse())
360 continue;
361 assert(Op.getSubReg() == 0 && "Should have physical registers only");
362 bool Live = !LPR.available(Op.getReg());
363 Op.setIsKill(!Live);
364 }
365 LPR.stepBackward(I);
366 }
367
368 return Changed;
369}
370
371bool HexagonGenMux::runOnMachineFunction(MachineFunction &MF) {
372 if (skipFunction(MF.getFunction()))
373 return false;
374 HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
375 HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
376 bool Changed = false;
377 for (auto &I : MF)
378 Changed |= genMuxInBlock(I);
379 return Changed;
380}
381
383 return new HexagonGenMux();
384}
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")
Rewrite Partial Register Uses
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
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:311
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:576
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:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
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:450
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:656
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
FunctionPass * createHexagonGenMux()
void initializeHexagonGenMuxPass(PassRegistry &Registry)