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