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