1 //===--- HexagonRDFOpt.cpp ------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "HexagonInstrInfo.h"
11 #include "HexagonSubtarget.h"
13 #include "RDFDeadCode.h"
15 #include "RDFLiveness.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/CodeGen/MachineBasicBlock.h"
18 #include "llvm/CodeGen/MachineDominanceFrontier.h"
19 #include "llvm/CodeGen/MachineDominators.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/Support/CommandLine.h"
24 #include "llvm/Support/Format.h"
25 #include "llvm/Target/TargetInstrInfo.h"
26 #include "llvm/Target/TargetRegisterInfo.h"
32 void initializeHexagonRDFOptPass(PassRegistry&);
33 FunctionPass *createHexagonRDFOpt();
37 unsigned RDFCount = 0;
38 cl::opt<unsigned> RDFLimit("rdf-limit", cl::init(UINT_MAX));
39 cl::opt<bool> RDFDump("rdf-dump", cl::init(false));
41 class HexagonRDFOpt : public MachineFunctionPass {
43 HexagonRDFOpt() : MachineFunctionPass(ID) {
44 initializeHexagonRDFOptPass(*PassRegistry::getPassRegistry());
46 void getAnalysisUsage(AnalysisUsage &AU) const override {
47 AU.addRequired<MachineDominatorTree>();
48 AU.addRequired<MachineDominanceFrontier>();
50 MachineFunctionPass::getAnalysisUsage(AU);
52 StringRef getPassName() const override {
53 return "Hexagon RDF optimizations";
55 bool runOnMachineFunction(MachineFunction &MF) override;
57 MachineFunctionProperties getRequiredProperties() const override {
58 return MachineFunctionProperties().set(
59 MachineFunctionProperties::Property::NoVRegs);
65 MachineDominatorTree *MDT;
66 MachineRegisterInfo *MRI;
69 char HexagonRDFOpt::ID = 0;
72 INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "rdfopt", "Hexagon RDF opt", false, false)
73 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
74 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
75 INITIALIZE_PASS_END(HexagonRDFOpt, "rdfopt", "Hexagon RDF opt", false, false)
79 struct HexagonCP : public CopyPropagation {
80 HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {}
81 bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override;
85 struct HexagonDCE : public DeadCodeElimination {
86 HexagonDCE(DataFlowGraph &G, MachineRegisterInfo &MRI)
87 : DeadCodeElimination(G, MRI) {}
88 bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove);
89 void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum);
93 } // end anonymous namespace
96 bool HexagonCP::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
97 auto mapRegs = [MI,&EM] (RegisterRef DstR, RegisterRef SrcR) -> void {
98 EM.insert(std::make_pair(DstR, SrcR));
101 DataFlowGraph &DFG = getDFG();
102 unsigned Opc = MI->getOpcode();
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(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_hi),
110 DFG.makeRegRef(HiOp.getReg(), HiOp.getSubReg()));
111 mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_lo),
112 DFG.makeRegRef(LoOp.getReg(), LoOp.getSubReg()));
115 case Hexagon::A2_addi: {
116 const MachineOperand &A = MI->getOperand(2);
117 if (!A.isImm() || A.getImm() != 0)
121 case Hexagon::A2_tfr: {
122 const MachineOperand &DstOp = MI->getOperand(0);
123 const MachineOperand &SrcOp = MI->getOperand(1);
124 mapRegs(DFG.makeRegRef(DstOp.getReg(), DstOp.getSubReg()),
125 DFG.makeRegRef(SrcOp.getReg(), SrcOp.getSubReg()));
130 return CopyPropagation::interpretAsCopy(MI, EM);
134 bool HexagonDCE::run() {
135 bool Collected = collect();
139 const SetVector<NodeId> &DeadNodes = getDeadNodes();
140 const SetVector<NodeId> &DeadInstrs = getDeadInstrs();
142 typedef DenseMap<NodeId,NodeId> RefToInstrMap;
144 SetVector<NodeId> PartlyDead;
145 DataFlowGraph &DFG = getDFG();
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);
161 SetVector<NodeId> Remove = DeadInstrs;
163 bool Changed = false;
164 for (NodeId N : PartlyDead) {
165 auto SA = DFG.addr<StmtNode*>(N);
167 dbgs() << "Partly dead: " << *SA.Addr->getCode();
168 Changed |= rewrite(SA, Remove);
171 return erase(Remove) || Changed;
175 void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) {
176 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
178 auto getOpNum = [MI] (MachineOperand &Op) -> unsigned {
179 for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i)
180 if (&MI->getOperand(i) == &Op)
182 llvm_unreachable("Invalid operand");
184 DenseMap<NodeId,unsigned> OpMap;
185 DataFlowGraph &DFG = getDFG();
186 NodeList Refs = IA.Addr->members(DFG);
187 for (NodeAddr<RefNode*> RA : Refs)
188 OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp())));
190 MI->RemoveOperand(OpNum);
192 for (NodeAddr<RefNode*> RA : Refs) {
193 unsigned N = OpMap[RA.Id];
195 RA.Addr->setRegRef(&MI->getOperand(N), DFG);
197 RA.Addr->setRegRef(&MI->getOperand(N-1), DFG);
202 bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) {
203 if (!getDFG().IsCode<NodeAttrs::Stmt>(IA))
205 DataFlowGraph &DFG = getDFG();
206 MachineInstr &MI = *NodeAddr<StmtNode*>(IA).Addr->getCode();
207 auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII());
208 if (HII.getAddrMode(MI) != HexagonII::PostInc)
210 unsigned Opc = MI.getOpcode();
211 unsigned OpNum, NewOpc;
213 case Hexagon::L2_loadri_pi:
214 NewOpc = Hexagon::L2_loadri_io;
217 case Hexagon::L2_loadrd_pi:
218 NewOpc = Hexagon::L2_loadrd_io;
221 case Hexagon::V6_vL32b_pi:
222 NewOpc = Hexagon::V6_vL32b_ai;
225 case Hexagon::S2_storeri_pi:
226 NewOpc = Hexagon::S2_storeri_io;
229 case Hexagon::S2_storerd_pi:
230 NewOpc = Hexagon::S2_storerd_io;
233 case Hexagon::V6_vS32b_pi:
234 NewOpc = Hexagon::V6_vS32b_ai;
240 auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool {
241 return getDeadNodes().count(DA.Id);
244 MachineOperand &Op = MI.getOperand(OpNum);
245 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) {
246 if (&DA.Addr->getOp() != &Op)
248 Defs = DFG.getRelatedRefs(IA, DA);
249 if (!all_of(Defs, IsDead))
254 // Mark all nodes in Defs for removal.
259 dbgs() << "Rewriting: " << MI;
260 MI.setDesc(HII.get(NewOpc));
261 MI.getOperand(OpNum+2).setImm(0);
262 removeOperand(IA, OpNum);
264 dbgs() << " to: " << MI;
270 bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) {
271 if (skipFunction(*MF.getFunction()))
274 if (RDFLimit.getPosition()) {
275 if (RDFCount >= RDFLimit)
280 MDT = &getAnalysis<MachineDominatorTree>();
281 const auto &MDF = getAnalysis<MachineDominanceFrontier>();
282 const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
283 const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
284 MRI = &MF.getRegInfo();
288 MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr);
290 TargetOperandInfo TOI(HII);
291 DataFlowGraph G(MF, HII, HRI, *MDT, MDF, 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);
298 dbgs() << "Starting copy propagation on: " << MF.getName() << '\n'
299 << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
305 dbgs() << "Starting dead code elimination on: " << MF.getName() << '\n'
306 << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
307 HexagonDCE DCE(G, *MRI);
309 Changed |= DCE.run();
313 dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n';
314 Liveness LV(*MRI, G);
322 MF.print(dbgs() << "After " << getPassName() << "\n", nullptr);
328 FunctionPass *llvm::createHexagonRDFOpt() {
329 return new HexagonRDFOpt();