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:
HexagonRDFOpt()44 HexagonRDFOpt() : MachineFunctionPass(ID) {
45 initializeHexagonRDFOptPass(*PassRegistry::getPassRegistry());
46 }
getAnalysisUsage(AnalysisUsage & AU) const47 void getAnalysisUsage(AnalysisUsage &AU) const override {
48 AU.addRequired<MachineDominatorTree>();
49 AU.addRequired<MachineDominanceFrontier>();
50 AU.setPreservesAll();
51 MachineFunctionPass::getAnalysisUsage(AU);
52 }
getPassName() const53 const char *getPassName() const override {
54 return "Hexagon RDF optimizations";
55 }
56 bool runOnMachineFunction(MachineFunction &MF) override;
57
getRequiredProperties() const58 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 {
HexagonCP__anonbd8cb0190211::HexagonCP81 HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {}
82 bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override;
83 };
84
85
86 struct HexagonDCE : public DeadCodeElimination {
HexagonDCE__anonbd8cb0190211::HexagonDCE87 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
interpretAsCopy(const MachineInstr * MI,EqualityMap & EM)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
run()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
removeOperand(NodeAddr<InstrNode * > IA,unsigned OpNum)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
rewrite(NodeAddr<InstrNode * > IA,SetVector<NodeId> & Remove)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
runOnMachineFunction(MachineFunction & MF)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
createHexagonRDFOpt()328 FunctionPass *llvm::createHexagonRDFOpt() {
329 return new HexagonRDFOpt();
330 }
331