HexagonRDFOpt.cpp revision 363496 
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"
11#include "MCTargetDesc/HexagonBaseInfo.h"
12#include "RDFCopy.h"
13#include "RDFDeadCode.h"
14#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SetVector.h"
17#include "llvm/CodeGen/MachineDominanceFrontier.h"
18#include "llvm/CodeGen/MachineDominators.h"
19#include "llvm/CodeGen/MachineFunction.h"
20#include "llvm/CodeGen/MachineFunctionPass.h"
21#include "llvm/CodeGen/MachineInstr.h"
22#include "llvm/CodeGen/MachineOperand.h"
23#include "llvm/CodeGen/MachineRegisterInfo.h"
24#include "llvm/CodeGen/RDFGraph.h"
25#include "llvm/CodeGen/RDFLiveness.h"
26#include "llvm/CodeGen/RDFRegisters.h"
27#include "llvm/InitializePasses.h"
28#include "llvm/Pass.h"
29#include "llvm/Support/CommandLine.h"
30#include "llvm/Support/Compiler.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/ErrorHandling.h"
33#include "llvm/Support/raw_ostream.h"
34#include <cassert>
35#include <limits>
36#include <utility>
37
38using namespace llvm;
39using namespace rdf;
40
41namespace llvm {
42
43  void initializeHexagonRDFOptPass(PassRegistry&);
44  FunctionPass *createHexagonRDFOpt();
45
46} // end namespace llvm
47
48static unsigned RDFCount = 0;
49
50static cl::opt<unsigned> RDFLimit("rdf-limit",
51    cl::init(std::numeric_limits<unsigned>::max()));
52static cl::opt<bool> RDFDump("rdf-dump", cl::init(false));
53
54namespace {
55
56  class HexagonRDFOpt : public MachineFunctionPass {
57  public:
58    HexagonRDFOpt() : MachineFunctionPass(ID) {}
59
60    void getAnalysisUsage(AnalysisUsage &AU) const override {
61      AU.addRequired<MachineDominatorTree>();
62      AU.addRequired<MachineDominanceFrontier>();
63      AU.setPreservesAll();
64      MachineFunctionPass::getAnalysisUsage(AU);
65    }
66
67    StringRef getPassName() const override {
68      return "Hexagon RDF optimizations";
69    }
70
71    bool runOnMachineFunction(MachineFunction &MF) override;
72
73    MachineFunctionProperties getRequiredProperties() const override {
74      return MachineFunctionProperties().set(
75          MachineFunctionProperties::Property::NoVRegs);
76    }
77
78    static char ID;
79
80  private:
81    MachineDominatorTree *MDT;
82    MachineRegisterInfo *MRI;
83  };
84
85struct HexagonCP : public CopyPropagation {
86  HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {}
87
88  bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override;
89};
90
91struct HexagonDCE : public DeadCodeElimination {
92  HexagonDCE(DataFlowGraph &G, MachineRegisterInfo &MRI)
93    : DeadCodeElimination(G, MRI) {}
94
95  bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove);
96  void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum);
97
98  bool run();
99};
100
101} // end anonymous namespace
102
103char HexagonRDFOpt::ID = 0;
104
105INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt",
106      "Hexagon RDF optimizations", false, false)
107INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
108INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
109INITIALIZE_PASS_END(HexagonRDFOpt, "hexagon-rdf-opt",
110      "Hexagon RDF optimizations", false, false)
111
112bool HexagonCP::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
113  auto mapRegs = [&EM] (RegisterRef DstR, RegisterRef SrcR) -> void {
114    EM.insert(std::make_pair(DstR, SrcR));
115  };
116
117  DataFlowGraph &DFG = getDFG();
118  unsigned Opc = MI->getOpcode();
119  switch (Opc) {
120    case Hexagon::A2_combinew: {
121      const MachineOperand &DstOp = MI->getOperand(0);
122      const MachineOperand &HiOp = MI->getOperand(1);
123      const MachineOperand &LoOp = MI->getOperand(2);
124      assert(DstOp.getSubReg() == 0 && "Unexpected subregister");
125      mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_hi),
126              DFG.makeRegRef(HiOp.getReg(),  HiOp.getSubReg()));
127      mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_lo),
128              DFG.makeRegRef(LoOp.getReg(), LoOp.getSubReg()));
129      return true;
130    }
131    case Hexagon::A2_addi: {
132      const MachineOperand &A = MI->getOperand(2);
133      if (!A.isImm() || A.getImm() != 0)
134        return false;
135      LLVM_FALLTHROUGH;
136    }
137    case Hexagon::A2_tfr: {
138      const MachineOperand &DstOp = MI->getOperand(0);
139      const MachineOperand &SrcOp = MI->getOperand(1);
140      mapRegs(DFG.makeRegRef(DstOp.getReg(), DstOp.getSubReg()),
141              DFG.makeRegRef(SrcOp.getReg(), SrcOp.getSubReg()));
142      return true;
143    }
144  }
145
146  return CopyPropagation::interpretAsCopy(MI, EM);
147}
148
149bool HexagonDCE::run() {
150  bool Collected = collect();
151  if (!Collected)
152    return false;
153
154  const SetVector<NodeId> &DeadNodes = getDeadNodes();
155  const SetVector<NodeId> &DeadInstrs = getDeadInstrs();
156
157  using RefToInstrMap = DenseMap<NodeId, NodeId>;
158
159  RefToInstrMap R2I;
160  SetVector<NodeId> PartlyDead;
161  DataFlowGraph &DFG = getDFG();
162
163  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
164    for (auto TA : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Stmt>, DFG)) {
165      NodeAddr<StmtNode*> SA = TA;
166      for (NodeAddr<RefNode*> RA : SA.Addr->members(DFG)) {
167        R2I.insert(std::make_pair(RA.Id, SA.Id));
168        if (DFG.IsDef(RA) && DeadNodes.count(RA.Id))
169          if (!DeadInstrs.count(SA.Id))
170            PartlyDead.insert(SA.Id);
171      }
172    }
173  }
174
175  // Nodes to remove.
176  SetVector<NodeId> Remove = DeadInstrs;
177
178  bool Changed = false;
179  for (NodeId N : PartlyDead) {
180    auto SA = DFG.addr<StmtNode*>(N);
181    if (trace())
182      dbgs() << "Partly dead: " << *SA.Addr->getCode();
183    Changed |= rewrite(SA, Remove);
184  }
185
186  return erase(Remove) || Changed;
187}
188
189void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) {
190  MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
191
192  auto getOpNum = [MI] (MachineOperand &Op) -> unsigned {
193    for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i)
194      if (&MI->getOperand(i) == &Op)
195        return i;
196    llvm_unreachable("Invalid operand");
197  };
198  DenseMap<NodeId,unsigned> OpMap;
199  DataFlowGraph &DFG = getDFG();
200  NodeList Refs = IA.Addr->members(DFG);
201  for (NodeAddr<RefNode*> RA : Refs)
202    OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp())));
203
204  MI->RemoveOperand(OpNum);
205
206  for (NodeAddr<RefNode*> RA : Refs) {
207    unsigned N = OpMap[RA.Id];
208    if (N < OpNum)
209      RA.Addr->setRegRef(&MI->getOperand(N), DFG);
210    else if (N > OpNum)
211      RA.Addr->setRegRef(&MI->getOperand(N-1), DFG);
212  }
213}
214
215bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) {
216  if (!getDFG().IsCode<NodeAttrs::Stmt>(IA))
217    return false;
218  DataFlowGraph &DFG = getDFG();
219  MachineInstr &MI = *NodeAddr<StmtNode*>(IA).Addr->getCode();
220  auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII());
221  if (HII.getAddrMode(MI) != HexagonII::PostInc)
222    return false;
223  unsigned Opc = MI.getOpcode();
224  unsigned OpNum, NewOpc;
225  switch (Opc) {
226    case Hexagon::L2_loadri_pi:
227      NewOpc = Hexagon::L2_loadri_io;
228      OpNum = 1;
229      break;
230    case Hexagon::L2_loadrd_pi:
231      NewOpc = Hexagon::L2_loadrd_io;
232      OpNum = 1;
233      break;
234    case Hexagon::V6_vL32b_pi:
235      NewOpc = Hexagon::V6_vL32b_ai;
236      OpNum = 1;
237      break;
238    case Hexagon::S2_storeri_pi:
239      NewOpc = Hexagon::S2_storeri_io;
240      OpNum = 0;
241      break;
242    case Hexagon::S2_storerd_pi:
243      NewOpc = Hexagon::S2_storerd_io;
244      OpNum = 0;
245      break;
246    case Hexagon::V6_vS32b_pi:
247      NewOpc = Hexagon::V6_vS32b_ai;
248      OpNum = 0;
249      break;
250    default:
251      return false;
252  }
253  auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool {
254    return getDeadNodes().count(DA.Id);
255  };
256  NodeList Defs;
257  MachineOperand &Op = MI.getOperand(OpNum);
258  for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) {
259    if (&DA.Addr->getOp() != &Op)
260      continue;
261    Defs = DFG.getRelatedRefs(IA, DA);
262    if (!llvm::all_of(Defs, IsDead))
263      return false;
264    break;
265  }
266
267  // Mark all nodes in Defs for removal.
268  for (auto D : Defs)
269    Remove.insert(D.Id);
270
271  if (trace())
272    dbgs() << "Rewriting: " << MI;
273  MI.setDesc(HII.get(NewOpc));
274  MI.getOperand(OpNum+2).setImm(0);
275  removeOperand(IA, OpNum);
276  if (trace())
277    dbgs() << "       to: " << MI;
278
279  return true;
280}
281
282bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) {
283  if (skipFunction(MF.getFunction()))
284    return false;
285
286  if (RDFLimit.getPosition()) {
287    if (RDFCount >= RDFLimit)
288      return false;
289    RDFCount++;
290  }
291
292  MDT = &getAnalysis<MachineDominatorTree>();
293  const auto &MDF = getAnalysis<MachineDominanceFrontier>();
294  const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
295  const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
296  MRI = &MF.getRegInfo();
297  bool Changed;
298
299  if (RDFDump)
300    MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr);
301
302  TargetOperandInfo TOI(HII);
303  DataFlowGraph G(MF, HII, HRI, *MDT, MDF, TOI);
304  // Dead phi nodes are necessary for copy propagation: we can add a use
305  // of a register in a block where it would need a phi node, but which
306  // was dead (and removed) during the graph build time.
307  G.build(BuildOptions::KeepDeadPhis);
308
309  if (RDFDump)
310    dbgs() << "Starting copy propagation on: " << MF.getName() << '\n'
311           << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
312  HexagonCP CP(G);
313  CP.trace(RDFDump);
314  Changed = CP.run();
315
316  if (RDFDump)
317    dbgs() << "Starting dead code elimination on: " << MF.getName() << '\n'
318           << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
319  HexagonDCE DCE(G, *MRI);
320  DCE.trace(RDFDump);
321  Changed |= DCE.run();
322
323  if (Changed) {
324    if (RDFDump)
325      dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n';
326    Liveness LV(*MRI, G);
327    LV.trace(RDFDump);
328    LV.computeLiveIns();
329    LV.resetLiveIns();
330    LV.resetKills();
331  }
332
333  if (RDFDump)
334    MF.print(dbgs() << "After " << getPassName() << "\n", nullptr);
335
336  return false;
337}
338
339FunctionPass *llvm::createHexagonRDFOpt() {
340  return new HexagonRDFOpt();
341}
342