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