1 //===- InstCombineSimplifyDemanded.cpp ------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains logic for simplifying instructions based on information
11 // about how they are used.
13 //===----------------------------------------------------------------------===//
15 #include "InstCombine.h"
16 #include "llvm/IR/DataLayout.h"
17 #include "llvm/IR/IntrinsicInst.h"
18 #include "llvm/IR/PatternMatch.h"
21 using namespace llvm::PatternMatch
;
23 #define DEBUG_TYPE "instcombine"
25 /// ShrinkDemandedConstant - Check to see if the specified operand of the
26 /// specified instruction is a constant integer. If so, check to see if there
27 /// are any bits set in the constant that are not demanded. If so, shrink the
28 /// constant and return true.
29 static bool ShrinkDemandedConstant(Instruction
*I
, unsigned OpNo
,
31 assert(I
&& "No instruction?");
32 assert(OpNo
< I
->getNumOperands() && "Operand index too large");
34 // If the operand is not a constant integer, nothing to do.
35 ConstantInt
*OpC
= dyn_cast
<ConstantInt
>(I
->getOperand(OpNo
));
36 if (!OpC
) return false;
38 // If there are no bits set that aren't demanded, nothing to do.
39 Demanded
= Demanded
.zextOrTrunc(OpC
->getValue().getBitWidth());
40 if ((~Demanded
& OpC
->getValue()) == 0)
43 // This instruction is producing bits that are not demanded. Shrink the RHS.
44 Demanded
&= OpC
->getValue();
45 I
->setOperand(OpNo
, ConstantInt::get(OpC
->getType(), Demanded
));
47 // If either 'nsw' or 'nuw' is set and the constant is negative,
48 // removing *any* bits from the constant could make overflow occur.
49 // Remove 'nsw' and 'nuw' from the instruction in this case.
50 if (auto *OBO
= dyn_cast
<OverflowingBinaryOperator
>(I
)) {
51 assert(OBO
->getOpcode() == Instruction::Add
);
52 if (OBO
->hasNoSignedWrap() || OBO
->hasNoUnsignedWrap()) {
53 if (OpC
->getValue().isNegative()) {
54 cast
<BinaryOperator
>(OBO
)->setHasNoSignedWrap(false);
55 cast
<BinaryOperator
>(OBO
)->setHasNoUnsignedWrap(false);
65 /// SimplifyDemandedInstructionBits - Inst is an integer instruction that
66 /// SimplifyDemandedBits knows about. See if the instruction has any
67 /// properties that allow us to simplify its operands.
68 bool InstCombiner::SimplifyDemandedInstructionBits(Instruction
&Inst
) {
69 unsigned BitWidth
= Inst
.getType()->getScalarSizeInBits();
70 APInt
KnownZero(BitWidth
, 0), KnownOne(BitWidth
, 0);
71 APInt
DemandedMask(APInt::getAllOnesValue(BitWidth
));
73 Value
*V
= SimplifyDemandedUseBits(&Inst
, DemandedMask
,
74 KnownZero
, KnownOne
, 0, &Inst
);
76 if (V
== &Inst
) return true;
77 ReplaceInstUsesWith(Inst
, V
);
81 /// SimplifyDemandedBits - This form of SimplifyDemandedBits simplifies the
82 /// specified instruction operand if possible, updating it in place. It returns
83 /// true if it made any change and false otherwise.
84 bool InstCombiner::SimplifyDemandedBits(Use
&U
, APInt DemandedMask
,
85 APInt
&KnownZero
, APInt
&KnownOne
,
87 Value
*NewVal
= SimplifyDemandedUseBits(U
.get(), DemandedMask
,
88 KnownZero
, KnownOne
, Depth
,
89 dyn_cast
<Instruction
>(U
.getUser()));
90 if (!NewVal
) return false;
96 /// SimplifyDemandedUseBits - This function attempts to replace V with a simpler
97 /// value based on the demanded bits. When this function is called, it is known
98 /// that only the bits set in DemandedMask of the result of V are ever used
99 /// downstream. Consequently, depending on the mask and V, it may be possible
100 /// to replace V with a constant or one of its operands. In such cases, this
101 /// function does the replacement and returns true. In all other cases, it
102 /// returns false after analyzing the expression and setting KnownOne and known
103 /// to be one in the expression. KnownZero contains all the bits that are known
104 /// to be zero in the expression. These are provided to potentially allow the
105 /// caller (which might recursively be SimplifyDemandedBits itself) to simplify
106 /// the expression. KnownOne and KnownZero always follow the invariant that
107 /// KnownOne & KnownZero == 0. That is, a bit can't be both 1 and 0. Note that
108 /// the bits in KnownOne and KnownZero may only be accurate for those bits set
109 /// in DemandedMask. Note also that the bitwidth of V, DemandedMask, KnownZero
110 /// and KnownOne must all be the same.
112 /// This returns null if it did not change anything and it permits no
113 /// simplification. This returns V itself if it did some simplification of V's
114 /// operands based on the information about what bits are demanded. This returns
115 /// some other non-null value if it found out that V is equal to another value
116 /// in the context where the specified bits are demanded, but not for all users.
117 Value
*InstCombiner::SimplifyDemandedUseBits(Value
*V
, APInt DemandedMask
,
118 APInt
&KnownZero
, APInt
&KnownOne
,
121 assert(V
!= nullptr && "Null pointer of Value???");
122 assert(Depth
<= 6 && "Limit Search Depth");
123 uint32_t BitWidth
= DemandedMask
.getBitWidth();
124 Type
*VTy
= V
->getType();
125 assert((DL
|| !VTy
->isPointerTy()) &&
126 "SimplifyDemandedBits needs to know bit widths!");
127 assert((!DL
|| DL
->getTypeSizeInBits(VTy
->getScalarType()) == BitWidth
) &&
128 (!VTy
->isIntOrIntVectorTy() ||
129 VTy
->getScalarSizeInBits() == BitWidth
) &&
130 KnownZero
.getBitWidth() == BitWidth
&&
131 KnownOne
.getBitWidth() == BitWidth
&&
132 "Value *V, DemandedMask, KnownZero and KnownOne "
133 "must have same BitWidth");
134 if (ConstantInt
*CI
= dyn_cast
<ConstantInt
>(V
)) {
135 // We know all of the bits for a constant!
136 KnownOne
= CI
->getValue() & DemandedMask
;
137 KnownZero
= ~KnownOne
& DemandedMask
;
140 if (isa
<ConstantPointerNull
>(V
)) {
141 // We know all of the bits for a constant!
142 KnownOne
.clearAllBits();
143 KnownZero
= DemandedMask
;
147 KnownZero
.clearAllBits();
148 KnownOne
.clearAllBits();
149 if (DemandedMask
== 0) { // Not demanding any bits from V.
150 if (isa
<UndefValue
>(V
))
152 return UndefValue::get(VTy
);
155 if (Depth
== 6) // Limit search depth.
158 APInt
LHSKnownZero(BitWidth
, 0), LHSKnownOne(BitWidth
, 0);
159 APInt
RHSKnownZero(BitWidth
, 0), RHSKnownOne(BitWidth
, 0);
161 Instruction
*I
= dyn_cast
<Instruction
>(V
);
163 computeKnownBits(V
, KnownZero
, KnownOne
, Depth
, CxtI
);
164 return nullptr; // Only analyze instructions.
167 // If there are multiple uses of this value and we aren't at the root, then
168 // we can't do any simplifications of the operands, because DemandedMask
169 // only reflects the bits demanded by *one* of the users.
170 if (Depth
!= 0 && !I
->hasOneUse()) {
171 // Despite the fact that we can't simplify this instruction in all User's
172 // context, we can at least compute the knownzero/knownone bits, and we can
173 // do simplifications that apply to *just* the one user if we know that
174 // this instruction has a simpler value in that context.
175 if (I
->getOpcode() == Instruction::And
) {
176 // If either the LHS or the RHS are Zero, the result is zero.
177 computeKnownBits(I
->getOperand(1), RHSKnownZero
, RHSKnownOne
, Depth
+1,
179 computeKnownBits(I
->getOperand(0), LHSKnownZero
, LHSKnownOne
, Depth
+1,
182 // If all of the demanded bits are known 1 on one side, return the other.
183 // These bits cannot contribute to the result of the 'and' in this
185 if ((DemandedMask
& ~LHSKnownZero
& RHSKnownOne
) ==
186 (DemandedMask
& ~LHSKnownZero
))
187 return I
->getOperand(0);
188 if ((DemandedMask
& ~RHSKnownZero
& LHSKnownOne
) ==
189 (DemandedMask
& ~RHSKnownZero
))
190 return I
->getOperand(1);
192 // If all of the demanded bits in the inputs are known zeros, return zero.
193 if ((DemandedMask
& (RHSKnownZero
|LHSKnownZero
)) == DemandedMask
)
194 return Constant::getNullValue(VTy
);
196 } else if (I
->getOpcode() == Instruction::Or
) {
197 // We can simplify (X|Y) -> X or Y in the user's context if we know that
198 // only bits from X or Y are demanded.
200 // If either the LHS or the RHS are One, the result is One.
201 computeKnownBits(I
->getOperand(1), RHSKnownZero
, RHSKnownOne
, Depth
+1,
203 computeKnownBits(I
->getOperand(0), LHSKnownZero
, LHSKnownOne
, Depth
+1,
206 // If all of the demanded bits are known zero on one side, return the
207 // other. These bits cannot contribute to the result of the 'or' in this
209 if ((DemandedMask
& ~LHSKnownOne
& RHSKnownZero
) ==
210 (DemandedMask
& ~LHSKnownOne
))
211 return I
->getOperand(0);
212 if ((DemandedMask
& ~RHSKnownOne
& LHSKnownZero
) ==
213 (DemandedMask
& ~RHSKnownOne
))
214 return I
->getOperand(1);
216 // If all of the potentially set bits on one side are known to be set on
217 // the other side, just use the 'other' side.
218 if ((DemandedMask
& (~RHSKnownZero
) & LHSKnownOne
) ==
219 (DemandedMask
& (~RHSKnownZero
)))
220 return I
->getOperand(0);
221 if ((DemandedMask
& (~LHSKnownZero
) & RHSKnownOne
) ==
222 (DemandedMask
& (~LHSKnownZero
)))
223 return I
->getOperand(1);
224 } else if (I
->getOpcode() == Instruction::Xor
) {
225 // We can simplify (X^Y) -> X or Y in the user's context if we know that
226 // only bits from X or Y are demanded.
228 computeKnownBits(I
->getOperand(1), RHSKnownZero
, RHSKnownOne
, Depth
+1,
230 computeKnownBits(I
->getOperand(0), LHSKnownZero
, LHSKnownOne
, Depth
+1,
233 // If all of the demanded bits are known zero on one side, return the
235 if ((DemandedMask
& RHSKnownZero
) == DemandedMask
)
236 return I
->getOperand(0);
237 if ((DemandedMask
& LHSKnownZero
) == DemandedMask
)
238 return I
->getOperand(1);
241 // Compute the KnownZero/KnownOne bits to simplify things downstream.
242 computeKnownBits(I
, KnownZero
, KnownOne
, Depth
, CxtI
);
246 // If this is the root being simplified, allow it to have multiple uses,
247 // just set the DemandedMask to all bits so that we can try to simplify the
248 // operands. This allows visitTruncInst (for example) to simplify the
249 // operand of a trunc without duplicating all the logic below.
250 if (Depth
== 0 && !V
->hasOneUse())
251 DemandedMask
= APInt::getAllOnesValue(BitWidth
);
253 switch (I
->getOpcode()) {
255 computeKnownBits(I
, KnownZero
, KnownOne
, Depth
, CxtI
);
257 case Instruction::And
:
258 // If either the LHS or the RHS are Zero, the result is zero.
259 if (SimplifyDemandedBits(I
->getOperandUse(1), DemandedMask
,
260 RHSKnownZero
, RHSKnownOne
, Depth
+1) ||
261 SimplifyDemandedBits(I
->getOperandUse(0), DemandedMask
& ~RHSKnownZero
,
262 LHSKnownZero
, LHSKnownOne
, Depth
+1))
264 assert(!(RHSKnownZero
& RHSKnownOne
) && "Bits known to be one AND zero?");
265 assert(!(LHSKnownZero
& LHSKnownOne
) && "Bits known to be one AND zero?");
267 // If the client is only demanding bits that we know, return the known
269 if ((DemandedMask
& ((RHSKnownZero
| LHSKnownZero
)|
270 (RHSKnownOne
& LHSKnownOne
))) == DemandedMask
)
271 return Constant::getIntegerValue(VTy
, RHSKnownOne
& LHSKnownOne
);
273 // If all of the demanded bits are known 1 on one side, return the other.
274 // These bits cannot contribute to the result of the 'and'.
275 if ((DemandedMask
& ~LHSKnownZero
& RHSKnownOne
) ==
276 (DemandedMask
& ~LHSKnownZero
))
277 return I
->getOperand(0);
278 if ((DemandedMask
& ~RHSKnownZero
& LHSKnownOne
) ==
279 (DemandedMask
& ~RHSKnownZero
))
280 return I
->getOperand(1);
282 // If all of the demanded bits in the inputs are known zeros, return zero.
283 if ((DemandedMask
& (RHSKnownZero
|LHSKnownZero
)) == DemandedMask
)
284 return Constant::getNullValue(VTy
);
286 // If the RHS is a constant, see if we can simplify it.
287 if (ShrinkDemandedConstant(I
, 1, DemandedMask
& ~LHSKnownZero
))
290 // Output known-1 bits are only known if set in both the LHS & RHS.
291 KnownOne
= RHSKnownOne
& LHSKnownOne
;
292 // Output known-0 are known to be clear if zero in either the LHS | RHS.
293 KnownZero
= RHSKnownZero
| LHSKnownZero
;
295 case Instruction::Or
:
296 // If either the LHS or the RHS are One, the result is One.
297 if (SimplifyDemandedBits(I
->getOperandUse(1), DemandedMask
,
298 RHSKnownZero
, RHSKnownOne
, Depth
+1) ||
299 SimplifyDemandedBits(I
->getOperandUse(0), DemandedMask
& ~RHSKnownOne
,
300 LHSKnownZero
, LHSKnownOne
, Depth
+1))
302 assert(!(RHSKnownZero
& RHSKnownOne
) && "Bits known to be one AND zero?");
303 assert(!(LHSKnownZero
& LHSKnownOne
) && "Bits known to be one AND zero?");
305 // If the client is only demanding bits that we know, return the known
307 if ((DemandedMask
& ((RHSKnownZero
& LHSKnownZero
)|
308 (RHSKnownOne
| LHSKnownOne
))) == DemandedMask
)
309 return Constant::getIntegerValue(VTy
, RHSKnownOne
| LHSKnownOne
);
311 // If all of the demanded bits are known zero on one side, return the other.
312 // These bits cannot contribute to the result of the 'or'.
313 if ((DemandedMask
& ~LHSKnownOne
& RHSKnownZero
) ==
314 (DemandedMask
& ~LHSKnownOne
))
315 return I
->getOperand(0);
316 if ((DemandedMask
& ~RHSKnownOne
& LHSKnownZero
) ==
317 (DemandedMask
& ~RHSKnownOne
))
318 return I
->getOperand(1);
320 // If all of the potentially set bits on one side are known to be set on
321 // the other side, just use the 'other' side.
322 if ((DemandedMask
& (~RHSKnownZero
) & LHSKnownOne
) ==
323 (DemandedMask
& (~RHSKnownZero
)))
324 return I
->getOperand(0);
325 if ((DemandedMask
& (~LHSKnownZero
) & RHSKnownOne
) ==
326 (DemandedMask
& (~LHSKnownZero
)))
327 return I
->getOperand(1);
329 // If the RHS is a constant, see if we can simplify it.
330 if (ShrinkDemandedConstant(I
, 1, DemandedMask
))
333 // Output known-0 bits are only known if clear in both the LHS & RHS.
334 KnownZero
= RHSKnownZero
& LHSKnownZero
;
335 // Output known-1 are known to be set if set in either the LHS | RHS.
336 KnownOne
= RHSKnownOne
| LHSKnownOne
;
338 case Instruction::Xor
: {
339 if (SimplifyDemandedBits(I
->getOperandUse(1), DemandedMask
,
340 RHSKnownZero
, RHSKnownOne
, Depth
+1) ||
341 SimplifyDemandedBits(I
->getOperandUse(0), DemandedMask
,
342 LHSKnownZero
, LHSKnownOne
, Depth
+1))
344 assert(!(RHSKnownZero
& RHSKnownOne
) && "Bits known to be one AND zero?");
345 assert(!(LHSKnownZero
& LHSKnownOne
) && "Bits known to be one AND zero?");
347 // Output known-0 bits are known if clear or set in both the LHS & RHS.
348 APInt IKnownZero
= (RHSKnownZero
& LHSKnownZero
) |
349 (RHSKnownOne
& LHSKnownOne
);
350 // Output known-1 are known to be set if set in only one of the LHS, RHS.
351 APInt IKnownOne
= (RHSKnownZero
& LHSKnownOne
) |
352 (RHSKnownOne
& LHSKnownZero
);
354 // If the client is only demanding bits that we know, return the known
356 if ((DemandedMask
& (IKnownZero
|IKnownOne
)) == DemandedMask
)
357 return Constant::getIntegerValue(VTy
, IKnownOne
);
359 // If all of the demanded bits are known zero on one side, return the other.
360 // These bits cannot contribute to the result of the 'xor'.
361 if ((DemandedMask
& RHSKnownZero
) == DemandedMask
)
362 return I
->getOperand(0);
363 if ((DemandedMask
& LHSKnownZero
) == DemandedMask
)
364 return I
->getOperand(1);
366 // If all of the demanded bits are known to be zero on one side or the
367 // other, turn this into an *inclusive* or.
368 // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
369 if ((DemandedMask
& ~RHSKnownZero
& ~LHSKnownZero
) == 0) {
371 BinaryOperator::CreateOr(I
->getOperand(0), I
->getOperand(1),
373 return InsertNewInstWith(Or
, *I
);
376 // If all of the demanded bits on one side are known, and all of the set
377 // bits on that side are also known to be set on the other side, turn this
378 // into an AND, as we know the bits will be cleared.
379 // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
380 if ((DemandedMask
& (RHSKnownZero
|RHSKnownOne
)) == DemandedMask
) {
382 if ((RHSKnownOne
& LHSKnownOne
) == RHSKnownOne
) {
383 Constant
*AndC
= Constant::getIntegerValue(VTy
,
384 ~RHSKnownOne
& DemandedMask
);
385 Instruction
*And
= BinaryOperator::CreateAnd(I
->getOperand(0), AndC
);
386 return InsertNewInstWith(And
, *I
);
390 // If the RHS is a constant, see if we can simplify it.
391 // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1.
392 if (ShrinkDemandedConstant(I
, 1, DemandedMask
))
395 // If our LHS is an 'and' and if it has one use, and if any of the bits we
396 // are flipping are known to be set, then the xor is just resetting those
397 // bits to zero. We can just knock out bits from the 'and' and the 'xor',
398 // simplifying both of them.
399 if (Instruction
*LHSInst
= dyn_cast
<Instruction
>(I
->getOperand(0)))
400 if (LHSInst
->getOpcode() == Instruction::And
&& LHSInst
->hasOneUse() &&
401 isa
<ConstantInt
>(I
->getOperand(1)) &&
402 isa
<ConstantInt
>(LHSInst
->getOperand(1)) &&
403 (LHSKnownOne
& RHSKnownOne
& DemandedMask
) != 0) {
404 ConstantInt
*AndRHS
= cast
<ConstantInt
>(LHSInst
->getOperand(1));
405 ConstantInt
*XorRHS
= cast
<ConstantInt
>(I
->getOperand(1));
406 APInt NewMask
= ~(LHSKnownOne
& RHSKnownOne
& DemandedMask
);
409 ConstantInt::get(I
->getType(), NewMask
& AndRHS
->getValue());
410 Instruction
*NewAnd
= BinaryOperator::CreateAnd(I
->getOperand(0), AndC
);
411 InsertNewInstWith(NewAnd
, *I
);
414 ConstantInt::get(I
->getType(), NewMask
& XorRHS
->getValue());
415 Instruction
*NewXor
= BinaryOperator::CreateXor(NewAnd
, XorC
);
416 return InsertNewInstWith(NewXor
, *I
);
419 // Output known-0 bits are known if clear or set in both the LHS & RHS.
420 KnownZero
= (RHSKnownZero
& LHSKnownZero
) | (RHSKnownOne
& LHSKnownOne
);
421 // Output known-1 are known to be set if set in only one of the LHS, RHS.
422 KnownOne
= (RHSKnownZero
& LHSKnownOne
) | (RHSKnownOne
& LHSKnownZero
);
425 case Instruction::Select
:
426 if (SimplifyDemandedBits(I
->getOperandUse(2), DemandedMask
,
427 RHSKnownZero
, RHSKnownOne
, Depth
+1) ||
428 SimplifyDemandedBits(I
->getOperandUse(1), DemandedMask
,
429 LHSKnownZero
, LHSKnownOne
, Depth
+1))
431 assert(!(RHSKnownZero
& RHSKnownOne
) && "Bits known to be one AND zero?");
432 assert(!(LHSKnownZero
& LHSKnownOne
) && "Bits known to be one AND zero?");
434 // If the operands are constants, see if we can simplify them.
435 if (ShrinkDemandedConstant(I
, 1, DemandedMask
) ||
436 ShrinkDemandedConstant(I
, 2, DemandedMask
))
439 // Only known if known in both the LHS and RHS.
440 KnownOne
= RHSKnownOne
& LHSKnownOne
;
441 KnownZero
= RHSKnownZero
& LHSKnownZero
;
443 case Instruction::Trunc
: {
444 unsigned truncBf
= I
->getOperand(0)->getType()->getScalarSizeInBits();
445 DemandedMask
= DemandedMask
.zext(truncBf
);
446 KnownZero
= KnownZero
.zext(truncBf
);
447 KnownOne
= KnownOne
.zext(truncBf
);
448 if (SimplifyDemandedBits(I
->getOperandUse(0), DemandedMask
,
449 KnownZero
, KnownOne
, Depth
+1))
451 DemandedMask
= DemandedMask
.trunc(BitWidth
);
452 KnownZero
= KnownZero
.trunc(BitWidth
);
453 KnownOne
= KnownOne
.trunc(BitWidth
);
454 assert(!(KnownZero
& KnownOne
) && "Bits known to be one AND zero?");
457 case Instruction::BitCast
:
458 if (!I
->getOperand(0)->getType()->isIntOrIntVectorTy())
459 return nullptr; // vector->int or fp->int?
461 if (VectorType
*DstVTy
= dyn_cast
<VectorType
>(I
->getType())) {
462 if (VectorType
*SrcVTy
=
463 dyn_cast
<VectorType
>(I
->getOperand(0)->getType())) {
464 if (DstVTy
->getNumElements() != SrcVTy
->getNumElements())
465 // Don't touch a bitcast between vectors of different element counts.
468 // Don't touch a scalar-to-vector bitcast.
470 } else if (I
->getOperand(0)->getType()->isVectorTy())
471 // Don't touch a vector-to-scalar bitcast.
474 if (SimplifyDemandedBits(I
->getOperandUse(0), DemandedMask
,
475 KnownZero
, KnownOne
, Depth
+1))
477 assert(!(KnownZero
& KnownOne
) && "Bits known to be one AND zero?");
479 case Instruction::ZExt
: {
480 // Compute the bits in the result that are not present in the input.
481 unsigned SrcBitWidth
=I
->getOperand(0)->getType()->getScalarSizeInBits();
483 DemandedMask
= DemandedMask
.trunc(SrcBitWidth
);
484 KnownZero
= KnownZero
.trunc(SrcBitWidth
);
485 KnownOne
= KnownOne
.trunc(SrcBitWidth
);
486 if (SimplifyDemandedBits(I
->getOperandUse(0), DemandedMask
,
487 KnownZero
, KnownOne
, Depth
+1))
489 DemandedMask
= DemandedMask
.zext(BitWidth
);
490 KnownZero
= KnownZero
.zext(BitWidth
);
491 KnownOne
= KnownOne
.zext(BitWidth
);
492 assert(!(KnownZero
& KnownOne
) && "Bits known to be one AND zero?");
493 // The top bits are known to be zero.
494 KnownZero
|= APInt::getHighBitsSet(BitWidth
, BitWidth
- SrcBitWidth
);
497 case Instruction::SExt
: {
498 // Compute the bits in the result that are not present in the input.
499 unsigned SrcBitWidth
=I
->getOperand(0)->getType()->getScalarSizeInBits();
501 APInt InputDemandedBits
= DemandedMask
&
502 APInt::getLowBitsSet(BitWidth
, SrcBitWidth
);
504 APInt
NewBits(APInt::getHighBitsSet(BitWidth
, BitWidth
- SrcBitWidth
));
505 // If any of the sign extended bits are demanded, we know that the sign
507 if ((NewBits
& DemandedMask
) != 0)
508 InputDemandedBits
.setBit(SrcBitWidth
-1);
510 InputDemandedBits
= InputDemandedBits
.trunc(SrcBitWidth
);
511 KnownZero
= KnownZero
.trunc(SrcBitWidth
);
512 KnownOne
= KnownOne
.trunc(SrcBitWidth
);
513 if (SimplifyDemandedBits(I
->getOperandUse(0), InputDemandedBits
,
514 KnownZero
, KnownOne
, Depth
+1))
516 InputDemandedBits
= InputDemandedBits
.zext(BitWidth
);
517 KnownZero
= KnownZero
.zext(BitWidth
);
518 KnownOne
= KnownOne
.zext(BitWidth
);
519 assert(!(KnownZero
& KnownOne
) && "Bits known to be one AND zero?");
521 // If the sign bit of the input is known set or clear, then we know the
522 // top bits of the result.
524 // If the input sign bit is known zero, or if the NewBits are not demanded
525 // convert this into a zero extension.
526 if (KnownZero
[SrcBitWidth
-1] || (NewBits
& ~DemandedMask
) == NewBits
) {
527 // Convert to ZExt cast
528 CastInst
*NewCast
= new ZExtInst(I
->getOperand(0), VTy
, I
->getName());
529 return InsertNewInstWith(NewCast
, *I
);
530 } else if (KnownOne
[SrcBitWidth
-1]) { // Input sign bit known set
535 case Instruction::Add
: {
536 // Figure out what the input bits are. If the top bits of the and result
537 // are not demanded, then the add doesn't demand them from its input
539 unsigned NLZ
= DemandedMask
.countLeadingZeros();
541 // If there is a constant on the RHS, there are a variety of xformations
543 if (ConstantInt
*RHS
= dyn_cast
<ConstantInt
>(I
->getOperand(1))) {
544 // If null, this should be simplified elsewhere. Some of the xforms here
545 // won't work if the RHS is zero.
549 // If the top bit of the output is demanded, demand everything from the
550 // input. Otherwise, we demand all the input bits except NLZ top bits.
551 APInt
InDemandedBits(APInt::getLowBitsSet(BitWidth
, BitWidth
- NLZ
));
553 // Find information about known zero/one bits in the input.
554 if (SimplifyDemandedBits(I
->getOperandUse(0), InDemandedBits
,
555 LHSKnownZero
, LHSKnownOne
, Depth
+1))
558 // If the RHS of the add has bits set that can't affect the input, reduce
560 if (ShrinkDemandedConstant(I
, 1, InDemandedBits
))
563 // Avoid excess work.
564 if (LHSKnownZero
== 0 && LHSKnownOne
== 0)
567 // Turn it into OR if input bits are zero.
568 if ((LHSKnownZero
& RHS
->getValue()) == RHS
->getValue()) {
570 BinaryOperator::CreateOr(I
->getOperand(0), I
->getOperand(1),
572 return InsertNewInstWith(Or
, *I
);
575 // We can say something about the output known-zero and known-one bits,
576 // depending on potential carries from the input constant and the
577 // unknowns. For example if the LHS is known to have at most the 0x0F0F0
578 // bits set and the RHS constant is 0x01001, then we know we have a known
579 // one mask of 0x00001 and a known zero mask of 0xE0F0E.
581 // To compute this, we first compute the potential carry bits. These are
582 // the bits which may be modified. I'm not aware of a better way to do
584 const APInt
&RHSVal
= RHS
->getValue();
585 APInt
CarryBits((~LHSKnownZero
+ RHSVal
) ^ (~LHSKnownZero
^ RHSVal
));
587 // Now that we know which bits have carries, compute the known-1/0 sets.
589 // Bits are known one if they are known zero in one operand and one in the
590 // other, and there is no input carry.
591 KnownOne
= ((LHSKnownZero
& RHSVal
) |
592 (LHSKnownOne
& ~RHSVal
)) & ~CarryBits
;
594 // Bits are known zero if they are known zero in both operands and there
595 // is no input carry.
596 KnownZero
= LHSKnownZero
& ~RHSVal
& ~CarryBits
;
598 // If the high-bits of this ADD are not demanded, then it does not demand
599 // the high bits of its LHS or RHS.
600 if (DemandedMask
[BitWidth
-1] == 0) {
601 // Right fill the mask of bits for this ADD to demand the most
602 // significant bit and all those below it.
603 APInt
DemandedFromOps(APInt::getLowBitsSet(BitWidth
, BitWidth
-NLZ
));
604 if (SimplifyDemandedBits(I
->getOperandUse(0), DemandedFromOps
,
605 LHSKnownZero
, LHSKnownOne
, Depth
+1) ||
606 SimplifyDemandedBits(I
->getOperandUse(1), DemandedFromOps
,
607 LHSKnownZero
, LHSKnownOne
, Depth
+1))
613 case Instruction::Sub
:
614 // If the high-bits of this SUB are not demanded, then it does not demand
615 // the high bits of its LHS or RHS.
616 if (DemandedMask
[BitWidth
-1] == 0) {
617 // Right fill the mask of bits for this SUB to demand the most
618 // significant bit and all those below it.
619 uint32_t NLZ
= DemandedMask
.countLeadingZeros();
620 APInt
DemandedFromOps(APInt::getLowBitsSet(BitWidth
, BitWidth
-NLZ
));
621 if (SimplifyDemandedBits(I
->getOperandUse(0), DemandedFromOps
,
622 LHSKnownZero
, LHSKnownOne
, Depth
+1) ||
623 SimplifyDemandedBits(I
->getOperandUse(1), DemandedFromOps
,
624 LHSKnownZero
, LHSKnownOne
, Depth
+1))
628 // Otherwise just hand the sub off to computeKnownBits to fill in
629 // the known zeros and ones.
630 computeKnownBits(V
, KnownZero
, KnownOne
, Depth
, CxtI
);
632 // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known
634 if (ConstantInt
*C0
= dyn_cast
<ConstantInt
>(I
->getOperand(0))) {
635 APInt I0
= C0
->getValue();
636 if ((I0
+ 1).isPowerOf2() && (I0
| KnownZero
).isAllOnesValue()) {
637 Instruction
*Xor
= BinaryOperator::CreateXor(I
->getOperand(1), C0
);
638 return InsertNewInstWith(Xor
, *I
);
642 case Instruction::Shl
:
643 if (ConstantInt
*SA
= dyn_cast
<ConstantInt
>(I
->getOperand(1))) {
645 Value
*VarX
; ConstantInt
*C1
;
646 if (match(I
->getOperand(0), m_Shr(m_Value(VarX
), m_ConstantInt(C1
)))) {
647 Instruction
*Shr
= cast
<Instruction
>(I
->getOperand(0));
648 Value
*R
= SimplifyShrShlDemandedBits(Shr
, I
, DemandedMask
,
649 KnownZero
, KnownOne
);
655 uint64_t ShiftAmt
= SA
->getLimitedValue(BitWidth
-1);
656 APInt
DemandedMaskIn(DemandedMask
.lshr(ShiftAmt
));
658 // If the shift is NUW/NSW, then it does demand the high bits.
659 ShlOperator
*IOp
= cast
<ShlOperator
>(I
);
660 if (IOp
->hasNoSignedWrap())
661 DemandedMaskIn
|= APInt::getHighBitsSet(BitWidth
, ShiftAmt
+1);
662 else if (IOp
->hasNoUnsignedWrap())
663 DemandedMaskIn
|= APInt::getHighBitsSet(BitWidth
, ShiftAmt
);
665 if (SimplifyDemandedBits(I
->getOperandUse(0), DemandedMaskIn
,
666 KnownZero
, KnownOne
, Depth
+1))
668 assert(!(KnownZero
& KnownOne
) && "Bits known to be one AND zero?");
669 KnownZero
<<= ShiftAmt
;
670 KnownOne
<<= ShiftAmt
;
671 // low bits known zero.
673 KnownZero
|= APInt::getLowBitsSet(BitWidth
, ShiftAmt
);
676 case Instruction::LShr
:
677 // For a logical shift right
678 if (ConstantInt
*SA
= dyn_cast
<ConstantInt
>(I
->getOperand(1))) {
679 uint64_t ShiftAmt
= SA
->getLimitedValue(BitWidth
-1);
681 // Unsigned shift right.
682 APInt
DemandedMaskIn(DemandedMask
.shl(ShiftAmt
));
684 // If the shift is exact, then it does demand the low bits (and knows that
686 if (cast
<LShrOperator
>(I
)->isExact())
687 DemandedMaskIn
|= APInt::getLowBitsSet(BitWidth
, ShiftAmt
);
689 if (SimplifyDemandedBits(I
->getOperandUse(0), DemandedMaskIn
,
690 KnownZero
, KnownOne
, Depth
+1))
692 assert(!(KnownZero
& KnownOne
) && "Bits known to be one AND zero?");
693 KnownZero
= APIntOps::lshr(KnownZero
, ShiftAmt
);
694 KnownOne
= APIntOps::lshr(KnownOne
, ShiftAmt
);
696 // Compute the new bits that are at the top now.
697 APInt
HighBits(APInt::getHighBitsSet(BitWidth
, ShiftAmt
));
698 KnownZero
|= HighBits
; // high bits known zero.
702 case Instruction::AShr
:
703 // If this is an arithmetic shift right and only the low-bit is set, we can
704 // always convert this into a logical shr, even if the shift amount is
705 // variable. The low bit of the shift cannot be an input sign bit unless
706 // the shift amount is >= the size of the datatype, which is undefined.
707 if (DemandedMask
== 1) {
708 // Perform the logical shift right.
709 Instruction
*NewVal
= BinaryOperator::CreateLShr(
710 I
->getOperand(0), I
->getOperand(1), I
->getName());
711 return InsertNewInstWith(NewVal
, *I
);
714 // If the sign bit is the only bit demanded by this ashr, then there is no
715 // need to do it, the shift doesn't change the high bit.
716 if (DemandedMask
.isSignBit())
717 return I
->getOperand(0);
719 if (ConstantInt
*SA
= dyn_cast
<ConstantInt
>(I
->getOperand(1))) {
720 uint32_t ShiftAmt
= SA
->getLimitedValue(BitWidth
-1);
722 // Signed shift right.
723 APInt
DemandedMaskIn(DemandedMask
.shl(ShiftAmt
));
724 // If any of the "high bits" are demanded, we should set the sign bit as
726 if (DemandedMask
.countLeadingZeros() <= ShiftAmt
)
727 DemandedMaskIn
.setBit(BitWidth
-1);
729 // If the shift is exact, then it does demand the low bits (and knows that
731 if (cast
<AShrOperator
>(I
)->isExact())
732 DemandedMaskIn
|= APInt::getLowBitsSet(BitWidth
, ShiftAmt
);
734 if (SimplifyDemandedBits(I
->getOperandUse(0), DemandedMaskIn
,
735 KnownZero
, KnownOne
, Depth
+1))
737 assert(!(KnownZero
& KnownOne
) && "Bits known to be one AND zero?");
738 // Compute the new bits that are at the top now.
739 APInt
HighBits(APInt::getHighBitsSet(BitWidth
, ShiftAmt
));
740 KnownZero
= APIntOps::lshr(KnownZero
, ShiftAmt
);
741 KnownOne
= APIntOps::lshr(KnownOne
, ShiftAmt
);
743 // Handle the sign bits.
744 APInt
SignBit(APInt::getSignBit(BitWidth
));
745 // Adjust to where it is now in the mask.
746 SignBit
= APIntOps::lshr(SignBit
, ShiftAmt
);
748 // If the input sign bit is known to be zero, or if none of the top bits
749 // are demanded, turn this into an unsigned shift right.
750 if (BitWidth
<= ShiftAmt
|| KnownZero
[BitWidth
-ShiftAmt
-1] ||
751 (HighBits
& ~DemandedMask
) == HighBits
) {
752 // Perform the logical shift right.
753 BinaryOperator
*NewVal
= BinaryOperator::CreateLShr(I
->getOperand(0),
755 NewVal
->setIsExact(cast
<BinaryOperator
>(I
)->isExact());
756 return InsertNewInstWith(NewVal
, *I
);
757 } else if ((KnownOne
& SignBit
) != 0) { // New bits are known one.
758 KnownOne
|= HighBits
;
762 case Instruction::SRem
:
763 if (ConstantInt
*Rem
= dyn_cast
<ConstantInt
>(I
->getOperand(1))) {
764 // X % -1 demands all the bits because we don't want to introduce
765 // INT_MIN % -1 (== undef) by accident.
766 if (Rem
->isAllOnesValue())
768 APInt RA
= Rem
->getValue().abs();
769 if (RA
.isPowerOf2()) {
770 if (DemandedMask
.ult(RA
)) // srem won't affect demanded bits
771 return I
->getOperand(0);
773 APInt LowBits
= RA
- 1;
774 APInt Mask2
= LowBits
| APInt::getSignBit(BitWidth
);
775 if (SimplifyDemandedBits(I
->getOperandUse(0), Mask2
,
776 LHSKnownZero
, LHSKnownOne
, Depth
+1))
779 // The low bits of LHS are unchanged by the srem.
780 KnownZero
= LHSKnownZero
& LowBits
;
781 KnownOne
= LHSKnownOne
& LowBits
;
783 // If LHS is non-negative or has all low bits zero, then the upper bits
785 if (LHSKnownZero
[BitWidth
-1] || ((LHSKnownZero
& LowBits
) == LowBits
))
786 KnownZero
|= ~LowBits
;
788 // If LHS is negative and not all low bits are zero, then the upper bits
790 if (LHSKnownOne
[BitWidth
-1] && ((LHSKnownOne
& LowBits
) != 0))
791 KnownOne
|= ~LowBits
;
793 assert(!(KnownZero
& KnownOne
) && "Bits known to be one AND zero?");
797 // The sign bit is the LHS's sign bit, except when the result of the
798 // remainder is zero.
799 if (DemandedMask
.isNegative() && KnownZero
.isNonNegative()) {
800 APInt
LHSKnownZero(BitWidth
, 0), LHSKnownOne(BitWidth
, 0);
801 computeKnownBits(I
->getOperand(0), LHSKnownZero
, LHSKnownOne
, Depth
+1,
803 // If it's known zero, our sign bit is also zero.
804 if (LHSKnownZero
.isNegative())
805 KnownZero
.setBit(KnownZero
.getBitWidth() - 1);
808 case Instruction::URem
: {
809 APInt
KnownZero2(BitWidth
, 0), KnownOne2(BitWidth
, 0);
810 APInt AllOnes
= APInt::getAllOnesValue(BitWidth
);
811 if (SimplifyDemandedBits(I
->getOperandUse(0), AllOnes
,
812 KnownZero2
, KnownOne2
, Depth
+1) ||
813 SimplifyDemandedBits(I
->getOperandUse(1), AllOnes
,
814 KnownZero2
, KnownOne2
, Depth
+1))
817 unsigned Leaders
= KnownZero2
.countLeadingOnes();
818 Leaders
= std::max(Leaders
,
819 KnownZero2
.countLeadingOnes());
820 KnownZero
= APInt::getHighBitsSet(BitWidth
, Leaders
) & DemandedMask
;
823 case Instruction::Call
:
824 if (IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(I
)) {
825 switch (II
->getIntrinsicID()) {
827 case Intrinsic::bswap
: {
828 // If the only bits demanded come from one byte of the bswap result,
829 // just shift the input byte into position to eliminate the bswap.
830 unsigned NLZ
= DemandedMask
.countLeadingZeros();
831 unsigned NTZ
= DemandedMask
.countTrailingZeros();
833 // Round NTZ down to the next byte. If we have 11 trailing zeros, then
834 // we need all the bits down to bit 8. Likewise, round NLZ. If we
835 // have 14 leading zeros, round to 8.
838 // If we need exactly one byte, we can do this transformation.
839 if (BitWidth
-NLZ
-NTZ
== 8) {
840 unsigned ResultBit
= NTZ
;
841 unsigned InputBit
= BitWidth
-NTZ
-8;
843 // Replace this with either a left or right shift to get the byte into
846 if (InputBit
> ResultBit
)
847 NewVal
= BinaryOperator::CreateLShr(II
->getArgOperand(0),
848 ConstantInt::get(I
->getType(), InputBit
-ResultBit
));
850 NewVal
= BinaryOperator::CreateShl(II
->getArgOperand(0),
851 ConstantInt::get(I
->getType(), ResultBit
-InputBit
));
853 return InsertNewInstWith(NewVal
, *I
);
856 // TODO: Could compute known zero/one bits based on the input.
859 case Intrinsic::x86_sse42_crc32_64_64
:
860 KnownZero
= APInt::getHighBitsSet(64, 32);
864 computeKnownBits(V
, KnownZero
, KnownOne
, Depth
, CxtI
);
868 // If the client is only demanding bits that we know, return the known
870 if ((DemandedMask
& (KnownZero
|KnownOne
)) == DemandedMask
)
871 return Constant::getIntegerValue(VTy
, KnownOne
);
875 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify
876 /// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into
877 /// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign
880 /// Suppose E1 and E2 are generally different in bits S={bm, bm+1,
881 /// ..., bn}, without considering the specific value X is holding.
882 /// This transformation is legal iff one of following conditions is hold:
883 /// 1) All the bit in S are 0, in this case E1 == E2.
884 /// 2) We don't care those bits in S, per the input DemandedMask.
885 /// 3) Combination of 1) and 2). Some bits in S are 0, and we don't care the
888 /// Currently we only test condition 2).
890 /// As with SimplifyDemandedUseBits, it returns NULL if the simplification was
892 Value
*InstCombiner::SimplifyShrShlDemandedBits(Instruction
*Shr
,
893 Instruction
*Shl
, APInt DemandedMask
, APInt
&KnownZero
, APInt
&KnownOne
) {
895 const APInt
&ShlOp1
= cast
<ConstantInt
>(Shl
->getOperand(1))->getValue();
896 const APInt
&ShrOp1
= cast
<ConstantInt
>(Shr
->getOperand(1))->getValue();
897 if (!ShlOp1
|| !ShrOp1
)
898 return nullptr; // Noop.
900 Value
*VarX
= Shr
->getOperand(0);
901 Type
*Ty
= VarX
->getType();
902 unsigned BitWidth
= Ty
->getIntegerBitWidth();
903 if (ShlOp1
.uge(BitWidth
) || ShrOp1
.uge(BitWidth
))
904 return nullptr; // Undef.
906 unsigned ShlAmt
= ShlOp1
.getZExtValue();
907 unsigned ShrAmt
= ShrOp1
.getZExtValue();
909 KnownOne
.clearAllBits();
910 KnownZero
= APInt::getBitsSet(KnownZero
.getBitWidth(), 0, ShlAmt
-1);
911 KnownZero
&= DemandedMask
;
913 APInt
BitMask1(APInt::getAllOnesValue(BitWidth
));
914 APInt
BitMask2(APInt::getAllOnesValue(BitWidth
));
916 bool isLshr
= (Shr
->getOpcode() == Instruction::LShr
);
917 BitMask1
= isLshr
? (BitMask1
.lshr(ShrAmt
) << ShlAmt
) :
918 (BitMask1
.ashr(ShrAmt
) << ShlAmt
);
920 if (ShrAmt
<= ShlAmt
) {
921 BitMask2
<<= (ShlAmt
- ShrAmt
);
923 BitMask2
= isLshr
? BitMask2
.lshr(ShrAmt
- ShlAmt
):
924 BitMask2
.ashr(ShrAmt
- ShlAmt
);
927 // Check if condition-2 (see the comment to this function) is satified.
928 if ((BitMask1
& DemandedMask
) == (BitMask2
& DemandedMask
)) {
929 if (ShrAmt
== ShlAmt
)
932 if (!Shr
->hasOneUse())
936 if (ShrAmt
< ShlAmt
) {
937 Constant
*Amt
= ConstantInt::get(VarX
->getType(), ShlAmt
- ShrAmt
);
938 New
= BinaryOperator::CreateShl(VarX
, Amt
);
939 BinaryOperator
*Orig
= cast
<BinaryOperator
>(Shl
);
940 New
->setHasNoSignedWrap(Orig
->hasNoSignedWrap());
941 New
->setHasNoUnsignedWrap(Orig
->hasNoUnsignedWrap());
943 Constant
*Amt
= ConstantInt::get(VarX
->getType(), ShrAmt
- ShlAmt
);
944 New
= isLshr
? BinaryOperator::CreateLShr(VarX
, Amt
) :
945 BinaryOperator::CreateAShr(VarX
, Amt
);
946 if (cast
<BinaryOperator
>(Shr
)->isExact())
947 New
->setIsExact(true);
950 return InsertNewInstWith(New
, *Shl
);
956 /// SimplifyDemandedVectorElts - The specified value produces a vector with
957 /// any number of elements. DemandedElts contains the set of elements that are
958 /// actually used by the caller. This method analyzes which elements of the
959 /// operand are undef and returns that information in UndefElts.
961 /// If the information about demanded elements can be used to simplify the
962 /// operation, the operation is simplified, then the resultant value is
963 /// returned. This returns null if no change was made.
964 Value
*InstCombiner::SimplifyDemandedVectorElts(Value
*V
, APInt DemandedElts
,
967 unsigned VWidth
= cast
<VectorType
>(V
->getType())->getNumElements();
968 APInt
EltMask(APInt::getAllOnesValue(VWidth
));
969 assert((DemandedElts
& ~EltMask
) == 0 && "Invalid DemandedElts!");
971 if (isa
<UndefValue
>(V
)) {
972 // If the entire vector is undefined, just return this info.
977 if (DemandedElts
== 0) { // If nothing is demanded, provide undef.
979 return UndefValue::get(V
->getType());
984 // Handle ConstantAggregateZero, ConstantVector, ConstantDataSequential.
985 if (Constant
*C
= dyn_cast
<Constant
>(V
)) {
986 // Check if this is identity. If so, return 0 since we are not simplifying
988 if (DemandedElts
.isAllOnesValue())
991 Type
*EltTy
= cast
<VectorType
>(V
->getType())->getElementType();
992 Constant
*Undef
= UndefValue::get(EltTy
);
994 SmallVector
<Constant
*, 16> Elts
;
995 for (unsigned i
= 0; i
!= VWidth
; ++i
) {
996 if (!DemandedElts
[i
]) { // If not demanded, set to undef.
997 Elts
.push_back(Undef
);
1002 Constant
*Elt
= C
->getAggregateElement(i
);
1003 if (!Elt
) return nullptr;
1005 if (isa
<UndefValue
>(Elt
)) { // Already undef.
1006 Elts
.push_back(Undef
);
1007 UndefElts
.setBit(i
);
1008 } else { // Otherwise, defined.
1009 Elts
.push_back(Elt
);
1013 // If we changed the constant, return it.
1014 Constant
*NewCV
= ConstantVector::get(Elts
);
1015 return NewCV
!= C
? NewCV
: nullptr;
1018 // Limit search depth.
1022 // If multiple users are using the root value, proceed with
1023 // simplification conservatively assuming that all elements
1025 if (!V
->hasOneUse()) {
1026 // Quit if we find multiple users of a non-root value though.
1027 // They'll be handled when it's their turn to be visited by
1028 // the main instcombine process.
1030 // TODO: Just compute the UndefElts information recursively.
1033 // Conservatively assume that all elements are needed.
1034 DemandedElts
= EltMask
;
1037 Instruction
*I
= dyn_cast
<Instruction
>(V
);
1038 if (!I
) return nullptr; // Only analyze instructions.
1040 bool MadeChange
= false;
1041 APInt
UndefElts2(VWidth
, 0);
1043 switch (I
->getOpcode()) {
1046 case Instruction::InsertElement
: {
1047 // If this is a variable index, we don't know which element it overwrites.
1048 // demand exactly the same input as we produce.
1049 ConstantInt
*Idx
= dyn_cast
<ConstantInt
>(I
->getOperand(2));
1051 // Note that we can't propagate undef elt info, because we don't know
1052 // which elt is getting updated.
1053 TmpV
= SimplifyDemandedVectorElts(I
->getOperand(0), DemandedElts
,
1054 UndefElts2
, Depth
+1);
1055 if (TmpV
) { I
->setOperand(0, TmpV
); MadeChange
= true; }
1059 // If this is inserting an element that isn't demanded, remove this
1061 unsigned IdxNo
= Idx
->getZExtValue();
1062 if (IdxNo
>= VWidth
|| !DemandedElts
[IdxNo
]) {
1064 return I
->getOperand(0);
1067 // Otherwise, the element inserted overwrites whatever was there, so the
1068 // input demanded set is simpler than the output set.
1069 APInt DemandedElts2
= DemandedElts
;
1070 DemandedElts2
.clearBit(IdxNo
);
1071 TmpV
= SimplifyDemandedVectorElts(I
->getOperand(0), DemandedElts2
,
1072 UndefElts
, Depth
+1);
1073 if (TmpV
) { I
->setOperand(0, TmpV
); MadeChange
= true; }
1075 // The inserted element is defined.
1076 UndefElts
.clearBit(IdxNo
);
1079 case Instruction::ShuffleVector
: {
1080 ShuffleVectorInst
*Shuffle
= cast
<ShuffleVectorInst
>(I
);
1081 uint64_t LHSVWidth
=
1082 cast
<VectorType
>(Shuffle
->getOperand(0)->getType())->getNumElements();
1083 APInt
LeftDemanded(LHSVWidth
, 0), RightDemanded(LHSVWidth
, 0);
1084 for (unsigned i
= 0; i
< VWidth
; i
++) {
1085 if (DemandedElts
[i
]) {
1086 unsigned MaskVal
= Shuffle
->getMaskValue(i
);
1087 if (MaskVal
!= -1u) {
1088 assert(MaskVal
< LHSVWidth
* 2 &&
1089 "shufflevector mask index out of range!");
1090 if (MaskVal
< LHSVWidth
)
1091 LeftDemanded
.setBit(MaskVal
);
1093 RightDemanded
.setBit(MaskVal
- LHSVWidth
);
1098 APInt
UndefElts4(LHSVWidth
, 0);
1099 TmpV
= SimplifyDemandedVectorElts(I
->getOperand(0), LeftDemanded
,
1100 UndefElts4
, Depth
+1);
1101 if (TmpV
) { I
->setOperand(0, TmpV
); MadeChange
= true; }
1103 APInt
UndefElts3(LHSVWidth
, 0);
1104 TmpV
= SimplifyDemandedVectorElts(I
->getOperand(1), RightDemanded
,
1105 UndefElts3
, Depth
+1);
1106 if (TmpV
) { I
->setOperand(1, TmpV
); MadeChange
= true; }
1108 bool NewUndefElts
= false;
1109 for (unsigned i
= 0; i
< VWidth
; i
++) {
1110 unsigned MaskVal
= Shuffle
->getMaskValue(i
);
1111 if (MaskVal
== -1u) {
1112 UndefElts
.setBit(i
);
1113 } else if (!DemandedElts
[i
]) {
1114 NewUndefElts
= true;
1115 UndefElts
.setBit(i
);
1116 } else if (MaskVal
< LHSVWidth
) {
1117 if (UndefElts4
[MaskVal
]) {
1118 NewUndefElts
= true;
1119 UndefElts
.setBit(i
);
1122 if (UndefElts3
[MaskVal
- LHSVWidth
]) {
1123 NewUndefElts
= true;
1124 UndefElts
.setBit(i
);
1130 // Add additional discovered undefs.
1131 SmallVector
<Constant
*, 16> Elts
;
1132 for (unsigned i
= 0; i
< VWidth
; ++i
) {
1134 Elts
.push_back(UndefValue::get(Type::getInt32Ty(I
->getContext())));
1136 Elts
.push_back(ConstantInt::get(Type::getInt32Ty(I
->getContext()),
1137 Shuffle
->getMaskValue(i
)));
1139 I
->setOperand(2, ConstantVector::get(Elts
));
1144 case Instruction::Select
: {
1145 APInt
LeftDemanded(DemandedElts
), RightDemanded(DemandedElts
);
1146 if (ConstantVector
* CV
= dyn_cast
<ConstantVector
>(I
->getOperand(0))) {
1147 for (unsigned i
= 0; i
< VWidth
; i
++) {
1148 if (CV
->getAggregateElement(i
)->isNullValue())
1149 LeftDemanded
.clearBit(i
);
1151 RightDemanded
.clearBit(i
);
1155 TmpV
= SimplifyDemandedVectorElts(I
->getOperand(1), LeftDemanded
,
1156 UndefElts
, Depth
+1);
1157 if (TmpV
) { I
->setOperand(1, TmpV
); MadeChange
= true; }
1159 TmpV
= SimplifyDemandedVectorElts(I
->getOperand(2), RightDemanded
,
1160 UndefElts2
, Depth
+1);
1161 if (TmpV
) { I
->setOperand(2, TmpV
); MadeChange
= true; }
1163 // Output elements are undefined if both are undefined.
1164 UndefElts
&= UndefElts2
;
1167 case Instruction::BitCast
: {
1168 // Vector->vector casts only.
1169 VectorType
*VTy
= dyn_cast
<VectorType
>(I
->getOperand(0)->getType());
1171 unsigned InVWidth
= VTy
->getNumElements();
1172 APInt
InputDemandedElts(InVWidth
, 0);
1175 if (VWidth
== InVWidth
) {
1176 // If we are converting from <4 x i32> -> <4 x f32>, we demand the same
1177 // elements as are demanded of us.
1179 InputDemandedElts
= DemandedElts
;
1180 } else if (VWidth
> InVWidth
) {
1184 // If there are more elements in the result than there are in the source,
1185 // then an input element is live if any of the corresponding output
1186 // elements are live.
1187 Ratio
= VWidth
/InVWidth
;
1188 for (unsigned OutIdx
= 0; OutIdx
!= VWidth
; ++OutIdx
) {
1189 if (DemandedElts
[OutIdx
])
1190 InputDemandedElts
.setBit(OutIdx
/Ratio
);
1196 // If there are more elements in the source than there are in the result,
1197 // then an input element is live if the corresponding output element is
1199 Ratio
= InVWidth
/VWidth
;
1200 for (unsigned InIdx
= 0; InIdx
!= InVWidth
; ++InIdx
)
1201 if (DemandedElts
[InIdx
/Ratio
])
1202 InputDemandedElts
.setBit(InIdx
);
1205 // div/rem demand all inputs, because they don't want divide by zero.
1206 TmpV
= SimplifyDemandedVectorElts(I
->getOperand(0), InputDemandedElts
,
1207 UndefElts2
, Depth
+1);
1209 I
->setOperand(0, TmpV
);
1213 UndefElts
= UndefElts2
;
1214 if (VWidth
> InVWidth
) {
1215 llvm_unreachable("Unimp");
1216 // If there are more elements in the result than there are in the source,
1217 // then an output element is undef if the corresponding input element is
1219 for (unsigned OutIdx
= 0; OutIdx
!= VWidth
; ++OutIdx
)
1220 if (UndefElts2
[OutIdx
/Ratio
])
1221 UndefElts
.setBit(OutIdx
);
1222 } else if (VWidth
< InVWidth
) {
1223 llvm_unreachable("Unimp");
1224 // If there are more elements in the source than there are in the result,
1225 // then a result element is undef if all of the corresponding input
1226 // elements are undef.
1227 UndefElts
= ~0ULL >> (64-VWidth
); // Start out all undef.
1228 for (unsigned InIdx
= 0; InIdx
!= InVWidth
; ++InIdx
)
1229 if (!UndefElts2
[InIdx
]) // Not undef?
1230 UndefElts
.clearBit(InIdx
/Ratio
); // Clear undef bit.
1234 case Instruction::And
:
1235 case Instruction::Or
:
1236 case Instruction::Xor
:
1237 case Instruction::Add
:
1238 case Instruction::Sub
:
1239 case Instruction::Mul
:
1240 // div/rem demand all inputs, because they don't want divide by zero.
1241 TmpV
= SimplifyDemandedVectorElts(I
->getOperand(0), DemandedElts
,
1242 UndefElts
, Depth
+1);
1243 if (TmpV
) { I
->setOperand(0, TmpV
); MadeChange
= true; }
1244 TmpV
= SimplifyDemandedVectorElts(I
->getOperand(1), DemandedElts
,
1245 UndefElts2
, Depth
+1);
1246 if (TmpV
) { I
->setOperand(1, TmpV
); MadeChange
= true; }
1248 // Output elements are undefined if both are undefined. Consider things
1249 // like undef&0. The result is known zero, not undef.
1250 UndefElts
&= UndefElts2
;
1252 case Instruction::FPTrunc
:
1253 case Instruction::FPExt
:
1254 TmpV
= SimplifyDemandedVectorElts(I
->getOperand(0), DemandedElts
,
1255 UndefElts
, Depth
+1);
1256 if (TmpV
) { I
->setOperand(0, TmpV
); MadeChange
= true; }
1259 case Instruction::Call
: {
1260 IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(I
);
1262 switch (II
->getIntrinsicID()) {
1265 // Binary vector operations that work column-wise. A dest element is a
1266 // function of the corresponding input elements from the two inputs.
1267 case Intrinsic::x86_sse_sub_ss
:
1268 case Intrinsic::x86_sse_mul_ss
:
1269 case Intrinsic::x86_sse_min_ss
:
1270 case Intrinsic::x86_sse_max_ss
:
1271 case Intrinsic::x86_sse2_sub_sd
:
1272 case Intrinsic::x86_sse2_mul_sd
:
1273 case Intrinsic::x86_sse2_min_sd
:
1274 case Intrinsic::x86_sse2_max_sd
:
1275 TmpV
= SimplifyDemandedVectorElts(II
->getArgOperand(0), DemandedElts
,
1276 UndefElts
, Depth
+1);
1277 if (TmpV
) { II
->setArgOperand(0, TmpV
); MadeChange
= true; }
1278 TmpV
= SimplifyDemandedVectorElts(II
->getArgOperand(1), DemandedElts
,
1279 UndefElts2
, Depth
+1);
1280 if (TmpV
) { II
->setArgOperand(1, TmpV
); MadeChange
= true; }
1282 // If only the low elt is demanded and this is a scalarizable intrinsic,
1283 // scalarize it now.
1284 if (DemandedElts
== 1) {
1285 switch (II
->getIntrinsicID()) {
1287 case Intrinsic::x86_sse_sub_ss
:
1288 case Intrinsic::x86_sse_mul_ss
:
1289 case Intrinsic::x86_sse2_sub_sd
:
1290 case Intrinsic::x86_sse2_mul_sd
:
1291 // TODO: Lower MIN/MAX/ABS/etc
1292 Value
*LHS
= II
->getArgOperand(0);
1293 Value
*RHS
= II
->getArgOperand(1);
1294 // Extract the element as scalars.
1295 LHS
= InsertNewInstWith(ExtractElementInst::Create(LHS
,
1296 ConstantInt::get(Type::getInt32Ty(I
->getContext()), 0U)), *II
);
1297 RHS
= InsertNewInstWith(ExtractElementInst::Create(RHS
,
1298 ConstantInt::get(Type::getInt32Ty(I
->getContext()), 0U)), *II
);
1300 switch (II
->getIntrinsicID()) {
1301 default: llvm_unreachable("Case stmts out of sync!");
1302 case Intrinsic::x86_sse_sub_ss
:
1303 case Intrinsic::x86_sse2_sub_sd
:
1304 TmpV
= InsertNewInstWith(BinaryOperator::CreateFSub(LHS
, RHS
,
1305 II
->getName()), *II
);
1307 case Intrinsic::x86_sse_mul_ss
:
1308 case Intrinsic::x86_sse2_mul_sd
:
1309 TmpV
= InsertNewInstWith(BinaryOperator::CreateFMul(LHS
, RHS
,
1310 II
->getName()), *II
);
1315 InsertElementInst::Create(
1316 UndefValue::get(II
->getType()), TmpV
,
1317 ConstantInt::get(Type::getInt32Ty(I
->getContext()), 0U, false),
1319 InsertNewInstWith(New
, *II
);
1324 // Output elements are undefined if both are undefined. Consider things
1325 // like undef&0. The result is known zero, not undef.
1326 UndefElts
&= UndefElts2
;
1332 return MadeChange
? I
: nullptr;