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

source code of llvm/lib/IR/ConstantFold.cpp