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> RDFLimit("rdf-limit", 51 cl::init(std::numeric_limits<unsigned>::max())); 52 static cl::opt<bool> RDFDump("rdf-dump", cl::init(false)); 53 54 namespace { 55 56 class HexagonRDFOpt : public MachineFunctionPass { 57 public: 58 HexagonRDFOpt() : MachineFunctionPass(ID) {} 59 60 void getAnalysisUsage(AnalysisUsage &AU) const override { 61 AU.addRequired<MachineDominatorTree>(); 62 AU.addRequired<MachineDominanceFrontier>(); 63 AU.setPreservesAll(); 64 MachineFunctionPass::getAnalysisUsage(AU); 65 } 66 67 StringRef getPassName() const override { 68 return "Hexagon RDF optimizations"; 69 } 70 71 bool runOnMachineFunction(MachineFunction &MF) override; 72 73 MachineFunctionProperties getRequiredProperties() const override { 74 return MachineFunctionProperties().set( 75 MachineFunctionProperties::Property::NoVRegs); 76 } 77 78 static char ID; 79 80 private: 81 MachineDominatorTree *MDT; 82 MachineRegisterInfo *MRI; 83 }; 84 85 struct HexagonCP : public CopyPropagation { 86 HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {} 87 88 bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override; 89 }; 90 91 struct HexagonDCE : public DeadCodeElimination { 92 HexagonDCE(DataFlowGraph &G, MachineRegisterInfo &MRI) 93 : DeadCodeElimination(G, MRI) {} 94 95 bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove); 96 void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum); 97 98 bool run(); 99 }; 100 101 } // end anonymous namespace 102 103 char HexagonRDFOpt::ID = 0; 104 105 INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt", 106 "Hexagon RDF optimizations", false, false) 107 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 108 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier) 109 INITIALIZE_PASS_END(HexagonRDFOpt, "hexagon-rdf-opt", 110 "Hexagon RDF optimizations", false, false) 111 112 bool HexagonCP::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) { 113 auto mapRegs = [&EM] (RegisterRef DstR, RegisterRef SrcR) -> void { 114 EM.insert(std::make_pair(DstR, SrcR)); 115 }; 116 117 DataFlowGraph &DFG = getDFG(); 118 unsigned Opc = MI->getOpcode(); 119 switch (Opc) { 120 case Hexagon::A2_combinew: { 121 const MachineOperand &DstOp = MI->getOperand(0); 122 const MachineOperand &HiOp = MI->getOperand(1); 123 const MachineOperand &LoOp = MI->getOperand(2); 124 assert(DstOp.getSubReg() == 0 && "Unexpected subregister"); 125 mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_hi), 126 DFG.makeRegRef(HiOp.getReg(), HiOp.getSubReg())); 127 mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_lo), 128 DFG.makeRegRef(LoOp.getReg(), LoOp.getSubReg())); 129 return true; 130 } 131 case Hexagon::A2_addi: { 132 const MachineOperand &A = MI->getOperand(2); 133 if (!A.isImm() || A.getImm() != 0) 134 return false; 135 LLVM_FALLTHROUGH; 136 } 137 case Hexagon::A2_tfr: { 138 const MachineOperand &DstOp = MI->getOperand(0); 139 const MachineOperand &SrcOp = MI->getOperand(1); 140 mapRegs(DFG.makeRegRef(DstOp.getReg(), DstOp.getSubReg()), 141 DFG.makeRegRef(SrcOp.getReg(), SrcOp.getSubReg())); 142 return true; 143 } 144 } 145 146 return CopyPropagation::interpretAsCopy(MI, EM); 147 } 148 149 bool HexagonDCE::run() { 150 bool Collected = collect(); 151 if (!Collected) 152 return false; 153 154 const SetVector<NodeId> &DeadNodes = getDeadNodes(); 155 const SetVector<NodeId> &DeadInstrs = getDeadInstrs(); 156 157 using RefToInstrMap = DenseMap<NodeId, NodeId>; 158 159 RefToInstrMap R2I; 160 SetVector<NodeId> PartlyDead; 161 DataFlowGraph &DFG = getDFG(); 162 163 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) { 164 for (auto TA : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Stmt>, DFG)) { 165 NodeAddr<StmtNode*> SA = TA; 166 for (NodeAddr<RefNode*> RA : SA.Addr->members(DFG)) { 167 R2I.insert(std::make_pair(RA.Id, SA.Id)); 168 if (DFG.IsDef(RA) && DeadNodes.count(RA.Id)) 169 if (!DeadInstrs.count(SA.Id)) 170 PartlyDead.insert(SA.Id); 171 } 172 } 173 } 174 175 // Nodes to remove. 176 SetVector<NodeId> Remove = DeadInstrs; 177 178 bool Changed = false; 179 for (NodeId N : PartlyDead) { 180 auto SA = DFG.addr<StmtNode*>(N); 181 if (trace()) 182 dbgs() << "Partly dead: " << *SA.Addr->getCode(); 183 Changed |= rewrite(SA, Remove); 184 } 185 186 return erase(Remove) || Changed; 187 } 188 189 void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) { 190 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode(); 191 192 auto getOpNum = [MI] (MachineOperand &Op) -> unsigned { 193 for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i) 194 if (&MI->getOperand(i) == &Op) 195 return i; 196 llvm_unreachable("Invalid operand"); 197 }; 198 DenseMap<NodeId,unsigned> OpMap; 199 DataFlowGraph &DFG = getDFG(); 200 NodeList Refs = IA.Addr->members(DFG); 201 for (NodeAddr<RefNode*> RA : Refs) 202 OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp()))); 203 204 MI->RemoveOperand(OpNum); 205 206 for (NodeAddr<RefNode*> RA : Refs) { 207 unsigned N = OpMap[RA.Id]; 208 if (N < OpNum) 209 RA.Addr->setRegRef(&MI->getOperand(N), DFG); 210 else if (N > OpNum) 211 RA.Addr->setRegRef(&MI->getOperand(N-1), DFG); 212 } 213 } 214 215 bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) { 216 if (!getDFG().IsCode<NodeAttrs::Stmt>(IA)) 217 return false; 218 DataFlowGraph &DFG = getDFG(); 219 MachineInstr &MI = *NodeAddr<StmtNode*>(IA).Addr->getCode(); 220 auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII()); 221 if (HII.getAddrMode(MI) != HexagonII::PostInc) 222 return false; 223 unsigned Opc = MI.getOpcode(); 224 unsigned OpNum, NewOpc; 225 switch (Opc) { 226 case Hexagon::L2_loadri_pi: 227 NewOpc = Hexagon::L2_loadri_io; 228 OpNum = 1; 229 break; 230 case Hexagon::L2_loadrd_pi: 231 NewOpc = Hexagon::L2_loadrd_io; 232 OpNum = 1; 233 break; 234 case Hexagon::V6_vL32b_pi: 235 NewOpc = Hexagon::V6_vL32b_ai; 236 OpNum = 1; 237 break; 238 case Hexagon::S2_storeri_pi: 239 NewOpc = Hexagon::S2_storeri_io; 240 OpNum = 0; 241 break; 242 case Hexagon::S2_storerd_pi: 243 NewOpc = Hexagon::S2_storerd_io; 244 OpNum = 0; 245 break; 246 case Hexagon::V6_vS32b_pi: 247 NewOpc = Hexagon::V6_vS32b_ai; 248 OpNum = 0; 249 break; 250 default: 251 return false; 252 } 253 auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool { 254 return getDeadNodes().count(DA.Id); 255 }; 256 NodeList Defs; 257 MachineOperand &Op = MI.getOperand(OpNum); 258 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) { 259 if (&DA.Addr->getOp() != &Op) 260 continue; 261 Defs = DFG.getRelatedRefs(IA, DA); 262 if (!llvm::all_of(Defs, IsDead)) 263 return false; 264 break; 265 } 266 267 // Mark all nodes in Defs for removal. 268 for (auto D : Defs) 269 Remove.insert(D.Id); 270 271 if (trace()) 272 dbgs() << "Rewriting: " << MI; 273 MI.setDesc(HII.get(NewOpc)); 274 MI.getOperand(OpNum+2).setImm(0); 275 removeOperand(IA, OpNum); 276 if (trace()) 277 dbgs() << " to: " << MI; 278 279 return true; 280 } 281 282 bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) { 283 if (skipFunction(MF.getFunction())) 284 return false; 285 286 if (RDFLimit.getPosition()) { 287 if (RDFCount >= RDFLimit) 288 return false; 289 RDFCount++; 290 } 291 292 MDT = &getAnalysis<MachineDominatorTree>(); 293 const auto &MDF = getAnalysis<MachineDominanceFrontier>(); 294 const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo(); 295 const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo(); 296 MRI = &MF.getRegInfo(); 297 bool Changed; 298 299 if (RDFDump) 300 MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr); 301 302 TargetOperandInfo TOI(HII); 303 DataFlowGraph G(MF, HII, HRI, *MDT, MDF, TOI); 304 // Dead phi nodes are necessary for copy propagation: we can add a use 305 // of a register in a block where it would need a phi node, but which 306 // was dead (and removed) during the graph build time. 307 G.build(BuildOptions::KeepDeadPhis); 308 309 if (RDFDump) 310 dbgs() << "Starting copy propagation on: " << MF.getName() << '\n' 311 << PrintNode<FuncNode*>(G.getFunc(), G) << '\n'; 312 HexagonCP CP(G); 313 CP.trace(RDFDump); 314 Changed = CP.run(); 315 316 if (RDFDump) 317 dbgs() << "Starting dead code elimination on: " << MF.getName() << '\n' 318 << PrintNode<FuncNode*>(G.getFunc(), G) << '\n'; 319 HexagonDCE DCE(G, *MRI); 320 DCE.trace(RDFDump); 321 Changed |= DCE.run(); 322 323 if (Changed) { 324 if (RDFDump) 325 dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n'; 326 Liveness LV(*MRI, G); 327 LV.trace(RDFDump); 328 LV.computeLiveIns(); 329 LV.resetLiveIns(); 330 LV.resetKills(); 331 } 332 333 if (RDFDump) 334 MF.print(dbgs() << "After " << getPassName() << "\n", nullptr); 335 336 return false; 337 } 338 339 FunctionPass *llvm::createHexagonRDFOpt() { 340 return new HexagonRDFOpt(); 341 } 342