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