Coverage Report

Created: 2017-10-03 07:32

/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
}