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