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