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 static cl::opt<bool> RDFDump("hexagon-rdf-dump", cl::Hidden); 54 static cl::opt<bool> RDFTrackReserved("hexagon-rdf-track-reserved", cl::Hidden); 55 56 namespace { 57 58 class HexagonRDFOpt : public MachineFunctionPass { 59 public: 60 HexagonRDFOpt() : MachineFunctionPass(ID) {} 61 62 void getAnalysisUsage(AnalysisUsage &AU) const override { 63 AU.addRequired<MachineDominatorTree>(); 64 AU.addRequired<MachineDominanceFrontier>(); 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().set( 77 MachineFunctionProperties::Property::NoVRegs); 78 } 79 80 static char ID; 81 82 private: 83 MachineDominatorTree *MDT; 84 MachineRegisterInfo *MRI; 85 }; 86 87 struct HexagonCP : public CopyPropagation { 88 HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {} 89 90 bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override; 91 }; 92 93 struct HexagonDCE : public DeadCodeElimination { 94 HexagonDCE(DataFlowGraph &G, MachineRegisterInfo &MRI) 95 : DeadCodeElimination(G, MRI) {} 96 97 bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove); 98 void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum); 99 100 bool run(); 101 }; 102 103 } // end anonymous namespace 104 105 char HexagonRDFOpt::ID = 0; 106 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) 113 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)); 117 }; 118 119 DataFlowGraph &DFG = getDFG(); 120 unsigned Opc = MI->getOpcode(); 121 switch (Opc) { 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())); 131 return true; 132 } 133 case Hexagon::A2_addi: { 134 const MachineOperand &A = MI->getOperand(2); 135 if (!A.isImm() || A.getImm() != 0) 136 return false; 137 [[fallthrough]]; 138 } 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())); 144 return true; 145 } 146 } 147 148 return CopyPropagation::interpretAsCopy(MI, EM); 149 } 150 151 bool HexagonDCE::run() { 152 bool Collected = collect(); 153 if (!Collected) 154 return false; 155 156 const SetVector<NodeId> &DeadNodes = getDeadNodes(); 157 const SetVector<NodeId> &DeadInstrs = getDeadInstrs(); 158 159 using RefToInstrMap = DenseMap<NodeId, NodeId>; 160 161 RefToInstrMap R2I; 162 SetVector<NodeId> PartlyDead; 163 DataFlowGraph &DFG = getDFG(); 164 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); 173 } 174 } 175 } 176 177 // Nodes to remove. 178 SetVector<NodeId> Remove = DeadInstrs; 179 180 bool Changed = false; 181 for (NodeId N : PartlyDead) { 182 auto SA = DFG.addr<StmtNode*>(N); 183 if (trace()) 184 dbgs() << "Partly dead: " << *SA.Addr->getCode(); 185 Changed |= rewrite(SA, Remove); 186 } 187 188 return erase(Remove) || Changed; 189 } 190 191 void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) { 192 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode(); 193 194 auto getOpNum = [MI] (MachineOperand &Op) -> unsigned { 195 for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i) 196 if (&MI->getOperand(i) == &Op) 197 return i; 198 llvm_unreachable("Invalid operand"); 199 }; 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()))); 205 206 MI->removeOperand(OpNum); 207 208 for (NodeAddr<RefNode*> RA : Refs) { 209 unsigned N = OpMap[RA.Id]; 210 if (N < OpNum) 211 RA.Addr->setRegRef(&MI->getOperand(N), DFG); 212 else if (N > OpNum) 213 RA.Addr->setRegRef(&MI->getOperand(N-1), DFG); 214 } 215 } 216 217 bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) { 218 if (!getDFG().IsCode<NodeAttrs::Stmt>(IA)) 219 return false; 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) 224 return false; 225 unsigned Opc = MI.getOpcode(); 226 unsigned OpNum, NewOpc; 227 switch (Opc) { 228 case Hexagon::L2_loadri_pi: 229 NewOpc = Hexagon::L2_loadri_io; 230 OpNum = 1; 231 break; 232 case Hexagon::L2_loadrd_pi: 233 NewOpc = Hexagon::L2_loadrd_io; 234 OpNum = 1; 235 break; 236 case Hexagon::V6_vL32b_pi: 237 NewOpc = Hexagon::V6_vL32b_ai; 238 OpNum = 1; 239 break; 240 case Hexagon::S2_storeri_pi: 241 NewOpc = Hexagon::S2_storeri_io; 242 OpNum = 0; 243 break; 244 case Hexagon::S2_storerd_pi: 245 NewOpc = Hexagon::S2_storerd_io; 246 OpNum = 0; 247 break; 248 case Hexagon::V6_vS32b_pi: 249 NewOpc = Hexagon::V6_vS32b_ai; 250 OpNum = 0; 251 break; 252 default: 253 return false; 254 } 255 auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool { 256 return getDeadNodes().count(DA.Id); 257 }; 258 NodeList Defs; 259 MachineOperand &Op = MI.getOperand(OpNum); 260 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) { 261 if (&DA.Addr->getOp() != &Op) 262 continue; 263 Defs = DFG.getRelatedRefs(IA, DA); 264 if (!llvm::all_of(Defs, IsDead)) 265 return false; 266 break; 267 } 268 269 // Mark all nodes in Defs for removal. 270 for (auto D : Defs) 271 Remove.insert(D.Id); 272 273 if (trace()) 274 dbgs() << "Rewriting: " << MI; 275 MI.setDesc(HII.get(NewOpc)); 276 MI.getOperand(OpNum+2).setImm(0); 277 removeOperand(IA, OpNum); 278 if (trace()) 279 dbgs() << " to: " << MI; 280 281 return true; 282 } 283 284 bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) { 285 if (skipFunction(MF.getFunction())) 286 return false; 287 288 if (RDFLimit.getPosition()) { 289 if (RDFCount >= RDFLimit) 290 return false; 291 RDFCount++; 292 } 293 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(); 299 bool Changed; 300 301 if (RDFDump) 302 MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr); 303 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; 312 G.build(Cfg); 313 314 if (RDFDump) 315 dbgs() << "Starting copy propagation on: " << MF.getName() << '\n' 316 << PrintNode<FuncNode*>(G.getFunc(), G) << '\n'; 317 HexagonCP CP(G); 318 CP.trace(RDFDump); 319 Changed = CP.run(); 320 321 if (RDFDump) 322 dbgs() << "Starting dead code elimination on: " << MF.getName() << '\n' 323 << PrintNode<FuncNode*>(G.getFunc(), G) << '\n'; 324 HexagonDCE DCE(G, *MRI); 325 DCE.trace(RDFDump); 326 Changed |= DCE.run(); 327 328 if (Changed) { 329 if (RDFDump) { 330 dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n' 331 << PrintNode<FuncNode*>(G.getFunc(), G) << '\n'; 332 } 333 Liveness LV(*MRI, G); 334 LV.trace(RDFDump); 335 LV.computeLiveIns(); 336 LV.resetLiveIns(); 337 LV.resetKills(); 338 } 339 340 if (RDFDump) 341 MF.print(dbgs() << "After " << getPassName() << "\n", nullptr); 342 343 return false; 344 } 345 346 FunctionPass *llvm::createHexagonRDFOpt() { 347 return new HexagonRDFOpt(); 348 } 349