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