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