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