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 
38 using namespace llvm;
39 using namespace rdf;
40 
41 namespace llvm {
42 
43   void initializeHexagonRDFOptPass(PassRegistry&);
44   FunctionPass *createHexagonRDFOpt();
45 
46 } // end namespace llvm
47 
48 static unsigned RDFCount = 0;
49 
50 static cl::opt<unsigned> RDFLimit("rdf-limit",
51     cl::init(std::numeric_limits<unsigned>::max()));
52 static cl::opt<bool> RDFDump("rdf-dump", cl::init(false));
53 
54 namespace {
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 
85 struct HexagonCP : public CopyPropagation {
86   HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {}
87 
88   bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override;
89 };
90 
91 struct 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 
103 char HexagonRDFOpt::ID = 0;
104 
105 INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt",
106       "Hexagon RDF optimizations", false, false)
107 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
108 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
109 INITIALIZE_PASS_END(HexagonRDFOpt, "hexagon-rdf-opt",
110       "Hexagon RDF optimizations", false, false)
111 
112 bool 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 
149 bool 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 
189 void 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 
215 bool 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 
282 bool 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 
339 FunctionPass *llvm::createHexagonRDFOpt() {
340   return new HexagonRDFOpt();
341 }
342