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