LLVM  10.0.0svn
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 #define DEBUG_TYPE "hexmux"
23 
24 #include "HexagonInstrInfo.h"
25 #include "HexagonRegisterInfo.h"
26 #include "HexagonSubtarget.h"
27 #include "llvm/ADT/BitVector.h"
28 #include "llvm/ADT/DenseMap.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/StringRef.h"
38 #include "llvm/IR/DebugLoc.h"
39 #include "llvm/MC/MCInstrDesc.h"
40 #include "llvm/MC/MCRegisterInfo.h"
41 #include "llvm/Pass.h"
44 #include <algorithm>
45 #include <cassert>
46 #include <iterator>
47 #include <limits>
48 #include <utility>
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 (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; ++I) {
187  MachineInstr *MI = &*I;
188  I2X.insert(std::make_pair(MI, Index));
189  Defs.reset();
190  Uses.reset();
191  getDefsUses(MI, Defs, Uses);
192  DUM.insert(std::make_pair(Index, DefUseInfo(Defs, Uses)));
193  Index++;
194  }
195 }
196 
197 bool HexagonGenMux::isCondTransfer(unsigned Opc) const {
198  switch (Opc) {
199  case Hexagon::A2_tfrt:
200  case Hexagon::A2_tfrf:
201  case Hexagon::C2_cmoveit:
202  case Hexagon::C2_cmoveif:
203  return true;
204  }
205  return false;
206 }
207 
208 unsigned HexagonGenMux::getMuxOpcode(const MachineOperand &Src1,
209  const MachineOperand &Src2) const {
210  bool IsReg1 = Src1.isReg(), IsReg2 = Src2.isReg();
211  if (IsReg1)
212  return IsReg2 ? Hexagon::C2_mux : Hexagon::C2_muxir;
213  if (IsReg2)
214  return Hexagon::C2_muxri;
215 
216  // Neither is a register. The first source is extendable, but the second
217  // is not (s8).
218  if (Src2.isImm() && isInt<8>(Src2.getImm()))
219  return Hexagon::C2_muxii;
220 
221  return 0;
222 }
223 
224 bool HexagonGenMux::genMuxInBlock(MachineBasicBlock &B) {
225  bool Changed = false;
226  InstrIndexMap I2X;
227  DefUseInfoMap DUM;
228  buildMaps(B, I2X, DUM);
229 
230  using CondsetMap = DenseMap<unsigned, CondsetInfo>;
231 
232  CondsetMap CM;
233  MuxInfoList ML;
234 
235  MachineBasicBlock::iterator NextI, End = B.end();
236  for (MachineBasicBlock::iterator I = B.begin(); I != End; I = NextI) {
237  MachineInstr *MI = &*I;
238  NextI = std::next(I);
239  unsigned Opc = MI->getOpcode();
240  if (!isCondTransfer(Opc))
241  continue;
242  Register DR = MI->getOperand(0).getReg();
243  if (isRegPair(DR))
244  continue;
245  MachineOperand &PredOp = MI->getOperand(1);
246  if (PredOp.isUndef())
247  continue;
248 
249  Register PR = PredOp.getReg();
250  unsigned Idx = I2X.lookup(MI);
251  CondsetMap::iterator F = CM.find(DR);
252  bool IfTrue = HII->isPredicatedTrue(Opc);
253 
254  // If there is no record of a conditional transfer for this register,
255  // or the predicate register differs, create a new record for it.
256  if (F != CM.end() && F->second.PredR != PR) {
257  CM.erase(F);
258  F = CM.end();
259  }
260  if (F == CM.end()) {
261  auto It = CM.insert(std::make_pair(DR, CondsetInfo()));
262  F = It.first;
263  F->second.PredR = PR;
264  }
265  CondsetInfo &CI = F->second;
266  if (IfTrue)
267  CI.TrueX = Idx;
268  else
269  CI.FalseX = Idx;
270  if (CI.TrueX == std::numeric_limits<unsigned>::max() ||
271  CI.FalseX == std::numeric_limits<unsigned>::max())
272  continue;
273 
274  // There is now a complete definition of DR, i.e. we have the predicate
275  // register, the definition if-true, and definition if-false.
276 
277  // First, check if the definitions are far enough from the definition
278  // of the predicate register.
279  unsigned MinX = std::min(CI.TrueX, CI.FalseX);
280  unsigned MaxX = std::max(CI.TrueX, CI.FalseX);
281  // Specifically, check if the predicate definition is within a prescribed
282  // distance from the farther of the two predicated instructions.
283  unsigned SearchX = (MaxX >= MinPredDist) ? MaxX-MinPredDist : 0;
284  bool NearDef = false;
285  for (unsigned X = SearchX; X < MaxX; ++X) {
286  const DefUseInfo &DU = DUM.lookup(X);
287  if (!DU.Defs[PR])
288  continue;
289  NearDef = true;
290  break;
291  }
292  if (NearDef)
293  continue;
294 
295  // The predicate register is not defined in the last few instructions.
296  // Check if the conversion to MUX is possible (either "up", i.e. at the
297  // place of the earlier partial definition, or "down", where the later
298  // definition is located). Examine all defs and uses between these two
299  // definitions.
300  // SR1, SR2 - source registers from the first and the second definition.
301  MachineBasicBlock::iterator It1 = B.begin(), It2 = B.begin();
302  std::advance(It1, MinX);
303  std::advance(It2, MaxX);
304  MachineInstr &Def1 = *It1, &Def2 = *It2;
305  MachineOperand *Src1 = &Def1.getOperand(2), *Src2 = &Def2.getOperand(2);
306  Register SR1 = Src1->isReg() ? Src1->getReg() : Register();
307  Register SR2 = Src2->isReg() ? Src2->getReg() : Register();
308  bool Failure = false, CanUp = true, CanDown = true;
309  for (unsigned X = MinX+1; X < MaxX; X++) {
310  const DefUseInfo &DU = DUM.lookup(X);
311  if (DU.Defs[PR] || DU.Defs[DR] || DU.Uses[DR]) {
312  Failure = true;
313  break;
314  }
315  if (CanDown && DU.Defs[SR1])
316  CanDown = false;
317  if (CanUp && DU.Defs[SR2])
318  CanUp = false;
319  }
320  if (Failure || (!CanUp && !CanDown))
321  continue;
322 
323  MachineOperand *SrcT = (MinX == CI.TrueX) ? Src1 : Src2;
324  MachineOperand *SrcF = (MinX == CI.FalseX) ? Src1 : Src2;
325  // Prefer "down", since this will move the MUX farther away from the
326  // predicate definition.
327  MachineBasicBlock::iterator At = CanDown ? Def2 : Def1;
328  ML.push_back(MuxInfo(At, DR, PR, SrcT, SrcF, Def1, Def2));
329  }
330 
331  for (MuxInfo &MX : ML) {
332  unsigned MxOpc = getMuxOpcode(*MX.SrcT, *MX.SrcF);
333  if (!MxOpc)
334  continue;
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.erase(MX.Def1);
343  B.erase(MX.Def2);
344  Changed = true;
345  }
346 
347  // Fix up kill flags.
348 
349  LivePhysRegs LPR(*HRI);
350  LPR.addLiveOuts(B);
351  auto IsLive = [&LPR,this] (unsigned Reg) -> bool {
352  for (MCSubRegIterator S(Reg, HRI, true); S.isValid(); ++S)
353  if (LPR.contains(*S))
354  return true;
355  return false;
356  };
357  for (auto I = B.rbegin(), E = B.rend(); I != E; ++I) {
358  if (I->isDebugInstr())
359  continue;
360  // This isn't 100% accurate, but it's safe.
361  // It won't detect (as a kill) a case like this
362  // r0 = add r0, 1 <-- r0 should be "killed"
363  // ... = r0
364  for (MachineOperand &Op : I->operands()) {
365  if (!Op.isReg() || !Op.isUse())
366  continue;
367  assert(Op.getSubReg() == 0 && "Should have physical registers only");
368  bool Live = IsLive(Op.getReg());
369  Op.setIsKill(!Live);
370  }
371  LPR.stepBackward(*I);
372  }
373 
374  return Changed;
375 }
376 
377 bool HexagonGenMux::runOnMachineFunction(MachineFunction &MF) {
378  if (skipFunction(MF.getFunction()))
379  return false;
380  HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
381  HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
382  bool Changed = false;
383  for (auto &I : MF)
384  Changed |= genMuxInBlock(I);
385  return Changed;
386 }
387 
389  return new HexagonGenMux();
390 }
const MachineInstrBuilder & add(const MachineOperand &MO) const
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:178
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
unsigned Reg
constexpr bool isInt< 8 >(int64_t x)
Definition: MathExtras.h:302
A debug info location.
Definition: DebugLoc.h:33
F(f)
INITIALIZE_PASS(HexagonGenMux, "hexagon-gen-mux", "Hexagon generate mux instructions", false, false) void HexagonGenMux
bool contains(MCPhysReg Reg) const
Returns true if register Reg is contained in the set.
Definition: LivePhysRegs.h:106
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:477
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
void clearKillInfo()
Clears kill flags on all operands.
void initializeHexagonGenMuxPass(PassRegistry &Registry)
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
reverse_iterator rend()
reverse_iterator rbegin()
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:19
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1165
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions...
const MCPhysReg * ImplicitDefs
Definition: MCInstrDesc.h:188
Represent the analysis usage information of a pass.
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
BitVector & reset()
Definition: BitVector.h:438
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
MCSubRegIterator enumerates all sub-registers of Reg.
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
FunctionPass * createHexagonGenMux()
Promote Memory to Register
Definition: Mem2Reg.cpp:109
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
int64_t getImm() const
const Function & getFunction() const
Return the LLVM function that this machine code represents.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:64
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:48
#define I(x, y, z)
Definition: MD5.cpp:58
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
Register getReg() const
getReg - Returns the register number.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
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"))
Properties which a MachineFunction may have at a given point in time.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
const MCPhysReg * ImplicitUses
Definition: MCInstrDesc.h:187