LLVM  10.0.0svn
HexagonRDFOpt.cpp
Go to the documentation of this file.
1 //===- HexagonRDFOpt.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 #include "HexagonInstrInfo.h"
10 #include "HexagonSubtarget.h"
12 #include "RDFCopy.h"
13 #include "RDFDeadCode.h"
14 #include "RDFGraph.h"
15 #include "RDFLiveness.h"
16 #include "RDFRegisters.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SetVector.h"
27 #include "llvm/Pass.h"
29 #include "llvm/Support/Compiler.h"
30 #include "llvm/Support/Debug.h"
33 #include <cassert>
34 #include <limits>
35 #include <utility>
36 
37 using namespace llvm;
38 using namespace rdf;
39 
40 namespace llvm {
41 
44 
45 } // end namespace llvm
46 
47 static unsigned RDFCount = 0;
48 
49 static cl::opt<unsigned> RDFLimit("rdf-limit",
51 static cl::opt<bool> RDFDump("rdf-dump", cl::init(false));
52 
53 namespace {
54 
55  class HexagonRDFOpt : public MachineFunctionPass {
56  public:
57  HexagonRDFOpt() : MachineFunctionPass(ID) {}
58 
59  void getAnalysisUsage(AnalysisUsage &AU) const override {
62  AU.setPreservesAll();
64  }
65 
66  StringRef getPassName() const override {
67  return "Hexagon RDF optimizations";
68  }
69 
70  bool runOnMachineFunction(MachineFunction &MF) override;
71 
72  MachineFunctionProperties getRequiredProperties() const override {
75  }
76 
77  static char ID;
78 
79  private:
82  };
83 
84 struct HexagonCP : public CopyPropagation {
85  HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {}
86 
87  bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override;
88 };
89 
90 struct HexagonDCE : public DeadCodeElimination {
91  HexagonDCE(DataFlowGraph &G, MachineRegisterInfo &MRI)
92  : DeadCodeElimination(G, MRI) {}
93 
95  void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum);
96 
97  bool run();
98 };
99 
100 } // end anonymous namespace
101 
102 char HexagonRDFOpt::ID = 0;
103 
104 INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt",
105  "Hexagon RDF optimizations", false, false)
108 INITIALIZE_PASS_END(HexagonRDFOpt, "hexagon-rdf-opt",
109  "Hexagon RDF optimizations", false, false)
110 
111 bool HexagonCP::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
112  auto mapRegs = [&EM] (RegisterRef DstR, RegisterRef SrcR) -> void {
113  EM.insert(std::make_pair(DstR, SrcR));
114  };
115 
116  DataFlowGraph &DFG = getDFG();
117  unsigned Opc = MI->getOpcode();
118  switch (Opc) {
119  case Hexagon::A2_combinew: {
120  const MachineOperand &DstOp = MI->getOperand(0);
121  const MachineOperand &HiOp = MI->getOperand(1);
122  const MachineOperand &LoOp = MI->getOperand(2);
123  assert(DstOp.getSubReg() == 0 && "Unexpected subregister");
124  mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_hi),
125  DFG.makeRegRef(HiOp.getReg(), HiOp.getSubReg()));
126  mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_lo),
127  DFG.makeRegRef(LoOp.getReg(), LoOp.getSubReg()));
128  return true;
129  }
130  case Hexagon::A2_addi: {
131  const MachineOperand &A = MI->getOperand(2);
132  if (!A.isImm() || A.getImm() != 0)
133  return false;
135  }
136  case Hexagon::A2_tfr: {
137  const MachineOperand &DstOp = MI->getOperand(0);
138  const MachineOperand &SrcOp = MI->getOperand(1);
139  mapRegs(DFG.makeRegRef(DstOp.getReg(), DstOp.getSubReg()),
140  DFG.makeRegRef(SrcOp.getReg(), SrcOp.getSubReg()));
141  return true;
142  }
143  }
144 
145  return CopyPropagation::interpretAsCopy(MI, EM);
146 }
147 
148 bool HexagonDCE::run() {
149  bool Collected = collect();
150  if (!Collected)
151  return false;
152 
153  const SetVector<NodeId> &DeadNodes = getDeadNodes();
154  const SetVector<NodeId> &DeadInstrs = getDeadInstrs();
155 
156  using RefToInstrMap = DenseMap<NodeId, NodeId>;
157 
158  RefToInstrMap R2I;
159  SetVector<NodeId> PartlyDead;
160  DataFlowGraph &DFG = getDFG();
161 
162  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
163  for (auto TA : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Stmt>, DFG)) {
164  NodeAddr<StmtNode*> SA = TA;
165  for (NodeAddr<RefNode*> RA : SA.Addr->members(DFG)) {
166  R2I.insert(std::make_pair(RA.Id, SA.Id));
167  if (DFG.IsDef(RA) && DeadNodes.count(RA.Id))
168  if (!DeadInstrs.count(SA.Id))
169  PartlyDead.insert(SA.Id);
170  }
171  }
172  }
173 
174  // Nodes to remove.
175  SetVector<NodeId> Remove = DeadInstrs;
176 
177  bool Changed = false;
178  for (NodeId N : PartlyDead) {
179  auto SA = DFG.addr<StmtNode*>(N);
180  if (trace())
181  dbgs() << "Partly dead: " << *SA.Addr->getCode();
182  Changed |= rewrite(SA, Remove);
183  }
184 
185  return erase(Remove) || Changed;
186 }
187 
188 void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) {
189  MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
190 
191  auto getOpNum = [MI] (MachineOperand &Op) -> unsigned {
192  for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i)
193  if (&MI->getOperand(i) == &Op)
194  return i;
195  llvm_unreachable("Invalid operand");
196  };
198  DataFlowGraph &DFG = getDFG();
199  NodeList Refs = IA.Addr->members(DFG);
200  for (NodeAddr<RefNode*> RA : Refs)
201  OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp())));
202 
203  MI->RemoveOperand(OpNum);
204 
205  for (NodeAddr<RefNode*> RA : Refs) {
206  unsigned N = OpMap[RA.Id];
207  if (N < OpNum)
208  RA.Addr->setRegRef(&MI->getOperand(N), DFG);
209  else if (N > OpNum)
210  RA.Addr->setRegRef(&MI->getOperand(N-1), DFG);
211  }
212 }
213 
215  if (!getDFG().IsCode<NodeAttrs::Stmt>(IA))
216  return false;
217  DataFlowGraph &DFG = getDFG();
218  MachineInstr &MI = *NodeAddr<StmtNode*>(IA).Addr->getCode();
219  auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII());
220  if (HII.getAddrMode(MI) != HexagonII::PostInc)
221  return false;
222  unsigned Opc = MI.getOpcode();
223  unsigned OpNum, NewOpc;
224  switch (Opc) {
225  case Hexagon::L2_loadri_pi:
226  NewOpc = Hexagon::L2_loadri_io;
227  OpNum = 1;
228  break;
229  case Hexagon::L2_loadrd_pi:
230  NewOpc = Hexagon::L2_loadrd_io;
231  OpNum = 1;
232  break;
233  case Hexagon::V6_vL32b_pi:
234  NewOpc = Hexagon::V6_vL32b_ai;
235  OpNum = 1;
236  break;
237  case Hexagon::S2_storeri_pi:
238  NewOpc = Hexagon::S2_storeri_io;
239  OpNum = 0;
240  break;
241  case Hexagon::S2_storerd_pi:
242  NewOpc = Hexagon::S2_storerd_io;
243  OpNum = 0;
244  break;
245  case Hexagon::V6_vS32b_pi:
246  NewOpc = Hexagon::V6_vS32b_ai;
247  OpNum = 0;
248  break;
249  default:
250  return false;
251  }
252  auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool {
253  return getDeadNodes().count(DA.Id);
254  };
255  NodeList Defs;
256  MachineOperand &Op = MI.getOperand(OpNum);
257  for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) {
258  if (&DA.Addr->getOp() != &Op)
259  continue;
260  Defs = DFG.getRelatedRefs(IA, DA);
261  if (!llvm::all_of(Defs, IsDead))
262  return false;
263  break;
264  }
265 
266  // Mark all nodes in Defs for removal.
267  for (auto D : Defs)
268  Remove.insert(D.Id);
269 
270  if (trace())
271  dbgs() << "Rewriting: " << MI;
272  MI.setDesc(HII.get(NewOpc));
273  MI.getOperand(OpNum+2).setImm(0);
274  removeOperand(IA, OpNum);
275  if (trace())
276  dbgs() << " to: " << MI;
277 
278  return true;
279 }
280 
281 bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) {
282  if (skipFunction(MF.getFunction()))
283  return false;
284 
285  if (RDFLimit.getPosition()) {
286  if (RDFCount >= RDFLimit)
287  return false;
288  RDFCount++;
289  }
290 
291  MDT = &getAnalysis<MachineDominatorTree>();
292  const auto &MDF = getAnalysis<MachineDominanceFrontier>();
293  const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
294  const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
295  MRI = &MF.getRegInfo();
296  bool Changed;
297 
298  if (RDFDump)
299  MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr);
300 
301  TargetOperandInfo TOI(HII);
302  DataFlowGraph G(MF, HII, HRI, *MDT, MDF, TOI);
303  // Dead phi nodes are necessary for copy propagation: we can add a use
304  // of a register in a block where it would need a phi node, but which
305  // was dead (and removed) during the graph build time.
307 
308  if (RDFDump)
309  dbgs() << "Starting copy propagation on: " << MF.getName() << '\n'
310  << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
311  HexagonCP CP(G);
312  CP.trace(RDFDump);
313  Changed = CP.run();
314 
315  if (RDFDump)
316  dbgs() << "Starting dead code elimination on: " << MF.getName() << '\n'
317  << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
318  HexagonDCE DCE(G, *MRI);
319  DCE.trace(RDFDump);
320  Changed |= DCE.run();
321 
322  if (Changed) {
323  if (RDFDump)
324  dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n';
325  Liveness LV(*MRI, G);
326  LV.trace(RDFDump);
327  LV.computeLiveIns();
328  LV.resetLiveIns();
329  LV.resetKills();
330  }
331 
332  if (RDFDump)
333  MF.print(dbgs() << "After " << getPassName() << "\n", nullptr);
334 
335  return false;
336 }
337 
339  return new HexagonRDFOpt();
340 }
void initializeHexagonRDFOptPass(PassRegistry &)
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
bool IsDead
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getSubReg() const
uint32_t NodeId
Definition: RDFGraph.h:260
INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt", "Hexagon RDF optimizations", false, false) INITIALIZE_PASS_END(HexagonRDFOpt
hexagon rdf opt
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1165
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
static cl::opt< unsigned > RDFLimit("rdf-limit", cl::init(std::numeric_limits< unsigned >::max()))
const TargetInstrInfo & getTII() const
Definition: RDFGraph.h:662
SI optimize exec mask operations pre RA
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:195
NodeAddr< FuncNode * > getFunc() const
Definition: RDFGraph.h:660
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
void trace(bool T)
Definition: RDFLiveness.h:97
RegisterRef makeRegRef(unsigned Reg, unsigned Sub) const
Definition: RDFGraph.cpp:964
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:210
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
static unsigned RDFCount
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
unsigned const MachineRegisterInfo * MRI
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.
NodeAddr< T > addr(NodeId N) const
Definition: RDFGraph.h:656
Represent the analysis usage information of a pass.
NodeList getRelatedRefs(NodeAddr< InstrNode *> IA, NodeAddr< RefNode *> RA) const
Definition: RDFGraph.cpp:1128
void setImm(int64_t immVal)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:913
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:527
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
virtual bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM)
Definition: RDFCopy.cpp:40
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
FunctionPass * createHexagonRDFOpt()
static cl::opt< bool > RDFDump("rdf-dump", cl::init(false))
MachineOperand class - Representation of each machine instruction operand.
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
hexagon rdf Hexagon RDF optimizations
int64_t getImm() const
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void setPreservesAll()
Set by analyses that do not transform their input at all.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:64
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
#define N
void build(unsigned Options=BuildOptions::None)
Definition: RDFGraph.cpp:866
static bool IsCode(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:792
static bool rewrite(Function &F)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
aarch64 promote const
A vector that has set insertion semantics.
Definition: SetVector.h:40
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:265
static bool IsDef(const NodeAddr< NodeBase *> BA)
Definition: RDFGraph.h:797
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
void RemoveOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with...
Register getReg() const
getReg - Returns the register number.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Properties which a MachineFunction may have at a given point in time.