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