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(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 | |
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>(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. |
132 | static Constant *(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 | |
183 | static 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 | |
190 | Constant *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 | |
335 | Constant *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 | |
413 | Constant *llvm::(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 | |
477 | Constant *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 | |
519 | Constant *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 | |
578 | Constant *llvm::(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 | |
590 | Constant *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 | |
619 | Constant *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 * = 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 | |
676 | Constant *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 * = 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 | |
1069 | static 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. |
1099 | static 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 | |
1208 | Constant *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". |
1420 | template<typename IndexTy> |
1421 | static 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. |
1447 | static 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. |
1466 | static 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 | |
1538 | Constant *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 | |