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 "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"
20 #include "llvm/CodeGen/MachineDominanceFrontier.h"
21 #include "llvm/CodeGen/MachineDominators.h"
22 #include "llvm/CodeGen/MachineFunction.h"
23 #include "llvm/CodeGen/MachineFunctionPass.h"
24 #include "llvm/CodeGen/MachineInstr.h"
25 #include "llvm/CodeGen/MachineOperand.h"
26 #include "llvm/CodeGen/MachineRegisterInfo.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Support/CommandLine.h"
29 #include "llvm/Support/Compiler.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/ErrorHandling.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include <cassert>
34 #include <limits>
35 #include <utility>
36 
37 using namespace llvm;
38 using namespace rdf;
39 
40 namespace llvm {
41 
42   void initializeHexagonRDFOptPass(PassRegistry&);
43   FunctionPass *createHexagonRDFOpt();
44 
45 } // end namespace llvm
46 
47 static unsigned RDFCount = 0;
48 
49 static cl::opt<unsigned> RDFLimit("rdf-limit",
50     cl::init(std::numeric_limits<unsigned>::max()));
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 {
60       AU.addRequired<MachineDominatorTree>();
61       AU.addRequired<MachineDominanceFrontier>();
62       AU.setPreservesAll();
63       MachineFunctionPass::getAnalysisUsage(AU);
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 {
73       return MachineFunctionProperties().set(
74           MachineFunctionProperties::Property::NoVRegs);
75     }
76 
77     static char ID;
78 
79   private:
80     MachineDominatorTree *MDT;
81     MachineRegisterInfo *MRI;
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 
94   bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove);
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)
106 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
107 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
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;
134       LLVM_FALLTHROUGH;
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   };
197   DenseMap<NodeId,unsigned> OpMap;
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 
214 bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) {
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.
306   G.build(BuildOptions::KeepDeadPhis);
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 
338 FunctionPass *llvm::createHexagonRDFOpt() {
339   return new HexagonRDFOpt();
340 }
341