Bug Summary

File:lib/Analysis/InstructionSimplify.cpp
Warning:line 1430, column 35
Called C++ object pointer is null

Annotated Source Code

1//===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements routines for folding instructions into simpler forms
11// that do not require creating new instructions. This does constant folding
12// ("add i32 1, 1" -> "2") but can also handle non-constant operands, either
13// returning a constant ("and i32 %x, 0" -> "0") or an already existing value
14// ("and i32 %x, %x" -> "%x"). All operands are assumed to have already been
15// simplified: This is usually true and assuming it simplifies the logic (if
16// they have not been simplified then results are correct but maybe suboptimal).
17//
18//===----------------------------------------------------------------------===//
19
20#include "llvm/Analysis/InstructionSimplify.h"
21#include "llvm/ADT/SetVector.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/Analysis/AliasAnalysis.h"
24#include "llvm/Analysis/CaptureTracking.h"
25#include "llvm/Analysis/ConstantFolding.h"
26#include "llvm/Analysis/MemoryBuiltins.h"
27#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
28#include "llvm/Analysis/ValueTracking.h"
29#include "llvm/Analysis/VectorUtils.h"
30#include "llvm/IR/ConstantRange.h"
31#include "llvm/IR/DataLayout.h"
32#include "llvm/IR/Dominators.h"
33#include "llvm/IR/GetElementPtrTypeIterator.h"
34#include "llvm/IR/GlobalAlias.h"
35#include "llvm/IR/Operator.h"
36#include "llvm/IR/PatternMatch.h"
37#include "llvm/IR/ValueHandle.h"
38#include <algorithm>
39using namespace llvm;
40using namespace llvm::PatternMatch;
41
42#define DEBUG_TYPE"instsimplify" "instsimplify"
43
44enum { RecursionLimit = 3 };
45
46STATISTIC(NumExpand, "Number of expansions")static llvm::Statistic NumExpand = {"instsimplify", "NumExpand"
, "Number of expansions", {0}, false}
;
47STATISTIC(NumReassoc, "Number of reassociations")static llvm::Statistic NumReassoc = {"instsimplify", "NumReassoc"
, "Number of reassociations", {0}, false}
;
48
49static Value *SimplifyAndInst(Value *, Value *, const SimplifyQuery &, unsigned);
50static Value *SimplifyBinOp(unsigned, Value *, Value *, const SimplifyQuery &,
51 unsigned);
52static Value *SimplifyFPBinOp(unsigned, Value *, Value *, const FastMathFlags &,
53 const SimplifyQuery &, unsigned);
54static Value *SimplifyCmpInst(unsigned, Value *, Value *, const SimplifyQuery &,
55 unsigned);
56static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
57 const SimplifyQuery &Q, unsigned MaxRecurse);
58static Value *SimplifyOrInst(Value *, Value *, const SimplifyQuery &, unsigned);
59static Value *SimplifyXorInst(Value *, Value *, const SimplifyQuery &, unsigned);
60static Value *SimplifyCastInst(unsigned, Value *, Type *,
61 const SimplifyQuery &, unsigned);
62
63/// For a boolean type or a vector of boolean type, return false or a vector
64/// with every element false.
65static Constant *getFalse(Type *Ty) {
66 return ConstantInt::getFalse(Ty);
67}
68
69/// For a boolean type or a vector of boolean type, return true or a vector
70/// with every element true.
71static Constant *getTrue(Type *Ty) {
72 return ConstantInt::getTrue(Ty);
73}
74
75/// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
76static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS,
77 Value *RHS) {
78 CmpInst *Cmp = dyn_cast<CmpInst>(V);
79 if (!Cmp)
80 return false;
81 CmpInst::Predicate CPred = Cmp->getPredicate();
82 Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
83 if (CPred == Pred && CLHS == LHS && CRHS == RHS)
84 return true;
85 return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS &&
86 CRHS == LHS;
87}
88
89/// Does the given value dominate the specified phi node?
90static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
91 Instruction *I = dyn_cast<Instruction>(V);
92 if (!I)
93 // Arguments and constants dominate all instructions.
94 return true;
95
96 // If we are processing instructions (and/or basic blocks) that have not been
97 // fully added to a function, the parent nodes may still be null. Simply
98 // return the conservative answer in these cases.
99 if (!I->getParent() || !P->getParent() || !I->getParent()->getParent())
100 return false;
101
102 // If we have a DominatorTree then do a precise test.
103 if (DT) {
104 if (!DT->isReachableFromEntry(P->getParent()))
105 return true;
106 if (!DT->isReachableFromEntry(I->getParent()))
107 return false;
108 return DT->dominates(I, P);
109 }
110
111 // Otherwise, if the instruction is in the entry block and is not an invoke,
112 // then it obviously dominates all phi nodes.
113 if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() &&
114 !isa<InvokeInst>(I))
115 return true;
116
117 return false;
118}
119
120/// Simplify "A op (B op' C)" by distributing op over op', turning it into
121/// "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is
122/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.
123/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)".
124/// Returns the simplified value, or null if no simplification was performed.
125static Value *ExpandBinOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
126 Instruction::BinaryOps OpcodeToExpand, const SimplifyQuery &Q,
127 unsigned MaxRecurse) {
128 // Recursion is always used, so bail out at once if we already hit the limit.
129 if (!MaxRecurse--)
130 return nullptr;
131
132 // Check whether the expression has the form "(A op' B) op C".
133 if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS))
134 if (Op0->getOpcode() == OpcodeToExpand) {
135 // It does! Try turning it into "(A op C) op' (B op C)".
136 Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
137 // Do "A op C" and "B op C" both simplify?
138 if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse))
139 if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
140 // They do! Return "L op' R" if it simplifies or is already available.
141 // If "L op' R" equals "A op' B" then "L op' R" is just the LHS.
142 if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand)
143 && L == B && R == A)) {
144 ++NumExpand;
145 return LHS;
146 }
147 // Otherwise return "L op' R" if it simplifies.
148 if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
149 ++NumExpand;
150 return V;
151 }
152 }
153 }
154
155 // Check whether the expression has the form "A op (B op' C)".
156 if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS))
157 if (Op1->getOpcode() == OpcodeToExpand) {
158 // It does! Try turning it into "(A op B) op' (A op C)".
159 Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
160 // Do "A op B" and "A op C" both simplify?
161 if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse))
162 if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) {
163 // They do! Return "L op' R" if it simplifies or is already available.
164 // If "L op' R" equals "B op' C" then "L op' R" is just the RHS.
165 if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand)
166 && L == C && R == B)) {
167 ++NumExpand;
168 return RHS;
169 }
170 // Otherwise return "L op' R" if it simplifies.
171 if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) {
172 ++NumExpand;
173 return V;
174 }
175 }
176 }
177
178 return nullptr;
179}
180
181/// Generic simplifications for associative binary operations.
182/// Returns the simpler value, or null if none was found.
183static Value *SimplifyAssociativeBinOp(Instruction::BinaryOps Opcode,
184 Value *LHS, Value *RHS, const SimplifyQuery &Q,
185 unsigned MaxRecurse) {
186 assert(Instruction::isAssociative(Opcode) && "Not an associative operation!")((Instruction::isAssociative(Opcode) && "Not an associative operation!"
) ? static_cast<void> (0) : __assert_fail ("Instruction::isAssociative(Opcode) && \"Not an associative operation!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 186, __PRETTY_FUNCTION__))
;
187
188 // Recursion is always used, so bail out at once if we already hit the limit.
189 if (!MaxRecurse--)
190 return nullptr;
191
192 BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
193 BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
194
195 // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely.
196 if (Op0 && Op0->getOpcode() == Opcode) {
197 Value *A = Op0->getOperand(0);
198 Value *B = Op0->getOperand(1);
199 Value *C = RHS;
200
201 // Does "B op C" simplify?
202 if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) {
203 // It does! Return "A op V" if it simplifies or is already available.
204 // If V equals B then "A op V" is just the LHS.
205 if (V == B) return LHS;
206 // Otherwise return "A op V" if it simplifies.
207 if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) {
208 ++NumReassoc;
209 return W;
210 }
211 }
212 }
213
214 // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely.
215 if (Op1 && Op1->getOpcode() == Opcode) {
216 Value *A = LHS;
217 Value *B = Op1->getOperand(0);
218 Value *C = Op1->getOperand(1);
219
220 // Does "A op B" simplify?
221 if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) {
222 // It does! Return "V op C" if it simplifies or is already available.
223 // If V equals B then "V op C" is just the RHS.
224 if (V == B) return RHS;
225 // Otherwise return "V op C" if it simplifies.
226 if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) {
227 ++NumReassoc;
228 return W;
229 }
230 }
231 }
232
233 // The remaining transforms require commutativity as well as associativity.
234 if (!Instruction::isCommutative(Opcode))
235 return nullptr;
236
237 // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely.
238 if (Op0 && Op0->getOpcode() == Opcode) {
239 Value *A = Op0->getOperand(0);
240 Value *B = Op0->getOperand(1);
241 Value *C = RHS;
242
243 // Does "C op A" simplify?
244 if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
245 // It does! Return "V op B" if it simplifies or is already available.
246 // If V equals A then "V op B" is just the LHS.
247 if (V == A) return LHS;
248 // Otherwise return "V op B" if it simplifies.
249 if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) {
250 ++NumReassoc;
251 return W;
252 }
253 }
254 }
255
256 // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely.
257 if (Op1 && Op1->getOpcode() == Opcode) {
258 Value *A = LHS;
259 Value *B = Op1->getOperand(0);
260 Value *C = Op1->getOperand(1);
261
262 // Does "C op A" simplify?
263 if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) {
264 // It does! Return "B op V" if it simplifies or is already available.
265 // If V equals C then "B op V" is just the RHS.
266 if (V == C) return RHS;
267 // Otherwise return "B op V" if it simplifies.
268 if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) {
269 ++NumReassoc;
270 return W;
271 }
272 }
273 }
274
275 return nullptr;
276}
277
278/// In the case of a binary operation with a select instruction as an operand,
279/// try to simplify the binop by seeing whether evaluating it on both branches
280/// of the select results in the same value. Returns the common value if so,
281/// otherwise returns null.
282static Value *ThreadBinOpOverSelect(Instruction::BinaryOps Opcode, Value *LHS,
283 Value *RHS, const SimplifyQuery &Q,
284 unsigned MaxRecurse) {
285 // Recursion is always used, so bail out at once if we already hit the limit.
286 if (!MaxRecurse--)
287 return nullptr;
288
289 SelectInst *SI;
290 if (isa<SelectInst>(LHS)) {
291 SI = cast<SelectInst>(LHS);
292 } else {
293 assert(isa<SelectInst>(RHS) && "No select instruction operand!")((isa<SelectInst>(RHS) && "No select instruction operand!"
) ? static_cast<void> (0) : __assert_fail ("isa<SelectInst>(RHS) && \"No select instruction operand!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 293, __PRETTY_FUNCTION__))
;
294 SI = cast<SelectInst>(RHS);
295 }
296
297 // Evaluate the BinOp on the true and false branches of the select.
298 Value *TV;
299 Value *FV;
300 if (SI == LHS) {
301 TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse);
302 FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse);
303 } else {
304 TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse);
305 FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse);
306 }
307
308 // If they simplified to the same value, then return the common value.
309 // If they both failed to simplify then return null.
310 if (TV == FV)
311 return TV;
312
313 // If one branch simplified to undef, return the other one.
314 if (TV && isa<UndefValue>(TV))
315 return FV;
316 if (FV && isa<UndefValue>(FV))
317 return TV;
318
319 // If applying the operation did not change the true and false select values,
320 // then the result of the binop is the select itself.
321 if (TV == SI->getTrueValue() && FV == SI->getFalseValue())
322 return SI;
323
324 // If one branch simplified and the other did not, and the simplified
325 // value is equal to the unsimplified one, return the simplified value.
326 // For example, select (cond, X, X & Z) & Z -> X & Z.
327 if ((FV && !TV) || (TV && !FV)) {
328 // Check that the simplified value has the form "X op Y" where "op" is the
329 // same as the original operation.
330 Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV);
331 if (Simplified && Simplified->getOpcode() == Opcode) {
332 // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS".
333 // We already know that "op" is the same as for the simplified value. See
334 // if the operands match too. If so, return the simplified value.
335 Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue();
336 Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS;
337 Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch;
338 if (Simplified->getOperand(0) == UnsimplifiedLHS &&
339 Simplified->getOperand(1) == UnsimplifiedRHS)
340 return Simplified;
341 if (Simplified->isCommutative() &&
342 Simplified->getOperand(1) == UnsimplifiedLHS &&
343 Simplified->getOperand(0) == UnsimplifiedRHS)
344 return Simplified;
345 }
346 }
347
348 return nullptr;
349}
350
351/// In the case of a comparison with a select instruction, try to simplify the
352/// comparison by seeing whether both branches of the select result in the same
353/// value. Returns the common value if so, otherwise returns null.
354static Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS,
355 Value *RHS, const SimplifyQuery &Q,
356 unsigned MaxRecurse) {
357 // Recursion is always used, so bail out at once if we already hit the limit.
358 if (!MaxRecurse--)
359 return nullptr;
360
361 // Make sure the select is on the LHS.
362 if (!isa<SelectInst>(LHS)) {
363 std::swap(LHS, RHS);
364 Pred = CmpInst::getSwappedPredicate(Pred);
365 }
366 assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!")((isa<SelectInst>(LHS) && "Not comparing with a select instruction!"
) ? static_cast<void> (0) : __assert_fail ("isa<SelectInst>(LHS) && \"Not comparing with a select instruction!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 366, __PRETTY_FUNCTION__))
;
367 SelectInst *SI = cast<SelectInst>(LHS);
368 Value *Cond = SI->getCondition();
369 Value *TV = SI->getTrueValue();
370 Value *FV = SI->getFalseValue();
371
372 // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it.
373 // Does "cmp TV, RHS" simplify?
374 Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse);
375 if (TCmp == Cond) {
376 // It not only simplified, it simplified to the select condition. Replace
377 // it with 'true'.
378 TCmp = getTrue(Cond->getType());
379 } else if (!TCmp) {
380 // It didn't simplify. However if "cmp TV, RHS" is equal to the select
381 // condition then we can replace it with 'true'. Otherwise give up.
382 if (!isSameCompare(Cond, Pred, TV, RHS))
383 return nullptr;
384 TCmp = getTrue(Cond->getType());
385 }
386
387 // Does "cmp FV, RHS" simplify?
388 Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse);
389 if (FCmp == Cond) {
390 // It not only simplified, it simplified to the select condition. Replace
391 // it with 'false'.
392 FCmp = getFalse(Cond->getType());
393 } else if (!FCmp) {
394 // It didn't simplify. However if "cmp FV, RHS" is equal to the select
395 // condition then we can replace it with 'false'. Otherwise give up.
396 if (!isSameCompare(Cond, Pred, FV, RHS))
397 return nullptr;
398 FCmp = getFalse(Cond->getType());
399 }
400
401 // If both sides simplified to the same value, then use it as the result of
402 // the original comparison.
403 if (TCmp == FCmp)
404 return TCmp;
405
406 // The remaining cases only make sense if the select condition has the same
407 // type as the result of the comparison, so bail out if this is not so.
408 if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy())
409 return nullptr;
410 // If the false value simplified to false, then the result of the compare
411 // is equal to "Cond && TCmp". This also catches the case when the false
412 // value simplified to false and the true value to true, returning "Cond".
413 if (match(FCmp, m_Zero()))
414 if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse))
415 return V;
416 // If the true value simplified to true, then the result of the compare
417 // is equal to "Cond || FCmp".
418 if (match(TCmp, m_One()))
419 if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse))
420 return V;
421 // Finally, if the false value simplified to true and the true value to
422 // false, then the result of the compare is equal to "!Cond".
423 if (match(FCmp, m_One()) && match(TCmp, m_Zero()))
424 if (Value *V =
425 SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()),
426 Q, MaxRecurse))
427 return V;
428
429 return nullptr;
430}
431
432/// In the case of a binary operation with an operand that is a PHI instruction,
433/// try to simplify the binop by seeing whether evaluating it on the incoming
434/// phi values yields the same result for every value. If so returns the common
435/// value, otherwise returns null.
436static Value *ThreadBinOpOverPHI(Instruction::BinaryOps Opcode, Value *LHS,
437 Value *RHS, const SimplifyQuery &Q,
438 unsigned MaxRecurse) {
439 // Recursion is always used, so bail out at once if we already hit the limit.
440 if (!MaxRecurse--)
441 return nullptr;
442
443 PHINode *PI;
444 if (isa<PHINode>(LHS)) {
445 PI = cast<PHINode>(LHS);
446 // Bail out if RHS and the phi may be mutually interdependent due to a loop.
447 if (!ValueDominatesPHI(RHS, PI, Q.DT))
448 return nullptr;
449 } else {
450 assert(isa<PHINode>(RHS) && "No PHI instruction operand!")((isa<PHINode>(RHS) && "No PHI instruction operand!"
) ? static_cast<void> (0) : __assert_fail ("isa<PHINode>(RHS) && \"No PHI instruction operand!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 450, __PRETTY_FUNCTION__))
;
451 PI = cast<PHINode>(RHS);
452 // Bail out if LHS and the phi may be mutually interdependent due to a loop.
453 if (!ValueDominatesPHI(LHS, PI, Q.DT))
454 return nullptr;
455 }
456
457 // Evaluate the BinOp on the incoming phi values.
458 Value *CommonValue = nullptr;
459 for (Value *Incoming : PI->incoming_values()) {
460 // If the incoming value is the phi node itself, it can safely be skipped.
461 if (Incoming == PI) continue;
462 Value *V = PI == LHS ?
463 SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) :
464 SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse);
465 // If the operation failed to simplify, or simplified to a different value
466 // to previously, then give up.
467 if (!V || (CommonValue && V != CommonValue))
468 return nullptr;
469 CommonValue = V;
470 }
471
472 return CommonValue;
473}
474
475/// In the case of a comparison with a PHI instruction, try to simplify the
476/// comparison by seeing whether comparing with all of the incoming phi values
477/// yields the same result every time. If so returns the common result,
478/// otherwise returns null.
479static Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS,
480 const SimplifyQuery &Q, unsigned MaxRecurse) {
481 // Recursion is always used, so bail out at once if we already hit the limit.
482 if (!MaxRecurse--)
483 return nullptr;
484
485 // Make sure the phi is on the LHS.
486 if (!isa<PHINode>(LHS)) {
487 std::swap(LHS, RHS);
488 Pred = CmpInst::getSwappedPredicate(Pred);
489 }
490 assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!")((isa<PHINode>(LHS) && "Not comparing with a phi instruction!"
) ? static_cast<void> (0) : __assert_fail ("isa<PHINode>(LHS) && \"Not comparing with a phi instruction!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 490, __PRETTY_FUNCTION__))
;
491 PHINode *PI = cast<PHINode>(LHS);
492
493 // Bail out if RHS and the phi may be mutually interdependent due to a loop.
494 if (!ValueDominatesPHI(RHS, PI, Q.DT))
495 return nullptr;
496
497 // Evaluate the BinOp on the incoming phi values.
498 Value *CommonValue = nullptr;
499 for (Value *Incoming : PI->incoming_values()) {
500 // If the incoming value is the phi node itself, it can safely be skipped.
501 if (Incoming == PI) continue;
502 Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse);
503 // If the operation failed to simplify, or simplified to a different value
504 // to previously, then give up.
505 if (!V || (CommonValue && V != CommonValue))
506 return nullptr;
507 CommonValue = V;
508 }
509
510 return CommonValue;
511}
512
513static Constant *foldOrCommuteConstant(Instruction::BinaryOps Opcode,
514 Value *&Op0, Value *&Op1,
515 const SimplifyQuery &Q) {
516 if (auto *CLHS = dyn_cast<Constant>(Op0)) {
517 if (auto *CRHS = dyn_cast<Constant>(Op1))
518 return ConstantFoldBinaryOpOperands(Opcode, CLHS, CRHS, Q.DL);
519
520 // Canonicalize the constant to the RHS if this is a commutative operation.
521 if (Instruction::isCommutative(Opcode))
522 std::swap(Op0, Op1);
523 }
524 return nullptr;
525}
526
527/// Given operands for an Add, see if we can fold the result.
528/// If not, this returns null.
529static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
530 const SimplifyQuery &Q, unsigned MaxRecurse) {
531 if (Constant *C = foldOrCommuteConstant(Instruction::Add, Op0, Op1, Q))
532 return C;
533
534 // X + undef -> undef
535 if (match(Op1, m_Undef()))
536 return Op1;
537
538 // X + 0 -> X
539 if (match(Op1, m_Zero()))
540 return Op0;
541
542 // X + (Y - X) -> Y
543 // (Y - X) + X -> Y
544 // Eg: X + -X -> 0
545 Value *Y = nullptr;
546 if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
547 match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
548 return Y;
549
550 // X + ~X -> -1 since ~X = -X-1
551 Type *Ty = Op0->getType();
552 if (match(Op0, m_Not(m_Specific(Op1))) ||
553 match(Op1, m_Not(m_Specific(Op0))))
554 return Constant::getAllOnesValue(Ty);
555
556 // add nsw/nuw (xor Y, signmask), signmask --> Y
557 // The no-wrapping add guarantees that the top bit will be set by the add.
558 // Therefore, the xor must be clearing the already set sign bit of Y.
559 if ((isNSW || isNUW) && match(Op1, m_SignMask()) &&
560 match(Op0, m_Xor(m_Value(Y), m_SignMask())))
561 return Y;
562
563 /// i1 add -> xor.
564 if (MaxRecurse && Op0->getType()->getScalarType()->isIntegerTy(1))
565 if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
566 return V;
567
568 // Try some generic simplifications for associative operations.
569 if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q,
570 MaxRecurse))
571 return V;
572
573 // Threading Add over selects and phi nodes is pointless, so don't bother.
574 // Threading over the select in "A + select(cond, B, C)" means evaluating
575 // "A+B" and "A+C" and seeing if they are equal; but they are equal if and
576 // only if B and C are equal. If B and C are equal then (since we assume
577 // that operands have already been simplified) "select(cond, B, C)" should
578 // have been simplified to the common value of B and C already. Analysing
579 // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly
580 // for threading over phi nodes.
581
582 return nullptr;
583}
584
585Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
586 const DataLayout &DL, const TargetLibraryInfo *TLI,
587 const DominatorTree *DT, AssumptionCache *AC,
588 const Instruction *CxtI) {
589 return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, {DL, TLI, DT, AC, CxtI},
590 RecursionLimit);
591}
592
593Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
594 const SimplifyQuery &Query) {
595 return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query, RecursionLimit);
596}
597
598/// \brief Compute the base pointer and cumulative constant offsets for V.
599///
600/// This strips all constant offsets off of V, leaving it the base pointer, and
601/// accumulates the total constant offset applied in the returned constant. It
602/// returns 0 if V is not a pointer, and returns the constant '0' if there are
603/// no constant offsets applied.
604///
605/// This is very similar to GetPointerBaseWithConstantOffset except it doesn't
606/// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc.
607/// folding.
608static Constant *stripAndComputeConstantOffsets(const DataLayout &DL, Value *&V,
609 bool AllowNonInbounds = false) {
610 assert(V->getType()->getScalarType()->isPointerTy())((V->getType()->getScalarType()->isPointerTy()) ? static_cast
<void> (0) : __assert_fail ("V->getType()->getScalarType()->isPointerTy()"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 610, __PRETTY_FUNCTION__))
;
611
612 Type *IntPtrTy = DL.getIntPtrType(V->getType())->getScalarType();
613 APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth());
614
615 // Even though we don't look through PHI nodes, we could be called on an
616 // instruction in an unreachable block, which may be on a cycle.
617 SmallPtrSet<Value *, 4> Visited;
618 Visited.insert(V);
619 do {
620 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
621 if ((!AllowNonInbounds && !GEP->isInBounds()) ||
622 !GEP->accumulateConstantOffset(DL, Offset))
623 break;
624 V = GEP->getPointerOperand();
625 } else if (Operator::getOpcode(V) == Instruction::BitCast) {
626 V = cast<Operator>(V)->getOperand(0);
627 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
628 if (GA->isInterposable())
629 break;
630 V = GA->getAliasee();
631 } else {
632 if (auto CS = CallSite(V))
633 if (Value *RV = CS.getReturnedArgOperand()) {
634 V = RV;
635 continue;
636 }
637 break;
638 }
639 assert(V->getType()->getScalarType()->isPointerTy() &&((V->getType()->getScalarType()->isPointerTy() &&
"Unexpected operand type!") ? static_cast<void> (0) : __assert_fail
("V->getType()->getScalarType()->isPointerTy() && \"Unexpected operand type!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 640, __PRETTY_FUNCTION__))
640 "Unexpected operand type!")((V->getType()->getScalarType()->isPointerTy() &&
"Unexpected operand type!") ? static_cast<void> (0) : __assert_fail
("V->getType()->getScalarType()->isPointerTy() && \"Unexpected operand type!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 640, __PRETTY_FUNCTION__))
;
641 } while (Visited.insert(V).second);
642
643 Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset);
644 if (V->getType()->isVectorTy())
645 return ConstantVector::getSplat(V->getType()->getVectorNumElements(),
646 OffsetIntPtr);
647 return OffsetIntPtr;
648}
649
650/// \brief Compute the constant difference between two pointer values.
651/// If the difference is not a constant, returns zero.
652static Constant *computePointerDifference(const DataLayout &DL, Value *LHS,
653 Value *RHS) {
654 Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
655 Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
656
657 // If LHS and RHS are not related via constant offsets to the same base
658 // value, there is nothing we can do here.
659 if (LHS != RHS)
660 return nullptr;
661
662 // Otherwise, the difference of LHS - RHS can be computed as:
663 // LHS - RHS
664 // = (LHSOffset + Base) - (RHSOffset + Base)
665 // = LHSOffset - RHSOffset
666 return ConstantExpr::getSub(LHSOffset, RHSOffset);
667}
668
669/// Given operands for a Sub, see if we can fold the result.
670/// If not, this returns null.
671static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
672 const SimplifyQuery &Q, unsigned MaxRecurse) {
673 if (Constant *C = foldOrCommuteConstant(Instruction::Sub, Op0, Op1, Q))
674 return C;
675
676 // X - undef -> undef
677 // undef - X -> undef
678 if (match(Op0, m_Undef()) || match(Op1, m_Undef()))
679 return UndefValue::get(Op0->getType());
680
681 // X - 0 -> X
682 if (match(Op1, m_Zero()))
683 return Op0;
684
685 // X - X -> 0
686 if (Op0 == Op1)
687 return Constant::getNullValue(Op0->getType());
688
689 // Is this a negation?
690 if (match(Op0, m_Zero())) {
691 // 0 - X -> 0 if the sub is NUW.
692 if (isNUW)
693 return Op0;
694
695 unsigned BitWidth = Op1->getType()->getScalarSizeInBits();
696 APInt KnownZero(BitWidth, 0);
697 APInt KnownOne(BitWidth, 0);
698 computeKnownBits(Op1, KnownZero, KnownOne, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
699 if (KnownZero.isMaxSignedValue()) {
700 // Op1 is either 0 or the minimum signed value. If the sub is NSW, then
701 // Op1 must be 0 because negating the minimum signed value is undefined.
702 if (isNSW)
703 return Op0;
704
705 // 0 - X -> X if X is 0 or the minimum signed value.
706 return Op1;
707 }
708 }
709
710 // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
711 // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
712 Value *X = nullptr, *Y = nullptr, *Z = Op1;
713 if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
714 // See if "V === Y - Z" simplifies.
715 if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1))
716 // It does! Now see if "X + V" simplifies.
717 if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) {
718 // It does, we successfully reassociated!
719 ++NumReassoc;
720 return W;
721 }
722 // See if "V === X - Z" simplifies.
723 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
724 // It does! Now see if "Y + V" simplifies.
725 if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) {
726 // It does, we successfully reassociated!
727 ++NumReassoc;
728 return W;
729 }
730 }
731
732 // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies.
733 // For example, X - (X + 1) -> -1
734 X = Op0;
735 if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z)
736 // See if "V === X - Y" simplifies.
737 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
738 // It does! Now see if "V - Z" simplifies.
739 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) {
740 // It does, we successfully reassociated!
741 ++NumReassoc;
742 return W;
743 }
744 // See if "V === X - Z" simplifies.
745 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1))
746 // It does! Now see if "V - Y" simplifies.
747 if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) {
748 // It does, we successfully reassociated!
749 ++NumReassoc;
750 return W;
751 }
752 }
753
754 // Z - (X - Y) -> (Z - X) + Y if everything simplifies.
755 // For example, X - (X - Y) -> Y.
756 Z = Op0;
757 if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y)
758 // See if "V === Z - X" simplifies.
759 if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1))
760 // It does! Now see if "V + Y" simplifies.
761 if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) {
762 // It does, we successfully reassociated!
763 ++NumReassoc;
764 return W;
765 }
766
767 // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies.
768 if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) &&
769 match(Op1, m_Trunc(m_Value(Y))))
770 if (X->getType() == Y->getType())
771 // See if "V === X - Y" simplifies.
772 if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1))
773 // It does! Now see if "trunc V" simplifies.
774 if (Value *W = SimplifyCastInst(Instruction::Trunc, V, Op0->getType(),
775 Q, MaxRecurse - 1))
776 // It does, return the simplified "trunc V".
777 return W;
778
779 // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...).
780 if (match(Op0, m_PtrToInt(m_Value(X))) &&
781 match(Op1, m_PtrToInt(m_Value(Y))))
782 if (Constant *Result = computePointerDifference(Q.DL, X, Y))
783 return ConstantExpr::getIntegerCast(Result, Op0->getType(), true);
784
785 // i1 sub -> xor.
786 if (MaxRecurse && Op0->getType()->getScalarType()->isIntegerTy(1))
787 if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1))
788 return V;
789
790 // Threading Sub over selects and phi nodes is pointless, so don't bother.
791 // Threading over the select in "A - select(cond, B, C)" means evaluating
792 // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
793 // only if B and C are equal. If B and C are equal then (since we assume
794 // that operands have already been simplified) "select(cond, B, C)" should
795 // have been simplified to the common value of B and C already. Analysing
796 // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly
797 // for threading over phi nodes.
798
799 return nullptr;
800}
801
802Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
803 const DataLayout &DL, const TargetLibraryInfo *TLI,
804 const DominatorTree *DT, AssumptionCache *AC,
805 const Instruction *CxtI) {
806 return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, {DL, TLI, DT, AC, CxtI},
807 RecursionLimit);
808}
809
810Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
811 const SimplifyQuery &Q) {
812 return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
813}
814
815/// Given operands for an FAdd, see if we can fold the result. If not, this
816/// returns null.
817static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
818 const SimplifyQuery &Q, unsigned MaxRecurse) {
819 if (Constant *C = foldOrCommuteConstant(Instruction::FAdd, Op0, Op1, Q))
820 return C;
821
822 // fadd X, -0 ==> X
823 if (match(Op1, m_NegZero()))
824 return Op0;
825
826 // fadd X, 0 ==> X, when we know X is not -0
827 if (match(Op1, m_Zero()) &&
828 (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI)))
829 return Op0;
830
831 // fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0
832 // where nnan and ninf have to occur at least once somewhere in this
833 // expression
834 Value *SubOp = nullptr;
835 if (match(Op1, m_FSub(m_AnyZero(), m_Specific(Op0))))
836 SubOp = Op1;
837 else if (match(Op0, m_FSub(m_AnyZero(), m_Specific(Op1))))
838 SubOp = Op0;
839 if (SubOp) {
840 Instruction *FSub = cast<Instruction>(SubOp);
841 if ((FMF.noNaNs() || FSub->hasNoNaNs()) &&
842 (FMF.noInfs() || FSub->hasNoInfs()))
843 return Constant::getNullValue(Op0->getType());
844 }
845
846 return nullptr;
847}
848
849/// Given operands for an FSub, see if we can fold the result. If not, this
850/// returns null.
851static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
852 const SimplifyQuery &Q, unsigned MaxRecurse) {
853 if (Constant *C = foldOrCommuteConstant(Instruction::FSub, Op0, Op1, Q))
854 return C;
855
856 // fsub X, 0 ==> X
857 if (match(Op1, m_Zero()))
858 return Op0;
859
860 // fsub X, -0 ==> X, when we know X is not -0
861 if (match(Op1, m_NegZero()) &&
862 (FMF.noSignedZeros() || CannotBeNegativeZero(Op0, Q.TLI)))
863 return Op0;
864
865 // fsub -0.0, (fsub -0.0, X) ==> X
866 Value *X;
867 if (match(Op0, m_NegZero()) && match(Op1, m_FSub(m_NegZero(), m_Value(X))))
868 return X;
869
870 // fsub 0.0, (fsub 0.0, X) ==> X if signed zeros are ignored.
871 if (FMF.noSignedZeros() && match(Op0, m_AnyZero()) &&
872 match(Op1, m_FSub(m_AnyZero(), m_Value(X))))
873 return X;
874
875 // fsub nnan x, x ==> 0.0
876 if (FMF.noNaNs() && Op0 == Op1)
877 return Constant::getNullValue(Op0->getType());
878
879 return nullptr;
880}
881
882/// Given the operands for an FMul, see if we can fold the result
883static Value *SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
884 const SimplifyQuery &Q, unsigned MaxRecurse) {
885 if (Constant *C = foldOrCommuteConstant(Instruction::FMul, Op0, Op1, Q))
886 return C;
887
888 // fmul X, 1.0 ==> X
889 if (match(Op1, m_FPOne()))
890 return Op0;
891
892 // fmul nnan nsz X, 0 ==> 0
893 if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZero()))
894 return Op1;
895
896 return nullptr;
897}
898
899/// Given operands for a Mul, see if we can fold the result.
900/// If not, this returns null.
901static Value *SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
902 unsigned MaxRecurse) {
903 if (Constant *C = foldOrCommuteConstant(Instruction::Mul, Op0, Op1, Q))
904 return C;
905
906 // X * undef -> 0
907 if (match(Op1, m_Undef()))
908 return Constant::getNullValue(Op0->getType());
909
910 // X * 0 -> 0
911 if (match(Op1, m_Zero()))
912 return Op1;
913
914 // X * 1 -> X
915 if (match(Op1, m_One()))
916 return Op0;
917
918 // (X / Y) * Y -> X if the division is exact.
919 Value *X = nullptr;
920 if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y
921 match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0))))) // Y * (X / Y)
922 return X;
923
924 // i1 mul -> and.
925 if (MaxRecurse && Op0->getType()->getScalarType()->isIntegerTy(1))
926 if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1))
927 return V;
928
929 // Try some generic simplifications for associative operations.
930 if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q,
931 MaxRecurse))
932 return V;
933
934 // Mul distributes over Add. Try some generic simplifications based on this.
935 if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add,
936 Q, MaxRecurse))
937 return V;
938
939 // If the operation is with the result of a select instruction, check whether
940 // operating on either branch of the select always yields the same value.
941 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
942 if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q,
943 MaxRecurse))
944 return V;
945
946 // If the operation is with the result of a phi instruction, check whether
947 // operating on all incoming values of the phi always yields the same value.
948 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
949 if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q,
950 MaxRecurse))
951 return V;
952
953 return nullptr;
954}
955
956Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
957 const DataLayout &DL,
958 const TargetLibraryInfo *TLI,
959 const DominatorTree *DT, AssumptionCache *AC,
960 const Instruction *CxtI) {
961 return ::SimplifyFAddInst(Op0, Op1, FMF, {DL, TLI, DT, AC, CxtI},
962 RecursionLimit);
963}
964
965Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF,
966 const SimplifyQuery &Q) {
967 return ::SimplifyFAddInst(Op0, Op1, FMF, Q, RecursionLimit);
968}
969
970Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
971 const DataLayout &DL,
972 const TargetLibraryInfo *TLI,
973 const DominatorTree *DT, AssumptionCache *AC,
974 const Instruction *CxtI) {
975 return ::SimplifyFSubInst(Op0, Op1, FMF, {DL, TLI, DT, AC, CxtI},
976 RecursionLimit);
977}
978
979Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF,
980 const SimplifyQuery &Q) {
981 return ::SimplifyFSubInst(Op0, Op1, FMF, Q, RecursionLimit);
982}
983
984Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
985 const DataLayout &DL,
986 const TargetLibraryInfo *TLI,
987 const DominatorTree *DT, AssumptionCache *AC,
988 const Instruction *CxtI) {
989 return ::SimplifyFMulInst(Op0, Op1, FMF, {DL, TLI, DT, AC, CxtI},
990 RecursionLimit);
991}
992
993Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, FastMathFlags FMF,
994 const SimplifyQuery &Q) {
995 return ::SimplifyFMulInst(Op0, Op1, FMF, Q, RecursionLimit);
996}
997
998Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout &DL,
999 const TargetLibraryInfo *TLI,
1000 const DominatorTree *DT, AssumptionCache *AC,
1001 const Instruction *CxtI) {
1002 return ::SimplifyMulInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
1003}
1004
1005Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1006 return ::SimplifyMulInst(Op0, Op1, Q, RecursionLimit);
1007}
1008
1009/// Check for common or similar folds of integer division or integer remainder.
1010static Value *simplifyDivRem(Value *Op0, Value *Op1, bool IsDiv) {
1011 Type *Ty = Op0->getType();
1012
1013 // X / undef -> undef
1014 // X % undef -> undef
1015 if (match(Op1, m_Undef()))
1016 return Op1;
1017
1018 // X / 0 -> undef
1019 // X % 0 -> undef
1020 // We don't need to preserve faults!
1021 if (match(Op1, m_Zero()))
1022 return UndefValue::get(Ty);
1023
1024 // If any element of a constant divisor vector is zero, the whole op is undef.
1025 auto *Op1C = dyn_cast<Constant>(Op1);
1026 if (Op1C && Ty->isVectorTy()) {
1027 unsigned NumElts = Ty->getVectorNumElements();
1028 for (unsigned i = 0; i != NumElts; ++i) {
1029 Constant *Elt = Op1C->getAggregateElement(i);
1030 if (Elt && Elt->isNullValue())
1031 return UndefValue::get(Ty);
1032 }
1033 }
1034
1035 // undef / X -> 0
1036 // undef % X -> 0
1037 if (match(Op0, m_Undef()))
1038 return Constant::getNullValue(Ty);
1039
1040 // 0 / X -> 0
1041 // 0 % X -> 0
1042 if (match(Op0, m_Zero()))
1043 return Op0;
1044
1045 // X / X -> 1
1046 // X % X -> 0
1047 if (Op0 == Op1)
1048 return IsDiv ? ConstantInt::get(Ty, 1) : Constant::getNullValue(Ty);
1049
1050 // X / 1 -> X
1051 // X % 1 -> 0
1052 // If this is a boolean op (single-bit element type), we can't have
1053 // division-by-zero or remainder-by-zero, so assume the divisor is 1.
1054 if (match(Op1, m_One()) || Ty->getScalarType()->isIntegerTy(1))
1055 return IsDiv ? Op0 : Constant::getNullValue(Ty);
1056
1057 return nullptr;
1058}
1059
1060/// Given operands for an SDiv or UDiv, see if we can fold the result.
1061/// If not, this returns null.
1062static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
1063 const SimplifyQuery &Q, unsigned MaxRecurse) {
1064 if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1065 return C;
1066
1067 if (Value *V = simplifyDivRem(Op0, Op1, true))
1068 return V;
1069
1070 bool isSigned = Opcode == Instruction::SDiv;
1071
1072 // (X * Y) / Y -> X if the multiplication does not overflow.
1073 Value *X = nullptr, *Y = nullptr;
1074 if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) {
1075 if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1
1076 OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0);
1077 // If the Mul knows it does not overflow, then we are good to go.
1078 if ((isSigned && Mul->hasNoSignedWrap()) ||
1079 (!isSigned && Mul->hasNoUnsignedWrap()))
1080 return X;
1081 // If X has the form X = A / Y then X * Y cannot overflow.
1082 if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X))
1083 if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y)
1084 return X;
1085 }
1086
1087 // (X rem Y) / Y -> 0
1088 if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
1089 (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
1090 return Constant::getNullValue(Op0->getType());
1091
1092 // (X /u C1) /u C2 -> 0 if C1 * C2 overflow
1093 ConstantInt *C1, *C2;
1094 if (!isSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) &&
1095 match(Op1, m_ConstantInt(C2))) {
1096 bool Overflow;
1097 (void)C1->getValue().umul_ov(C2->getValue(), Overflow);
1098 if (Overflow)
1099 return Constant::getNullValue(Op0->getType());
1100 }
1101
1102 // If the operation is with the result of a select instruction, check whether
1103 // operating on either branch of the select always yields the same value.
1104 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1105 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1106 return V;
1107
1108 // If the operation is with the result of a phi instruction, check whether
1109 // operating on all incoming values of the phi always yields the same value.
1110 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1111 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1112 return V;
1113
1114 return nullptr;
1115}
1116
1117/// Given operands for an SDiv, see if we can fold the result.
1118/// If not, this returns null.
1119static Value *SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1120 unsigned MaxRecurse) {
1121 if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse))
1122 return V;
1123
1124 return nullptr;
1125}
1126
1127Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout &DL,
1128 const TargetLibraryInfo *TLI,
1129 const DominatorTree *DT, AssumptionCache *AC,
1130 const Instruction *CxtI) {
1131 return ::SimplifySDivInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
1132}
1133
1134Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1135 return ::SimplifySDivInst(Op0, Op1, Q, RecursionLimit);
1136}
1137
1138/// Given operands for a UDiv, see if we can fold the result.
1139/// If not, this returns null.
1140static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1141 unsigned MaxRecurse) {
1142 if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse))
1143 return V;
1144
1145 // udiv %V, C -> 0 if %V < C
1146 if (MaxRecurse) {
1147 if (Constant *C = dyn_cast_or_null<Constant>(SimplifyICmpInst(
1148 ICmpInst::ICMP_ULT, Op0, Op1, Q, MaxRecurse - 1))) {
1149 if (C->isAllOnesValue()) {
1150 return Constant::getNullValue(Op0->getType());
1151 }
1152 }
1153 }
1154
1155 return nullptr;
1156}
1157
1158Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout &DL,
1159 const TargetLibraryInfo *TLI,
1160 const DominatorTree *DT, AssumptionCache *AC,
1161 const Instruction *CxtI) {
1162 return ::SimplifyUDivInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
1163}
1164
1165Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1166 return ::SimplifyUDivInst(Op0, Op1, Q, RecursionLimit);
1167}
1168
1169static Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
1170 const SimplifyQuery &Q, unsigned) {
1171 if (Constant *C = foldOrCommuteConstant(Instruction::FDiv, Op0, Op1, Q))
1172 return C;
1173
1174 // undef / X -> undef (the undef could be a snan).
1175 if (match(Op0, m_Undef()))
1176 return Op0;
1177
1178 // X / undef -> undef
1179 if (match(Op1, m_Undef()))
1180 return Op1;
1181
1182 // X / 1.0 -> X
1183 if (match(Op1, m_FPOne()))
1184 return Op0;
1185
1186 // 0 / X -> 0
1187 // Requires that NaNs are off (X could be zero) and signed zeroes are
1188 // ignored (X could be positive or negative, so the output sign is unknown).
1189 if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero()))
1190 return Op0;
1191
1192 if (FMF.noNaNs()) {
1193 // X / X -> 1.0 is legal when NaNs are ignored.
1194 if (Op0 == Op1)
1195 return ConstantFP::get(Op0->getType(), 1.0);
1196
1197 // -X / X -> -1.0 and
1198 // X / -X -> -1.0 are legal when NaNs are ignored.
1199 // We can ignore signed zeros because +-0.0/+-0.0 is NaN and ignored.
1200 if ((BinaryOperator::isFNeg(Op0, /*IgnoreZeroSign=*/true) &&
1201 BinaryOperator::getFNegArgument(Op0) == Op1) ||
1202 (BinaryOperator::isFNeg(Op1, /*IgnoreZeroSign=*/true) &&
1203 BinaryOperator::getFNegArgument(Op1) == Op0))
1204 return ConstantFP::get(Op0->getType(), -1.0);
1205 }
1206
1207 return nullptr;
1208}
1209
1210Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
1211 const DataLayout &DL,
1212 const TargetLibraryInfo *TLI,
1213 const DominatorTree *DT, AssumptionCache *AC,
1214 const Instruction *CxtI) {
1215 return ::SimplifyFDivInst(Op0, Op1, FMF, {DL, TLI, DT, AC, CxtI},
1216 RecursionLimit);
1217}
1218
1219Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF,
1220 const SimplifyQuery &Q) {
1221 return ::SimplifyFDivInst(Op0, Op1, FMF, Q, RecursionLimit);
1222}
1223
1224/// Given operands for an SRem or URem, see if we can fold the result.
1225/// If not, this returns null.
1226static Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
1227 const SimplifyQuery &Q, unsigned MaxRecurse) {
1228 if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1229 return C;
1230
1231 if (Value *V = simplifyDivRem(Op0, Op1, false))
1232 return V;
1233
1234 // (X % Y) % Y -> X % Y
1235 if ((Opcode == Instruction::SRem &&
1236 match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
1237 (Opcode == Instruction::URem &&
1238 match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
1239 return Op0;
1240
1241 // If the operation is with the result of a select instruction, check whether
1242 // operating on either branch of the select always yields the same value.
1243 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1244 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1245 return V;
1246
1247 // If the operation is with the result of a phi instruction, check whether
1248 // operating on all incoming values of the phi always yields the same value.
1249 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1250 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1251 return V;
1252
1253 return nullptr;
1254}
1255
1256/// Given operands for an SRem, see if we can fold the result.
1257/// If not, this returns null.
1258static Value *SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1259 unsigned MaxRecurse) {
1260 if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse))
1261 return V;
1262
1263 return nullptr;
1264}
1265
1266Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout &DL,
1267 const TargetLibraryInfo *TLI,
1268 const DominatorTree *DT, AssumptionCache *AC,
1269 const Instruction *CxtI) {
1270 return ::SimplifySRemInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
1271}
1272
1273Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1274 return ::SimplifySRemInst(Op0, Op1, Q, RecursionLimit);
1275}
1276
1277/// Given operands for a URem, see if we can fold the result.
1278/// If not, this returns null.
1279static Value *SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1280 unsigned MaxRecurse) {
1281 if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse))
1282 return V;
1283
1284 // urem %V, C -> %V if %V < C
1285 if (MaxRecurse) {
1286 if (Constant *C = dyn_cast_or_null<Constant>(SimplifyICmpInst(
1287 ICmpInst::ICMP_ULT, Op0, Op1, Q, MaxRecurse - 1))) {
1288 if (C->isAllOnesValue()) {
1289 return Op0;
1290 }
1291 }
1292 }
1293
1294 return nullptr;
1295}
1296
1297Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout &DL,
1298 const TargetLibraryInfo *TLI,
1299 const DominatorTree *DT, AssumptionCache *AC,
1300 const Instruction *CxtI) {
1301 return ::SimplifyURemInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
1302}
1303
1304Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1305 return ::SimplifyURemInst(Op0, Op1, Q, RecursionLimit);
1306}
1307
1308static Value *SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
1309 const SimplifyQuery &Q, unsigned) {
1310 if (Constant *C = foldOrCommuteConstant(Instruction::FRem, Op0, Op1, Q))
1311 return C;
1312
1313 // undef % X -> undef (the undef could be a snan).
1314 if (match(Op0, m_Undef()))
1315 return Op0;
1316
1317 // X % undef -> undef
1318 if (match(Op1, m_Undef()))
1319 return Op1;
1320
1321 // 0 % X -> 0
1322 // Requires that NaNs are off (X could be zero) and signed zeroes are
1323 // ignored (X could be positive or negative, so the output sign is unknown).
1324 if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op0, m_AnyZero()))
1325 return Op0;
1326
1327 return nullptr;
1328}
1329
1330Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
1331 const DataLayout &DL,
1332 const TargetLibraryInfo *TLI,
1333 const DominatorTree *DT, AssumptionCache *AC,
1334 const Instruction *CxtI) {
1335 return ::SimplifyFRemInst(Op0, Op1, FMF, {DL, TLI, DT, AC, CxtI},
1336 RecursionLimit);
1337}
1338
1339Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, FastMathFlags FMF,
1340 const SimplifyQuery &Q) {
1341 return ::SimplifyFRemInst(Op0, Op1, FMF, Q, RecursionLimit);
1342}
1343
1344/// Returns true if a shift by \c Amount always yields undef.
1345static bool isUndefShift(Value *Amount) {
1346 Constant *C = dyn_cast<Constant>(Amount);
1347 if (!C)
1348 return false;
1349
1350 // X shift by undef -> undef because it may shift by the bitwidth.
1351 if (isa<UndefValue>(C))
1352 return true;
1353
1354 // Shifting by the bitwidth or more is undefined.
1355 if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
1356 if (CI->getValue().getLimitedValue() >=
1357 CI->getType()->getScalarSizeInBits())
1358 return true;
1359
1360 // If all lanes of a vector shift are undefined the whole shift is.
1361 if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) {
1362 for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I)
1363 if (!isUndefShift(C->getAggregateElement(I)))
1364 return false;
1365 return true;
1366 }
1367
1368 return false;
1369}
1370
1371/// Given operands for an Shl, LShr or AShr, see if we can fold the result.
1372/// If not, this returns null.
1373static Value *SimplifyShift(Instruction::BinaryOps Opcode, Value *Op0,
1374 Value *Op1, const SimplifyQuery &Q, unsigned MaxRecurse) {
1375 if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
1376 return C;
1377
1378 // 0 shift by X -> 0
1379 if (match(Op0, m_Zero()))
1380 return Op0;
1381
1382 // X shift by 0 -> X
1383 if (match(Op1, m_Zero()))
1384 return Op0;
1385
1386 // Fold undefined shifts.
1387 if (isUndefShift(Op1))
1388 return UndefValue::get(Op0->getType());
1389
1390 // If the operation is with the result of a select instruction, check whether
1391 // operating on either branch of the select always yields the same value.
1392 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1393 if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
1394 return V;
1395
1396 // If the operation is with the result of a phi instruction, check whether
1397 // operating on all incoming values of the phi always yields the same value.
1398 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1399 if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
1400 return V;
1401
1402 // If any bits in the shift amount make that value greater than or equal to
1403 // the number of bits in the type, the shift is undefined.
1404 unsigned BitWidth = Op1->getType()->getScalarSizeInBits();
1405 APInt KnownZero(BitWidth, 0);
1406 APInt KnownOne(BitWidth, 0);
1407 computeKnownBits(Op1, KnownZero, KnownOne, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1408 if (KnownOne.getLimitedValue() >= BitWidth)
1409 return UndefValue::get(Op0->getType());
1410
1411 // If all valid bits in the shift amount are known zero, the first operand is
1412 // unchanged.
1413 unsigned NumValidShiftBits = Log2_32_Ceil(BitWidth);
1414 if (KnownZero.countTrailingOnes() >= NumValidShiftBits)
1415 return Op0;
1416
1417 return nullptr;
1418}
1419
1420/// \brief Given operands for an Shl, LShr or AShr, see if we can
1421/// fold the result. If not, this returns null.
1422static Value *SimplifyRightShift(Instruction::BinaryOps Opcode, Value *Op0,
1423 Value *Op1, bool isExact, const SimplifyQuery &Q,
1424 unsigned MaxRecurse) {
1425 if (Value *V = SimplifyShift(Opcode, Op0, Op1, Q, MaxRecurse))
4
Assuming 'V' is null
5
Assuming pointer value is null
6
Taking false branch
1426 return V;
1427
1428 // X >> X -> 0
1429 if (Op0 == Op1)
7
Assuming 'Op0' is equal to 'Op1'
8
Taking true branch
1430 return Constant::getNullValue(Op0->getType());
9
Called C++ object pointer is null
1431
1432 // undef >> X -> 0
1433 // undef >> X -> undef (if it's exact)
1434 if (match(Op0, m_Undef()))
1435 return isExact ? Op0 : Constant::getNullValue(Op0->getType());
1436
1437 // The low bit cannot be shifted out of an exact shift if it is set.
1438 if (isExact) {
1439 unsigned BitWidth = Op0->getType()->getScalarSizeInBits();
1440 APInt Op0KnownZero(BitWidth, 0);
1441 APInt Op0KnownOne(BitWidth, 0);
1442 computeKnownBits(Op0, Op0KnownZero, Op0KnownOne, Q.DL, /*Depth=*/0, Q.AC,
1443 Q.CxtI, Q.DT);
1444 if (Op0KnownOne[0])
1445 return Op0;
1446 }
1447
1448 return nullptr;
1449}
1450
1451/// Given operands for an Shl, see if we can fold the result.
1452/// If not, this returns null.
1453static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1454 const SimplifyQuery &Q, unsigned MaxRecurse) {
1455 if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse))
1456 return V;
1457
1458 // undef << X -> 0
1459 // undef << X -> undef if (if it's NSW/NUW)
1460 if (match(Op0, m_Undef()))
1461 return isNSW || isNUW ? Op0 : Constant::getNullValue(Op0->getType());
1462
1463 // (X >> A) << A -> X
1464 Value *X;
1465 if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1)))))
1466 return X;
1467 return nullptr;
1468}
1469
1470Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1471 const DataLayout &DL, const TargetLibraryInfo *TLI,
1472 const DominatorTree *DT, AssumptionCache *AC,
1473 const Instruction *CxtI) {
1474 return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, {DL, TLI, DT, AC, CxtI},
1475 RecursionLimit);
1476}
1477
1478Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
1479 const SimplifyQuery &Q) {
1480 return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
1481}
1482
1483/// Given operands for an LShr, see if we can fold the result.
1484/// If not, this returns null.
1485static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1486 const SimplifyQuery &Q, unsigned MaxRecurse) {
1487 if (Value *V = SimplifyRightShift(Instruction::LShr, Op0, Op1, isExact, Q,
1488 MaxRecurse))
1489 return V;
1490
1491 // (X << A) >> A -> X
1492 Value *X;
1493 if (match(Op0, m_NUWShl(m_Value(X), m_Specific(Op1))))
1494 return X;
1495
1496 return nullptr;
1497}
1498
1499Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1500 const DataLayout &DL,
1501 const TargetLibraryInfo *TLI,
1502 const DominatorTree *DT, AssumptionCache *AC,
1503 const Instruction *CxtI) {
1504 return ::SimplifyLShrInst(Op0, Op1, isExact, {DL, TLI, DT, AC, CxtI},
1505 RecursionLimit);
1506}
1507
1508Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
1509 const SimplifyQuery &Q) {
1510 return ::SimplifyLShrInst(Op0, Op1, isExact, Q, RecursionLimit);
1511}
1512
1513/// Given operands for an AShr, see if we can fold the result.
1514/// If not, this returns null.
1515static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1516 const SimplifyQuery &Q, unsigned MaxRecurse) {
1517 if (Value *V = SimplifyRightShift(Instruction::AShr, Op0, Op1, isExact, Q,
2
Passing value via 2nd parameter 'Op0'
3
Calling 'SimplifyRightShift'
1518 MaxRecurse))
1519 return V;
1520
1521 // all ones >>a X -> all ones
1522 if (match(Op0, m_AllOnes()))
1523 return Op0;
1524
1525 // (X << A) >> A -> X
1526 Value *X;
1527 if (match(Op0, m_NSWShl(m_Value(X), m_Specific(Op1))))
1528 return X;
1529
1530 // Arithmetic shifting an all-sign-bit value is a no-op.
1531 unsigned NumSignBits = ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
1532 if (NumSignBits == Op0->getType()->getScalarSizeInBits())
1533 return Op0;
1534
1535 return nullptr;
1536}
1537
1538Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1539 const DataLayout &DL,
1540 const TargetLibraryInfo *TLI,
1541 const DominatorTree *DT, AssumptionCache *AC,
1542 const Instruction *CxtI) {
1543 return ::SimplifyAShrInst(Op0, Op1, isExact, {DL, TLI, DT, AC, CxtI},
1
Calling 'SimplifyAShrInst'
1544 RecursionLimit);
1545}
1546
1547Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
1548 const SimplifyQuery &Q) {
1549 return ::SimplifyAShrInst(Op0, Op1, isExact, Q, RecursionLimit);
1550}
1551
1552static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
1553 ICmpInst *UnsignedICmp, bool IsAnd) {
1554 Value *X, *Y;
1555
1556 ICmpInst::Predicate EqPred;
1557 if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) ||
1558 !ICmpInst::isEquality(EqPred))
1559 return nullptr;
1560
1561 ICmpInst::Predicate UnsignedPred;
1562 if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) &&
1563 ICmpInst::isUnsigned(UnsignedPred))
1564 ;
1565 else if (match(UnsignedICmp,
1566 m_ICmp(UnsignedPred, m_Value(Y), m_Specific(X))) &&
1567 ICmpInst::isUnsigned(UnsignedPred))
1568 UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
1569 else
1570 return nullptr;
1571
1572 // X < Y && Y != 0 --> X < Y
1573 // X < Y || Y != 0 --> Y != 0
1574 if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE)
1575 return IsAnd ? UnsignedICmp : ZeroICmp;
1576
1577 // X >= Y || Y != 0 --> true
1578 // X >= Y || Y == 0 --> X >= Y
1579 if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) {
1580 if (EqPred == ICmpInst::ICMP_NE)
1581 return getTrue(UnsignedICmp->getType());
1582 return UnsignedICmp;
1583 }
1584
1585 // X < Y && Y == 0 --> false
1586 if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ &&
1587 IsAnd)
1588 return getFalse(UnsignedICmp->getType());
1589
1590 return nullptr;
1591}
1592
1593/// Commuted variants are assumed to be handled by calling this function again
1594/// with the parameters swapped.
1595static Value *simplifyAndOfICmpsWithSameOperands(ICmpInst *Op0, ICmpInst *Op1) {
1596 ICmpInst::Predicate Pred0, Pred1;
1597 Value *A ,*B;
1598 if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) ||
1599 !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B))))
1600 return nullptr;
1601
1602 // We have (icmp Pred0, A, B) & (icmp Pred1, A, B).
1603 // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we
1604 // can eliminate Op1 from this 'and'.
1605 if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1))
1606 return Op0;
1607
1608 // Check for any combination of predicates that are guaranteed to be disjoint.
1609 if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) ||
1610 (Pred0 == ICmpInst::ICMP_EQ && ICmpInst::isFalseWhenEqual(Pred1)) ||
1611 (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT) ||
1612 (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT))
1613 return getFalse(Op0->getType());
1614
1615 return nullptr;
1616}
1617
1618/// Commuted variants are assumed to be handled by calling this function again
1619/// with the parameters swapped.
1620static Value *SimplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
1621 if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true))
1622 return X;
1623
1624 if (Value *X = simplifyAndOfICmpsWithSameOperands(Op0, Op1))
1625 return X;
1626
1627 // FIXME: This should be shared with or-of-icmps.
1628 // Look for this pattern: (icmp V, C0) & (icmp V, C1)).
1629 Type *ITy = Op0->getType();
1630 ICmpInst::Predicate Pred0, Pred1;
1631 const APInt *C0, *C1;
1632 Value *V;
1633 if (match(Op0, m_ICmp(Pred0, m_Value(V), m_APInt(C0))) &&
1634 match(Op1, m_ICmp(Pred1, m_Specific(V), m_APInt(C1)))) {
1635 // Make a constant range that's the intersection of the two icmp ranges.
1636 // If the intersection is empty, we know that the result is false.
1637 auto Range0 = ConstantRange::makeExactICmpRegion(Pred0, *C0);
1638 auto Range1 = ConstantRange::makeExactICmpRegion(Pred1, *C1);
1639 if (Range0.intersectWith(Range1).isEmptySet())
1640 return getFalse(ITy);
1641
1642 // If a range is a superset of the other, the smaller set is all we need.
1643 if (Range0.contains(Range1))
1644 return Op1;
1645 if (Range1.contains(Range0))
1646 return Op0;
1647 }
1648
1649 // (icmp (add V, C0), C1) & (icmp V, C0)
1650 if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1))))
1651 return nullptr;
1652
1653 if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value())))
1654 return nullptr;
1655
1656 auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
1657 if (AddInst->getOperand(1) != Op1->getOperand(1))
1658 return nullptr;
1659
1660 bool isNSW = AddInst->hasNoSignedWrap();
1661 bool isNUW = AddInst->hasNoUnsignedWrap();
1662
1663 const APInt Delta = *C1 - *C0;
1664 if (C0->isStrictlyPositive()) {
1665 if (Delta == 2) {
1666 if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_SGT)
1667 return getFalse(ITy);
1668 if (Pred0 == ICmpInst::ICMP_SLT && Pred1 == ICmpInst::ICMP_SGT && isNSW)
1669 return getFalse(ITy);
1670 }
1671 if (Delta == 1) {
1672 if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_SGT)
1673 return getFalse(ITy);
1674 if (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGT && isNSW)
1675 return getFalse(ITy);
1676 }
1677 }
1678 if (C0->getBoolValue() && isNUW) {
1679 if (Delta == 2)
1680 if (Pred0 == ICmpInst::ICMP_ULT && Pred1 == ICmpInst::ICMP_UGT)
1681 return getFalse(ITy);
1682 if (Delta == 1)
1683 if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT)
1684 return getFalse(ITy);
1685 }
1686
1687 return nullptr;
1688}
1689
1690/// Given operands for an And, see if we can fold the result.
1691/// If not, this returns null.
1692static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1693 unsigned MaxRecurse) {
1694 if (Constant *C = foldOrCommuteConstant(Instruction::And, Op0, Op1, Q))
1695 return C;
1696
1697 // X & undef -> 0
1698 if (match(Op1, m_Undef()))
1699 return Constant::getNullValue(Op0->getType());
1700
1701 // X & X = X
1702 if (Op0 == Op1)
1703 return Op0;
1704
1705 // X & 0 = 0
1706 if (match(Op1, m_Zero()))
1707 return Op1;
1708
1709 // X & -1 = X
1710 if (match(Op1, m_AllOnes()))
1711 return Op0;
1712
1713 // A & ~A = ~A & A = 0
1714 if (match(Op0, m_Not(m_Specific(Op1))) ||
1715 match(Op1, m_Not(m_Specific(Op0))))
1716 return Constant::getNullValue(Op0->getType());
1717
1718 // (A | ?) & A = A
1719 Value *A = nullptr, *B = nullptr;
1720 if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
1721 (A == Op1 || B == Op1))
1722 return Op1;
1723
1724 // A & (A | ?) = A
1725 if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
1726 (A == Op0 || B == Op0))
1727 return Op0;
1728
1729 // A & (-A) = A if A is a power of two or zero.
1730 if (match(Op0, m_Neg(m_Specific(Op1))) ||
1731 match(Op1, m_Neg(m_Specific(Op0)))) {
1732 if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
1733 Q.DT))
1734 return Op0;
1735 if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
1736 Q.DT))
1737 return Op1;
1738 }
1739
1740 if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) {
1741 if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) {
1742 if (Value *V = SimplifyAndOfICmps(ICILHS, ICIRHS))
1743 return V;
1744 if (Value *V = SimplifyAndOfICmps(ICIRHS, ICILHS))
1745 return V;
1746 }
1747 }
1748
1749 // The compares may be hidden behind casts. Look through those and try the
1750 // same folds as above.
1751 auto *Cast0 = dyn_cast<CastInst>(Op0);
1752 auto *Cast1 = dyn_cast<CastInst>(Op1);
1753 if (Cast0 && Cast1 && Cast0->getOpcode() == Cast1->getOpcode() &&
1754 Cast0->getSrcTy() == Cast1->getSrcTy()) {
1755 auto *Cmp0 = dyn_cast<ICmpInst>(Cast0->getOperand(0));
1756 auto *Cmp1 = dyn_cast<ICmpInst>(Cast1->getOperand(0));
1757 if (Cmp0 && Cmp1) {
1758 Instruction::CastOps CastOpc = Cast0->getOpcode();
1759 Type *ResultType = Cast0->getType();
1760 if (auto *V = dyn_cast_or_null<Constant>(SimplifyAndOfICmps(Cmp0, Cmp1)))
1761 return ConstantExpr::getCast(CastOpc, V, ResultType);
1762 if (auto *V = dyn_cast_or_null<Constant>(SimplifyAndOfICmps(Cmp1, Cmp0)))
1763 return ConstantExpr::getCast(CastOpc, V, ResultType);
1764 }
1765 }
1766
1767 // Try some generic simplifications for associative operations.
1768 if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q,
1769 MaxRecurse))
1770 return V;
1771
1772 // And distributes over Or. Try some generic simplifications based on this.
1773 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
1774 Q, MaxRecurse))
1775 return V;
1776
1777 // And distributes over Xor. Try some generic simplifications based on this.
1778 if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor,
1779 Q, MaxRecurse))
1780 return V;
1781
1782 // If the operation is with the result of a select instruction, check whether
1783 // operating on either branch of the select always yields the same value.
1784 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1785 if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q,
1786 MaxRecurse))
1787 return V;
1788
1789 // If the operation is with the result of a phi instruction, check whether
1790 // operating on all incoming values of the phi always yields the same value.
1791 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
1792 if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q,
1793 MaxRecurse))
1794 return V;
1795
1796 return nullptr;
1797}
1798
1799Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout &DL,
1800 const TargetLibraryInfo *TLI,
1801 const DominatorTree *DT, AssumptionCache *AC,
1802 const Instruction *CxtI) {
1803 return ::SimplifyAndInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
1804}
1805
1806Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
1807 return ::SimplifyAndInst(Op0, Op1, Q, RecursionLimit);
1808}
1809
1810/// Commuted variants are assumed to be handled by calling this function again
1811/// with the parameters swapped.
1812static Value *simplifyOrOfICmpsWithSameOperands(ICmpInst *Op0, ICmpInst *Op1) {
1813 ICmpInst::Predicate Pred0, Pred1;
1814 Value *A ,*B;
1815 if (!match(Op0, m_ICmp(Pred0, m_Value(A), m_Value(B))) ||
1816 !match(Op1, m_ICmp(Pred1, m_Specific(A), m_Specific(B))))
1817 return nullptr;
1818
1819 // We have (icmp Pred0, A, B) | (icmp Pred1, A, B).
1820 // If Op1 is always implied true by Op0, then Op0 is a subset of Op1, and we
1821 // can eliminate Op0 from this 'or'.
1822 if (ICmpInst::isImpliedTrueByMatchingCmp(Pred0, Pred1))
1823 return Op1;
1824
1825 // Check for any combination of predicates that cover the entire range of
1826 // possibilities.
1827 if ((Pred0 == ICmpInst::getInversePredicate(Pred1)) ||
1828 (Pred0 == ICmpInst::ICMP_NE && ICmpInst::isTrueWhenEqual(Pred1)) ||
1829 (Pred0 == ICmpInst::ICMP_SLE && Pred1 == ICmpInst::ICMP_SGE) ||
1830 (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGE))
1831 return getTrue(Op0->getType());
1832
1833 return nullptr;
1834}
1835
1836/// Commuted variants are assumed to be handled by calling this function again
1837/// with the parameters swapped.
1838static Value *SimplifyOrOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
1839 if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false))
1840 return X;
1841
1842 if (Value *X = simplifyOrOfICmpsWithSameOperands(Op0, Op1))
1843 return X;
1844
1845 // (icmp (add V, C0), C1) | (icmp V, C0)
1846 ICmpInst::Predicate Pred0, Pred1;
1847 const APInt *C0, *C1;
1848 Value *V;
1849 if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_APInt(C0)), m_APInt(C1))))
1850 return nullptr;
1851
1852 if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Value())))
1853 return nullptr;
1854
1855 auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
1856 if (AddInst->getOperand(1) != Op1->getOperand(1))
1857 return nullptr;
1858
1859 Type *ITy = Op0->getType();
1860 bool isNSW = AddInst->hasNoSignedWrap();
1861 bool isNUW = AddInst->hasNoUnsignedWrap();
1862
1863 const APInt Delta = *C1 - *C0;
1864 if (C0->isStrictlyPositive()) {
1865 if (Delta == 2) {
1866 if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_SLE)
1867 return getTrue(ITy);
1868 if (Pred0 == ICmpInst::ICMP_SGE && Pred1 == ICmpInst::ICMP_SLE && isNSW)
1869 return getTrue(ITy);
1870 }
1871 if (Delta == 1) {
1872 if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_SLE)
1873 return getTrue(ITy);
1874 if (Pred0 == ICmpInst::ICMP_SGT && Pred1 == ICmpInst::ICMP_SLE && isNSW)
1875 return getTrue(ITy);
1876 }
1877 }
1878 if (C0->getBoolValue() && isNUW) {
1879 if (Delta == 2)
1880 if (Pred0 == ICmpInst::ICMP_UGE && Pred1 == ICmpInst::ICMP_ULE)
1881 return getTrue(ITy);
1882 if (Delta == 1)
1883 if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE)
1884 return getTrue(ITy);
1885 }
1886
1887 return nullptr;
1888}
1889
1890/// Given operands for an Or, see if we can fold the result.
1891/// If not, this returns null.
1892static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
1893 unsigned MaxRecurse) {
1894 if (Constant *C = foldOrCommuteConstant(Instruction::Or, Op0, Op1, Q))
1895 return C;
1896
1897 // X | undef -> -1
1898 if (match(Op1, m_Undef()))
1899 return Constant::getAllOnesValue(Op0->getType());
1900
1901 // X | X = X
1902 if (Op0 == Op1)
1903 return Op0;
1904
1905 // X | 0 = X
1906 if (match(Op1, m_Zero()))
1907 return Op0;
1908
1909 // X | -1 = -1
1910 if (match(Op1, m_AllOnes()))
1911 return Op1;
1912
1913 // A | ~A = ~A | A = -1
1914 if (match(Op0, m_Not(m_Specific(Op1))) ||
1915 match(Op1, m_Not(m_Specific(Op0))))
1916 return Constant::getAllOnesValue(Op0->getType());
1917
1918 // (A & ?) | A = A
1919 Value *A = nullptr, *B = nullptr;
1920 if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
1921 (A == Op1 || B == Op1))
1922 return Op1;
1923
1924 // A | (A & ?) = A
1925 if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
1926 (A == Op0 || B == Op0))
1927 return Op0;
1928
1929 // ~(A & ?) | A = -1
1930 if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) &&
1931 (A == Op1 || B == Op1))
1932 return Constant::getAllOnesValue(Op1->getType());
1933
1934 // A | ~(A & ?) = -1
1935 if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) &&
1936 (A == Op0 || B == Op0))
1937 return Constant::getAllOnesValue(Op0->getType());
1938
1939 // (A & ~B) | (A ^ B) -> (A ^ B)
1940 // (~B & A) | (A ^ B) -> (A ^ B)
1941 // (A & ~B) | (B ^ A) -> (B ^ A)
1942 // (~B & A) | (B ^ A) -> (B ^ A)
1943 if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
1944 (match(Op0, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
1945 match(Op0, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
1946 return Op1;
1947
1948 // Commute the 'or' operands.
1949 // (A ^ B) | (A & ~B) -> (A ^ B)
1950 // (A ^ B) | (~B & A) -> (A ^ B)
1951 // (B ^ A) | (A & ~B) -> (B ^ A)
1952 // (B ^ A) | (~B & A) -> (B ^ A)
1953 if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
1954 (match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
1955 match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
1956 return Op0;
1957
1958 if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) {
1959 if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) {
1960 if (Value *V = SimplifyOrOfICmps(ICILHS, ICIRHS))
1961 return V;
1962 if (Value *V = SimplifyOrOfICmps(ICIRHS, ICILHS))
1963 return V;
1964 }
1965 }
1966
1967 // Try some generic simplifications for associative operations.
1968 if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q,
1969 MaxRecurse))
1970 return V;
1971
1972 // Or distributes over And. Try some generic simplifications based on this.
1973 if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q,
1974 MaxRecurse))
1975 return V;
1976
1977 // If the operation is with the result of a select instruction, check whether
1978 // operating on either branch of the select always yields the same value.
1979 if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
1980 if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q,
1981 MaxRecurse))
1982 return V;
1983
1984 // (A & C)|(B & D)
1985 Value *C = nullptr, *D = nullptr;
1986 if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
1987 match(Op1, m_And(m_Value(B), m_Value(D)))) {
1988 ConstantInt *C1 = dyn_cast<ConstantInt>(C);
1989 ConstantInt *C2 = dyn_cast<ConstantInt>(D);
1990 if (C1 && C2 && (C1->getValue() == ~C2->getValue())) {
1991 // (A & C1)|(B & C2)
1992 // If we have: ((V + N) & C1) | (V & C2)
1993 // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0
1994 // replace with V+N.
1995 Value *V1, *V2;
1996 if ((C2->getValue() & (C2->getValue() + 1)) == 0 && // C2 == 0+1+
1997 match(A, m_Add(m_Value(V1), m_Value(V2)))) {
1998 // Add commutes, try both ways.
1999 if (V1 == B &&
2000 MaskedValueIsZero(V2, C2->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2001 return A;
2002 if (V2 == B &&
2003 MaskedValueIsZero(V1, C2->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2004 return A;
2005 }
2006 // Or commutes, try both ways.
2007 if ((C1->getValue() & (C1->getValue() + 1)) == 0 &&
2008 match(B, m_Add(m_Value(V1), m_Value(V2)))) {
2009 // Add commutes, try both ways.
2010 if (V1 == A &&
2011 MaskedValueIsZero(V2, C1->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2012 return B;
2013 if (V2 == A &&
2014 MaskedValueIsZero(V1, C1->getValue(), Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2015 return B;
2016 }
2017 }
2018 }
2019
2020 // If the operation is with the result of a phi instruction, check whether
2021 // operating on all incoming values of the phi always yields the same value.
2022 if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
2023 if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse))
2024 return V;
2025
2026 return nullptr;
2027}
2028
2029Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout &DL,
2030 const TargetLibraryInfo *TLI,
2031 const DominatorTree *DT, AssumptionCache *AC,
2032 const Instruction *CxtI) {
2033 return ::SimplifyOrInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
2034}
2035
2036Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
2037 return ::SimplifyOrInst(Op0, Op1, Q, RecursionLimit);
2038}
2039
2040/// Given operands for a Xor, see if we can fold the result.
2041/// If not, this returns null.
2042static Value *SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
2043 unsigned MaxRecurse) {
2044 if (Constant *C = foldOrCommuteConstant(Instruction::Xor, Op0, Op1, Q))
2045 return C;
2046
2047 // A ^ undef -> undef
2048 if (match(Op1, m_Undef()))
2049 return Op1;
2050
2051 // A ^ 0 = A
2052 if (match(Op1, m_Zero()))
2053 return Op0;
2054
2055 // A ^ A = 0
2056 if (Op0 == Op1)
2057 return Constant::getNullValue(Op0->getType());
2058
2059 // A ^ ~A = ~A ^ A = -1
2060 if (match(Op0, m_Not(m_Specific(Op1))) ||
2061 match(Op1, m_Not(m_Specific(Op0))))
2062 return Constant::getAllOnesValue(Op0->getType());
2063
2064 // Try some generic simplifications for associative operations.
2065 if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q,
2066 MaxRecurse))
2067 return V;
2068
2069 // Threading Xor over selects and phi nodes is pointless, so don't bother.
2070 // Threading over the select in "A ^ select(cond, B, C)" means evaluating
2071 // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
2072 // only if B and C are equal. If B and C are equal then (since we assume
2073 // that operands have already been simplified) "select(cond, B, C)" should
2074 // have been simplified to the common value of B and C already. Analysing
2075 // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly
2076 // for threading over phi nodes.
2077
2078 return nullptr;
2079}
2080
2081Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout &DL,
2082 const TargetLibraryInfo *TLI,
2083 const DominatorTree *DT, AssumptionCache *AC,
2084 const Instruction *CxtI) {
2085 return ::SimplifyXorInst(Op0, Op1, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
2086}
2087
2088Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
2089 return ::SimplifyXorInst(Op0, Op1, Q, RecursionLimit);
2090}
2091
2092
2093static Type *GetCompareTy(Value *Op) {
2094 return CmpInst::makeCmpResultType(Op->getType());
2095}
2096
2097/// Rummage around inside V looking for something equivalent to the comparison
2098/// "LHS Pred RHS". Return such a value if found, otherwise return null.
2099/// Helper function for analyzing max/min idioms.
2100static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred,
2101 Value *LHS, Value *RHS) {
2102 SelectInst *SI = dyn_cast<SelectInst>(V);
2103 if (!SI)
2104 return nullptr;
2105 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
2106 if (!Cmp)
2107 return nullptr;
2108 Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1);
2109 if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS)
2110 return Cmp;
2111 if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) &&
2112 LHS == CmpRHS && RHS == CmpLHS)
2113 return Cmp;
2114 return nullptr;
2115}
2116
2117// A significant optimization not implemented here is assuming that alloca
2118// addresses are not equal to incoming argument values. They don't *alias*,
2119// as we say, but that doesn't mean they aren't equal, so we take a
2120// conservative approach.
2121//
2122// This is inspired in part by C++11 5.10p1:
2123// "Two pointers of the same type compare equal if and only if they are both
2124// null, both point to the same function, or both represent the same
2125// address."
2126//
2127// This is pretty permissive.
2128//
2129// It's also partly due to C11 6.5.9p6:
2130// "Two pointers compare equal if and only if both are null pointers, both are
2131// pointers to the same object (including a pointer to an object and a
2132// subobject at its beginning) or function, both are pointers to one past the
2133// last element of the same array object, or one is a pointer to one past the
2134// end of one array object and the other is a pointer to the start of a
2135// different array object that happens to immediately follow the first array
2136// object in the address space.)
2137//
2138// C11's version is more restrictive, however there's no reason why an argument
2139// couldn't be a one-past-the-end value for a stack object in the caller and be
2140// equal to the beginning of a stack object in the callee.
2141//
2142// If the C and C++ standards are ever made sufficiently restrictive in this
2143// area, it may be possible to update LLVM's semantics accordingly and reinstate
2144// this optimization.
2145static Constant *
2146computePointerICmp(const DataLayout &DL, const TargetLibraryInfo *TLI,
2147 const DominatorTree *DT, CmpInst::Predicate Pred,
2148 const Instruction *CxtI, Value *LHS, Value *RHS) {
2149 // First, skip past any trivial no-ops.
2150 LHS = LHS->stripPointerCasts();
2151 RHS = RHS->stripPointerCasts();
2152
2153 // A non-null pointer is not equal to a null pointer.
2154 if (llvm::isKnownNonNull(LHS) && isa<ConstantPointerNull>(RHS) &&
2155 (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE))
2156 return ConstantInt::get(GetCompareTy(LHS),
2157 !CmpInst::isTrueWhenEqual(Pred));
2158
2159 // We can only fold certain predicates on pointer comparisons.
2160 switch (Pred) {
2161 default:
2162 return nullptr;
2163
2164 // Equality comaprisons are easy to fold.
2165 case CmpInst::ICMP_EQ:
2166 case CmpInst::ICMP_NE:
2167 break;
2168
2169 // We can only handle unsigned relational comparisons because 'inbounds' on
2170 // a GEP only protects against unsigned wrapping.
2171 case CmpInst::ICMP_UGT:
2172 case CmpInst::ICMP_UGE:
2173 case CmpInst::ICMP_ULT:
2174 case CmpInst::ICMP_ULE:
2175 // However, we have to switch them to their signed variants to handle
2176 // negative indices from the base pointer.
2177 Pred = ICmpInst::getSignedPredicate(Pred);
2178 break;
2179 }
2180
2181 // Strip off any constant offsets so that we can reason about them.
2182 // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets
2183 // here and compare base addresses like AliasAnalysis does, however there are
2184 // numerous hazards. AliasAnalysis and its utilities rely on special rules
2185 // governing loads and stores which don't apply to icmps. Also, AliasAnalysis
2186 // doesn't need to guarantee pointer inequality when it says NoAlias.
2187 Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
2188 Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
2189
2190 // If LHS and RHS are related via constant offsets to the same base
2191 // value, we can replace it with an icmp which just compares the offsets.
2192 if (LHS == RHS)
2193 return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset);
2194
2195 // Various optimizations for (in)equality comparisons.
2196 if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {
2197 // Different non-empty allocations that exist at the same time have
2198 // different addresses (if the program can tell). Global variables always
2199 // exist, so they always exist during the lifetime of each other and all
2200 // allocas. Two different allocas usually have different addresses...
2201 //
2202 // However, if there's an @llvm.stackrestore dynamically in between two
2203 // allocas, they may have the same address. It's tempting to reduce the
2204 // scope of the problem by only looking at *static* allocas here. That would
2205 // cover the majority of allocas while significantly reducing the likelihood
2206 // of having an @llvm.stackrestore pop up in the middle. However, it's not
2207 // actually impossible for an @llvm.stackrestore to pop up in the middle of
2208 // an entry block. Also, if we have a block that's not attached to a
2209 // function, we can't tell if it's "static" under the current definition.
2210 // Theoretically, this problem could be fixed by creating a new kind of
2211 // instruction kind specifically for static allocas. Such a new instruction
2212 // could be required to be at the top of the entry block, thus preventing it
2213 // from being subject to a @llvm.stackrestore. Instcombine could even
2214 // convert regular allocas into these special allocas. It'd be nifty.
2215 // However, until then, this problem remains open.
2216 //
2217 // So, we'll assume that two non-empty allocas have different addresses
2218 // for now.
2219 //
2220 // With all that, if the offsets are within the bounds of their allocations
2221 // (and not one-past-the-end! so we can't use inbounds!), and their
2222 // allocations aren't the same, the pointers are not equal.
2223 //
2224 // Note that it's not necessary to check for LHS being a global variable
2225 // address, due to canonicalization and constant folding.
2226 if (isa<AllocaInst>(LHS) &&
2227 (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) {
2228 ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset);
2229 ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(RHSOffset);
2230 uint64_t LHSSize, RHSSize;
2231 if (LHSOffsetCI && RHSOffsetCI &&
2232 getObjectSize(LHS, LHSSize, DL, TLI) &&
2233 getObjectSize(RHS, RHSSize, DL, TLI)) {
2234 const APInt &LHSOffsetValue = LHSOffsetCI->getValue();
2235 const APInt &RHSOffsetValue = RHSOffsetCI->getValue();
2236 if (!LHSOffsetValue.isNegative() &&
2237 !RHSOffsetValue.isNegative() &&
2238 LHSOffsetValue.ult(LHSSize) &&
2239 RHSOffsetValue.ult(RHSSize)) {
2240 return ConstantInt::get(GetCompareTy(LHS),
2241 !CmpInst::isTrueWhenEqual(Pred));
2242 }
2243 }
2244
2245 // Repeat the above check but this time without depending on DataLayout
2246 // or being able to compute a precise size.
2247 if (!cast<PointerType>(LHS->getType())->isEmptyTy() &&
2248 !cast<PointerType>(RHS->getType())->isEmptyTy() &&
2249 LHSOffset->isNullValue() &&
2250 RHSOffset->isNullValue())
2251 return ConstantInt::get(GetCompareTy(LHS),
2252 !CmpInst::isTrueWhenEqual(Pred));
2253 }
2254
2255 // Even if an non-inbounds GEP occurs along the path we can still optimize
2256 // equality comparisons concerning the result. We avoid walking the whole
2257 // chain again by starting where the last calls to
2258 // stripAndComputeConstantOffsets left off and accumulate the offsets.
2259 Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true);
2260 Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true);
2261 if (LHS == RHS)
2262 return ConstantExpr::getICmp(Pred,
2263 ConstantExpr::getAdd(LHSOffset, LHSNoBound),
2264 ConstantExpr::getAdd(RHSOffset, RHSNoBound));
2265
2266 // If one side of the equality comparison must come from a noalias call
2267 // (meaning a system memory allocation function), and the other side must
2268 // come from a pointer that cannot overlap with dynamically-allocated
2269 // memory within the lifetime of the current function (allocas, byval
2270 // arguments, globals), then determine the comparison result here.
2271 SmallVector<Value *, 8> LHSUObjs, RHSUObjs;
2272 GetUnderlyingObjects(LHS, LHSUObjs, DL);
2273 GetUnderlyingObjects(RHS, RHSUObjs, DL);
2274
2275 // Is the set of underlying objects all noalias calls?
2276 auto IsNAC = [](ArrayRef<Value *> Objects) {
2277 return all_of(Objects, isNoAliasCall);
2278 };
2279
2280 // Is the set of underlying objects all things which must be disjoint from
2281 // noalias calls. For allocas, we consider only static ones (dynamic
2282 // allocas might be transformed into calls to malloc not simultaneously
2283 // live with the compared-to allocation). For globals, we exclude symbols
2284 // that might be resolve lazily to symbols in another dynamically-loaded
2285 // library (and, thus, could be malloc'ed by the implementation).
2286 auto IsAllocDisjoint = [](ArrayRef<Value *> Objects) {
2287 return all_of(Objects, [](Value *V) {
2288 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
2289 return AI->getParent() && AI->getFunction() && AI->isStaticAlloca();
2290 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
2291 return (GV->hasLocalLinkage() || GV->hasHiddenVisibility() ||
2292 GV->hasProtectedVisibility() || GV->hasGlobalUnnamedAddr()) &&
2293 !GV->isThreadLocal();
2294 if (const Argument *A = dyn_cast<Argument>(V))
2295 return A->hasByValAttr();
2296 return false;
2297 });
2298 };
2299
2300 if ((IsNAC(LHSUObjs) && IsAllocDisjoint(RHSUObjs)) ||
2301 (IsNAC(RHSUObjs) && IsAllocDisjoint(LHSUObjs)))
2302 return ConstantInt::get(GetCompareTy(LHS),
2303 !CmpInst::isTrueWhenEqual(Pred));
2304
2305 // Fold comparisons for non-escaping pointer even if the allocation call
2306 // cannot be elided. We cannot fold malloc comparison to null. Also, the
2307 // dynamic allocation call could be either of the operands.
2308 Value *MI = nullptr;
2309 if (isAllocLikeFn(LHS, TLI) && llvm::isKnownNonNullAt(RHS, CxtI, DT))
2310 MI = LHS;
2311 else if (isAllocLikeFn(RHS, TLI) && llvm::isKnownNonNullAt(LHS, CxtI, DT))
2312 MI = RHS;
2313 // FIXME: We should also fold the compare when the pointer escapes, but the
2314 // compare dominates the pointer escape
2315 if (MI && !PointerMayBeCaptured(MI, true, true))
2316 return ConstantInt::get(GetCompareTy(LHS),
2317 CmpInst::isFalseWhenEqual(Pred));
2318 }
2319
2320 // Otherwise, fail.
2321 return nullptr;
2322}
2323
2324/// Fold an icmp when its operands have i1 scalar type.
2325static Value *simplifyICmpOfBools(CmpInst::Predicate Pred, Value *LHS,
2326 Value *RHS, const SimplifyQuery &Q) {
2327 Type *ITy = GetCompareTy(LHS); // The return type.
2328 Type *OpTy = LHS->getType(); // The operand type.
2329 if (!OpTy->getScalarType()->isIntegerTy(1))
2330 return nullptr;
2331
2332 switch (Pred) {
2333 default:
2334 break;
2335 case ICmpInst::ICMP_EQ:
2336 // X == 1 -> X
2337 if (match(RHS, m_One()))
2338 return LHS;
2339 break;
2340 case ICmpInst::ICMP_NE:
2341 // X != 0 -> X
2342 if (match(RHS, m_Zero()))
2343 return LHS;
2344 break;
2345 case ICmpInst::ICMP_UGT:
2346 // X >u 0 -> X
2347 if (match(RHS, m_Zero()))
2348 return LHS;
2349 break;
2350 case ICmpInst::ICMP_UGE:
2351 // X >=u 1 -> X
2352 if (match(RHS, m_One()))
2353 return LHS;
2354 if (isImpliedCondition(RHS, LHS, Q.DL).getValueOr(false))
2355 return getTrue(ITy);
2356 break;
2357 case ICmpInst::ICMP_SGE:
2358 /// For signed comparison, the values for an i1 are 0 and -1
2359 /// respectively. This maps into a truth table of:
2360 /// LHS | RHS | LHS >=s RHS | LHS implies RHS
2361 /// 0 | 0 | 1 (0 >= 0) | 1
2362 /// 0 | 1 | 1 (0 >= -1) | 1
2363 /// 1 | 0 | 0 (-1 >= 0) | 0
2364 /// 1 | 1 | 1 (-1 >= -1) | 1
2365 if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false))
2366 return getTrue(ITy);
2367 break;
2368 case ICmpInst::ICMP_SLT:
2369 // X <s 0 -> X
2370 if (match(RHS, m_Zero()))
2371 return LHS;
2372 break;
2373 case ICmpInst::ICMP_SLE:
2374 // X <=s -1 -> X
2375 if (match(RHS, m_One()))
2376 return LHS;
2377 break;
2378 case ICmpInst::ICMP_ULE:
2379 if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false))
2380 return getTrue(ITy);
2381 break;
2382 }
2383
2384 return nullptr;
2385}
2386
2387/// Try hard to fold icmp with zero RHS because this is a common case.
2388static Value *simplifyICmpWithZero(CmpInst::Predicate Pred, Value *LHS,
2389 Value *RHS, const SimplifyQuery &Q) {
2390 if (!match(RHS, m_Zero()))
2391 return nullptr;
2392
2393 Type *ITy = GetCompareTy(LHS); // The return type.
2394 bool LHSKnownNonNegative, LHSKnownNegative;
2395 switch (Pred) {
2396 default:
2397 llvm_unreachable("Unknown ICmp predicate!")::llvm::llvm_unreachable_internal("Unknown ICmp predicate!", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 2397)
;
2398 case ICmpInst::ICMP_ULT:
2399 return getFalse(ITy);
2400 case ICmpInst::ICMP_UGE:
2401 return getTrue(ITy);
2402 case ICmpInst::ICMP_EQ:
2403 case ICmpInst::ICMP_ULE:
2404 if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2405 return getFalse(ITy);
2406 break;
2407 case ICmpInst::ICMP_NE:
2408 case ICmpInst::ICMP_UGT:
2409 if (isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2410 return getTrue(ITy);
2411 break;
2412 case ICmpInst::ICMP_SLT:
2413 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC,
2414 Q.CxtI, Q.DT);
2415 if (LHSKnownNegative)
2416 return getTrue(ITy);
2417 if (LHSKnownNonNegative)
2418 return getFalse(ITy);
2419 break;
2420 case ICmpInst::ICMP_SLE:
2421 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC,
2422 Q.CxtI, Q.DT);
2423 if (LHSKnownNegative)
2424 return getTrue(ITy);
2425 if (LHSKnownNonNegative && isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2426 return getFalse(ITy);
2427 break;
2428 case ICmpInst::ICMP_SGE:
2429 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC,
2430 Q.CxtI, Q.DT);
2431 if (LHSKnownNegative)
2432 return getFalse(ITy);
2433 if (LHSKnownNonNegative)
2434 return getTrue(ITy);
2435 break;
2436 case ICmpInst::ICMP_SGT:
2437 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0, Q.AC,
2438 Q.CxtI, Q.DT);
2439 if (LHSKnownNegative)
2440 return getFalse(ITy);
2441 if (LHSKnownNonNegative && isKnownNonZero(LHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
2442 return getTrue(ITy);
2443 break;
2444 }
2445
2446 return nullptr;
2447}
2448
2449/// Many binary operators with a constant operand have an easy-to-compute
2450/// range of outputs. This can be used to fold a comparison to always true or
2451/// always false.
2452static void setLimitsForBinOp(BinaryOperator &BO, APInt &Lower, APInt &Upper) {
2453 unsigned Width = Lower.getBitWidth();
2454 const APInt *C;
2455 switch (BO.getOpcode()) {
2456 case Instruction::Add:
2457 if (match(BO.getOperand(1), m_APInt(C)) && *C != 0) {
2458 // FIXME: If we have both nuw and nsw, we should reduce the range further.
2459 if (BO.hasNoUnsignedWrap()) {
2460 // 'add nuw x, C' produces [C, UINT_MAX].
2461 Lower = *C;
2462 } else if (BO.hasNoSignedWrap()) {
2463 if (C->isNegative()) {
2464 // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C].
2465 Lower = APInt::getSignedMinValue(Width);
2466 Upper = APInt::getSignedMaxValue(Width) + *C + 1;
2467 } else {
2468 // 'add nsw x, +C' produces [SINT_MIN + C, SINT_MAX].
2469 Lower = APInt::getSignedMinValue(Width) + *C;
2470 Upper = APInt::getSignedMaxValue(Width) + 1;
2471 }
2472 }
2473 }
2474 break;
2475
2476 case Instruction::And:
2477 if (match(BO.getOperand(1), m_APInt(C)))
2478 // 'and x, C' produces [0, C].
2479 Upper = *C + 1;
2480 break;
2481
2482 case Instruction::Or:
2483 if (match(BO.getOperand(1), m_APInt(C)))
2484 // 'or x, C' produces [C, UINT_MAX].
2485 Lower = *C;
2486 break;
2487
2488 case Instruction::AShr:
2489 if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
2490 // 'ashr x, C' produces [INT_MIN >> C, INT_MAX >> C].
2491 Lower = APInt::getSignedMinValue(Width).ashr(*C);
2492 Upper = APInt::getSignedMaxValue(Width).ashr(*C) + 1;
2493 } else if (match(BO.getOperand(0), m_APInt(C))) {
2494 unsigned ShiftAmount = Width - 1;
2495 if (*C != 0 && BO.isExact())
2496 ShiftAmount = C->countTrailingZeros();
2497 if (C->isNegative()) {
2498 // 'ashr C, x' produces [C, C >> (Width-1)]
2499 Lower = *C;
2500 Upper = C->ashr(ShiftAmount) + 1;
2501 } else {
2502 // 'ashr C, x' produces [C >> (Width-1), C]
2503 Lower = C->ashr(ShiftAmount);
2504 Upper = *C + 1;
2505 }
2506 }
2507 break;
2508
2509 case Instruction::LShr:
2510 if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
2511 // 'lshr x, C' produces [0, UINT_MAX >> C].
2512 Upper = APInt::getAllOnesValue(Width).lshr(*C) + 1;
2513 } else if (match(BO.getOperand(0), m_APInt(C))) {
2514 // 'lshr C, x' produces [C >> (Width-1), C].
2515 unsigned ShiftAmount = Width - 1;
2516 if (*C != 0 && BO.isExact())
2517 ShiftAmount = C->countTrailingZeros();
2518 Lower = C->lshr(ShiftAmount);
2519 Upper = *C + 1;
2520 }
2521 break;
2522
2523 case Instruction::Shl:
2524 if (match(BO.getOperand(0), m_APInt(C))) {
2525 if (BO.hasNoUnsignedWrap()) {
2526 // 'shl nuw C, x' produces [C, C << CLZ(C)]
2527 Lower = *C;
2528 Upper = Lower.shl(Lower.countLeadingZeros()) + 1;
2529 } else if (BO.hasNoSignedWrap()) { // TODO: What if both nuw+nsw?
2530 if (C->isNegative()) {
2531 // 'shl nsw C, x' produces [C << CLO(C)-1, C]
2532 unsigned ShiftAmount = C->countLeadingOnes() - 1;
2533 Lower = C->shl(ShiftAmount);
2534 Upper = *C + 1;
2535 } else {
2536 // 'shl nsw C, x' produces [C, C << CLZ(C)-1]
2537 unsigned ShiftAmount = C->countLeadingZeros() - 1;
2538 Lower = *C;
2539 Upper = C->shl(ShiftAmount) + 1;
2540 }
2541 }
2542 }
2543 break;
2544
2545 case Instruction::SDiv:
2546 if (match(BO.getOperand(1), m_APInt(C))) {
2547 APInt IntMin = APInt::getSignedMinValue(Width);
2548 APInt IntMax = APInt::getSignedMaxValue(Width);
2549 if (C->isAllOnesValue()) {
2550 // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX]
2551 // where C != -1 and C != 0 and C != 1
2552 Lower = IntMin + 1;
2553 Upper = IntMax + 1;
2554 } else if (C->countLeadingZeros() < Width - 1) {
2555 // 'sdiv x, C' produces [INT_MIN / C, INT_MAX / C]
2556 // where C != -1 and C != 0 and C != 1
2557 Lower = IntMin.sdiv(*C);
2558 Upper = IntMax.sdiv(*C);
2559 if (Lower.sgt(Upper))
2560 std::swap(Lower, Upper);
2561 Upper = Upper + 1;
2562 assert(Upper != Lower && "Upper part of range has wrapped!")((Upper != Lower && "Upper part of range has wrapped!"
) ? static_cast<void> (0) : __assert_fail ("Upper != Lower && \"Upper part of range has wrapped!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 2562, __PRETTY_FUNCTION__))
;
2563 }
2564 } else if (match(BO.getOperand(0), m_APInt(C))) {
2565 if (C->isMinSignedValue()) {
2566 // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2].
2567 Lower = *C;
2568 Upper = Lower.lshr(1) + 1;
2569 } else {
2570 // 'sdiv C, x' produces [-|C|, |C|].
2571 Upper = C->abs() + 1;
2572 Lower = (-Upper) + 1;
2573 }
2574 }
2575 break;
2576
2577 case Instruction::UDiv:
2578 if (match(BO.getOperand(1), m_APInt(C)) && *C != 0) {
2579 // 'udiv x, C' produces [0, UINT_MAX / C].
2580 Upper = APInt::getMaxValue(Width).udiv(*C) + 1;
2581 } else if (match(BO.getOperand(0), m_APInt(C))) {
2582 // 'udiv C, x' produces [0, C].
2583 Upper = *C + 1;
2584 }
2585 break;
2586
2587 case Instruction::SRem:
2588 if (match(BO.getOperand(1), m_APInt(C))) {
2589 // 'srem x, C' produces (-|C|, |C|).
2590 Upper = C->abs();
2591 Lower = (-Upper) + 1;
2592 }
2593 break;
2594
2595 case Instruction::URem:
2596 if (match(BO.getOperand(1), m_APInt(C)))
2597 // 'urem x, C' produces [0, C).
2598 Upper = *C;
2599 break;
2600
2601 default:
2602 break;
2603 }
2604}
2605
2606static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS,
2607 Value *RHS) {
2608 const APInt *C;
2609 if (!match(RHS, m_APInt(C)))
2610 return nullptr;
2611
2612 // Rule out tautological comparisons (eg., ult 0 or uge 0).
2613 ConstantRange RHS_CR = ConstantRange::makeExactICmpRegion(Pred, *C);
2614 if (RHS_CR.isEmptySet())
2615 return ConstantInt::getFalse(GetCompareTy(RHS));
2616 if (RHS_CR.isFullSet())
2617 return ConstantInt::getTrue(GetCompareTy(RHS));
2618
2619 // Find the range of possible values for binary operators.
2620 unsigned Width = C->getBitWidth();
2621 APInt Lower = APInt(Width, 0);
2622 APInt Upper = APInt(Width, 0);
2623 if (auto *BO = dyn_cast<BinaryOperator>(LHS))
2624 setLimitsForBinOp(*BO, Lower, Upper);
2625
2626 ConstantRange LHS_CR =
2627 Lower != Upper ? ConstantRange(Lower, Upper) : ConstantRange(Width, true);
2628
2629 if (auto *I = dyn_cast<Instruction>(LHS))
2630 if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
2631 LHS_CR = LHS_CR.intersectWith(getConstantRangeFromMetadata(*Ranges));
2632
2633 if (!LHS_CR.isFullSet()) {
2634 if (RHS_CR.contains(LHS_CR))
2635 return ConstantInt::getTrue(GetCompareTy(RHS));
2636 if (RHS_CR.inverse().contains(LHS_CR))
2637 return ConstantInt::getFalse(GetCompareTy(RHS));
2638 }
2639
2640 return nullptr;
2641}
2642
2643static Value *simplifyICmpWithBinOp(CmpInst::Predicate Pred, Value *LHS,
2644 Value *RHS, const SimplifyQuery &Q,
2645 unsigned MaxRecurse) {
2646 Type *ITy = GetCompareTy(LHS); // The return type.
2647
2648 BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS);
2649 BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS);
2650 if (MaxRecurse && (LBO || RBO)) {
2651 // Analyze the case when either LHS or RHS is an add instruction.
2652 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
2653 // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null).
2654 bool NoLHSWrapProblem = false, NoRHSWrapProblem = false;
2655 if (LBO && LBO->getOpcode() == Instruction::Add) {
2656 A = LBO->getOperand(0);
2657 B = LBO->getOperand(1);
2658 NoLHSWrapProblem =
2659 ICmpInst::isEquality(Pred) ||
2660 (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) ||
2661 (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap());
2662 }
2663 if (RBO && RBO->getOpcode() == Instruction::Add) {
2664 C = RBO->getOperand(0);
2665 D = RBO->getOperand(1);
2666 NoRHSWrapProblem =
2667 ICmpInst::isEquality(Pred) ||
2668 (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) ||
2669 (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap());
2670 }
2671
2672 // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
2673 if ((A == RHS || B == RHS) && NoLHSWrapProblem)
2674 if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A,
2675 Constant::getNullValue(RHS->getType()), Q,
2676 MaxRecurse - 1))
2677 return V;
2678
2679 // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
2680 if ((C == LHS || D == LHS) && NoRHSWrapProblem)
2681 if (Value *V =
2682 SimplifyICmpInst(Pred, Constant::getNullValue(LHS->getType()),
2683 C == LHS ? D : C, Q, MaxRecurse - 1))
2684 return V;
2685
2686 // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow.
2687 if (A && C && (A == C || A == D || B == C || B == D) && NoLHSWrapProblem &&
2688 NoRHSWrapProblem) {
2689 // Determine Y and Z in the form icmp (X+Y), (X+Z).
2690 Value *Y, *Z;
2691 if (A == C) {
2692 // C + B == C + D -> B == D
2693 Y = B;
2694 Z = D;
2695 } else if (A == D) {
2696 // D + B == C + D -> B == C
2697 Y = B;
2698 Z = C;
2699 } else if (B == C) {
2700 // A + C == C + D -> A == D
2701 Y = A;
2702 Z = D;
2703 } else {
2704 assert(B == D)((B == D) ? static_cast<void> (0) : __assert_fail ("B == D"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 2704, __PRETTY_FUNCTION__))
;
2705 // A + D == C + D -> A == C
2706 Y = A;
2707 Z = C;
2708 }
2709 if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse - 1))
2710 return V;
2711 }
2712 }
2713
2714 {
2715 Value *Y = nullptr;
2716 // icmp pred (or X, Y), X
2717 if (LBO && match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS)))) {
2718 if (Pred == ICmpInst::ICMP_ULT)
2719 return getFalse(ITy);
2720 if (Pred == ICmpInst::ICMP_UGE)
2721 return getTrue(ITy);
2722
2723 if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
2724 bool RHSKnownNonNegative, RHSKnownNegative;
2725 bool YKnownNonNegative, YKnownNegative;
2726 ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, Q.DL, 0,
2727 Q.AC, Q.CxtI, Q.DT);
2728 ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, Q.DL, 0, Q.AC,
2729 Q.CxtI, Q.DT);
2730 if (RHSKnownNonNegative && YKnownNegative)
2731 return Pred == ICmpInst::ICMP_SLT ? getTrue(ITy) : getFalse(ITy);
2732 if (RHSKnownNegative || YKnownNonNegative)
2733 return Pred == ICmpInst::ICMP_SLT ? getFalse(ITy) : getTrue(ITy);
2734 }
2735 }
2736 // icmp pred X, (or X, Y)
2737 if (RBO && match(RBO, m_c_Or(m_Value(Y), m_Specific(LHS)))) {
2738 if (Pred == ICmpInst::ICMP_ULE)
2739 return getTrue(ITy);
2740 if (Pred == ICmpInst::ICMP_UGT)
2741 return getFalse(ITy);
2742
2743 if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE) {
2744 bool LHSKnownNonNegative, LHSKnownNegative;
2745 bool YKnownNonNegative, YKnownNegative;
2746 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0,
2747 Q.AC, Q.CxtI, Q.DT);
2748 ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, Q.DL, 0, Q.AC,
2749 Q.CxtI, Q.DT);
2750 if (LHSKnownNonNegative && YKnownNegative)
2751 return Pred == ICmpInst::ICMP_SGT ? getTrue(ITy) : getFalse(ITy);
2752 if (LHSKnownNegative || YKnownNonNegative)
2753 return Pred == ICmpInst::ICMP_SGT ? getFalse(ITy) : getTrue(ITy);
2754 }
2755 }
2756 }
2757
2758 // icmp pred (and X, Y), X
2759 if (LBO && match(LBO, m_CombineOr(m_And(m_Value(), m_Specific(RHS)),
2760 m_And(m_Specific(RHS), m_Value())))) {
2761 if (Pred == ICmpInst::ICMP_UGT)
2762 return getFalse(ITy);
2763 if (Pred == ICmpInst::ICMP_ULE)
2764 return getTrue(ITy);
2765 }
2766 // icmp pred X, (and X, Y)
2767 if (RBO && match(RBO, m_CombineOr(m_And(m_Value(), m_Specific(LHS)),
2768 m_And(m_Specific(LHS), m_Value())))) {
2769 if (Pred == ICmpInst::ICMP_UGE)
2770 return getTrue(ITy);
2771 if (Pred == ICmpInst::ICMP_ULT)
2772 return getFalse(ITy);
2773 }
2774
2775 // 0 - (zext X) pred C
2776 if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) {
2777 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) {
2778 if (RHSC->getValue().isStrictlyPositive()) {
2779 if (Pred == ICmpInst::ICMP_SLT)
2780 return ConstantInt::getTrue(RHSC->getContext());
2781 if (Pred == ICmpInst::ICMP_SGE)
2782 return ConstantInt::getFalse(RHSC->getContext());
2783 if (Pred == ICmpInst::ICMP_EQ)
2784 return ConstantInt::getFalse(RHSC->getContext());
2785 if (Pred == ICmpInst::ICMP_NE)
2786 return ConstantInt::getTrue(RHSC->getContext());
2787 }
2788 if (RHSC->getValue().isNonNegative()) {
2789 if (Pred == ICmpInst::ICMP_SLE)
2790 return ConstantInt::getTrue(RHSC->getContext());
2791 if (Pred == ICmpInst::ICMP_SGT)
2792 return ConstantInt::getFalse(RHSC->getContext());
2793 }
2794 }
2795 }
2796
2797 // icmp pred (urem X, Y), Y
2798 if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
2799 bool KnownNonNegative, KnownNegative;
2800 switch (Pred) {
2801 default:
2802 break;
2803 case ICmpInst::ICMP_SGT:
2804 case ICmpInst::ICMP_SGE:
2805 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC,
2806 Q.CxtI, Q.DT);
2807 if (!KnownNonNegative)
2808 break;
2809 LLVM_FALLTHROUGH[[clang::fallthrough]];
2810 case ICmpInst::ICMP_EQ:
2811 case ICmpInst::ICMP_UGT:
2812 case ICmpInst::ICMP_UGE:
2813 return getFalse(ITy);
2814 case ICmpInst::ICMP_SLT:
2815 case ICmpInst::ICMP_SLE:
2816 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC,
2817 Q.CxtI, Q.DT);
2818 if (!KnownNonNegative)
2819 break;
2820 LLVM_FALLTHROUGH[[clang::fallthrough]];
2821 case ICmpInst::ICMP_NE:
2822 case ICmpInst::ICMP_ULT:
2823 case ICmpInst::ICMP_ULE:
2824 return getTrue(ITy);
2825 }
2826 }
2827
2828 // icmp pred X, (urem Y, X)
2829 if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) {
2830 bool KnownNonNegative, KnownNegative;
2831 switch (Pred) {
2832 default:
2833 break;
2834 case ICmpInst::ICMP_SGT:
2835 case ICmpInst::ICMP_SGE:
2836 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC,
2837 Q.CxtI, Q.DT);
2838 if (!KnownNonNegative)
2839 break;
2840 LLVM_FALLTHROUGH[[clang::fallthrough]];
2841 case ICmpInst::ICMP_NE:
2842 case ICmpInst::ICMP_UGT:
2843 case ICmpInst::ICMP_UGE:
2844 return getTrue(ITy);
2845 case ICmpInst::ICMP_SLT:
2846 case ICmpInst::ICMP_SLE:
2847 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL, 0, Q.AC,
2848 Q.CxtI, Q.DT);
2849 if (!KnownNonNegative)
2850 break;
2851 LLVM_FALLTHROUGH[[clang::fallthrough]];
2852 case ICmpInst::ICMP_EQ:
2853 case ICmpInst::ICMP_ULT:
2854 case ICmpInst::ICMP_ULE:
2855 return getFalse(ITy);
2856 }
2857 }
2858
2859 // x >> y <=u x
2860 // x udiv y <=u x.
2861 if (LBO && (match(LBO, m_LShr(m_Specific(RHS), m_Value())) ||
2862 match(LBO, m_UDiv(m_Specific(RHS), m_Value())))) {
2863 // icmp pred (X op Y), X
2864 if (Pred == ICmpInst::ICMP_UGT)
2865 return getFalse(ITy);
2866 if (Pred == ICmpInst::ICMP_ULE)
2867 return getTrue(ITy);
2868 }
2869
2870 // x >=u x >> y
2871 // x >=u x udiv y.
2872 if (RBO && (match(RBO, m_LShr(m_Specific(LHS), m_Value())) ||
2873 match(RBO, m_UDiv(m_Specific(LHS), m_Value())))) {
2874 // icmp pred X, (X op Y)
2875 if (Pred == ICmpInst::ICMP_ULT)
2876 return getFalse(ITy);
2877 if (Pred == ICmpInst::ICMP_UGE)
2878 return getTrue(ITy);
2879 }
2880
2881 // handle:
2882 // CI2 << X == CI
2883 // CI2 << X != CI
2884 //
2885 // where CI2 is a power of 2 and CI isn't
2886 if (auto *CI = dyn_cast<ConstantInt>(RHS)) {
2887 const APInt *CI2Val, *CIVal = &CI->getValue();
2888 if (LBO && match(LBO, m_Shl(m_APInt(CI2Val), m_Value())) &&
2889 CI2Val->isPowerOf2()) {
2890 if (!CIVal->isPowerOf2()) {
2891 // CI2 << X can equal zero in some circumstances,
2892 // this simplification is unsafe if CI is zero.
2893 //
2894 // We know it is safe if:
2895 // - The shift is nsw, we can't shift out the one bit.
2896 // - The shift is nuw, we can't shift out the one bit.
2897 // - CI2 is one
2898 // - CI isn't zero
2899 if (LBO->hasNoSignedWrap() || LBO->hasNoUnsignedWrap() ||
2900 *CI2Val == 1 || !CI->isZero()) {
2901 if (Pred == ICmpInst::ICMP_EQ)
2902 return ConstantInt::getFalse(RHS->getContext());
2903 if (Pred == ICmpInst::ICMP_NE)
2904 return ConstantInt::getTrue(RHS->getContext());
2905 }
2906 }
2907 if (CIVal->isSignMask() && *CI2Val == 1) {
2908 if (Pred == ICmpInst::ICMP_UGT)
2909 return ConstantInt::getFalse(RHS->getContext());
2910 if (Pred == ICmpInst::ICMP_ULE)
2911 return ConstantInt::getTrue(RHS->getContext());
2912 }
2913 }
2914 }
2915
2916 if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() &&
2917 LBO->getOperand(1) == RBO->getOperand(1)) {
2918 switch (LBO->getOpcode()) {
2919 default:
2920 break;
2921 case Instruction::UDiv:
2922 case Instruction::LShr:
2923 if (ICmpInst::isSigned(Pred))
2924 break;
2925 LLVM_FALLTHROUGH[[clang::fallthrough]];
2926 case Instruction::SDiv:
2927 case Instruction::AShr:
2928 if (!LBO->isExact() || !RBO->isExact())
2929 break;
2930 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2931 RBO->getOperand(0), Q, MaxRecurse - 1))
2932 return V;
2933 break;
2934 case Instruction::Shl: {
2935 bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap();
2936 bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap();
2937 if (!NUW && !NSW)
2938 break;
2939 if (!NSW && ICmpInst::isSigned(Pred))
2940 break;
2941 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0),
2942 RBO->getOperand(0), Q, MaxRecurse - 1))
2943 return V;
2944 break;
2945 }
2946 }
2947 }
2948 return nullptr;
2949}
2950
2951/// Simplify integer comparisons where at least one operand of the compare
2952/// matches an integer min/max idiom.
2953static Value *simplifyICmpWithMinMax(CmpInst::Predicate Pred, Value *LHS,
2954 Value *RHS, const SimplifyQuery &Q,
2955 unsigned MaxRecurse) {
2956 Type *ITy = GetCompareTy(LHS); // The return type.
2957 Value *A, *B;
2958 CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE;
2959 CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B".
2960
2961 // Signed variants on "max(a,b)>=a -> true".
2962 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
2963 if (A != RHS)
2964 std::swap(A, B); // smax(A, B) pred A.
2965 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
2966 // We analyze this as smax(A, B) pred A.
2967 P = Pred;
2968 } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) &&
2969 (A == LHS || B == LHS)) {
2970 if (A != LHS)
2971 std::swap(A, B); // A pred smax(A, B).
2972 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B".
2973 // We analyze this as smax(A, B) swapped-pred A.
2974 P = CmpInst::getSwappedPredicate(Pred);
2975 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
2976 (A == RHS || B == RHS)) {
2977 if (A != RHS)
2978 std::swap(A, B); // smin(A, B) pred A.
2979 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
2980 // We analyze this as smax(-A, -B) swapped-pred -A.
2981 // Note that we do not need to actually form -A or -B thanks to EqP.
2982 P = CmpInst::getSwappedPredicate(Pred);
2983 } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) &&
2984 (A == LHS || B == LHS)) {
2985 if (A != LHS)
2986 std::swap(A, B); // A pred smin(A, B).
2987 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B".
2988 // We analyze this as smax(-A, -B) pred -A.
2989 // Note that we do not need to actually form -A or -B thanks to EqP.
2990 P = Pred;
2991 }
2992 if (P != CmpInst::BAD_ICMP_PREDICATE) {
2993 // Cases correspond to "max(A, B) p A".
2994 switch (P) {
2995 default:
2996 break;
2997 case CmpInst::ICMP_EQ:
2998 case CmpInst::ICMP_SLE:
2999 // Equivalent to "A EqP B". This may be the same as the condition tested
3000 // in the max/min; if so, we can just return that.
3001 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
3002 return V;
3003 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
3004 return V;
3005 // Otherwise, see if "A EqP B" simplifies.
3006 if (MaxRecurse)
3007 if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1))
3008 return V;
3009 break;
3010 case CmpInst::ICMP_NE:
3011 case CmpInst::ICMP_SGT: {
3012 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
3013 // Equivalent to "A InvEqP B". This may be the same as the condition
3014 // tested in the max/min; if so, we can just return that.
3015 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
3016 return V;
3017 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
3018 return V;
3019 // Otherwise, see if "A InvEqP B" simplifies.
3020 if (MaxRecurse)
3021 if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1))
3022 return V;
3023 break;
3024 }
3025 case CmpInst::ICMP_SGE:
3026 // Always true.
3027 return getTrue(ITy);
3028 case CmpInst::ICMP_SLT:
3029 // Always false.
3030 return getFalse(ITy);
3031 }
3032 }
3033
3034 // Unsigned variants on "max(a,b)>=a -> true".
3035 P = CmpInst::BAD_ICMP_PREDICATE;
3036 if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) {
3037 if (A != RHS)
3038 std::swap(A, B); // umax(A, B) pred A.
3039 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
3040 // We analyze this as umax(A, B) pred A.
3041 P = Pred;
3042 } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) &&
3043 (A == LHS || B == LHS)) {
3044 if (A != LHS)
3045 std::swap(A, B); // A pred umax(A, B).
3046 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B".
3047 // We analyze this as umax(A, B) swapped-pred A.
3048 P = CmpInst::getSwappedPredicate(Pred);
3049 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
3050 (A == RHS || B == RHS)) {
3051 if (A != RHS)
3052 std::swap(A, B); // umin(A, B) pred A.
3053 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
3054 // We analyze this as umax(-A, -B) swapped-pred -A.
3055 // Note that we do not need to actually form -A or -B thanks to EqP.
3056 P = CmpInst::getSwappedPredicate(Pred);
3057 } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) &&
3058 (A == LHS || B == LHS)) {
3059 if (A != LHS)
3060 std::swap(A, B); // A pred umin(A, B).
3061 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B".
3062 // We analyze this as umax(-A, -B) pred -A.
3063 // Note that we do not need to actually form -A or -B thanks to EqP.
3064 P = Pred;
3065 }
3066 if (P != CmpInst::BAD_ICMP_PREDICATE) {
3067 // Cases correspond to "max(A, B) p A".
3068 switch (P) {
3069 default:
3070 break;
3071 case CmpInst::ICMP_EQ:
3072 case CmpInst::ICMP_ULE:
3073 // Equivalent to "A EqP B". This may be the same as the condition tested
3074 // in the max/min; if so, we can just return that.
3075 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B))
3076 return V;
3077 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B))
3078 return V;
3079 // Otherwise, see if "A EqP B" simplifies.
3080 if (MaxRecurse)
3081 if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse - 1))
3082 return V;
3083 break;
3084 case CmpInst::ICMP_NE:
3085 case CmpInst::ICMP_UGT: {
3086 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP);
3087 // Equivalent to "A InvEqP B". This may be the same as the condition
3088 // tested in the max/min; if so, we can just return that.
3089 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B))
3090 return V;
3091 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B))
3092 return V;
3093 // Otherwise, see if "A InvEqP B" simplifies.
3094 if (MaxRecurse)
3095 if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse - 1))
3096 return V;
3097 break;
3098 }
3099 case CmpInst::ICMP_UGE:
3100 // Always true.
3101 return getTrue(ITy);
3102 case CmpInst::ICMP_ULT:
3103 // Always false.
3104 return getFalse(ITy);
3105 }
3106 }
3107
3108 // Variants on "max(x,y) >= min(x,z)".
3109 Value *C, *D;
3110 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
3111 match(RHS, m_SMin(m_Value(C), m_Value(D))) &&
3112 (A == C || A == D || B == C || B == D)) {
3113 // max(x, ?) pred min(x, ?).
3114 if (Pred == CmpInst::ICMP_SGE)
3115 // Always true.
3116 return getTrue(ITy);
3117 if (Pred == CmpInst::ICMP_SLT)
3118 // Always false.
3119 return getFalse(ITy);
3120 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) &&
3121 match(RHS, m_SMax(m_Value(C), m_Value(D))) &&
3122 (A == C || A == D || B == C || B == D)) {
3123 // min(x, ?) pred max(x, ?).
3124 if (Pred == CmpInst::ICMP_SLE)
3125 // Always true.
3126 return getTrue(ITy);
3127 if (Pred == CmpInst::ICMP_SGT)
3128 // Always false.
3129 return getFalse(ITy);
3130 } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) &&
3131 match(RHS, m_UMin(m_Value(C), m_Value(D))) &&
3132 (A == C || A == D || B == C || B == D)) {
3133 // max(x, ?) pred min(x, ?).
3134 if (Pred == CmpInst::ICMP_UGE)
3135 // Always true.
3136 return getTrue(ITy);
3137 if (Pred == CmpInst::ICMP_ULT)
3138 // Always false.
3139 return getFalse(ITy);
3140 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) &&
3141 match(RHS, m_UMax(m_Value(C), m_Value(D))) &&
3142 (A == C || A == D || B == C || B == D)) {
3143 // min(x, ?) pred max(x, ?).
3144 if (Pred == CmpInst::ICMP_ULE)
3145 // Always true.
3146 return getTrue(ITy);
3147 if (Pred == CmpInst::ICMP_UGT)
3148 // Always false.
3149 return getFalse(ITy);
3150 }
3151
3152 return nullptr;
3153}
3154
3155/// Given operands for an ICmpInst, see if we can fold the result.
3156/// If not, this returns null.
3157static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3158 const SimplifyQuery &Q, unsigned MaxRecurse) {
3159 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
3160 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!")((CmpInst::isIntPredicate(Pred) && "Not an integer compare!"
) ? static_cast<void> (0) : __assert_fail ("CmpInst::isIntPredicate(Pred) && \"Not an integer compare!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 3160, __PRETTY_FUNCTION__))
;
3161
3162 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
3163 if (Constant *CRHS = dyn_cast<Constant>(RHS))
3164 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
3165
3166 // If we have a constant, make sure it is on the RHS.
3167 std::swap(LHS, RHS);
3168 Pred = CmpInst::getSwappedPredicate(Pred);
3169 }
3170
3171 Type *ITy = GetCompareTy(LHS); // The return type.
3172
3173 // icmp X, X -> true/false
3174 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false
3175 // because X could be 0.
3176 if (LHS == RHS || isa<UndefValue>(RHS))
3177 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
3178
3179 if (Value *V = simplifyICmpOfBools(Pred, LHS, RHS, Q))
3180 return V;
3181
3182 if (Value *V = simplifyICmpWithZero(Pred, LHS, RHS, Q))
3183 return V;
3184
3185 if (Value *V = simplifyICmpWithConstant(Pred, LHS, RHS))
3186 return V;
3187
3188 // If both operands have range metadata, use the metadata
3189 // to simplify the comparison.
3190 if (isa<Instruction>(RHS) && isa<Instruction>(LHS)) {
3191 auto RHS_Instr = cast<Instruction>(RHS);
3192 auto LHS_Instr = cast<Instruction>(LHS);
3193
3194 if (RHS_Instr->getMetadata(LLVMContext::MD_range) &&
3195 LHS_Instr->getMetadata(LLVMContext::MD_range)) {
3196 auto RHS_CR = getConstantRangeFromMetadata(
3197 *RHS_Instr->getMetadata(LLVMContext::MD_range));
3198 auto LHS_CR = getConstantRangeFromMetadata(
3199 *LHS_Instr->getMetadata(LLVMContext::MD_range));
3200
3201 auto Satisfied_CR = ConstantRange::makeSatisfyingICmpRegion(Pred, RHS_CR);
3202 if (Satisfied_CR.contains(LHS_CR))
3203 return ConstantInt::getTrue(RHS->getContext());
3204
3205 auto InversedSatisfied_CR = ConstantRange::makeSatisfyingICmpRegion(
3206 CmpInst::getInversePredicate(Pred), RHS_CR);
3207 if (InversedSatisfied_CR.contains(LHS_CR))
3208 return ConstantInt::getFalse(RHS->getContext());
3209 }
3210 }
3211
3212 // Compare of cast, for example (zext X) != 0 -> X != 0
3213 if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) {
3214 Instruction *LI = cast<CastInst>(LHS);
3215 Value *SrcOp = LI->getOperand(0);
3216 Type *SrcTy = SrcOp->getType();
3217 Type *DstTy = LI->getType();
3218
3219 // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input
3220 // if the integer type is the same size as the pointer type.
3221 if (MaxRecurse && isa<PtrToIntInst>(LI) &&
3222 Q.DL.getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) {
3223 if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
3224 // Transfer the cast to the constant.
3225 if (Value *V = SimplifyICmpInst(Pred, SrcOp,
3226 ConstantExpr::getIntToPtr(RHSC, SrcTy),
3227 Q, MaxRecurse-1))
3228 return V;
3229 } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) {
3230 if (RI->getOperand(0)->getType() == SrcTy)
3231 // Compare without the cast.
3232 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
3233 Q, MaxRecurse-1))
3234 return V;
3235 }
3236 }
3237
3238 if (isa<ZExtInst>(LHS)) {
3239 // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the
3240 // same type.
3241 if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
3242 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
3243 // Compare X and Y. Note that signed predicates become unsigned.
3244 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
3245 SrcOp, RI->getOperand(0), Q,
3246 MaxRecurse-1))
3247 return V;
3248 }
3249 // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
3250 // too. If not, then try to deduce the result of the comparison.
3251 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
3252 // Compute the constant that would happen if we truncated to SrcTy then
3253 // reextended to DstTy.
3254 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
3255 Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
3256
3257 // If the re-extended constant didn't change then this is effectively
3258 // also a case of comparing two zero-extended values.
3259 if (RExt == CI && MaxRecurse)
3260 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
3261 SrcOp, Trunc, Q, MaxRecurse-1))
3262 return V;
3263
3264 // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit
3265 // there. Use this to work out the result of the comparison.
3266 if (RExt != CI) {
3267 switch (Pred) {
3268 default: llvm_unreachable("Unknown ICmp predicate!")::llvm::llvm_unreachable_internal("Unknown ICmp predicate!", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 3268)
;
3269 // LHS <u RHS.
3270 case ICmpInst::ICMP_EQ:
3271 case ICmpInst::ICMP_UGT:
3272 case ICmpInst::ICMP_UGE:
3273 return ConstantInt::getFalse(CI->getContext());
3274
3275 case ICmpInst::ICMP_NE:
3276 case ICmpInst::ICMP_ULT:
3277 case ICmpInst::ICMP_ULE:
3278 return ConstantInt::getTrue(CI->getContext());
3279
3280 // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS
3281 // is non-negative then LHS <s RHS.
3282 case ICmpInst::ICMP_SGT:
3283 case ICmpInst::ICMP_SGE:
3284 return CI->getValue().isNegative() ?
3285 ConstantInt::getTrue(CI->getContext()) :
3286 ConstantInt::getFalse(CI->getContext());
3287
3288 case ICmpInst::ICMP_SLT:
3289 case ICmpInst::ICMP_SLE:
3290 return CI->getValue().isNegative() ?
3291 ConstantInt::getFalse(CI->getContext()) :
3292 ConstantInt::getTrue(CI->getContext());
3293 }
3294 }
3295 }
3296 }
3297
3298 if (isa<SExtInst>(LHS)) {
3299 // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the
3300 // same type.
3301 if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
3302 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
3303 // Compare X and Y. Note that the predicate does not change.
3304 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
3305 Q, MaxRecurse-1))
3306 return V;
3307 }
3308 // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
3309 // too. If not, then try to deduce the result of the comparison.
3310 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
3311 // Compute the constant that would happen if we truncated to SrcTy then
3312 // reextended to DstTy.
3313 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
3314 Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
3315
3316 // If the re-extended constant didn't change then this is effectively
3317 // also a case of comparing two sign-extended values.
3318 if (RExt == CI && MaxRecurse)
3319 if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1))
3320 return V;
3321
3322 // Otherwise the upper bits of LHS are all equal, while RHS has varying
3323 // bits there. Use this to work out the result of the comparison.
3324 if (RExt != CI) {
3325 switch (Pred) {
3326 default: llvm_unreachable("Unknown ICmp predicate!")::llvm::llvm_unreachable_internal("Unknown ICmp predicate!", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 3326)
;
3327 case ICmpInst::ICMP_EQ:
3328 return ConstantInt::getFalse(CI->getContext());
3329 case ICmpInst::ICMP_NE:
3330 return ConstantInt::getTrue(CI->getContext());
3331
3332 // If RHS is non-negative then LHS <s RHS. If RHS is negative then
3333 // LHS >s RHS.
3334 case ICmpInst::ICMP_SGT:
3335 case ICmpInst::ICMP_SGE:
3336 return CI->getValue().isNegative() ?
3337 ConstantInt::getTrue(CI->getContext()) :
3338 ConstantInt::getFalse(CI->getContext());
3339 case ICmpInst::ICMP_SLT:
3340 case ICmpInst::ICMP_SLE:
3341 return CI->getValue().isNegative() ?
3342 ConstantInt::getFalse(CI->getContext()) :
3343 ConstantInt::getTrue(CI->getContext());
3344
3345 // If LHS is non-negative then LHS <u RHS. If LHS is negative then
3346 // LHS >u RHS.
3347 case ICmpInst::ICMP_UGT:
3348 case ICmpInst::ICMP_UGE:
3349 // Comparison is true iff the LHS <s 0.
3350 if (MaxRecurse)
3351 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp,
3352 Constant::getNullValue(SrcTy),
3353 Q, MaxRecurse-1))
3354 return V;
3355 break;
3356 case ICmpInst::ICMP_ULT:
3357 case ICmpInst::ICMP_ULE:
3358 // Comparison is true iff the LHS >=s 0.
3359 if (MaxRecurse)
3360 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp,
3361 Constant::getNullValue(SrcTy),
3362 Q, MaxRecurse-1))
3363 return V;
3364 break;
3365 }
3366 }
3367 }
3368 }
3369 }
3370
3371 // icmp eq|ne X, Y -> false|true if X != Y
3372 if ((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE) &&
3373 isKnownNonEqual(LHS, RHS, Q.DL, Q.AC, Q.CxtI, Q.DT)) {
3374 LLVMContext &Ctx = LHS->getType()->getContext();
3375 return Pred == ICmpInst::ICMP_NE ?
3376 ConstantInt::getTrue(Ctx) : ConstantInt::getFalse(Ctx);
3377 }
3378
3379 if (Value *V = simplifyICmpWithBinOp(Pred, LHS, RHS, Q, MaxRecurse))
3380 return V;
3381
3382 if (Value *V = simplifyICmpWithMinMax(Pred, LHS, RHS, Q, MaxRecurse))
3383 return V;
3384
3385 // Simplify comparisons of related pointers using a powerful, recursive
3386 // GEP-walk when we have target data available..
3387 if (LHS->getType()->isPointerTy())
3388 if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.CxtI, LHS, RHS))
3389 return C;
3390 if (auto *CLHS = dyn_cast<PtrToIntOperator>(LHS))
3391 if (auto *CRHS = dyn_cast<PtrToIntOperator>(RHS))
3392 if (Q.DL.getTypeSizeInBits(CLHS->getPointerOperandType()) ==
3393 Q.DL.getTypeSizeInBits(CLHS->getType()) &&
3394 Q.DL.getTypeSizeInBits(CRHS->getPointerOperandType()) ==
3395 Q.DL.getTypeSizeInBits(CRHS->getType()))
3396 if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.CxtI,
3397 CLHS->getPointerOperand(),
3398 CRHS->getPointerOperand()))
3399 return C;
3400
3401 if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) {
3402 if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) {
3403 if (GLHS->getPointerOperand() == GRHS->getPointerOperand() &&
3404 GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() &&
3405 (ICmpInst::isEquality(Pred) ||
3406 (GLHS->isInBounds() && GRHS->isInBounds() &&
3407 Pred == ICmpInst::getSignedPredicate(Pred)))) {
3408 // The bases are equal and the indices are constant. Build a constant
3409 // expression GEP with the same indices and a null base pointer to see
3410 // what constant folding can make out of it.
3411 Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType());
3412 SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end());
3413 Constant *NewLHS = ConstantExpr::getGetElementPtr(
3414 GLHS->getSourceElementType(), Null, IndicesLHS);
3415
3416 SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end());
3417 Constant *NewRHS = ConstantExpr::getGetElementPtr(
3418 GLHS->getSourceElementType(), Null, IndicesRHS);
3419 return ConstantExpr::getICmp(Pred, NewLHS, NewRHS);
3420 }
3421 }
3422 }
3423
3424 // If a bit is known to be zero for A and known to be one for B,
3425 // then A and B cannot be equal.
3426 if (ICmpInst::isEquality(Pred)) {
3427 const APInt *RHSVal;
3428 if (match(RHS, m_APInt(RHSVal))) {
3429 unsigned BitWidth = RHSVal->getBitWidth();
3430 APInt LHSKnownZero(BitWidth, 0);
3431 APInt LHSKnownOne(BitWidth, 0);
3432 computeKnownBits(LHS, LHSKnownZero, LHSKnownOne, Q.DL, /*Depth=*/0, Q.AC,
3433 Q.CxtI, Q.DT);
3434 if (LHSKnownZero.intersects(*RHSVal) || !LHSKnownOne.isSubsetOf(*RHSVal))
3435 return Pred == ICmpInst::ICMP_EQ ? ConstantInt::getFalse(ITy)
3436 : ConstantInt::getTrue(ITy);
3437 }
3438 }
3439
3440 // If the comparison is with the result of a select instruction, check whether
3441 // comparing with either branch of the select always yields the same value.
3442 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
3443 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
3444 return V;
3445
3446 // If the comparison is with the result of a phi instruction, check whether
3447 // doing the compare with each incoming phi value yields a common result.
3448 if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
3449 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
3450 return V;
3451
3452 return nullptr;
3453}
3454
3455Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3456 const DataLayout &DL,
3457 const TargetLibraryInfo *TLI,
3458 const DominatorTree *DT, AssumptionCache *AC,
3459 const Instruction *CxtI) {
3460 return ::SimplifyICmpInst(Predicate, LHS, RHS, {DL, TLI, DT, AC, CxtI},
3461 RecursionLimit);
3462}
3463
3464Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3465 const SimplifyQuery &Q) {
3466 return ::SimplifyICmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
3467}
3468
3469/// Given operands for an FCmpInst, see if we can fold the result.
3470/// If not, this returns null.
3471static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3472 FastMathFlags FMF, const SimplifyQuery &Q,
3473 unsigned MaxRecurse) {
3474 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
3475 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!")((CmpInst::isFPPredicate(Pred) && "Not an FP compare!"
) ? static_cast<void> (0) : __assert_fail ("CmpInst::isFPPredicate(Pred) && \"Not an FP compare!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 3475, __PRETTY_FUNCTION__))
;
3476
3477 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
3478 if (Constant *CRHS = dyn_cast<Constant>(RHS))
3479 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI);
3480
3481 // If we have a constant, make sure it is on the RHS.
3482 std::swap(LHS, RHS);
3483 Pred = CmpInst::getSwappedPredicate(Pred);
3484 }
3485
3486 // Fold trivial predicates.
3487 Type *RetTy = GetCompareTy(LHS);
3488 if (Pred == FCmpInst::FCMP_FALSE)
3489 return getFalse(RetTy);
3490 if (Pred == FCmpInst::FCMP_TRUE)
3491 return getTrue(RetTy);
3492
3493 // UNO/ORD predicates can be trivially folded if NaNs are ignored.
3494 if (FMF.noNaNs()) {
3495 if (Pred == FCmpInst::FCMP_UNO)
3496 return getFalse(RetTy);
3497 if (Pred == FCmpInst::FCMP_ORD)
3498 return getTrue(RetTy);
3499 }
3500
3501 // fcmp pred x, undef and fcmp pred undef, x
3502 // fold to true if unordered, false if ordered
3503 if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) {
3504 // Choosing NaN for the undef will always make unordered comparison succeed
3505 // and ordered comparison fail.
3506 return ConstantInt::get(RetTy, CmpInst::isUnordered(Pred));
3507 }
3508
3509 // fcmp x,x -> true/false. Not all compares are foldable.
3510 if (LHS == RHS) {
3511 if (CmpInst::isTrueWhenEqual(Pred))
3512 return getTrue(RetTy);
3513 if (CmpInst::isFalseWhenEqual(Pred))
3514 return getFalse(RetTy);
3515 }
3516
3517 // Handle fcmp with constant RHS
3518 const ConstantFP *CFP = nullptr;
3519 if (const auto *RHSC = dyn_cast<Constant>(RHS)) {
3520 if (RHS->getType()->isVectorTy())
3521 CFP = dyn_cast_or_null<ConstantFP>(RHSC->getSplatValue());
3522 else
3523 CFP = dyn_cast<ConstantFP>(RHSC);
3524 }
3525 if (CFP) {
3526 // If the constant is a nan, see if we can fold the comparison based on it.
3527 if (CFP->getValueAPF().isNaN()) {
3528 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
3529 return getFalse(RetTy);
3530 assert(FCmpInst::isUnordered(Pred) &&((FCmpInst::isUnordered(Pred) && "Comparison must be either ordered or unordered!"
) ? static_cast<void> (0) : __assert_fail ("FCmpInst::isUnordered(Pred) && \"Comparison must be either ordered or unordered!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 3531, __PRETTY_FUNCTION__))
3531 "Comparison must be either ordered or unordered!")((FCmpInst::isUnordered(Pred) && "Comparison must be either ordered or unordered!"
) ? static_cast<void> (0) : __assert_fail ("FCmpInst::isUnordered(Pred) && \"Comparison must be either ordered or unordered!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 3531, __PRETTY_FUNCTION__))
;
3532 // True if unordered.
3533 return getTrue(RetTy);
3534 }
3535 // Check whether the constant is an infinity.
3536 if (CFP->getValueAPF().isInfinity()) {
3537 if (CFP->getValueAPF().isNegative()) {
3538 switch (Pred) {
3539 case FCmpInst::FCMP_OLT:
3540 // No value is ordered and less than negative infinity.
3541 return getFalse(RetTy);
3542 case FCmpInst::FCMP_UGE:
3543 // All values are unordered with or at least negative infinity.
3544 return getTrue(RetTy);
3545 default:
3546 break;
3547 }
3548 } else {
3549 switch (Pred) {
3550 case FCmpInst::FCMP_OGT:
3551 // No value is ordered and greater than infinity.
3552 return getFalse(RetTy);
3553 case FCmpInst::FCMP_ULE:
3554 // All values are unordered with and at most infinity.
3555 return getTrue(RetTy);
3556 default:
3557 break;
3558 }
3559 }
3560 }
3561 if (CFP->getValueAPF().isZero()) {
3562 switch (Pred) {
3563 case FCmpInst::FCMP_UGE:
3564 if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
3565 return getTrue(RetTy);
3566 break;
3567 case FCmpInst::FCMP_OLT:
3568 // X < 0
3569 if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
3570 return getFalse(RetTy);
3571 break;
3572 default:
3573 break;
3574 }
3575 }
3576 }
3577
3578 // If the comparison is with the result of a select instruction, check whether
3579 // comparing with either branch of the select always yields the same value.
3580 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
3581 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
3582 return V;
3583
3584 // If the comparison is with the result of a phi instruction, check whether
3585 // doing the compare with each incoming phi value yields a common result.
3586 if (isa<PHINode>(LHS) || isa<PHINode>(RHS))
3587 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse))
3588 return V;
3589
3590 return nullptr;
3591}
3592
3593Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3594 FastMathFlags FMF, const DataLayout &DL,
3595 const TargetLibraryInfo *TLI,
3596 const DominatorTree *DT, AssumptionCache *AC,
3597 const Instruction *CxtI) {
3598 return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, {DL, TLI, DT, AC, CxtI},
3599 RecursionLimit);
3600}
3601
3602Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
3603 FastMathFlags FMF, const SimplifyQuery &Q) {
3604 return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, Q, RecursionLimit);
3605}
3606
3607/// See if V simplifies when its operand Op is replaced with RepOp.
3608static const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
3609 const SimplifyQuery &Q,
3610 unsigned MaxRecurse) {
3611 // Trivial replacement.
3612 if (V == Op)
3613 return RepOp;
3614
3615 auto *I = dyn_cast<Instruction>(V);
3616 if (!I)
3617 return nullptr;
3618
3619 // If this is a binary operator, try to simplify it with the replaced op.
3620 if (auto *B = dyn_cast<BinaryOperator>(I)) {
3621 // Consider:
3622 // %cmp = icmp eq i32 %x, 2147483647
3623 // %add = add nsw i32 %x, 1
3624 // %sel = select i1 %cmp, i32 -2147483648, i32 %add
3625 //
3626 // We can't replace %sel with %add unless we strip away the flags.
3627 if (isa<OverflowingBinaryOperator>(B))
3628 if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap())
3629 return nullptr;
3630 if (isa<PossiblyExactOperator>(B))
3631 if (B->isExact())
3632 return nullptr;
3633
3634 if (MaxRecurse) {
3635 if (B->getOperand(0) == Op)
3636 return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), Q,
3637 MaxRecurse - 1);
3638 if (B->getOperand(1) == Op)
3639 return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, Q,
3640 MaxRecurse - 1);
3641 }
3642 }
3643
3644 // Same for CmpInsts.
3645 if (CmpInst *C = dyn_cast<CmpInst>(I)) {
3646 if (MaxRecurse) {
3647 if (C->getOperand(0) == Op)
3648 return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), Q,
3649 MaxRecurse - 1);
3650 if (C->getOperand(1) == Op)
3651 return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, Q,
3652 MaxRecurse - 1);
3653 }
3654 }
3655
3656 // TODO: We could hand off more cases to instsimplify here.
3657
3658 // If all operands are constant after substituting Op for RepOp then we can
3659 // constant fold the instruction.
3660 if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) {
3661 // Build a list of all constant operands.
3662 SmallVector<Constant *, 8> ConstOps;
3663 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
3664 if (I->getOperand(i) == Op)
3665 ConstOps.push_back(CRepOp);
3666 else if (Constant *COp = dyn_cast<Constant>(I->getOperand(i)))
3667 ConstOps.push_back(COp);
3668 else
3669 break;
3670 }
3671
3672 // All operands were constants, fold it.
3673 if (ConstOps.size() == I->getNumOperands()) {
3674 if (CmpInst *C = dyn_cast<CmpInst>(I))
3675 return ConstantFoldCompareInstOperands(C->getPredicate(), ConstOps[0],
3676 ConstOps[1], Q.DL, Q.TLI);
3677
3678 if (LoadInst *LI = dyn_cast<LoadInst>(I))
3679 if (!LI->isVolatile())
3680 return ConstantFoldLoadFromConstPtr(ConstOps[0], LI->getType(), Q.DL);
3681
3682 return ConstantFoldInstOperands(I, ConstOps, Q.DL, Q.TLI);
3683 }
3684 }
3685
3686 return nullptr;
3687}
3688
3689/// Try to simplify a select instruction when its condition operand is an
3690/// integer comparison where one operand of the compare is a constant.
3691static Value *simplifySelectBitTest(Value *TrueVal, Value *FalseVal, Value *X,
3692 const APInt *Y, bool TrueWhenUnset) {
3693 const APInt *C;
3694
3695 // (X & Y) == 0 ? X & ~Y : X --> X
3696 // (X & Y) != 0 ? X & ~Y : X --> X & ~Y
3697 if (FalseVal == X && match(TrueVal, m_And(m_Specific(X), m_APInt(C))) &&
3698 *Y == ~*C)
3699 return TrueWhenUnset ? FalseVal : TrueVal;
3700
3701 // (X & Y) == 0 ? X : X & ~Y --> X & ~Y
3702 // (X & Y) != 0 ? X : X & ~Y --> X
3703 if (TrueVal == X && match(FalseVal, m_And(m_Specific(X), m_APInt(C))) &&
3704 *Y == ~*C)
3705 return TrueWhenUnset ? FalseVal : TrueVal;
3706
3707 if (Y->isPowerOf2()) {
3708 // (X & Y) == 0 ? X | Y : X --> X | Y
3709 // (X & Y) != 0 ? X | Y : X --> X
3710 if (FalseVal == X && match(TrueVal, m_Or(m_Specific(X), m_APInt(C))) &&
3711 *Y == *C)
3712 return TrueWhenUnset ? TrueVal : FalseVal;
3713
3714 // (X & Y) == 0 ? X : X | Y --> X
3715 // (X & Y) != 0 ? X : X | Y --> X | Y
3716 if (TrueVal == X && match(FalseVal, m_Or(m_Specific(X), m_APInt(C))) &&
3717 *Y == *C)
3718 return TrueWhenUnset ? TrueVal : FalseVal;
3719 }
3720
3721 return nullptr;
3722}
3723
3724/// An alternative way to test if a bit is set or not uses sgt/slt instead of
3725/// eq/ne.
3726static Value *simplifySelectWithFakeICmpEq(Value *CmpLHS, Value *TrueVal,
3727 Value *FalseVal,
3728 bool TrueWhenUnset) {
3729 unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();
3730 if (!BitWidth)
3731 return nullptr;
3732
3733 APInt MinSignedValue;
3734 Value *X;
3735 if (match(CmpLHS, m_Trunc(m_Value(X))) && (X == TrueVal || X == FalseVal)) {
3736 // icmp slt (trunc X), 0 <--> icmp ne (and X, C), 0
3737 // icmp sgt (trunc X), -1 <--> icmp eq (and X, C), 0
3738 unsigned DestSize = CmpLHS->getType()->getScalarSizeInBits();
3739 MinSignedValue = APInt::getSignedMinValue(DestSize).zext(BitWidth);
3740 } else {
3741 // icmp slt X, 0 <--> icmp ne (and X, C), 0
3742 // icmp sgt X, -1 <--> icmp eq (and X, C), 0
3743 X = CmpLHS;
3744 MinSignedValue = APInt::getSignedMinValue(BitWidth);
3745 }
3746
3747 if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, X, &MinSignedValue,
3748 TrueWhenUnset))
3749 return V;
3750
3751 return nullptr;
3752}
3753
3754/// Try to simplify a select instruction when its condition operand is an
3755/// integer comparison.
3756static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
3757 Value *FalseVal, const SimplifyQuery &Q,
3758 unsigned MaxRecurse) {
3759 ICmpInst::Predicate Pred;
3760 Value *CmpLHS, *CmpRHS;
3761 if (!match(CondVal, m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS))))
3762 return nullptr;
3763
3764 // FIXME: This code is nearly duplicated in InstCombine. Using/refactoring
3765 // decomposeBitTestICmp() might help.
3766 if (ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero())) {
3767 Value *X;
3768 const APInt *Y;
3769 if (match(CmpLHS, m_And(m_Value(X), m_APInt(Y))))
3770 if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, X, Y,
3771 Pred == ICmpInst::ICMP_EQ))
3772 return V;
3773 } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
3774 // Comparing signed-less-than 0 checks if the sign bit is set.
3775 if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, TrueVal, FalseVal,
3776 false))
3777 return V;
3778 } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
3779 // Comparing signed-greater-than -1 checks if the sign bit is not set.
3780 if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, TrueVal, FalseVal,
3781 true))
3782 return V;
3783 }
3784
3785 if (CondVal->hasOneUse()) {
3786 const APInt *C;
3787 if (match(CmpRHS, m_APInt(C))) {
3788 // X < MIN ? T : F --> F
3789 if (Pred == ICmpInst::ICMP_SLT && C->isMinSignedValue())
3790 return FalseVal;
3791 // X < MIN ? T : F --> F
3792 if (Pred == ICmpInst::ICMP_ULT && C->isMinValue())
3793 return FalseVal;
3794 // X > MAX ? T : F --> F
3795 if (Pred == ICmpInst::ICMP_SGT && C->isMaxSignedValue())
3796 return FalseVal;
3797 // X > MAX ? T : F --> F
3798 if (Pred == ICmpInst::ICMP_UGT && C->isMaxValue())
3799 return FalseVal;
3800 }
3801 }
3802
3803 // If we have an equality comparison, then we know the value in one of the
3804 // arms of the select. See if substituting this value into the arm and
3805 // simplifying the result yields the same value as the other arm.
3806 if (Pred == ICmpInst::ICMP_EQ) {
3807 if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3808 TrueVal ||
3809 SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3810 TrueVal)
3811 return FalseVal;
3812 if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3813 FalseVal ||
3814 SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3815 FalseVal)
3816 return FalseVal;
3817 } else if (Pred == ICmpInst::ICMP_NE) {
3818 if (SimplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3819 FalseVal ||
3820 SimplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3821 FalseVal)
3822 return TrueVal;
3823 if (SimplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q, MaxRecurse) ==
3824 TrueVal ||
3825 SimplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q, MaxRecurse) ==
3826 TrueVal)
3827 return TrueVal;
3828 }
3829
3830 return nullptr;
3831}
3832
3833/// Given operands for a SelectInst, see if we can fold the result.
3834/// If not, this returns null.
3835static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal,
3836 Value *FalseVal, const SimplifyQuery &Q,
3837 unsigned MaxRecurse) {
3838 // select true, X, Y -> X
3839 // select false, X, Y -> Y
3840 if (Constant *CB = dyn_cast<Constant>(CondVal)) {
3841 if (CB->isAllOnesValue())
3842 return TrueVal;
3843 if (CB->isNullValue())
3844 return FalseVal;
3845 }
3846
3847 // select C, X, X -> X
3848 if (TrueVal == FalseVal)
3849 return TrueVal;
3850
3851 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
3852 if (isa<Constant>(TrueVal))
3853 return TrueVal;
3854 return FalseVal;
3855 }
3856 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
3857 return FalseVal;
3858 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
3859 return TrueVal;
3860
3861 if (Value *V =
3862 simplifySelectWithICmpCond(CondVal, TrueVal, FalseVal, Q, MaxRecurse))
3863 return V;
3864
3865 return nullptr;
3866}
3867
3868Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
3869 const DataLayout &DL,
3870 const TargetLibraryInfo *TLI,
3871 const DominatorTree *DT, AssumptionCache *AC,
3872 const Instruction *CxtI) {
3873 return ::SimplifySelectInst(Cond, TrueVal, FalseVal, {DL, TLI, DT, AC, CxtI},
3874 RecursionLimit);
3875}
3876
3877Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
3878 const SimplifyQuery &Q) {
3879 return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Q, RecursionLimit);
3880}
3881
3882/// Given operands for an GetElementPtrInst, see if we can fold the result.
3883/// If not, this returns null.
3884static Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
3885 const SimplifyQuery &Q, unsigned) {
3886 // The type of the GEP pointer operand.
3887 unsigned AS =
3888 cast<PointerType>(Ops[0]->getType()->getScalarType())->getAddressSpace();
3889
3890 // getelementptr P -> P.
3891 if (Ops.size() == 1)
3892 return Ops[0];
3893
3894 // Compute the (pointer) type returned by the GEP instruction.
3895 Type *LastType = GetElementPtrInst::getIndexedType(SrcTy, Ops.slice(1));
3896 Type *GEPTy = PointerType::get(LastType, AS);
3897 if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType()))
3898 GEPTy = VectorType::get(GEPTy, VT->getNumElements());
3899 else if (VectorType *VT = dyn_cast<VectorType>(Ops[1]->getType()))
3900 GEPTy = VectorType::get(GEPTy, VT->getNumElements());
3901
3902 if (isa<UndefValue>(Ops[0]))
3903 return UndefValue::get(GEPTy);
3904
3905 if (Ops.size() == 2) {
3906 // getelementptr P, 0 -> P.
3907 if (match(Ops[1], m_Zero()))
3908 return Ops[0];
3909
3910 Type *Ty = SrcTy;
3911 if (Ty->isSized()) {
3912 Value *P;
3913 uint64_t C;
3914 uint64_t TyAllocSize = Q.DL.getTypeAllocSize(Ty);
3915 // getelementptr P, N -> P if P points to a type of zero size.
3916 if (TyAllocSize == 0)
3917 return Ops[0];
3918
3919 // The following transforms are only safe if the ptrtoint cast
3920 // doesn't truncate the pointers.
3921 if (Ops[1]->getType()->getScalarSizeInBits() ==
3922 Q.DL.getPointerSizeInBits(AS)) {
3923 auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * {
3924 if (match(P, m_Zero()))
3925 return Constant::getNullValue(GEPTy);
3926 Value *Temp;
3927 if (match(P, m_PtrToInt(m_Value(Temp))))
3928 if (Temp->getType() == GEPTy)
3929 return Temp;
3930 return nullptr;
3931 };
3932
3933 // getelementptr V, (sub P, V) -> P if P points to a type of size 1.
3934 if (TyAllocSize == 1 &&
3935 match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0])))))
3936 if (Value *R = PtrToIntOrZero(P))
3937 return R;
3938
3939 // getelementptr V, (ashr (sub P, V), C) -> Q
3940 // if P points to a type of size 1 << C.
3941 if (match(Ops[1],
3942 m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
3943 m_ConstantInt(C))) &&
3944 TyAllocSize == 1ULL << C)
3945 if (Value *R = PtrToIntOrZero(P))
3946 return R;
3947
3948 // getelementptr V, (sdiv (sub P, V), C) -> Q
3949 // if P points to a type of size C.
3950 if (match(Ops[1],
3951 m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
3952 m_SpecificInt(TyAllocSize))))
3953 if (Value *R = PtrToIntOrZero(P))
3954 return R;
3955 }
3956 }
3957 }
3958
3959 if (Q.DL.getTypeAllocSize(LastType) == 1 &&
3960 all_of(Ops.slice(1).drop_back(1),
3961 [](Value *Idx) { return match(Idx, m_Zero()); })) {
3962 unsigned PtrWidth =
3963 Q.DL.getPointerSizeInBits(Ops[0]->getType()->getPointerAddressSpace());
3964 if (Q.DL.getTypeSizeInBits(Ops.back()->getType()) == PtrWidth) {
3965 APInt BasePtrOffset(PtrWidth, 0);
3966 Value *StrippedBasePtr =
3967 Ops[0]->stripAndAccumulateInBoundsConstantOffsets(Q.DL,
3968 BasePtrOffset);
3969
3970 // gep (gep V, C), (sub 0, V) -> C
3971 if (match(Ops.back(),
3972 m_Sub(m_Zero(), m_PtrToInt(m_Specific(StrippedBasePtr))))) {
3973 auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset);
3974 return ConstantExpr::getIntToPtr(CI, GEPTy);
3975 }
3976 // gep (gep V, C), (xor V, -1) -> C-1
3977 if (match(Ops.back(),
3978 m_Xor(m_PtrToInt(m_Specific(StrippedBasePtr)), m_AllOnes()))) {
3979 auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset - 1);
3980 return ConstantExpr::getIntToPtr(CI, GEPTy);
3981 }
3982 }
3983 }
3984
3985 // Check to see if this is constant foldable.
3986 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
3987 if (!isa<Constant>(Ops[i]))
3988 return nullptr;
3989
3990 return ConstantExpr::getGetElementPtr(SrcTy, cast<Constant>(Ops[0]),
3991 Ops.slice(1));
3992}
3993
3994Value *llvm::SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
3995 const DataLayout &DL,
3996 const TargetLibraryInfo *TLI,
3997 const DominatorTree *DT, AssumptionCache *AC,
3998 const Instruction *CxtI) {
3999 return ::SimplifyGEPInst(SrcTy, Ops, {DL, TLI, DT, AC, CxtI}, RecursionLimit);
4000}
4001
4002Value *llvm::SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
4003 const SimplifyQuery &Q) {
4004 return ::SimplifyGEPInst(SrcTy, Ops, Q, RecursionLimit);
4005}
4006
4007/// Given operands for an InsertValueInst, see if we can fold the result.
4008/// If not, this returns null.
4009static Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
4010 ArrayRef<unsigned> Idxs, const SimplifyQuery &Q,
4011 unsigned) {
4012 if (Constant *CAgg = dyn_cast<Constant>(Agg))
4013 if (Constant *CVal = dyn_cast<Constant>(Val))
4014 return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs);
4015
4016 // insertvalue x, undef, n -> x
4017 if (match(Val, m_Undef()))
4018 return Agg;
4019
4020 // insertvalue x, (extractvalue y, n), n
4021 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val))
4022 if (EV->getAggregateOperand()->getType() == Agg->getType() &&
4023 EV->getIndices() == Idxs) {
4024 // insertvalue undef, (extractvalue y, n), n -> y
4025 if (match(Agg, m_Undef()))
4026 return EV->getAggregateOperand();
4027
4028 // insertvalue y, (extractvalue y, n), n -> y
4029 if (Agg == EV->getAggregateOperand())
4030 return Agg;
4031 }
4032
4033 return nullptr;
4034}
4035
4036Value *llvm::SimplifyInsertValueInst(
4037 Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, const DataLayout &DL,
4038 const TargetLibraryInfo *TLI, const DominatorTree *DT, AssumptionCache *AC,
4039 const Instruction *CxtI) {
4040 return ::SimplifyInsertValueInst(Agg, Val, Idxs, {DL, TLI, DT, AC, CxtI},
4041 RecursionLimit);
4042}
4043
4044Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val,
4045 ArrayRef<unsigned> Idxs,
4046 const SimplifyQuery &Q) {
4047 return ::SimplifyInsertValueInst(Agg, Val, Idxs, Q, RecursionLimit);
4048}
4049
4050/// Given operands for an ExtractValueInst, see if we can fold the result.
4051/// If not, this returns null.
4052static Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
4053 const SimplifyQuery &, unsigned) {
4054 if (auto *CAgg = dyn_cast<Constant>(Agg))
4055 return ConstantFoldExtractValueInstruction(CAgg, Idxs);
4056
4057 // extractvalue x, (insertvalue y, elt, n), n -> elt
4058 unsigned NumIdxs = Idxs.size();
4059 for (auto *IVI = dyn_cast<InsertValueInst>(Agg); IVI != nullptr;
4060 IVI = dyn_cast<InsertValueInst>(IVI->getAggregateOperand())) {
4061 ArrayRef<unsigned> InsertValueIdxs = IVI->getIndices();
4062 unsigned NumInsertValueIdxs = InsertValueIdxs.size();
4063 unsigned NumCommonIdxs = std::min(NumInsertValueIdxs, NumIdxs);
4064 if (InsertValueIdxs.slice(0, NumCommonIdxs) ==
4065 Idxs.slice(0, NumCommonIdxs)) {
4066 if (NumIdxs == NumInsertValueIdxs)
4067 return IVI->getInsertedValueOperand();
4068 break;
4069 }
4070 }
4071
4072 return nullptr;
4073}
4074
4075Value *llvm::SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
4076 const DataLayout &DL,
4077 const TargetLibraryInfo *TLI,
4078 const DominatorTree *DT,
4079 AssumptionCache *AC,
4080 const Instruction *CxtI) {
4081 return ::SimplifyExtractValueInst(Agg, Idxs, {DL, TLI, DT, AC, CxtI},
4082 RecursionLimit);
4083}
4084
4085Value *llvm::SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
4086 const SimplifyQuery &Q) {
4087 return ::SimplifyExtractValueInst(Agg, Idxs, Q, RecursionLimit);
4088}
4089
4090/// Given operands for an ExtractElementInst, see if we can fold the result.
4091/// If not, this returns null.
4092static Value *SimplifyExtractElementInst(Value *Vec, Value *Idx, const SimplifyQuery &,
4093 unsigned) {
4094 if (auto *CVec = dyn_cast<Constant>(Vec)) {
4095 if (auto *CIdx = dyn_cast<Constant>(Idx))
4096 return ConstantFoldExtractElementInstruction(CVec, CIdx);
4097
4098 // The index is not relevant if our vector is a splat.
4099 if (auto *Splat = CVec->getSplatValue())
4100 return Splat;
4101
4102 if (isa<UndefValue>(Vec))
4103 return UndefValue::get(Vec->getType()->getVectorElementType());
4104 }
4105
4106 // If extracting a specified index from the vector, see if we can recursively
4107 // find a previously computed scalar that was inserted into the vector.
4108 if (auto *IdxC = dyn_cast<ConstantInt>(Idx))
4109 if (Value *Elt = findScalarElement(Vec, IdxC->getZExtValue()))
4110 return Elt;
4111
4112 return nullptr;
4113}
4114
4115Value *llvm::SimplifyExtractElementInst(
4116 Value *Vec, Value *Idx, const DataLayout &DL, const TargetLibraryInfo *TLI,
4117 const DominatorTree *DT, AssumptionCache *AC, const Instruction *CxtI) {
4118 return ::SimplifyExtractElementInst(Vec, Idx, {DL, TLI, DT, AC, CxtI},
4119 RecursionLimit);
4120}
4121
4122Value *llvm::SimplifyExtractElementInst(Value *Vec, Value *Idx,
4123 const SimplifyQuery &Q) {
4124 return ::SimplifyExtractElementInst(Vec, Idx, Q, RecursionLimit);
4125}
4126
4127/// See if we can fold the given phi. If not, returns null.
4128static Value *SimplifyPHINode(PHINode *PN, const SimplifyQuery &Q) {
4129 // If all of the PHI's incoming values are the same then replace the PHI node
4130 // with the common value.
4131 Value *CommonValue = nullptr;
4132 bool HasUndefInput = false;
4133 for (Value *Incoming : PN->incoming_values()) {
4134 // If the incoming value is the phi node itself, it can safely be skipped.
4135 if (Incoming == PN) continue;
4136 if (isa<UndefValue>(Incoming)) {
4137 // Remember that we saw an undef value, but otherwise ignore them.
4138 HasUndefInput = true;
4139 continue;
4140 }
4141 if (CommonValue && Incoming != CommonValue)
4142 return nullptr; // Not the same, bail out.
4143 CommonValue = Incoming;
4144 }
4145
4146 // If CommonValue is null then all of the incoming values were either undef or
4147 // equal to the phi node itself.
4148 if (!CommonValue)
4149 return UndefValue::get(PN->getType());
4150
4151 // If we have a PHI node like phi(X, undef, X), where X is defined by some
4152 // instruction, we cannot return X as the result of the PHI node unless it
4153 // dominates the PHI block.
4154 if (HasUndefInput)
4155 return ValueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr;
4156
4157 return CommonValue;
4158}
4159
4160static Value *SimplifyCastInst(unsigned CastOpc, Value *Op,
4161 Type *Ty, const SimplifyQuery &Q, unsigned MaxRecurse) {
4162 if (auto *C = dyn_cast<Constant>(Op))
4163 return ConstantFoldCastOperand(CastOpc, C, Ty, Q.DL);
4164
4165 if (auto *CI = dyn_cast<CastInst>(Op)) {
4166 auto *Src = CI->getOperand(0);
4167 Type *SrcTy = Src->getType();
4168 Type *MidTy = CI->getType();
4169 Type *DstTy = Ty;
4170 if (Src->getType() == Ty) {
4171 auto FirstOp = static_cast<Instruction::CastOps>(CI->getOpcode());
4172 auto SecondOp = static_cast<Instruction::CastOps>(CastOpc);
4173 Type *SrcIntPtrTy =
4174 SrcTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(SrcTy) : nullptr;
4175 Type *MidIntPtrTy =
4176 MidTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(MidTy) : nullptr;
4177 Type *DstIntPtrTy =
4178 DstTy->isPtrOrPtrVectorTy() ? Q.DL.getIntPtrType(DstTy) : nullptr;
4179 if (CastInst::isEliminableCastPair(FirstOp, SecondOp, SrcTy, MidTy, DstTy,
4180 SrcIntPtrTy, MidIntPtrTy,
4181 DstIntPtrTy) == Instruction::BitCast)
4182 return Src;
4183 }
4184 }
4185
4186 // bitcast x -> x
4187 if (CastOpc == Instruction::BitCast)
4188 if (Op->getType() == Ty)
4189 return Op;
4190
4191 return nullptr;
4192}
4193
4194Value *llvm::SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
4195 const DataLayout &DL,
4196 const TargetLibraryInfo *TLI,
4197 const DominatorTree *DT, AssumptionCache *AC,
4198 const Instruction *CxtI) {
4199 return ::SimplifyCastInst(CastOpc, Op, Ty, {DL, TLI, DT, AC, CxtI},
4200 RecursionLimit);
4201}
4202
4203Value *llvm::SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
4204 const SimplifyQuery &Q) {
4205 return ::SimplifyCastInst(CastOpc, Op, Ty, Q, RecursionLimit);
4206}
4207
4208/// For the given destination element of a shuffle, peek through shuffles to
4209/// match a root vector source operand that contains that element in the same
4210/// vector lane (ie, the same mask index), so we can eliminate the shuffle(s).
4211static Value *foldIdentityShuffles(int DestElt, Value *Op0, Value *Op1,
4212 Constant *Mask, Value *RootVec, int RootElt,
4213 unsigned MaxRecurse) {
4214 if (!MaxRecurse--)
4215 return nullptr;
4216
4217 // Bail out if any mask value is undefined. That kind of shuffle may be
4218 // simplified further based on demanded bits or other folds.
4219 int MaskVal = ShuffleVectorInst::getMaskValue(Mask, RootElt);
4220 if (MaskVal == -1)
4221 return nullptr;
4222
4223 // The mask value chooses which source operand we need to look at next.
4224 Value *SourceOp;
4225 int InVecNumElts = Op0->getType()->getVectorNumElements();
4226 if (MaskVal < InVecNumElts) {
4227 RootElt = MaskVal;
4228 SourceOp = Op0;
4229 } else {
4230 RootElt = MaskVal - InVecNumElts;
4231 SourceOp = Op1;
4232 }
4233
4234 // If the source operand is a shuffle itself, look through it to find the
4235 // matching root vector.
4236 if (auto *SourceShuf = dyn_cast<ShuffleVectorInst>(SourceOp)) {
4237 return foldIdentityShuffles(
4238 DestElt, SourceShuf->getOperand(0), SourceShuf->getOperand(1),
4239 SourceShuf->getMask(), RootVec, RootElt, MaxRecurse);
4240 }
4241
4242 // TODO: Look through bitcasts? What if the bitcast changes the vector element
4243 // size?
4244
4245 // The source operand is not a shuffle. Initialize the root vector value for
4246 // this shuffle if that has not been done yet.
4247 if (!RootVec)
4248 RootVec = SourceOp;
4249
4250 // Give up as soon as a source operand does not match the existing root value.
4251 if (RootVec != SourceOp)
4252 return nullptr;
4253
4254 // The element must be coming from the same lane in the source vector
4255 // (although it may have crossed lanes in intermediate shuffles).
4256 if (RootElt != DestElt)
4257 return nullptr;
4258
4259 return RootVec;
4260}
4261
4262static Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
4263 Type *RetTy, const SimplifyQuery &Q,
4264 unsigned MaxRecurse) {
4265 Type *InVecTy = Op0->getType();
4266 unsigned MaskNumElts = Mask->getType()->getVectorNumElements();
4267 unsigned InVecNumElts = InVecTy->getVectorNumElements();
4268
4269 auto *Op0Const = dyn_cast<Constant>(Op0);
4270 auto *Op1Const = dyn_cast<Constant>(Op1);
4271
4272 // If all operands are constant, constant fold the shuffle.
4273 if (Op0Const && Op1Const)
4274 return ConstantFoldShuffleVectorInstruction(Op0Const, Op1Const, Mask);
4275
4276 // If only one of the operands is constant, constant fold the shuffle if the
4277 // mask does not select elements from the variable operand.
4278 bool MaskSelects0 = false, MaskSelects1 = false;
4279 for (unsigned i = 0; i != MaskNumElts; ++i) {
4280 int Idx = ShuffleVectorInst::getMaskValue(Mask, i);
4281 if (Idx == -1)
4282 continue;
4283 if ((unsigned)Idx < InVecNumElts)
4284 MaskSelects0 = true;
4285 else
4286 MaskSelects1 = true;
4287 }
4288 if (!MaskSelects0 && Op1Const)
4289 return ConstantFoldShuffleVectorInstruction(UndefValue::get(InVecTy),
4290 Op1Const, Mask);
4291 if (!MaskSelects1 && Op0Const)
4292 return ConstantFoldShuffleVectorInstruction(Op0Const,
4293 UndefValue::get(InVecTy), Mask);
4294
4295 // A shuffle of a splat is always the splat itself. Legal if the shuffle's
4296 // value type is same as the input vectors' type.
4297 if (auto *OpShuf = dyn_cast<ShuffleVectorInst>(Op0))
4298 if (!MaskSelects1 && RetTy == InVecTy &&
4299 OpShuf->getMask()->getSplatValue())
4300 return Op0;
4301 if (auto *OpShuf = dyn_cast<ShuffleVectorInst>(Op1))
4302 if (!MaskSelects0 && RetTy == InVecTy &&
4303 OpShuf->getMask()->getSplatValue())
4304 return Op1;
4305
4306 // Don't fold a shuffle with undef mask elements. This may get folded in a
4307 // better way using demanded bits or other analysis.
4308 // TODO: Should we allow this?
4309 for (unsigned i = 0; i != MaskNumElts; ++i)
4310 if (ShuffleVectorInst::getMaskValue(Mask, i) == -1)
4311 return nullptr;
4312
4313 // Check if every element of this shuffle can be mapped back to the
4314 // corresponding element of a single root vector. If so, we don't need this
4315 // shuffle. This handles simple identity shuffles as well as chains of
4316 // shuffles that may widen/narrow and/or move elements across lanes and back.
4317 Value *RootVec = nullptr;
4318 for (unsigned i = 0; i != MaskNumElts; ++i) {
4319 // Note that recursion is limited for each vector element, so if any element
4320 // exceeds the limit, this will fail to simplify.
4321 RootVec = foldIdentityShuffles(i, Op0, Op1, Mask, RootVec, i, MaxRecurse);
4322
4323 // We can't replace a widening/narrowing shuffle with one of its operands.
4324 if (!RootVec || RootVec->getType() != RetTy)
4325 return nullptr;
4326 }
4327 return RootVec;
4328}
4329
4330/// Given operands for a ShuffleVectorInst, fold the result or return null.
4331Value *llvm::SimplifyShuffleVectorInst(
4332 Value *Op0, Value *Op1, Constant *Mask, Type *RetTy,
4333 const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT,
4334 AssumptionCache *AC, const Instruction *CxtI) {
4335 return ::SimplifyShuffleVectorInst(Op0, Op1, Mask, RetTy,
4336 {DL, TLI, DT, AC, CxtI}, RecursionLimit);
4337}
4338
4339Value *llvm::SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
4340 Type *RetTy, const SimplifyQuery &Q) {
4341 return ::SimplifyShuffleVectorInst(Op0, Op1, Mask, RetTy, Q, RecursionLimit);
4342}
4343
4344//=== Helper functions for higher up the class hierarchy.
4345
4346/// Given operands for a BinaryOperator, see if we can fold the result.
4347/// If not, this returns null.
4348static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4349 const SimplifyQuery &Q, unsigned MaxRecurse) {
4350 switch (Opcode) {
4351 case Instruction::Add:
4352 return SimplifyAddInst(LHS, RHS, false, false, Q, MaxRecurse);
4353 case Instruction::FAdd:
4354 return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4355 case Instruction::Sub:
4356 return SimplifySubInst(LHS, RHS, false, false, Q, MaxRecurse);
4357 case Instruction::FSub:
4358 return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4359 case Instruction::Mul:
4360 return SimplifyMulInst(LHS, RHS, Q, MaxRecurse);
4361 case Instruction::FMul:
4362 return SimplifyFMulInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4363 case Instruction::SDiv:
4364 return SimplifySDivInst(LHS, RHS, Q, MaxRecurse);
4365 case Instruction::UDiv:
4366 return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse);
4367 case Instruction::FDiv:
4368 return SimplifyFDivInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4369 case Instruction::SRem:
4370 return SimplifySRemInst(LHS, RHS, Q, MaxRecurse);
4371 case Instruction::URem:
4372 return SimplifyURemInst(LHS, RHS, Q, MaxRecurse);
4373 case Instruction::FRem:
4374 return SimplifyFRemInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4375 case Instruction::Shl:
4376 return SimplifyShlInst(LHS, RHS, false, false, Q, MaxRecurse);
4377 case Instruction::LShr:
4378 return SimplifyLShrInst(LHS, RHS, false, Q, MaxRecurse);
4379 case Instruction::AShr:
4380 return SimplifyAShrInst(LHS, RHS, false, Q, MaxRecurse);
4381 case Instruction::And:
4382 return SimplifyAndInst(LHS, RHS, Q, MaxRecurse);
4383 case Instruction::Or:
4384 return SimplifyOrInst(LHS, RHS, Q, MaxRecurse);
4385 case Instruction::Xor:
4386 return SimplifyXorInst(LHS, RHS, Q, MaxRecurse);
4387 default:
4388 llvm_unreachable("Unexpected opcode")::llvm::llvm_unreachable_internal("Unexpected opcode", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 4388)
;
4389 }
4390}
4391
4392/// Given operands for a BinaryOperator, see if we can fold the result.
4393/// If not, this returns null.
4394/// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
4395/// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
4396static Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4397 const FastMathFlags &FMF, const SimplifyQuery &Q,
4398 unsigned MaxRecurse) {
4399 switch (Opcode) {
4400 case Instruction::FAdd:
4401 return SimplifyFAddInst(LHS, RHS, FMF, Q, MaxRecurse);
4402 case Instruction::FSub:
4403 return SimplifyFSubInst(LHS, RHS, FMF, Q, MaxRecurse);
4404 case Instruction::FMul:
4405 return SimplifyFMulInst(LHS, RHS, FMF, Q, MaxRecurse);
4406 case Instruction::FDiv:
4407 return SimplifyFDivInst(LHS, RHS, FMF, Q, MaxRecurse);
4408 default:
4409 return SimplifyBinOp(Opcode, LHS, RHS, Q, MaxRecurse);
4410 }
4411}
4412
4413Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4414 const DataLayout &DL, const TargetLibraryInfo *TLI,
4415 const DominatorTree *DT, AssumptionCache *AC,
4416 const Instruction *CxtI) {
4417 return ::SimplifyBinOp(Opcode, LHS, RHS, {DL, TLI, DT, AC, CxtI},
4418 RecursionLimit);
4419}
4420
4421Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4422 const SimplifyQuery &Q) {
4423 return ::SimplifyBinOp(Opcode, LHS, RHS, Q, RecursionLimit);
4424}
4425
4426Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4427 FastMathFlags FMF, const DataLayout &DL,
4428 const TargetLibraryInfo *TLI,
4429 const DominatorTree *DT, AssumptionCache *AC,
4430 const Instruction *CxtI) {
4431 return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, {DL, TLI, DT, AC, CxtI},
4432 RecursionLimit);
4433}
4434
4435Value *llvm::SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
4436 FastMathFlags FMF, const SimplifyQuery &Q) {
4437 return ::SimplifyFPBinOp(Opcode, LHS, RHS, FMF, Q, RecursionLimit);
4438}
4439
4440/// Given operands for a CmpInst, see if we can fold the result.
4441static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
4442 const SimplifyQuery &Q, unsigned MaxRecurse) {
4443 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
4444 return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse);
4445 return SimplifyFCmpInst(Predicate, LHS, RHS, FastMathFlags(), Q, MaxRecurse);
4446}
4447
4448Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
4449 const DataLayout &DL, const TargetLibraryInfo *TLI,
4450 const DominatorTree *DT, AssumptionCache *AC,
4451 const Instruction *CxtI) {
4452 return ::SimplifyCmpInst(Predicate, LHS, RHS, {DL, TLI, DT, AC, CxtI},
4453 RecursionLimit);
4454}
4455
4456Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
4457 const SimplifyQuery &Q) {
4458 return ::SimplifyCmpInst(Predicate, LHS, RHS, Q, RecursionLimit);
4459}
4460
4461static bool IsIdempotent(Intrinsic::ID ID) {
4462 switch (ID) {
4463 default: return false;
4464
4465 // Unary idempotent: f(f(x)) = f(x)
4466 case Intrinsic::fabs:
4467 case Intrinsic::floor:
4468 case Intrinsic::ceil:
4469 case Intrinsic::trunc:
4470 case Intrinsic::rint:
4471 case Intrinsic::nearbyint:
4472 case Intrinsic::round:
4473 return true;
4474 }
4475}
4476
4477static Value *SimplifyRelativeLoad(Constant *Ptr, Constant *Offset,
4478 const DataLayout &DL) {
4479 GlobalValue *PtrSym;
4480 APInt PtrOffset;
4481 if (!IsConstantOffsetFromGlobal(Ptr, PtrSym, PtrOffset, DL))
4482 return nullptr;
4483
4484 Type *Int8PtrTy = Type::getInt8PtrTy(Ptr->getContext());
4485 Type *Int32Ty = Type::getInt32Ty(Ptr->getContext());
4486 Type *Int32PtrTy = Int32Ty->getPointerTo();
4487 Type *Int64Ty = Type::getInt64Ty(Ptr->getContext());
4488
4489 auto *OffsetConstInt = dyn_cast<ConstantInt>(Offset);
4490 if (!OffsetConstInt || OffsetConstInt->getType()->getBitWidth() > 64)
4491 return nullptr;
4492
4493 uint64_t OffsetInt = OffsetConstInt->getSExtValue();
4494 if (OffsetInt % 4 != 0)
4495 return nullptr;
4496
4497 Constant *C = ConstantExpr::getGetElementPtr(
4498 Int32Ty, ConstantExpr::getBitCast(Ptr, Int32PtrTy),
4499 ConstantInt::get(Int64Ty, OffsetInt / 4));
4500 Constant *Loaded = ConstantFoldLoadFromConstPtr(C, Int32Ty, DL);
4501 if (!Loaded)
4502 return nullptr;
4503
4504 auto *LoadedCE = dyn_cast<ConstantExpr>(Loaded);
4505 if (!LoadedCE)
4506 return nullptr;
4507
4508 if (LoadedCE->getOpcode() == Instruction::Trunc) {
4509 LoadedCE = dyn_cast<ConstantExpr>(LoadedCE->getOperand(0));
4510 if (!LoadedCE)
4511 return nullptr;
4512 }
4513
4514 if (LoadedCE->getOpcode() != Instruction::Sub)
4515 return nullptr;
4516
4517 auto *LoadedLHS = dyn_cast<ConstantExpr>(LoadedCE->getOperand(0));
4518 if (!LoadedLHS || LoadedLHS->getOpcode() != Instruction::PtrToInt)
4519 return nullptr;
4520 auto *LoadedLHSPtr = LoadedLHS->getOperand(0);
4521
4522 Constant *LoadedRHS = LoadedCE->getOperand(1);
4523 GlobalValue *LoadedRHSSym;
4524 APInt LoadedRHSOffset;
4525 if (!IsConstantOffsetFromGlobal(LoadedRHS, LoadedRHSSym, LoadedRHSOffset,
4526 DL) ||
4527 PtrSym != LoadedRHSSym || PtrOffset != LoadedRHSOffset)
4528 return nullptr;
4529
4530 return ConstantExpr::getBitCast(LoadedLHSPtr, Int8PtrTy);
4531}
4532
4533static bool maskIsAllZeroOrUndef(Value *Mask) {
4534 auto *ConstMask = dyn_cast<Constant>(Mask);
4535 if (!ConstMask)
4536 return false;
4537 if (ConstMask->isNullValue() || isa<UndefValue>(ConstMask))
4538 return true;
4539 for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E;
4540 ++I) {
4541 if (auto *MaskElt = ConstMask->getAggregateElement(I))
4542 if (MaskElt->isNullValue() || isa<UndefValue>(MaskElt))
4543 continue;
4544 return false;
4545 }
4546 return true;
4547}
4548
4549template <typename IterTy>
4550static Value *SimplifyIntrinsic(Function *F, IterTy ArgBegin, IterTy ArgEnd,
4551 const SimplifyQuery &Q, unsigned MaxRecurse) {
4552 Intrinsic::ID IID = F->getIntrinsicID();
4553 unsigned NumOperands = std::distance(ArgBegin, ArgEnd);
4554
4555 // Unary Ops
4556 if (NumOperands == 1) {
4557 // Perform idempotent optimizations
4558 if (IsIdempotent(IID)) {
4559 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*ArgBegin)) {
4560 if (II->getIntrinsicID() == IID)
4561 return II;
4562 }
4563 }
4564
4565 switch (IID) {
4566 case Intrinsic::fabs: {
4567 if (SignBitMustBeZero(*ArgBegin, Q.TLI))
4568 return *ArgBegin;
4569 return nullptr;
4570 }
4571 default:
4572 return nullptr;
4573 }
4574 }
4575
4576 // Binary Ops
4577 if (NumOperands == 2) {
4578 Value *LHS = *ArgBegin;
4579 Value *RHS = *(ArgBegin + 1);
4580 Type *ReturnType = F->getReturnType();
4581
4582 switch (IID) {
4583 case Intrinsic::usub_with_overflow:
4584 case Intrinsic::ssub_with_overflow: {
4585 // X - X -> { 0, false }
4586 if (LHS == RHS)
4587 return Constant::getNullValue(ReturnType);
4588
4589 // X - undef -> undef
4590 // undef - X -> undef
4591 if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS))
4592 return UndefValue::get(ReturnType);
4593
4594 return nullptr;
4595 }
4596 case Intrinsic::uadd_with_overflow:
4597 case Intrinsic::sadd_with_overflow: {
4598 // X + undef -> undef
4599 if (isa<UndefValue>(RHS))
4600 return UndefValue::get(ReturnType);
4601
4602 return nullptr;
4603 }
4604 case Intrinsic::umul_with_overflow:
4605 case Intrinsic::smul_with_overflow: {
4606 // X * 0 -> { 0, false }
4607 if (match(RHS, m_Zero()))
4608 return Constant::getNullValue(ReturnType);
4609
4610 // X * undef -> { 0, false }
4611 if (match(RHS, m_Undef()))
4612 return Constant::getNullValue(ReturnType);
4613
4614 return nullptr;
4615 }
4616 case Intrinsic::load_relative: {
4617 Constant *C0 = dyn_cast<Constant>(LHS);
4618 Constant *C1 = dyn_cast<Constant>(RHS);
4619 if (C0 && C1)
4620 return SimplifyRelativeLoad(C0, C1, Q.DL);
4621 return nullptr;
4622 }
4623 default:
4624 return nullptr;
4625 }
4626 }
4627
4628 // Simplify calls to llvm.masked.load.*
4629 switch (IID) {
4630 case Intrinsic::masked_load: {
4631 Value *MaskArg = ArgBegin[2];
4632 Value *PassthruArg = ArgBegin[3];
4633 // If the mask is all zeros or undef, the "passthru" argument is the result.
4634 if (maskIsAllZeroOrUndef(MaskArg))
4635 return PassthruArg;
4636 return nullptr;
4637 }
4638 default:
4639 return nullptr;
4640 }
4641}
4642
4643template <typename IterTy>
4644static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd,
4645 const SimplifyQuery &Q, unsigned MaxRecurse) {
4646 Type *Ty = V->getType();
4647 if (PointerType *PTy = dyn_cast<PointerType>(Ty))
4648 Ty = PTy->getElementType();
4649 FunctionType *FTy = cast<FunctionType>(Ty);
4650
4651 // call undef -> undef
4652 // call null -> undef
4653 if (isa<UndefValue>(V) || isa<ConstantPointerNull>(V))
4654 return UndefValue::get(FTy->getReturnType());
4655
4656 Function *F = dyn_cast<Function>(V);
4657 if (!F)
4658 return nullptr;
4659
4660 if (F->isIntrinsic())
4661 if (Value *Ret = SimplifyIntrinsic(F, ArgBegin, ArgEnd, Q, MaxRecurse))
4662 return Ret;
4663
4664 if (!canConstantFoldCallTo(F))
4665 return nullptr;
4666
4667 SmallVector<Constant *, 4> ConstantArgs;
4668 ConstantArgs.reserve(ArgEnd - ArgBegin);
4669 for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) {
4670 Constant *C = dyn_cast<Constant>(*I);
4671 if (!C)
4672 return nullptr;
4673 ConstantArgs.push_back(C);
4674 }
4675
4676 return ConstantFoldCall(F, ConstantArgs, Q.TLI);
4677}
4678
4679Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin,
4680 User::op_iterator ArgEnd, const DataLayout &DL,
4681 const TargetLibraryInfo *TLI, const DominatorTree *DT,
4682 AssumptionCache *AC, const Instruction *CxtI) {
4683 return ::SimplifyCall(V, ArgBegin, ArgEnd, {DL, TLI, DT, AC, CxtI},
4684 RecursionLimit);
4685}
4686
4687Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin,
4688 User::op_iterator ArgEnd, const SimplifyQuery &Q) {
4689 return ::SimplifyCall(V, ArgBegin, ArgEnd, Q, RecursionLimit);
4690}
4691
4692Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args,
4693 const DataLayout &DL, const TargetLibraryInfo *TLI,
4694 const DominatorTree *DT, AssumptionCache *AC,
4695 const Instruction *CxtI) {
4696 return ::SimplifyCall(V, Args.begin(), Args.end(), {DL, TLI, DT, AC, CxtI},
4697 RecursionLimit);
4698}
4699
4700Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args,
4701 const SimplifyQuery &Q) {
4702 return ::SimplifyCall(V, Args.begin(), Args.end(), Q, RecursionLimit);
4703}
4704
4705/// See if we can compute a simplified version of this instruction.
4706/// If not, this returns null.
4707Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout &DL,
4708 const TargetLibraryInfo *TLI,
4709 const DominatorTree *DT, AssumptionCache *AC,
4710 OptimizationRemarkEmitter *ORE) {
4711 return SimplifyInstruction(I, {DL, TLI, DT, AC, I}, ORE);
4712}
4713
4714Value *llvm::SimplifyInstruction(Instruction *I, const SimplifyQuery &Q,
4715 OptimizationRemarkEmitter *ORE) {
4716 Value *Result;
4717
4718 switch (I->getOpcode()) {
4719 default:
4720 Result = ConstantFoldInstruction(I, Q.DL, Q.TLI);
4721 break;
4722 case Instruction::FAdd:
4723 Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1),
4724 I->getFastMathFlags(), Q);
4725 break;
4726 case Instruction::Add:
4727 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1),
4728 cast<BinaryOperator>(I)->hasNoSignedWrap(),
4729 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
4730 break;
4731 case Instruction::FSub:
4732 Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1),
4733 I->getFastMathFlags(), Q);
4734 break;
4735 case Instruction::Sub:
4736 Result = SimplifySubInst(I->getOperand(0), I->getOperand(1),
4737 cast<BinaryOperator>(I)->hasNoSignedWrap(),
4738 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
4739 break;
4740 case Instruction::FMul:
4741 Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1),
4742 I->getFastMathFlags(), Q);
4743 break;
4744 case Instruction::Mul:
4745 Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), Q);
4746 break;
4747 case Instruction::SDiv:
4748 Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), Q);
4749 break;
4750 case Instruction::UDiv:
4751 Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), Q);
4752 break;
4753 case Instruction::FDiv:
4754 Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1),
4755 I->getFastMathFlags(), Q);
4756 break;
4757 case Instruction::SRem:
4758 Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), Q);
4759 break;
4760 case Instruction::URem:
4761 Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), Q);
4762 break;
4763 case Instruction::FRem:
4764 Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1),
4765 I->getFastMathFlags(), Q);
4766 break;
4767 case Instruction::Shl:
4768 Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1),
4769 cast<BinaryOperator>(I)->hasNoSignedWrap(),
4770 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), Q);
4771 break;
4772 case Instruction::LShr:
4773 Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1),
4774 cast<BinaryOperator>(I)->isExact(), Q);
4775 break;
4776 case Instruction::AShr:
4777 Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1),
4778 cast<BinaryOperator>(I)->isExact(), Q);
4779 break;
4780 case Instruction::And:
4781 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), Q);
4782 break;
4783 case Instruction::Or:
4784 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), Q);
4785 break;
4786 case Instruction::Xor:
4787 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), Q);
4788 break;
4789 case Instruction::ICmp:
4790 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
4791 I->getOperand(0), I->getOperand(1), Q);
4792 break;
4793 case Instruction::FCmp:
4794 Result =
4795 SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), I->getOperand(0),
4796 I->getOperand(1), I->getFastMathFlags(), Q);
4797 break;
4798 case Instruction::Select:
4799 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1),
4800 I->getOperand(2), Q);
4801 break;
4802 case Instruction::GetElementPtr: {
4803 SmallVector<Value *, 8> Ops(I->op_begin(), I->op_end());
4804 Result = SimplifyGEPInst(cast<GetElementPtrInst>(I)->getSourceElementType(),
4805 Ops, Q);
4806 break;
4807 }
4808 case Instruction::InsertValue: {
4809 InsertValueInst *IV = cast<InsertValueInst>(I);
4810 Result = SimplifyInsertValueInst(IV->getAggregateOperand(),
4811 IV->getInsertedValueOperand(),
4812 IV->getIndices(), Q);
4813 break;
4814 }
4815 case Instruction::ExtractValue: {
4816 auto *EVI = cast<ExtractValueInst>(I);
4817 Result = SimplifyExtractValueInst(EVI->getAggregateOperand(),
4818 EVI->getIndices(), Q);
4819 break;
4820 }
4821 case Instruction::ExtractElement: {
4822 auto *EEI = cast<ExtractElementInst>(I);
4823 Result = SimplifyExtractElementInst(EEI->getVectorOperand(),
4824 EEI->getIndexOperand(), Q);
4825 break;
4826 }
4827 case Instruction::ShuffleVector: {
4828 auto *SVI = cast<ShuffleVectorInst>(I);
4829 Result = SimplifyShuffleVectorInst(SVI->getOperand(0), SVI->getOperand(1),
4830 SVI->getMask(), SVI->getType(), Q);
4831 break;
4832 }
4833 case Instruction::PHI:
4834 Result = SimplifyPHINode(cast<PHINode>(I), Q);
4835 break;
4836 case Instruction::Call: {
4837 CallSite CS(cast<CallInst>(I));
4838 Result = SimplifyCall(CS.getCalledValue(), CS.arg_begin(), CS.arg_end(), Q);
4839 break;
4840 }
4841#define HANDLE_CAST_INST(num, opc, clas) case Instruction::opc:
4842#include "llvm/IR/Instruction.def"
4843#undef HANDLE_CAST_INST
4844 Result =
4845 SimplifyCastInst(I->getOpcode(), I->getOperand(0), I->getType(), Q);
4846 break;
4847 case Instruction::Alloca:
4848 // No simplifications for Alloca and it can't be constant folded.
4849 Result = nullptr;
4850 break;
4851 }
4852
4853 // In general, it is possible for computeKnownBits to determine all bits in a
4854 // value even when the operands are not all constants.
4855 if (!Result && I->getType()->isIntOrIntVectorTy()) {
4856 unsigned BitWidth = I->getType()->getScalarSizeInBits();
4857 APInt KnownZero(BitWidth, 0);
4858 APInt KnownOne(BitWidth, 0);
4859 computeKnownBits(I, KnownZero, KnownOne, Q.DL, /*Depth*/ 0, Q.AC, I, Q.DT,
4860 ORE);
4861 if ((KnownZero | KnownOne).isAllOnesValue())
4862 Result = ConstantInt::get(I->getType(), KnownOne);
4863 }
4864
4865 /// If called on unreachable code, the above logic may report that the
4866 /// instruction simplified to itself. Make life easier for users by
4867 /// detecting that case here, returning a safe value instead.
4868 return Result == I ? UndefValue::get(I->getType()) : Result;
4869}
4870
4871/// \brief Implementation of recursive simplification through an instruction's
4872/// uses.
4873///
4874/// This is the common implementation of the recursive simplification routines.
4875/// If we have a pre-simplified value in 'SimpleV', that is forcibly used to
4876/// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of
4877/// instructions to process and attempt to simplify it using
4878/// InstructionSimplify.
4879///
4880/// This routine returns 'true' only when *it* simplifies something. The passed
4881/// in simplified value does not count toward this.
4882static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV,
4883 const TargetLibraryInfo *TLI,
4884 const DominatorTree *DT,
4885 AssumptionCache *AC) {
4886 bool Simplified = false;
4887 SmallSetVector<Instruction *, 8> Worklist;
4888 const DataLayout &DL = I->getModule()->getDataLayout();
4889
4890 // If we have an explicit value to collapse to, do that round of the
4891 // simplification loop by hand initially.
4892 if (SimpleV) {
4893 for (User *U : I->users())
4894 if (U != I)
4895 Worklist.insert(cast<Instruction>(U));
4896
4897 // Replace the instruction with its simplified value.
4898 I->replaceAllUsesWith(SimpleV);
4899
4900 // Gracefully handle edge cases where the instruction is not wired into any
4901 // parent block.
4902 if (I->getParent() && !I->isEHPad() && !isa<TerminatorInst>(I) &&
4903 !I->mayHaveSideEffects())
4904 I->eraseFromParent();
4905 } else {
4906 Worklist.insert(I);
4907 }
4908
4909 // Note that we must test the size on each iteration, the worklist can grow.
4910 for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
4911 I = Worklist[Idx];
4912
4913 // See if this instruction simplifies.
4914 SimpleV = SimplifyInstruction(I, DL, TLI, DT, AC);
4915 if (!SimpleV)
4916 continue;
4917
4918 Simplified = true;
4919
4920 // Stash away all the uses of the old instruction so we can check them for
4921 // recursive simplifications after a RAUW. This is cheaper than checking all
4922 // uses of To on the recursive step in most cases.
4923 for (User *U : I->users())
4924 Worklist.insert(cast<Instruction>(U));
4925
4926 // Replace the instruction with its simplified value.
4927 I->replaceAllUsesWith(SimpleV);
4928
4929 // Gracefully handle edge cases where the instruction is not wired into any
4930 // parent block.
4931 if (I->getParent() && !I->isEHPad() && !isa<TerminatorInst>(I) &&
4932 !I->mayHaveSideEffects())
4933 I->eraseFromParent();
4934 }
4935 return Simplified;
4936}
4937
4938bool llvm::recursivelySimplifyInstruction(Instruction *I,
4939 const TargetLibraryInfo *TLI,
4940 const DominatorTree *DT,
4941 AssumptionCache *AC) {
4942 return replaceAndRecursivelySimplifyImpl(I, nullptr, TLI, DT, AC);
4943}
4944
4945bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
4946 const TargetLibraryInfo *TLI,
4947 const DominatorTree *DT,
4948 AssumptionCache *AC) {
4949 assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!")((I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!"
) ? static_cast<void> (0) : __assert_fail ("I != SimpleV && \"replaceAndRecursivelySimplify(X,X) is not valid!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 4949, __PRETTY_FUNCTION__))
;
4950 assert(SimpleV && "Must provide a simplified value.")((SimpleV && "Must provide a simplified value.") ? static_cast
<void> (0) : __assert_fail ("SimpleV && \"Must provide a simplified value.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301389/lib/Analysis/InstructionSimplify.cpp"
, 4950, __PRETTY_FUNCTION__))
;
4951 return replaceAndRecursivelySimplifyImpl(I, SimpleV, TLI, DT, AC);
4952}