Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- InstCombineSimplifyDemanded.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 file contains logic for simplifying instructions based on information
10
// about how they are used.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "InstCombineInternal.h"
15
#include "llvm/Analysis/ValueTracking.h"
16
#include "llvm/IR/IntrinsicInst.h"
17
#include "llvm/IR/PatternMatch.h"
18
#include "llvm/Support/KnownBits.h"
19
20
using namespace llvm;
21
using namespace llvm::PatternMatch;
22
23
#define DEBUG_TYPE "instcombine"
24
25
namespace {
26
27
struct AMDGPUImageDMaskIntrinsic {
28
  unsigned Intr;
29
};
30
31
#define GET_AMDGPUImageDMaskIntrinsicTable_IMPL
32
#include "InstCombineTables.inc"
33
34
} // end anonymous namespace
35
36
/// Check to see if the specified operand of the specified instruction is a
37
/// constant integer. If so, check to see if there are any bits set in the
38
/// constant that are not demanded. If so, shrink the constant and return true.
39
static bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo,
40
11.8M
                                   const APInt &Demanded) {
41
11.8M
  assert(I && "No instruction?");
42
11.8M
  assert(OpNo < I->getNumOperands() && "Operand index too large");
43
11.8M
44
11.8M
  // The operand must be a constant integer or splat integer.
45
11.8M
  Value *Op = I->getOperand(OpNo);
46
11.8M
  const APInt *C;
47
11.8M
  if (!match(Op, m_APInt(C)))
48
6.85M
    return false;
49
5.03M
50
5.03M
  // If there are no bits set that aren't demanded, nothing to do.
51
5.03M
  if (C->isSubsetOf(Demanded))
52
5.02M
    return false;
53
9.09k
54
9.09k
  // This instruction is producing bits that are not demanded. Shrink the RHS.
55
9.09k
  I->setOperand(OpNo, ConstantInt::get(Op->getType(), *C & Demanded));
56
9.09k
57
9.09k
  return true;
58
9.09k
}
59
60
61
62
/// Inst is an integer instruction that SimplifyDemandedBits knows about. See if
63
/// the instruction has any properties that allow us to simplify its operands.
64
6.75M
bool InstCombiner::SimplifyDemandedInstructionBits(Instruction &Inst) {
65
6.75M
  unsigned BitWidth = Inst.getType()->getScalarSizeInBits();
66
6.75M
  KnownBits Known(BitWidth);
67
6.75M
  APInt DemandedMask(APInt::getAllOnesValue(BitWidth));
68
6.75M
69
6.75M
  Value *V = SimplifyDemandedUseBits(&Inst, DemandedMask, Known,
70
6.75M
                                     0, &Inst);
71
6.75M
  if (!V) 
return false6.72M
;
72
21.5k
  if (V == &Inst) 
return true17.3k
;
73
4.20k
  replaceInstUsesWith(Inst, V);
74
4.20k
  return true;
75
4.20k
}
76
77
/// This form of SimplifyDemandedBits simplifies the specified instruction
78
/// operand if possible, updating it in place. It returns true if it made any
79
/// change and false otherwise.
80
bool InstCombiner::SimplifyDemandedBits(Instruction *I, unsigned OpNo,
81
                                        const APInt &DemandedMask,
82
                                        KnownBits &Known,
83
53.7M
                                        unsigned Depth) {
84
53.7M
  Use &U = I->getOperandUse(OpNo);
85
53.7M
  Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask, Known,
86
53.7M
                                          Depth, I);
87
53.7M
  if (!NewVal) 
return false53.6M
;
88
42.9k
  U = NewVal;
89
42.9k
  return true;
90
42.9k
}
91
92
93
/// This function attempts to replace V with a simpler value based on the
94
/// demanded bits. When this function is called, it is known that only the bits
95
/// set in DemandedMask of the result of V are ever used downstream.
96
/// Consequently, depending on the mask and V, it may be possible to replace V
97
/// with a constant or one of its operands. In such cases, this function does
98
/// the replacement and returns true. In all other cases, it returns false after
99
/// analyzing the expression and setting KnownOne and known to be one in the
100
/// expression. Known.Zero contains all the bits that are known to be zero in
101
/// the expression. These are provided to potentially allow the caller (which
102
/// might recursively be SimplifyDemandedBits itself) to simplify the
103
/// expression.
104
/// Known.One and Known.Zero always follow the invariant that:
105
///   Known.One & Known.Zero == 0.
106
/// That is, a bit can't be both 1 and 0. Note that the bits in Known.One and
107
/// Known.Zero may only be accurate for those bits set in DemandedMask. Note
108
/// also that the bitwidth of V, DemandedMask, Known.Zero and Known.One must all
109
/// be the same.
110
///
111
/// This returns null if it did not change anything and it permits no
112
/// simplification.  This returns V itself if it did some simplification of V's
113
/// operands based on the information about what bits are demanded. This returns
114
/// some other non-null value if it found out that V is equal to another value
115
/// in the context where the specified bits are demanded, but not for all users.
116
Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask,
117
                                             KnownBits &Known, unsigned Depth,
118
60.4M
                                             Instruction *CxtI) {
119
60.4M
  assert(V != nullptr && "Null pointer of Value???");
120
60.4M
  assert(Depth <= 6 && "Limit Search Depth");
121
60.4M
  uint32_t BitWidth = DemandedMask.getBitWidth();
122
60.4M
  Type *VTy = V->getType();
123
60.4M
  assert(
124
60.4M
      (!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) &&
125
60.4M
      Known.getBitWidth() == BitWidth &&
126
60.4M
      "Value *V, DemandedMask and Known must have same BitWidth");
127
60.4M
128
60.4M
  if (isa<Constant>(V)) {
129
16.0M
    computeKnownBits(V, Known, Depth, CxtI);
130
16.0M
    return nullptr;
131
16.0M
  }
132
44.4M
133
44.4M
  Known.resetAll();
134
44.4M
  if (DemandedMask.isNullValue())     // Not demanding any bits from V.
135
153
    return UndefValue::get(VTy);
136
44.4M
137
44.4M
  if (Depth == 6)        // Limit search depth.
138
45.4k
    return nullptr;
139
44.3M
140
44.3M
  Instruction *I = dyn_cast<Instruction>(V);
141
44.3M
  if (!I) {
142
3.16M
    computeKnownBits(V, Known, Depth, CxtI);
143
3.16M
    return nullptr;        // Only analyze instructions.
144
3.16M
  }
145
41.2M
146
41.2M
  // If there are multiple uses of this value and we aren't at the root, then
147
41.2M
  // we can't do any simplifications of the operands, because DemandedMask
148
41.2M
  // only reflects the bits demanded by *one* of the users.
149
41.2M
  if (Depth != 0 && 
!I->hasOneUse()17.6M
)
150
8.98M
    return SimplifyMultipleUseDemandedBits(I, DemandedMask, Known, Depth, CxtI);
151
32.2M
152
32.2M
  KnownBits LHSKnown(BitWidth), RHSKnown(BitWidth);
153
32.2M
154
32.2M
  // If this is the root being simplified, allow it to have multiple uses,
155
32.2M
  // just set the DemandedMask to all bits so that we can try to simplify the
156
32.2M
  // operands.  This allows visitTruncInst (for example) to simplify the
157
32.2M
  // operand of a trunc without duplicating all the logic below.
158
32.2M
  if (Depth == 0 && 
!V->hasOneUse()23.5M
)
159
11.5M
    DemandedMask.setAllBits();
160
32.2M
161
32.2M
  switch (I->getOpcode()) {
162
32.2M
  default:
163
14.2M
    computeKnownBits(I, Known, Depth, CxtI);
164
14.2M
    break;
165
32.2M
  case Instruction::And: {
166
3.11M
    // If either the LHS or the RHS are Zero, the result is zero.
167
3.11M
    if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
168
3.11M
        SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.Zero, LHSKnown,
169
3.11M
                             Depth + 1))
170
3.78k
      return I;
171
3.11M
    assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
172
3.11M
    assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
173
3.11M
174
3.11M
    // Output known-0 are known to be clear if zero in either the LHS | RHS.
175
3.11M
    APInt IKnownZero = RHSKnown.Zero | LHSKnown.Zero;
176
3.11M
    // Output known-1 bits are only known if set in both the LHS & RHS.
177
3.11M
    APInt IKnownOne = RHSKnown.One & LHSKnown.One;
178
3.11M
179
3.11M
    // If the client is only demanding bits that we know, return the known
180
3.11M
    // constant.
181
3.11M
    if (DemandedMask.isSubsetOf(IKnownZero|IKnownOne))
182
31
      return Constant::getIntegerValue(VTy, IKnownOne);
183
3.11M
184
3.11M
    // If all of the demanded bits are known 1 on one side, return the other.
185
3.11M
    // These bits cannot contribute to the result of the 'and'.
186
3.11M
    if (DemandedMask.isSubsetOf(LHSKnown.Zero | RHSKnown.One))
187
27.7k
      return I->getOperand(0);
188
3.08M
    if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.One))
189
518
      return I->getOperand(1);
190
3.08M
191
3.08M
    // If the RHS is a constant, see if we can simplify it.
192
3.08M
    if (ShrinkDemandedConstant(I, 1, DemandedMask & ~LHSKnown.Zero))
193
6.71k
      return I;
194
3.07M
195
3.07M
    Known.Zero = std::move(IKnownZero);
196
3.07M
    Known.One  = std::move(IKnownOne);
197
3.07M
    break;
198
3.07M
  }
199
3.07M
  case Instruction::Or: {
200
1.03M
    // If either the LHS or the RHS are One, the result is One.
201
1.03M
    if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
202
1.03M
        SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.One, LHSKnown,
203
1.03M
                             Depth + 1))
204
2.15k
      return I;
205
1.03M
    assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
206
1.03M
    assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
207
1.03M
208
1.03M
    // Output known-0 bits are only known if clear in both the LHS & RHS.
209
1.03M
    APInt IKnownZero = RHSKnown.Zero & LHSKnown.Zero;
210
1.03M
    // Output known-1 are known. to be set if s.et in either the LHS | RHS.
211
1.03M
    APInt IKnownOne = RHSKnown.One | LHSKnown.One;
212
1.03M
213
1.03M
    // If the client is only demanding bits that we know, return the known
214
1.03M
    // constant.
215
1.03M
    if (DemandedMask.isSubsetOf(IKnownZero|IKnownOne))
216
4
      return Constant::getIntegerValue(VTy, IKnownOne);
217
1.03M
218
1.03M
    // If all of the demanded bits are known zero on one side, return the other.
219
1.03M
    // These bits cannot contribute to the result of the 'or'.
220
1.03M
    if (DemandedMask.isSubsetOf(LHSKnown.One | RHSKnown.Zero))
221
115
      return I->getOperand(0);
222
1.03M
    if (DemandedMask.isSubsetOf(RHSKnown.One | LHSKnown.Zero))
223
43
      return I->getOperand(1);
224
1.03M
225
1.03M
    // If the RHS is a constant, see if we can simplify it.
226
1.03M
    if (ShrinkDemandedConstant(I, 1, DemandedMask))
227
18
      return I;
228
1.03M
229
1.03M
    Known.Zero = std::move(IKnownZero);
230
1.03M
    Known.One  = std::move(IKnownOne);
231
1.03M
    break;
232
1.03M
  }
233
1.03M
  case Instruction::Xor: {
234
576k
    if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
235
576k
        
SimplifyDemandedBits(I, 0, DemandedMask, LHSKnown, Depth + 1)576k
)
236
256
      return I;
237
575k
    assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
238
575k
    assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
239
575k
240
575k
    // Output known-0 bits are known if clear or set in both the LHS & RHS.
241
575k
    APInt IKnownZero = (RHSKnown.Zero & LHSKnown.Zero) |
242
575k
                       (RHSKnown.One & LHSKnown.One);
243
575k
    // Output known-1 are known to be set if set in only one of the LHS, RHS.
244
575k
    APInt IKnownOne =  (RHSKnown.Zero & LHSKnown.One) |
245
575k
                       (RHSKnown.One & LHSKnown.Zero);
246
575k
247
575k
    // If the client is only demanding bits that we know, return the known
248
575k
    // constant.
249
575k
    if (DemandedMask.isSubsetOf(IKnownZero|IKnownOne))
250
24
      return Constant::getIntegerValue(VTy, IKnownOne);
251
575k
252
575k
    // If all of the demanded bits are known zero on one side, return the other.
253
575k
    // These bits cannot contribute to the result of the 'xor'.
254
575k
    if (DemandedMask.isSubsetOf(RHSKnown.Zero))
255
10
      return I->getOperand(0);
256
575k
    if (DemandedMask.isSubsetOf(LHSKnown.Zero))
257
0
      return I->getOperand(1);
258
575k
259
575k
    // If all of the demanded bits are known to be zero on one side or the
260
575k
    // other, turn this into an *inclusive* or.
261
575k
    //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
262
575k
    if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.Zero)) {
263
46
      Instruction *Or =
264
46
        BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1),
265
46
                                 I->getName());
266
46
      return InsertNewInstWith(Or, *I);
267
46
    }
268
575k
269
575k
    // If all of the demanded bits on one side are known, and all of the set
270
575k
    // bits on that side are also known to be set on the other side, turn this
271
575k
    // into an AND, as we know the bits will be cleared.
272
575k
    //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
273
575k
    if (DemandedMask.isSubsetOf(RHSKnown.Zero|RHSKnown.One) &&
274
575k
        
RHSKnown.One.isSubsetOf(LHSKnown.One)360k
) {
275
111
      Constant *AndC = Constant::getIntegerValue(VTy,
276
111
                                                 ~RHSKnown.One & DemandedMask);
277
111
      Instruction *And = BinaryOperator::CreateAnd(I->getOperand(0), AndC);
278
111
      return InsertNewInstWith(And, *I);
279
111
    }
280
575k
281
575k
    // If the RHS is a constant, see if we can simplify it.
282
575k
    // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1.
283
575k
    if (ShrinkDemandedConstant(I, 1, DemandedMask))
284
1.35k
      return I;
285
574k
286
574k
    // If our LHS is an 'and' and if it has one use, and if any of the bits we
287
574k
    // are flipping are known to be set, then the xor is just resetting those
288
574k
    // bits to zero.  We can just knock out bits from the 'and' and the 'xor',
289
574k
    // simplifying both of them.
290
574k
    if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0)))
291
538k
      if (LHSInst->getOpcode() == Instruction::And && 
LHSInst->hasOneUse()29.2k
&&
292
538k
          
isa<ConstantInt>(I->getOperand(1))25.7k
&&
293
538k
          
isa<ConstantInt>(LHSInst->getOperand(1))18.1k
&&
294
538k
          
(LHSKnown.One & RHSKnown.One & DemandedMask) != 09.45k
) {
295
4
        ConstantInt *AndRHS = cast<ConstantInt>(LHSInst->getOperand(1));
296
4
        ConstantInt *XorRHS = cast<ConstantInt>(I->getOperand(1));
297
4
        APInt NewMask = ~(LHSKnown.One & RHSKnown.One & DemandedMask);
298
4
299
4
        Constant *AndC =
300
4
          ConstantInt::get(I->getType(), NewMask & AndRHS->getValue());
301
4
        Instruction *NewAnd = BinaryOperator::CreateAnd(I->getOperand(0), AndC);
302
4
        InsertNewInstWith(NewAnd, *I);
303
4
304
4
        Constant *XorC =
305
4
          ConstantInt::get(I->getType(), NewMask & XorRHS->getValue());
306
4
        Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC);
307
4
        return InsertNewInstWith(NewXor, *I);
308
4
      }
309
574k
310
574k
    // Output known-0 bits are known if clear or set in both the LHS & RHS.
311
574k
    Known.Zero = std::move(IKnownZero);
312
574k
    // Output known-1 are known to be set if set in only one of the LHS, RHS.
313
574k
    Known.One  = std::move(IKnownOne);
314
574k
    break;
315
574k
  }
316
574k
  case Instruction::Select: {
317
551k
    Value *LHS, *RHS;
318
551k
    SelectPatternFlavor SPF = matchSelectPattern(I, LHS, RHS).Flavor;
319
551k
    if (SPF == SPF_UMAX) {
320
104k
      // UMax(A, C) == A if ...
321
104k
      // The lowest non-zero bit of DemandMask is higher than the highest
322
104k
      // non-zero bit of C.
323
104k
      const APInt *C;
324
104k
      unsigned CTZ = DemandedMask.countTrailingZeros();
325
104k
      if (match(RHS, m_APInt(C)) && 
CTZ >= C->getActiveBits()43.0k
)
326
7
        return LHS;
327
446k
    } else if (SPF == SPF_UMIN) {
328
18.1k
      // UMin(A, C) == A if ...
329
18.1k
      // The lowest non-zero bit of DemandMask is higher than the highest
330
18.1k
      // non-one bit of C.
331
18.1k
      // This comes from using DeMorgans on the above umax example.
332
18.1k
      const APInt *C;
333
18.1k
      unsigned CTZ = DemandedMask.countTrailingZeros();
334
18.1k
      if (match(RHS, m_APInt(C)) &&
335
18.1k
          
CTZ >= C->getBitWidth() - C->countLeadingOnes()5.34k
)
336
3
        return LHS;
337
551k
    }
338
551k
339
551k
    // If this is a select as part of any other min/max pattern, don't simplify
340
551k
    // any further in case we break the structure.
341
551k
    if (SPF != SPF_UNKNOWN)
342
289k
      return nullptr;
343
261k
344
261k
    if (SimplifyDemandedBits(I, 2, DemandedMask, RHSKnown, Depth + 1) ||
345
261k
        
SimplifyDemandedBits(I, 1, DemandedMask, LHSKnown, Depth + 1)261k
)
346
189
      return I;
347
261k
    assert(!RHSKnown.hasConflict() && "Bits known to be one AND zero?");
348
261k
    assert(!LHSKnown.hasConflict() && "Bits known to be one AND zero?");
349
261k
350
261k
    // If the operands are constants, see if we can simplify them.
351
261k
    if (ShrinkDemandedConstant(I, 1, DemandedMask) ||
352
261k
        
ShrinkDemandedConstant(I, 2, DemandedMask)261k
)
353
172
      return I;
354
261k
355
261k
    // Only known if known in both the LHS and RHS.
356
261k
    Known.One = RHSKnown.One & LHSKnown.One;
357
261k
    Known.Zero = RHSKnown.Zero & LHSKnown.Zero;
358
261k
    break;
359
261k
  }
360
2.82M
  case Instruction::ZExt:
361
2.82M
  case Instruction::Trunc: {
362
2.82M
    unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
363
2.82M
364
2.82M
    APInt InputDemandedMask = DemandedMask.zextOrTrunc(SrcBitWidth);
365
2.82M
    KnownBits InputKnown(SrcBitWidth);
366
2.82M
    if (SimplifyDemandedBits(I, 0, InputDemandedMask, InputKnown, Depth + 1))
367
5.53k
      return I;
368
2.82M
    assert(InputKnown.getBitWidth() == SrcBitWidth && "Src width changed?");
369
2.82M
    Known = InputKnown.zextOrTrunc(BitWidth,
370
2.82M
                                   true /* ExtendedBitsAreKnownZero */);
371
2.82M
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
372
2.82M
    break;
373
2.82M
  }
374
2.82M
  case Instruction::BitCast:
375
54.2k
    if (!I->getOperand(0)->getType()->isIntOrIntVectorTy())
376
51.1k
      return nullptr;  // vector->int or fp->int?
377
3.12k
378
3.12k
    if (VectorType *DstVTy = dyn_cast<VectorType>(I->getType())) {
379
1.79k
      if (VectorType *SrcVTy =
380
1.77k
            dyn_cast<VectorType>(I->getOperand(0)->getType())) {
381
1.77k
        if (DstVTy->getNumElements() != SrcVTy->getNumElements())
382
1.77k
          // Don't touch a bitcast between vectors of different element counts.
383
1.77k
          return nullptr;
384
24
      } else
385
24
        // Don't touch a scalar-to-vector bitcast.
386
24
        return nullptr;
387
1.32k
    } else if (I->getOperand(0)->getType()->isVectorTy())
388
1.32k
      // Don't touch a vector-to-scalar bitcast.
389
1.32k
      return nullptr;
390
0
391
0
    if (SimplifyDemandedBits(I, 0, DemandedMask, Known, Depth + 1))
392
0
      return I;
393
0
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
394
0
    break;
395
517k
  case Instruction::SExt: {
396
517k
    // Compute the bits in the result that are not present in the input.
397
517k
    unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
398
517k
399
517k
    APInt InputDemandedBits = DemandedMask.trunc(SrcBitWidth);
400
517k
401
517k
    // If any of the sign extended bits are demanded, we know that the sign
402
517k
    // bit is demanded.
403
517k
    if (DemandedMask.getActiveBits() > SrcBitWidth)
404
516k
      InputDemandedBits.setBit(SrcBitWidth-1);
405
517k
406
517k
    KnownBits InputKnown(SrcBitWidth);
407
517k
    if (SimplifyDemandedBits(I, 0, InputDemandedBits, InputKnown, Depth + 1))
408
110
      return I;
409
517k
410
517k
    // If the input sign bit is known zero, or if the NewBits are not demanded
411
517k
    // convert this into a zero extension.
412
517k
    if (InputKnown.isNonNegative() ||
413
517k
        
DemandedMask.getActiveBits() <= SrcBitWidth517k
) {
414
1.02k
      // Convert to ZExt cast.
415
1.02k
      CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName());
416
1.02k
      return InsertNewInstWith(NewCast, *I);
417
1.02k
     }
418
516k
419
516k
    // If the sign bit of the input is known set or clear, then we know the
420
516k
    // top bits of the result.
421
516k
    Known = InputKnown.sext(BitWidth);
422
516k
    assert(!Known.hasConflict() && "Bits known to be one AND zero?");
423
516k
    break;
424
516k
  }
425
3.33M
  case Instruction::Add:
426
3.33M
  case Instruction::Sub: {
427
3.33M
    /// If the high-bits of an ADD/SUB are not demanded, then we do not care
428
3.33M
    /// about the high bits of the operands.
429
3.33M
    unsigned NLZ = DemandedMask.countLeadingZeros();
430
3.33M
    // Right fill the mask of bits for this ADD/SUB to demand the most
431
3.33M
    // significant bit and all those below it.
432
3.33M
    APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ));
433
3.33M
    if (ShrinkDemandedConstant(I, 0, DemandedFromOps) ||
434
3.33M
        
SimplifyDemandedBits(I, 0, DemandedFromOps, LHSKnown, Depth + 1)3.33M
||
435
3.33M
        
ShrinkDemandedConstant(I, 1, DemandedFromOps)3.33M
||
436
3.33M
        
SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnown, Depth + 1)3.33M
) {
437
2.04k
      if (NLZ > 0) {
438
1.87k
        // Disable the nsw and nuw flags here: We can no longer guarantee that
439
1.87k
        // we won't wrap after simplification. Removing the nsw/nuw flags is
440
1.87k
        // legal here because the top bit is not demanded.
441
1.87k
        BinaryOperator &BinOP = *cast<BinaryOperator>(I);
442
1.87k
        BinOP.setHasNoSignedWrap(false);
443
1.87k
        BinOP.setHasNoUnsignedWrap(false);
444
1.87k
      }
445
2.04k
      return I;
446
2.04k
    }
447
3.33M
448
3.33M
    // If we are known to be adding/subtracting zeros to every bit below
449
3.33M
    // the highest demanded bit, we just return the other side.
450
3.33M
    if (DemandedFromOps.isSubsetOf(RHSKnown.Zero))
451
666
      return I->getOperand(0);
452
3.33M
    // We can't do this with the LHS for subtraction, unless we are only
453
3.33M
    // demanding the LSB.
454
3.33M
    if ((I->getOpcode() == Instruction::Add ||
455
3.33M
         
DemandedFromOps.isOneValue()750k
) &&
456
3.33M
        
DemandedFromOps.isSubsetOf(LHSKnown.Zero)2.58M
)
457
8
      return I->getOperand(1);
458
3.33M
459
3.33M
    // Otherwise just compute the known bits of the result.
460
3.33M
    bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
461
3.33M
    Known = KnownBits::computeForAddSub(I->getOpcode() == Instruction::Add,
462
3.33M
                                        NSW, LHSKnown, RHSKnown);
463
3.33M
    break;
464
3.33M
  }
465
3.33M
  case Instruction::Shl: {
466
1.83M
    const APInt *SA;
467
1.83M
    if (match(I->getOperand(1), m_APInt(SA))) {
468
1.48M
      const APInt *ShrAmt;
469
1.48M
      if (match(I->getOperand(0), m_Shr(m_Value(), m_APInt(ShrAmt))))
470
24.3k
        if (Instruction *Shr = dyn_cast<Instruction>(I->getOperand(0)))
471
24.3k
          if (Value *R = simplifyShrShlDemandedBits(Shr, *ShrAmt, I, *SA,
472
301
                                                    DemandedMask, Known))
473
301
            return R;
474
1.48M
475
1.48M
      uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
476
1.48M
      APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt));
477
1.48M
478
1.48M
      // If the shift is NUW/NSW, then it does demand the high bits.
479
1.48M
      ShlOperator *IOp = cast<ShlOperator>(I);
480
1.48M
      if (IOp->hasNoSignedWrap())
481
603k
        DemandedMaskIn.setHighBits(ShiftAmt+1);
482
878k
      else if (IOp->hasNoUnsignedWrap())
483
101k
        DemandedMaskIn.setHighBits(ShiftAmt);
484
1.48M
485
1.48M
      if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
486
1.74k
        return I;
487
1.48M
      assert(!Known.hasConflict() && "Bits known to be one AND zero?");
488
1.48M
      Known.Zero <<= ShiftAmt;
489
1.48M
      Known.One  <<= ShiftAmt;
490
1.48M
      // low bits known zero.
491
1.48M
      if (ShiftAmt)
492
1.48M
        Known.Zero.setLowBits(ShiftAmt);
493
1.48M
    }
494
1.83M
    
break1.83M
;
495
1.83M
  }
496
1.83M
  case Instruction::LShr: {
497
1.75M
    const APInt *SA;
498
1.75M
    if (match(I->getOperand(1), m_APInt(SA))) {
499
1.63M
      uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
500
1.63M
501
1.63M
      // Unsigned shift right.
502
1.63M
      APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
503
1.63M
504
1.63M
      // If the shift is exact, then it does demand the low bits (and knows that
505
1.63M
      // they are zero).
506
1.63M
      if (cast<LShrOperator>(I)->isExact())
507
34.1k
        DemandedMaskIn.setLowBits(ShiftAmt);
508
1.63M
509
1.63M
      if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
510
1.55k
        return I;
511
1.63M
      assert(!Known.hasConflict() && "Bits known to be one AND zero?");
512
1.63M
      Known.Zero.lshrInPlace(ShiftAmt);
513
1.63M
      Known.One.lshrInPlace(ShiftAmt);
514
1.63M
      if (ShiftAmt)
515
1.63M
        Known.Zero.setHighBits(ShiftAmt);  // high bits known zero.
516
1.63M
    }
517
1.75M
    
break1.75M
;
518
1.75M
  }
519
1.75M
  case Instruction::AShr: {
520
410k
    // If this is an arithmetic shift right and only the low-bit is set, we can
521
410k
    // always convert this into a logical shr, even if the shift amount is
522
410k
    // variable.  The low bit of the shift cannot be an input sign bit unless
523
410k
    // the shift amount is >= the size of the datatype, which is undefined.
524
410k
    if (DemandedMask.isOneValue()) {
525
130
      // Perform the logical shift right.
526
130
      Instruction *NewVal = BinaryOperator::CreateLShr(
527
130
                        I->getOperand(0), I->getOperand(1), I->getName());
528
130
      return InsertNewInstWith(NewVal, *I);
529
130
    }
530
410k
531
410k
    // If the sign bit is the only bit demanded by this ashr, then there is no
532
410k
    // need to do it, the shift doesn't change the high bit.
533
410k
    if (DemandedMask.isSignMask())
534
22
      return I->getOperand(0);
535
410k
536
410k
    const APInt *SA;
537
410k
    if (match(I->getOperand(1), m_APInt(SA))) {
538
382k
      uint32_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
539
382k
540
382k
      // Signed shift right.
541
382k
      APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
542
382k
      // If any of the high bits are demanded, we should set the sign bit as
543
382k
      // demanded.
544
382k
      if (DemandedMask.countLeadingZeros() <= ShiftAmt)
545
379k
        DemandedMaskIn.setSignBit();
546
382k
547
382k
      // If the shift is exact, then it does demand the low bits (and knows that
548
382k
      // they are zero).
549
382k
      if (cast<AShrOperator>(I)->isExact())
550
269k
        DemandedMaskIn.setLowBits(ShiftAmt);
551
382k
552
382k
      if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
553
614
        return I;
554
381k
555
381k
      unsigned SignBits = ComputeNumSignBits(I->getOperand(0), Depth + 1, CxtI);
556
381k
557
381k
      assert(!Known.hasConflict() && "Bits known to be one AND zero?");
558
381k
      // Compute the new bits that are at the top now plus sign bits.
559
381k
      APInt HighBits(APInt::getHighBitsSet(
560
381k
          BitWidth, std::min(SignBits + ShiftAmt - 1, BitWidth)));
561
381k
      Known.Zero.lshrInPlace(ShiftAmt);
562
381k
      Known.One.lshrInPlace(ShiftAmt);
563
381k
564
381k
      // If the input sign bit is known to be zero, or if none of the top bits
565
381k
      // are demanded, turn this into an unsigned shift right.
566
381k
      assert(BitWidth > ShiftAmt && "Shift amount not saturated?");
567
381k
      if (Known.Zero[BitWidth-ShiftAmt-1] ||
568
381k
          
!DemandedMask.intersects(HighBits)379k
) {
569
3.49k
        BinaryOperator *LShr = BinaryOperator::CreateLShr(I->getOperand(0),
570
3.49k
                                                          I->getOperand(1));
571
3.49k
        LShr->setIsExact(cast<BinaryOperator>(I)->isExact());
572
3.49k
        return InsertNewInstWith(LShr, *I);
573
378k
      } else if (Known.One[BitWidth-ShiftAmt-1]) { // New bits are known one.
574
4
        Known.One |= HighBits;
575
4
      }
576
381k
    }
577
410k
    
break406k
;
578
410k
  }
579
410k
  case Instruction::UDiv: {
580
136k
    // UDiv doesn't demand low bits that are zero in the divisor.
581
136k
    const APInt *SA;
582
136k
    if (match(I->getOperand(1), m_APInt(SA))) {
583
65.0k
      // If the shift is exact, then it does demand the low bits.
584
65.0k
      if (cast<UDivOperator>(I)->isExact())
585
120
        break;
586
64.9k
587
64.9k
      // FIXME: Take the demanded mask of the result into account.
588
64.9k
      unsigned RHSTrailingZeros = SA->countTrailingZeros();
589
64.9k
      APInt DemandedMaskIn =
590
64.9k
          APInt::getHighBitsSet(BitWidth, BitWidth - RHSTrailingZeros);
591
64.9k
      if (SimplifyDemandedBits(I, 0, DemandedMaskIn, LHSKnown, Depth + 1))
592
63
        return I;
593
64.9k
594
64.9k
      // Propagate zero bits from the input.
595
64.9k
      Known.Zero.setHighBits(std::min(
596
64.9k
          BitWidth, LHSKnown.Zero.countLeadingOnes() + RHSTrailingZeros));
597
64.9k
    }
598
136k
    
break136k
;
599
136k
  }
600
136k
  case Instruction::SRem:
601
41.1k
    if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
602
17.5k
      // X % -1 demands all the bits because we don't want to introduce
603
17.5k
      // INT_MIN % -1 (== undef) by accident.
604
17.5k
      if (Rem->isMinusOne())
605
0
        break;
606
17.5k
      APInt RA = Rem->getValue().abs();
607
17.5k
      if (RA.isPowerOf2()) {
608
9.66k
        if (DemandedMask.ult(RA))    // srem won't affect demanded bits
609
1
          return I->getOperand(0);
610
9.66k
611
9.66k
        APInt LowBits = RA - 1;
612
9.66k
        APInt Mask2 = LowBits | APInt::getSignMask(BitWidth);
613
9.66k
        if (SimplifyDemandedBits(I, 0, Mask2, LHSKnown, Depth + 1))
614
2
          return I;
615
9.65k
616
9.65k
        // The low bits of LHS are unchanged by the srem.
617
9.65k
        Known.Zero = LHSKnown.Zero & LowBits;
618
9.65k
        Known.One = LHSKnown.One & LowBits;
619
9.65k
620
9.65k
        // If LHS is non-negative or has all low bits zero, then the upper bits
621
9.65k
        // are all zero.
622
9.65k
        if (LHSKnown.isNonNegative() || 
LowBits.isSubsetOf(LHSKnown.Zero)9.54k
)
623
114
          Known.Zero |= ~LowBits;
624
9.65k
625
9.65k
        // If LHS is negative and not all low bits are zero, then the upper bits
626
9.65k
        // are all one.
627
9.65k
        if (LHSKnown.isNegative() && 
LowBits.intersects(LHSKnown.One)0
)
628
0
          Known.One |= ~LowBits;
629
9.65k
630
9.65k
        assert(!Known.hasConflict() && "Bits known to be one AND zero?");
631
9.65k
        break;
632
9.65k
      }
633
17.5k
    }
634
31.5k
635
31.5k
    // The sign bit is the LHS's sign bit, except when the result of the
636
31.5k
    // remainder is zero.
637
31.5k
    if (DemandedMask.isSignBitSet()) {
638
29.8k
      computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1, CxtI);
639
29.8k
      // If it's known zero, our sign bit is also zero.
640
29.8k
      if (LHSKnown.isNonNegative())
641
189
        Known.makeNonNegative();
642
29.8k
    }
643
31.5k
    break;
644
47.1k
  case Instruction::URem: {
645
47.1k
    KnownBits Known2(BitWidth);
646
47.1k
    APInt AllOnes = APInt::getAllOnesValue(BitWidth);
647
47.1k
    if (SimplifyDemandedBits(I, 0, AllOnes, Known2, Depth + 1) ||
648
47.1k
        SimplifyDemandedBits(I, 1, AllOnes, Known2, Depth + 1))
649
0
      return I;
650
47.1k
651
47.1k
    unsigned Leaders = Known2.countMinLeadingZeros();
652
47.1k
    Known.Zero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask;
653
47.1k
    break;
654
47.1k
  }
655
1.78M
  case Instruction::Call:
656
1.78M
    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
657
68.5k
      switch (II->getIntrinsicID()) {
658
68.5k
      
default: break66.9k
;
659
68.5k
      case Intrinsic::bswap: {
660
780
        // If the only bits demanded come from one byte of the bswap result,
661
780
        // just shift the input byte into position to eliminate the bswap.
662
780
        unsigned NLZ = DemandedMask.countLeadingZeros();
663
780
        unsigned NTZ = DemandedMask.countTrailingZeros();
664
780
665
780
        // Round NTZ down to the next byte.  If we have 11 trailing zeros, then
666
780
        // we need all the bits down to bit 8.  Likewise, round NLZ.  If we
667
780
        // have 14 leading zeros, round to 8.
668
780
        NLZ &= ~7;
669
780
        NTZ &= ~7;
670
780
        // If we need exactly one byte, we can do this transformation.
671
780
        if (BitWidth-NLZ-NTZ == 8) {
672
7
          unsigned ResultBit = NTZ;
673
7
          unsigned InputBit = BitWidth-NTZ-8;
674
7
675
7
          // Replace this with either a left or right shift to get the byte into
676
7
          // the right place.
677
7
          Instruction *NewVal;
678
7
          if (InputBit > ResultBit)
679
4
            NewVal = BinaryOperator::CreateLShr(II->getArgOperand(0),
680
4
                    ConstantInt::get(I->getType(), InputBit-ResultBit));
681
3
          else
682
3
            NewVal = BinaryOperator::CreateShl(II->getArgOperand(0),
683
3
                    ConstantInt::get(I->getType(), ResultBit-InputBit));
684
7
          NewVal->takeName(I);
685
7
          return InsertNewInstWith(NewVal, *I);
686
7
        }
687
773
688
773
        // TODO: Could compute known zero/one bits based on the input.
689
773
        break;
690
773
      }
691
813
      case Intrinsic::fshr:
692
813
      case Intrinsic::fshl: {
693
813
        const APInt *SA;
694
813
        if (!match(I->getOperand(2), m_APInt(SA)))
695
195
          break;
696
618
697
618
        // Normalize to funnel shift left. APInt shifts of BitWidth are well-
698
618
        // defined, so no need to special-case zero shifts here.
699
618
        uint64_t ShiftAmt = SA->urem(BitWidth);
700
618
        if (II->getIntrinsicID() == Intrinsic::fshr)
701
0
          ShiftAmt = BitWidth - ShiftAmt;
702
618
703
618
        APInt DemandedMaskLHS(DemandedMask.lshr(ShiftAmt));
704
618
        APInt DemandedMaskRHS(DemandedMask.shl(BitWidth - ShiftAmt));
705
618
        if (SimplifyDemandedBits(I, 0, DemandedMaskLHS, LHSKnown, Depth + 1) ||
706
618
            
SimplifyDemandedBits(I, 1, DemandedMaskRHS, RHSKnown, Depth + 1)609
)
707
16
          return I;
708
602
709
602
        Known.Zero = LHSKnown.Zero.shl(ShiftAmt) |
710
602
                     RHSKnown.Zero.lshr(BitWidth - ShiftAmt);
711
602
        Known.One = LHSKnown.One.shl(ShiftAmt) |
712
602
                    RHSKnown.One.lshr(BitWidth - ShiftAmt);
713
602
        break;
714
602
      }
715
602
      case Intrinsic::x86_mmx_pmovmskb:
716
2
      case Intrinsic::x86_sse_movmsk_ps:
717
2
      case Intrinsic::x86_sse2_movmsk_pd:
718
2
      case Intrinsic::x86_sse2_pmovmskb_128:
719
2
      case Intrinsic::x86_avx_movmsk_ps_256:
720
2
      case Intrinsic::x86_avx_movmsk_pd_256:
721
2
      case Intrinsic::x86_avx2_pmovmskb: {
722
2
        // MOVMSK copies the vector elements' sign bits to the low bits
723
2
        // and zeros the high bits.
724
2
        unsigned ArgWidth;
725
2
        if (II->getIntrinsicID() == Intrinsic::x86_mmx_pmovmskb) {
726
2
          ArgWidth = 8; // Arg is x86_mmx, but treated as <8 x i8>.
727
2
        } else {
728
0
          auto Arg = II->getArgOperand(0);
729
0
          auto ArgType = cast<VectorType>(Arg->getType());
730
0
          ArgWidth = ArgType->getNumElements();
731
0
        }
732
2
733
2
        // If we don't need any of low bits then return zero,
734
2
        // we know that DemandedMask is non-zero already.
735
2
        APInt DemandedElts = DemandedMask.zextOrTrunc(ArgWidth);
736
2
        if (DemandedElts.isNullValue())
737
1
          return ConstantInt::getNullValue(VTy);
738
1
739
1
        // We know that the upper bits are set to zero.
740
1
        Known.Zero.setBitsFrom(ArgWidth);
741
1
        return nullptr;
742
1
      }
743
1
      case Intrinsic::x86_sse42_crc32_64_64:
744
1
        Known.Zero.setBitsFrom(32);
745
1
        return nullptr;
746
1.78M
      }
747
1.78M
    }
748
1.78M
    computeKnownBits(V, Known, Depth, CxtI);
749
1.78M
    break;
750
31.8M
  }
751
31.8M
752
31.8M
  // If the client is only demanding bits that we know, return the known
753
31.8M
  // constant.
754
31.8M
  if (DemandedMask.isSubsetOf(Known.Zero|Known.One))
755
181
    return Constant::getIntegerValue(VTy, Known.One);
756
31.8M
  return nullptr;
757
31.8M
}
758
759
/// Helper routine of SimplifyDemandedUseBits. It computes Known
760
/// bits. It also tries to handle simplifications that can be done based on
761
/// DemandedMask, but without modifying the Instruction.
762
Value *InstCombiner::SimplifyMultipleUseDemandedBits(Instruction *I,
763
                                                     const APInt &DemandedMask,
764
                                                     KnownBits &Known,
765
                                                     unsigned Depth,
766
8.98M
                                                     Instruction *CxtI) {
767
8.98M
  unsigned BitWidth = DemandedMask.getBitWidth();
768
8.98M
  Type *ITy = I->getType();
769
8.98M
770
8.98M
  KnownBits LHSKnown(BitWidth);
771
8.98M
  KnownBits RHSKnown(BitWidth);
772
8.98M
773
8.98M
  // Despite the fact that we can't simplify this instruction in all User's
774
8.98M
  // context, we can at least compute the known bits, and we can
775
8.98M
  // do simplifications that apply to *just* the one user if we know that
776
8.98M
  // this instruction has a simpler value in that context.
777
8.98M
  switch (I->getOpcode()) {
778
8.98M
  case Instruction::And: {
779
321k
    // If either the LHS or the RHS are Zero, the result is zero.
780
321k
    computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
781
321k
    computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1,
782
321k
                     CxtI);
783
321k
784
321k
    // Output known-0 are known to be clear if zero in either the LHS | RHS.
785
321k
    APInt IKnownZero = RHSKnown.Zero | LHSKnown.Zero;
786
321k
    // Output known-1 bits are only known if set in both the LHS & RHS.
787
321k
    APInt IKnownOne = RHSKnown.One & LHSKnown.One;
788
321k
789
321k
    // If the client is only demanding bits that we know, return the known
790
321k
    // constant.
791
321k
    if (DemandedMask.isSubsetOf(IKnownZero|IKnownOne))
792
6
      return Constant::getIntegerValue(ITy, IKnownOne);
793
321k
794
321k
    // If all of the demanded bits are known 1 on one side, return the other.
795
321k
    // These bits cannot contribute to the result of the 'and' in this
796
321k
    // context.
797
321k
    if (DemandedMask.isSubsetOf(LHSKnown.Zero | RHSKnown.One))
798
898
      return I->getOperand(0);
799
320k
    if (DemandedMask.isSubsetOf(RHSKnown.Zero | LHSKnown.One))
800
0
      return I->getOperand(1);
801
320k
802
320k
    Known.Zero = std::move(IKnownZero);
803
320k
    Known.One  = std::move(IKnownOne);
804
320k
    break;
805
320k
  }
806
320k
  case Instruction::Or: {
807
162k
    // We can simplify (X|Y) -> X or Y in the user's context if we know that
808
162k
    // only bits from X or Y are demanded.
809
162k
810
162k
    // If either the LHS or the RHS are One, the result is One.
811
162k
    computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
812
162k
    computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1,
813
162k
                     CxtI);
814
162k
815
162k
    // Output known-0 bits are only known if clear in both the LHS & RHS.
816
162k
    APInt IKnownZero = RHSKnown.Zero & LHSKnown.Zero;
817
162k
    // Output known-1 are known to be set if set in either the LHS | RHS.
818
162k
    APInt IKnownOne = RHSKnown.One | LHSKnown.One;
819
162k
820
162k
    // If the client is only demanding bits that we know, return the known
821
162k
    // constant.
822
162k
    if (DemandedMask.isSubsetOf(IKnownZero|IKnownOne))
823
25
      return Constant::getIntegerValue(ITy, IKnownOne);
824
162k
825
162k
    // If all of the demanded bits are known zero on one side, return the
826
162k
    // other.  These bits cannot contribute to the result of the 'or' in this
827
162k
    // context.
828
162k
    if (DemandedMask.isSubsetOf(LHSKnown.One | RHSKnown.Zero))
829
1.14k
      return I->getOperand(0);
830
161k
    if (DemandedMask.isSubsetOf(RHSKnown.One | LHSKnown.Zero))
831
1.12k
      return I->getOperand(1);
832
160k
833
160k
    Known.Zero = std::move(IKnownZero);
834
160k
    Known.One  = std::move(IKnownOne);
835
160k
    break;
836
160k
  }
837
160k
  case Instruction::Xor: {
838
129k
    // We can simplify (X^Y) -> X or Y in the user's context if we know that
839
129k
    // only bits from X or Y are demanded.
840
129k
841
129k
    computeKnownBits(I->getOperand(1), RHSKnown, Depth + 1, CxtI);
842
129k
    computeKnownBits(I->getOperand(0), LHSKnown, Depth + 1,
843
129k
                     CxtI);
844
129k
845
129k
    // Output known-0 bits are known if clear or set in both the LHS & RHS.
846
129k
    APInt IKnownZero = (RHSKnown.Zero & LHSKnown.Zero) |
847
129k
                       (RHSKnown.One & LHSKnown.One);
848
129k
    // Output known-1 are known to be set if set in only one of the LHS, RHS.
849
129k
    APInt IKnownOne =  (RHSKnown.Zero & LHSKnown.One) |
850
129k
                       (RHSKnown.One & LHSKnown.Zero);
851
129k
852
129k
    // If the client is only demanding bits that we know, return the known
853
129k
    // constant.
854
129k
    if (DemandedMask.isSubsetOf(IKnownZero|IKnownOne))
855
1
      return Constant::getIntegerValue(ITy, IKnownOne);
856
129k
857
129k
    // If all of the demanded bits are known zero on one side, return the
858
129k
    // other.
859
129k
    if (DemandedMask.isSubsetOf(RHSKnown.Zero))
860
26
      return I->getOperand(0);
861
129k
    if (DemandedMask.isSubsetOf(LHSKnown.Zero))
862
88
      return I->getOperand(1);
863
129k
864
129k
    // Output known-0 bits are known if clear or set in both the LHS & RHS.
865
129k
    Known.Zero = std::move(IKnownZero);
866
129k
    // Output known-1 are known to be set if set in only one of the LHS, RHS.
867
129k
    Known.One  = std::move(IKnownOne);
868
129k
    break;
869
129k
  }
870
8.36M
  default:
871
8.36M
    // Compute the Known bits to simplify things downstream.
872
8.36M
    computeKnownBits(I, Known, Depth, CxtI);
873
8.36M
874
8.36M
    // If this user is only demanding bits that we know, return the known
875
8.36M
    // constant.
876
8.36M
    if (DemandedMask.isSubsetOf(Known.Zero|Known.One))
877
171
      return Constant::getIntegerValue(ITy, Known.One);
878
8.36M
879
8.36M
    break;
880
8.97M
  }
881
8.97M
882
8.97M
  return nullptr;
883
8.97M
}
884
885
886
/// Helper routine of SimplifyDemandedUseBits. It tries to simplify
887
/// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into
888
/// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign
889
/// of "C2-C1".
890
///
891
/// Suppose E1 and E2 are generally different in bits S={bm, bm+1,
892
/// ..., bn}, without considering the specific value X is holding.
893
/// This transformation is legal iff one of following conditions is hold:
894
///  1) All the bit in S are 0, in this case E1 == E2.
895
///  2) We don't care those bits in S, per the input DemandedMask.
896
///  3) Combination of 1) and 2). Some bits in S are 0, and we don't care the
897
///     rest bits.
898
///
899
/// Currently we only test condition 2).
900
///
901
/// As with SimplifyDemandedUseBits, it returns NULL if the simplification was
902
/// not successful.
903
Value *
904
InstCombiner::simplifyShrShlDemandedBits(Instruction *Shr, const APInt &ShrOp1,
905
                                         Instruction *Shl, const APInt &ShlOp1,
906
                                         const APInt &DemandedMask,
907
24.3k
                                         KnownBits &Known) {
908
24.3k
  if (!ShlOp1 || !ShrOp1)
909
0
    return nullptr; // No-op.
910
24.3k
911
24.3k
  Value *VarX = Shr->getOperand(0);
912
24.3k
  Type *Ty = VarX->getType();
913
24.3k
  unsigned BitWidth = Ty->getScalarSizeInBits();
914
24.3k
  if (ShlOp1.uge(BitWidth) || ShrOp1.uge(BitWidth))
915
7
    return nullptr; // Undef.
916
24.3k
917
24.3k
  unsigned ShlAmt = ShlOp1.getZExtValue();
918
24.3k
  unsigned ShrAmt = ShrOp1.getZExtValue();
919
24.3k
920
24.3k
  Known.One.clearAllBits();
921
24.3k
  Known.Zero.setLowBits(ShlAmt - 1);
922
24.3k
  Known.Zero &= DemandedMask;
923
24.3k
924
24.3k
  APInt BitMask1(APInt::getAllOnesValue(BitWidth));
925
24.3k
  APInt BitMask2(APInt::getAllOnesValue(BitWidth));
926
24.3k
927
24.3k
  bool isLshr = (Shr->getOpcode() == Instruction::LShr);
928
24.3k
  BitMask1 = isLshr ? 
(BitMask1.lshr(ShrAmt) << ShlAmt)22.1k
:
929
24.3k
                      
(BitMask1.ashr(ShrAmt) << ShlAmt)2.14k
;
930
24.3k
931
24.3k
  if (ShrAmt <= ShlAmt) {
932
15.2k
    BitMask2 <<= (ShlAmt - ShrAmt);
933
15.2k
  } else {
934
9.08k
    BitMask2 = isLshr ? 
BitMask2.lshr(ShrAmt - ShlAmt)7.31k
:
935
9.08k
                        
BitMask2.ashr(ShrAmt - ShlAmt)1.76k
;
936
9.08k
  }
937
24.3k
938
24.3k
  // Check if condition-2 (see the comment to this function) is satified.
939
24.3k
  if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) {
940
574
    if (ShrAmt == ShlAmt)
941
80
      return VarX;
942
494
943
494
    if (!Shr->hasOneUse())
944
273
      return nullptr;
945
221
946
221
    BinaryOperator *New;
947
221
    if (ShrAmt < ShlAmt) {
948
144
      Constant *Amt = ConstantInt::get(VarX->getType(), ShlAmt - ShrAmt);
949
144
      New = BinaryOperator::CreateShl(VarX, Amt);
950
144
      BinaryOperator *Orig = cast<BinaryOperator>(Shl);
951
144
      New->setHasNoSignedWrap(Orig->hasNoSignedWrap());
952
144
      New->setHasNoUnsignedWrap(Orig->hasNoUnsignedWrap());
953
144
    } else {
954
77
      Constant *Amt = ConstantInt::get(VarX->getType(), ShrAmt - ShlAmt);
955
77
      New = isLshr ? 
BinaryOperator::CreateLShr(VarX, Amt)75
:
956
77
                     
BinaryOperator::CreateAShr(VarX, Amt)2
;
957
77
      if (cast<BinaryOperator>(Shr)->isExact())
958
1
        New->setIsExact(true);
959
77
    }
960
221
961
221
    return InsertNewInstWith(New, *Shl);
962
221
  }
963
23.7k
964
23.7k
  return nullptr;
965
23.7k
}
966
967
/// Implement SimplifyDemandedVectorElts for amdgcn buffer and image intrinsics.
968
///
969
/// Note: This only supports non-TFE/LWE image intrinsic calls; those have
970
///       struct returns.
971
Value *InstCombiner::simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II,
972
                                                           APInt DemandedElts,
973
541
                                                           int DMaskIdx) {
974
541
  unsigned VWidth = II->getType()->getVectorNumElements();
975
541
  if (VWidth == 1)
976
6
    return nullptr;
977
535
978
535
  ConstantInt *NewDMask = nullptr;
979
535
980
535
  if (DMaskIdx < 0) {
981
360
    // Pretend that a prefix of elements is demanded to simplify the code
982
360
    // below.
983
360
    DemandedElts = (1 << DemandedElts.getActiveBits()) - 1;
984
360
  } else {
985
175
    ConstantInt *DMask = cast<ConstantInt>(II->getArgOperand(DMaskIdx));
986
175
    unsigned DMaskVal = DMask->getZExtValue() & 0xf;
987
175
988
175
    // Mask off values that are undefined because the dmask doesn't cover them
989
175
    DemandedElts &= (1 << countPopulation(DMaskVal)) - 1;
990
175
991
175
    unsigned NewDMaskVal = 0;
992
175
    unsigned OrigLoadIdx = 0;
993
875
    for (unsigned SrcIdx = 0; SrcIdx < 4; 
++SrcIdx700
) {
994
700
      const unsigned Bit = 1 << SrcIdx;
995
700
      if (!!(DMaskVal & Bit)) {
996
543
        if (!!DemandedElts[OrigLoadIdx])
997
408
          NewDMaskVal |= Bit;
998
543
        OrigLoadIdx++;
999
543
      }
1000
700
    }
1001
175
1002
175
    if (DMaskVal != NewDMaskVal)
1003
51
      NewDMask = ConstantInt::get(DMask->getType(), NewDMaskVal);
1004
175
  }
1005
535
1006
535
  unsigned NewNumElts = DemandedElts.countPopulation();
1007
535
  if (!NewNumElts)
1008
1
    return UndefValue::get(II->getType());
1009
534
1010
534
  if (NewNumElts >= VWidth && 
DemandedElts.isMask()397
) {
1011
397
    if (NewDMask)
1012
0
      II->setArgOperand(DMaskIdx, NewDMask);
1013
397
    return nullptr;
1014
397
  }
1015
137
1016
137
  // Determine the overload types of the original intrinsic.
1017
137
  auto IID = II->getIntrinsicID();
1018
137
  SmallVector<Intrinsic::IITDescriptor, 16> Table;
1019
137
  getIntrinsicInfoTableEntries(IID, Table);
1020
137
  ArrayRef<Intrinsic::IITDescriptor> TableRef = Table;
1021
137
1022
137
  // Validate function argument and return types, extracting overloaded types
1023
137
  // along the way.
1024
137
  FunctionType *FTy = II->getCalledFunction()->getFunctionType();
1025
137
  SmallVector<Type *, 6> OverloadTys;
1026
137
  Intrinsic::matchIntrinsicSignature(FTy, TableRef, OverloadTys);
1027
137
1028
137
  Module *M = II->getParent()->getParent()->getParent();
1029
137
  Type *EltTy = II->getType()->getVectorElementType();
1030
137
  Type *NewTy = (NewNumElts == 1) ? 
EltTy83
:
VectorType::get(EltTy, NewNumElts)54
;
1031
137
1032
137
  OverloadTys[0] = NewTy;
1033
137
  Function *NewIntrin = Intrinsic::getDeclaration(M, IID, OverloadTys);
1034
137
1035
137
  SmallVector<Value *, 16> Args;
1036
1.03k
  for (unsigned I = 0, E = II->getNumArgOperands(); I != E; 
++I902
)
1037
902
    Args.push_back(II->getArgOperand(I));
1038
137
1039
137
  if (NewDMask)
1040
51
    Args[DMaskIdx] = NewDMask;
1041
137
1042
137
  IRBuilderBase::InsertPointGuard Guard(Builder);
1043
137
  Builder.SetInsertPoint(II);
1044
137
1045
137
  CallInst *NewCall = Builder.CreateCall(NewIntrin, Args);
1046
137
  NewCall->takeName(II);
1047
137
  NewCall->copyMetadata(*II);
1048
137
1049
137
  if (NewNumElts == 1) {
1050
83
    return Builder.CreateInsertElement(UndefValue::get(II->getType()), NewCall,
1051
83
                                       DemandedElts.countTrailingZeros());
1052
83
  }
1053
54
1054
54
  SmallVector<uint32_t, 8> EltMask;
1055
54
  unsigned NewLoadIdx = 0;
1056
257
  for (unsigned OrigLoadIdx = 0; OrigLoadIdx < VWidth; 
++OrigLoadIdx203
) {
1057
203
    if (!!DemandedElts[OrigLoadIdx])
1058
129
      EltMask.push_back(NewLoadIdx++);
1059
74
    else
1060
74
      EltMask.push_back(NewNumElts);
1061
203
  }
1062
54
1063
54
  Value *Shuffle =
1064
54
      Builder.CreateShuffleVector(NewCall, UndefValue::get(NewTy), EltMask);
1065
54
1066
54
  return Shuffle;
1067
54
}
1068
1069
/// The specified value produces a vector with any number of elements.
1070
/// DemandedElts contains the set of elements that are actually used by the
1071
/// caller. This method analyzes which elements of the operand are undef and
1072
/// returns that information in UndefElts.
1073
///
1074
/// If the information about demanded elements can be used to simplify the
1075
/// operation, the operation is simplified, then the resultant value is
1076
/// returned.  This returns null if no change was made.
1077
Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
1078
                                                APInt &UndefElts,
1079
1.20M
                                                unsigned Depth) {
1080
1.20M
  unsigned VWidth = V->getType()->getVectorNumElements();
1081
1.20M
  APInt EltMask(APInt::getAllOnesValue(VWidth));
1082
1.20M
  assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!");
1083
1.20M
1084
1.20M
  if (isa<UndefValue>(V)) {
1085
365k
    // If the entire vector is undefined, just return this info.
1086
365k
    UndefElts = EltMask;
1087
365k
    return nullptr;
1088
365k
  }
1089
837k
1090
837k
  if (DemandedElts.isNullValue()) { // If nothing is demanded, provide undef.
1091
1.79k
    UndefElts = EltMask;
1092
1.79k
    return UndefValue::get(V->getType());
1093
1.79k
  }
1094
835k
1095
835k
  UndefElts = 0;
1096
835k
1097
835k
  if (auto *C = dyn_cast<Constant>(V)) {
1098
14.0k
    // Check if this is identity. If so, return 0 since we are not simplifying
1099
14.0k
    // anything.
1100
14.0k
    if (DemandedElts.isAllOnesValue())
1101
8.68k
      return nullptr;
1102
5.32k
1103
5.32k
    Type *EltTy = cast<VectorType>(V->getType())->getElementType();
1104
5.32k
    Constant *Undef = UndefValue::get(EltTy);
1105
5.32k
    SmallVector<Constant*, 16> Elts;
1106
29.0k
    for (unsigned i = 0; i != VWidth; 
++i23.7k
) {
1107
23.7k
      if (!DemandedElts[i]) {   // If not demanded, set to undef.
1108
10.2k
        Elts.push_back(Undef);
1109
10.2k
        UndefElts.setBit(i);
1110
10.2k
        continue;
1111
10.2k
      }
1112
13.4k
1113
13.4k
      Constant *Elt = C->getAggregateElement(i);
1114
13.4k
      if (!Elt) 
return nullptr0
;
1115
13.4k
1116
13.4k
      if (isa<UndefValue>(Elt)) {   // Already undef.
1117
870
        Elts.push_back(Undef);
1118
870
        UndefElts.setBit(i);
1119
12.5k
      } else {                               // Otherwise, defined.
1120
12.5k
        Elts.push_back(Elt);
1121
12.5k
      }
1122
13.4k
    }
1123
5.32k
1124
5.32k
    // If we changed the constant, return it.
1125
5.32k
    Constant *NewCV = ConstantVector::get(Elts);
1126
5.32k
    return NewCV != C ? 
NewCV544
:
nullptr4.78k
;
1127
821k
  }
1128
821k
1129
821k
  // Limit search depth.
1130
821k
  if (Depth == 10)
1131
571
    return nullptr;
1132
821k
1133
821k
  // If multiple users are using the root value, proceed with
1134
821k
  // simplification conservatively assuming that all elements
1135
821k
  // are needed.
1136
821k
  if (!V->hasOneUse()) {
1137
176k
    // Quit if we find multiple users of a non-root value though.
1138
176k
    // They'll be handled when it's their turn to be visited by
1139
176k
    // the main instcombine process.
1140
176k
    if (Depth != 0)
1141
157k
      // TODO: Just compute the UndefElts information recursively.
1142
157k
      return nullptr;
1143
19.1k
1144
19.1k
    // Conservatively assume that all elements are needed.
1145
19.1k
    DemandedElts = EltMask;
1146
19.1k
  }
1147
821k
1148
821k
  Instruction *I = dyn_cast<Instruction>(V);
1149
663k
  if (!I) 
return nullptr9.10k
; // Only analyze instructions.
1150
654k
1151
654k
  bool MadeChange = false;
1152
654k
  auto simplifyAndSetOp = [&](Instruction *Inst, unsigned OpNum,
1153
796k
                              APInt Demanded, APInt &Undef) {
1154
796k
    auto *II = dyn_cast<IntrinsicInst>(Inst);
1155
796k
    Value *Op = II ? 
II->getArgOperand(OpNum)2.43k
:
Inst->getOperand(OpNum)793k
;
1156
796k
    if (Value *V = SimplifyDemandedVectorElts(Op, Demanded, Undef, Depth + 1)) {
1157
6.26k
      if (II)
1158
164
        II->setArgOperand(OpNum, V);
1159
6.09k
      else
1160
6.09k
        Inst->setOperand(OpNum, V);
1161
6.26k
      MadeChange = true;
1162
6.26k
    }
1163
796k
  };
1164
654k
1165
654k
  APInt UndefElts2(VWidth, 0);
1166
654k
  APInt UndefElts3(VWidth, 0);
1167
654k
  switch (I->getOpcode()) {
1168
654k
  
default: break72.9k
;
1169
654k
1170
654k
  case Instruction::GetElementPtr: {
1171
1.46k
    // The LangRef requires that struct geps have all constant indices.  As
1172
1.46k
    // such, we can't convert any operand to partial undef.
1173
1.46k
    auto mayIndexStructType = [](GetElementPtrInst &GEP) {
1174
1.46k
      for (auto I = gep_type_begin(GEP), E = gep_type_end(GEP);
1175
2.94k
           I != E; 
I++1.48k
)
1176
1.85k
        if (I.isStruct())
1177
1.09k
          
return true370
;;
1178
1.09k
      return false;
1179
1.46k
    };
1180
1.46k
    if (mayIndexStructType(cast<GetElementPtrInst>(*I)))
1181
370
      break;
1182
1.09k
    
1183
1.09k
    // Conservatively track the demanded elements back through any vector
1184
1.09k
    // operands we may have.  We know there must be at least one, or we
1185
1.09k
    // wouldn't have a vector result to get here. Note that we intentionally
1186
1.09k
    // merge the undef bits here since gepping with either an undef base or
1187
1.09k
    // index results in undef. 
1188
3.29k
    
for (unsigned i = 0; 1.09k
i < I->getNumOperands();
i++2.20k
) {
1189
2.20k
      if (isa<UndefValue>(I->getOperand(i))) {
1190
0
        // If the entire vector is undefined, just return this info.
1191
0
        UndefElts = EltMask;
1192
0
        return nullptr;
1193
0
      }
1194
2.20k
      if (I->getOperand(i)->getType()->isVectorTy()) {
1195
1.26k
        APInt UndefEltsOp(VWidth, 0);
1196
1.26k
        simplifyAndSetOp(I, i, DemandedElts, UndefEltsOp);
1197
1.26k
        UndefElts |= UndefEltsOp;
1198
1.26k
      }
1199
2.20k
    }
1200
1.09k
1201
1.09k
    break;
1202
1.09k
  }
1203
273k
  case Instruction::InsertElement: {
1204
273k
    // If this is a variable index, we don't know which element it overwrites.
1205
273k
    // demand exactly the same input as we produce.
1206
273k
    ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2));
1207
273k
    if (!Idx) {
1208
867
      // Note that we can't propagate undef elt info, because we don't know
1209
867
      // which elt is getting updated.
1210
867
      simplifyAndSetOp(I, 0, DemandedElts, UndefElts2);
1211
867
      break;
1212
867
    }
1213
272k
1214
272k
    // The element inserted overwrites whatever was there, so the input demanded
1215
272k
    // set is simpler than the output set.
1216
272k
    unsigned IdxNo = Idx->getZExtValue();
1217
272k
    APInt PreInsertDemandedElts = DemandedElts;
1218
272k
    if (IdxNo < VWidth)
1219
272k
      PreInsertDemandedElts.clearBit(IdxNo);
1220
272k
1221
272k
    simplifyAndSetOp(I, 0, PreInsertDemandedElts, UndefElts);
1222
272k
1223
272k
    // If this is inserting an element that isn't demanded, remove this
1224
272k
    // insertelement.
1225
272k
    if (IdxNo >= VWidth || !DemandedElts[IdxNo]) {
1226
131
      Worklist.Add(I);
1227
131
      return I->getOperand(0);
1228
131
    }
1229
272k
1230
272k
    // The inserted element is defined.
1231
272k
    UndefElts.clearBit(IdxNo);
1232
272k
    break;
1233
272k
  }
1234
272k
  case Instruction::ShuffleVector: {
1235
226k
    ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I);
1236
226k
    unsigned LHSVWidth =
1237
226k
      Shuffle->getOperand(0)->getType()->getVectorNumElements();
1238
226k
    APInt LeftDemanded(LHSVWidth, 0), RightDemanded(LHSVWidth, 0);
1239
1.27M
    for (unsigned i = 0; i < VWidth; 
i++1.05M
) {
1240
1.05M
      if (DemandedElts[i]) {
1241
1.01M
        unsigned MaskVal = Shuffle->getMaskValue(i);
1242
1.01M
        if (MaskVal != -1u) {
1243
970k
          assert(MaskVal < LHSVWidth * 2 &&
1244
970k
                 "shufflevector mask index out of range!");
1245
970k
          if (MaskVal < LHSVWidth)
1246
797k
            LeftDemanded.setBit(MaskVal);
1247
172k
          else
1248
172k
            RightDemanded.setBit(MaskVal - LHSVWidth);
1249
970k
        }
1250
1.01M
      }
1251
1.05M
    }
1252
226k
1253
226k
    APInt LHSUndefElts(LHSVWidth, 0);
1254
226k
    simplifyAndSetOp(I, 0, LeftDemanded, LHSUndefElts);
1255
226k
1256
226k
    APInt RHSUndefElts(LHSVWidth, 0);
1257
226k
    simplifyAndSetOp(I, 1, RightDemanded, RHSUndefElts);
1258
226k
1259
226k
    bool NewUndefElts = false;
1260
226k
    unsigned LHSIdx = -1u, LHSValIdx = -1u;
1261
226k
    unsigned RHSIdx = -1u, RHSValIdx = -1u;
1262
226k
    bool LHSUniform = true;
1263
226k
    bool RHSUniform = true;
1264
1.27M
    for (unsigned i = 0; i < VWidth; 
i++1.05M
) {
1265
1.05M
      unsigned MaskVal = Shuffle->getMaskValue(i);
1266
1.05M
      if (MaskVal == -1u) {
1267
74.9k
        UndefElts.setBit(i);
1268
976k
      } else if (!DemandedElts[i]) {
1269
6.34k
        NewUndefElts = true;
1270
6.34k
        UndefElts.setBit(i);
1271
970k
      } else if (MaskVal < LHSVWidth) {
1272
797k
        if (LHSUndefElts[MaskVal]) {
1273
39
          NewUndefElts = true;
1274
39
          UndefElts.setBit(i);
1275
797k
        } else {
1276
797k
          LHSIdx = LHSIdx == -1u ? 
i225k
:
LHSVWidth571k
;
1277
797k
          LHSValIdx = LHSValIdx == -1u ? 
MaskVal225k
:
LHSVWidth571k
;
1278
797k
          LHSUniform = LHSUniform && 
(MaskVal == i)516k
;
1279
797k
        }
1280
797k
      } else {
1281
172k
        if (RHSUndefElts[MaskVal - LHSVWidth]) {
1282
43
          NewUndefElts = true;
1283
43
          UndefElts.setBit(i);
1284
172k
        } else {
1285
172k
          RHSIdx = RHSIdx == -1u ? 
i35.0k
:
LHSVWidth137k
;
1286
172k
          RHSValIdx = RHSValIdx == -1u ? 
MaskVal - LHSVWidth35.0k
:
LHSVWidth137k
;
1287
172k
          RHSUniform = RHSUniform && 
(MaskVal - LHSVWidth == i)38.6k
;
1288
172k
        }
1289
172k
      }
1290
1.05M
    }
1291
226k
1292
226k
    // Try to transform shuffle with constant vector and single element from
1293
226k
    // this constant vector to single insertelement instruction.
1294
226k
    // shufflevector V, C, <v1, v2, .., ci, .., vm> ->
1295
226k
    // insertelement V, C[ci], ci-n
1296
226k
    if (LHSVWidth == Shuffle->getType()->getNumElements()) {
1297
80.7k
      Value *Op = nullptr;
1298
80.7k
      Constant *Value = nullptr;
1299
80.7k
      unsigned Idx = -1u;
1300
80.7k
1301
80.7k
      // Find constant vector with the single element in shuffle (LHS or RHS).
1302
80.7k
      if (LHSIdx < LHSVWidth && 
RHSUniform4.54k
) {
1303
3.77k
        if (auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(0))) {
1304
10
          Op = Shuffle->getOperand(1);
1305
10
          Value = CV->getOperand(LHSValIdx);
1306
10
          Idx = LHSIdx;
1307
10
        }
1308
3.77k
      }
1309
80.7k
      if (RHSIdx < LHSVWidth && 
LHSUniform1.66k
) {
1310
1.15k
        if (auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(1))) {
1311
3
          Op = Shuffle->getOperand(0);
1312
3
          Value = CV->getOperand(RHSValIdx);
1313
3
          Idx = RHSIdx;
1314
3
        }
1315
1.15k
      }
1316
80.7k
      // Found constant vector with single element - convert to insertelement.
1317
80.7k
      if (Op && 
Value13
) {
1318
13
        Instruction *New = InsertElementInst::Create(
1319
13
            Op, Value, ConstantInt::get(Type::getInt32Ty(I->getContext()), Idx),
1320
13
            Shuffle->getName());
1321
13
        InsertNewInstWith(New, *Shuffle);
1322
13
        return New;
1323
13
      }
1324
226k
    }
1325
226k
    if (NewUndefElts) {
1326
844
      // Add additional discovered undefs.
1327
844
      SmallVector<Constant*, 16> Elts;
1328
10.6k
      for (unsigned i = 0; i < VWidth; 
++i9.77k
) {
1329
9.77k
        if (UndefElts[i])
1330
6.60k
          Elts.push_back(UndefValue::get(Type::getInt32Ty(I->getContext())));
1331
3.17k
        else
1332
3.17k
          Elts.push_back(ConstantInt::get(Type::getInt32Ty(I->getContext()),
1333
3.17k
                                          Shuffle->getMaskValue(i)));
1334
9.77k
      }
1335
844
      I->setOperand(2, ConstantVector::get(Elts));
1336
844
      MadeChange = true;
1337
844
    }
1338
226k
    break;
1339
226k
  }
1340
226k
  case Instruction::Select: {
1341
8.28k
    // If this is a vector select, try to transform the select condition based
1342
8.28k
    // on the current demanded elements.
1343
8.28k
    SelectInst *Sel = cast<SelectInst>(I);
1344
8.28k
    if (Sel->getCondition()->getType()->isVectorTy()) {
1345
7.96k
      // TODO: We are not doing anything with UndefElts based on this call.
1346
7.96k
      // It is overwritten below based on the other select operands. If an
1347
7.96k
      // element of the select condition is known undef, then we are free to
1348
7.96k
      // choose the output value from either arm of the select. If we know that
1349
7.96k
      // one of those values is undef, then the output can be undef.
1350
7.96k
      simplifyAndSetOp(I, 0, DemandedElts, UndefElts);
1351
7.96k
    }
1352
8.28k
1353
8.28k
    // Next, see if we can transform the arms of the select.
1354
8.28k
    APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts);
1355
8.28k
    if (auto *CV = dyn_cast<ConstantVector>(Sel->getCondition())) {
1356
10
      for (unsigned i = 0; i < VWidth; 
i++8
) {
1357
8
        // isNullValue() always returns false when called on a ConstantExpr.
1358
8
        // Skip constant expressions to avoid propagating incorrect information.
1359
8
        Constant *CElt = CV->getAggregateElement(i);
1360
8
        if (isa<ConstantExpr>(CElt))
1361
1
          continue;
1362
7
        // TODO: If a select condition element is undef, we can demand from
1363
7
        // either side. If one side is known undef, choosing that side would
1364
7
        // propagate undef.
1365
7
        if (CElt->isNullValue())
1366
2
          DemandedLHS.clearBit(i);
1367
5
        else
1368
5
          DemandedRHS.clearBit(i);
1369
7
      }
1370
2
    }
1371
8.28k
1372
8.28k
    simplifyAndSetOp(I, 1, DemandedLHS, UndefElts2);
1373
8.28k
    simplifyAndSetOp(I, 2, DemandedRHS, UndefElts3);
1374
8.28k
1375
8.28k
    // Output elements are undefined if the element from each arm is undefined.
1376
8.28k
    // TODO: This can be improved. See comment in select condition handling.
1377
8.28k
    UndefElts = UndefElts2 & UndefElts3;
1378
8.28k
    break;
1379
226k
  }
1380
226k
  case Instruction::BitCast: {
1381
4.85k
    // Vector->vector casts only.
1382
4.85k
    VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType());
1383
4.85k
    if (!VTy) 
break624
;
1384
4.23k
    unsigned InVWidth = VTy->getNumElements();
1385
4.23k
    APInt InputDemandedElts(InVWidth, 0);
1386
4.23k
    UndefElts2 = APInt(InVWidth, 0);
1387
4.23k
    unsigned Ratio;
1388
4.23k
1389
4.23k
    if (VWidth == InVWidth) {
1390
597
      // If we are converting from <4 x i32> -> <4 x f32>, we demand the same
1391
597
      // elements as are demanded of us.
1392
597
      Ratio = 1;
1393
597
      InputDemandedElts = DemandedElts;
1394
3.63k
    } else if ((VWidth % InVWidth) == 0) {
1395
3.33k
      // If the number of elements in the output is a multiple of the number of
1396
3.33k
      // elements in the input then an input element is live if any of the
1397
3.33k
      // corresponding output elements are live.
1398
3.33k
      Ratio = VWidth / InVWidth;
1399
20.9k
      for (unsigned OutIdx = 0; OutIdx != VWidth; 
++OutIdx17.5k
)
1400
17.5k
        if (DemandedElts[OutIdx])
1401
6.39k
          InputDemandedElts.setBit(OutIdx / Ratio);
1402
3.33k
    } else 
if (300
(InVWidth % VWidth) == 0300
) {
1403
300
      // If the number of elements in the input is a multiple of the number of
1404
300
      // elements in the output then an input element is live if the
1405
300
      // corresponding output element is live.
1406
300
      Ratio = InVWidth / VWidth;
1407
4.42k
      for (unsigned InIdx = 0; InIdx != InVWidth; 
++InIdx4.12k
)
1408
4.12k
        if (DemandedElts[InIdx / Ratio])
1409
1.95k
          InputDemandedElts.setBit(InIdx);
1410
300
    } else {
1411
0
      // Unsupported so far.
1412
0
      break;
1413
0
    }
1414
4.23k
1415
4.23k
    simplifyAndSetOp(I, 0, InputDemandedElts, UndefElts2);
1416
4.23k
1417
4.23k
    if (VWidth == InVWidth) {
1418
597
      UndefElts = UndefElts2;
1419
3.63k
    } else if ((VWidth % InVWidth) == 0) {
1420
3.33k
      // If the number of elements in the output is a multiple of the number of
1421
3.33k
      // elements in the input then an output element is undef if the
1422
3.33k
      // corresponding input element is undef.
1423
20.9k
      for (unsigned OutIdx = 0; OutIdx != VWidth; 
++OutIdx17.5k
)
1424
17.5k
        if (UndefElts2[OutIdx / Ratio])
1425
5.09k
          UndefElts.setBit(OutIdx);
1426
3.33k
    } else 
if (300
(InVWidth % VWidth) == 0300
) {
1427
300
      // If the number of elements in the input is a multiple of the number of
1428
300
      // elements in the output then an output element is undef if all of the
1429
300
      // corresponding input elements are undef.
1430
1.06k
      for (unsigned OutIdx = 0; OutIdx != VWidth; 
++OutIdx764
) {
1431
764
        APInt SubUndef = UndefElts2.lshr(OutIdx * Ratio).zextOrTrunc(Ratio);
1432
764
        if (SubUndef.countPopulation() == Ratio)
1433
35
          UndefElts.setBit(OutIdx);
1434
764
      }
1435
300
    } else {
1436
0
      llvm_unreachable("Unimp");
1437
0
    }
1438
4.23k
    break;
1439
4.23k
  }
1440
4.23k
  case Instruction::FPTrunc:
1441
109
  case Instruction::FPExt:
1442
109
    simplifyAndSetOp(I, 0, DemandedElts, UndefElts);
1443
109
    break;
1444
109
1445
67.2k
  case Instruction::Call: {
1446
67.2k
    IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
1447
67.2k
    if (!II) 
break6.60k
;
1448
60.6k
    switch (II->getIntrinsicID()) {
1449
60.6k
    case Intrinsic::masked_gather: // fallthrough
1450
508
    case Intrinsic::masked_load: {
1451
508
      // Subtlety: If we load from a pointer, the pointer must be valid
1452
508
      // regardless of whether the element is demanded.  Doing otherwise risks
1453
508
      // segfaults which didn't exist in the original program.
1454
508
      APInt DemandedPtrs(APInt::getAllOnesValue(VWidth)),
1455
508
        DemandedPassThrough(DemandedElts);
1456
508
      if (auto *CV = dyn_cast<ConstantVector>(II->getOperand(2)))
1457
2.05k
        
for (unsigned i = 0; 219
i < VWidth;
i++1.83k
) {
1458
1.83k
          Constant *CElt = CV->getAggregateElement(i);
1459
1.83k
          if (CElt->isNullValue())
1460
134
            DemandedPtrs.clearBit(i);
1461
1.70k
          else if (CElt->isAllOnesValue())
1462
1.69k
            DemandedPassThrough.clearBit(i);
1463
1.83k
        }
1464
508
      if (II->getIntrinsicID() == Intrinsic::masked_gather)
1465
394
        simplifyAndSetOp(II, 0, DemandedPtrs, UndefElts2);
1466
508
      simplifyAndSetOp(II, 3, DemandedPassThrough, UndefElts3);
1467
508
      
1468
508
      // Output elements are undefined if the element from both sources are.
1469
508
      // TODO: can strengthen via mask as well.
1470
508
      UndefElts = UndefElts2 & UndefElts3;
1471
508
      break;
1472
508
    }
1473
508
    case Intrinsic::x86_xop_vfrcz_ss:
1474
23
    case Intrinsic::x86_xop_vfrcz_sd:
1475
23
      // The instructions for these intrinsics are speced to zero upper bits not
1476
23
      // pass them through like other scalar intrinsics. So we shouldn't just
1477
23
      // use Arg0 if DemandedElts[0] is clear like we do for other intrinsics.
1478
23
      // Instead we should return a zero vector.
1479
23
      if (!DemandedElts[0]) {
1480
2
        Worklist.Add(II);
1481
2
        return ConstantAggregateZero::get(II->getType());
1482
2
      }
1483
21
1484
21
      // Only the lower element is used.
1485
21
      DemandedElts = 1;
1486
21
      simplifyAndSetOp(II, 0, DemandedElts, UndefElts);
1487
21
1488
21
      // Only the lower element is undefined. The high elements are zero.
1489
21
      UndefElts = UndefElts[0];
1490
21
      break;
1491
21
1492
21
    // Unary scalar-as-vector operations that work column-wise.
1493
21
    case Intrinsic::x86_sse_rcp_ss:
1494
16
    case Intrinsic::x86_sse_rsqrt_ss:
1495
16
      simplifyAndSetOp(II, 0, DemandedElts, UndefElts);
1496
16
1497
16
      // If lowest element of a scalar op isn't used then use Arg0.
1498
16
      if (!DemandedElts[0]) {
1499
2
        Worklist.Add(II);
1500
2
        return II->getArgOperand(0);
1501
2
      }
1502
14
      // TODO: If only low elt lower SQRT to FSQRT (with rounding/exceptions
1503
14
      // checks).
1504
14
      break;
1505
14
1506
14
    // Binary scalar-as-vector operations that work column-wise. The high
1507
14
    // elements come from operand 0. The low element is a function of both
1508
14
    // operands.
1509
341
    case Intrinsic::x86_sse_min_ss:
1510
341
    case Intrinsic::x86_sse_max_ss:
1511
341
    case Intrinsic::x86_sse_cmp_ss:
1512
341
    case Intrinsic::x86_sse2_min_sd:
1513
341
    case Intrinsic::x86_sse2_max_sd:
1514
341
    case Intrinsic::x86_sse2_cmp_sd: {
1515
341
      simplifyAndSetOp(II, 0, DemandedElts, UndefElts);
1516
341
1517
341
      // If lowest element of a scalar op isn't used then use Arg0.
1518
341
      if (!DemandedElts[0]) {
1519
6
        Worklist.Add(II);
1520
6
        return II->getArgOperand(0);
1521
6
      }
1522
335
1523
335
      // Only lower element is used for operand 1.
1524
335
      DemandedElts = 1;
1525
335
      simplifyAndSetOp(II, 1, DemandedElts, UndefElts2);
1526
335
1527
335
      // Lower element is undefined if both lower elements are undefined.
1528
335
      // Consider things like undef&0.  The result is known zero, not undef.
1529
335
      if (!UndefElts2[0])
1530
335
        UndefElts.clearBit(0);
1531
335
1532
335
      break;
1533
335
    }
1534
335
1535
335
    // Binary scalar-as-vector operations that work column-wise. The high
1536
335
    // elements come from operand 0 and the low element comes from operand 1.
1537
335
    case Intrinsic::x86_sse41_round_ss:
1538
25
    case Intrinsic::x86_sse41_round_sd: {
1539
25
      // Don't use the low element of operand 0.
1540
25
      APInt DemandedElts2 = DemandedElts;
1541
25
      DemandedElts2.clearBit(0);
1542
25
      simplifyAndSetOp(II, 0, DemandedElts2, UndefElts);
1543
25
1544
25
      // If lowest element of a scalar op isn't used then use Arg0.
1545
25
      if (!DemandedElts[0]) {
1546
2
        Worklist.Add(II);
1547
2
        return II->getArgOperand(0);
1548
2
      }
1549
23
1550
23
      // Only lower element is used for operand 1.
1551
23
      DemandedElts = 1;
1552
23
      simplifyAndSetOp(II, 1, DemandedElts, UndefElts2);
1553
23
1554
23
      // Take the high undef elements from operand 0 and take the lower element
1555
23
      // from operand 1.
1556
23
      UndefElts.clearBit(0);
1557
23
      UndefElts |= UndefElts2[0];
1558
23
      break;
1559
23
    }
1560
23
1561
23
    // Three input scalar-as-vector operations that work column-wise. The high
1562
23
    // elements come from operand 0 and the low element is a function of all
1563
23
    // three inputs.
1564
152
    case Intrinsic::x86_avx512_mask_add_ss_round:
1565
152
    case Intrinsic::x86_avx512_mask_div_ss_round:
1566
152
    case Intrinsic::x86_avx512_mask_mul_ss_round:
1567
152
    case Intrinsic::x86_avx512_mask_sub_ss_round:
1568
152
    case Intrinsic::x86_avx512_mask_max_ss_round:
1569
152
    case Intrinsic::x86_avx512_mask_min_ss_round:
1570
152
    case Intrinsic::x86_avx512_mask_add_sd_round:
1571
152
    case Intrinsic::x86_avx512_mask_div_sd_round:
1572
152
    case Intrinsic::x86_avx512_mask_mul_sd_round:
1573
152
    case Intrinsic::x86_avx512_mask_sub_sd_round:
1574
152
    case Intrinsic::x86_avx512_mask_max_sd_round:
1575
152
    case Intrinsic::x86_avx512_mask_min_sd_round:
1576
152
      simplifyAndSetOp(II, 0, DemandedElts, UndefElts);
1577
152
1578
152
      // If lowest element of a scalar op isn't used then use Arg0.
1579
152
      if (!DemandedElts[0]) {
1580
12
        Worklist.Add(II);
1581
12
        return II->getArgOperand(0);
1582
12
      }
1583
140
1584
140
      // Only lower element is used for operand 1 and 2.
1585
140
      DemandedElts = 1;
1586
140
      simplifyAndSetOp(II, 1, DemandedElts, UndefElts2);
1587
140
      simplifyAndSetOp(II, 2, DemandedElts, UndefElts3);
1588
140
1589
140
      // Lower element is undefined if all three lower elements are undefined.
1590
140
      // Consider things like undef&0.  The result is known zero, not undef.
1591
140
      if (!UndefElts2[0] || 
!UndefElts3[0]0
)
1592
140
        UndefElts.clearBit(0);
1593
140
1594
140
      break;
1595
140
1596
140
    case Intrinsic::x86_sse2_packssdw_128:
1597
93
    case Intrinsic::x86_sse2_packsswb_128:
1598
93
    case Intrinsic::x86_sse2_packuswb_128:
1599
93
    case Intrinsic::x86_sse41_packusdw:
1600
93
    case Intrinsic::x86_avx2_packssdw:
1601
93
    case Intrinsic::x86_avx2_packsswb:
1602
93
    case Intrinsic::x86_avx2_packusdw:
1603
93
    case Intrinsic::x86_avx2_packuswb:
1604
93
    case Intrinsic::x86_avx512_packssdw_512:
1605
93
    case Intrinsic::x86_avx512_packsswb_512:
1606
93
    case Intrinsic::x86_avx512_packusdw_512:
1607
93
    case Intrinsic::x86_avx512_packuswb_512: {
1608
93
      auto *Ty0 = II->getArgOperand(0)->getType();
1609
93
      unsigned InnerVWidth = Ty0->getVectorNumElements();
1610
93
      assert(VWidth == (InnerVWidth * 2) && "Unexpected input size");
1611
93
1612
93
      unsigned NumLanes = Ty0->getPrimitiveSizeInBits() / 128;
1613
93
      unsigned VWidthPerLane = VWidth / NumLanes;
1614
93
      unsigned InnerVWidthPerLane = InnerVWidth / NumLanes;
1615
93
1616
93
      // Per lane, pack the elements of the first input and then the second.
1617
93
      // e.g.
1618
93
      // v8i16 PACK(v4i32 X, v4i32 Y) - (X[0..3],Y[0..3])
1619
93
      // v32i8 PACK(v16i16 X, v16i16 Y) - (X[0..7],Y[0..7]),(X[8..15],Y[8..15])
1620
279
      for (int OpNum = 0; OpNum != 2; 
++OpNum186
) {
1621
186
        APInt OpDemandedElts(InnerVWidth, 0);
1622
612
        for (unsigned Lane = 0; Lane != NumLanes; 
++Lane426
) {
1623
426
          unsigned LaneIdx = Lane * VWidthPerLane;
1624
2.81k
          for (unsigned Elt = 0; Elt != InnerVWidthPerLane; 
++Elt2.38k
) {
1625
2.38k
            unsigned Idx = LaneIdx + Elt + InnerVWidthPerLane * OpNum;
1626
2.38k
            if (DemandedElts[Idx])
1627
2.01k
              OpDemandedElts.setBit((Lane * InnerVWidthPerLane) + Elt);
1628
2.38k
          }
1629
426
        }
1630
186
1631
186
        // Demand elements from the operand.
1632
186
        APInt OpUndefElts(InnerVWidth, 0);
1633
186
        simplifyAndSetOp(II, OpNum, OpDemandedElts, OpUndefElts);
1634
186
1635
186
        // Pack the operand's UNDEF elements, one lane at a time.
1636
186
        OpUndefElts = OpUndefElts.zext(VWidth);
1637
612
        for (unsigned Lane = 0; Lane != NumLanes; 
++Lane426
) {
1638
426
          APInt LaneElts = OpUndefElts.lshr(InnerVWidthPerLane * Lane);
1639
426
          LaneElts = LaneElts.getLoBits(InnerVWidthPerLane);
1640
426
          LaneElts <<= InnerVWidthPerLane * (2 * Lane + OpNum);
1641
426
          UndefElts |= LaneElts;
1642
426
        }
1643
186
      }
1644
93
      break;
1645
93
    }
1646
93
1647
93
    // PSHUFB
1648
152
    case Intrinsic::x86_ssse3_pshuf_b_128:
1649
152
    case Intrinsic::x86_avx2_pshuf_b:
1650
152
    case Intrinsic::x86_avx512_pshuf_b_512:
1651
152
    // PERMILVAR
1652
152
    case Intrinsic::x86_avx_vpermilvar_ps:
1653
152
    case Intrinsic::x86_avx_vpermilvar_ps_256:
1654
152
    case Intrinsic::x86_avx512_vpermilvar_ps_512:
1655
152
    case Intrinsic::x86_avx_vpermilvar_pd:
1656
152
    case Intrinsic::x86_avx_vpermilvar_pd_256:
1657
152
    case Intrinsic::x86_avx512_vpermilvar_pd_512:
1658
152
    // PERMV
1659
152
    case Intrinsic::x86_avx2_permd:
1660
152
    case Intrinsic::x86_avx2_permps: {
1661
152
      simplifyAndSetOp(II, 1, DemandedElts, UndefElts);
1662
152
      break;
1663
152
    }
1664
152
1665
152
    // SSE4A instructions leave the upper 64-bits of the 128-bit result
1666
152
    // in an undefined state.
1667
152
    case Intrinsic::x86_sse4a_extrq:
1668
79
    case Intrinsic::x86_sse4a_extrqi:
1669
79
    case Intrinsic::x86_sse4a_insertq:
1670
79
    case Intrinsic::x86_sse4a_insertqi:
1671
79
      UndefElts.setHighBits(VWidth / 2);
1672
79
      break;
1673
366
    case Intrinsic::amdgcn_buffer_load:
1674
366
    case Intrinsic::amdgcn_buffer_load_format:
1675
366
    case Intrinsic::amdgcn_raw_buffer_load:
1676
366
    case Intrinsic::amdgcn_raw_buffer_load_format:
1677
366
    case Intrinsic::amdgcn_struct_buffer_load:
1678
366
    case Intrinsic::amdgcn_struct_buffer_load_format:
1679
366
      return simplifyAMDGCNMemoryIntrinsicDemanded(II, DemandedElts);
1680
58.9k
    default: {
1681
58.9k
      if (getAMDGPUImageDMaskIntrinsic(II->getIntrinsicID()))
1682
175
        return simplifyAMDGCNMemoryIntrinsicDemanded(II, DemandedElts, 0);
1683
58.7k
1684
58.7k
      break;
1685
58.7k
    }
1686
60.1k
    } // switch on IntrinsicID
1687
60.1k
    break;
1688
60.1k
  } // case Call
1689
654k
  } // switch on Opcode
1690
654k
1691
654k
  // TODO: We bail completely on integer div/rem and shifts because they have
1692
654k
  // UB/poison potential, but that should be refined.
1693
654k
  BinaryOperator *BO;
1694
654k
  if (match(I, m_BinOp(BO)) && 
!BO->isIntDivRem()19.2k
&&
!BO->isShift()19.1k
) {
1695
18.6k
    simplifyAndSetOp(I, 0, DemandedElts, UndefElts);
1696
18.6k
    simplifyAndSetOp(I, 1, DemandedElts, UndefElts2);
1697
18.6k
1698
18.6k
    // Any change to an instruction with potential poison must clear those flags
1699
18.6k
    // because we can not guarantee those constraints now. Other analysis may
1700
18.6k
    // determine that it is safe to re-apply the flags.
1701
18.6k
    if (MadeChange)
1702
81
      BO->dropPoisonGeneratingFlags();
1703
18.6k
1704
18.6k
    // Output elements are undefined if both are undefined. Consider things
1705
18.6k
    // like undef & 0. The result is known zero, not undef.
1706
18.6k
    UndefElts &= UndefElts2;
1707
18.6k
  }
1708
654k
1709
654k
  // If we've proven all of the lanes undef, return an undef value.
1710
654k
  // TODO: Intersect w/demanded lanes
1711
654k
  if (UndefElts.isAllOnesValue())
1712
654k
    
return UndefValue::get(I->getType())29
;;
1713
654k
1714
654k
  return MadeChange ? 
I6.61k
:
nullptr647k
;
1715
654k
}