LLVM  16.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"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/ADT/StringRef.h"
36 #include "llvm/IR/DebugLoc.h"
37 #include "llvm/MC/MCInstrDesc.h"
38 #include "llvm/MC/MCRegisterInfo.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 
50 using namespace llvm;
51 
52 namespace llvm {
53 
56 
57 } // end namespace llvm
58 
59 // Initialize this to 0 to always prefer generating mux by default.
60 static 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 
64 namespace {
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 
82  MachineFunctionProperties getRequiredProperties() const override {
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 
141 char HexagonGenMux::ID = 0;
142 
143 INITIALIZE_PASS(HexagonGenMux, "hexagon-gen-mux",
144  "Hexagon generate mux instructions", false, false)
145 
146 void HexagonGenMux::getSubRegs(unsigned Reg, BitVector &SRs) const {
147  for (MCSubRegIterator I(Reg, HRI); I.isValid(); ++I)
148  SRs[*I] = true;
149 }
150 
151 void HexagonGenMux::expandReg(unsigned Reg, BitVector &Set) const {
152  if (isRegPair(Reg))
153  getSubRegs(Reg, Set);
154  else
155  Set[Reg] = true;
156 }
157 
158 void 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  if (const MCPhysReg *R = D.ImplicitDefs)
164  while (*R)
165  expandReg(*R++, Defs);
166  if (const MCPhysReg *R = D.ImplicitUses)
167  while (*R)
168  expandReg(*R++, Uses);
169 
170  // Look over all operands, and collect explicit defs and uses.
171  for (const MachineOperand &MO : MI->operands()) {
172  if (!MO.isReg() || MO.isImplicit())
173  continue;
174  Register R = MO.getReg();
175  BitVector &Set = MO.isDef() ? Defs : Uses;
176  expandReg(R, Set);
177  }
178 }
179 
180 void HexagonGenMux::buildMaps(MachineBasicBlock &B, InstrIndexMap &I2X,
181  DefUseInfoMap &DUM) {
182  unsigned Index = 0;
183  unsigned NR = HRI->getNumRegs();
184  BitVector Defs(NR), Uses(NR);
185 
186  for (MachineInstr &MI : B) {
187  I2X.insert(std::make_pair(&MI, Index));
188  Defs.reset();
189  Uses.reset();
190  getDefsUses(&MI, Defs, Uses);
191  DUM.insert(std::make_pair(Index, DefUseInfo(Defs, Uses)));
192  Index++;
193  }
194 }
195 
196 bool HexagonGenMux::isCondTransfer(unsigned Opc) const {
197  switch (Opc) {
198  case Hexagon::A2_tfrt:
199  case Hexagon::A2_tfrf:
200  case Hexagon::C2_cmoveit:
201  case Hexagon::C2_cmoveif:
202  return true;
203  }
204  return false;
205 }
206 
207 unsigned HexagonGenMux::getMuxOpcode(const MachineOperand &Src1,
208  const MachineOperand &Src2) const {
209  bool IsReg1 = Src1.isReg(), IsReg2 = Src2.isReg();
210  if (IsReg1)
211  return IsReg2 ? Hexagon::C2_mux : Hexagon::C2_muxir;
212  if (IsReg2)
213  return Hexagon::C2_muxri;
214 
215  // Neither is a register. The first source is extendable, but the second
216  // is not (s8).
217  if (Src2.isImm() && isInt<8>(Src2.getImm()))
218  return Hexagon::C2_muxii;
219 
220  return 0;
221 }
222 
223 bool HexagonGenMux::genMuxInBlock(MachineBasicBlock &B) {
224  bool Changed = false;
225  InstrIndexMap I2X;
226  DefUseInfoMap DUM;
227  buildMaps(B, I2X, DUM);
228 
229  using CondsetMap = DenseMap<unsigned, CondsetInfo>;
230 
231  CondsetMap CM;
232  MuxInfoList ML;
233 
235  unsigned Opc = MI.getOpcode();
236  if (!isCondTransfer(Opc))
237  continue;
238  Register DR = MI.getOperand(0).getReg();
239  if (isRegPair(DR))
240  continue;
241  MachineOperand &PredOp = MI.getOperand(1);
242  if (PredOp.isUndef())
243  continue;
244 
245  Register PR = PredOp.getReg();
246  unsigned Idx = I2X.lookup(&MI);
247  CondsetMap::iterator F = CM.find(DR);
248  bool IfTrue = HII->isPredicatedTrue(Opc);
249 
250  // If there is no record of a conditional transfer for this register,
251  // or the predicate register differs, create a new record for it.
252  if (F != CM.end() && F->second.PredR != PR) {
253  CM.erase(F);
254  F = CM.end();
255  }
256  if (F == CM.end()) {
257  auto It = CM.insert(std::make_pair(DR, CondsetInfo()));
258  F = It.first;
259  F->second.PredR = PR;
260  }
261  CondsetInfo &CI = F->second;
262  if (IfTrue)
263  CI.TrueX = Idx;
264  else
265  CI.FalseX = Idx;
266  if (CI.TrueX == std::numeric_limits<unsigned>::max() ||
267  CI.FalseX == std::numeric_limits<unsigned>::max())
268  continue;
269 
270  // There is now a complete definition of DR, i.e. we have the predicate
271  // register, the definition if-true, and definition if-false.
272 
273  // First, check if the definitions are far enough from the definition
274  // of the predicate register.
275  unsigned MinX = std::min(CI.TrueX, CI.FalseX);
276  unsigned MaxX = std::max(CI.TrueX, CI.FalseX);
277  // Specifically, check if the predicate definition is within a prescribed
278  // distance from the farther of the two predicated instructions.
279  unsigned SearchX = (MaxX >= MinPredDist) ? MaxX-MinPredDist : 0;
280  bool NearDef = false;
281  for (unsigned X = SearchX; X < MaxX; ++X) {
282  const DefUseInfo &DU = DUM.lookup(X);
283  if (!DU.Defs[PR])
284  continue;
285  NearDef = true;
286  break;
287  }
288  if (NearDef)
289  continue;
290 
291  // The predicate register is not defined in the last few instructions.
292  // Check if the conversion to MUX is possible (either "up", i.e. at the
293  // place of the earlier partial definition, or "down", where the later
294  // definition is located). Examine all defs and uses between these two
295  // definitions.
296  // SR1, SR2 - source registers from the first and the second definition.
297  MachineBasicBlock::iterator It1 = B.begin(), It2 = B.begin();
298  std::advance(It1, MinX);
299  std::advance(It2, MaxX);
300  MachineInstr &Def1 = *It1, &Def2 = *It2;
301  MachineOperand *Src1 = &Def1.getOperand(2), *Src2 = &Def2.getOperand(2);
302  Register SR1 = Src1->isReg() ? Src1->getReg() : Register();
303  Register SR2 = Src2->isReg() ? Src2->getReg() : Register();
304  bool Failure = false, CanUp = true, CanDown = true;
305  for (unsigned X = MinX+1; X < MaxX; X++) {
306  const DefUseInfo &DU = DUM.lookup(X);
307  if (DU.Defs[PR] || DU.Defs[DR] || DU.Uses[DR]) {
308  Failure = true;
309  break;
310  }
311  if (CanDown && DU.Defs[SR1])
312  CanDown = false;
313  if (CanUp && DU.Defs[SR2])
314  CanUp = false;
315  }
316  if (Failure || (!CanUp && !CanDown))
317  continue;
318 
319  MachineOperand *SrcT = (MinX == CI.TrueX) ? Src1 : Src2;
320  MachineOperand *SrcF = (MinX == CI.FalseX) ? Src1 : Src2;
321  // Prefer "down", since this will move the MUX farther away from the
322  // predicate definition.
323  MachineBasicBlock::iterator At = CanDown ? Def2 : Def1;
324  ML.push_back(MuxInfo(At, DR, PR, SrcT, SrcF, Def1, Def2));
325  }
326 
327  for (MuxInfo &MX : ML) {
328  unsigned MxOpc = getMuxOpcode(*MX.SrcT, *MX.SrcF);
329  if (!MxOpc)
330  continue;
331  // Basic correctness check: since we are deleting instructions, validate the
332  // iterators. There is a possibility that one of Def1 or Def2 is translated
333  // to "mux" and being considered for other "mux" instructions.
334  if (!MX.At->getParent() || !MX.Def1->getParent() || !MX.Def2->getParent())
335  continue;
336 
337  MachineBasicBlock &B = *MX.At->getParent();
338  const DebugLoc &DL = B.findDebugLoc(MX.At);
339  auto NewMux = BuildMI(B, MX.At, DL, HII->get(MxOpc), MX.DefR)
340  .addReg(MX.PredR)
341  .add(*MX.SrcT)
342  .add(*MX.SrcF);
343  NewMux->clearKillInfo();
344  B.remove(MX.Def1);
345  B.remove(MX.Def2);
346  Changed = true;
347  }
348 
349  // Fix up kill flags.
350 
351  LivePhysRegs LPR(*HRI);
352  LPR.addLiveOuts(B);
353  auto IsLive = [&LPR,this] (unsigned Reg) -> bool {
354  for (MCSubRegIterator S(Reg, HRI, true); S.isValid(); ++S)
355  if (LPR.contains(*S))
356  return true;
357  return false;
358  };
359  for (MachineInstr &I : llvm::reverse(B)) {
360  if (I.isDebugInstr())
361  continue;
362  // This isn't 100% accurate, but it's safe.
363  // It won't detect (as a kill) a case like this
364  // r0 = add r0, 1 <-- r0 should be "killed"
365  // ... = r0
366  for (MachineOperand &Op : I.operands()) {
367  if (!Op.isReg() || !Op.isUse())
368  continue;
369  assert(Op.getSubReg() == 0 && "Should have physical registers only");
370  bool Live = IsLive(Op.getReg());
371  Op.setIsKill(!Live);
372  }
373  LPR.stepBackward(I);
374  }
375 
376  return Changed;
377 }
378 
379 bool HexagonGenMux::runOnMachineFunction(MachineFunction &MF) {
380  if (skipFunction(MF.getFunction()))
381  return false;
382  HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
383  HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
384  bool Changed = false;
385  for (auto &I : MF)
386  Changed |= genMuxInBlock(I);
387  return Changed;
388 }
389 
391  return new HexagonGenMux();
392 }
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
MachineInstr.h
MathExtras.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
MCInstrDesc.h
llvm::MachineInstrBuilder::add
const MachineInstrBuilder & add(const MachineOperand &MO) const
Definition: MachineInstrBuilder.h:224
StringRef.h
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
HexagonSubtarget.h
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
llvm::LivePhysRegs
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
DenseMap.h
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:127
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:590
CommandLine.h
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:546
llvm::createHexagonGenMux
FunctionPass * createHexagonGenMux()
Definition: HexagonGenMux.cpp:390
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
llvm::MachineInstr::clearKillInfo
void clearKillInfo()
Clears kill flags on all operands.
Definition: MachineInstr.cpp:1197
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:197
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:196
llvm::PassRegistry
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
BitVector.h
DebugLoc.h
llvm::BitVector
Definition: BitVector.h:75
HexagonInstrInfo.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:657
llvm::cl::opt
Definition: CommandLine.h:1412
INITIALIZE_PASS
INITIALIZE_PASS(HexagonGenMux, "hexagon-gen-mux", "Hexagon generate mux instructions", false, false) void HexagonGenMux
Definition: HexagonGenMux.cpp:143
llvm::MachineOperand::isUndef
bool isUndef() const
Definition: MachineOperand.h:394
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MCPhysReg
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:21
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::make_early_inc_range
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:716
MCRegisterInfo.h
MachineFunctionPass.h
HexagonRegisterInfo.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:97
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::HexagonInstrInfo
Definition: HexagonInstrInfo.h:38
MinPredDist
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"))
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:623
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::initializeHexagonGenMuxPass
void initializeHexagonGenMuxPass(PassRegistry &Registry)
llvm::MachineOperand::isImm
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
Definition: MachineOperand.h:322
llvm::BitVector::reset
BitVector & reset()
Definition: BitVector.h:385
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:597
llvm::Registry
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:357
SmallVector.h
MachineInstrBuilder.h
llvm::remarks::Type::Failure
@ Failure
llvm::HexagonSubtarget
Definition: HexagonSubtarget.h:43
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
MachineOperand.h
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::HexagonRegisterInfo
Definition: HexagonRegisterInfo.h:29
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::cl::desc
Definition: CommandLine.h:413
MachineFunction.h
llvm::MachineInstrBundleIterator< MachineInstr >
LivePhysRegs.h