Bug Summary

File:build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp
Warning:line 569, column 3
1st function call argument is an uninitialized value

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name HexagonVectorLoopCarriedReuse.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-15/lib/clang/15.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Target/Hexagon -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Target/Hexagon -I include -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-15/lib/clang/15.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -ferror-limit 19 -fvisibility hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-04-20-140412-16051-1 -x c++ /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Target/Hexagon/HexagonVectorLoopCarriedReuse.cpp
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
49using namespace llvm;
50
51#define DEBUG_TYPE"hexagon-vlcr" "hexagon-vlcr"
52
53STATISTIC(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
56static cl::opt<int> HexagonVLCRIterationLim("hexagon-vlcr-iteration-lim",
57 cl::Hidden,
58 cl::desc("Maximum distance of loop carried dependences that are handled"),
59 cl::init(2), cl::ZeroOrMore);
60
61namespace llvm {
62
63void initializeHexagonVectorLoopCarriedReuseLegacyPassPass(PassRegistry &);
64Pass *createHexagonVectorLoopCarriedReuseLegacyPass();
65
66} // end namespace llvm
67
68namespace {
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
213char HexagonVectorLoopCarriedReuseLegacyPass::ID = 0;
214
215INITIALIZE_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) {
218INITIALIZE_PASS_DEPENDENCY(LoopSimplify)initializeLoopSimplifyPass(Registry);
219INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)initializeLCSSAWrapperPassPass(Registry);
220INITIALIZE_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
224PreservedAnalyses
225HexagonVectorLoopCarriedReusePass::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
236bool HexagonVectorLoopCarriedReuseLegacyPass::runOnLoop(Loop *L,
237 LPPassManager &LPM) {
238 if (skipLoop(L))
1
Assuming the condition is false
2
Taking false branch
239 return false;
240 HexagonVectorLoopCarriedReuse Vlcr(L);
241 return Vlcr.run();
3
Calling 'HexagonVectorLoopCarriedReuse::run'
242}
243
244bool HexagonVectorLoopCarriedReuse::run() {
245 if (!CurLoop->getLoopPreheader())
4
Assuming the condition is false
5
Taking false branch
246 return false;
247
248 // Work only on innermost loops.
249 if (!CurLoop->getSubLoops().empty())
6
Assuming the condition is false
7
Taking false branch
250 return false;
251
252 // Work only on single basic blocks loops.
253 if (CurLoop->getNumBlocks() != 1)
8
Assuming the condition is false
9
Taking false branch
254 return false;
255
256 return doVLCR();
10
Calling 'HexagonVectorLoopCarriedReuse::doVLCR'
257}
258
259bool 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
323bool 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
355bool 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}
371void 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
512Value *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
520void HexagonVectorLoopCarriedReuse::reuseValue() {
521 LLVM_DEBUG(dbgs() << ReuseCandidate)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("hexagon-vlcr")) { dbgs() << ReuseCandidate; } } while
(false)
;
19
Assuming 'DebugFlag' is false
20
Loop condition is false. Exiting loop
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__))
;
21
Assuming the condition is true
22
'?' condition is true
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)
;
23
Assuming 'DebugFlag' is false
24
Loop condition is false. Exiting loop
530
531 SmallVector<Instruction *, 4> InstsInPreheader;
532 for (int i = 0; i < Iterations; ++i) {
25
Assuming 'i' is >= 'Iterations'
26
Loop condition is false. Execution continues on line 553
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;
27
'NewPhi' declared without an initial value
558 for (int i = Iterations-1; i >=0 ; --i) {
28
Assuming 'i' is < 0
29
Loop condition is false. Execution continues on line 569
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);
30
1st function call argument is an uninitialized value
570 ReplacedInsts.insert(Inst2Replace);
571 ++HexagonNumVectorLoopCarriedReuse;
572}
573
574bool 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__))
11
Assuming the condition is true
12
'?' condition is true
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__))
13
Assuming the condition is true
14
'?' condition is true
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)
;
15
Assuming 'DebugFlag' is false
16
Loop condition is false. Exiting loop
584 do {
585 // Reset datastructures.
586 Dependences.clear();
587 Continue = false;
588
589 findLoopCarriedDeps();
590 findValueToReuse();
591 if (ReuseCandidate.isDefined()) {
17
Taking true branch
592 reuseValue();
18
Calling 'HexagonVectorLoopCarriedReuse::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
601void 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
637DepChain *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
647void 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
665Pass *llvm::createHexagonVectorLoopCarriedReuseLegacyPass() {
666 return new HexagonVectorLoopCarriedReuseLegacyPass();
667}