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