1//===- ConstantFold.cpp - LLVM constant folder ----------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements folding of constants for LLVM. This implements the
10// (internal) ConstantFold.h interface, which is used by the
11// ConstantExpr::get* methods to automatically fold constants when possible.
12//
13// The current constant folding implementation is implemented in two pieces: the
14// pieces that don't need DataLayout, and the pieces that do. This is to avoid
15// a dependence in IR on Target.
16//
17//===----------------------------------------------------------------------===//
18
19#include "llvm/IR/ConstantFold.h"
20#include "llvm/ADT/APSInt.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/IR/Constants.h"
23#include "llvm/IR/DerivedTypes.h"
24#include "llvm/IR/Function.h"
25#include "llvm/IR/GetElementPtrTypeIterator.h"
26#include "llvm/IR/GlobalAlias.h"
27#include "llvm/IR/GlobalVariable.h"
28#include "llvm/IR/Instructions.h"
29#include "llvm/IR/Module.h"
30#include "llvm/IR/Operator.h"
31#include "llvm/IR/PatternMatch.h"
32#include "llvm/Support/ErrorHandling.h"
33using namespace llvm;
34using namespace llvm::PatternMatch;
35
36//===----------------------------------------------------------------------===//
37// ConstantFold*Instruction Implementations
38//===----------------------------------------------------------------------===//
39
40/// This function determines which opcode to use to fold two constant cast
41/// expressions together. It uses CastInst::isEliminableCastPair to determine
42/// the opcode. Consequently its just a wrapper around that function.
43/// Determine if it is valid to fold a cast of a cast
44static unsigned
45foldConstantCastPair(
46 unsigned opc, ///< opcode of the second cast constant expression
47 ConstantExpr *Op, ///< the first cast constant expression
48 Type *DstTy ///< destination type of the first cast
49) {
50 assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!");
51 assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type");
52 assert(CastInst::isCast(opc) && "Invalid cast opcode");
53
54 // The types and opcodes for the two Cast constant expressions
55 Type *SrcTy = Op->getOperand(i_nocapture: 0)->getType();
56 Type *MidTy = Op->getType();
57 Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode());
58 Instruction::CastOps secondOp = Instruction::CastOps(opc);
59
60 // Assume that pointers are never more than 64 bits wide, and only use this
61 // for the middle type. Otherwise we could end up folding away illegal
62 // bitcasts between address spaces with different sizes.
63 IntegerType *FakeIntPtrTy = Type::getInt64Ty(C&: DstTy->getContext());
64
65 // Let CastInst::isEliminableCastPair do the heavy lifting.
66 return CastInst::isEliminableCastPair(firstOpcode: firstOp, secondOpcode: secondOp, SrcTy, MidTy, DstTy,
67 SrcIntPtrTy: nullptr, MidIntPtrTy: FakeIntPtrTy, DstIntPtrTy: nullptr);
68}
69
70static Constant *FoldBitCast(Constant *V, Type *DestTy) {
71 Type *SrcTy = V->getType();
72 if (SrcTy == DestTy)
73 return V; // no-op cast
74
75 // Handle casts from one vector constant to another. We know that the src
76 // and dest type have the same size (otherwise its an illegal cast).
77 if (VectorType *DestPTy = dyn_cast<VectorType>(Val: DestTy)) {
78 if (V->isAllOnesValue())
79 return Constant::getAllOnesValue(Ty: DestTy);
80
81 // Canonicalize scalar-to-vector bitcasts into vector-to-vector bitcasts
82 // This allows for other simplifications (although some of them
83 // can only be handled by Analysis/ConstantFolding.cpp).
84 if (isa<ConstantInt>(Val: V) || isa<ConstantFP>(Val: V))
85 return ConstantExpr::getBitCast(C: ConstantVector::get(V), Ty: DestPTy);
86 return nullptr;
87 }
88
89 // Handle integral constant input.
90 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: V)) {
91 // See note below regarding the PPC_FP128 restriction.
92 if (DestTy->isFloatingPointTy() && !DestTy->isPPC_FP128Ty())
93 return ConstantFP::get(Context&: DestTy->getContext(),
94 V: APFloat(DestTy->getFltSemantics(),
95 CI->getValue()));
96
97 // Otherwise, can't fold this (vector?)
98 return nullptr;
99 }
100
101 // Handle ConstantFP input: FP -> Integral.
102 if (ConstantFP *FP = dyn_cast<ConstantFP>(Val: V)) {
103 // PPC_FP128 is really the sum of two consecutive doubles, where the first
104 // double is always stored first in memory, regardless of the target
105 // endianness. The memory layout of i128, however, depends on the target
106 // endianness, and so we can't fold this without target endianness
107 // information. This should instead be handled by
108 // Analysis/ConstantFolding.cpp
109 if (FP->getType()->isPPC_FP128Ty())
110 return nullptr;
111
112 // Make sure dest type is compatible with the folded integer constant.
113 if (!DestTy->isIntegerTy())
114 return nullptr;
115
116 return ConstantInt::get(Context&: FP->getContext(),
117 V: FP->getValueAPF().bitcastToAPInt());
118 }
119
120 return nullptr;
121}
122
123static Constant *foldMaybeUndesirableCast(unsigned opc, Constant *V,
124 Type *DestTy) {
125 return ConstantExpr::isDesirableCastOp(Opcode: opc)
126 ? ConstantExpr::getCast(ops: opc, C: V, Ty: DestTy)
127 : ConstantFoldCastInstruction(opcode: opc, V, DestTy);
128}
129
130Constant *llvm::ConstantFoldCastInstruction(unsigned opc, Constant *V,
131 Type *DestTy) {
132 if (isa<PoisonValue>(Val: V))
133 return PoisonValue::get(T: DestTy);
134
135 if (isa<UndefValue>(Val: V)) {
136 // zext(undef) = 0, because the top bits will be zero.
137 // sext(undef) = 0, because the top bits will all be the same.
138 // [us]itofp(undef) = 0, because the result value is bounded.
139 if (opc == Instruction::ZExt || opc == Instruction::SExt ||
140 opc == Instruction::UIToFP || opc == Instruction::SIToFP)
141 return Constant::getNullValue(Ty: DestTy);
142 return UndefValue::get(T: DestTy);
143 }
144
145 if (V->isNullValue() && !DestTy->isX86_MMXTy() && !DestTy->isX86_AMXTy() &&
146 opc != Instruction::AddrSpaceCast)
147 return Constant::getNullValue(Ty: DestTy);
148
149 // If the cast operand is a constant expression, there's a few things we can
150 // do to try to simplify it.
151 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Val: V)) {
152 if (CE->isCast()) {
153 // Try hard to fold cast of cast because they are often eliminable.
154 if (unsigned newOpc = foldConstantCastPair(opc, Op: CE, DstTy: DestTy))
155 return foldMaybeUndesirableCast(opc: newOpc, V: CE->getOperand(i_nocapture: 0), DestTy);
156 }
157 }
158
159 // If the cast operand is a constant vector, perform the cast by
160 // operating on each element. In the cast of bitcasts, the element
161 // count may be mismatched; don't attempt to handle that here.
162 if ((isa<ConstantVector>(Val: V) || isa<ConstantDataVector>(Val: V)) &&
163 DestTy->isVectorTy() &&
164 cast<FixedVectorType>(Val: DestTy)->getNumElements() ==
165 cast<FixedVectorType>(Val: V->getType())->getNumElements()) {
166 VectorType *DestVecTy = cast<VectorType>(Val: DestTy);
167 Type *DstEltTy = DestVecTy->getElementType();
168 // Fast path for splatted constants.
169 if (Constant *Splat = V->getSplatValue()) {
170 Constant *Res = foldMaybeUndesirableCast(opc, V: Splat, DestTy: DstEltTy);
171 if (!Res)
172 return nullptr;
173 return ConstantVector::getSplat(
174 EC: cast<VectorType>(Val: DestTy)->getElementCount(), Elt: Res);
175 }
176 SmallVector<Constant *, 16> res;
177 Type *Ty = IntegerType::get(C&: V->getContext(), NumBits: 32);
178 for (unsigned i = 0,
179 e = cast<FixedVectorType>(Val: V->getType())->getNumElements();
180 i != e; ++i) {
181 Constant *C = ConstantExpr::getExtractElement(Vec: V, Idx: ConstantInt::get(Ty, V: i));
182 Constant *Casted = foldMaybeUndesirableCast(opc, V: C, DestTy: DstEltTy);
183 if (!Casted)
184 return nullptr;
185 res.push_back(Elt: Casted);
186 }
187 return ConstantVector::get(V: res);
188 }
189
190 // We actually have to do a cast now. Perform the cast according to the
191 // opcode specified.
192 switch (opc) {
193 default:
194 llvm_unreachable("Failed to cast constant expression");
195 case Instruction::FPTrunc:
196 case Instruction::FPExt:
197 if (ConstantFP *FPC = dyn_cast<ConstantFP>(Val: V)) {
198 bool ignored;
199 APFloat Val = FPC->getValueAPF();
200 Val.convert(ToSemantics: DestTy->getFltSemantics(), RM: APFloat::rmNearestTiesToEven,
201 losesInfo: &ignored);
202 return ConstantFP::get(Context&: V->getContext(), V: Val);
203 }
204 return nullptr; // Can't fold.
205 case Instruction::FPToUI:
206 case Instruction::FPToSI:
207 if (ConstantFP *FPC = dyn_cast<ConstantFP>(Val: V)) {
208 const APFloat &V = FPC->getValueAPF();
209 bool ignored;
210 uint32_t DestBitWidth = cast<IntegerType>(Val: DestTy)->getBitWidth();
211 APSInt IntVal(DestBitWidth, opc == Instruction::FPToUI);
212 if (APFloat::opInvalidOp ==
213 V.convertToInteger(Result&: IntVal, RM: APFloat::rmTowardZero, IsExact: &ignored)) {
214 // Undefined behavior invoked - the destination type can't represent
215 // the input constant.
216 return PoisonValue::get(T: DestTy);
217 }
218 return ConstantInt::get(Context&: FPC->getContext(), V: IntVal);
219 }
220 return nullptr; // Can't fold.
221 case Instruction::UIToFP:
222 case Instruction::SIToFP:
223 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: V)) {
224 const APInt &api = CI->getValue();
225 APFloat apf(DestTy->getFltSemantics(),
226 APInt::getZero(numBits: DestTy->getPrimitiveSizeInBits()));
227 apf.convertFromAPInt(Input: api, IsSigned: opc==Instruction::SIToFP,
228 RM: APFloat::rmNearestTiesToEven);
229 return ConstantFP::get(Context&: V->getContext(), V: apf);
230 }
231 return nullptr;
232 case Instruction::ZExt:
233 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: V)) {
234 uint32_t BitWidth = cast<IntegerType>(Val: DestTy)->getBitWidth();
235 return ConstantInt::get(Context&: V->getContext(),
236 V: CI->getValue().zext(width: BitWidth));
237 }
238 return nullptr;
239 case Instruction::SExt:
240 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: V)) {
241 uint32_t BitWidth = cast<IntegerType>(Val: DestTy)->getBitWidth();
242 return ConstantInt::get(Context&: V->getContext(),
243 V: CI->getValue().sext(width: BitWidth));
244 }
245 return nullptr;
246 case Instruction::Trunc: {
247 if (V->getType()->isVectorTy())
248 return nullptr;
249
250 uint32_t DestBitWidth = cast<IntegerType>(Val: DestTy)->getBitWidth();
251 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: V)) {
252 return ConstantInt::get(Context&: V->getContext(),
253 V: CI->getValue().trunc(width: DestBitWidth));
254 }
255
256 return nullptr;
257 }
258 case Instruction::BitCast:
259 return FoldBitCast(V, DestTy);
260 case Instruction::AddrSpaceCast:
261 case Instruction::IntToPtr:
262 case Instruction::PtrToInt:
263 return nullptr;
264 }
265}
266
267Constant *llvm::ConstantFoldSelectInstruction(Constant *Cond,
268 Constant *V1, Constant *V2) {
269 // Check for i1 and vector true/false conditions.
270 if (Cond->isNullValue()) return V2;
271 if (Cond->isAllOnesValue()) return V1;
272
273 // If the condition is a vector constant, fold the result elementwise.
274 if (ConstantVector *CondV = dyn_cast<ConstantVector>(Val: Cond)) {
275 auto *V1VTy = CondV->getType();
276 SmallVector<Constant*, 16> Result;
277 Type *Ty = IntegerType::get(C&: CondV->getContext(), NumBits: 32);
278 for (unsigned i = 0, e = V1VTy->getNumElements(); i != e; ++i) {
279 Constant *V;
280 Constant *V1Element = ConstantExpr::getExtractElement(Vec: V1,
281 Idx: ConstantInt::get(Ty, V: i));
282 Constant *V2Element = ConstantExpr::getExtractElement(Vec: V2,
283 Idx: ConstantInt::get(Ty, V: i));
284 auto *Cond = cast<Constant>(Val: CondV->getOperand(i_nocapture: i));
285 if (isa<PoisonValue>(Val: Cond)) {
286 V = PoisonValue::get(T: V1Element->getType());
287 } else if (V1Element == V2Element) {
288 V = V1Element;
289 } else if (isa<UndefValue>(Val: Cond)) {
290 V = isa<UndefValue>(Val: V1Element) ? V1Element : V2Element;
291 } else {
292 if (!isa<ConstantInt>(Val: Cond)) break;
293 V = Cond->isNullValue() ? V2Element : V1Element;
294 }
295 Result.push_back(Elt: V);
296 }
297
298 // If we were able to build the vector, return it.
299 if (Result.size() == V1VTy->getNumElements())
300 return ConstantVector::get(V: Result);
301 }
302
303 if (isa<PoisonValue>(Val: Cond))
304 return PoisonValue::get(T: V1->getType());
305
306 if (isa<UndefValue>(Val: Cond)) {
307 if (isa<UndefValue>(Val: V1)) return V1;
308 return V2;
309 }
310
311 if (V1 == V2) return V1;
312
313 if (isa<PoisonValue>(Val: V1))
314 return V2;
315 if (isa<PoisonValue>(Val: V2))
316 return V1;
317
318 // If the true or false value is undef, we can fold to the other value as
319 // long as the other value isn't poison.
320 auto NotPoison = [](Constant *C) {
321 if (isa<PoisonValue>(Val: C))
322 return false;
323
324 // TODO: We can analyze ConstExpr by opcode to determine if there is any
325 // possibility of poison.
326 if (isa<ConstantExpr>(Val: C))
327 return false;
328
329 if (isa<ConstantInt>(Val: C) || isa<GlobalVariable>(Val: C) || isa<ConstantFP>(Val: C) ||
330 isa<ConstantPointerNull>(Val: C) || isa<Function>(Val: C))
331 return true;
332
333 if (C->getType()->isVectorTy())
334 return !C->containsPoisonElement() && !C->containsConstantExpression();
335
336 // TODO: Recursively analyze aggregates or other constants.
337 return false;
338 };
339 if (isa<UndefValue>(Val: V1) && NotPoison(V2)) return V2;
340 if (isa<UndefValue>(Val: V2) && NotPoison(V1)) return V1;
341
342 return nullptr;
343}
344
345Constant *llvm::ConstantFoldExtractElementInstruction(Constant *Val,
346 Constant *Idx) {
347 auto *ValVTy = cast<VectorType>(Val: Val->getType());
348
349 // extractelt poison, C -> poison
350 // extractelt C, undef -> poison
351 if (isa<PoisonValue>(Val) || isa<UndefValue>(Val: Idx))
352 return PoisonValue::get(T: ValVTy->getElementType());
353
354 // extractelt undef, C -> undef
355 if (isa<UndefValue>(Val))
356 return UndefValue::get(T: ValVTy->getElementType());
357
358 auto *CIdx = dyn_cast<ConstantInt>(Val: Idx);
359 if (!CIdx)
360 return nullptr;
361
362 if (auto *ValFVTy = dyn_cast<FixedVectorType>(Val: Val->getType())) {
363 // ee({w,x,y,z}, wrong_value) -> poison
364 if (CIdx->uge(Num: ValFVTy->getNumElements()))
365 return PoisonValue::get(T: ValFVTy->getElementType());
366 }
367
368 // ee (gep (ptr, idx0, ...), idx) -> gep (ee (ptr, idx), ee (idx0, idx), ...)
369 if (auto *CE = dyn_cast<ConstantExpr>(Val)) {
370 if (auto *GEP = dyn_cast<GEPOperator>(Val: CE)) {
371 SmallVector<Constant *, 8> Ops;
372 Ops.reserve(N: CE->getNumOperands());
373 for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) {
374 Constant *Op = CE->getOperand(i_nocapture: i);
375 if (Op->getType()->isVectorTy()) {
376 Constant *ScalarOp = ConstantExpr::getExtractElement(Vec: Op, Idx);
377 if (!ScalarOp)
378 return nullptr;
379 Ops.push_back(Elt: ScalarOp);
380 } else
381 Ops.push_back(Elt: Op);
382 }
383 return CE->getWithOperands(Ops, Ty: ValVTy->getElementType(), OnlyIfReduced: false,
384 SrcTy: GEP->getSourceElementType());
385 } else if (CE->getOpcode() == Instruction::InsertElement) {
386 if (const auto *IEIdx = dyn_cast<ConstantInt>(Val: CE->getOperand(i_nocapture: 2))) {
387 if (APSInt::isSameValue(I1: APSInt(IEIdx->getValue()),
388 I2: APSInt(CIdx->getValue()))) {
389 return CE->getOperand(i_nocapture: 1);
390 } else {
391 return ConstantExpr::getExtractElement(Vec: CE->getOperand(i_nocapture: 0), Idx: CIdx);
392 }
393 }
394 }
395 }
396
397 if (Constant *C = Val->getAggregateElement(Elt: CIdx))
398 return C;
399
400 // Lane < Splat minimum vector width => extractelt Splat(x), Lane -> x
401 if (CIdx->getValue().ult(RHS: ValVTy->getElementCount().getKnownMinValue())) {
402 if (Constant *SplatVal = Val->getSplatValue())
403 return SplatVal;
404 }
405
406 return nullptr;
407}
408
409Constant *llvm::ConstantFoldInsertElementInstruction(Constant *Val,
410 Constant *Elt,
411 Constant *Idx) {
412 if (isa<UndefValue>(Val: Idx))
413 return PoisonValue::get(T: Val->getType());
414
415 // Inserting null into all zeros is still all zeros.
416 // TODO: This is true for undef and poison splats too.
417 if (isa<ConstantAggregateZero>(Val) && Elt->isNullValue())
418 return Val;
419
420 ConstantInt *CIdx = dyn_cast<ConstantInt>(Val: Idx);
421 if (!CIdx) return nullptr;
422
423 // Do not iterate on scalable vector. The num of elements is unknown at
424 // compile-time.
425 if (isa<ScalableVectorType>(Val: Val->getType()))
426 return nullptr;
427
428 auto *ValTy = cast<FixedVectorType>(Val: Val->getType());
429
430 unsigned NumElts = ValTy->getNumElements();
431 if (CIdx->uge(Num: NumElts))
432 return PoisonValue::get(T: Val->getType());
433
434 SmallVector<Constant*, 16> Result;
435 Result.reserve(N: NumElts);
436 auto *Ty = Type::getInt32Ty(C&: Val->getContext());
437 uint64_t IdxVal = CIdx->getZExtValue();
438 for (unsigned i = 0; i != NumElts; ++i) {
439 if (i == IdxVal) {
440 Result.push_back(Elt);
441 continue;
442 }
443
444 Constant *C = ConstantExpr::getExtractElement(Vec: Val, Idx: ConstantInt::get(Ty, V: i));
445 Result.push_back(Elt: C);
446 }
447
448 return ConstantVector::get(V: Result);
449}
450
451Constant *llvm::ConstantFoldShuffleVectorInstruction(Constant *V1, Constant *V2,
452 ArrayRef<int> Mask) {
453 auto *V1VTy = cast<VectorType>(Val: V1->getType());
454 unsigned MaskNumElts = Mask.size();
455 auto MaskEltCount =
456 ElementCount::get(MinVal: MaskNumElts, Scalable: isa<ScalableVectorType>(Val: V1VTy));
457 Type *EltTy = V1VTy->getElementType();
458
459 // Poison shuffle mask -> poison value.
460 if (all_of(Range&: Mask, P: [](int Elt) { return Elt == PoisonMaskElem; })) {
461 return PoisonValue::get(T: VectorType::get(ElementType: EltTy, EC: MaskEltCount));
462 }
463
464 // If the mask is all zeros this is a splat, no need to go through all
465 // elements.
466 if (all_of(Range&: Mask, P: [](int Elt) { return Elt == 0; })) {
467 Type *Ty = IntegerType::get(C&: V1->getContext(), NumBits: 32);
468 Constant *Elt =
469 ConstantExpr::getExtractElement(Vec: V1, Idx: ConstantInt::get(Ty, V: 0));
470
471 if (Elt->isNullValue()) {
472 auto *VTy = VectorType::get(ElementType: EltTy, EC: MaskEltCount);
473 return ConstantAggregateZero::get(Ty: VTy);
474 } else if (!MaskEltCount.isScalable())
475 return ConstantVector::getSplat(EC: MaskEltCount, Elt);
476 }
477
478 // Do not iterate on scalable vector. The num of elements is unknown at
479 // compile-time.
480 if (isa<ScalableVectorType>(Val: V1VTy))
481 return nullptr;
482
483 unsigned SrcNumElts = V1VTy->getElementCount().getKnownMinValue();
484
485 // Loop over the shuffle mask, evaluating each element.
486 SmallVector<Constant*, 32> Result;
487 for (unsigned i = 0; i != MaskNumElts; ++i) {
488 int Elt = Mask[i];
489 if (Elt == -1) {
490 Result.push_back(Elt: UndefValue::get(T: EltTy));
491 continue;
492 }
493 Constant *InElt;
494 if (unsigned(Elt) >= SrcNumElts*2)
495 InElt = UndefValue::get(T: EltTy);
496 else if (unsigned(Elt) >= SrcNumElts) {
497 Type *Ty = IntegerType::get(C&: V2->getContext(), NumBits: 32);
498 InElt =
499 ConstantExpr::getExtractElement(Vec: V2,
500 Idx: ConstantInt::get(Ty, V: Elt - SrcNumElts));
501 } else {
502 Type *Ty = IntegerType::get(C&: V1->getContext(), NumBits: 32);
503 InElt = ConstantExpr::getExtractElement(Vec: V1, Idx: ConstantInt::get(Ty, V: Elt));
504 }
505 Result.push_back(Elt: InElt);
506 }
507
508 return ConstantVector::get(V: Result);
509}
510
511Constant *llvm::ConstantFoldExtractValueInstruction(Constant *Agg,
512 ArrayRef<unsigned> Idxs) {
513 // Base case: no indices, so return the entire value.
514 if (Idxs.empty())
515 return Agg;
516
517 if (Constant *C = Agg->getAggregateElement(Elt: Idxs[0]))
518 return ConstantFoldExtractValueInstruction(Agg: C, Idxs: Idxs.slice(N: 1));
519
520 return nullptr;
521}
522
523Constant *llvm::ConstantFoldInsertValueInstruction(Constant *Agg,
524 Constant *Val,
525 ArrayRef<unsigned> Idxs) {
526 // Base case: no indices, so replace the entire value.
527 if (Idxs.empty())
528 return Val;
529
530 unsigned NumElts;
531 if (StructType *ST = dyn_cast<StructType>(Val: Agg->getType()))
532 NumElts = ST->getNumElements();
533 else
534 NumElts = cast<ArrayType>(Val: Agg->getType())->getNumElements();
535
536 SmallVector<Constant*, 32> Result;
537 for (unsigned i = 0; i != NumElts; ++i) {
538 Constant *C = Agg->getAggregateElement(Elt: i);
539 if (!C) return nullptr;
540
541 if (Idxs[0] == i)
542 C = ConstantFoldInsertValueInstruction(Agg: C, Val, Idxs: Idxs.slice(N: 1));
543
544 Result.push_back(Elt: C);
545 }
546
547 if (StructType *ST = dyn_cast<StructType>(Val: Agg->getType()))
548 return ConstantStruct::get(T: ST, V: Result);
549 return ConstantArray::get(T: cast<ArrayType>(Val: Agg->getType()), V: Result);
550}
551
552Constant *llvm::ConstantFoldUnaryInstruction(unsigned Opcode, Constant *C) {
553 assert(Instruction::isUnaryOp(Opcode) && "Non-unary instruction detected");
554
555 // Handle scalar UndefValue and scalable vector UndefValue. Fixed-length
556 // vectors are always evaluated per element.
557 bool IsScalableVector = isa<ScalableVectorType>(Val: C->getType());
558 bool HasScalarUndefOrScalableVectorUndef =
559 (!C->getType()->isVectorTy() || IsScalableVector) && isa<UndefValue>(Val: C);
560
561 if (HasScalarUndefOrScalableVectorUndef) {
562 switch (static_cast<Instruction::UnaryOps>(Opcode)) {
563 case Instruction::FNeg:
564 return C; // -undef -> undef
565 case Instruction::UnaryOpsEnd:
566 llvm_unreachable("Invalid UnaryOp");
567 }
568 }
569
570 // Constant should not be UndefValue, unless these are vector constants.
571 assert(!HasScalarUndefOrScalableVectorUndef && "Unexpected UndefValue");
572 // We only have FP UnaryOps right now.
573 assert(!isa<ConstantInt>(C) && "Unexpected Integer UnaryOp");
574
575 if (ConstantFP *CFP = dyn_cast<ConstantFP>(Val: C)) {
576 const APFloat &CV = CFP->getValueAPF();
577 switch (Opcode) {
578 default:
579 break;
580 case Instruction::FNeg:
581 return ConstantFP::get(Context&: C->getContext(), V: neg(X: CV));
582 }
583 } else if (auto *VTy = dyn_cast<FixedVectorType>(Val: C->getType())) {
584
585 Type *Ty = IntegerType::get(C&: VTy->getContext(), NumBits: 32);
586 // Fast path for splatted constants.
587 if (Constant *Splat = C->getSplatValue())
588 if (Constant *Elt = ConstantFoldUnaryInstruction(Opcode, C: Splat))
589 return ConstantVector::getSplat(EC: VTy->getElementCount(), Elt);
590
591 // Fold each element and create a vector constant from those constants.
592 SmallVector<Constant *, 16> Result;
593 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
594 Constant *ExtractIdx = ConstantInt::get(Ty, V: i);
595 Constant *Elt = ConstantExpr::getExtractElement(Vec: C, Idx: ExtractIdx);
596 Constant *Res = ConstantFoldUnaryInstruction(Opcode, C: Elt);
597 if (!Res)
598 return nullptr;
599 Result.push_back(Elt: Res);
600 }
601
602 return ConstantVector::get(V: Result);
603 }
604
605 // We don't know how to fold this.
606 return nullptr;
607}
608
609Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode, Constant *C1,
610 Constant *C2) {
611 assert(Instruction::isBinaryOp(Opcode) && "Non-binary instruction detected");
612
613 // Simplify BinOps with their identity values first. They are no-ops and we
614 // can always return the other value, including undef or poison values.
615 if (Constant *Identity = ConstantExpr::getBinOpIdentity(
616 Opcode, Ty: C1->getType(), /*AllowRHSIdentity*/ AllowRHSConstant: false)) {
617 if (C1 == Identity)
618 return C2;
619 if (C2 == Identity)
620 return C1;
621 } else if (Constant *Identity = ConstantExpr::getBinOpIdentity(
622 Opcode, Ty: C1->getType(), /*AllowRHSIdentity*/ AllowRHSConstant: true)) {
623 if (C2 == Identity)
624 return C1;
625 }
626
627 // Binary operations propagate poison.
628 if (isa<PoisonValue>(Val: C1) || isa<PoisonValue>(Val: C2))
629 return PoisonValue::get(T: C1->getType());
630
631 // Handle scalar UndefValue and scalable vector UndefValue. Fixed-length
632 // vectors are always evaluated per element.
633 bool IsScalableVector = isa<ScalableVectorType>(Val: C1->getType());
634 bool HasScalarUndefOrScalableVectorUndef =
635 (!C1->getType()->isVectorTy() || IsScalableVector) &&
636 (isa<UndefValue>(Val: C1) || isa<UndefValue>(Val: C2));
637 if (HasScalarUndefOrScalableVectorUndef) {
638 switch (static_cast<Instruction::BinaryOps>(Opcode)) {
639 case Instruction::Xor:
640 if (isa<UndefValue>(Val: C1) && isa<UndefValue>(Val: C2))
641 // Handle undef ^ undef -> 0 special case. This is a common
642 // idiom (misuse).
643 return Constant::getNullValue(Ty: C1->getType());
644 [[fallthrough]];
645 case Instruction::Add:
646 case Instruction::Sub:
647 return UndefValue::get(T: C1->getType());
648 case Instruction::And:
649 if (isa<UndefValue>(Val: C1) && isa<UndefValue>(Val: C2)) // undef & undef -> undef
650 return C1;
651 return Constant::getNullValue(Ty: C1->getType()); // undef & X -> 0
652 case Instruction::Mul: {
653 // undef * undef -> undef
654 if (isa<UndefValue>(Val: C1) && isa<UndefValue>(Val: C2))
655 return C1;
656 const APInt *CV;
657 // X * undef -> undef if X is odd
658 if (match(V: C1, P: m_APInt(Res&: CV)) || match(V: C2, P: m_APInt(Res&: CV)))
659 if ((*CV)[0])
660 return UndefValue::get(T: C1->getType());
661
662 // X * undef -> 0 otherwise
663 return Constant::getNullValue(Ty: C1->getType());
664 }
665 case Instruction::SDiv:
666 case Instruction::UDiv:
667 // X / undef -> poison
668 // X / 0 -> poison
669 if (match(V: C2, P: m_CombineOr(L: m_Undef(), R: m_Zero())))
670 return PoisonValue::get(T: C2->getType());
671 // undef / X -> 0 otherwise
672 return Constant::getNullValue(Ty: C1->getType());
673 case Instruction::URem:
674 case Instruction::SRem:
675 // X % undef -> poison
676 // X % 0 -> poison
677 if (match(V: C2, P: m_CombineOr(L: m_Undef(), R: m_Zero())))
678 return PoisonValue::get(T: C2->getType());
679 // undef % X -> 0 otherwise
680 return Constant::getNullValue(Ty: C1->getType());
681 case Instruction::Or: // X | undef -> -1
682 if (isa<UndefValue>(Val: C1) && isa<UndefValue>(Val: C2)) // undef | undef -> undef
683 return C1;
684 return Constant::getAllOnesValue(Ty: C1->getType()); // undef | X -> ~0
685 case Instruction::LShr:
686 // X >>l undef -> poison
687 if (isa<UndefValue>(Val: C2))
688 return PoisonValue::get(T: C2->getType());
689 // undef >>l X -> 0
690 return Constant::getNullValue(Ty: C1->getType());
691 case Instruction::AShr:
692 // X >>a undef -> poison
693 if (isa<UndefValue>(Val: C2))
694 return PoisonValue::get(T: C2->getType());
695 // TODO: undef >>a X -> poison if the shift is exact
696 // undef >>a X -> 0
697 return Constant::getNullValue(Ty: C1->getType());
698 case Instruction::Shl:
699 // X << undef -> undef
700 if (isa<UndefValue>(Val: C2))
701 return PoisonValue::get(T: C2->getType());
702 // undef << X -> 0
703 return Constant::getNullValue(Ty: C1->getType());
704 case Instruction::FSub:
705 // -0.0 - undef --> undef (consistent with "fneg undef")
706 if (match(V: C1, P: m_NegZeroFP()) && isa<UndefValue>(Val: C2))
707 return C2;
708 [[fallthrough]];
709 case Instruction::FAdd:
710 case Instruction::FMul:
711 case Instruction::FDiv:
712 case Instruction::FRem:
713 // [any flop] undef, undef -> undef
714 if (isa<UndefValue>(Val: C1) && isa<UndefValue>(Val: C2))
715 return C1;
716 // [any flop] C, undef -> NaN
717 // [any flop] undef, C -> NaN
718 // We could potentially specialize NaN/Inf constants vs. 'normal'
719 // constants (possibly differently depending on opcode and operand). This
720 // would allow returning undef sometimes. But it is always safe to fold to
721 // NaN because we can choose the undef operand as NaN, and any FP opcode
722 // with a NaN operand will propagate NaN.
723 return ConstantFP::getNaN(Ty: C1->getType());
724 case Instruction::BinaryOpsEnd:
725 llvm_unreachable("Invalid BinaryOp");
726 }
727 }
728
729 // Neither constant should be UndefValue, unless these are vector constants.
730 assert((!HasScalarUndefOrScalableVectorUndef) && "Unexpected UndefValue");
731
732 // Handle simplifications when the RHS is a constant int.
733 if (ConstantInt *CI2 = dyn_cast<ConstantInt>(Val: C2)) {
734 switch (Opcode) {
735 case Instruction::Mul:
736 if (CI2->isZero())
737 return C2; // X * 0 == 0
738 break;
739 case Instruction::UDiv:
740 case Instruction::SDiv:
741 if (CI2->isZero())
742 return PoisonValue::get(T: CI2->getType()); // X / 0 == poison
743 break;
744 case Instruction::URem:
745 case Instruction::SRem:
746 if (CI2->isOne())
747 return Constant::getNullValue(Ty: CI2->getType()); // X % 1 == 0
748 if (CI2->isZero())
749 return PoisonValue::get(T: CI2->getType()); // X % 0 == poison
750 break;
751 case Instruction::And:
752 if (CI2->isZero())
753 return C2; // X & 0 == 0
754
755 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(Val: C1)) {
756 // If and'ing the address of a global with a constant, fold it.
757 if (CE1->getOpcode() == Instruction::PtrToInt &&
758 isa<GlobalValue>(Val: CE1->getOperand(i_nocapture: 0))) {
759 GlobalValue *GV = cast<GlobalValue>(Val: CE1->getOperand(i_nocapture: 0));
760
761 Align GVAlign; // defaults to 1
762
763 if (Module *TheModule = GV->getParent()) {
764 const DataLayout &DL = TheModule->getDataLayout();
765 GVAlign = GV->getPointerAlignment(DL);
766
767 // If the function alignment is not specified then assume that it
768 // is 4.
769 // This is dangerous; on x86, the alignment of the pointer
770 // corresponds to the alignment of the function, but might be less
771 // than 4 if it isn't explicitly specified.
772 // However, a fix for this behaviour was reverted because it
773 // increased code size (see https://reviews.llvm.org/D55115)
774 // FIXME: This code should be deleted once existing targets have
775 // appropriate defaults
776 if (isa<Function>(Val: GV) && !DL.getFunctionPtrAlign())
777 GVAlign = Align(4);
778 } else if (isa<GlobalVariable>(Val: GV)) {
779 GVAlign = cast<GlobalVariable>(Val: GV)->getAlign().valueOrOne();
780 }
781
782 if (GVAlign > 1) {
783 unsigned DstWidth = CI2->getBitWidth();
784 unsigned SrcWidth = std::min(a: DstWidth, b: Log2(A: GVAlign));
785 APInt BitsNotSet(APInt::getLowBitsSet(numBits: DstWidth, loBitsSet: SrcWidth));
786
787 // If checking bits we know are clear, return zero.
788 if ((CI2->getValue() & BitsNotSet) == CI2->getValue())
789 return Constant::getNullValue(Ty: CI2->getType());
790 }
791 }
792 }
793 break;
794 case Instruction::Or:
795 if (CI2->isMinusOne())
796 return C2; // X | -1 == -1
797 break;
798 }
799 } else if (isa<ConstantInt>(Val: C1)) {
800 // If C1 is a ConstantInt and C2 is not, swap the operands.
801 if (Instruction::isCommutative(Opcode))
802 return ConstantExpr::isDesirableBinOp(Opcode)
803 ? ConstantExpr::get(Opcode, C1: C2, C2: C1)
804 : ConstantFoldBinaryInstruction(Opcode, C1: C2, C2: C1);
805 }
806
807 if (ConstantInt *CI1 = dyn_cast<ConstantInt>(Val: C1)) {
808 if (ConstantInt *CI2 = dyn_cast<ConstantInt>(Val: C2)) {
809 const APInt &C1V = CI1->getValue();
810 const APInt &C2V = CI2->getValue();
811 switch (Opcode) {
812 default:
813 break;
814 case Instruction::Add:
815 return ConstantInt::get(Context&: CI1->getContext(), V: C1V + C2V);
816 case Instruction::Sub:
817 return ConstantInt::get(Context&: CI1->getContext(), V: C1V - C2V);
818 case Instruction::Mul:
819 return ConstantInt::get(Context&: CI1->getContext(), V: C1V * C2V);
820 case Instruction::UDiv:
821 assert(!CI2->isZero() && "Div by zero handled above");
822 return ConstantInt::get(Context&: CI1->getContext(), V: C1V.udiv(RHS: C2V));
823 case Instruction::SDiv:
824 assert(!CI2->isZero() && "Div by zero handled above");
825 if (C2V.isAllOnes() && C1V.isMinSignedValue())
826 return PoisonValue::get(T: CI1->getType()); // MIN_INT / -1 -> poison
827 return ConstantInt::get(Context&: CI1->getContext(), V: C1V.sdiv(RHS: C2V));
828 case Instruction::URem:
829 assert(!CI2->isZero() && "Div by zero handled above");
830 return ConstantInt::get(Context&: CI1->getContext(), V: C1V.urem(RHS: C2V));
831 case Instruction::SRem:
832 assert(!CI2->isZero() && "Div by zero handled above");
833 if (C2V.isAllOnes() && C1V.isMinSignedValue())
834 return PoisonValue::get(T: CI1->getType()); // MIN_INT % -1 -> poison
835 return ConstantInt::get(Context&: CI1->getContext(), V: C1V.srem(RHS: C2V));
836 case Instruction::And:
837 return ConstantInt::get(Context&: CI1->getContext(), V: C1V & C2V);
838 case Instruction::Or:
839 return ConstantInt::get(Context&: CI1->getContext(), V: C1V | C2V);
840 case Instruction::Xor:
841 return ConstantInt::get(Context&: CI1->getContext(), V: C1V ^ C2V);
842 case Instruction::Shl:
843 if (C2V.ult(RHS: C1V.getBitWidth()))
844 return ConstantInt::get(Context&: CI1->getContext(), V: C1V.shl(ShiftAmt: C2V));
845 return PoisonValue::get(T: C1->getType()); // too big shift is poison
846 case Instruction::LShr:
847 if (C2V.ult(RHS: C1V.getBitWidth()))
848 return ConstantInt::get(Context&: CI1->getContext(), V: C1V.lshr(ShiftAmt: C2V));
849 return PoisonValue::get(T: C1->getType()); // too big shift is poison
850 case Instruction::AShr:
851 if (C2V.ult(RHS: C1V.getBitWidth()))
852 return ConstantInt::get(Context&: CI1->getContext(), V: C1V.ashr(ShiftAmt: C2V));
853 return PoisonValue::get(T: C1->getType()); // too big shift is poison
854 }
855 }
856
857 switch (Opcode) {
858 case Instruction::SDiv:
859 case Instruction::UDiv:
860 case Instruction::URem:
861 case Instruction::SRem:
862 case Instruction::LShr:
863 case Instruction::AShr:
864 case Instruction::Shl:
865 if (CI1->isZero()) return C1;
866 break;
867 default:
868 break;
869 }
870 } else if (ConstantFP *CFP1 = dyn_cast<ConstantFP>(Val: C1)) {
871 if (ConstantFP *CFP2 = dyn_cast<ConstantFP>(Val: C2)) {
872 const APFloat &C1V = CFP1->getValueAPF();
873 const APFloat &C2V = CFP2->getValueAPF();
874 APFloat C3V = C1V; // copy for modification
875 switch (Opcode) {
876 default:
877 break;
878 case Instruction::FAdd:
879 (void)C3V.add(RHS: C2V, RM: APFloat::rmNearestTiesToEven);
880 return ConstantFP::get(Context&: C1->getContext(), V: C3V);
881 case Instruction::FSub:
882 (void)C3V.subtract(RHS: C2V, RM: APFloat::rmNearestTiesToEven);
883 return ConstantFP::get(Context&: C1->getContext(), V: C3V);
884 case Instruction::FMul:
885 (void)C3V.multiply(RHS: C2V, RM: APFloat::rmNearestTiesToEven);
886 return ConstantFP::get(Context&: C1->getContext(), V: C3V);
887 case Instruction::FDiv:
888 (void)C3V.divide(RHS: C2V, RM: APFloat::rmNearestTiesToEven);
889 return ConstantFP::get(Context&: C1->getContext(), V: C3V);
890 case Instruction::FRem:
891 (void)C3V.mod(RHS: C2V);
892 return ConstantFP::get(Context&: C1->getContext(), V: C3V);
893 }
894 }
895 } else if (auto *VTy = dyn_cast<VectorType>(Val: C1->getType())) {
896 // Fast path for splatted constants.
897 if (Constant *C2Splat = C2->getSplatValue()) {
898 if (Instruction::isIntDivRem(Opcode) && C2Splat->isNullValue())
899 return PoisonValue::get(T: VTy);
900 if (Constant *C1Splat = C1->getSplatValue()) {
901 Constant *Res =
902 ConstantExpr::isDesirableBinOp(Opcode)
903 ? ConstantExpr::get(Opcode, C1: C1Splat, C2: C2Splat)
904 : ConstantFoldBinaryInstruction(Opcode, C1: C1Splat, C2: C2Splat);
905 if (!Res)
906 return nullptr;
907 return ConstantVector::getSplat(EC: VTy->getElementCount(), Elt: Res);
908 }
909 }
910
911 if (auto *FVTy = dyn_cast<FixedVectorType>(Val: VTy)) {
912 // Fold each element and create a vector constant from those constants.
913 SmallVector<Constant*, 16> Result;
914 Type *Ty = IntegerType::get(C&: FVTy->getContext(), NumBits: 32);
915 for (unsigned i = 0, e = FVTy->getNumElements(); i != e; ++i) {
916 Constant *ExtractIdx = ConstantInt::get(Ty, V: i);
917 Constant *LHS = ConstantExpr::getExtractElement(Vec: C1, Idx: ExtractIdx);
918 Constant *RHS = ConstantExpr::getExtractElement(Vec: C2, Idx: ExtractIdx);
919
920 // If any element of a divisor vector is zero, the whole op is poison.
921 if (Instruction::isIntDivRem(Opcode) && RHS->isNullValue())
922 return PoisonValue::get(T: VTy);
923
924 Constant *Res = ConstantExpr::isDesirableBinOp(Opcode)
925 ? ConstantExpr::get(Opcode, C1: LHS, C2: RHS)
926 : ConstantFoldBinaryInstruction(Opcode, C1: LHS, C2: RHS);
927 if (!Res)
928 return nullptr;
929 Result.push_back(Elt: Res);
930 }
931
932 return ConstantVector::get(V: Result);
933 }
934 }
935
936 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(Val: C1)) {
937 // There are many possible foldings we could do here. We should probably
938 // at least fold add of a pointer with an integer into the appropriate
939 // getelementptr. This will improve alias analysis a bit.
940
941 // Given ((a + b) + c), if (b + c) folds to something interesting, return
942 // (a + (b + c)).
943 if (Instruction::isAssociative(Opcode) && CE1->getOpcode() == Opcode) {
944 Constant *T = ConstantExpr::get(Opcode, C1: CE1->getOperand(i_nocapture: 1), C2);
945 if (!isa<ConstantExpr>(Val: T) || cast<ConstantExpr>(Val: T)->getOpcode() != Opcode)
946 return ConstantExpr::get(Opcode, C1: CE1->getOperand(i_nocapture: 0), C2: T);
947 }
948 } else if (isa<ConstantExpr>(Val: C2)) {
949 // If C2 is a constant expr and C1 isn't, flop them around and fold the
950 // other way if possible.
951 if (Instruction::isCommutative(Opcode))
952 return ConstantFoldBinaryInstruction(Opcode, C1: C2, C2: C1);
953 }
954
955 // i1 can be simplified in many cases.
956 if (C1->getType()->isIntegerTy(Bitwidth: 1)) {
957 switch (Opcode) {
958 case Instruction::Add:
959 case Instruction::Sub:
960 return ConstantExpr::getXor(C1, C2);
961 case Instruction::Shl:
962 case Instruction::LShr:
963 case Instruction::AShr:
964 // We can assume that C2 == 0. If it were one the result would be
965 // undefined because the shift value is as large as the bitwidth.
966 return C1;
967 case Instruction::SDiv:
968 case Instruction::UDiv:
969 // We can assume that C2 == 1. If it were zero the result would be
970 // undefined through division by zero.
971 return C1;
972 case Instruction::URem:
973 case Instruction::SRem:
974 // We can assume that C2 == 1. If it were zero the result would be
975 // undefined through division by zero.
976 return ConstantInt::getFalse(Context&: C1->getContext());
977 default:
978 break;
979 }
980 }
981
982 // We don't know how to fold this.
983 return nullptr;
984}
985
986static ICmpInst::Predicate areGlobalsPotentiallyEqual(const GlobalValue *GV1,
987 const GlobalValue *GV2) {
988 auto isGlobalUnsafeForEquality = [](const GlobalValue *GV) {
989 if (GV->isInterposable() || GV->hasGlobalUnnamedAddr())
990 return true;
991 if (const auto *GVar = dyn_cast<GlobalVariable>(Val: GV)) {
992 Type *Ty = GVar->getValueType();
993 // A global with opaque type might end up being zero sized.
994 if (!Ty->isSized())
995 return true;
996 // A global with an empty type might lie at the address of any other
997 // global.
998 if (Ty->isEmptyTy())
999 return true;
1000 }
1001 return false;
1002 };
1003 // Don't try to decide equality of aliases.
1004 if (!isa<GlobalAlias>(Val: GV1) && !isa<GlobalAlias>(Val: GV2))
1005 if (!isGlobalUnsafeForEquality(GV1) && !isGlobalUnsafeForEquality(GV2))
1006 return ICmpInst::ICMP_NE;
1007 return ICmpInst::BAD_ICMP_PREDICATE;
1008}
1009
1010/// This function determines if there is anything we can decide about the two
1011/// constants provided. This doesn't need to handle simple things like integer
1012/// comparisons, but should instead handle ConstantExprs and GlobalValues.
1013/// If we can determine that the two constants have a particular relation to
1014/// each other, we should return the corresponding ICmp predicate, otherwise
1015/// return ICmpInst::BAD_ICMP_PREDICATE.
1016static ICmpInst::Predicate evaluateICmpRelation(Constant *V1, Constant *V2) {
1017 assert(V1->getType() == V2->getType() &&
1018 "Cannot compare different types of values!");
1019 if (V1 == V2) return ICmpInst::ICMP_EQ;
1020
1021 // The following folds only apply to pointers.
1022 if (!V1->getType()->isPointerTy())
1023 return ICmpInst::BAD_ICMP_PREDICATE;
1024
1025 // To simplify this code we canonicalize the relation so that the first
1026 // operand is always the most "complex" of the two. We consider simple
1027 // constants (like ConstantPointerNull) to be the simplest, followed by
1028 // BlockAddress, GlobalValues, and ConstantExpr's (the most complex).
1029 auto GetComplexity = [](Constant *V) {
1030 if (isa<ConstantExpr>(Val: V))
1031 return 3;
1032 if (isa<GlobalValue>(Val: V))
1033 return 2;
1034 if (isa<BlockAddress>(Val: V))
1035 return 1;
1036 return 0;
1037 };
1038 if (GetComplexity(V1) < GetComplexity(V2)) {
1039 ICmpInst::Predicate SwappedRelation = evaluateICmpRelation(V1: V2, V2: V1);
1040 if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE)
1041 return ICmpInst::getSwappedPredicate(pred: SwappedRelation);
1042 return ICmpInst::BAD_ICMP_PREDICATE;
1043 }
1044
1045 if (const BlockAddress *BA = dyn_cast<BlockAddress>(Val: V1)) {
1046 // Now we know that the RHS is a BlockAddress or simple constant.
1047 if (const BlockAddress *BA2 = dyn_cast<BlockAddress>(Val: V2)) {
1048 // Block address in another function can't equal this one, but block
1049 // addresses in the current function might be the same if blocks are
1050 // empty.
1051 if (BA2->getFunction() != BA->getFunction())
1052 return ICmpInst::ICMP_NE;
1053 } else if (isa<ConstantPointerNull>(Val: V2)) {
1054 return ICmpInst::ICMP_NE;
1055 }
1056 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(Val: V1)) {
1057 // Now we know that the RHS is a GlobalValue, BlockAddress or simple
1058 // constant.
1059 if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(Val: V2)) {
1060 return areGlobalsPotentiallyEqual(GV1: GV, GV2);
1061 } else if (isa<BlockAddress>(Val: V2)) {
1062 return ICmpInst::ICMP_NE; // Globals never equal labels.
1063 } else if (isa<ConstantPointerNull>(Val: V2)) {
1064 // GlobalVals can never be null unless they have external weak linkage.
1065 // We don't try to evaluate aliases here.
1066 // NOTE: We should not be doing this constant folding if null pointer
1067 // is considered valid for the function. But currently there is no way to
1068 // query it from the Constant type.
1069 if (!GV->hasExternalWeakLinkage() && !isa<GlobalAlias>(Val: GV) &&
1070 !NullPointerIsDefined(F: nullptr /* F */,
1071 AS: GV->getType()->getAddressSpace()))
1072 return ICmpInst::ICMP_UGT;
1073 }
1074 } else if (auto *CE1 = dyn_cast<ConstantExpr>(Val: V1)) {
1075 // Ok, the LHS is known to be a constantexpr. The RHS can be any of a
1076 // constantexpr, a global, block address, or a simple constant.
1077 Constant *CE1Op0 = CE1->getOperand(i_nocapture: 0);
1078
1079 switch (CE1->getOpcode()) {
1080 case Instruction::GetElementPtr: {
1081 GEPOperator *CE1GEP = cast<GEPOperator>(Val: CE1);
1082 // Ok, since this is a getelementptr, we know that the constant has a
1083 // pointer type. Check the various cases.
1084 if (isa<ConstantPointerNull>(Val: V2)) {
1085 // If we are comparing a GEP to a null pointer, check to see if the base
1086 // of the GEP equals the null pointer.
1087 if (const GlobalValue *GV = dyn_cast<GlobalValue>(Val: CE1Op0)) {
1088 // If its not weak linkage, the GVal must have a non-zero address
1089 // so the result is greater-than
1090 if (!GV->hasExternalWeakLinkage() && CE1GEP->isInBounds())
1091 return ICmpInst::ICMP_UGT;
1092 }
1093 } else if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(Val: V2)) {
1094 if (const GlobalValue *GV = dyn_cast<GlobalValue>(Val: CE1Op0)) {
1095 if (GV != GV2) {
1096 if (CE1GEP->hasAllZeroIndices())
1097 return areGlobalsPotentiallyEqual(GV1: GV, GV2);
1098 return ICmpInst::BAD_ICMP_PREDICATE;
1099 }
1100 }
1101 } else if (const auto *CE2GEP = dyn_cast<GEPOperator>(Val: V2)) {
1102 // By far the most common case to handle is when the base pointers are
1103 // obviously to the same global.
1104 const Constant *CE2Op0 = cast<Constant>(Val: CE2GEP->getPointerOperand());
1105 if (isa<GlobalValue>(Val: CE1Op0) && isa<GlobalValue>(Val: CE2Op0)) {
1106 // Don't know relative ordering, but check for inequality.
1107 if (CE1Op0 != CE2Op0) {
1108 if (CE1GEP->hasAllZeroIndices() && CE2GEP->hasAllZeroIndices())
1109 return areGlobalsPotentiallyEqual(GV1: cast<GlobalValue>(Val: CE1Op0),
1110 GV2: cast<GlobalValue>(Val: CE2Op0));
1111 return ICmpInst::BAD_ICMP_PREDICATE;
1112 }
1113 }
1114 }
1115 break;
1116 }
1117 default:
1118 break;
1119 }
1120 }
1121
1122 return ICmpInst::BAD_ICMP_PREDICATE;
1123}
1124
1125Constant *llvm::ConstantFoldCompareInstruction(CmpInst::Predicate Predicate,
1126 Constant *C1, Constant *C2) {
1127 Type *ResultTy;
1128 if (VectorType *VT = dyn_cast<VectorType>(Val: C1->getType()))
1129 ResultTy = VectorType::get(ElementType: Type::getInt1Ty(C&: C1->getContext()),
1130 EC: VT->getElementCount());
1131 else
1132 ResultTy = Type::getInt1Ty(C&: C1->getContext());
1133
1134 // Fold FCMP_FALSE/FCMP_TRUE unconditionally.
1135 if (Predicate == FCmpInst::FCMP_FALSE)
1136 return Constant::getNullValue(Ty: ResultTy);
1137
1138 if (Predicate == FCmpInst::FCMP_TRUE)
1139 return Constant::getAllOnesValue(Ty: ResultTy);
1140
1141 // Handle some degenerate cases first
1142 if (isa<PoisonValue>(Val: C1) || isa<PoisonValue>(Val: C2))
1143 return PoisonValue::get(T: ResultTy);
1144
1145 if (isa<UndefValue>(Val: C1) || isa<UndefValue>(Val: C2)) {
1146 bool isIntegerPredicate = ICmpInst::isIntPredicate(P: Predicate);
1147 // For EQ and NE, we can always pick a value for the undef to make the
1148 // predicate pass or fail, so we can return undef.
1149 // Also, if both operands are undef, we can return undef for int comparison.
1150 if (ICmpInst::isEquality(P: Predicate) || (isIntegerPredicate && C1 == C2))
1151 return UndefValue::get(T: ResultTy);
1152
1153 // Otherwise, for integer compare, pick the same value as the non-undef
1154 // operand, and fold it to true or false.
1155 if (isIntegerPredicate)
1156 return ConstantInt::get(Ty: ResultTy, V: CmpInst::isTrueWhenEqual(predicate: Predicate));
1157
1158 // Choosing NaN for the undef will always make unordered comparison succeed
1159 // and ordered comparison fails.
1160 return ConstantInt::get(Ty: ResultTy, V: CmpInst::isUnordered(predicate: Predicate));
1161 }
1162
1163 if (C2->isNullValue()) {
1164 // The caller is expected to commute the operands if the constant expression
1165 // is C2.
1166 // C1 >= 0 --> true
1167 if (Predicate == ICmpInst::ICMP_UGE)
1168 return Constant::getAllOnesValue(Ty: ResultTy);
1169 // C1 < 0 --> false
1170 if (Predicate == ICmpInst::ICMP_ULT)
1171 return Constant::getNullValue(Ty: ResultTy);
1172 }
1173
1174 // If the comparison is a comparison between two i1's, simplify it.
1175 if (C1->getType()->isIntegerTy(Bitwidth: 1)) {
1176 switch (Predicate) {
1177 case ICmpInst::ICMP_EQ:
1178 if (isa<ConstantInt>(Val: C2))
1179 return ConstantExpr::getXor(C1, C2: ConstantExpr::getNot(C: C2));
1180 return ConstantExpr::getXor(C1: ConstantExpr::getNot(C: C1), C2);
1181 case ICmpInst::ICMP_NE:
1182 return ConstantExpr::getXor(C1, C2);
1183 default:
1184 break;
1185 }
1186 }
1187
1188 if (isa<ConstantInt>(Val: C1) && isa<ConstantInt>(Val: C2)) {
1189 const APInt &V1 = cast<ConstantInt>(Val: C1)->getValue();
1190 const APInt &V2 = cast<ConstantInt>(Val: C2)->getValue();
1191 return ConstantInt::get(Ty: ResultTy, V: ICmpInst::compare(LHS: V1, RHS: V2, Pred: Predicate));
1192 } else if (isa<ConstantFP>(Val: C1) && isa<ConstantFP>(Val: C2)) {
1193 const APFloat &C1V = cast<ConstantFP>(Val: C1)->getValueAPF();
1194 const APFloat &C2V = cast<ConstantFP>(Val: C2)->getValueAPF();
1195 return ConstantInt::get(Ty: ResultTy, V: FCmpInst::compare(LHS: C1V, RHS: C2V, Pred: Predicate));
1196 } else if (auto *C1VTy = dyn_cast<VectorType>(Val: C1->getType())) {
1197
1198 // Fast path for splatted constants.
1199 if (Constant *C1Splat = C1->getSplatValue())
1200 if (Constant *C2Splat = C2->getSplatValue())
1201 if (Constant *Elt =
1202 ConstantFoldCompareInstruction(Predicate, C1: C1Splat, C2: C2Splat))
1203 return ConstantVector::getSplat(EC: C1VTy->getElementCount(), Elt);
1204
1205 // Do not iterate on scalable vector. The number of elements is unknown at
1206 // compile-time.
1207 if (isa<ScalableVectorType>(Val: C1VTy))
1208 return nullptr;
1209
1210 // If we can constant fold the comparison of each element, constant fold
1211 // the whole vector comparison.
1212 SmallVector<Constant*, 4> ResElts;
1213 Type *Ty = IntegerType::get(C&: C1->getContext(), NumBits: 32);
1214 // Compare the elements, producing an i1 result or constant expr.
1215 for (unsigned I = 0, E = C1VTy->getElementCount().getKnownMinValue();
1216 I != E; ++I) {
1217 Constant *C1E =
1218 ConstantExpr::getExtractElement(Vec: C1, Idx: ConstantInt::get(Ty, V: I));
1219 Constant *C2E =
1220 ConstantExpr::getExtractElement(Vec: C2, Idx: ConstantInt::get(Ty, V: I));
1221 Constant *Elt = ConstantFoldCompareInstruction(Predicate, C1: C1E, C2: C2E);
1222 if (!Elt)
1223 return nullptr;
1224
1225 ResElts.push_back(Elt);
1226 }
1227
1228 return ConstantVector::get(V: ResElts);
1229 }
1230
1231 if (C1->getType()->isFPOrFPVectorTy()) {
1232 if (C1 == C2) {
1233 // We know that C1 == C2 || isUnordered(C1, C2).
1234 if (Predicate == FCmpInst::FCMP_ONE)
1235 return ConstantInt::getFalse(Ty: ResultTy);
1236 else if (Predicate == FCmpInst::FCMP_UEQ)
1237 return ConstantInt::getTrue(Ty: ResultTy);
1238 }
1239 } else {
1240 // Evaluate the relation between the two constants, per the predicate.
1241 int Result = -1; // -1 = unknown, 0 = known false, 1 = known true.
1242 switch (evaluateICmpRelation(V1: C1, V2: C2)) {
1243 default: llvm_unreachable("Unknown relational!");
1244 case ICmpInst::BAD_ICMP_PREDICATE:
1245 break; // Couldn't determine anything about these constants.
1246 case ICmpInst::ICMP_EQ: // We know the constants are equal!
1247 // If we know the constants are equal, we can decide the result of this
1248 // computation precisely.
1249 Result = ICmpInst::isTrueWhenEqual(predicate: Predicate);
1250 break;
1251 case ICmpInst::ICMP_ULT:
1252 switch (Predicate) {
1253 case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_ULE:
1254 Result = 1; break;
1255 case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_UGE:
1256 Result = 0; break;
1257 default:
1258 break;
1259 }
1260 break;
1261 case ICmpInst::ICMP_SLT:
1262 switch (Predicate) {
1263 case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SLE:
1264 Result = 1; break;
1265 case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SGE:
1266 Result = 0; break;
1267 default:
1268 break;
1269 }
1270 break;
1271 case ICmpInst::ICMP_UGT:
1272 switch (Predicate) {
1273 case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_UGE:
1274 Result = 1; break;
1275 case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_ULE:
1276 Result = 0; break;
1277 default:
1278 break;
1279 }
1280 break;
1281 case ICmpInst::ICMP_SGT:
1282 switch (Predicate) {
1283 case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SGE:
1284 Result = 1; break;
1285 case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SLE:
1286 Result = 0; break;
1287 default:
1288 break;
1289 }
1290 break;
1291 case ICmpInst::ICMP_ULE:
1292 if (Predicate == ICmpInst::ICMP_UGT)
1293 Result = 0;
1294 if (Predicate == ICmpInst::ICMP_ULT || Predicate == ICmpInst::ICMP_ULE)
1295 Result = 1;
1296 break;
1297 case ICmpInst::ICMP_SLE:
1298 if (Predicate == ICmpInst::ICMP_SGT)
1299 Result = 0;
1300 if (Predicate == ICmpInst::ICMP_SLT || Predicate == ICmpInst::ICMP_SLE)
1301 Result = 1;
1302 break;
1303 case ICmpInst::ICMP_UGE:
1304 if (Predicate == ICmpInst::ICMP_ULT)
1305 Result = 0;
1306 if (Predicate == ICmpInst::ICMP_UGT || Predicate == ICmpInst::ICMP_UGE)
1307 Result = 1;
1308 break;
1309 case ICmpInst::ICMP_SGE:
1310 if (Predicate == ICmpInst::ICMP_SLT)
1311 Result = 0;
1312 if (Predicate == ICmpInst::ICMP_SGT || Predicate == ICmpInst::ICMP_SGE)
1313 Result = 1;
1314 break;
1315 case ICmpInst::ICMP_NE:
1316 if (Predicate == ICmpInst::ICMP_EQ)
1317 Result = 0;
1318 if (Predicate == ICmpInst::ICMP_NE)
1319 Result = 1;
1320 break;
1321 }
1322
1323 // If we evaluated the result, return it now.
1324 if (Result != -1)
1325 return ConstantInt::get(Ty: ResultTy, V: Result);
1326
1327 if ((!isa<ConstantExpr>(Val: C1) && isa<ConstantExpr>(Val: C2)) ||
1328 (C1->isNullValue() && !C2->isNullValue())) {
1329 // If C2 is a constant expr and C1 isn't, flip them around and fold the
1330 // other way if possible.
1331 // Also, if C1 is null and C2 isn't, flip them around.
1332 Predicate = ICmpInst::getSwappedPredicate(pred: Predicate);
1333 return ConstantFoldCompareInstruction(Predicate, C1: C2, C2: C1);
1334 }
1335 }
1336 return nullptr;
1337}
1338
1339Constant *llvm::ConstantFoldGetElementPtr(Type *PointeeTy, Constant *C,
1340 std::optional<ConstantRange> InRange,
1341 ArrayRef<Value *> Idxs) {
1342 if (Idxs.empty()) return C;
1343
1344 Type *GEPTy = GetElementPtrInst::getGEPReturnType(
1345 Ptr: C, IdxList: ArrayRef((Value *const *)Idxs.data(), Idxs.size()));
1346
1347 if (isa<PoisonValue>(Val: C))
1348 return PoisonValue::get(T: GEPTy);
1349
1350 if (isa<UndefValue>(Val: C))
1351 return UndefValue::get(T: GEPTy);
1352
1353 auto IsNoOp = [&]() {
1354 // Avoid losing inrange information.
1355 if (InRange)
1356 return false;
1357
1358 return all_of(Range&: Idxs, P: [](Value *Idx) {
1359 Constant *IdxC = cast<Constant>(Val: Idx);
1360 return IdxC->isNullValue() || isa<UndefValue>(Val: IdxC);
1361 });
1362 };
1363 if (IsNoOp())
1364 return GEPTy->isVectorTy() && !C->getType()->isVectorTy()
1365 ? ConstantVector::getSplat(
1366 EC: cast<VectorType>(Val: GEPTy)->getElementCount(), Elt: C)
1367 : C;
1368
1369 return nullptr;
1370}
1371