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