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