1 //===- HexagonRDFOpt.cpp --------------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 #include "HexagonInstrInfo.h"
10 #include "HexagonSubtarget.h"
11 #include "MCTargetDesc/HexagonBaseInfo.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"
43 void initializeHexagonRDFOptPass(PassRegistry&);
44 FunctionPass *createHexagonRDFOpt();
46 } // end namespace llvm
48 static unsigned RDFCount = 0;
50 static cl::opt<unsigned>
51 RDFLimit("hexagon-rdf-limit",
52 cl::init(std::numeric_limits<unsigned>::max()));
53 static cl::opt<bool> RDFDump("hexagon-rdf-dump", cl::Hidden);
54 static cl::opt<bool> RDFTrackReserved("hexagon-rdf-track-reserved", cl::Hidden);
58 class HexagonRDFOpt : public MachineFunctionPass {
60 HexagonRDFOpt() : MachineFunctionPass(ID) {}
62 void getAnalysisUsage(AnalysisUsage &AU) const override {
63 AU.addRequired<MachineDominatorTree>();
64 AU.addRequired<MachineDominanceFrontier>();
66 MachineFunctionPass::getAnalysisUsage(AU);
69 StringRef getPassName() const override {
70 return "Hexagon RDF optimizations";
73 bool runOnMachineFunction(MachineFunction &MF) override;
75 MachineFunctionProperties getRequiredProperties() const override {
76 return MachineFunctionProperties().set(
77 MachineFunctionProperties::Property::NoVRegs);
83 MachineDominatorTree *MDT;
84 MachineRegisterInfo *MRI;
87 struct HexagonCP : public CopyPropagation {
88 HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {}
90 bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override;
93 struct HexagonDCE : public DeadCodeElimination {
94 HexagonDCE(DataFlowGraph &G, MachineRegisterInfo &MRI)
95 : DeadCodeElimination(G, MRI) {}
97 bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove);
98 void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum);
103 } // end anonymous namespace
105 char HexagonRDFOpt::ID = 0;
107 INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt",
108 "Hexagon RDF optimizations", false, false)
109 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
110 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
111 INITIALIZE_PASS_END(HexagonRDFOpt, "hexagon-rdf-opt",
112 "Hexagon RDF optimizations", false, false)
114 bool HexagonCP::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
115 auto mapRegs = [&EM] (RegisterRef DstR, RegisterRef SrcR) -> void {
116 EM.insert(std::make_pair(DstR, SrcR));
119 DataFlowGraph &DFG = getDFG();
120 unsigned Opc = MI->getOpcode();
122 case Hexagon::A2_combinew: {
123 const MachineOperand &DstOp = MI->getOperand(0);
124 const MachineOperand &HiOp = MI->getOperand(1);
125 const MachineOperand &LoOp = MI->getOperand(2);
126 assert(DstOp.getSubReg() == 0 && "Unexpected subregister");
127 mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_hi),
128 DFG.makeRegRef(HiOp.getReg(), HiOp.getSubReg()));
129 mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_lo),
130 DFG.makeRegRef(LoOp.getReg(), LoOp.getSubReg()));
133 case Hexagon::A2_addi: {
134 const MachineOperand &A = MI->getOperand(2);
135 if (!A.isImm() || A.getImm() != 0)
139 case Hexagon::A2_tfr: {
140 const MachineOperand &DstOp = MI->getOperand(0);
141 const MachineOperand &SrcOp = MI->getOperand(1);
142 mapRegs(DFG.makeRegRef(DstOp.getReg(), DstOp.getSubReg()),
143 DFG.makeRegRef(SrcOp.getReg(), SrcOp.getSubReg()));
148 return CopyPropagation::interpretAsCopy(MI, EM);
151 bool HexagonDCE::run() {
152 bool Collected = collect();
156 const SetVector<NodeId> &DeadNodes = getDeadNodes();
157 const SetVector<NodeId> &DeadInstrs = getDeadInstrs();
159 using RefToInstrMap = DenseMap<NodeId, NodeId>;
162 SetVector<NodeId> PartlyDead;
163 DataFlowGraph &DFG = getDFG();
165 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
166 for (auto TA : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Stmt>, DFG)) {
167 NodeAddr<StmtNode*> SA = TA;
168 for (NodeAddr<RefNode*> RA : SA.Addr->members(DFG)) {
169 R2I.insert(std::make_pair(RA.Id, SA.Id));
170 if (DFG.IsDef(RA) && DeadNodes.count(RA.Id))
171 if (!DeadInstrs.count(SA.Id))
172 PartlyDead.insert(SA.Id);
178 SetVector<NodeId> Remove = DeadInstrs;
180 bool Changed = false;
181 for (NodeId N : PartlyDead) {
182 auto SA = DFG.addr<StmtNode*>(N);
184 dbgs() << "Partly dead: " << *SA.Addr->getCode();
185 Changed |= rewrite(SA, Remove);
188 return erase(Remove) || Changed;
191 void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) {
192 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
194 auto getOpNum = [MI] (MachineOperand &Op) -> unsigned {
195 for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i)
196 if (&MI->getOperand(i) == &Op)
198 llvm_unreachable("Invalid operand");
200 DenseMap<NodeId,unsigned> OpMap;
201 DataFlowGraph &DFG = getDFG();
202 NodeList Refs = IA.Addr->members(DFG);
203 for (NodeAddr<RefNode*> RA : Refs)
204 OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp())));
206 MI->removeOperand(OpNum);
208 for (NodeAddr<RefNode*> RA : Refs) {
209 unsigned N = OpMap[RA.Id];
211 RA.Addr->setRegRef(&MI->getOperand(N), DFG);
213 RA.Addr->setRegRef(&MI->getOperand(N-1), DFG);
217 bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) {
218 if (!getDFG().IsCode<NodeAttrs::Stmt>(IA))
220 DataFlowGraph &DFG = getDFG();
221 MachineInstr &MI = *NodeAddr<StmtNode*>(IA).Addr->getCode();
222 auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII());
223 if (HII.getAddrMode(MI) != HexagonII::PostInc)
225 unsigned Opc = MI.getOpcode();
226 unsigned OpNum, NewOpc;
228 case Hexagon::L2_loadri_pi:
229 NewOpc = Hexagon::L2_loadri_io;
232 case Hexagon::L2_loadrd_pi:
233 NewOpc = Hexagon::L2_loadrd_io;
236 case Hexagon::V6_vL32b_pi:
237 NewOpc = Hexagon::V6_vL32b_ai;
240 case Hexagon::S2_storeri_pi:
241 NewOpc = Hexagon::S2_storeri_io;
244 case Hexagon::S2_storerd_pi:
245 NewOpc = Hexagon::S2_storerd_io;
248 case Hexagon::V6_vS32b_pi:
249 NewOpc = Hexagon::V6_vS32b_ai;
255 auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool {
256 return getDeadNodes().count(DA.Id);
259 MachineOperand &Op = MI.getOperand(OpNum);
260 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) {
261 if (&DA.Addr->getOp() != &Op)
263 Defs = DFG.getRelatedRefs(IA, DA);
264 if (!llvm::all_of(Defs, IsDead))
269 // Mark all nodes in Defs for removal.
274 dbgs() << "Rewriting: " << MI;
275 MI.setDesc(HII.get(NewOpc));
276 MI.getOperand(OpNum+2).setImm(0);
277 removeOperand(IA, OpNum);
279 dbgs() << " to: " << MI;
284 bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) {
285 if (skipFunction(MF.getFunction()))
288 if (RDFLimit.getPosition()) {
289 if (RDFCount >= RDFLimit)
294 MDT = &getAnalysis<MachineDominatorTree>();
295 const auto &MDF = getAnalysis<MachineDominanceFrontier>();
296 const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
297 const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
298 MRI = &MF.getRegInfo();
302 MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr);
304 DataFlowGraph G(MF, HII, HRI, *MDT, MDF);
305 // Dead phi nodes are necessary for copy propagation: we can add a use
306 // of a register in a block where it would need a phi node, but which
307 // was dead (and removed) during the graph build time.
308 DataFlowGraph::Config Cfg;
309 Cfg.Options = RDFTrackReserved
310 ? BuildOptions::KeepDeadPhis
311 : BuildOptions::KeepDeadPhis | BuildOptions::OmitReserved;
315 dbgs() << "Starting copy propagation on: " << MF.getName() << '\n'
316 << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
322 dbgs() << "Starting dead code elimination on: " << MF.getName() << '\n'
323 << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
324 HexagonDCE DCE(G, *MRI);
326 Changed |= DCE.run();
330 dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n'
331 << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
333 Liveness LV(*MRI, G);
341 MF.print(dbgs() << "After " << getPassName() << "\n", nullptr);
346 FunctionPass *llvm::createHexagonRDFOpt() {
347 return new HexagonRDFOpt();