File: | build/source/llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp |
Warning: | line 569, column 3 1st function call argument is an uninitialized value |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- HexagonVectorLoopCarriedReuse.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 | // This pass removes the computation of provably redundant expressions that have | |||
10 | // been computed earlier in a previous iteration. It relies on the use of PHIs | |||
11 | // to identify loop carried dependences. This is scalar replacement for vector | |||
12 | // types. | |||
13 | // | |||
14 | //===----------------------------------------------------------------------===// | |||
15 | ||||
16 | #include "HexagonVectorLoopCarriedReuse.h" | |||
17 | #include "llvm/ADT/SetVector.h" | |||
18 | #include "llvm/ADT/SmallVector.h" | |||
19 | #include "llvm/ADT/Statistic.h" | |||
20 | #include "llvm/Analysis/LoopInfo.h" | |||
21 | #include "llvm/Analysis/LoopPass.h" | |||
22 | #include "llvm/IR/BasicBlock.h" | |||
23 | #include "llvm/IR/DerivedTypes.h" | |||
24 | #include "llvm/IR/IRBuilder.h" | |||
25 | #include "llvm/IR/Instruction.h" | |||
26 | #include "llvm/IR/Instructions.h" | |||
27 | #include "llvm/IR/IntrinsicInst.h" | |||
28 | #include "llvm/IR/Intrinsics.h" | |||
29 | #include "llvm/IR/IntrinsicsHexagon.h" | |||
30 | #include "llvm/IR/Use.h" | |||
31 | #include "llvm/IR/User.h" | |||
32 | #include "llvm/IR/Value.h" | |||
33 | #include "llvm/InitializePasses.h" | |||
34 | #include "llvm/Pass.h" | |||
35 | #include "llvm/Support/Casting.h" | |||
36 | #include "llvm/Support/CommandLine.h" | |||
37 | #include "llvm/Support/Compiler.h" | |||
38 | #include "llvm/Support/Debug.h" | |||
39 | #include "llvm/Support/raw_ostream.h" | |||
40 | #include "llvm/Transforms/Scalar.h" | |||
41 | #include "llvm/Transforms/Utils.h" | |||
42 | #include <algorithm> | |||
43 | #include <cassert> | |||
44 | #include <cstddef> | |||
45 | #include <map> | |||
46 | #include <memory> | |||
47 | #include <set> | |||
48 | ||||
49 | using namespace llvm; | |||
50 | ||||
51 | #define DEBUG_TYPE"hexagon-vlcr" "hexagon-vlcr" | |||
52 | ||||
53 | STATISTIC(HexagonNumVectorLoopCarriedReuse,static llvm::Statistic HexagonNumVectorLoopCarriedReuse = {"hexagon-vlcr" , "HexagonNumVectorLoopCarriedReuse", "Number of values that were reused from a previous iteration." } | |||
54 | "Number of values that were reused from a previous iteration.")static llvm::Statistic HexagonNumVectorLoopCarriedReuse = {"hexagon-vlcr" , "HexagonNumVectorLoopCarriedReuse", "Number of values that were reused from a previous iteration." }; | |||
55 | ||||
56 | static cl::opt<int> HexagonVLCRIterationLim( | |||
57 | "hexagon-vlcr-iteration-lim", cl::Hidden, | |||
58 | cl::desc("Maximum distance of loop carried dependences that are handled"), | |||
59 | cl::init(2)); | |||
60 | ||||
61 | namespace llvm { | |||
62 | ||||
63 | void initializeHexagonVectorLoopCarriedReuseLegacyPassPass(PassRegistry &); | |||
64 | Pass *createHexagonVectorLoopCarriedReuseLegacyPass(); | |||
65 | ||||
66 | } // end namespace llvm | |||
67 | ||||
68 | namespace { | |||
69 | ||||
70 | // See info about DepChain in the comments at the top of this file. | |||
71 | using ChainOfDependences = SmallVector<Instruction *, 4>; | |||
72 | ||||
73 | class DepChain { | |||
74 | ChainOfDependences Chain; | |||
75 | ||||
76 | public: | |||
77 | bool isIdentical(DepChain &Other) const { | |||
78 | if (Other.size() != size()) | |||
79 | return false; | |||
80 | ChainOfDependences &OtherChain = Other.getChain(); | |||
81 | for (int i = 0; i < size(); ++i) { | |||
82 | if (Chain[i] != OtherChain[i]) | |||
83 | return false; | |||
84 | } | |||
85 | return true; | |||
86 | } | |||
87 | ||||
88 | ChainOfDependences &getChain() { | |||
89 | return Chain; | |||
90 | } | |||
91 | ||||
92 | int size() const { | |||
93 | return Chain.size(); | |||
94 | } | |||
95 | ||||
96 | void clear() { | |||
97 | Chain.clear(); | |||
98 | } | |||
99 | ||||
100 | void push_back(Instruction *I) { | |||
101 | Chain.push_back(I); | |||
102 | } | |||
103 | ||||
104 | int iterations() const { | |||
105 | return size() - 1; | |||
106 | } | |||
107 | ||||
108 | Instruction *front() const { | |||
109 | return Chain.front(); | |||
110 | } | |||
111 | ||||
112 | Instruction *back() const { | |||
113 | return Chain.back(); | |||
114 | } | |||
115 | ||||
116 | Instruction *&operator[](const int index) { | |||
117 | return Chain[index]; | |||
118 | } | |||
119 | ||||
120 | friend raw_ostream &operator<< (raw_ostream &OS, const DepChain &D); | |||
121 | }; | |||
122 | ||||
123 | LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) | |||
124 | raw_ostream &operator<<(raw_ostream &OS, const DepChain &D) { | |||
125 | const ChainOfDependences &CD = D.Chain; | |||
126 | int ChainSize = CD.size(); | |||
127 | OS << "**DepChain Start::**\n"; | |||
128 | for (int i = 0; i < ChainSize -1; ++i) { | |||
129 | OS << *(CD[i]) << " -->\n"; | |||
130 | } | |||
131 | OS << *CD[ChainSize-1] << "\n"; | |||
132 | return OS; | |||
133 | } | |||
134 | ||||
135 | struct ReuseValue { | |||
136 | Instruction *Inst2Replace = nullptr; | |||
137 | ||||
138 | // In the new PHI node that we'll construct this is the value that'll be | |||
139 | // used over the backedge. This is the value that gets reused from a | |||
140 | // previous iteration. | |||
141 | Instruction *BackedgeInst = nullptr; | |||
142 | std::map<Instruction *, DepChain *> DepChains; | |||
143 | int Iterations = -1; | |||
144 | ||||
145 | ReuseValue() = default; | |||
146 | ||||
147 | void reset() { | |||
148 | Inst2Replace = nullptr; | |||
149 | BackedgeInst = nullptr; | |||
150 | DepChains.clear(); | |||
151 | Iterations = -1; | |||
152 | } | |||
153 | bool isDefined() { return Inst2Replace != nullptr; } | |||
154 | }; | |||
155 | ||||
156 | LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__)) | |||
157 | raw_ostream &operator<<(raw_ostream &OS, const ReuseValue &RU) { | |||
158 | OS << "** ReuseValue ***\n"; | |||
159 | OS << "Instruction to Replace: " << *(RU.Inst2Replace) << "\n"; | |||
160 | OS << "Backedge Instruction: " << *(RU.BackedgeInst) << "\n"; | |||
161 | return OS; | |||
162 | } | |||
163 | ||||
164 | class HexagonVectorLoopCarriedReuseLegacyPass : public LoopPass { | |||
165 | public: | |||
166 | static char ID; | |||
167 | ||||
168 | explicit HexagonVectorLoopCarriedReuseLegacyPass() : LoopPass(ID) { | |||
169 | PassRegistry *PR = PassRegistry::getPassRegistry(); | |||
170 | initializeHexagonVectorLoopCarriedReuseLegacyPassPass(*PR); | |||
171 | } | |||
172 | ||||
173 | StringRef getPassName() const override { | |||
174 | return "Hexagon-specific loop carried reuse for HVX vectors"; | |||
175 | } | |||
176 | ||||
177 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
178 | AU.addRequiredID(LoopSimplifyID); | |||
179 | AU.addRequiredID(LCSSAID); | |||
180 | AU.addPreservedID(LCSSAID); | |||
181 | AU.setPreservesCFG(); | |||
182 | } | |||
183 | ||||
184 | bool runOnLoop(Loop *L, LPPassManager &LPM) override; | |||
185 | }; | |||
186 | ||||
187 | class HexagonVectorLoopCarriedReuse { | |||
188 | public: | |||
189 | HexagonVectorLoopCarriedReuse(Loop *L) : CurLoop(L){}; | |||
190 | ||||
191 | bool run(); | |||
192 | ||||
193 | private: | |||
194 | SetVector<DepChain *> Dependences; | |||
195 | std::set<Instruction *> ReplacedInsts; | |||
196 | Loop *CurLoop; | |||
197 | ReuseValue ReuseCandidate; | |||
198 | ||||
199 | bool doVLCR(); | |||
200 | void findLoopCarriedDeps(); | |||
201 | void findValueToReuse(); | |||
202 | void findDepChainFromPHI(Instruction *I, DepChain &D); | |||
203 | void reuseValue(); | |||
204 | Value *findValueInBlock(Value *Op, BasicBlock *BB); | |||
205 | DepChain *getDepChainBtwn(Instruction *I1, Instruction *I2, int Iters); | |||
206 | bool isEquivalentOperation(Instruction *I1, Instruction *I2); | |||
207 | bool canReplace(Instruction *I); | |||
208 | bool isCallInstCommutative(CallInst *C); | |||
209 | }; | |||
210 | ||||
211 | } // end anonymous namespace | |||
212 | ||||
213 | char HexagonVectorLoopCarriedReuseLegacyPass::ID = 0; | |||
214 | ||||
215 | INITIALIZE_PASS_BEGIN(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",static void *initializeHexagonVectorLoopCarriedReuseLegacyPassPassOnce (PassRegistry &Registry) { | |||
216 | "Hexagon-specific predictive commoning for HVX vectors",static void *initializeHexagonVectorLoopCarriedReuseLegacyPassPassOnce (PassRegistry &Registry) { | |||
217 | false, false)static void *initializeHexagonVectorLoopCarriedReuseLegacyPassPassOnce (PassRegistry &Registry) { | |||
218 | INITIALIZE_PASS_DEPENDENCY(LoopSimplify)initializeLoopSimplifyPass(Registry); | |||
219 | INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)initializeLCSSAWrapperPassPass(Registry); | |||
220 | INITIALIZE_PASS_END(HexagonVectorLoopCarriedReuseLegacyPass, "hexagon-vlcr",PassInfo *PI = new PassInfo( "Hexagon-specific predictive commoning for HVX vectors" , "hexagon-vlcr", &HexagonVectorLoopCarriedReuseLegacyPass ::ID, PassInfo::NormalCtor_t(callDefaultCtor<HexagonVectorLoopCarriedReuseLegacyPass >), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeHexagonVectorLoopCarriedReuseLegacyPassPassFlag ; void llvm::initializeHexagonVectorLoopCarriedReuseLegacyPassPass (PassRegistry &Registry) { llvm::call_once(InitializeHexagonVectorLoopCarriedReuseLegacyPassPassFlag , initializeHexagonVectorLoopCarriedReuseLegacyPassPassOnce, std ::ref(Registry)); } | |||
221 | "Hexagon-specific predictive commoning for HVX vectors",PassInfo *PI = new PassInfo( "Hexagon-specific predictive commoning for HVX vectors" , "hexagon-vlcr", &HexagonVectorLoopCarriedReuseLegacyPass ::ID, PassInfo::NormalCtor_t(callDefaultCtor<HexagonVectorLoopCarriedReuseLegacyPass >), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeHexagonVectorLoopCarriedReuseLegacyPassPassFlag ; void llvm::initializeHexagonVectorLoopCarriedReuseLegacyPassPass (PassRegistry &Registry) { llvm::call_once(InitializeHexagonVectorLoopCarriedReuseLegacyPassPassFlag , initializeHexagonVectorLoopCarriedReuseLegacyPassPassOnce, std ::ref(Registry)); } | |||
222 | false, false)PassInfo *PI = new PassInfo( "Hexagon-specific predictive commoning for HVX vectors" , "hexagon-vlcr", &HexagonVectorLoopCarriedReuseLegacyPass ::ID, PassInfo::NormalCtor_t(callDefaultCtor<HexagonVectorLoopCarriedReuseLegacyPass >), false, false); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeHexagonVectorLoopCarriedReuseLegacyPassPassFlag ; void llvm::initializeHexagonVectorLoopCarriedReuseLegacyPassPass (PassRegistry &Registry) { llvm::call_once(InitializeHexagonVectorLoopCarriedReuseLegacyPassPassFlag , initializeHexagonVectorLoopCarriedReuseLegacyPassPassOnce, std ::ref(Registry)); } | |||
223 | ||||
224 | PreservedAnalyses | |||
225 | HexagonVectorLoopCarriedReusePass::run(Loop &L, LoopAnalysisManager &LAM, | |||
226 | LoopStandardAnalysisResults &AR, | |||
227 | LPMUpdater &U) { | |||
228 | HexagonVectorLoopCarriedReuse Vlcr(&L); | |||
229 | if (!Vlcr.run()) | |||
230 | return PreservedAnalyses::all(); | |||
231 | PreservedAnalyses PA; | |||
232 | PA.preserveSet<CFGAnalyses>(); | |||
233 | return PA; | |||
234 | } | |||
235 | ||||
236 | bool HexagonVectorLoopCarriedReuseLegacyPass::runOnLoop(Loop *L, | |||
237 | LPPassManager &LPM) { | |||
238 | if (skipLoop(L)) | |||
| ||||
239 | return false; | |||
240 | HexagonVectorLoopCarriedReuse Vlcr(L); | |||
241 | return Vlcr.run(); | |||
242 | } | |||
243 | ||||
244 | bool HexagonVectorLoopCarriedReuse::run() { | |||
245 | if (!CurLoop->getLoopPreheader()) | |||
246 | return false; | |||
247 | ||||
248 | // Work only on innermost loops. | |||
249 | if (!CurLoop->getSubLoops().empty()) | |||
250 | return false; | |||
251 | ||||
252 | // Work only on single basic blocks loops. | |||
253 | if (CurLoop->getNumBlocks() != 1) | |||
254 | return false; | |||
255 | ||||
256 | return doVLCR(); | |||
257 | } | |||
258 | ||||
259 | bool HexagonVectorLoopCarriedReuse::isCallInstCommutative(CallInst *C) { | |||
260 | switch (C->getCalledFunction()->getIntrinsicID()) { | |||
261 | case Intrinsic::hexagon_V6_vaddb: | |||
262 | case Intrinsic::hexagon_V6_vaddb_128B: | |||
263 | case Intrinsic::hexagon_V6_vaddh: | |||
264 | case Intrinsic::hexagon_V6_vaddh_128B: | |||
265 | case Intrinsic::hexagon_V6_vaddw: | |||
266 | case Intrinsic::hexagon_V6_vaddw_128B: | |||
267 | case Intrinsic::hexagon_V6_vaddubh: | |||
268 | case Intrinsic::hexagon_V6_vaddubh_128B: | |||
269 | case Intrinsic::hexagon_V6_vadduhw: | |||
270 | case Intrinsic::hexagon_V6_vadduhw_128B: | |||
271 | case Intrinsic::hexagon_V6_vaddhw: | |||
272 | case Intrinsic::hexagon_V6_vaddhw_128B: | |||
273 | case Intrinsic::hexagon_V6_vmaxb: | |||
274 | case Intrinsic::hexagon_V6_vmaxb_128B: | |||
275 | case Intrinsic::hexagon_V6_vmaxh: | |||
276 | case Intrinsic::hexagon_V6_vmaxh_128B: | |||
277 | case Intrinsic::hexagon_V6_vmaxw: | |||
278 | case Intrinsic::hexagon_V6_vmaxw_128B: | |||
279 | case Intrinsic::hexagon_V6_vmaxub: | |||
280 | case Intrinsic::hexagon_V6_vmaxub_128B: | |||
281 | case Intrinsic::hexagon_V6_vmaxuh: | |||
282 | case Intrinsic::hexagon_V6_vmaxuh_128B: | |||
283 | case Intrinsic::hexagon_V6_vminub: | |||
284 | case Intrinsic::hexagon_V6_vminub_128B: | |||
285 | case Intrinsic::hexagon_V6_vminuh: | |||
286 | case Intrinsic::hexagon_V6_vminuh_128B: | |||
287 | case Intrinsic::hexagon_V6_vminb: | |||
288 | case Intrinsic::hexagon_V6_vminb_128B: | |||
289 | case Intrinsic::hexagon_V6_vminh: | |||
290 | case Intrinsic::hexagon_V6_vminh_128B: | |||
291 | case Intrinsic::hexagon_V6_vminw: | |||
292 | case Intrinsic::hexagon_V6_vminw_128B: | |||
293 | case Intrinsic::hexagon_V6_vmpyub: | |||
294 | case Intrinsic::hexagon_V6_vmpyub_128B: | |||
295 | case Intrinsic::hexagon_V6_vmpyuh: | |||
296 | case Intrinsic::hexagon_V6_vmpyuh_128B: | |||
297 | case Intrinsic::hexagon_V6_vavgub: | |||
298 | case Intrinsic::hexagon_V6_vavgub_128B: | |||
299 | case Intrinsic::hexagon_V6_vavgh: | |||
300 | case Intrinsic::hexagon_V6_vavgh_128B: | |||
301 | case Intrinsic::hexagon_V6_vavguh: | |||
302 | case Intrinsic::hexagon_V6_vavguh_128B: | |||
303 | case Intrinsic::hexagon_V6_vavgw: | |||
304 | case Intrinsic::hexagon_V6_vavgw_128B: | |||
305 | case Intrinsic::hexagon_V6_vavgb: | |||
306 | case Intrinsic::hexagon_V6_vavgb_128B: | |||
307 | case Intrinsic::hexagon_V6_vavguw: | |||
308 | case Intrinsic::hexagon_V6_vavguw_128B: | |||
309 | case Intrinsic::hexagon_V6_vabsdiffh: | |||
310 | case Intrinsic::hexagon_V6_vabsdiffh_128B: | |||
311 | case Intrinsic::hexagon_V6_vabsdiffub: | |||
312 | case Intrinsic::hexagon_V6_vabsdiffub_128B: | |||
313 | case Intrinsic::hexagon_V6_vabsdiffuh: | |||
314 | case Intrinsic::hexagon_V6_vabsdiffuh_128B: | |||
315 | case Intrinsic::hexagon_V6_vabsdiffw: | |||
316 | case Intrinsic::hexagon_V6_vabsdiffw_128B: | |||
317 | return true; | |||
318 | default: | |||
319 | return false; | |||
320 | } | |||
321 | } | |||
322 | ||||
323 | bool HexagonVectorLoopCarriedReuse::isEquivalentOperation(Instruction *I1, | |||
324 | Instruction *I2) { | |||
325 | if (!I1->isSameOperationAs(I2)) | |||
326 | return false; | |||
327 | // This check is in place specifically for intrinsics. isSameOperationAs will | |||
328 | // return two for any two hexagon intrinsics because they are essentially the | |||
329 | // same instruciton (CallInst). We need to scratch the surface to see if they | |||
330 | // are calls to the same function. | |||
331 | if (CallInst *C1 = dyn_cast<CallInst>(I1)) { | |||
332 | if (CallInst *C2 = dyn_cast<CallInst>(I2)) { | |||
333 | if (C1->getCalledFunction() != C2->getCalledFunction()) | |||
334 | return false; | |||
335 | } | |||
336 | } | |||
337 | ||||
338 | // If both the Instructions are of Vector Type and any of the element | |||
339 | // is integer constant, check their values too for equivalence. | |||
340 | if (I1->getType()->isVectorTy() && I2->getType()->isVectorTy()) { | |||
341 | unsigned NumOperands = I1->getNumOperands(); | |||
342 | for (unsigned i = 0; i < NumOperands; ++i) { | |||
343 | ConstantInt *C1 = dyn_cast<ConstantInt>(I1->getOperand(i)); | |||
344 | ConstantInt *C2 = dyn_cast<ConstantInt>(I2->getOperand(i)); | |||
345 | if(!C1) continue; | |||
346 | assert(C2)(static_cast <bool> (C2) ? void (0) : __assert_fail ("C2" , "llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp" , 346, __extension__ __PRETTY_FUNCTION__)); | |||
347 | if (C1->getSExtValue() != C2->getSExtValue()) | |||
348 | return false; | |||
349 | } | |||
350 | } | |||
351 | ||||
352 | return true; | |||
353 | } | |||
354 | ||||
355 | bool HexagonVectorLoopCarriedReuse::canReplace(Instruction *I) { | |||
356 | const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I); | |||
357 | if (!II) | |||
358 | return true; | |||
359 | ||||
360 | switch (II->getIntrinsicID()) { | |||
361 | case Intrinsic::hexagon_V6_hi: | |||
362 | case Intrinsic::hexagon_V6_lo: | |||
363 | case Intrinsic::hexagon_V6_hi_128B: | |||
364 | case Intrinsic::hexagon_V6_lo_128B: | |||
365 | LLVM_DEBUG(dbgs() << "Not considering for reuse: " << *II << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Not considering for reuse: " << *II << "\n"; } } while (false); | |||
366 | return false; | |||
367 | default: | |||
368 | return true; | |||
369 | } | |||
370 | } | |||
371 | void HexagonVectorLoopCarriedReuse::findValueToReuse() { | |||
372 | for (auto *D : Dependences) { | |||
373 | LLVM_DEBUG(dbgs() << "Processing dependence " << *(D->front()) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Processing dependence " << *(D->front()) << "\n"; } } while (false); | |||
374 | if (D->iterations() > HexagonVLCRIterationLim) { | |||
375 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << ".. Skipping because number of iterations > than the limit\n" ; } } while (false) | |||
376 | dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << ".. Skipping because number of iterations > than the limit\n" ; } } while (false) | |||
377 | << ".. Skipping because number of iterations > than the limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << ".. Skipping because number of iterations > than the limit\n" ; } } while (false); | |||
378 | continue; | |||
379 | } | |||
380 | ||||
381 | PHINode *PN = cast<PHINode>(D->front()); | |||
382 | Instruction *BEInst = D->back(); | |||
383 | int Iters = D->iterations(); | |||
384 | BasicBlock *BB = PN->getParent(); | |||
385 | LLVM_DEBUG(dbgs() << "Checking if any uses of " << *PNdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Checking if any uses of " << *PN << " can be reused\n"; } } while (false) | |||
386 | << " can be reused\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Checking if any uses of " << *PN << " can be reused\n"; } } while (false); | |||
387 | ||||
388 | SmallVector<Instruction *, 4> PNUsers; | |||
389 | for (Use &U : PN->uses()) { | |||
390 | Instruction *User = cast<Instruction>(U.getUser()); | |||
391 | ||||
392 | if (User->getParent() != BB) | |||
393 | continue; | |||
394 | if (ReplacedInsts.count(User)) { | |||
395 | LLVM_DEBUG(dbgs() << *Userdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << *User << " has already been replaced. Skipping...\n" ; } } while (false) | |||
396 | << " has already been replaced. Skipping...\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << *User << " has already been replaced. Skipping...\n" ; } } while (false); | |||
397 | continue; | |||
398 | } | |||
399 | if (isa<PHINode>(User)) | |||
400 | continue; | |||
401 | if (User->mayHaveSideEffects()) | |||
402 | continue; | |||
403 | if (!canReplace(User)) | |||
404 | continue; | |||
405 | ||||
406 | PNUsers.push_back(User); | |||
407 | } | |||
408 | LLVM_DEBUG(dbgs() << PNUsers.size() << " use(s) of the PHI in the block\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << PNUsers.size() << " use(s) of the PHI in the block\n" ; } } while (false); | |||
409 | ||||
410 | // For each interesting use I of PN, find an Instruction BEUser that | |||
411 | // performs the same operation as I on BEInst and whose other operands, | |||
412 | // if any, can also be rematerialized in OtherBB. We stop when we find the | |||
413 | // first such Instruction BEUser. This is because once BEUser is | |||
414 | // rematerialized in OtherBB, we may find more such "fixup" opportunities | |||
415 | // in this block. So, we'll start over again. | |||
416 | for (Instruction *I : PNUsers) { | |||
417 | for (Use &U : BEInst->uses()) { | |||
418 | Instruction *BEUser = cast<Instruction>(U.getUser()); | |||
419 | ||||
420 | if (BEUser->getParent() != BB) | |||
421 | continue; | |||
422 | if (!isEquivalentOperation(I, BEUser)) | |||
423 | continue; | |||
424 | ||||
425 | int NumOperands = I->getNumOperands(); | |||
426 | ||||
427 | // Take operands of each PNUser one by one and try to find DepChain | |||
428 | // with every operand of the BEUser. If any of the operands of BEUser | |||
429 | // has DepChain with current operand of the PNUser, break the matcher | |||
430 | // loop. Keep doing this for Every PNUser operand. If PNUser operand | |||
431 | // does not have DepChain with any of the BEUser operand, break the | |||
432 | // outer matcher loop, mark the BEUser as null and reset the ReuseCandidate. | |||
433 | // This ensures that DepChain exist for all the PNUser operand with | |||
434 | // BEUser operand. This also ensures that DepChains are independent of | |||
435 | // the positions in PNUser and BEUser. | |||
436 | std::map<Instruction *, DepChain *> DepChains; | |||
437 | CallInst *C1 = dyn_cast<CallInst>(I); | |||
438 | if ((I && I->isCommutative()) || (C1 && isCallInstCommutative(C1))) { | |||
439 | bool Found = false; | |||
440 | for (int OpNo = 0; OpNo < NumOperands; ++OpNo) { | |||
441 | Value *Op = I->getOperand(OpNo); | |||
442 | Instruction *OpInst = dyn_cast<Instruction>(Op); | |||
443 | Found = false; | |||
444 | for (int T = 0; T < NumOperands; ++T) { | |||
445 | Value *BEOp = BEUser->getOperand(T); | |||
446 | Instruction *BEOpInst = dyn_cast<Instruction>(BEOp); | |||
447 | if (!OpInst && !BEOpInst) { | |||
448 | if (Op == BEOp) { | |||
449 | Found = true; | |||
450 | break; | |||
451 | } | |||
452 | } | |||
453 | ||||
454 | if ((OpInst && !BEOpInst) || (!OpInst && BEOpInst)) | |||
455 | continue; | |||
456 | ||||
457 | DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters); | |||
458 | ||||
459 | if (D) { | |||
460 | Found = true; | |||
461 | DepChains[OpInst] = D; | |||
462 | break; | |||
463 | } | |||
464 | } | |||
465 | if (!Found) { | |||
466 | BEUser = nullptr; | |||
467 | break; | |||
468 | } | |||
469 | } | |||
470 | } else { | |||
471 | ||||
472 | for (int OpNo = 0; OpNo < NumOperands; ++OpNo) { | |||
473 | Value *Op = I->getOperand(OpNo); | |||
474 | Value *BEOp = BEUser->getOperand(OpNo); | |||
475 | ||||
476 | Instruction *OpInst = dyn_cast<Instruction>(Op); | |||
477 | if (!OpInst) { | |||
478 | if (Op == BEOp) | |||
479 | continue; | |||
480 | // Do not allow reuse to occur when the operands may be different | |||
481 | // values. | |||
482 | BEUser = nullptr; | |||
483 | break; | |||
484 | } | |||
485 | ||||
486 | Instruction *BEOpInst = dyn_cast<Instruction>(BEOp); | |||
487 | DepChain *D = getDepChainBtwn(OpInst, BEOpInst, Iters); | |||
488 | ||||
489 | if (D) { | |||
490 | DepChains[OpInst] = D; | |||
491 | } else { | |||
492 | BEUser = nullptr; | |||
493 | break; | |||
494 | } | |||
495 | } | |||
496 | } | |||
497 | if (BEUser) { | |||
498 | LLVM_DEBUG(dbgs() << "Found Value for reuse.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Found Value for reuse.\n" ; } } while (false); | |||
499 | ReuseCandidate.Inst2Replace = I; | |||
500 | ReuseCandidate.BackedgeInst = BEUser; | |||
501 | ReuseCandidate.DepChains = DepChains; | |||
502 | ReuseCandidate.Iterations = Iters; | |||
503 | return; | |||
504 | } | |||
505 | ReuseCandidate.reset(); | |||
506 | } | |||
507 | } | |||
508 | } | |||
509 | ReuseCandidate.reset(); | |||
510 | } | |||
511 | ||||
512 | Value *HexagonVectorLoopCarriedReuse::findValueInBlock(Value *Op, | |||
513 | BasicBlock *BB) { | |||
514 | PHINode *PN = dyn_cast<PHINode>(Op); | |||
515 | assert(PN)(static_cast <bool> (PN) ? void (0) : __assert_fail ("PN" , "llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp" , 515, __extension__ __PRETTY_FUNCTION__)); | |||
516 | Value *ValueInBlock = PN->getIncomingValueForBlock(BB); | |||
517 | return ValueInBlock; | |||
518 | } | |||
519 | ||||
520 | void HexagonVectorLoopCarriedReuse::reuseValue() { | |||
521 | LLVM_DEBUG(dbgs() << ReuseCandidate)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << ReuseCandidate; } } while (false); | |||
522 | Instruction *Inst2Replace = ReuseCandidate.Inst2Replace; | |||
523 | Instruction *BEInst = ReuseCandidate.BackedgeInst; | |||
524 | int NumOperands = Inst2Replace->getNumOperands(); | |||
525 | std::map<Instruction *, DepChain *> &DepChains = ReuseCandidate.DepChains; | |||
526 | int Iterations = ReuseCandidate.Iterations; | |||
527 | BasicBlock *LoopPH = CurLoop->getLoopPreheader(); | |||
528 | assert(!DepChains.empty() && "No DepChains")(static_cast <bool> (!DepChains.empty() && "No DepChains" ) ? void (0) : __assert_fail ("!DepChains.empty() && \"No DepChains\"" , "llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp" , 528, __extension__ __PRETTY_FUNCTION__)); | |||
529 | LLVM_DEBUG(dbgs() << "reuseValue is making the following changes\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "reuseValue is making the following changes\n" ; } } while (false); | |||
530 | ||||
531 | SmallVector<Instruction *, 4> InstsInPreheader; | |||
532 | for (int i = 0; i < Iterations; ++i) { | |||
533 | Instruction *InstInPreheader = Inst2Replace->clone(); | |||
534 | SmallVector<Value *, 4> Ops; | |||
535 | for (int j = 0; j < NumOperands; ++j) { | |||
536 | Instruction *I = dyn_cast<Instruction>(Inst2Replace->getOperand(j)); | |||
537 | if (!I) | |||
538 | continue; | |||
539 | // Get the DepChain corresponding to this operand. | |||
540 | DepChain &D = *DepChains[I]; | |||
541 | // Get the PHI for the iteration number and find | |||
542 | // the incoming value from the Loop Preheader for | |||
543 | // that PHI. | |||
544 | Value *ValInPreheader = findValueInBlock(D[i], LoopPH); | |||
545 | InstInPreheader->setOperand(j, ValInPreheader); | |||
546 | } | |||
547 | InstsInPreheader.push_back(InstInPreheader); | |||
548 | InstInPreheader->setName(Inst2Replace->getName() + ".hexagon.vlcr"); | |||
549 | InstInPreheader->insertBefore(LoopPH->getTerminator()); | |||
550 | LLVM_DEBUG(dbgs() << "Added " << *InstInPreheader << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Added " << *InstInPreheader << " to " << LoopPH->getName() << "\n"; } } while (false) | |||
551 | << LoopPH->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Added " << *InstInPreheader << " to " << LoopPH->getName() << "\n"; } } while (false); | |||
552 | } | |||
553 | BasicBlock *BB = BEInst->getParent(); | |||
554 | IRBuilder<> IRB(BB); | |||
555 | IRB.SetInsertPoint(BB->getFirstNonPHI()); | |||
556 | Value *BEVal = BEInst; | |||
557 | PHINode *NewPhi; | |||
558 | for (int i = Iterations-1; i >=0 ; --i) { | |||
559 | Instruction *InstInPreheader = InstsInPreheader[i]; | |||
560 | NewPhi = IRB.CreatePHI(InstInPreheader->getType(), 2); | |||
561 | NewPhi->addIncoming(InstInPreheader, LoopPH); | |||
562 | NewPhi->addIncoming(BEVal, BB); | |||
563 | LLVM_DEBUG(dbgs() << "Adding " << *NewPhi << " to " << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Adding " << *NewPhi << " to " << BB->getName() << "\n"; } } while (false) | |||
564 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Adding " << *NewPhi << " to " << BB->getName() << "\n"; } } while (false); | |||
565 | BEVal = NewPhi; | |||
566 | } | |||
567 | // We are in LCSSA form. So, a value defined inside the Loop is used only | |||
568 | // inside the loop. So, the following is safe. | |||
569 | Inst2Replace->replaceAllUsesWith(NewPhi); | |||
| ||||
570 | ReplacedInsts.insert(Inst2Replace); | |||
571 | ++HexagonNumVectorLoopCarriedReuse; | |||
572 | } | |||
573 | ||||
574 | bool HexagonVectorLoopCarriedReuse::doVLCR() { | |||
575 | assert(CurLoop->getSubLoops().empty() &&(static_cast <bool> (CurLoop->getSubLoops().empty() && "Can do VLCR on the innermost loop only") ? void (0) : __assert_fail ("CurLoop->getSubLoops().empty() && \"Can do VLCR on the innermost loop only\"" , "llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp" , 576, __extension__ __PRETTY_FUNCTION__)) | |||
576 | "Can do VLCR on the innermost loop only")(static_cast <bool> (CurLoop->getSubLoops().empty() && "Can do VLCR on the innermost loop only") ? void (0) : __assert_fail ("CurLoop->getSubLoops().empty() && \"Can do VLCR on the innermost loop only\"" , "llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp" , 576, __extension__ __PRETTY_FUNCTION__)); | |||
577 | assert((CurLoop->getNumBlocks() == 1) &&(static_cast <bool> ((CurLoop->getNumBlocks() == 1) && "Can do VLCR only on single block loops") ? void (0) : __assert_fail ("(CurLoop->getNumBlocks() == 1) && \"Can do VLCR only on single block loops\"" , "llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp" , 578, __extension__ __PRETTY_FUNCTION__)) | |||
578 | "Can do VLCR only on single block loops")(static_cast <bool> ((CurLoop->getNumBlocks() == 1) && "Can do VLCR only on single block loops") ? void (0) : __assert_fail ("(CurLoop->getNumBlocks() == 1) && \"Can do VLCR only on single block loops\"" , "llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp" , 578, __extension__ __PRETTY_FUNCTION__)); | |||
579 | ||||
580 | bool Changed = false; | |||
581 | bool Continue; | |||
582 | ||||
583 | LLVM_DEBUG(dbgs() << "Working on Loop: " << *CurLoop->getHeader() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Working on Loop: " << *CurLoop->getHeader() << "\n"; } } while (false); | |||
584 | do { | |||
585 | // Reset datastructures. | |||
586 | Dependences.clear(); | |||
587 | Continue = false; | |||
588 | ||||
589 | findLoopCarriedDeps(); | |||
590 | findValueToReuse(); | |||
591 | if (ReuseCandidate.isDefined()) { | |||
592 | reuseValue(); | |||
593 | Changed = true; | |||
594 | Continue = true; | |||
595 | } | |||
596 | llvm::for_each(Dependences, std::default_delete<DepChain>()); | |||
597 | } while (Continue); | |||
598 | return Changed; | |||
599 | } | |||
600 | ||||
601 | void HexagonVectorLoopCarriedReuse::findDepChainFromPHI(Instruction *I, | |||
602 | DepChain &D) { | |||
603 | PHINode *PN = dyn_cast<PHINode>(I); | |||
604 | if (!PN) { | |||
605 | D.push_back(I); | |||
606 | return; | |||
607 | } else { | |||
608 | auto NumIncomingValues = PN->getNumIncomingValues(); | |||
609 | if (NumIncomingValues != 2) { | |||
610 | D.clear(); | |||
611 | return; | |||
612 | } | |||
613 | ||||
614 | BasicBlock *BB = PN->getParent(); | |||
615 | if (BB != CurLoop->getHeader()) { | |||
616 | D.clear(); | |||
617 | return; | |||
618 | } | |||
619 | ||||
620 | Value *BEVal = PN->getIncomingValueForBlock(BB); | |||
621 | Instruction *BEInst = dyn_cast<Instruction>(BEVal); | |||
622 | // This is a single block loop with a preheader, so at least | |||
623 | // one value should come over the backedge. | |||
624 | assert(BEInst && "There should be a value over the backedge")(static_cast <bool> (BEInst && "There should be a value over the backedge" ) ? void (0) : __assert_fail ("BEInst && \"There should be a value over the backedge\"" , "llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp" , 624, __extension__ __PRETTY_FUNCTION__)); | |||
625 | ||||
626 | Value *PreHdrVal = | |||
627 | PN->getIncomingValueForBlock(CurLoop->getLoopPreheader()); | |||
628 | if(!PreHdrVal || !isa<Instruction>(PreHdrVal)) { | |||
629 | D.clear(); | |||
630 | return; | |||
631 | } | |||
632 | D.push_back(PN); | |||
633 | findDepChainFromPHI(BEInst, D); | |||
634 | } | |||
635 | } | |||
636 | ||||
637 | DepChain *HexagonVectorLoopCarriedReuse::getDepChainBtwn(Instruction *I1, | |||
638 | Instruction *I2, | |||
639 | int Iters) { | |||
640 | for (auto *D : Dependences) { | |||
641 | if (D->front() == I1 && D->back() == I2 && D->iterations() == Iters) | |||
642 | return D; | |||
643 | } | |||
644 | return nullptr; | |||
645 | } | |||
646 | ||||
647 | void HexagonVectorLoopCarriedReuse::findLoopCarriedDeps() { | |||
648 | BasicBlock *BB = CurLoop->getHeader(); | |||
649 | for (auto I = BB->begin(), E = BB->end(); I != E && isa<PHINode>(I); ++I) { | |||
650 | auto *PN = cast<PHINode>(I); | |||
651 | if (!isa<VectorType>(PN->getType())) | |||
652 | continue; | |||
653 | ||||
654 | DepChain *D = new DepChain(); | |||
655 | findDepChainFromPHI(PN, *D); | |||
656 | if (D->size() != 0) | |||
657 | Dependences.insert(D); | |||
658 | else | |||
659 | delete D; | |||
660 | } | |||
661 | LLVM_DEBUG(dbgs() << "Found " << Dependences.size() << " dependences\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { dbgs() << "Found " << Dependences .size() << " dependences\n"; } } while (false); | |||
662 | LLVM_DEBUG(for (const DepChain *D : Dependences) dbgs() << *D << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("hexagon-vlcr")) { for (const DepChain *D : Dependences) dbgs () << *D << "\n";; } } while (false); | |||
663 | } | |||
664 | ||||
665 | Pass *llvm::createHexagonVectorLoopCarriedReuseLegacyPass() { | |||
666 | return new HexagonVectorLoopCarriedReuseLegacyPass(); | |||
667 | } |