/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/VectorUtils.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===----------- VectorUtils.cpp - Vectorizer utility functions -----------===// |
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 | | // This file defines vectorizer utilities. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "llvm/Analysis/VectorUtils.h" |
15 | | #include "llvm/ADT/EquivalenceClasses.h" |
16 | | #include "llvm/Analysis/DemandedBits.h" |
17 | | #include "llvm/Analysis/LoopInfo.h" |
18 | | #include "llvm/Analysis/ScalarEvolution.h" |
19 | | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
20 | | #include "llvm/Analysis/TargetTransformInfo.h" |
21 | | #include "llvm/Analysis/ValueTracking.h" |
22 | | #include "llvm/IR/Constants.h" |
23 | | #include "llvm/IR/GetElementPtrTypeIterator.h" |
24 | | #include "llvm/IR/IRBuilder.h" |
25 | | #include "llvm/IR/PatternMatch.h" |
26 | | #include "llvm/IR/Value.h" |
27 | | |
28 | | using namespace llvm; |
29 | | using namespace llvm::PatternMatch; |
30 | | |
31 | | /// \brief Identify if the intrinsic is trivially vectorizable. |
32 | | /// This method returns true if the intrinsic's argument types are all |
33 | | /// scalars for the scalar form of the intrinsic and all vectors for |
34 | | /// the vector form of the intrinsic. |
35 | 32.9k | bool llvm::isTriviallyVectorizable(Intrinsic::ID ID) { |
36 | 32.9k | switch (ID) { |
37 | 18.7k | case Intrinsic::sqrt: |
38 | 18.7k | case Intrinsic::sin: |
39 | 18.7k | case Intrinsic::cos: |
40 | 18.7k | case Intrinsic::exp: |
41 | 18.7k | case Intrinsic::exp2: |
42 | 18.7k | case Intrinsic::log: |
43 | 18.7k | case Intrinsic::log10: |
44 | 18.7k | case Intrinsic::log2: |
45 | 18.7k | case Intrinsic::fabs: |
46 | 18.7k | case Intrinsic::minnum: |
47 | 18.7k | case Intrinsic::maxnum: |
48 | 18.7k | case Intrinsic::copysign: |
49 | 18.7k | case Intrinsic::floor: |
50 | 18.7k | case Intrinsic::ceil: |
51 | 18.7k | case Intrinsic::trunc: |
52 | 18.7k | case Intrinsic::rint: |
53 | 18.7k | case Intrinsic::nearbyint: |
54 | 18.7k | case Intrinsic::round: |
55 | 18.7k | case Intrinsic::bswap: |
56 | 18.7k | case Intrinsic::bitreverse: |
57 | 18.7k | case Intrinsic::ctpop: |
58 | 18.7k | case Intrinsic::pow: |
59 | 18.7k | case Intrinsic::fma: |
60 | 18.7k | case Intrinsic::fmuladd: |
61 | 18.7k | case Intrinsic::ctlz: |
62 | 18.7k | case Intrinsic::cttz: |
63 | 18.7k | case Intrinsic::powi: |
64 | 18.7k | return true; |
65 | 14.1k | default: |
66 | 14.1k | return false; |
67 | 0 | } |
68 | 0 | } |
69 | | |
70 | | /// \brief Identifies if the intrinsic has a scalar operand. It check for |
71 | | /// ctlz,cttz and powi special intrinsics whose argument is scalar. |
72 | | bool llvm::hasVectorInstrinsicScalarOpd(Intrinsic::ID ID, |
73 | 11.4k | unsigned ScalarOpdIdx) { |
74 | 11.4k | switch (ID) { |
75 | 2.41k | case Intrinsic::ctlz: |
76 | 2.41k | case Intrinsic::cttz: |
77 | 2.41k | case Intrinsic::powi: |
78 | 2.41k | return (ScalarOpdIdx == 1); |
79 | 9.08k | default: |
80 | 9.08k | return false; |
81 | 0 | } |
82 | 0 | } |
83 | | |
84 | | /// \brief Returns intrinsic ID for call. |
85 | | /// For the input call instruction it finds mapping intrinsic and returns |
86 | | /// its ID, in case it does not found it return not_intrinsic. |
87 | | Intrinsic::ID llvm::getVectorIntrinsicIDForCall(const CallInst *CI, |
88 | 97.6k | const TargetLibraryInfo *TLI) { |
89 | 97.6k | Intrinsic::ID ID = getIntrinsicForCallSite(CI, TLI); |
90 | 97.6k | if (ID == Intrinsic::not_intrinsic) |
91 | 73.9k | return Intrinsic::not_intrinsic; |
92 | 23.7k | |
93 | 23.7k | if (23.7k isTriviallyVectorizable(ID) || 23.7k ID == Intrinsic::lifetime_start7.36k || |
94 | 23.7k | ID == Intrinsic::lifetime_end7.25k || ID == Intrinsic::assume7.21k ) |
95 | 16.5k | return ID; |
96 | 7.19k | return Intrinsic::not_intrinsic; |
97 | 7.19k | } |
98 | | |
99 | | /// \brief Find the operand of the GEP that should be checked for consecutive |
100 | | /// stores. This ignores trailing indices that have no effect on the final |
101 | | /// pointer. |
102 | 240k | unsigned llvm::getGEPInductionOperand(const GetElementPtrInst *Gep) { |
103 | 240k | const DataLayout &DL = Gep->getModule()->getDataLayout(); |
104 | 240k | unsigned LastOperand = Gep->getNumOperands() - 1; |
105 | 240k | unsigned GEPAllocSize = DL.getTypeAllocSize(Gep->getResultElementType()); |
106 | 240k | |
107 | 240k | // Walk backwards and try to peel off zeros. |
108 | 240k | while (LastOperand > 1 && 240k match(Gep->getOperand(LastOperand), m_Zero())122k ) { |
109 | 8.52k | // Find the type we're currently indexing into. |
110 | 8.52k | gep_type_iterator GEPTI = gep_type_begin(Gep); |
111 | 8.52k | std::advance(GEPTI, LastOperand - 2); |
112 | 8.52k | |
113 | 8.52k | // If it's a type with the same allocation size as the result of the GEP we |
114 | 8.52k | // can peel off the zero index. |
115 | 8.52k | if (DL.getTypeAllocSize(GEPTI.getIndexedType()) != GEPAllocSize) |
116 | 8.03k | break; |
117 | 489 | --LastOperand; |
118 | 489 | } |
119 | 240k | |
120 | 240k | return LastOperand; |
121 | 240k | } |
122 | | |
123 | | /// \brief If the argument is a GEP, then returns the operand identified by |
124 | | /// getGEPInductionOperand. However, if there is some other non-loop-invariant |
125 | | /// operand, it returns that instead. |
126 | 363k | Value *llvm::stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp) { |
127 | 363k | GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr); |
128 | 363k | if (!GEP) |
129 | 123k | return Ptr; |
130 | 240k | |
131 | 240k | unsigned InductionOperand = getGEPInductionOperand(GEP); |
132 | 240k | |
133 | 240k | // Check that all of the gep indices are uniform except for our induction |
134 | 240k | // operand. |
135 | 741k | for (unsigned i = 0, e = GEP->getNumOperands(); i != e741k ; ++i501k ) |
136 | 578k | if (578k i != InductionOperand && |
137 | 415k | !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp)) |
138 | 77.0k | return Ptr; |
139 | 163k | return GEP->getOperand(InductionOperand); |
140 | 363k | } |
141 | | |
142 | | /// \brief If a value has only one user that is a CastInst, return it. |
143 | 3.07k | Value *llvm::getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) { |
144 | 3.07k | Value *UniqueCast = nullptr; |
145 | 10.7k | for (User *U : Ptr->users()) { |
146 | 10.7k | CastInst *CI = dyn_cast<CastInst>(U); |
147 | 10.7k | if (CI && 10.7k CI->getType() == Ty3.87k ) { |
148 | 3.87k | if (!UniqueCast) |
149 | 3.07k | UniqueCast = CI; |
150 | 3.87k | else |
151 | 800 | return nullptr; |
152 | 2.27k | } |
153 | 10.7k | } |
154 | 2.27k | return UniqueCast; |
155 | 2.27k | } |
156 | | |
157 | | /// \brief Get the stride of a pointer access in a loop. Looks for symbolic |
158 | | /// strides "a[i*stride]". Returns the symbolic stride, or null otherwise. |
159 | 363k | Value *llvm::getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp) { |
160 | 363k | auto *PtrTy = dyn_cast<PointerType>(Ptr->getType()); |
161 | 363k | if (!PtrTy || 363k PtrTy->isAggregateType()363k ) |
162 | 0 | return nullptr; |
163 | 363k | |
164 | 363k | // Try to remove a gep instruction to make the pointer (actually index at this |
165 | 363k | // point) easier analyzable. If OrigPtr is equal to Ptr we are analzying the |
166 | 363k | // pointer, otherwise, we are analyzing the index. |
167 | 363k | Value *OrigPtr = Ptr; |
168 | 363k | |
169 | 363k | // The size of the pointer access. |
170 | 363k | int64_t PtrAccessSize = 1; |
171 | 363k | |
172 | 363k | Ptr = stripGetElementPtr(Ptr, SE, Lp); |
173 | 363k | const SCEV *V = SE->getSCEV(Ptr); |
174 | 363k | |
175 | 363k | if (Ptr != OrigPtr) |
176 | 363k | // Strip off casts. |
177 | 172k | while (const SCEVCastExpr *163k C172k = dyn_cast<SCEVCastExpr>(V)) |
178 | 8.72k | V = C->getOperand(); |
179 | 363k | |
180 | 363k | const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V); |
181 | 363k | if (!S) |
182 | 70.5k | return nullptr; |
183 | 293k | |
184 | 293k | V = S->getStepRecurrence(*SE); |
185 | 293k | if (!V) |
186 | 0 | return nullptr; |
187 | 293k | |
188 | 293k | // Strip off the size of access multiplication if we are still analyzing the |
189 | 293k | // pointer. |
190 | 293k | if (293k OrigPtr == Ptr293k ) { |
191 | 144k | if (const SCEVMulExpr *M144k = dyn_cast<SCEVMulExpr>(V)) { |
192 | 28.5k | if (M->getOperand(0)->getSCEVType() != scConstant) |
193 | 0 | return nullptr; |
194 | 28.5k | |
195 | 28.5k | const APInt &APStepVal = cast<SCEVConstant>(M->getOperand(0))->getAPInt(); |
196 | 28.5k | |
197 | 28.5k | // Huge step value - give up. |
198 | 28.5k | if (APStepVal.getBitWidth() > 64) |
199 | 0 | return nullptr; |
200 | 28.5k | |
201 | 28.5k | int64_t StepVal = APStepVal.getSExtValue(); |
202 | 28.5k | if (PtrAccessSize != StepVal) |
203 | 28.5k | return nullptr; |
204 | 0 | V = M->getOperand(1); |
205 | 0 | } |
206 | 144k | } |
207 | 293k | |
208 | 293k | // Strip off casts. |
209 | 264k | Type *StripedOffRecurrenceCast = nullptr; |
210 | 264k | if (const SCEVCastExpr *C264k = dyn_cast<SCEVCastExpr>(V)) { |
211 | 3.37k | StripedOffRecurrenceCast = C->getType(); |
212 | 3.37k | V = C->getOperand(); |
213 | 3.37k | } |
214 | 264k | |
215 | 264k | // Look for the loop invariant symbolic value. |
216 | 264k | const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V); |
217 | 264k | if (!U) |
218 | 261k | return nullptr; |
219 | 3.16k | |
220 | 3.16k | Value *Stride = U->getValue(); |
221 | 3.16k | if (!Lp->isLoopInvariant(Stride)) |
222 | 0 | return nullptr; |
223 | 3.16k | |
224 | 3.16k | // If we have stripped off the recurrence cast we have to make sure that we |
225 | 3.16k | // return the value that is used in this loop so that we can replace it later. |
226 | 3.16k | if (3.16k StripedOffRecurrenceCast3.16k ) |
227 | 3.07k | Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast); |
228 | 363k | |
229 | 363k | return Stride; |
230 | 363k | } |
231 | | |
232 | | /// \brief Given a vector and an element number, see if the scalar value is |
233 | | /// already around as a register, for example if it were inserted then extracted |
234 | | /// from the vector. |
235 | 280k | Value *llvm::findScalarElement(Value *V, unsigned EltNo) { |
236 | 280k | assert(V->getType()->isVectorTy() && "Not looking at a vector?"); |
237 | 280k | VectorType *VTy = cast<VectorType>(V->getType()); |
238 | 280k | unsigned Width = VTy->getNumElements(); |
239 | 280k | if (EltNo >= Width) // Out of range access. |
240 | 1 | return UndefValue::get(VTy->getElementType()); |
241 | 280k | |
242 | 280k | if (Constant *280k C280k = dyn_cast<Constant>(V)) |
243 | 18 | return C->getAggregateElement(EltNo); |
244 | 280k | |
245 | 280k | if (InsertElementInst *280k III280k = dyn_cast<InsertElementInst>(V)) { |
246 | 35.6k | // If this is an insert to a variable element, we don't know what it is. |
247 | 35.6k | if (!isa<ConstantInt>(III->getOperand(2))) |
248 | 3.09k | return nullptr; |
249 | 32.5k | unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue(); |
250 | 32.5k | |
251 | 32.5k | // If this is an insert to the element we are looking for, return the |
252 | 32.5k | // inserted value. |
253 | 32.5k | if (EltNo == IIElt) |
254 | 327 | return III->getOperand(1); |
255 | 32.2k | |
256 | 32.2k | // Otherwise, the insertelement doesn't modify the value, recurse on its |
257 | 32.2k | // vector input. |
258 | 32.2k | return findScalarElement(III->getOperand(0), EltNo); |
259 | 32.2k | } |
260 | 244k | |
261 | 244k | if (ShuffleVectorInst *244k SVI244k = dyn_cast<ShuffleVectorInst>(V)) { |
262 | 349 | unsigned LHSWidth = SVI->getOperand(0)->getType()->getVectorNumElements(); |
263 | 349 | int InEl = SVI->getMaskValue(EltNo); |
264 | 349 | if (InEl < 0) |
265 | 0 | return UndefValue::get(VTy->getElementType()); |
266 | 349 | if (349 InEl < (int)LHSWidth349 ) |
267 | 305 | return findScalarElement(SVI->getOperand(0), InEl); |
268 | 44 | return findScalarElement(SVI->getOperand(1), InEl - LHSWidth); |
269 | 44 | } |
270 | 244k | |
271 | 244k | // Extract a value from a vector add operation with a constant zero. |
272 | 244k | Value *Val = nullptr; Constant *Con = nullptr; |
273 | 244k | if (match(V, m_Add(m_Value(Val), m_Constant(Con)))) |
274 | 948 | if (Constant *948 Elt948 = Con->getAggregateElement(EltNo)) |
275 | 947 | if (947 Elt->isNullValue()947 ) |
276 | 8 | return findScalarElement(Val, EltNo); |
277 | 244k | |
278 | 244k | // Otherwise, we don't know. |
279 | 244k | return nullptr; |
280 | 244k | } |
281 | | |
282 | | /// \brief Get splat value if the input is a splat vector or return nullptr. |
283 | | /// This function is not fully general. It checks only 2 cases: |
284 | | /// the input value is (1) a splat constants vector or (2) a sequence |
285 | | /// of instructions that broadcast a single value into a vector. |
286 | | /// |
287 | 3.57M | const llvm::Value *llvm::getSplatValue(const Value *V) { |
288 | 3.57M | |
289 | 3.57M | if (auto *C = dyn_cast<Constant>(V)) |
290 | 7.60k | if (7.60k isa<VectorType>(V->getType())7.60k ) |
291 | 6.47k | return C->getSplatValue(); |
292 | 3.56M | |
293 | 3.56M | auto *ShuffleInst = dyn_cast<ShuffleVectorInst>(V); |
294 | 3.56M | if (!ShuffleInst) |
295 | 3.56M | return nullptr; |
296 | 792 | // All-zero (or undef) shuffle mask elements. |
297 | 792 | for (int MaskElt : ShuffleInst->getShuffleMask()) |
298 | 9.02k | if (9.02k MaskElt != 0 && 9.02k MaskElt != -1412 ) |
299 | 248 | return nullptr; |
300 | 544 | // The first shuffle source is 'insertelement' with index 0. |
301 | 544 | auto *InsertEltInst = |
302 | 544 | dyn_cast<InsertElementInst>(ShuffleInst->getOperand(0)); |
303 | 544 | if (!InsertEltInst || 544 !isa<ConstantInt>(InsertEltInst->getOperand(2))500 || |
304 | 500 | !cast<ConstantInt>(InsertEltInst->getOperand(2))->isZero()) |
305 | 49 | return nullptr; |
306 | 495 | |
307 | 495 | return InsertEltInst->getOperand(1); |
308 | 495 | } |
309 | | |
310 | | MapVector<Instruction *, uint64_t> |
311 | | llvm::computeMinimumValueSizes(ArrayRef<BasicBlock *> Blocks, DemandedBits &DB, |
312 | 27.9k | const TargetTransformInfo *TTI) { |
313 | 27.9k | |
314 | 27.9k | // DemandedBits will give us every value's live-out bits. But we want |
315 | 27.9k | // to ensure no extra casts would need to be inserted, so every DAG |
316 | 27.9k | // of connected values must have the same minimum bitwidth. |
317 | 27.9k | EquivalenceClasses<Value *> ECs; |
318 | 27.9k | SmallVector<Value *, 16> Worklist; |
319 | 27.9k | SmallPtrSet<Value *, 4> Roots; |
320 | 27.9k | SmallPtrSet<Value *, 16> Visited; |
321 | 27.9k | DenseMap<Value *, uint64_t> DBits; |
322 | 27.9k | SmallPtrSet<Instruction *, 4> InstructionSet; |
323 | 27.9k | MapVector<Instruction *, uint64_t> MinBWs; |
324 | 27.9k | |
325 | 27.9k | // Determine the roots. We work bottom-up, from truncs or icmps. |
326 | 27.9k | bool SeenExtFromIllegalType = false; |
327 | 27.9k | for (auto *BB : Blocks) |
328 | 28.8k | for (auto &I : *BB) 28.8k { |
329 | 355k | InstructionSet.insert(&I); |
330 | 355k | |
331 | 355k | if (TTI && 355k (isa<ZExtInst>(&I) || 355k isa<SExtInst>(&I)352k ) && |
332 | 5.49k | !TTI->isTypeLegal(I.getOperand(0)->getType())) |
333 | 3.31k | SeenExtFromIllegalType = true; |
334 | 355k | |
335 | 355k | // Only deal with non-vector integers up to 64-bits wide. |
336 | 355k | if ((isa<TruncInst>(&I) || 355k isa<ICmpInst>(&I)336k ) && |
337 | 49.0k | !I.getType()->isVectorTy() && |
338 | 355k | I.getOperand(0)->getType()->getScalarSizeInBits() <= 6449.0k ) { |
339 | 49.0k | // Don't make work for ourselves. If we know the loaded type is legal, |
340 | 49.0k | // don't add it to the worklist. |
341 | 49.0k | if (TTI && 49.0k isa<TruncInst>(&I)49.0k && TTI->isTypeLegal(I.getType())18.2k ) |
342 | 16.4k | continue; |
343 | 32.5k | |
344 | 32.5k | Worklist.push_back(&I); |
345 | 32.5k | Roots.insert(&I); |
346 | 32.5k | } |
347 | 28.8k | } |
348 | 27.9k | // Early exit. |
349 | 27.9k | if (Worklist.empty() || 27.9k (TTI && 27.9k !SeenExtFromIllegalType27.9k )) |
350 | 26.4k | return MinBWs; |
351 | 1.56k | |
352 | 1.56k | // Now proceed breadth-first, unioning values together. |
353 | 18.2k | while (1.56k !Worklist.empty()18.2k ) { |
354 | 16.6k | Value *Val = Worklist.pop_back_val(); |
355 | 16.6k | Value *Leader = ECs.getOrInsertLeaderValue(Val); |
356 | 16.6k | |
357 | 16.6k | if (Visited.count(Val)) |
358 | 2.65k | continue; |
359 | 13.9k | Visited.insert(Val); |
360 | 13.9k | |
361 | 13.9k | // Non-instructions terminate a chain successfully. |
362 | 13.9k | if (!isa<Instruction>(Val)) |
363 | 2.59k | continue; |
364 | 11.3k | Instruction *I = cast<Instruction>(Val); |
365 | 11.3k | |
366 | 11.3k | // If we encounter a type that is larger than 64 bits, we can't represent |
367 | 11.3k | // it so bail out. |
368 | 11.3k | if (DB.getDemandedBits(I).getBitWidth() > 64) |
369 | 0 | return MapVector<Instruction *, uint64_t>(); |
370 | 11.3k | |
371 | 11.3k | uint64_t V = DB.getDemandedBits(I).getZExtValue(); |
372 | 11.3k | DBits[Leader] |= V; |
373 | 11.3k | DBits[I] = V; |
374 | 11.3k | |
375 | 11.3k | // Casts, loads and instructions outside of our range terminate a chain |
376 | 11.3k | // successfully. |
377 | 11.3k | if (isa<SExtInst>(I) || 11.3k isa<ZExtInst>(I)10.7k || isa<LoadInst>(I)9.79k || |
378 | 8.86k | !InstructionSet.count(I)) |
379 | 2.92k | continue; |
380 | 8.47k | |
381 | 8.47k | // Unsafe casts terminate a chain unsuccessfully. We can't do anything |
382 | 8.47k | // useful with bitcasts, ptrtoints or inttoptrs and it'd be unsafe to |
383 | 8.47k | // transform anything that relies on them. |
384 | 8.47k | if (8.47k isa<BitCastInst>(I) || 8.47k isa<PtrToIntInst>(I)8.47k || isa<IntToPtrInst>(I)8.47k || |
385 | 8.47k | !I->getType()->isIntegerTy()8.47k ) { |
386 | 36 | DBits[Leader] |= ~0ULL; |
387 | 36 | continue; |
388 | 36 | } |
389 | 8.43k | |
390 | 8.43k | // We don't modify the types of PHIs. Reductions will already have been |
391 | 8.43k | // truncated if possible, and inductions' sizes will have been chosen by |
392 | 8.43k | // indvars. |
393 | 8.43k | if (8.43k isa<PHINode>(I)8.43k ) |
394 | 379 | continue; |
395 | 8.05k | |
396 | 8.05k | if (8.05k DBits[Leader] == ~0ULL8.05k ) |
397 | 8.05k | // All bits demanded, no point continuing. |
398 | 1.29k | continue; |
399 | 6.76k | |
400 | 6.76k | for (Value *O : cast<User>(I)->operands()) 6.76k { |
401 | 13.1k | ECs.unionSets(Leader, O); |
402 | 13.1k | Worklist.push_back(O); |
403 | 13.1k | } |
404 | 16.6k | } |
405 | 1.56k | |
406 | 1.56k | // Now we've discovered all values, walk them to see if there are |
407 | 1.56k | // any users we didn't see. If there are, we can't optimize that |
408 | 1.56k | // chain. |
409 | 1.56k | for (auto &I : DBits) |
410 | 11.3k | for (auto *U : I.first->users()) |
411 | 19.0k | if (19.0k U->getType()->isIntegerTy() && 19.0k DBits.count(U) == 016.5k ) |
412 | 6.55k | DBits[ECs.getOrInsertLeaderValue(I.first)] |= ~0ULL; |
413 | 1.56k | |
414 | 15.5k | for (auto I = ECs.begin(), E = ECs.end(); I != E15.5k ; ++I13.9k ) { |
415 | 13.9k | uint64_t LeaderDemandedBits = 0; |
416 | 27.9k | for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME27.9k ; ++MI13.9k ) |
417 | 13.9k | LeaderDemandedBits |= DBits[*MI]; |
418 | 13.9k | |
419 | 13.9k | uint64_t MinBW = (sizeof(LeaderDemandedBits) * 8) - |
420 | 13.9k | llvm::countLeadingZeros(LeaderDemandedBits); |
421 | 13.9k | // Round up to a power of 2 |
422 | 13.9k | if (!isPowerOf2_64((uint64_t)MinBW)) |
423 | 11.6k | MinBW = NextPowerOf2(MinBW); |
424 | 13.9k | |
425 | 13.9k | // We don't modify the types of PHIs. Reductions will already have been |
426 | 13.9k | // truncated if possible, and inductions' sizes will have been chosen by |
427 | 13.9k | // indvars. |
428 | 13.9k | // If we are required to shrink a PHI, abandon this entire equivalence class. |
429 | 13.9k | bool Abort = false; |
430 | 27.9k | for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME27.9k ; ++MI13.9k ) |
431 | 13.9k | if (13.9k isa<PHINode>(*MI) && 13.9k MinBW < (*MI)->getType()->getScalarSizeInBits()431 ) { |
432 | 0 | Abort = true; |
433 | 0 | break; |
434 | 0 | } |
435 | 13.9k | if (Abort) |
436 | 0 | continue; |
437 | 13.9k | |
438 | 27.9k | for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); 13.9k MI != ME27.9k ; ++MI13.9k ) { |
439 | 13.9k | if (!isa<Instruction>(*MI)) |
440 | 2.59k | continue; |
441 | 11.3k | Type *Ty = (*MI)->getType(); |
442 | 11.3k | if (Roots.count(*MI)) |
443 | 3.51k | Ty = cast<Instruction>(*MI)->getOperand(0)->getType(); |
444 | 11.3k | if (MinBW < Ty->getScalarSizeInBits()) |
445 | 450 | MinBWs[cast<Instruction>(*MI)] = MinBW; |
446 | 13.9k | } |
447 | 13.9k | } |
448 | 1.56k | |
449 | 1.56k | return MinBWs; |
450 | 27.9k | } |
451 | | |
452 | | /// \returns \p I after propagating metadata from \p VL. |
453 | 208k | Instruction *llvm::propagateMetadata(Instruction *Inst, ArrayRef<Value *> VL) { |
454 | 208k | Instruction *I0 = cast<Instruction>(VL[0]); |
455 | 208k | SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata; |
456 | 208k | I0->getAllMetadataOtherThanDebugLoc(Metadata); |
457 | 208k | |
458 | 208k | for (auto Kind : |
459 | 208k | {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, |
460 | 208k | LLVMContext::MD_noalias, LLVMContext::MD_fpmath, |
461 | 1.25M | LLVMContext::MD_nontemporal, LLVMContext::MD_invariant_load}) { |
462 | 1.25M | MDNode *MD = I0->getMetadata(Kind); |
463 | 1.25M | |
464 | 1.29M | for (int J = 1, E = VL.size(); MD && 1.29M J != E110k ; ++J44.2k ) { |
465 | 44.2k | const Instruction *IJ = cast<Instruction>(VL[J]); |
466 | 44.2k | MDNode *IMD = IJ->getMetadata(Kind); |
467 | 44.2k | switch (Kind) { |
468 | 44.1k | case LLVMContext::MD_tbaa: |
469 | 44.1k | MD = MDNode::getMostGenericTBAA(MD, IMD); |
470 | 44.1k | break; |
471 | 68 | case LLVMContext::MD_alias_scope: |
472 | 68 | MD = MDNode::getMostGenericAliasScope(MD, IMD); |
473 | 68 | break; |
474 | 2 | case LLVMContext::MD_fpmath: |
475 | 2 | MD = MDNode::getMostGenericFPMath(MD, IMD); |
476 | 2 | break; |
477 | 94 | case LLVMContext::MD_noalias: |
478 | 94 | case LLVMContext::MD_nontemporal: |
479 | 94 | case LLVMContext::MD_invariant_load: |
480 | 94 | MD = MDNode::intersect(MD, IMD); |
481 | 94 | break; |
482 | 0 | default: |
483 | 0 | llvm_unreachable("unhandled metadata"); |
484 | 44.2k | } |
485 | 44.2k | } |
486 | 1.25M | |
487 | 1.25M | Inst->setMetadata(Kind, MD); |
488 | 1.25M | } |
489 | 208k | |
490 | 208k | return Inst; |
491 | 208k | } |
492 | | |
493 | | Constant *llvm::createInterleaveMask(IRBuilder<> &Builder, unsigned VF, |
494 | 285 | unsigned NumVecs) { |
495 | 285 | SmallVector<Constant *, 16> Mask; |
496 | 1.92k | for (unsigned i = 0; i < VF1.92k ; i++1.64k ) |
497 | 5.43k | for (unsigned j = 0; 1.64k j < NumVecs5.43k ; j++3.79k ) |
498 | 3.79k | Mask.push_back(Builder.getInt32(j * VF + i)); |
499 | 285 | |
500 | 285 | return ConstantVector::get(Mask); |
501 | 285 | } |
502 | | |
503 | | Constant *llvm::createStrideMask(IRBuilder<> &Builder, unsigned Start, |
504 | 742 | unsigned Stride, unsigned VF) { |
505 | 742 | SmallVector<Constant *, 16> Mask; |
506 | 3.42k | for (unsigned i = 0; i < VF3.42k ; i++2.68k ) |
507 | 2.68k | Mask.push_back(Builder.getInt32(Start + i * Stride)); |
508 | 742 | |
509 | 742 | return ConstantVector::get(Mask); |
510 | 742 | } |
511 | | |
512 | | Constant *llvm::createSequentialMask(IRBuilder<> &Builder, unsigned Start, |
513 | 1.35k | unsigned NumInts, unsigned NumUndefs) { |
514 | 1.35k | SmallVector<Constant *, 16> Mask; |
515 | 15.4k | for (unsigned i = 0; i < NumInts15.4k ; i++14.0k ) |
516 | 14.0k | Mask.push_back(Builder.getInt32(Start + i)); |
517 | 1.35k | |
518 | 1.35k | Constant *Undef = UndefValue::get(Builder.getInt32Ty()); |
519 | 1.95k | for (unsigned i = 0; i < NumUndefs1.95k ; i++600 ) |
520 | 600 | Mask.push_back(Undef); |
521 | 1.35k | |
522 | 1.35k | return ConstantVector::get(Mask); |
523 | 1.35k | } |
524 | | |
525 | | /// A helper function for concatenating vectors. This function concatenates two |
526 | | /// vectors having the same element type. If the second vector has fewer |
527 | | /// elements than the first, it is padded with undefs. |
528 | | static Value *concatenateTwoVectors(IRBuilder<> &Builder, Value *V1, |
529 | 475 | Value *V2) { |
530 | 475 | VectorType *VecTy1 = dyn_cast<VectorType>(V1->getType()); |
531 | 475 | VectorType *VecTy2 = dyn_cast<VectorType>(V2->getType()); |
532 | 475 | assert(VecTy1 && VecTy2 && |
533 | 475 | VecTy1->getScalarType() == VecTy2->getScalarType() && |
534 | 475 | "Expect two vectors with the same element type"); |
535 | 475 | |
536 | 475 | unsigned NumElts1 = VecTy1->getNumElements(); |
537 | 475 | unsigned NumElts2 = VecTy2->getNumElements(); |
538 | 475 | assert(NumElts1 >= NumElts2 && "Unexpect the first vector has less elements"); |
539 | 475 | |
540 | 475 | if (NumElts1 > NumElts2475 ) { |
541 | 64 | // Extend with UNDEFs. |
542 | 64 | Constant *ExtMask = |
543 | 64 | createSequentialMask(Builder, 0, NumElts2, NumElts1 - NumElts2); |
544 | 64 | V2 = Builder.CreateShuffleVector(V2, UndefValue::get(VecTy2), ExtMask); |
545 | 64 | } |
546 | 475 | |
547 | 475 | Constant *Mask = createSequentialMask(Builder, 0, NumElts1 + NumElts2, 0); |
548 | 475 | return Builder.CreateShuffleVector(V1, V2, Mask); |
549 | 475 | } |
550 | | |
551 | 341 | Value *llvm::concatenateVectors(IRBuilder<> &Builder, ArrayRef<Value *> Vecs) { |
552 | 341 | unsigned NumVecs = Vecs.size(); |
553 | 341 | assert(NumVecs > 1 && "Should be at least two vectors"); |
554 | 341 | |
555 | 341 | SmallVector<Value *, 8> ResList; |
556 | 341 | ResList.append(Vecs.begin(), Vecs.end()); |
557 | 440 | do { |
558 | 440 | SmallVector<Value *, 8> TmpList; |
559 | 915 | for (unsigned i = 0; i < NumVecs - 1915 ; i += 2475 ) { |
560 | 475 | Value *V0 = ResList[i], *V1 = ResList[i + 1]; |
561 | 475 | assert((V0->getType() == V1->getType() || i == NumVecs - 2) && |
562 | 475 | "Only the last vector may have a different type"); |
563 | 475 | |
564 | 475 | TmpList.push_back(concatenateTwoVectors(Builder, V0, V1)); |
565 | 475 | } |
566 | 440 | |
567 | 440 | // Push the last vector if the total number of vectors is odd. |
568 | 440 | if (NumVecs % 2 != 0) |
569 | 64 | TmpList.push_back(ResList[NumVecs - 1]); |
570 | 440 | |
571 | 440 | ResList = TmpList; |
572 | 440 | NumVecs = ResList.size(); |
573 | 440 | } while (NumVecs > 1); |
574 | 341 | |
575 | 341 | return ResList[0]; |
576 | 341 | } |