← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp
 
1
//===- InstCombineVectorOps.cpp -------------------------------------------===//
 
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 implements instcombine for ExtractElement, InsertElement and
 
11
// ShuffleVector.
 
12
//
 
13
//===----------------------------------------------------------------------===//
 
14
 
 
15
#include "InstCombine.h"
 
16
using namespace llvm;
 
17
 
 
18
/// CheapToScalarize - Return true if the value is cheaper to scalarize than it
 
19
/// is to leave as a vector operation.
 
20
static bool CheapToScalarize(Value *V, bool isConstant) {
 
21
  if (isa<ConstantAggregateZero>(V)) 
 
22
    return true;
 
23
  if (ConstantVector *C = dyn_cast<ConstantVector>(V)) {
 
24
    if (isConstant) return true;
 
25
    // If all elts are the same, we can extract.
 
26
    Constant *Op0 = C->getOperand(0);
 
27
    for (unsigned i = 1; i < C->getNumOperands(); ++i)
 
28
      if (C->getOperand(i) != Op0)
 
29
        return false;
 
30
    return true;
 
31
  }
 
32
  Instruction *I = dyn_cast<Instruction>(V);
 
33
  if (!I) return false;
 
34
  
 
35
  // Insert element gets simplified to the inserted element or is deleted if
 
36
  // this is constant idx extract element and its a constant idx insertelt.
 
37
  if (I->getOpcode() == Instruction::InsertElement && isConstant &&
 
38
      isa<ConstantInt>(I->getOperand(2)))
 
39
    return true;
 
40
  if (I->getOpcode() == Instruction::Load && I->hasOneUse())
 
41
    return true;
 
42
  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I))
 
43
    if (BO->hasOneUse() &&
 
44
        (CheapToScalarize(BO->getOperand(0), isConstant) ||
 
45
         CheapToScalarize(BO->getOperand(1), isConstant)))
 
46
      return true;
 
47
  if (CmpInst *CI = dyn_cast<CmpInst>(I))
 
48
    if (CI->hasOneUse() &&
 
49
        (CheapToScalarize(CI->getOperand(0), isConstant) ||
 
50
         CheapToScalarize(CI->getOperand(1), isConstant)))
 
51
      return true;
 
52
  
 
53
  return false;
 
54
}
 
55
 
 
56
/// Read and decode a shufflevector mask.
 
57
///
 
58
/// It turns undef elements into values that are larger than the number of
 
59
/// elements in the input.
 
60
static std::vector<unsigned> getShuffleMask(const ShuffleVectorInst *SVI) {
 
61
  unsigned NElts = SVI->getType()->getNumElements();
 
62
  if (isa<ConstantAggregateZero>(SVI->getOperand(2)))
 
63
    return std::vector<unsigned>(NElts, 0);
 
64
  if (isa<UndefValue>(SVI->getOperand(2)))
 
65
    return std::vector<unsigned>(NElts, 2*NElts);
 
66
  
 
67
  std::vector<unsigned> Result;
 
68
  const ConstantVector *CP = cast<ConstantVector>(SVI->getOperand(2));
 
69
  for (User::const_op_iterator i = CP->op_begin(), e = CP->op_end(); i!=e; ++i)
 
70
    if (isa<UndefValue>(*i))
 
71
      Result.push_back(NElts*2);  // undef -> 8
 
72
    else
 
73
      Result.push_back(cast<ConstantInt>(*i)->getZExtValue());
 
74
  return Result;
 
75
}
 
76
 
 
77
/// FindScalarElement - Given a vector and an element number, see if the scalar
 
78
/// value is already around as a register, for example if it were inserted then
 
79
/// extracted from the vector.
 
80
static Value *FindScalarElement(Value *V, unsigned EltNo) {
 
81
  assert(V->getType()->isVectorTy() && "Not looking at a vector?");
 
82
  const VectorType *PTy = cast<VectorType>(V->getType());
 
83
  unsigned Width = PTy->getNumElements();
 
84
  if (EltNo >= Width)  // Out of range access.
 
85
    return UndefValue::get(PTy->getElementType());
 
86
  
 
87
  if (isa<UndefValue>(V))
 
88
    return UndefValue::get(PTy->getElementType());
 
89
  if (isa<ConstantAggregateZero>(V))
 
90
    return Constant::getNullValue(PTy->getElementType());
 
91
  if (ConstantVector *CP = dyn_cast<ConstantVector>(V))
 
92
    return CP->getOperand(EltNo);
 
93
  
 
94
  if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) {
 
95
    // If this is an insert to a variable element, we don't know what it is.
 
96
    if (!isa<ConstantInt>(III->getOperand(2))) 
 
97
      return 0;
 
98
    unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue();
 
99
    
 
100
    // If this is an insert to the element we are looking for, return the
 
101
    // inserted value.
 
102
    if (EltNo == IIElt) 
 
103
      return III->getOperand(1);
 
104
    
 
105
    // Otherwise, the insertelement doesn't modify the value, recurse on its
 
106
    // vector input.
 
107
    return FindScalarElement(III->getOperand(0), EltNo);
 
108
  }
 
109
  
 
110
  if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V)) {
 
111
    unsigned LHSWidth =
 
112
    cast<VectorType>(SVI->getOperand(0)->getType())->getNumElements();
 
113
    unsigned InEl = getShuffleMask(SVI)[EltNo];
 
114
    if (InEl < LHSWidth)
 
115
      return FindScalarElement(SVI->getOperand(0), InEl);
 
116
    else if (InEl < LHSWidth*2)
 
117
      return FindScalarElement(SVI->getOperand(1), InEl - LHSWidth);
 
118
    else
 
119
      return UndefValue::get(PTy->getElementType());
 
120
  }
 
121
  
 
122
  // Otherwise, we don't know.
 
123
  return 0;
 
124
}
 
125
 
 
126
Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
 
127
  // If vector val is undef, replace extract with scalar undef.
 
128
  if (isa<UndefValue>(EI.getOperand(0)))
 
129
    return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
 
130
  
 
131
  // If vector val is constant 0, replace extract with scalar 0.
 
132
  if (isa<ConstantAggregateZero>(EI.getOperand(0)))
 
133
    return ReplaceInstUsesWith(EI, Constant::getNullValue(EI.getType()));
 
134
  
 
135
  if (ConstantVector *C = dyn_cast<ConstantVector>(EI.getOperand(0))) {
 
136
    // If vector val is constant with all elements the same, replace EI with
 
137
    // that element. When the elements are not identical, we cannot replace yet
 
138
    // (we do that below, but only when the index is constant).
 
139
    Constant *op0 = C->getOperand(0);
 
140
    for (unsigned i = 1; i != C->getNumOperands(); ++i)
 
141
      if (C->getOperand(i) != op0) {
 
142
        op0 = 0; 
 
143
        break;
 
144
      }
 
145
    if (op0)
 
146
      return ReplaceInstUsesWith(EI, op0);
 
147
  }
 
148
  
 
149
  // If extracting a specified index from the vector, see if we can recursively
 
150
  // find a previously computed scalar that was inserted into the vector.
 
151
  if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) {
 
152
    unsigned IndexVal = IdxC->getZExtValue();
 
153
    unsigned VectorWidth = EI.getVectorOperandType()->getNumElements();
 
154
    
 
155
    // If this is extracting an invalid index, turn this into undef, to avoid
 
156
    // crashing the code below.
 
157
    if (IndexVal >= VectorWidth)
 
158
      return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
 
159
    
 
160
    // This instruction only demands the single element from the input vector.
 
161
    // If the input vector has a single use, simplify it based on this use
 
162
    // property.
 
163
    if (EI.getOperand(0)->hasOneUse() && VectorWidth != 1) {
 
164
      APInt UndefElts(VectorWidth, 0);
 
165
      APInt DemandedMask(VectorWidth, 0);
 
166
      DemandedMask.set(IndexVal);
 
167
      if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0),
 
168
                                                DemandedMask, UndefElts)) {
 
169
        EI.setOperand(0, V);
 
170
        return &EI;
 
171
      }
 
172
    }
 
173
    
 
174
    if (Value *Elt = FindScalarElement(EI.getOperand(0), IndexVal))
 
175
      return ReplaceInstUsesWith(EI, Elt);
 
176
    
 
177
    // If the this extractelement is directly using a bitcast from a vector of
 
178
    // the same number of elements, see if we can find the source element from
 
179
    // it.  In this case, we will end up needing to bitcast the scalars.
 
180
    if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) {
 
181
      if (const VectorType *VT = 
 
182
          dyn_cast<VectorType>(BCI->getOperand(0)->getType()))
 
183
        if (VT->getNumElements() == VectorWidth)
 
184
          if (Value *Elt = FindScalarElement(BCI->getOperand(0), IndexVal))
 
185
            return new BitCastInst(Elt, EI.getType());
 
186
    }
 
187
  }
 
188
  
 
189
  if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) {
 
190
    // Push extractelement into predecessor operation if legal and
 
191
    // profitable to do so
 
192
    if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
 
193
      if (I->hasOneUse() &&
 
194
          CheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) {
 
195
        Value *newEI0 =
 
196
        Builder->CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
 
197
                                      EI.getName()+".lhs");
 
198
        Value *newEI1 =
 
199
        Builder->CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
 
200
                                      EI.getName()+".rhs");
 
201
        return BinaryOperator::Create(BO->getOpcode(), newEI0, newEI1);
 
202
      }
 
203
    } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
 
204
      // Extracting the inserted element?
 
205
      if (IE->getOperand(2) == EI.getOperand(1))
 
206
        return ReplaceInstUsesWith(EI, IE->getOperand(1));
 
207
      // If the inserted and extracted elements are constants, they must not
 
208
      // be the same value, extract from the pre-inserted value instead.
 
209
      if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) {
 
210
        Worklist.AddValue(EI.getOperand(0));
 
211
        EI.setOperand(0, IE->getOperand(0));
 
212
        return &EI;
 
213
      }
 
214
    } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) {
 
215
      // If this is extracting an element from a shufflevector, figure out where
 
216
      // it came from and extract from the appropriate input element instead.
 
217
      if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) {
 
218
        unsigned SrcIdx = getShuffleMask(SVI)[Elt->getZExtValue()];
 
219
        Value *Src;
 
220
        unsigned LHSWidth =
 
221
        cast<VectorType>(SVI->getOperand(0)->getType())->getNumElements();
 
222
        
 
223
        if (SrcIdx < LHSWidth)
 
224
          Src = SVI->getOperand(0);
 
225
        else if (SrcIdx < LHSWidth*2) {
 
226
          SrcIdx -= LHSWidth;
 
227
          Src = SVI->getOperand(1);
 
228
        } else {
 
229
          return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
 
230
        }
 
231
        return ExtractElementInst::Create(Src,
 
232
                                          ConstantInt::get(Type::getInt32Ty(EI.getContext()),
 
233
                                                           SrcIdx, false));
 
234
      }
 
235
    }
 
236
    // FIXME: Canonicalize extractelement(bitcast) -> bitcast(extractelement)
 
237
  }
 
238
  return 0;
 
239
}
 
240
 
 
241
/// CollectSingleShuffleElements - If V is a shuffle of values that ONLY returns
 
242
/// elements from either LHS or RHS, return the shuffle mask and true. 
 
243
/// Otherwise, return false.
 
244
static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
 
245
                                         std::vector<Constant*> &Mask) {
 
246
  assert(V->getType() == LHS->getType() && V->getType() == RHS->getType() &&
 
247
         "Invalid CollectSingleShuffleElements");
 
248
  unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
 
249
  
 
250
  if (isa<UndefValue>(V)) {
 
251
    Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
 
252
    return true;
 
253
  }
 
254
  
 
255
  if (V == LHS) {
 
256
    for (unsigned i = 0; i != NumElts; ++i)
 
257
      Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
 
258
    return true;
 
259
  }
 
260
  
 
261
  if (V == RHS) {
 
262
    for (unsigned i = 0; i != NumElts; ++i)
 
263
      Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()),
 
264
                                      i+NumElts));
 
265
    return true;
 
266
  }
 
267
  
 
268
  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
 
269
    // If this is an insert of an extract from some other vector, include it.
 
270
    Value *VecOp    = IEI->getOperand(0);
 
271
    Value *ScalarOp = IEI->getOperand(1);
 
272
    Value *IdxOp    = IEI->getOperand(2);
 
273
    
 
274
    if (!isa<ConstantInt>(IdxOp))
 
275
      return false;
 
276
    unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 
277
    
 
278
    if (isa<UndefValue>(ScalarOp)) {  // inserting undef into vector.
 
279
      // Okay, we can handle this if the vector we are insertinting into is
 
280
      // transitively ok.
 
281
      if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
 
282
        // If so, update the mask to reflect the inserted undef.
 
283
        Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
 
284
        return true;
 
285
      }      
 
286
    } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
 
287
      if (isa<ConstantInt>(EI->getOperand(1)) &&
 
288
          EI->getOperand(0)->getType() == V->getType()) {
 
289
        unsigned ExtractedIdx =
 
290
        cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 
291
        
 
292
        // This must be extracting from either LHS or RHS.
 
293
        if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
 
294
          // Okay, we can handle this if the vector we are insertinting into is
 
295
          // transitively ok.
 
296
          if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
 
297
            // If so, update the mask to reflect the inserted value.
 
298
            if (EI->getOperand(0) == LHS) {
 
299
              Mask[InsertedIdx % NumElts] = 
 
300
              ConstantInt::get(Type::getInt32Ty(V->getContext()),
 
301
                               ExtractedIdx);
 
302
            } else {
 
303
              assert(EI->getOperand(0) == RHS);
 
304
              Mask[InsertedIdx % NumElts] = 
 
305
              ConstantInt::get(Type::getInt32Ty(V->getContext()),
 
306
                               ExtractedIdx+NumElts);
 
307
              
 
308
            }
 
309
            return true;
 
310
          }
 
311
        }
 
312
      }
 
313
    }
 
314
  }
 
315
  // TODO: Handle shufflevector here!
 
316
  
 
317
  return false;
 
318
}
 
319
 
 
320
/// CollectShuffleElements - We are building a shuffle of V, using RHS as the
 
321
/// RHS of the shuffle instruction, if it is not null.  Return a shuffle mask
 
322
/// that computes V and the LHS value of the shuffle.
 
323
static Value *CollectShuffleElements(Value *V, std::vector<Constant*> &Mask,
 
324
                                     Value *&RHS) {
 
325
  assert(V->getType()->isVectorTy() && 
 
326
         (RHS == 0 || V->getType() == RHS->getType()) &&
 
327
         "Invalid shuffle!");
 
328
  unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
 
329
  
 
330
  if (isa<UndefValue>(V)) {
 
331
    Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
 
332
    return V;
 
333
  } else if (isa<ConstantAggregateZero>(V)) {
 
334
    Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
 
335
    return V;
 
336
  } else if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
 
337
    // If this is an insert of an extract from some other vector, include it.
 
338
    Value *VecOp    = IEI->getOperand(0);
 
339
    Value *ScalarOp = IEI->getOperand(1);
 
340
    Value *IdxOp    = IEI->getOperand(2);
 
341
    
 
342
    if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
 
343
      if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp) &&
 
344
          EI->getOperand(0)->getType() == V->getType()) {
 
345
        unsigned ExtractedIdx =
 
346
        cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 
347
        unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 
348
        
 
349
        // Either the extracted from or inserted into vector must be RHSVec,
 
350
        // otherwise we'd end up with a shuffle of three inputs.
 
351
        if (EI->getOperand(0) == RHS || RHS == 0) {
 
352
          RHS = EI->getOperand(0);
 
353
          Value *V = CollectShuffleElements(VecOp, Mask, RHS);
 
354
          Mask[InsertedIdx % NumElts] = 
 
355
          ConstantInt::get(Type::getInt32Ty(V->getContext()),
 
356
                           NumElts+ExtractedIdx);
 
357
          return V;
 
358
        }
 
359
        
 
360
        if (VecOp == RHS) {
 
361
          Value *V = CollectShuffleElements(EI->getOperand(0), Mask, RHS);
 
362
          // Everything but the extracted element is replaced with the RHS.
 
363
          for (unsigned i = 0; i != NumElts; ++i) {
 
364
            if (i != InsertedIdx)
 
365
              Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()),
 
366
                                         NumElts+i);
 
367
          }
 
368
          return V;
 
369
        }
 
370
        
 
371
        // If this insertelement is a chain that comes from exactly these two
 
372
        // vectors, return the vector and the effective shuffle.
 
373
        if (CollectSingleShuffleElements(IEI, EI->getOperand(0), RHS, Mask))
 
374
          return EI->getOperand(0);
 
375
      }
 
376
    }
 
377
  }
 
378
  // TODO: Handle shufflevector here!
 
379
  
 
380
  // Otherwise, can't do anything fancy.  Return an identity vector.
 
381
  for (unsigned i = 0; i != NumElts; ++i)
 
382
    Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
 
383
  return V;
 
384
}
 
385
 
 
386
Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
 
387
  Value *VecOp    = IE.getOperand(0);
 
388
  Value *ScalarOp = IE.getOperand(1);
 
389
  Value *IdxOp    = IE.getOperand(2);
 
390
  
 
391
  // Inserting an undef or into an undefined place, remove this.
 
392
  if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
 
393
    ReplaceInstUsesWith(IE, VecOp);
 
394
  
 
395
  // If the inserted element was extracted from some other vector, and if the 
 
396
  // indexes are constant, try to turn this into a shufflevector operation.
 
397
  if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
 
398
    if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp) &&
 
399
        EI->getOperand(0)->getType() == IE.getType()) {
 
400
      unsigned NumVectorElts = IE.getType()->getNumElements();
 
401
      unsigned ExtractedIdx =
 
402
      cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 
403
      unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 
404
      
 
405
      if (ExtractedIdx >= NumVectorElts) // Out of range extract.
 
406
        return ReplaceInstUsesWith(IE, VecOp);
 
407
      
 
408
      if (InsertedIdx >= NumVectorElts)  // Out of range insert.
 
409
        return ReplaceInstUsesWith(IE, UndefValue::get(IE.getType()));
 
410
      
 
411
      // If we are extracting a value from a vector, then inserting it right
 
412
      // back into the same place, just use the input vector.
 
413
      if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx)
 
414
        return ReplaceInstUsesWith(IE, VecOp);      
 
415
      
 
416
      // If this insertelement isn't used by some other insertelement, turn it
 
417
      // (and any insertelements it points to), into one big shuffle.
 
418
      if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.use_back())) {
 
419
        std::vector<Constant*> Mask;
 
420
        Value *RHS = 0;
 
421
        Value *LHS = CollectShuffleElements(&IE, Mask, RHS);
 
422
        if (RHS == 0) RHS = UndefValue::get(LHS->getType());
 
423
        // We now have a shuffle of LHS, RHS, Mask.
 
424
        return new ShuffleVectorInst(LHS, RHS,
 
425
                                     ConstantVector::get(Mask));
 
426
      }
 
427
    }
 
428
  }
 
429
  
 
430
  unsigned VWidth = cast<VectorType>(VecOp->getType())->getNumElements();
 
431
  APInt UndefElts(VWidth, 0);
 
432
  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
 
433
  if (SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts))
 
434
    return &IE;
 
435
  
 
436
  return 0;
 
437
}
 
438
 
 
439
 
 
440
Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
 
441
  Value *LHS = SVI.getOperand(0);
 
442
  Value *RHS = SVI.getOperand(1);
 
443
  std::vector<unsigned> Mask = getShuffleMask(&SVI);
 
444
  
 
445
  bool MadeChange = false;
 
446
  
 
447
  // Undefined shuffle mask -> undefined value.
 
448
  if (isa<UndefValue>(SVI.getOperand(2)))
 
449
    return ReplaceInstUsesWith(SVI, UndefValue::get(SVI.getType()));
 
450
  
 
451
  unsigned VWidth = cast<VectorType>(SVI.getType())->getNumElements();
 
452
  
 
453
  if (VWidth != cast<VectorType>(LHS->getType())->getNumElements())
 
454
    return 0;
 
455
  
 
456
  APInt UndefElts(VWidth, 0);
 
457
  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
 
458
  if (SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
 
459
    LHS = SVI.getOperand(0);
 
460
    RHS = SVI.getOperand(1);
 
461
    MadeChange = true;
 
462
  }
 
463
  
 
464
  // Canonicalize shuffle(x    ,x,mask) -> shuffle(x, undef,mask')
 
465
  // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
 
466
  if (LHS == RHS || isa<UndefValue>(LHS)) {
 
467
    if (isa<UndefValue>(LHS) && LHS == RHS) {
 
468
      // shuffle(undef,undef,mask) -> undef.
 
469
      return ReplaceInstUsesWith(SVI, LHS);
 
470
    }
 
471
    
 
472
    // Remap any references to RHS to use LHS.
 
473
    std::vector<Constant*> Elts;
 
474
    for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
 
475
      if (Mask[i] >= 2*e)
 
476
        Elts.push_back(UndefValue::get(Type::getInt32Ty(SVI.getContext())));
 
477
      else {
 
478
        if ((Mask[i] >= e && isa<UndefValue>(RHS)) ||
 
479
            (Mask[i] <  e && isa<UndefValue>(LHS))) {
 
480
          Mask[i] = 2*e;     // Turn into undef.
 
481
          Elts.push_back(UndefValue::get(Type::getInt32Ty(SVI.getContext())));
 
482
        } else {
 
483
          Mask[i] = Mask[i] % e;  // Force to LHS.
 
484
          Elts.push_back(ConstantInt::get(Type::getInt32Ty(SVI.getContext()),
 
485
                                          Mask[i]));
 
486
        }
 
487
      }
 
488
    }
 
489
    SVI.setOperand(0, SVI.getOperand(1));
 
490
    SVI.setOperand(1, UndefValue::get(RHS->getType()));
 
491
    SVI.setOperand(2, ConstantVector::get(Elts));
 
492
    LHS = SVI.getOperand(0);
 
493
    RHS = SVI.getOperand(1);
 
494
    MadeChange = true;
 
495
  }
 
496
  
 
497
  // Analyze the shuffle, are the LHS or RHS and identity shuffles?
 
498
  bool isLHSID = true, isRHSID = true;
 
499
  
 
500
  for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
 
501
    if (Mask[i] >= e*2) continue;  // Ignore undef values.
 
502
    // Is this an identity shuffle of the LHS value?
 
503
    isLHSID &= (Mask[i] == i);
 
504
    
 
505
    // Is this an identity shuffle of the RHS value?
 
506
    isRHSID &= (Mask[i]-e == i);
 
507
  }
 
508
  
 
509
  // Eliminate identity shuffles.
 
510
  if (isLHSID) return ReplaceInstUsesWith(SVI, LHS);
 
511
  if (isRHSID) return ReplaceInstUsesWith(SVI, RHS);
 
512
  
 
513
  // If the LHS is a shufflevector itself, see if we can combine it with this
 
514
  // one without producing an unusual shuffle.  Here we are really conservative:
 
515
  // we are absolutely afraid of producing a shuffle mask not in the input
 
516
  // program, because the code gen may not be smart enough to turn a merged
 
517
  // shuffle into two specific shuffles: it may produce worse code.  As such,
 
518
  // we only merge two shuffles if the result is one of the two input shuffle
 
519
  // masks.  In this case, merging the shuffles just removes one instruction,
 
520
  // which we know is safe.  This is good for things like turning:
 
521
  // (splat(splat)) -> splat.
 
522
  if (ShuffleVectorInst *LHSSVI = dyn_cast<ShuffleVectorInst>(LHS)) {
 
523
    if (isa<UndefValue>(RHS)) {
 
524
      std::vector<unsigned> LHSMask = getShuffleMask(LHSSVI);
 
525
      
 
526
      if (LHSMask.size() == Mask.size()) {
 
527
        std::vector<unsigned> NewMask;
 
528
        for (unsigned i = 0, e = Mask.size(); i != e; ++i)
 
529
          if (Mask[i] >= e)
 
530
            NewMask.push_back(2*e);
 
531
          else
 
532
            NewMask.push_back(LHSMask[Mask[i]]);
 
533
        
 
534
        // If the result mask is equal to the src shuffle or this
 
535
        // shuffle mask, do the replacement.
 
536
        if (NewMask == LHSMask || NewMask == Mask) {
 
537
          unsigned LHSInNElts =
 
538
          cast<VectorType>(LHSSVI->getOperand(0)->getType())->
 
539
          getNumElements();
 
540
          std::vector<Constant*> Elts;
 
541
          for (unsigned i = 0, e = NewMask.size(); i != e; ++i) {
 
542
            if (NewMask[i] >= LHSInNElts*2) {
 
543
              Elts.push_back(UndefValue::get(
 
544
                                             Type::getInt32Ty(SVI.getContext())));
 
545
            } else {
 
546
              Elts.push_back(ConstantInt::get(
 
547
                                              Type::getInt32Ty(SVI.getContext()),
 
548
                                              NewMask[i]));
 
549
            }
 
550
          }
 
551
          return new ShuffleVectorInst(LHSSVI->getOperand(0),
 
552
                                       LHSSVI->getOperand(1),
 
553
                                       ConstantVector::get(Elts));
 
554
        }
 
555
      }
 
556
    }
 
557
  }
 
558
  
 
559
  return MadeChange ? &SVI : 0;
 
560
}
 
561