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