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 38 using namespace llvm; 39 using namespace rdf; 40 41 namespace llvm { 42 43 void initializeHexagonRDFOptPass(PassRegistry&); 44 FunctionPass *createHexagonRDFOpt(); 45 46 } // end namespace llvm 47 48 static unsigned RDFCount = 0; 49 50 static cl::opt<unsigned> 51 RDFLimit("hexagon-rdf-limit", 52 cl::init(std::numeric_limits<unsigned>::max())); 53 54 extern cl::opt<unsigned> RDFFuncBlockLimit; 55 56 static cl::opt<bool> RDFDump("hexagon-rdf-dump", cl::Hidden); 57 static cl::opt<bool> RDFTrackReserved("hexagon-rdf-track-reserved", cl::Hidden); 58 59 namespace { 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 90 struct HexagonCP : public CopyPropagation { 91 HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {} 92 93 bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override; 94 }; 95 96 struct 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 108 char HexagonRDFOpt::ID = 0; 109 110 INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt", 111 "Hexagon RDF optimizations", false, false) 112 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass) 113 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier) 114 INITIALIZE_PASS_END(HexagonRDFOpt, "hexagon-rdf-opt", 115 "Hexagon RDF optimizations", false, false) 116 117 bool HexagonCP::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) { 118 auto mapRegs = [&EM] (RegisterRef DstR, RegisterRef SrcR) -> void { 119 EM.insert(std::make_pair(DstR, 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(0); 127 const MachineOperand &HiOp = MI->getOperand(1); 128 const MachineOperand &LoOp = MI->getOperand(2); 129 assert(DstOp.getSubReg() == 0 && "Unexpected subregister"); 130 mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_hi), 131 DFG.makeRegRef(HiOp.getReg(), HiOp.getSubReg())); 132 mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_lo), 133 DFG.makeRegRef(LoOp.getReg(), LoOp.getSubReg())); 134 return true; 135 } 136 case Hexagon::A2_addi: { 137 const MachineOperand &A = MI->getOperand(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(0); 144 const MachineOperand &SrcOp = MI->getOperand(1); 145 mapRegs(DFG.makeRegRef(DstOp.getReg(), DstOp.getSubReg()), 146 DFG.makeRegRef(SrcOp.getReg(), SrcOp.getSubReg())); 147 return true; 148 } 149 } 150 151 return CopyPropagation::interpretAsCopy(MI, EM); 152 } 153 154 bool 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(DFG)) { 169 for (auto TA : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Stmt>, DFG)) { 170 NodeAddr<StmtNode*> SA = TA; 171 for (NodeAddr<RefNode*> RA : SA.Addr->members(DFG)) { 172 R2I.insert(std::make_pair(RA.Id, SA.Id)); 173 if (DFG.IsDef(RA) && DeadNodes.count(RA.Id)) 174 if (!DeadInstrs.count(SA.Id)) 175 PartlyDead.insert(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(SA, Remove); 189 } 190 191 return erase(Remove) || Changed; 192 } 193 194 void 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(DFG); 206 for (NodeAddr<RefNode*> RA : Refs) 207 OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp()))); 208 209 MI->removeOperand(OpNum); 210 211 for (NodeAddr<RefNode*> RA : Refs) { 212 unsigned N = OpMap[RA.Id]; 213 if (N < OpNum) 214 RA.Addr->setRegRef(&MI->getOperand(N), DFG); 215 else if (N > OpNum) 216 RA.Addr->setRegRef(&MI->getOperand(N-1), DFG); 217 } 218 } 219 220 bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) { 221 if (!getDFG().IsCode<NodeAttrs::Stmt>(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(DA.Id); 260 }; 261 NodeList Defs; 262 MachineOperand &Op = MI.getOperand(OpNum); 263 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) { 264 if (&DA.Addr->getOp() != &Op) 265 continue; 266 Defs = DFG.getRelatedRefs(IA, DA); 267 if (!llvm::all_of(Defs, IsDead)) 268 return false; 269 break; 270 } 271 272 // Mark all nodes in Defs for removal. 273 for (auto D : Defs) 274 Remove.insert(D.Id); 275 276 if (trace()) 277 dbgs() << "Rewriting: " << MI; 278 MI.setDesc(HII.get(NewOpc)); 279 MI.getOperand(OpNum+2).setImm(0); 280 removeOperand(IA, OpNum); 281 if (trace()) 282 dbgs() << " to: " << MI; 283 284 return true; 285 } 286 287 bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) { 288 if (skipFunction(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(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(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(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(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(RDFDump); 346 LV.computeLiveIns(); 347 LV.resetLiveIns(); 348 LV.resetKills(); 349 } 350 351 if (RDFDump) 352 MF.print(dbgs() << "After " << getPassName() << "\n", nullptr); 353 354 return false; 355 } 356 357 FunctionPass *llvm::createHexagonRDFOpt() { 358 return new HexagonRDFOpt(); 359 } 360