1//===- InstCombineCasts.cpp -----------------------------------------------===//
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 the visit functions for cast operations.
10//
11//===----------------------------------------------------------------------===//
12
13#include "InstCombineInternal.h"
14#include "llvm/ADT/APInt.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/STLFunctionalExtras.h"
18#include "llvm/ADT/SetVector.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/Analysis/ConstantFolding.h"
21#include "llvm/IR/DataLayout.h"
22#include "llvm/IR/DebugInfo.h"
23#include "llvm/IR/Instruction.h"
24#include "llvm/IR/PatternMatch.h"
25#include "llvm/IR/Type.h"
26#include "llvm/IR/Value.h"
27#include "llvm/Support/KnownBits.h"
28#include "llvm/Transforms/InstCombine/InstCombiner.h"
29#include <optional>
30
31using namespace llvm;
32using namespace PatternMatch;
33
34#define DEBUG_TYPE "instcombine"
35
36using EvaluatedMap = SmallDenseMap<Value *, Value *, 8>;
37
38static Value *EvaluateInDifferentTypeImpl(Value *V, Type *Ty, bool isSigned,
39 InstCombinerImpl &IC,
40 EvaluatedMap &Processed) {
41 // Since we cover transformation of instructions with multiple users, we might
42 // come to the same node via multiple paths. We should not create a
43 // replacement for every single one of them though.
44 if (Value *Result = Processed.lookup(Val: V))
45 return Result;
46
47 if (Constant *C = dyn_cast<Constant>(Val: V))
48 return ConstantFoldIntegerCast(C, DestTy: Ty, IsSigned: isSigned, DL: IC.getDataLayout());
49
50 // Otherwise, it must be an instruction.
51 Instruction *I = cast<Instruction>(Val: V);
52 Instruction *Res = nullptr;
53 unsigned Opc = I->getOpcode();
54 switch (Opc) {
55 case Instruction::Add:
56 case Instruction::Sub:
57 case Instruction::Mul:
58 case Instruction::And:
59 case Instruction::Or:
60 case Instruction::Xor:
61 case Instruction::AShr:
62 case Instruction::LShr:
63 case Instruction::Shl:
64 case Instruction::UDiv:
65 case Instruction::URem: {
66 Value *LHS = EvaluateInDifferentTypeImpl(V: I->getOperand(i: 0), Ty, isSigned, IC,
67 Processed);
68 Value *RHS = EvaluateInDifferentTypeImpl(V: I->getOperand(i: 1), Ty, isSigned, IC,
69 Processed);
70 Res = BinaryOperator::Create(Op: (Instruction::BinaryOps)Opc, S1: LHS, S2: RHS);
71 if (Opc == Instruction::LShr || Opc == Instruction::AShr)
72 Res->setIsExact(I->isExact());
73 break;
74 }
75 case Instruction::Trunc:
76 case Instruction::ZExt:
77 case Instruction::SExt:
78 // If the source type of the cast is the type we're trying for then we can
79 // just return the source. There's no need to insert it because it is not
80 // new.
81 if (I->getOperand(i: 0)->getType() == Ty)
82 return I->getOperand(i: 0);
83
84 // Otherwise, must be the same type of cast, so just reinsert a new one.
85 // This also handles the case of zext(trunc(x)) -> zext(x).
86 Res = CastInst::CreateIntegerCast(S: I->getOperand(i: 0), Ty,
87 isSigned: Opc == Instruction::SExt);
88 if (auto *Trunc = dyn_cast<TruncInst>(Val: I)) {
89 if (auto *NewTrunc = dyn_cast<TruncInst>(Val: Res)) {
90 if (Trunc->getType()->getScalarSizeInBits() <=
91 Ty->getScalarSizeInBits()) {
92 NewTrunc->setHasNoSignedWrap(Trunc->hasNoSignedWrap());
93 NewTrunc->setHasNoUnsignedWrap(Trunc->hasNoUnsignedWrap());
94 }
95 } else if (auto *NewZExt = dyn_cast<ZExtInst>(Val: Res)) {
96 if (Trunc->hasNoUnsignedWrap())
97 NewZExt->setNonNeg();
98 }
99 }
100 break;
101 case Instruction::Select: {
102 Value *True = EvaluateInDifferentTypeImpl(V: I->getOperand(i: 1), Ty, isSigned,
103 IC, Processed);
104 Value *False = EvaluateInDifferentTypeImpl(V: I->getOperand(i: 2), Ty, isSigned,
105 IC, Processed);
106 Res = SelectInst::Create(C: I->getOperand(i: 0), S1: True, S2: False);
107 break;
108 }
109 case Instruction::PHI: {
110 PHINode *OPN = cast<PHINode>(Val: I);
111 PHINode *NPN = PHINode::Create(Ty, NumReservedValues: OPN->getNumIncomingValues());
112 for (unsigned i = 0, e = OPN->getNumIncomingValues(); i != e; ++i) {
113 Value *V = EvaluateInDifferentTypeImpl(V: OPN->getIncomingValue(i), Ty,
114 isSigned, IC, Processed);
115 NPN->addIncoming(V, BB: OPN->getIncomingBlock(i));
116 }
117 Res = NPN;
118 break;
119 }
120 case Instruction::FPToUI:
121 case Instruction::FPToSI:
122 Res = CastInst::Create(static_cast<Instruction::CastOps>(Opc),
123 S: I->getOperand(i: 0), Ty);
124 break;
125 case Instruction::Call:
126 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I)) {
127 switch (II->getIntrinsicID()) {
128 default:
129 llvm_unreachable("Unsupported call!");
130 case Intrinsic::vscale: {
131 Function *Fn = Intrinsic::getOrInsertDeclaration(
132 M: I->getModule(), id: Intrinsic::vscale, OverloadTys: {Ty});
133 Res = CallInst::Create(Ty: Fn->getFunctionType(), F: Fn);
134 break;
135 }
136 case Intrinsic::umin:
137 case Intrinsic::umax:
138 case Intrinsic::smin:
139 case Intrinsic::smax: {
140 Value *Op0 = EvaluateInDifferentTypeImpl(V: II->getArgOperand(i: 0), Ty,
141 isSigned, IC, Processed);
142 Value *Op1 = EvaluateInDifferentTypeImpl(V: II->getArgOperand(i: 1), Ty,
143 isSigned, IC, Processed);
144 Function *Fn = Intrinsic::getOrInsertDeclaration(
145 M: I->getModule(), id: II->getIntrinsicID(), OverloadTys: {Ty});
146 Res = CallInst::Create(Ty: Fn->getFunctionType(), Func: Fn, Args: {Op0, Op1});
147 break;
148 }
149 case Intrinsic::abs: {
150 Value *Arg = EvaluateInDifferentTypeImpl(V: II->getArgOperand(i: 0), Ty,
151 isSigned, IC, Processed);
152 Function *Fn = Intrinsic::getOrInsertDeclaration(
153 M: I->getModule(), id: II->getIntrinsicID(), OverloadTys: {Ty});
154 Res = CallInst::Create(Ty: Fn->getFunctionType(), Func: Fn,
155 Args: {Arg, ConstantInt::getFalse(Context&: I->getContext())});
156 break;
157 }
158 }
159 }
160 break;
161 case Instruction::ShuffleVector: {
162 auto *ScalarTy = cast<VectorType>(Val: Ty)->getElementType();
163 auto *VTy = cast<VectorType>(Val: I->getOperand(i: 0)->getType());
164 auto *FixedTy = VectorType::get(ElementType: ScalarTy, EC: VTy->getElementCount());
165 Value *Op0 = EvaluateInDifferentTypeImpl(V: I->getOperand(i: 0), Ty: FixedTy,
166 isSigned, IC, Processed);
167 Value *Op1 = EvaluateInDifferentTypeImpl(V: I->getOperand(i: 1), Ty: FixedTy,
168 isSigned, IC, Processed);
169 Res = new ShuffleVectorInst(Op0, Op1,
170 cast<ShuffleVectorInst>(Val: I)->getShuffleMask());
171 break;
172 }
173 default:
174 // TODO: Can handle more cases here.
175 llvm_unreachable("Unreachable!");
176 }
177
178 Res->takeName(V: I);
179 Value *Result = IC.InsertNewInstWith(New: Res, Old: I->getIterator());
180 // There is no need in keeping track of the old value/new value relationship
181 // when we have only one user, we came have here from that user and no-one
182 // else cares.
183 if (!V->hasOneUse())
184 Processed[V] = Result;
185
186 return Result;
187}
188
189/// Given an expression that CanEvaluateTruncated or CanEvaluateSExtd returns
190/// true for, actually insert the code to evaluate the expression.
191Value *InstCombinerImpl::EvaluateInDifferentType(Value *V, Type *Ty,
192 bool isSigned) {
193 EvaluatedMap Processed;
194 return EvaluateInDifferentTypeImpl(V, Ty, isSigned, IC&: *this, Processed);
195}
196
197Instruction::CastOps
198InstCombinerImpl::isEliminableCastPair(const CastInst *CI1,
199 const CastInst *CI2) {
200 Type *SrcTy = CI1->getSrcTy();
201 Type *MidTy = CI1->getDestTy();
202 Type *DstTy = CI2->getDestTy();
203
204 Instruction::CastOps firstOp = CI1->getOpcode();
205 Instruction::CastOps secondOp = CI2->getOpcode();
206 Type *SrcIntPtrTy =
207 SrcTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(SrcTy) : nullptr;
208 Type *DstIntPtrTy =
209 DstTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(DstTy) : nullptr;
210 unsigned Res = CastInst::isEliminableCastPair(firstOpcode: firstOp, secondOpcode: secondOp, SrcTy, MidTy,
211 DstTy, DL: &DL);
212
213 // We don't want to form an inttoptr or ptrtoint that converts to an integer
214 // type that differs from the pointer size.
215 if ((Res == Instruction::IntToPtr && SrcTy != DstIntPtrTy) ||
216 (Res == Instruction::PtrToInt && DstTy != SrcIntPtrTy))
217 Res = 0;
218
219 return Instruction::CastOps(Res);
220}
221
222/// Implement the transforms common to all CastInst visitors.
223Instruction *InstCombinerImpl::commonCastTransforms(CastInst &CI) {
224 Value *Src = CI.getOperand(i_nocapture: 0);
225 Type *Ty = CI.getType();
226
227 if (Value *Res =
228 simplifyCastInst(CastOpc: CI.getOpcode(), Op: Src, Ty, Q: SQ.getWithInstruction(I: &CI)))
229 return replaceInstUsesWith(I&: CI, V: Res);
230
231 // Try to eliminate a cast of a cast.
232 if (auto *CSrc = dyn_cast<CastInst>(Val: Src)) { // A->B->C cast
233 if (Instruction::CastOps NewOpc = isEliminableCastPair(CI1: CSrc, CI2: &CI)) {
234 // The first cast (CSrc) is eliminable so we need to fix up or replace
235 // the second cast (CI). CSrc will then have a good chance of being dead.
236 auto *Res = CastInst::Create(NewOpc, S: CSrc->getOperand(i_nocapture: 0), Ty);
237 // Point debug users of the dying cast to the new one.
238 if (CSrc->hasOneUse())
239 replaceAllDbgUsesWith(From&: *CSrc, To&: *Res, DomPoint&: CI, DT);
240 return Res;
241 }
242 }
243
244 if (auto *Sel = dyn_cast<SelectInst>(Val: Src)) {
245 // We are casting a select. Try to fold the cast into the select if the
246 // select does not have a compare instruction with matching operand types
247 // or the select is likely better done in a narrow type.
248 // Creating a select with operands that are different sizes than its
249 // condition may inhibit other folds and lead to worse codegen.
250 Value *Cond = Sel->getCondition();
251 if (!isa<CmpInst, TruncInst>(Val: Cond) ||
252 cast<Instruction>(Val: Cond)->getOperand(i: 0)->getType() != Sel->getType() ||
253 (CI.getOpcode() == Instruction::Trunc &&
254 shouldChangeType(From: CI.getSrcTy(), To: CI.getType()))) {
255
256 // If it's a bitcast involving vectors, make sure it has the same number
257 // of elements on both sides.
258 if (CI.getOpcode() != Instruction::BitCast ||
259 match(V: &CI, P: m_ElementWiseBitCast(Op: m_Value()))) {
260 if (Instruction *NV = FoldOpIntoSelect(Op&: CI, SI: Sel)) {
261 replaceAllDbgUsesWith(From&: *Sel, To&: *NV, DomPoint&: CI, DT);
262 return NV;
263 }
264 }
265 }
266 }
267
268 // If we are casting a PHI, then fold the cast into the PHI.
269 if (auto *PN = dyn_cast<PHINode>(Val: Src)) {
270 // Don't do this if it would create a PHI node with an illegal type from a
271 // legal type.
272 if (!Src->getType()->isIntegerTy() || !CI.getType()->isIntegerTy() ||
273 shouldChangeType(From: CI.getSrcTy(), To: CI.getType()))
274 if (Instruction *NV = foldOpIntoPhi(I&: CI, PN))
275 return NV;
276 }
277
278 // Canonicalize a unary shuffle after the cast if neither operation changes
279 // the size or element size of the input vector.
280 // TODO: We could allow size-changing ops if that doesn't harm codegen.
281 // cast (shuffle X, Mask) --> shuffle (cast X), Mask
282 Value *X;
283 ArrayRef<int> Mask;
284 if (match(V: Src, P: m_OneUse(SubPattern: m_Shuffle(v1: m_Value(V&: X), v2: m_Poison(), mask: m_Mask(Mask))))) {
285 // TODO: Allow scalable vectors?
286 auto *SrcTy = dyn_cast<FixedVectorType>(Val: X->getType());
287 auto *DestTy = dyn_cast<FixedVectorType>(Val: Ty);
288 if (SrcTy && DestTy &&
289 SrcTy->getNumElements() == DestTy->getNumElements() &&
290 SrcTy->getPrimitiveSizeInBits() == DestTy->getPrimitiveSizeInBits()) {
291 Value *CastX = Builder.CreateCast(Op: CI.getOpcode(), V: X, DestTy);
292 return new ShuffleVectorInst(CastX, Mask);
293 }
294 }
295
296 return nullptr;
297}
298
299namespace {
300
301/// Helper class for evaluating whether a value can be computed in a different
302/// type without changing its value. Used by cast simplification transforms.
303class TypeEvaluationHelper {
304public:
305 /// Return true if we can evaluate the specified expression tree as type Ty
306 /// instead of its larger type, and arrive with the same value.
307 /// This is used by code that tries to eliminate truncates.
308 [[nodiscard]] static bool canEvaluateTruncated(Value *V, Type *Ty,
309 InstCombinerImpl &IC,
310 Instruction *CxtI);
311
312 /// Determine if the specified value can be computed in the specified wider
313 /// type and produce the same low bits. If not, return false.
314 [[nodiscard]] static bool canEvaluateZExtd(Value *V, Type *Ty,
315 unsigned &BitsToClear,
316 InstCombinerImpl &IC,
317 Instruction *CxtI);
318
319 /// Return true if we can take the specified value and return it as type Ty
320 /// without inserting any new casts and without changing the value of the
321 /// common low bits.
322 [[nodiscard]] static bool canEvaluateSExtd(Value *V, Type *Ty);
323
324private:
325 /// Constants and extensions/truncates from the destination type are always
326 /// free to be evaluated in that type.
327 [[nodiscard]] static bool canAlwaysEvaluateInType(Value *V, Type *Ty);
328
329 /// Check if we traversed all the users of the multi-use values we've seen.
330 [[nodiscard]] bool allPendingVisited() const {
331 return llvm::all_of(Range: Pending,
332 P: [this](Value *V) { return Visited.contains(Val: V); });
333 }
334
335 /// A generic wrapper for canEvaluate* recursions to inject visitation
336 /// tracking and enforce correct multi-use value evaluations.
337 [[nodiscard]] bool
338 canEvaluate(Value *V, Type *Ty,
339 llvm::function_ref<bool(Value *, Type *Type)> Pred) {
340 if (canAlwaysEvaluateInType(V, Ty))
341 return true;
342
343 auto *I = dyn_cast<Instruction>(Val: V);
344
345 if (I == nullptr)
346 return false;
347
348 // We insert false by default to return false when we encounter user loops.
349 const auto [It, Inserted] = Visited.insert(KV: {V, false});
350
351 // There are three possible cases for us having information on this value
352 // in the Visited map:
353 // 1. We properly checked it and concluded that we can evaluate it (true)
354 // 2. We properly checked it and concluded that we can't (false)
355 // 3. We started to check it, but during the recursive traversal we came
356 // back to it.
357 //
358 // For cases 1 and 2, we can safely return the stored result. For case 3, we
359 // can potentially have a situation where we can evaluate recursive user
360 // chains, but that can be quite tricky to do properly and isntead, we
361 // return false.
362 //
363 // In any case, we should return whatever was there in the map to begin
364 // with.
365 if (!Inserted)
366 return It->getSecond();
367
368 // We can easily make a decision about single-user values whether they can
369 // be evaluated in a different type or not, we came from that user. This is
370 // not as simple for multi-user values.
371 //
372 // In general, we have the following case (inverted control-flow, users are
373 // at the top):
374 //
375 // Cast %A
376 // ____|
377 // /
378 // %A = Use %B, %C
379 // ________| |
380 // / |
381 // %B = Use %D |
382 // ________| |
383 // / |
384 // %D = Use %C |
385 // ________|___|
386 // /
387 // %C = ...
388 //
389 // In this case, when we check %A, %B and %D, we are confident that we can
390 // make the decision here and now, since we came from their only users.
391 //
392 // For %C, it is harder. We come there twice, and when we come the first
393 // time, it's hard to tell if we will visit the second user (technically
394 // it's not hard, but we might need a lot of repetitive checks with non-zero
395 // cost).
396 //
397 // In the case above, we are allowed to evaluate %C in different type
398 // because all of it users were part of the traversal.
399 //
400 // In the following case, however, we can't make this conclusion:
401 //
402 // Cast %A
403 // ____|
404 // /
405 // %A = Use %B, %C
406 // ________| |
407 // / |
408 // %B = Use %D |
409 // ________| |
410 // / |
411 // %D = Use %C |
412 // | |
413 // foo(%C) | | <- never traversing foo(%C)
414 // ________|___|
415 // /
416 // %C = ...
417 //
418 // In this case, we still can evaluate %C in a different type, but we'd need
419 // to create a copy of the original %C to be used in foo(%C). Such
420 // duplication might be not profitable.
421 //
422 // For this reason, we collect all users of the mult-user values and mark
423 // them as "pending" and defer this decision to the very end. When we are
424 // done and and ready to have a positive verdict, we should double-check all
425 // of the pending users and ensure that we visited them. allPendingVisited
426 // predicate checks exactly that.
427 if (!I->hasOneUse()) {
428 for (Use &U : I->uses()) {
429 // For most instructions, evaluating them in a different type will
430 // change the type of all operands. This is not the case for select
431 // conditions. Make sure we don't retain an extra use via the select
432 // condition.
433 if (isa<SelectInst>(Val: U.getUser()) && U.getOperandNo() == 0)
434 return false;
435
436 Pending.push_back(Elt: U.getUser());
437 }
438 }
439
440 const bool Result = Pred(V, Ty);
441 // We have to set result this way and not via It because Pred is recursive
442 // and it is very likely that we grew Visited and invalidated It.
443 Visited[V] = Result;
444 return Result;
445 }
446
447 /// Filter out values that we can not evaluate in the destination type for
448 /// free.
449 [[nodiscard]] bool canNotEvaluateInType(Value *V, Type *Ty);
450
451 [[nodiscard]] bool canEvaluateTruncatedImpl(Value *V, Type *Ty,
452 InstCombinerImpl &IC,
453 Instruction *CxtI);
454 [[nodiscard]] bool canEvaluateTruncatedPred(Value *V, Type *Ty,
455 InstCombinerImpl &IC,
456 Instruction *CxtI);
457 [[nodiscard]] bool canEvaluateZExtdImpl(Value *V, Type *Ty,
458 unsigned &BitsToClear,
459 InstCombinerImpl &IC,
460 Instruction *CxtI);
461 [[nodiscard]] bool canEvaluateSExtdImpl(Value *V, Type *Ty);
462 [[nodiscard]] bool canEvaluateSExtdPred(Value *V, Type *Ty);
463
464 /// A bookkeeping map to memorize an already made decision for a traversed
465 /// value.
466 SmallDenseMap<Value *, bool, 8> Visited;
467
468 /// A list of pending values to check in the end.
469 SmallVector<Value *, 8> Pending;
470};
471
472} // anonymous namespace
473
474/// Constants and extensions/truncates from the destination type are always
475/// free to be evaluated in that type. This is a helper for canEvaluate*.
476bool TypeEvaluationHelper::canAlwaysEvaluateInType(Value *V, Type *Ty) {
477 if (isa<Constant>(Val: V))
478 return match(V, P: m_ImmConstant());
479
480 Value *X;
481 if (match(V, P: m_ZExtOrSExt(Op: m_SpecificType(RefTy: Ty, V&: X))) ||
482 match(V, P: m_Trunc(Op: m_SpecificType(RefTy: Ty, V&: X))))
483 return true;
484
485 return false;
486}
487
488/// Filter out values that we can not evaluate in the destination type for free.
489/// This is a helper for canEvaluate*.
490bool TypeEvaluationHelper::canNotEvaluateInType(Value *V, Type *Ty) {
491 if (!isa<Instruction>(Val: V))
492 return true;
493 // We don't extend or shrink something that has multiple uses -- doing so
494 // would require duplicating the instruction which isn't profitable.
495 if (!V->hasOneUse())
496 return true;
497
498 return false;
499}
500
501/// Return true if we can evaluate the specified expression tree as type Ty
502/// instead of its larger type, and arrive with the same value.
503/// This is used by code that tries to eliminate truncates.
504///
505/// Ty will always be a type smaller than V. We should return true if trunc(V)
506/// can be computed by computing V in the smaller type. If V is an instruction,
507/// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only
508/// makes sense if x and y can be efficiently truncated.
509///
510/// This function works on both vectors and scalars.
511///
512bool TypeEvaluationHelper::canEvaluateTruncated(Value *V, Type *Ty,
513 InstCombinerImpl &IC,
514 Instruction *CxtI) {
515 TypeEvaluationHelper TYH;
516 return TYH.canEvaluateTruncatedImpl(V, Ty, IC, CxtI) &&
517 // We need to check whether we visited all users of multi-user values,
518 // and we have to do it at the very end, outside of the recursion.
519 TYH.allPendingVisited();
520}
521
522bool TypeEvaluationHelper::canEvaluateTruncatedImpl(Value *V, Type *Ty,
523 InstCombinerImpl &IC,
524 Instruction *CxtI) {
525 return canEvaluate(V, Ty, Pred: [this, &IC, CxtI](Value *V, Type *Ty) {
526 return canEvaluateTruncatedPred(V, Ty, IC, CxtI);
527 });
528}
529
530bool TypeEvaluationHelper::canEvaluateTruncatedPred(Value *V, Type *Ty,
531 InstCombinerImpl &IC,
532 Instruction *CxtI) {
533 auto *I = cast<Instruction>(Val: V);
534 Type *OrigTy = V->getType();
535 switch (I->getOpcode()) {
536 case Instruction::Add:
537 case Instruction::Sub:
538 case Instruction::Mul:
539 case Instruction::And:
540 case Instruction::Or:
541 case Instruction::Xor:
542 // These operators can all arbitrarily be extended or truncated.
543 return canEvaluateTruncatedImpl(V: I->getOperand(i: 0), Ty, IC, CxtI) &&
544 canEvaluateTruncatedImpl(V: I->getOperand(i: 1), Ty, IC, CxtI);
545
546 case Instruction::UDiv:
547 case Instruction::URem: {
548 // UDiv and URem can be truncated if all the truncated bits are zero.
549 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
550 uint32_t BitWidth = Ty->getScalarSizeInBits();
551 assert(BitWidth < OrigBitWidth && "Unexpected bitwidths!");
552 APInt Mask = APInt::getBitsSetFrom(numBits: OrigBitWidth, loBit: BitWidth);
553 // Do not preserve the original context instruction. Simplifying div/rem
554 // based on later context may introduce a trap.
555 if (IC.MaskedValueIsZero(V: I->getOperand(i: 0), Mask, CxtI: I) &&
556 IC.MaskedValueIsZero(V: I->getOperand(i: 1), Mask, CxtI: I)) {
557 return canEvaluateTruncatedImpl(V: I->getOperand(i: 0), Ty, IC, CxtI) &&
558 canEvaluateTruncatedImpl(V: I->getOperand(i: 1), Ty, IC, CxtI);
559 }
560 break;
561 }
562 case Instruction::Shl: {
563 // If we are truncating the result of this SHL, and if it's a shift of an
564 // inrange amount, we can always perform a SHL in a smaller type.
565 uint32_t BitWidth = Ty->getScalarSizeInBits();
566 KnownBits AmtKnownBits =
567 llvm::computeKnownBits(V: I->getOperand(i: 1), DL: IC.getDataLayout());
568 if (AmtKnownBits.getMaxValue().ult(RHS: BitWidth))
569 return canEvaluateTruncatedImpl(V: I->getOperand(i: 0), Ty, IC, CxtI) &&
570 canEvaluateTruncatedImpl(V: I->getOperand(i: 1), Ty, IC, CxtI);
571 break;
572 }
573 case Instruction::LShr: {
574 // If this is a truncate of a logical shr, we can truncate it to a smaller
575 // lshr iff we know that the bits we would otherwise be shifting in are
576 // already zeros.
577 // TODO: It is enough to check that the bits we would be shifting in are
578 // zero - use AmtKnownBits.getMaxValue().
579 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
580 uint32_t BitWidth = Ty->getScalarSizeInBits();
581 KnownBits AmtKnownBits = IC.computeKnownBits(V: I->getOperand(i: 1), CxtI);
582 APInt MaxShiftAmt = AmtKnownBits.getMaxValue();
583 APInt ShiftedBits = APInt::getBitsSetFrom(numBits: OrigBitWidth, loBit: BitWidth);
584 if (MaxShiftAmt.ult(RHS: BitWidth)) {
585 // If the only user is a trunc then we can narrow the shift if any new
586 // MSBs are not going to be used.
587 if (auto *Trunc = dyn_cast<TruncInst>(Val: V->user_back())) {
588 auto DemandedBits = Trunc->getType()->getScalarSizeInBits();
589 if ((MaxShiftAmt + DemandedBits).ule(RHS: BitWidth))
590 return canEvaluateTruncatedImpl(V: I->getOperand(i: 0), Ty, IC, CxtI) &&
591 canEvaluateTruncatedImpl(V: I->getOperand(i: 1), Ty, IC, CxtI);
592 }
593 if (IC.MaskedValueIsZero(V: I->getOperand(i: 0), Mask: ShiftedBits, CxtI))
594 return canEvaluateTruncatedImpl(V: I->getOperand(i: 0), Ty, IC, CxtI) &&
595 canEvaluateTruncatedImpl(V: I->getOperand(i: 1), Ty, IC, CxtI);
596 }
597 break;
598 }
599 case Instruction::AShr: {
600 // If this is a truncate of an arithmetic shr, we can truncate it to a
601 // smaller ashr iff we know that all the bits from the sign bit of the
602 // original type and the sign bit of the truncate type are similar.
603 // TODO: It is enough to check that the bits we would be shifting in are
604 // similar to sign bit of the truncate type.
605 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
606 uint32_t BitWidth = Ty->getScalarSizeInBits();
607 KnownBits AmtKnownBits =
608 llvm::computeKnownBits(V: I->getOperand(i: 1), DL: IC.getDataLayout());
609 unsigned ShiftedBits = OrigBitWidth - BitWidth;
610 if (AmtKnownBits.getMaxValue().ult(RHS: BitWidth) &&
611 ShiftedBits < IC.ComputeNumSignBits(Op: I->getOperand(i: 0), CxtI))
612 return canEvaluateTruncatedImpl(V: I->getOperand(i: 0), Ty, IC, CxtI) &&
613 canEvaluateTruncatedImpl(V: I->getOperand(i: 1), Ty, IC, CxtI);
614 break;
615 }
616 case Instruction::Trunc:
617 // trunc(trunc(x)) -> trunc(x)
618 return true;
619 case Instruction::ZExt:
620 case Instruction::SExt:
621 // trunc(ext(x)) -> ext(x) if the source type is smaller than the new dest
622 // trunc(ext(x)) -> trunc(x) if the source type is larger than the new dest
623 return true;
624 case Instruction::Select: {
625 SelectInst *SI = cast<SelectInst>(Val: I);
626 return canEvaluateTruncatedImpl(V: SI->getTrueValue(), Ty, IC, CxtI) &&
627 canEvaluateTruncatedImpl(V: SI->getFalseValue(), Ty, IC, CxtI);
628 }
629 case Instruction::PHI: {
630 // We can change a phi if we can change all operands. Note that we never
631 // get into trouble with cyclic PHIs here because canEvaluate handles use
632 // chain loops.
633 PHINode *PN = cast<PHINode>(Val: I);
634 return llvm::all_of(
635 Range: PN->incoming_values(), P: [this, Ty, &IC, CxtI](Value *IncValue) {
636 return canEvaluateTruncatedImpl(V: IncValue, Ty, IC, CxtI);
637 });
638 }
639 case Instruction::FPToUI:
640 case Instruction::FPToSI: {
641 // If the integer type can hold the max FP value, it is safe to cast
642 // directly to that type. Otherwise, we may create poison via overflow
643 // that did not exist in the original code.
644 Type *InputTy = I->getOperand(i: 0)->getType()->getScalarType();
645 const fltSemantics &Semantics = InputTy->getFltSemantics();
646 uint32_t MinBitWidth = APFloatBase::semanticsIntSizeInBits(
647 Semantics, I->getOpcode() == Instruction::FPToSI);
648 return Ty->getScalarSizeInBits() >= MinBitWidth;
649 }
650 case Instruction::ShuffleVector:
651 return canEvaluateTruncatedImpl(V: I->getOperand(i: 0), Ty, IC, CxtI) &&
652 canEvaluateTruncatedImpl(V: I->getOperand(i: 1), Ty, IC, CxtI);
653
654 case Instruction::Call: {
655 Value *AbsOp;
656 if (match(V: I, P: m_Intrinsic<Intrinsic::abs>(Ops: m_Value(V&: AbsOp), Ops: m_Value()))) {
657 if (IC.ComputeMaxSignificantBits(Op: AbsOp, CxtI) > Ty->getScalarSizeInBits())
658 return false;
659 return canEvaluateTruncatedImpl(V: AbsOp, Ty, IC, CxtI);
660 }
661 auto *MM = dyn_cast<MinMaxIntrinsic>(Val: I);
662 if (!MM)
663 return false;
664 // The min/max can be performed in the narrow type when each operand has
665 // zero high bits (for umin/umax) or enough sign bits (for smin/smax).
666 Value *Op0 = MM->getLHS();
667 Value *Op1 = MM->getRHS();
668 uint32_t BitWidth = Ty->getScalarSizeInBits();
669 if (MM->isSigned()) {
670 if (IC.ComputeMaxSignificantBits(Op: Op0, CxtI) > BitWidth ||
671 IC.ComputeMaxSignificantBits(Op: Op1, CxtI) > BitWidth)
672 break;
673 } else {
674 APInt Mask =
675 APInt::getBitsSetFrom(numBits: OrigTy->getScalarSizeInBits(), loBit: BitWidth);
676 if (!IC.MaskedValueIsZero(V: Op0, Mask, CxtI) ||
677 !IC.MaskedValueIsZero(V: Op1, Mask, CxtI))
678 break;
679 }
680 return canEvaluateTruncatedImpl(V: Op0, Ty, IC, CxtI) &&
681 canEvaluateTruncatedImpl(V: Op1, Ty, IC, CxtI);
682 }
683 default:
684 // TODO: Can handle more cases here.
685 break;
686 }
687
688 return false;
689}
690
691/// Given a vector that is bitcast to an integer, optionally logically
692/// right-shifted, and truncated, convert it to an extractelement.
693/// Example (big endian):
694/// trunc (lshr (bitcast <4 x i32> %X to i128), 32) to i32
695/// --->
696/// extractelement <4 x i32> %X, 1
697static Instruction *foldVecTruncToExtElt(TruncInst &Trunc,
698 InstCombinerImpl &IC) {
699 Value *TruncOp = Trunc.getOperand(i_nocapture: 0);
700 Type *DestType = Trunc.getType();
701 if (!TruncOp->hasOneUse() || !isa<IntegerType>(Val: DestType))
702 return nullptr;
703
704 Value *VecInput = nullptr;
705 ConstantInt *ShiftVal = nullptr;
706 if (!match(V: TruncOp, P: m_CombineOr(Ps: m_BitCast(Op: m_Value(V&: VecInput)),
707 Ps: m_LShr(L: m_BitCast(Op: m_Value(V&: VecInput)),
708 R: m_ConstantInt(CI&: ShiftVal)))) ||
709 !isa<VectorType>(Val: VecInput->getType()))
710 return nullptr;
711
712 VectorType *VecType = cast<VectorType>(Val: VecInput->getType());
713 unsigned VecWidth = VecType->getPrimitiveSizeInBits();
714 unsigned DestWidth = DestType->getPrimitiveSizeInBits();
715 unsigned ShiftAmount = ShiftVal ? ShiftVal->getZExtValue() : 0;
716
717 if ((VecWidth % DestWidth != 0) || (ShiftAmount % DestWidth != 0))
718 return nullptr;
719
720 // If the element type of the vector doesn't match the result type,
721 // bitcast it to a vector type that we can extract from.
722 unsigned NumVecElts = VecWidth / DestWidth;
723 if (VecType->getElementType() != DestType) {
724 VecType = FixedVectorType::get(ElementType: DestType, NumElts: NumVecElts);
725 VecInput = IC.Builder.CreateBitCast(V: VecInput, DestTy: VecType, Name: "bc");
726 }
727
728 unsigned Elt = ShiftAmount / DestWidth;
729 if (IC.getDataLayout().isBigEndian())
730 Elt = NumVecElts - 1 - Elt;
731
732 return ExtractElementInst::Create(Vec: VecInput, Idx: IC.Builder.getInt32(C: Elt));
733}
734
735/// Whenever an element is extracted from a vector, optionally shifted down, and
736/// then truncated, canonicalize by converting it to a bitcast followed by an
737/// extractelement.
738///
739/// Examples (little endian):
740/// trunc (extractelement <4 x i64> %X, 0) to i32
741/// --->
742/// extractelement <8 x i32> (bitcast <4 x i64> %X to <8 x i32>), i32 0
743///
744/// trunc (lshr (extractelement <4 x i32> %X, 0), 8) to i8
745/// --->
746/// extractelement <16 x i8> (bitcast <4 x i32> %X to <16 x i8>), i32 1
747static Instruction *foldVecExtTruncToExtElt(TruncInst &Trunc,
748 InstCombinerImpl &IC) {
749 Value *Src = Trunc.getOperand(i_nocapture: 0);
750 Type *SrcType = Src->getType();
751 Type *DstType = Trunc.getType();
752
753 // Only attempt this if we have simple aliasing of the vector elements.
754 // A badly fit destination size would result in an invalid cast.
755 unsigned SrcBits = SrcType->getScalarSizeInBits();
756 unsigned DstBits = DstType->getScalarSizeInBits();
757 unsigned TruncRatio = SrcBits / DstBits;
758 if ((SrcBits % DstBits) != 0)
759 return nullptr;
760
761 Value *VecOp;
762 ConstantInt *Cst;
763 const APInt *ShiftAmount = nullptr;
764 if (!match(V: Src, P: m_OneUse(SubPattern: m_ExtractElt(Val: m_Value(V&: VecOp), Idx: m_ConstantInt(CI&: Cst)))) &&
765 !match(V: Src,
766 P: m_OneUse(SubPattern: m_LShr(L: m_ExtractElt(Val: m_Value(V&: VecOp), Idx: m_ConstantInt(CI&: Cst)),
767 R: m_APInt(Res&: ShiftAmount)))))
768 return nullptr;
769
770 auto *VecOpTy = cast<VectorType>(Val: VecOp->getType());
771 auto VecElts = VecOpTy->getElementCount();
772
773 uint64_t BitCastNumElts = VecElts.getKnownMinValue() * TruncRatio;
774 // Make sure we don't overflow in the calculation of the new index.
775 // (VecOpIdx + 1) * TruncRatio should not overflow.
776 if (Cst->uge(Num: std::numeric_limits<uint64_t>::max() / TruncRatio))
777 return nullptr;
778 uint64_t VecOpIdx = Cst->getZExtValue();
779 uint64_t NewIdx = IC.getDataLayout().isBigEndian()
780 ? (VecOpIdx + 1) * TruncRatio - 1
781 : VecOpIdx * TruncRatio;
782
783 // Adjust index by the whole number of truncated elements.
784 if (ShiftAmount) {
785 // Check shift amount is in range and shifts a whole number of truncated
786 // elements.
787 if (ShiftAmount->uge(RHS: SrcBits) || ShiftAmount->urem(RHS: DstBits) != 0)
788 return nullptr;
789
790 uint64_t IdxOfs = ShiftAmount->udiv(RHS: DstBits).getZExtValue();
791 // IdxOfs is guaranteed to be less than TruncRatio, so we won't overflow in
792 // the adjustment.
793 assert(IdxOfs < TruncRatio &&
794 "IdxOfs is expected to be less than TruncRatio.");
795 NewIdx = IC.getDataLayout().isBigEndian() ? (NewIdx - IdxOfs)
796 : (NewIdx + IdxOfs);
797 }
798
799 assert(BitCastNumElts <= std::numeric_limits<uint32_t>::max() &&
800 "overflow 32-bits");
801
802 auto *BitCastTo =
803 VectorType::get(ElementType: DstType, NumElements: BitCastNumElts, Scalable: VecElts.isScalable());
804 Value *BitCast = IC.Builder.CreateBitCast(V: VecOp, DestTy: BitCastTo);
805 return ExtractElementInst::Create(Vec: BitCast, Idx: IC.Builder.getInt64(C: NewIdx));
806}
807
808/// Funnel/Rotate left/right may occur in a wider type than necessary because of
809/// type promotion rules. Try to narrow the inputs and convert to funnel shift.
810Instruction *InstCombinerImpl::narrowFunnelShift(TruncInst &Trunc) {
811 assert((isa<VectorType>(Trunc.getSrcTy()) ||
812 shouldChangeType(Trunc.getSrcTy(), Trunc.getType())) &&
813 "Don't narrow to an illegal scalar type");
814
815 // Bail out on strange types. It is possible to handle some of these patterns
816 // even with non-power-of-2 sizes, but it is not a likely scenario.
817 Type *DestTy = Trunc.getType();
818 unsigned NarrowWidth = DestTy->getScalarSizeInBits();
819 unsigned WideWidth = Trunc.getSrcTy()->getScalarSizeInBits();
820 if (!isPowerOf2_32(Value: NarrowWidth))
821 return nullptr;
822
823 // First, find an or'd pair of opposite shifts:
824 // trunc (or (lshr ShVal0, ShAmt0), (shl ShVal1, ShAmt1))
825 BinaryOperator *Or0, *Or1;
826 if (!match(V: Trunc.getOperand(i_nocapture: 0), P: m_OneUse(SubPattern: m_Or(L: m_BinOp(I&: Or0), R: m_BinOp(I&: Or1)))))
827 return nullptr;
828
829 Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;
830 if (!match(V: Or0, P: m_OneUse(SubPattern: m_LogicalShift(L: m_Value(V&: ShVal0), R: m_Value(V&: ShAmt0)))) ||
831 !match(V: Or1, P: m_OneUse(SubPattern: m_LogicalShift(L: m_Value(V&: ShVal1), R: m_Value(V&: ShAmt1)))) ||
832 Or0->getOpcode() == Or1->getOpcode())
833 return nullptr;
834
835 // Canonicalize to or(shl(ShVal0, ShAmt0), lshr(ShVal1, ShAmt1)).
836 if (Or0->getOpcode() == BinaryOperator::LShr) {
837 std::swap(a&: Or0, b&: Or1);
838 std::swap(a&: ShVal0, b&: ShVal1);
839 std::swap(a&: ShAmt0, b&: ShAmt1);
840 }
841 assert(Or0->getOpcode() == BinaryOperator::Shl &&
842 Or1->getOpcode() == BinaryOperator::LShr &&
843 "Illegal or(shift,shift) pair");
844
845 // Match the shift amount operands for a funnel/rotate pattern. This always
846 // matches a subtraction on the R operand.
847 auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width) -> Value * {
848 // The shift amounts may add up to the narrow bit width:
849 // (shl ShVal0, L) | (lshr ShVal1, Width - L)
850 // If this is a funnel shift (different operands are shifted), then the
851 // shift amount can not over-shift (create poison) in the narrow type.
852 unsigned MaxShiftAmountWidth = Log2_32(Value: NarrowWidth);
853 APInt HiBitMask = ~APInt::getLowBitsSet(numBits: WideWidth, loBitsSet: MaxShiftAmountWidth);
854 if (ShVal0 == ShVal1 || MaskedValueIsZero(V: L, Mask: HiBitMask))
855 if (match(V: R, P: m_OneUse(SubPattern: m_Sub(L: m_SpecificInt(V: Width), R: m_Specific(V: L)))))
856 return L;
857
858 // The following patterns currently only work for rotation patterns.
859 // TODO: Add more general funnel-shift compatible patterns.
860 if (ShVal0 != ShVal1)
861 return nullptr;
862
863 // The shift amount may be masked with negation:
864 // (shl ShVal0, (X & (Width - 1))) | (lshr ShVal1, ((-X) & (Width - 1)))
865 Value *X;
866 unsigned Mask = Width - 1;
867 if (match(V: L, P: m_And(L: m_Value(V&: X), R: m_SpecificInt(V: Mask))) &&
868 match(V: R, P: m_And(L: m_Neg(V: m_Specific(V: X)), R: m_SpecificInt(V: Mask))))
869 return X;
870
871 // Same as above, but the shift amount may be extended after masking:
872 if (match(V: L, P: m_ZExt(Op: m_And(L: m_Value(V&: X), R: m_SpecificInt(V: Mask)))) &&
873 match(V: R, P: m_ZExt(Op: m_And(L: m_Neg(V: m_Specific(V: X)), R: m_SpecificInt(V: Mask)))))
874 return X;
875
876 return nullptr;
877 };
878
879 Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, NarrowWidth);
880 bool IsFshl = true; // Sub on LSHR.
881 if (!ShAmt) {
882 ShAmt = matchShiftAmount(ShAmt1, ShAmt0, NarrowWidth);
883 IsFshl = false; // Sub on SHL.
884 }
885 if (!ShAmt)
886 return nullptr;
887
888 // The right-shifted value must have high zeros in the wide type (for example
889 // from 'zext', 'and' or 'shift'). High bits of the left-shifted value are
890 // truncated, so those do not matter.
891 APInt HiBitMask = APInt::getHighBitsSet(numBits: WideWidth, hiBitsSet: WideWidth - NarrowWidth);
892 if (!MaskedValueIsZero(V: ShVal1, Mask: HiBitMask, CxtI: &Trunc))
893 return nullptr;
894
895 // Adjust the width of ShAmt for narrowed funnel shift operation:
896 // - Zero-extend if ShAmt is narrower than the destination type.
897 // - Truncate if ShAmt is wider, discarding non-significant high-order bits.
898 // This prepares ShAmt for llvm.fshl.i8(trunc(ShVal), trunc(ShVal),
899 // zext/trunc(ShAmt)).
900 Value *NarrowShAmt = Builder.CreateZExtOrTrunc(V: ShAmt, DestTy);
901
902 Value *X, *Y;
903 X = Y = Builder.CreateTrunc(V: ShVal0, DestTy);
904 if (ShVal0 != ShVal1)
905 Y = Builder.CreateTrunc(V: ShVal1, DestTy);
906 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
907 Function *F =
908 Intrinsic::getOrInsertDeclaration(M: Trunc.getModule(), id: IID, OverloadTys: DestTy);
909 return CallInst::Create(Func: F, Args: {X, Y, NarrowShAmt});
910}
911
912/// Try to narrow the width of math or bitwise logic instructions by pulling a
913/// truncate ahead of binary operators.
914Instruction *InstCombinerImpl::narrowBinOp(TruncInst &Trunc) {
915 Type *SrcTy = Trunc.getSrcTy();
916 Type *DestTy = Trunc.getType();
917 unsigned SrcWidth = SrcTy->getScalarSizeInBits();
918 unsigned DestWidth = DestTy->getScalarSizeInBits();
919
920 if (!isa<VectorType>(Val: SrcTy) && !shouldChangeType(From: SrcTy, To: DestTy))
921 return nullptr;
922
923 BinaryOperator *BinOp;
924 if (!match(V: Trunc.getOperand(i_nocapture: 0), P: m_OneUse(SubPattern: m_BinOp(I&: BinOp))))
925 return nullptr;
926
927 Value *BinOp0 = BinOp->getOperand(i_nocapture: 0);
928 Value *BinOp1 = BinOp->getOperand(i_nocapture: 1);
929 switch (BinOp->getOpcode()) {
930 case Instruction::And:
931 case Instruction::Or:
932 case Instruction::Xor:
933 case Instruction::Add:
934 case Instruction::Sub:
935 case Instruction::Mul: {
936 Constant *C;
937 if (match(V: BinOp0, P: m_Constant(C))) {
938 // trunc (binop C, X) --> binop (trunc C', X)
939 Constant *NarrowC = ConstantExpr::getTrunc(C, Ty: DestTy);
940 Value *TruncX = Builder.CreateTrunc(V: BinOp1, DestTy);
941 return BinaryOperator::Create(Op: BinOp->getOpcode(), S1: NarrowC, S2: TruncX);
942 }
943 if (match(V: BinOp1, P: m_Constant(C))) {
944 // trunc (binop X, C) --> binop (trunc X, C')
945 Constant *NarrowC = ConstantExpr::getTrunc(C, Ty: DestTy);
946 Value *TruncX = Builder.CreateTrunc(V: BinOp0, DestTy);
947 return BinaryOperator::Create(Op: BinOp->getOpcode(), S1: TruncX, S2: NarrowC);
948 }
949 Value *X;
950 if (match(V: BinOp0, P: m_ZExtOrSExt(Op: m_SpecificType(RefTy: DestTy, V&: X)))) {
951 // trunc (binop (ext X), Y) --> binop X, (trunc Y)
952 Value *NarrowOp1 = Builder.CreateTrunc(V: BinOp1, DestTy);
953 return BinaryOperator::Create(Op: BinOp->getOpcode(), S1: X, S2: NarrowOp1);
954 }
955 if (match(V: BinOp1, P: m_ZExtOrSExt(Op: m_SpecificType(RefTy: DestTy, V&: X)))) {
956 // trunc (binop Y, (ext X)) --> binop (trunc Y), X
957 Value *NarrowOp0 = Builder.CreateTrunc(V: BinOp0, DestTy);
958 return BinaryOperator::Create(Op: BinOp->getOpcode(), S1: NarrowOp0, S2: X);
959 }
960 break;
961 }
962 case Instruction::LShr:
963 case Instruction::AShr: {
964 // trunc (*shr (trunc A), C) --> trunc(*shr A, C)
965 Value *A;
966 Constant *C;
967 if (match(V: BinOp0, P: m_Trunc(Op: m_Value(V&: A))) && match(V: BinOp1, P: m_Constant(C))) {
968 unsigned MaxShiftAmt = SrcWidth - DestWidth;
969 // If the shift is small enough, all zero/sign bits created by the shift
970 // are removed by the trunc.
971 if (match(V: C, P: m_SpecificInt_ICMP(Predicate: ICmpInst::ICMP_ULE,
972 Threshold: APInt(SrcWidth, MaxShiftAmt)))) {
973 auto *OldShift = cast<Instruction>(Val: Trunc.getOperand(i_nocapture: 0));
974 bool IsExact = OldShift->isExact();
975 if (Constant *ShAmt = ConstantFoldIntegerCast(C, DestTy: A->getType(),
976 /*IsSigned*/ true, DL)) {
977 ShAmt = Constant::mergeUndefsWith(C: ShAmt, Other: C);
978 Value *Shift =
979 OldShift->getOpcode() == Instruction::AShr
980 ? Builder.CreateAShr(LHS: A, RHS: ShAmt, Name: OldShift->getName(), isExact: IsExact)
981 : Builder.CreateLShr(LHS: A, RHS: ShAmt, Name: OldShift->getName(), isExact: IsExact);
982 return CastInst::CreateTruncOrBitCast(S: Shift, Ty: DestTy);
983 }
984 }
985 }
986 break;
987 }
988 default: break;
989 }
990
991 if (Instruction *NarrowOr = narrowFunnelShift(Trunc))
992 return NarrowOr;
993
994 return nullptr;
995}
996
997/// Try to narrow the width of a splat shuffle. This could be generalized to any
998/// shuffle with a constant operand, but we limit the transform to avoid
999/// creating a shuffle type that targets may not be able to lower effectively.
1000static Instruction *shrinkSplatShuffle(TruncInst &Trunc,
1001 InstCombiner::BuilderTy &Builder) {
1002 Value *Shuf = Trunc.getOperand(i_nocapture: 0), *ShufVec;
1003 ArrayRef<int> SplatMask;
1004 if (match(V: Shuf, P: m_OneUse(SubPattern: m_Shuffle(v1: m_Value(V&: ShufVec), v2: m_Poison(),
1005 mask: m_Mask(SplatMask)))) &&
1006 match(Mask: SplatMask, P: m_SplatMask()) &&
1007 ElementCount::isKnownGE(
1008 LHS: cast<VectorType>(Val: Shuf->getType())->getElementCount(),
1009 RHS: cast<VectorType>(Val: ShufVec->getType())->getElementCount())) {
1010 // trunc (shuf X, poison, SplatMask) --> shuf (trunc X), poison, SplatMask
1011 Type *NewTruncTy =
1012 ShufVec->getType()->getWithNewType(EltTy: Trunc.getType()->getScalarType());
1013 Value *NarrowOp = Builder.CreateTrunc(V: ShufVec, DestTy: NewTruncTy);
1014 return new ShuffleVectorInst(NarrowOp, SplatMask);
1015 }
1016
1017 return nullptr;
1018}
1019
1020/// Try to narrow the width of an insert element. This could be generalized for
1021/// any vector constant, but we limit the transform to insertion into poison to
1022/// avoid potential backend problems from unsupported insertion widths. This
1023/// could also be extended to handle the case of inserting a scalar constant
1024/// into a vector variable.
1025static Instruction *shrinkInsertElt(CastInst &Trunc,
1026 InstCombiner::BuilderTy &Builder) {
1027 Instruction::CastOps Opcode = Trunc.getOpcode();
1028 assert((Opcode == Instruction::Trunc || Opcode == Instruction::FPTrunc) &&
1029 "Unexpected instruction for shrinking");
1030
1031 Value *Elt, *Index;
1032 if (match(V: Trunc.getOperand(i_nocapture: 0),
1033 P: m_OneUse(SubPattern: m_InsertElt(Val: m_Poison(), Elt: m_Value(V&: Elt), Idx: m_Value(V&: Index))))) {
1034 // trunc (inselt poison, X, Index) --> inselt poison, (trunc X), Index
1035 // fptrunc (inselt poison, X, Index) --> inselt poison, (fptrunc X), Index
1036 auto *NarrowPoison = PoisonValue::get(T: Trunc.getType());
1037 Value *NarrowOp =
1038 Builder.CreateCast(Op: Opcode, V: Elt, DestTy: Trunc.getType()->getScalarType());
1039 return InsertElementInst::Create(Vec: NarrowPoison, NewElt: NarrowOp, Idx: Index);
1040 }
1041
1042 return nullptr;
1043}
1044
1045Instruction *InstCombinerImpl::visitTrunc(TruncInst &Trunc) {
1046 if (Instruction *Result = commonCastTransforms(CI&: Trunc))
1047 return Result;
1048
1049 Value *Src = Trunc.getOperand(i_nocapture: 0);
1050 Type *DestTy = Trunc.getType(), *SrcTy = Src->getType();
1051 unsigned DestWidth = DestTy->getScalarSizeInBits();
1052 unsigned SrcWidth = SrcTy->getScalarSizeInBits();
1053
1054 // Attempt to truncate the entire input expression tree to the destination
1055 // type. Only do this if the dest type is a simple type, don't convert the
1056 // expression tree to something weird like i93 unless the source is also
1057 // strange.
1058 if ((DestTy->isVectorTy() || shouldChangeType(From: SrcTy, To: DestTy)) &&
1059 TypeEvaluationHelper::canEvaluateTruncated(V: Src, Ty: DestTy, IC&: *this, CxtI: &Trunc)) {
1060
1061 // If this cast is a truncate, evaluting in a different type always
1062 // eliminates the cast, so it is always a win.
1063 LLVM_DEBUG(
1064 dbgs() << "ICE: EvaluateInDifferentType converting expression type"
1065 " to avoid cast: "
1066 << Trunc << '\n');
1067 Value *Res = EvaluateInDifferentType(V: Src, Ty: DestTy, isSigned: false);
1068 assert(Res->getType() == DestTy);
1069 return replaceInstUsesWith(I&: Trunc, V: Res);
1070 }
1071
1072 // For integer types, check if we can shorten the entire input expression to
1073 // DestWidth * 2, which won't allow removing the truncate, but reducing the
1074 // width may enable further optimizations, e.g. allowing for larger
1075 // vectorization factors.
1076 if (auto *DestITy = dyn_cast<IntegerType>(Val: DestTy)) {
1077 if (DestWidth * 2 < SrcWidth) {
1078 auto *NewDestTy = DestITy->getExtendedType();
1079 if (shouldChangeType(From: SrcTy, To: NewDestTy) &&
1080 TypeEvaluationHelper::canEvaluateTruncated(V: Src, Ty: NewDestTy, IC&: *this,
1081 CxtI: &Trunc)) {
1082 LLVM_DEBUG(
1083 dbgs() << "ICE: EvaluateInDifferentType converting expression type"
1084 " to reduce the width of operand of"
1085 << Trunc << '\n');
1086 Value *Res = EvaluateInDifferentType(V: Src, Ty: NewDestTy, isSigned: false);
1087 return new TruncInst(Res, DestTy);
1088 }
1089 }
1090 }
1091 Value *X;
1092 if (DestWidth == 1 &&
1093 (Trunc.hasNoUnsignedWrap() || Trunc.hasNoSignedWrap()) &&
1094 match(V: Src, P: m_Exact(SubPattern: m_Shr(L: m_Value(V&: X), R: m_Value()))))
1095 return new ICmpInst(ICmpInst::ICMP_NE, X, Constant::getNullValue(Ty: SrcTy));
1096
1097 // See if we can simplify any instructions used by the input whose sole
1098 // purpose is to compute bits we don't care about.
1099 if (SimplifyDemandedInstructionBits(Inst&: Trunc))
1100 return &Trunc;
1101
1102 if (DestWidth == 1) {
1103 Value *Zero = Constant::getNullValue(Ty: SrcTy);
1104
1105 const APInt *C1;
1106 Constant *C2;
1107 if (match(V: Src, P: m_OneUse(SubPattern: m_Shr(L: m_Shl(L: m_Power2(V&: C1), R: m_Value(V&: X)),
1108 R: m_ImmConstant(C&: C2))))) {
1109 // trunc ((C1 << X) >> C2) to i1 --> X == (C2-cttz(C1)), where C1 is pow2
1110 Constant *Log2C1 = ConstantInt::get(Ty: SrcTy, V: C1->exactLogBase2());
1111 Constant *CmpC = ConstantExpr::getSub(C1: C2, C2: Log2C1);
1112 return new ICmpInst(ICmpInst::ICMP_EQ, X, CmpC);
1113 }
1114
1115 if (match(V: Src, P: m_Shr(L: m_Value(V&: X), R: m_SpecificInt(V: SrcWidth - 1)))) {
1116 // trunc (ashr X, BW-1) to i1 --> icmp slt X, 0
1117 // trunc (lshr X, BW-1) to i1 --> icmp slt X, 0
1118 return new ICmpInst(ICmpInst::ICMP_SLT, X, Zero);
1119 }
1120
1121 Constant *C;
1122 if (match(V: Src, P: m_OneUse(SubPattern: m_LShr(L: m_Value(V&: X), R: m_ImmConstant(C))))) {
1123 // trunc (lshr X, C) to i1 --> icmp ne (and X, C'), 0
1124 Constant *One = ConstantInt::get(Ty: SrcTy, V: APInt(SrcWidth, 1));
1125 Value *MaskC = Builder.CreateShl(LHS: One, RHS: C);
1126 Value *And = Builder.CreateAnd(LHS: X, RHS: MaskC);
1127 return new ICmpInst(ICmpInst::ICMP_NE, And, Zero);
1128 }
1129 if (match(V: Src, P: m_OneUse(SubPattern: m_c_Or(L: m_LShr(L: m_Value(V&: X), R: m_ImmConstant(C)),
1130 R: m_Deferred(V: X))))) {
1131 // trunc (or (lshr X, C), X) to i1 --> icmp ne (and X, C'), 0
1132 Constant *One = ConstantInt::get(Ty: SrcTy, V: APInt(SrcWidth, 1));
1133 Value *MaskC = Builder.CreateShl(LHS: One, RHS: C);
1134 Value *And = Builder.CreateAnd(LHS: X, RHS: Builder.CreateOr(LHS: MaskC, RHS: One));
1135 return new ICmpInst(ICmpInst::ICMP_NE, And, Zero);
1136 }
1137
1138 {
1139 const APInt *C;
1140 if (match(V: Src, P: m_Shl(L: m_APInt(Res&: C), R: m_Value(V&: X))) && (*C)[0] == 1) {
1141 // trunc (C << X) to i1 --> X == 0, where C is odd
1142 return new ICmpInst(ICmpInst::Predicate::ICMP_EQ, X, Zero);
1143 }
1144 }
1145
1146 if (Trunc.hasNoUnsignedWrap() || Trunc.hasNoSignedWrap()) {
1147 Value *X, *Y;
1148 if (match(V: Src, P: m_Xor(L: m_Value(V&: X), R: m_Value(V&: Y))))
1149 return new ICmpInst(ICmpInst::ICMP_NE, X, Y);
1150 }
1151
1152 if (match(V: Src,
1153 P: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::usub_sat>(Ops: m_One(), Ops: m_Value(V&: X)))))
1154 return new ICmpInst(ICmpInst::ICMP_EQ, X,
1155 ConstantInt::getNullValue(Ty: SrcTy));
1156 }
1157
1158 Value *A, *B;
1159 Constant *C;
1160
1161 // trunc(u/smin(zext(a) + zext(b), MAX)) --> uadd.sat(a, b)
1162 if (match(V: Src, P: m_OneUse(SubPattern: m_CombineOr(
1163 Ps: m_UMin(Op0: m_OneUse(SubPattern: m_Add(L: m_ZExt(Op: m_SpecificType(RefTy: DestTy, V&: A)),
1164 R: m_ZExt(Op: m_SpecificType(RefTy: DestTy, V&: B)))),
1165 Op1: m_SpecificInt(V: APInt::getMaxValue(numBits: DestWidth))),
1166 Ps: m_SMin(Op0: m_OneUse(SubPattern: m_Add(L: m_ZExt(Op: m_SpecificType(RefTy: DestTy, V&: A)),
1167 R: m_ZExt(Op: m_SpecificType(RefTy: DestTy, V&: B)))),
1168 Op1: m_SpecificInt(V: APInt::getMaxValue(numBits: DestWidth))))))) {
1169 return replaceInstUsesWith(
1170 I&: Trunc, V: Builder.CreateBinaryIntrinsic(ID: Intrinsic::uadd_sat, LHS: A, RHS: B));
1171 }
1172
1173 // trunc(smax(zext(a) - zext(b), 0)) --> usub.sat(a, b)
1174 if (match(V: Src,
1175 P: m_OneUse(SubPattern: m_SMax(Op0: m_OneUse(SubPattern: m_Sub(L: m_ZExt(Op: m_SpecificType(RefTy: DestTy, V&: A)),
1176 R: m_ZExt(Op: m_SpecificType(RefTy: DestTy, V&: B)))),
1177 Op1: m_Zero())))) {
1178 return replaceInstUsesWith(
1179 I&: Trunc, V: Builder.CreateBinaryIntrinsic(ID: Intrinsic::usub_sat, LHS: A, RHS: B));
1180 }
1181
1182 if (match(V: Src, P: m_LShr(L: m_SExt(Op: m_Value(V&: A)), R: m_Constant(C)))) {
1183 unsigned AWidth = A->getType()->getScalarSizeInBits();
1184 unsigned MaxShiftAmt = SrcWidth - std::max(a: DestWidth, b: AWidth);
1185 auto *OldSh = cast<Instruction>(Val: Src);
1186 bool IsExact = OldSh->isExact();
1187
1188 // If the shift is small enough, all zero bits created by the shift are
1189 // removed by the trunc.
1190 if (match(V: C, P: m_SpecificInt_ICMP(Predicate: ICmpInst::ICMP_ULE,
1191 Threshold: APInt(SrcWidth, MaxShiftAmt)))) {
1192 auto GetNewShAmt = [&](unsigned Width) {
1193 Constant *MaxAmt = ConstantInt::get(Ty: SrcTy, V: Width - 1, IsSigned: false);
1194 Constant *Cmp =
1195 ConstantFoldCompareInstOperands(Predicate: ICmpInst::ICMP_ULT, LHS: C, RHS: MaxAmt, DL);
1196 Constant *ShAmt = ConstantFoldSelectInstruction(Cond: Cmp, V1: C, V2: MaxAmt);
1197 return ConstantFoldCastOperand(Opcode: Instruction::Trunc, C: ShAmt, DestTy: A->getType(),
1198 DL);
1199 };
1200
1201 // trunc (lshr (sext A), C) --> ashr A, C
1202 if (A->getType() == DestTy) {
1203 Constant *ShAmt = GetNewShAmt(DestWidth);
1204 ShAmt = Constant::mergeUndefsWith(C: ShAmt, Other: C);
1205 return IsExact ? BinaryOperator::CreateExactAShr(V1: A, V2: ShAmt)
1206 : BinaryOperator::CreateAShr(V1: A, V2: ShAmt);
1207 }
1208 // The types are mismatched, so create a cast after shifting:
1209 // trunc (lshr (sext A), C) --> sext/trunc (ashr A, C)
1210 if (Src->hasOneUse()) {
1211 Constant *ShAmt = GetNewShAmt(AWidth);
1212 Value *Shift = Builder.CreateAShr(LHS: A, RHS: ShAmt, Name: "", isExact: IsExact);
1213 return CastInst::CreateIntegerCast(S: Shift, Ty: DestTy, isSigned: true);
1214 }
1215 }
1216 // TODO: Mask high bits with 'and'.
1217 }
1218
1219 if (Instruction *I = narrowBinOp(Trunc))
1220 return I;
1221
1222 if (Instruction *I = shrinkSplatShuffle(Trunc, Builder))
1223 return I;
1224
1225 if (Instruction *I = shrinkInsertElt(Trunc, Builder))
1226 return I;
1227
1228 if (Src->hasOneUse() &&
1229 (isa<VectorType>(Val: SrcTy) || shouldChangeType(From: SrcTy, To: DestTy))) {
1230 // Transform "trunc (shl X, cst)" -> "shl (trunc X), cst" so long as the
1231 // dest type is native and cst < dest size.
1232 if (match(V: Src, P: m_Shl(L: m_Value(V&: A), R: m_Constant(C))) &&
1233 !match(V: A, P: m_Shr(L: m_Value(), R: m_Constant()))) {
1234 // Skip shifts of shift by constants. It undoes a combine in
1235 // FoldShiftByConstant and is the extend in reg pattern.
1236 APInt Threshold = APInt(C->getType()->getScalarSizeInBits(), DestWidth);
1237 if (match(V: C, P: m_SpecificInt_ICMP(Predicate: ICmpInst::ICMP_ULT, Threshold))) {
1238 // If neither the wide shift nor the truncate wrap, propagate the wrap
1239 // flags on the new truncate and shift.
1240 auto *WideShl = cast<OverflowingBinaryOperator>(Val: Src);
1241 bool NUW = Trunc.hasNoUnsignedWrap() && WideShl->hasNoUnsignedWrap();
1242 bool NSW = Trunc.hasNoSignedWrap() && WideShl->hasNoSignedWrap();
1243 Value *NewTrunc = Builder.CreateTrunc(V: A, DestTy, Name: A->getName() + ".tr",
1244 /*IsNUW=*/NUW, /*IsNSW=*/NSW);
1245 auto *NewShl = BinaryOperator::Create(
1246 Op: Instruction::Shl, S1: NewTrunc, S2: ConstantExpr::getTrunc(C, Ty: DestTy));
1247 NewShl->setHasNoUnsignedWrap(NUW);
1248 NewShl->setHasNoSignedWrap(NSW);
1249 return NewShl;
1250 }
1251 }
1252 }
1253
1254 // trunc (select(icmp_ult(A, DestTy_umax+1), A, sext(icmp_sgt(A, 0)))) -->
1255 // trunc (smin(smax(0, A), DestTy_umax))
1256 if (SrcTy->isIntegerTy() && isPowerOf2_64(Value: SrcTy->getPrimitiveSizeInBits()) &&
1257 isPowerOf2_64(Value: DestTy->getPrimitiveSizeInBits()) &&
1258 match(V: Src, P: m_OneUse(SubPattern: m_Select(
1259 C: m_OneUse(SubPattern: m_SpecificICmp(MatchPred: ICmpInst::ICMP_ULT, L: m_Value(V&: A),
1260 R: m_Constant(C))),
1261 L: m_Deferred(V: A),
1262 R: m_OneUse(SubPattern: m_SExt(Op: m_OneUse(SubPattern: m_SpecificICmp(
1263 MatchPred: ICmpInst::ICMP_SGT, L: m_Deferred(V: A), R: m_Zero())))))))) {
1264 APInt UpperBound = C->getUniqueInteger();
1265 APInt TruncatedMax = APInt::getAllOnes(numBits: DestTy->getIntegerBitWidth());
1266 TruncatedMax = TruncatedMax.zext(width: UpperBound.getBitWidth());
1267 if (!UpperBound.isZero() && UpperBound - 1 == TruncatedMax) {
1268 Value *SMax = Builder.CreateIntrinsic(ID: Intrinsic::smax, OverloadTypes: {SrcTy},
1269 Args: {ConstantInt::get(Ty: SrcTy, V: 0), A});
1270 Value *SMin = Builder.CreateIntrinsic(
1271 ID: Intrinsic::smin, OverloadTypes: {SrcTy},
1272 Args: {SMax, ConstantInt::get(Ty: SrcTy, V: TruncatedMax)});
1273 return new TruncInst(SMin, DestTy);
1274 }
1275 }
1276
1277 if (Instruction *I = foldVecTruncToExtElt(Trunc, IC&: *this))
1278 return I;
1279
1280 if (Instruction *I = foldVecExtTruncToExtElt(Trunc, IC&: *this))
1281 return I;
1282
1283 // trunc (ctlz_i32(zext(A), B) --> add(ctlz_i16(A, B), C)
1284 if (match(V: Src, P: m_OneUse(SubPattern: m_Ctlz(Op0: m_ZExt(Op: m_Value(V&: A)), Op1: m_Value(V&: B))))) {
1285 unsigned AWidth = A->getType()->getScalarSizeInBits();
1286 if (AWidth == DestWidth && AWidth > Log2_32(Value: SrcWidth)) {
1287 Value *WidthDiff = ConstantInt::get(Ty: A->getType(), V: SrcWidth - AWidth);
1288 Value *NarrowCtlz =
1289 Builder.CreateIntrinsic(ID: Intrinsic::ctlz, OverloadTypes: {Trunc.getType()}, Args: {A, B});
1290 return BinaryOperator::CreateAdd(V1: NarrowCtlz, V2: WidthDiff);
1291 }
1292 }
1293
1294 if (match(V: Src, P: m_VScale())) {
1295 if (Trunc.getFunction() &&
1296 Trunc.getFunction()->hasFnAttribute(Kind: Attribute::VScaleRange)) {
1297 Attribute Attr =
1298 Trunc.getFunction()->getFnAttribute(Kind: Attribute::VScaleRange);
1299 if (std::optional<unsigned> MaxVScale = Attr.getVScaleRangeMax())
1300 if (Log2_32(Value: *MaxVScale) < DestWidth)
1301 return replaceInstUsesWith(I&: Trunc, V: Builder.CreateVScale(Ty: DestTy));
1302 }
1303 }
1304
1305 // trunc(scmp(x, y)) -> scmp(x, y) with a narrower result type.
1306 // trunc(ucmp(x, y)) -> ucmp(x, y) with a narrower result type.
1307 // scmp/ucmp produce only -1, 0, or 1, so any result type with at least 2
1308 // bits can represent every possible value and the truncation is lossless.
1309 if (DestWidth >= 2)
1310 if (auto *CI = dyn_cast<CmpIntrinsic>(Val: Src); CI && CI->hasOneUse())
1311 return replaceInstUsesWith(
1312 I&: Trunc, V: Builder.CreateIntrinsic(RetTy: DestTy, ID: CI->getIntrinsicID(),
1313 Args: {CI->getLHS(), CI->getRHS()}));
1314
1315 if (DestWidth == 1 &&
1316 (Trunc.hasNoUnsignedWrap() || Trunc.hasNoSignedWrap()) &&
1317 isKnownNonZero(V: Src, Q: SQ.getWithInstruction(I: &Trunc)))
1318 return replaceInstUsesWith(I&: Trunc, V: ConstantInt::getTrue(Ty: DestTy));
1319
1320 bool Changed = false;
1321 if (!Trunc.hasNoSignedWrap() &&
1322 ComputeMaxSignificantBits(Op: Src, CxtI: &Trunc) <= DestWidth) {
1323 Trunc.setHasNoSignedWrap(true);
1324 Changed = true;
1325 }
1326 if (!Trunc.hasNoUnsignedWrap() &&
1327 MaskedValueIsZero(V: Src, Mask: APInt::getBitsSetFrom(numBits: SrcWidth, loBit: DestWidth),
1328 CxtI: &Trunc)) {
1329 Trunc.setHasNoUnsignedWrap(true);
1330 Changed = true;
1331 }
1332
1333 const APInt *C1;
1334 Value *V1;
1335 // OP = { lshr, ashr }
1336 // trunc ( OP i8 C1, V1) to i1 -> icmp eq V1, log_2(C1) iff C1 is power of 2
1337 if (DestWidth == 1 && match(V: Src, P: m_Shr(L: m_Power2(V&: C1), R: m_Value(V&: V1)))) {
1338 Value *Right = ConstantInt::get(Ty: V1->getType(), V: C1->countr_zero());
1339 return new ICmpInst(ICmpInst::ICMP_EQ, V1, Right);
1340 }
1341
1342 // OP = { lshr, ashr }
1343 // trunc ( OP i8 C1, V1) to i1 -> icmp ult V1, log_2(C1 + 1) iff (C1 + 1) is
1344 // power of 2
1345 if (DestWidth == 1 && match(V: Src, P: m_Shr(L: m_LowBitMask(V&: C1), R: m_Value(V&: V1)))) {
1346 Value *Right = ConstantInt::get(Ty: V1->getType(), V: C1->countr_one());
1347 return new ICmpInst(ICmpInst::ICMP_ULT, V1, Right);
1348 }
1349
1350 // OP = { lshr, ashr }
1351 // trunc ( OP i8 C1, V1) to i1 -> icmp ugt V1, cttz(C1) - 1 iff (C1) is
1352 // negative power of 2
1353 if (DestWidth == 1 && match(V: Src, P: m_Shr(L: m_NegatedPower2(V&: C1), R: m_Value(V&: V1)))) {
1354 Value *Right = ConstantInt::get(Ty: V1->getType(), V: C1->countr_zero());
1355 return new ICmpInst(ICmpInst::ICMP_UGE, V1, Right);
1356 }
1357
1358 return Changed ? &Trunc : nullptr;
1359}
1360
1361Instruction *InstCombinerImpl::transformZExtICmp(ICmpInst *Cmp,
1362 ZExtInst &Zext) {
1363 // If we are just checking for a icmp eq of a single bit and zext'ing it
1364 // to an integer, then shift the bit to the appropriate place and then
1365 // cast to integer to avoid the comparison.
1366
1367 // FIXME: This set of transforms does not check for extra uses and/or creates
1368 // an extra instruction (an optional final cast is not included
1369 // in the transform comments). We may also want to favor icmp over
1370 // shifts in cases of equal instructions because icmp has better
1371 // analysis in general (invert the transform).
1372
1373 const APInt *Op1CV;
1374 if (match(V: Cmp->getOperand(i_nocapture: 1), P: m_APInt(Res&: Op1CV))) {
1375
1376 // zext (x <s 0) to i32 --> x>>u31 true if signbit set.
1377 if (Cmp->getPredicate() == ICmpInst::ICMP_SLT && Op1CV->isZero()) {
1378 Value *In = Cmp->getOperand(i_nocapture: 0);
1379 Value *Sh = ConstantInt::get(Ty: In->getType(),
1380 V: In->getType()->getScalarSizeInBits() - 1);
1381 In = Builder.CreateLShr(LHS: In, RHS: Sh, Name: In->getName() + ".lobit");
1382 if (In->getType() != Zext.getType())
1383 In = Builder.CreateIntCast(V: In, DestTy: Zext.getType(), isSigned: false /*ZExt*/);
1384
1385 return replaceInstUsesWith(I&: Zext, V: In);
1386 }
1387
1388 // zext (X == 0) to i32 --> X^1 iff X has only the low bit set.
1389 // zext (X == 0) to i32 --> (X>>1)^1 iff X has only the 2nd bit set.
1390 // zext (X != 0) to i32 --> X iff X has only the low bit set.
1391 // zext (X != 0) to i32 --> X>>1 iff X has only the 2nd bit set.
1392
1393 if (Op1CV->isZero() && Cmp->isEquality()) {
1394 // Exactly 1 possible 1? But not the high-bit because that is
1395 // canonicalized to this form.
1396 KnownBits Known = computeKnownBits(V: Cmp->getOperand(i_nocapture: 0), CxtI: &Zext);
1397 APInt KnownZeroMask(~Known.Zero);
1398 uint32_t ShAmt = KnownZeroMask.logBase2();
1399 bool IsExpectShAmt = KnownZeroMask.isPowerOf2() &&
1400 (Zext.getType()->getScalarSizeInBits() != ShAmt + 1);
1401 if (IsExpectShAmt &&
1402 (Cmp->getOperand(i_nocapture: 0)->getType() == Zext.getType() ||
1403 Cmp->getPredicate() == ICmpInst::ICMP_NE || ShAmt == 0)) {
1404 Value *In = Cmp->getOperand(i_nocapture: 0);
1405 if (ShAmt) {
1406 // Perform a logical shr by shiftamt.
1407 // Insert the shift to put the result in the low bit.
1408 In = Builder.CreateLShr(LHS: In, RHS: ConstantInt::get(Ty: In->getType(), V: ShAmt),
1409 Name: In->getName() + ".lobit");
1410 }
1411
1412 // Toggle the low bit for "X == 0".
1413 if (Cmp->getPredicate() == ICmpInst::ICMP_EQ)
1414 In = Builder.CreateXor(LHS: In, RHS: ConstantInt::get(Ty: In->getType(), V: 1));
1415
1416 if (Zext.getType() == In->getType())
1417 return replaceInstUsesWith(I&: Zext, V: In);
1418
1419 Value *IntCast = Builder.CreateIntCast(V: In, DestTy: Zext.getType(), isSigned: false);
1420 return replaceInstUsesWith(I&: Zext, V: IntCast);
1421 }
1422 }
1423 }
1424
1425 if (Cmp->isEquality()) {
1426 // Test if a bit is clear/set using a shifted-one mask:
1427 // zext (icmp eq (and X, (1 << ShAmt)), 0) --> and (lshr (not X), ShAmt), 1
1428 // zext (icmp ne (and X, (1 << ShAmt)), 0) --> and (lshr X, ShAmt), 1
1429 Value *X, *ShAmt;
1430 if (Cmp->hasOneUse() && match(V: Cmp->getOperand(i_nocapture: 1), P: m_ZeroInt()) &&
1431 match(V: Cmp->getOperand(i_nocapture: 0),
1432 P: m_OneUse(SubPattern: m_c_And(L: m_Shl(L: m_One(), R: m_Value(V&: ShAmt)), R: m_Value(V&: X))))) {
1433 auto *And = cast<BinaryOperator>(Val: Cmp->getOperand(i_nocapture: 0));
1434 Value *Shift = And->getOperand(i_nocapture: X == And->getOperand(i_nocapture: 0) ? 1 : 0);
1435 if (Zext.getType() == And->getType() ||
1436 Cmp->getPredicate() != ICmpInst::ICMP_EQ || Shift->hasOneUse()) {
1437 if (Cmp->getPredicate() == ICmpInst::ICMP_EQ)
1438 X = Builder.CreateNot(V: X);
1439 Value *Lshr = Builder.CreateLShr(LHS: X, RHS: ShAmt);
1440 Value *And1 =
1441 Builder.CreateAnd(LHS: Lshr, RHS: ConstantInt::get(Ty: X->getType(), V: 1));
1442 return replaceInstUsesWith(
1443 I&: Zext, V: Builder.CreateZExtOrTrunc(V: And1, DestTy: Zext.getType()));
1444 }
1445 }
1446 }
1447
1448 return nullptr;
1449}
1450
1451/// Determine if the specified value can be computed in the specified wider type
1452/// and produce the same low bits. If not, return false.
1453///
1454/// If this function returns true, it can also return a non-zero number of bits
1455/// (in BitsToClear) which indicates that the value it computes is correct for
1456/// the zero extend, but that the additional BitsToClear bits need to be zero'd
1457/// out. For example, to promote something like:
1458///
1459/// %B = trunc i64 %A to i32
1460/// %C = lshr i32 %B, 8
1461/// %E = zext i32 %C to i64
1462///
1463/// CanEvaluateZExtd for the 'lshr' will return true, and BitsToClear will be
1464/// set to 8 to indicate that the promoted value needs to have bits 24-31
1465/// cleared in addition to bits 32-63. Since an 'and' will be generated to
1466/// clear the top bits anyway, doing this has no extra cost.
1467///
1468/// This function works on both vectors and scalars.
1469bool TypeEvaluationHelper::canEvaluateZExtd(Value *V, Type *Ty,
1470 unsigned &BitsToClear,
1471 InstCombinerImpl &IC,
1472 Instruction *CxtI) {
1473 TypeEvaluationHelper TYH;
1474 return TYH.canEvaluateZExtdImpl(V, Ty, BitsToClear, IC, CxtI);
1475}
1476bool TypeEvaluationHelper::canEvaluateZExtdImpl(Value *V, Type *Ty,
1477 unsigned &BitsToClear,
1478 InstCombinerImpl &IC,
1479 Instruction *CxtI) {
1480 BitsToClear = 0;
1481 if (canAlwaysEvaluateInType(V, Ty))
1482 return true;
1483 // We stick to the one-user limit for the ZExt transform due to the fact
1484 // that this predicate returns two values: predicate result and BitsToClear.
1485 if (canNotEvaluateInType(V, Ty))
1486 return false;
1487
1488 auto *I = cast<Instruction>(Val: V);
1489 unsigned Tmp;
1490 switch (I->getOpcode()) {
1491 case Instruction::ZExt: // zext(zext(x)) -> zext(x).
1492 case Instruction::SExt: // zext(sext(x)) -> sext(x).
1493 case Instruction::Trunc: // zext(trunc(x)) -> trunc(x) or zext(x)
1494 return true;
1495 case Instruction::And:
1496 case Instruction::Or:
1497 case Instruction::Xor:
1498 case Instruction::Add:
1499 case Instruction::Sub:
1500 case Instruction::Mul:
1501 if (!canEvaluateZExtdImpl(V: I->getOperand(i: 0), Ty, BitsToClear, IC, CxtI) ||
1502 !canEvaluateZExtdImpl(V: I->getOperand(i: 1), Ty, BitsToClear&: Tmp, IC, CxtI))
1503 return false;
1504 // These can all be promoted if neither operand has 'bits to clear'.
1505 if (BitsToClear == 0 && Tmp == 0)
1506 return true;
1507
1508 // If the operation is an AND/OR/XOR and the bits to clear are zero in the
1509 // other side, BitsToClear is ok.
1510 if (Tmp == 0 && I->isBitwiseLogicOp()) {
1511 // We use MaskedValueIsZero here for generality, but the case we care
1512 // about the most is constant RHS.
1513 unsigned VSize = V->getType()->getScalarSizeInBits();
1514 if (IC.MaskedValueIsZero(V: I->getOperand(i: 1),
1515 Mask: APInt::getHighBitsSet(numBits: VSize, hiBitsSet: BitsToClear),
1516 CxtI)) {
1517 // If this is an And instruction and all of the BitsToClear are
1518 // known to be zero we can reset BitsToClear.
1519 if (I->getOpcode() == Instruction::And)
1520 BitsToClear = 0;
1521 return true;
1522 }
1523 }
1524
1525 // Otherwise, we don't know how to analyze this BitsToClear case yet.
1526 return false;
1527
1528 case Instruction::Shl: {
1529 // We can promote shl(x, cst) if we can promote x. Since shl overwrites the
1530 // upper bits we can reduce BitsToClear by the shift amount.
1531 uint64_t ShiftAmt;
1532 if (match(V: I->getOperand(i: 1), P: m_ConstantInt(V&: ShiftAmt))) {
1533 if (!canEvaluateZExtdImpl(V: I->getOperand(i: 0), Ty, BitsToClear, IC, CxtI))
1534 return false;
1535 BitsToClear = ShiftAmt < BitsToClear ? BitsToClear - ShiftAmt : 0;
1536 return true;
1537 }
1538 return false;
1539 }
1540 case Instruction::LShr: {
1541 // We can promote lshr(x, cst) if we can promote x. This requires the
1542 // ultimate 'and' to clear out the high zero bits we're clearing out though.
1543 uint64_t ShiftAmt;
1544 if (match(V: I->getOperand(i: 1), P: m_ConstantInt(V&: ShiftAmt))) {
1545 if (!canEvaluateZExtdImpl(V: I->getOperand(i: 0), Ty, BitsToClear, IC, CxtI))
1546 return false;
1547 BitsToClear += ShiftAmt;
1548 if (BitsToClear > V->getType()->getScalarSizeInBits())
1549 BitsToClear = V->getType()->getScalarSizeInBits();
1550 return true;
1551 }
1552 // Cannot promote variable LSHR.
1553 return false;
1554 }
1555 case Instruction::Select:
1556 if (!canEvaluateZExtdImpl(V: I->getOperand(i: 1), Ty, BitsToClear&: Tmp, IC, CxtI) ||
1557 !canEvaluateZExtdImpl(V: I->getOperand(i: 2), Ty, BitsToClear, IC, CxtI) ||
1558 // TODO: If important, we could handle the case when the BitsToClear are
1559 // known zero in the disagreeing side.
1560 Tmp != BitsToClear)
1561 return false;
1562 return true;
1563
1564 case Instruction::PHI: {
1565 // We can change a phi if we can change all operands. Note that we never
1566 // get into trouble with cyclic PHIs here because we only consider
1567 // instructions with a single use.
1568 PHINode *PN = cast<PHINode>(Val: I);
1569 if (!canEvaluateZExtdImpl(V: PN->getIncomingValue(i: 0), Ty, BitsToClear, IC,
1570 CxtI))
1571 return false;
1572 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
1573 if (!canEvaluateZExtdImpl(V: PN->getIncomingValue(i), Ty, BitsToClear&: Tmp, IC, CxtI) ||
1574 // TODO: If important, we could handle the case when the BitsToClear
1575 // are known zero in the disagreeing input.
1576 Tmp != BitsToClear)
1577 return false;
1578 return true;
1579 }
1580 case Instruction::Call:
1581 // llvm.vscale() can always be executed in larger type, because the
1582 // value is automatically zero-extended.
1583 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I))
1584 if (II->getIntrinsicID() == Intrinsic::vscale)
1585 return true;
1586 return false;
1587 default:
1588 // TODO: Can handle more cases here.
1589 return false;
1590 }
1591}
1592
1593Instruction *InstCombinerImpl::visitZExt(ZExtInst &Zext) {
1594 // If this zero extend is only used by a truncate, let the truncate be
1595 // eliminated before we try to optimize this zext.
1596 if (Zext.hasOneUse() && isa<TruncInst>(Val: Zext.user_back()) &&
1597 !isa<Constant>(Val: Zext.getOperand(i_nocapture: 0)))
1598 return nullptr;
1599
1600 // If one of the common conversion will work, do it.
1601 if (Instruction *Result = commonCastTransforms(CI&: Zext))
1602 return Result;
1603
1604 if (auto *NewI = foldExtractionOfVectorDeinterleave(RootZExt&: Zext))
1605 return NewI;
1606
1607 Value *Src = Zext.getOperand(i_nocapture: 0);
1608 Type *SrcTy = Src->getType(), *DestTy = Zext.getType();
1609
1610 // zext nneg bool x -> 0
1611 if (SrcTy->isIntOrIntVectorTy(BitWidth: 1) && Zext.hasNonNeg())
1612 return replaceInstUsesWith(I&: Zext, V: Constant::getNullValue(Ty: Zext.getType()));
1613
1614 // zext nneg means Src is non-negative and we can treat this as an sext.
1615 // Evaluating as a signed type means that any constant operands will be
1616 // sign-extended instead of zero-extended, which means that, if the
1617 // expression tree contains only no-signed-wrap arithmetic, the sign bits in
1618 // the final result should be enough that we avoid having to clear the high
1619 // bits.
1620 bool EvaluateAsSigned =
1621 Zext.hasNonNeg() && TypeEvaluationHelper::canEvaluateSExtd(V: Src, Ty: DestTy);
1622
1623 // Try to extend the entire expression tree to the wide destination type.
1624 unsigned BitsToClear = 0;
1625 if (shouldChangeType(From: SrcTy, To: DestTy) &&
1626 (EvaluateAsSigned || TypeEvaluationHelper::canEvaluateZExtd(
1627 V: Src, Ty: DestTy, BitsToClear, IC&: *this, CxtI: &Zext))) {
1628 assert(BitsToClear <= SrcTy->getScalarSizeInBits() &&
1629 "Can't clear more bits than in SrcTy");
1630
1631 // Okay, we can transform this! Insert the new expression now.
1632 LLVM_DEBUG(
1633 dbgs() << "ICE: EvaluateInDifferentType converting expression type"
1634 " to avoid zero extend: "
1635 << Zext << '\n');
1636 Value *Res = EvaluateInDifferentType(V: Src, Ty: DestTy, isSigned: EvaluateAsSigned);
1637 assert(Res->getType() == DestTy);
1638
1639 // Preserve debug values referring to Src if the zext is its last use.
1640 if (auto *SrcOp = dyn_cast<Instruction>(Val: Src))
1641 if (SrcOp->hasOneUse())
1642 replaceAllDbgUsesWith(From&: *SrcOp, To&: *Res, DomPoint&: Zext, DT);
1643
1644 uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits() - BitsToClear;
1645 uint32_t DestBitSize = DestTy->getScalarSizeInBits();
1646
1647 // If the high bits are already filled with zeros, just replace this
1648 // cast with the result. If we've evaluated as a signed expressions then
1649 // instead check that the high bits are the sign bit, which we know is zero.
1650 if (EvaluateAsSigned
1651 ? (ComputeNumSignBits(Op: Res, CxtI: &Zext) > DestBitSize - SrcBitsKept)
1652 : MaskedValueIsZero(
1653 V: Res,
1654 Mask: APInt::getHighBitsSet(numBits: DestBitSize, hiBitsSet: DestBitSize - SrcBitsKept),
1655 CxtI: &Zext))
1656 return replaceInstUsesWith(I&: Zext, V: Res);
1657
1658 // We need to emit an AND to clear the high bits.
1659 Constant *C = ConstantInt::get(Ty: Res->getType(),
1660 V: APInt::getLowBitsSet(numBits: DestBitSize, loBitsSet: SrcBitsKept));
1661 return BinaryOperator::CreateAnd(V1: Res, V2: C);
1662 }
1663
1664 // If this is a TRUNC followed by a ZEXT then we are dealing with integral
1665 // types and if the sizes are just right we can convert this into a logical
1666 // 'and' which will be much cheaper than the pair of casts.
1667 if (auto *CSrc = dyn_cast<TruncInst>(Val: Src)) { // A->B->C cast
1668 // TODO: Subsume this into EvaluateInDifferentType.
1669
1670 // Get the sizes of the types involved. We know that the intermediate type
1671 // will be smaller than A or C, but don't know the relation between A and C.
1672 Value *A = CSrc->getOperand(i_nocapture: 0);
1673 unsigned SrcSize = A->getType()->getScalarSizeInBits();
1674 unsigned MidSize = CSrc->getType()->getScalarSizeInBits();
1675 unsigned DstSize = DestTy->getScalarSizeInBits();
1676 // If we're actually extending zero bits, then if
1677 // SrcSize < DstSize: zext(a & mask)
1678 // SrcSize == DstSize: a & mask
1679 // SrcSize > DstSize: trunc(a) & mask
1680 if (SrcSize < DstSize) {
1681 APInt AndValue(APInt::getLowBitsSet(numBits: SrcSize, loBitsSet: MidSize));
1682 Constant *AndConst = ConstantInt::get(Ty: A->getType(), V: AndValue);
1683 Value *And = Builder.CreateAnd(LHS: A, RHS: AndConst, Name: CSrc->getName() + ".mask");
1684 return new ZExtInst(And, DestTy);
1685 }
1686
1687 if (SrcSize == DstSize) {
1688 APInt AndValue(APInt::getLowBitsSet(numBits: SrcSize, loBitsSet: MidSize));
1689 return BinaryOperator::CreateAnd(V1: A, V2: ConstantInt::get(Ty: A->getType(),
1690 V: AndValue));
1691 }
1692 if (SrcSize > DstSize) {
1693 Value *Trunc = Builder.CreateTrunc(V: A, DestTy);
1694 APInt AndValue(APInt::getLowBitsSet(numBits: DstSize, loBitsSet: MidSize));
1695 return BinaryOperator::CreateAnd(V1: Trunc,
1696 V2: ConstantInt::get(Ty: Trunc->getType(),
1697 V: AndValue));
1698 }
1699 }
1700
1701 if (auto *Cmp = dyn_cast<ICmpInst>(Val: Src))
1702 return transformZExtICmp(Cmp, Zext);
1703
1704 Constant *C;
1705 Value *X;
1706 // zext((trunc(X) & C) ^ C) -> ((X & zext(C)) ^ zext(C)).
1707 Value *And;
1708 if (match(V: Src, P: m_OneUse(SubPattern: m_Xor(L: m_Value(V&: And), R: m_Constant(C)))) &&
1709 match(V: And, P: m_OneUse(SubPattern: m_And(L: m_Trunc(Op: m_SpecificType(RefTy: DestTy, V&: X)),
1710 R: m_Specific(V: C))))) {
1711 Value *ZC = Builder.CreateZExt(V: C, DestTy);
1712 return BinaryOperator::CreateXor(V1: Builder.CreateAnd(LHS: X, RHS: ZC), V2: ZC);
1713 }
1714
1715 // zext(sub(0, trunc(X))) -> and(sub(0, X), mask)
1716 if (match(V: Src, P: m_Sub(L: m_Zero(), R: m_Trunc(Op: m_SpecificType(RefTy: DestTy, V&: X))))) {
1717 APInt Mask = APInt::getLowBitsSet(numBits: DestTy->getScalarSizeInBits(),
1718 loBitsSet: SrcTy->getScalarSizeInBits());
1719 Value *Neg = Builder.CreateSub(LHS: ConstantInt::get(Ty: DestTy, V: 0), RHS: X);
1720 return BinaryOperator::CreateAnd(V1: Neg, V2: ConstantInt::get(Ty: DestTy, V: Mask));
1721 }
1722
1723 // If we are truncating, masking, and then zexting back to the original type,
1724 // that's just a mask. This is not handled by canEvaluateZextd if the
1725 // intermediate values have extra uses. This could be generalized further for
1726 // a non-constant mask operand.
1727 // zext (and (trunc X), C) --> and X, (zext C)
1728 if (match(V: Src, P: m_And(L: m_Trunc(Op: m_SpecificType(RefTy: DestTy, V&: X)), R: m_Constant(C)))) {
1729 Value *ZextC = Builder.CreateZExt(V: C, DestTy);
1730 return BinaryOperator::CreateAnd(V1: X, V2: ZextC);
1731 }
1732
1733 Value *Y;
1734 if (match(V: Src, P: m_OneUse(SubPattern: m_c_BitwiseLogic(
1735 L: m_NUWTrunc(Op: m_SpecificType(RefTy: DestTy, V&: X)), R: m_Value(V&: Y))))) {
1736 Value *ZextY = Builder.CreateZExt(V: Y, DestTy);
1737 return BinaryOperator::Create(Op: cast<BinaryOperator>(Val: Src)->getOpcode(), S1: X,
1738 S2: ZextY);
1739 }
1740
1741 if (match(V: Src, P: m_VScale())) {
1742 if (Zext.getFunction() &&
1743 Zext.getFunction()->hasFnAttribute(Kind: Attribute::VScaleRange)) {
1744 Attribute Attr =
1745 Zext.getFunction()->getFnAttribute(Kind: Attribute::VScaleRange);
1746 if (std::optional<unsigned> MaxVScale = Attr.getVScaleRangeMax()) {
1747 unsigned TypeWidth = Src->getType()->getScalarSizeInBits();
1748 if (Log2_32(Value: *MaxVScale) < TypeWidth)
1749 return replaceInstUsesWith(I&: Zext, V: Builder.CreateVScale(Ty: DestTy));
1750 }
1751 }
1752 }
1753
1754 if (!Zext.hasNonNeg()) {
1755 // If this zero extend is only used by a shift, add nneg flag.
1756 if (Zext.hasOneUse() &&
1757 SrcTy->getScalarSizeInBits() >
1758 Log2_64_Ceil(Value: DestTy->getScalarSizeInBits()) &&
1759 match(V: Zext.user_back(), P: m_Shift(L: m_Value(), R: m_Specific(V: &Zext)))) {
1760 Zext.setNonNeg();
1761 return &Zext;
1762 }
1763
1764 if (isKnownNonNegative(V: Src, SQ: SQ.getWithInstruction(I: &Zext))) {
1765 Zext.setNonNeg();
1766 return &Zext;
1767 }
1768 }
1769
1770 return nullptr;
1771}
1772
1773/// Transform (sext icmp) to bitwise / integer operations to eliminate the icmp.
1774Instruction *InstCombinerImpl::transformSExtICmp(ICmpInst *Cmp,
1775 SExtInst &Sext) {
1776 Value *Op0 = Cmp->getOperand(i_nocapture: 0), *Op1 = Cmp->getOperand(i_nocapture: 1);
1777 ICmpInst::Predicate Pred = Cmp->getPredicate();
1778
1779 // Don't bother if Op1 isn't of vector or integer type.
1780 if (!Op1->getType()->isIntOrIntVectorTy())
1781 return nullptr;
1782
1783 if (Pred == ICmpInst::ICMP_SLT && match(V: Op1, P: m_ZeroInt())) {
1784 // sext (x <s 0) --> ashr x, 31 (all ones if negative)
1785 Value *Sh = ConstantInt::get(Ty: Op0->getType(),
1786 V: Op0->getType()->getScalarSizeInBits() - 1);
1787 Value *In = Builder.CreateAShr(LHS: Op0, RHS: Sh, Name: Op0->getName() + ".lobit");
1788 if (In->getType() != Sext.getType())
1789 In = Builder.CreateIntCast(V: In, DestTy: Sext.getType(), isSigned: true /*SExt*/);
1790
1791 return replaceInstUsesWith(I&: Sext, V: In);
1792 }
1793
1794 if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Val: Op1)) {
1795 // If we know that only one bit of the LHS of the icmp can be set and we
1796 // have an equality comparison with zero or a power of 2, we can transform
1797 // the icmp and sext into bitwise/integer operations.
1798 if (Cmp->hasOneUse() &&
1799 Cmp->isEquality() && (Op1C->isZero() || Op1C->getValue().isPowerOf2())){
1800 KnownBits Known = computeKnownBits(V: Op0, CxtI: &Sext);
1801
1802 APInt KnownZeroMask(~Known.Zero);
1803 if (KnownZeroMask.isPowerOf2()) {
1804 Value *In = Cmp->getOperand(i_nocapture: 0);
1805
1806 // If the icmp tests for a known zero bit we can constant fold it.
1807 if (!Op1C->isZero() && Op1C->getValue() != KnownZeroMask) {
1808 Value *V = Pred == ICmpInst::ICMP_NE ?
1809 ConstantInt::getAllOnesValue(Ty: Sext.getType()) :
1810 ConstantInt::getNullValue(Ty: Sext.getType());
1811 return replaceInstUsesWith(I&: Sext, V);
1812 }
1813
1814 if (!Op1C->isZero() == (Pred == ICmpInst::ICMP_NE)) {
1815 // sext ((x & 2^n) == 0) -> (x >> n) - 1
1816 // sext ((x & 2^n) != 2^n) -> (x >> n) - 1
1817 unsigned ShiftAmt = KnownZeroMask.countr_zero();
1818 // Perform a right shift to place the desired bit in the LSB.
1819 if (ShiftAmt)
1820 In = Builder.CreateLShr(LHS: In,
1821 RHS: ConstantInt::get(Ty: In->getType(), V: ShiftAmt));
1822
1823 // At this point "In" is either 1 or 0. Subtract 1 to turn
1824 // {1, 0} -> {0, -1}.
1825 In = Builder.CreateAdd(LHS: In,
1826 RHS: ConstantInt::getAllOnesValue(Ty: In->getType()),
1827 Name: "sext");
1828 } else {
1829 // sext ((x & 2^n) != 0) -> (x << bitwidth-n) a>> bitwidth-1
1830 // sext ((x & 2^n) == 2^n) -> (x << bitwidth-n) a>> bitwidth-1
1831 unsigned ShiftAmt = KnownZeroMask.countl_zero();
1832 // Perform a left shift to place the desired bit in the MSB.
1833 if (ShiftAmt)
1834 In = Builder.CreateShl(LHS: In,
1835 RHS: ConstantInt::get(Ty: In->getType(), V: ShiftAmt));
1836
1837 // Distribute the bit over the whole bit width.
1838 In = Builder.CreateAShr(LHS: In, RHS: ConstantInt::get(Ty: In->getType(),
1839 V: KnownZeroMask.getBitWidth() - 1), Name: "sext");
1840 }
1841
1842 if (Sext.getType() == In->getType())
1843 return replaceInstUsesWith(I&: Sext, V: In);
1844 return CastInst::CreateIntegerCast(S: In, Ty: Sext.getType(), isSigned: true/*SExt*/);
1845 }
1846 }
1847 }
1848
1849 return nullptr;
1850}
1851
1852/// Return true if we can take the specified value and return it as type Ty
1853/// without inserting any new casts and without changing the value of the common
1854/// low bits. This is used by code that tries to promote integer operations to
1855/// a wider types will allow us to eliminate the extension.
1856///
1857/// This function works on both vectors and scalars.
1858///
1859bool TypeEvaluationHelper::canEvaluateSExtd(Value *V, Type *Ty) {
1860 TypeEvaluationHelper TYH;
1861 return TYH.canEvaluateSExtdImpl(V, Ty) && TYH.allPendingVisited();
1862}
1863
1864bool TypeEvaluationHelper::canEvaluateSExtdImpl(Value *V, Type *Ty) {
1865 return canEvaluate(V, Ty, Pred: [this](Value *V, Type *Ty) {
1866 return canEvaluateSExtdPred(V, Ty);
1867 });
1868}
1869
1870bool TypeEvaluationHelper::canEvaluateSExtdPred(Value *V, Type *Ty) {
1871 assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() &&
1872 "Can't sign extend type to a smaller type");
1873
1874 auto *I = cast<Instruction>(Val: V);
1875 switch (I->getOpcode()) {
1876 case Instruction::SExt: // sext(sext(x)) -> sext(x)
1877 case Instruction::ZExt: // sext(zext(x)) -> zext(x)
1878 case Instruction::Trunc: // sext(trunc(x)) -> trunc(x) or sext(x)
1879 return true;
1880 case Instruction::And:
1881 case Instruction::Or:
1882 case Instruction::Xor:
1883 case Instruction::Add:
1884 case Instruction::Sub:
1885 case Instruction::Mul:
1886 // These operators can all arbitrarily be extended if their inputs can.
1887 return canEvaluateSExtdImpl(V: I->getOperand(i: 0), Ty) &&
1888 canEvaluateSExtdImpl(V: I->getOperand(i: 1), Ty);
1889
1890 // case Instruction::Shl: TODO
1891 // case Instruction::LShr: TODO
1892
1893 case Instruction::Select:
1894 return canEvaluateSExtdImpl(V: I->getOperand(i: 1), Ty) &&
1895 canEvaluateSExtdImpl(V: I->getOperand(i: 2), Ty);
1896
1897 case Instruction::PHI: {
1898 // We can change a phi if we can change all operands. Note that we never
1899 // get into trouble with cyclic PHIs here because canEvaluate handles use
1900 // chain loops.
1901 PHINode *PN = cast<PHINode>(Val: I);
1902 for (Value *IncValue : PN->incoming_values())
1903 if (!canEvaluateSExtdImpl(V: IncValue, Ty))
1904 return false;
1905 return true;
1906 }
1907 default:
1908 // TODO: Can handle more cases here.
1909 break;
1910 }
1911
1912 return false;
1913}
1914
1915Instruction *InstCombinerImpl::visitSExt(SExtInst &Sext) {
1916 // If this sign extend is only used by a truncate, let the truncate be
1917 // eliminated before we try to optimize this sext.
1918 if (Sext.hasOneUse() && isa<TruncInst>(Val: Sext.user_back()))
1919 return nullptr;
1920
1921 if (Instruction *I = commonCastTransforms(CI&: Sext))
1922 return I;
1923
1924 Value *Src = Sext.getOperand(i_nocapture: 0);
1925 Type *SrcTy = Src->getType(), *DestTy = Sext.getType();
1926 unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1927 unsigned DestBitSize = DestTy->getScalarSizeInBits();
1928
1929 // If the value being extended is zero or positive, use a zext instead.
1930 if (isKnownNonNegative(V: Src, SQ: SQ.getWithInstruction(I: &Sext))) {
1931 auto CI = CastInst::Create(Instruction::ZExt, S: Src, Ty: DestTy);
1932 CI->setNonNeg(true);
1933 return CI;
1934 }
1935
1936 // Try to extend the entire expression tree to the wide destination type.
1937 bool ShouldExtendExpression = true;
1938 Value *TruncSrc = nullptr;
1939 // It is not desirable to extend expression in the trunc + sext pattern when
1940 // destination type is narrower than original (pre-trunc) type.
1941 if (match(V: Src, P: m_Trunc(Op: m_Value(V&: TruncSrc))))
1942 if (TruncSrc->getType()->getScalarSizeInBits() > DestBitSize)
1943 ShouldExtendExpression = false;
1944 if (ShouldExtendExpression && shouldChangeType(From: SrcTy, To: DestTy) &&
1945 TypeEvaluationHelper::canEvaluateSExtd(V: Src, Ty: DestTy)) {
1946 // Okay, we can transform this! Insert the new expression now.
1947 LLVM_DEBUG(
1948 dbgs() << "ICE: EvaluateInDifferentType converting expression type"
1949 " to avoid sign extend: "
1950 << Sext << '\n');
1951 Value *Res = EvaluateInDifferentType(V: Src, Ty: DestTy, isSigned: true);
1952 assert(Res->getType() == DestTy);
1953
1954 // If the high bits are already filled with sign bit, just replace this
1955 // cast with the result.
1956 if (ComputeNumSignBits(Op: Res, CxtI: &Sext) > DestBitSize - SrcBitSize)
1957 return replaceInstUsesWith(I&: Sext, V: Res);
1958
1959 // We need to emit a shl + ashr to do the sign extend.
1960 Value *ShAmt = ConstantInt::get(Ty: DestTy, V: DestBitSize - SrcBitSize);
1961 return BinaryOperator::CreateAShr(V1: Builder.CreateShl(LHS: Res, RHS: ShAmt, Name: "sext"),
1962 V2: ShAmt);
1963 }
1964
1965 Value *X = TruncSrc;
1966 if (X) {
1967 // If the input has more sign bits than bits truncated, then convert
1968 // directly to final type.
1969 unsigned XBitSize = X->getType()->getScalarSizeInBits();
1970 bool HasNSW = cast<TruncInst>(Val: Src)->hasNoSignedWrap();
1971 if (HasNSW || (ComputeNumSignBits(Op: X, CxtI: &Sext) > XBitSize - SrcBitSize)) {
1972 auto *Res = CastInst::CreateIntegerCast(S: X, Ty: DestTy, /* isSigned */ true);
1973 if (auto *ResTrunc = dyn_cast<TruncInst>(Val: Res); ResTrunc && HasNSW)
1974 ResTrunc->setHasNoSignedWrap(true);
1975 return Res;
1976 }
1977
1978 // If input is a trunc from the destination type, then convert into shifts.
1979 if (Src->hasOneUse() && X->getType() == DestTy) {
1980 // sext (trunc X) --> ashr (shl X, C), C
1981 Constant *ShAmt = ConstantInt::get(Ty: DestTy, V: DestBitSize - SrcBitSize);
1982 return BinaryOperator::CreateAShr(V1: Builder.CreateShl(LHS: X, RHS: ShAmt), V2: ShAmt);
1983 }
1984
1985 // If we are replacing shifted-in high zero bits with sign bits, convert
1986 // the logic shift to arithmetic shift and eliminate the cast to
1987 // intermediate type:
1988 // sext (trunc (lshr Y, C)) --> sext/trunc (ashr Y, C)
1989 Value *Y;
1990 if (Src->hasOneUse() &&
1991 match(V: X, P: m_LShr(L: m_Value(V&: Y),
1992 R: m_SpecificIntAllowPoison(V: XBitSize - SrcBitSize)))) {
1993 Value *Ashr = Builder.CreateAShr(LHS: Y, RHS: XBitSize - SrcBitSize);
1994 return CastInst::CreateIntegerCast(S: Ashr, Ty: DestTy, /* isSigned */ true);
1995 }
1996 }
1997
1998 if (auto *Cmp = dyn_cast<ICmpInst>(Val: Src))
1999 return transformSExtICmp(Cmp, Sext);
2000
2001 // If the input is a shl/ashr pair of a same constant, then this is a sign
2002 // extension from a smaller value. If we could trust arbitrary bitwidth
2003 // integers, we could turn this into a truncate to the smaller bit and then
2004 // use a sext for the whole extension. Since we don't, look deeper and check
2005 // for a truncate. If the source and dest are the same type, eliminate the
2006 // trunc and extend and just do shifts. For example, turn:
2007 // %a = trunc i32 %i to i8
2008 // %b = shl i8 %a, C
2009 // %c = ashr i8 %b, C
2010 // %d = sext i8 %c to i32
2011 // into:
2012 // %a = shl i32 %i, 32-(8-C)
2013 // %d = ashr i32 %a, 32-(8-C)
2014 Value *A = nullptr;
2015 // TODO: Eventually this could be subsumed by EvaluateInDifferentType.
2016 Constant *BA = nullptr, *CA = nullptr;
2017 if (match(V: Src,
2018 P: m_AShr(L: m_Shl(L: m_Trunc(Op: m_SpecificType(RefTy: DestTy, V&: A)), R: m_Constant(C&: BA)),
2019 R: m_ImmConstant(C&: CA))) &&
2020 BA->isElementWiseEqual(Y: CA)) {
2021 Constant *WideCurrShAmt =
2022 ConstantFoldCastOperand(Opcode: Instruction::SExt, C: CA, DestTy, DL);
2023 assert(WideCurrShAmt && "Constant folding of ImmConstant cannot fail");
2024 Constant *NumLowbitsLeft = ConstantExpr::getSub(
2025 C1: ConstantInt::get(Ty: DestTy, V: SrcTy->getScalarSizeInBits()), C2: WideCurrShAmt);
2026 Constant *NewShAmt = ConstantExpr::getSub(
2027 C1: ConstantInt::get(Ty: DestTy, V: DestTy->getScalarSizeInBits()),
2028 C2: NumLowbitsLeft);
2029 NewShAmt =
2030 Constant::mergeUndefsWith(C: Constant::mergeUndefsWith(C: NewShAmt, Other: BA), Other: CA);
2031 A = Builder.CreateShl(LHS: A, RHS: NewShAmt, Name: Sext.getName());
2032 return BinaryOperator::CreateAShr(V1: A, V2: NewShAmt);
2033 }
2034
2035 // Splatting a bit of constant-index across a value:
2036 // sext (ashr (trunc iN X to iM), M-1) to iN --> ashr (shl X, N-M), N-1
2037 // If the dest type is different, use a cast (adjust use check).
2038 if (match(V: Src, P: m_OneUse(SubPattern: m_AShr(L: m_Trunc(Op: m_Value(V&: X)),
2039 R: m_SpecificInt(V: SrcBitSize - 1))))) {
2040 Type *XTy = X->getType();
2041 unsigned XBitSize = XTy->getScalarSizeInBits();
2042 Constant *ShlAmtC = ConstantInt::get(Ty: XTy, V: XBitSize - SrcBitSize);
2043 Constant *AshrAmtC = ConstantInt::get(Ty: XTy, V: XBitSize - 1);
2044 if (XTy == DestTy)
2045 return BinaryOperator::CreateAShr(V1: Builder.CreateShl(LHS: X, RHS: ShlAmtC),
2046 V2: AshrAmtC);
2047 if (cast<BinaryOperator>(Val: Src)->getOperand(i_nocapture: 0)->hasOneUse()) {
2048 Value *Ashr = Builder.CreateAShr(LHS: Builder.CreateShl(LHS: X, RHS: ShlAmtC), RHS: AshrAmtC);
2049 return CastInst::CreateIntegerCast(S: Ashr, Ty: DestTy, /* isSigned */ true);
2050 }
2051 }
2052
2053 if (match(V: Src, P: m_VScale())) {
2054 if (Sext.getFunction() &&
2055 Sext.getFunction()->hasFnAttribute(Kind: Attribute::VScaleRange)) {
2056 Attribute Attr =
2057 Sext.getFunction()->getFnAttribute(Kind: Attribute::VScaleRange);
2058 if (std::optional<unsigned> MaxVScale = Attr.getVScaleRangeMax())
2059 if (Log2_32(Value: *MaxVScale) < (SrcBitSize - 1))
2060 return replaceInstUsesWith(I&: Sext, V: Builder.CreateVScale(Ty: DestTy));
2061 }
2062 }
2063
2064 // sext(scmp(x, y)) -> scmp(x, y) with a wider result type.
2065 // sext(ucmp(x, y)) -> ucmp(x, y) with a wider result type.
2066 // scmp/ucmp return only -1, 0, or 1, which sign-extend correctly to any
2067 // wider integer type, so we can sink the extension into the intrinsic.
2068 if (auto *CI = dyn_cast<CmpIntrinsic>(Val: Src); CI && CI->hasOneUse())
2069 return replaceInstUsesWith(
2070 I&: Sext, V: Builder.CreateIntrinsic(RetTy: DestTy, ID: CI->getIntrinsicID(),
2071 Args: {CI->getLHS(), CI->getRHS()}));
2072
2073 Value *Y;
2074 if (match(V: Src, P: m_OneUse(SubPattern: m_c_BitwiseLogic(
2075 L: m_NSWTrunc(Op: m_SpecificType(RefTy: DestTy, V&: X)), R: m_Value(V&: Y))))) {
2076 Value *SextY = Builder.CreateSExt(V: Y, DestTy);
2077 return BinaryOperator::Create(Op: cast<BinaryOperator>(Val: Src)->getOpcode(), S1: X,
2078 S2: SextY);
2079 }
2080
2081 return nullptr;
2082}
2083
2084/// Return a Constant* for the specified floating-point constant if it fits
2085/// in the specified FP type without changing its value.
2086static bool fitsInFPType(APFloat F, const fltSemantics &Sem) {
2087 bool losesInfo;
2088 (void)F.convert(ToSemantics: Sem, RM: APFloat::rmNearestTiesToEven, losesInfo: &losesInfo);
2089 return !losesInfo;
2090}
2091
2092static Type *shrinkFPConstant(LLVMContext &Ctx, const APFloat &F,
2093 bool PreferBFloat) {
2094 // See if the value can be truncated to bfloat and then reextended.
2095 if (PreferBFloat && fitsInFPType(F, Sem: APFloat::BFloat()))
2096 return Type::getBFloatTy(C&: Ctx);
2097 // See if the value can be truncated to half and then reextended.
2098 if (!PreferBFloat && fitsInFPType(F, Sem: APFloat::IEEEhalf()))
2099 return Type::getHalfTy(C&: Ctx);
2100 // See if the value can be truncated to float and then reextended.
2101 if (fitsInFPType(F, Sem: APFloat::IEEEsingle()))
2102 return Type::getFloatTy(C&: Ctx);
2103 if (&F.getSemantics() == &APFloat::IEEEdouble())
2104 return nullptr; // Won't shrink.
2105 // See if the value can be truncated to double and then reextended.
2106 if (fitsInFPType(F, Sem: APFloat::IEEEdouble()))
2107 return Type::getDoubleTy(C&: Ctx);
2108 // Don't try to shrink to various long double types.
2109 return nullptr;
2110}
2111
2112static Type *shrinkFPConstant(ConstantFP *CFP, bool PreferBFloat) {
2113 Type *Ty = CFP->getType();
2114 if (Ty->getScalarType()->isPPC_FP128Ty())
2115 return nullptr; // No constant folding of this.
2116
2117 Type *ShrinkTy =
2118 shrinkFPConstant(Ctx&: CFP->getContext(), F: CFP->getValueAPF(), PreferBFloat);
2119 if (ShrinkTy)
2120 if (auto *VecTy = dyn_cast<VectorType>(Val: Ty))
2121 ShrinkTy = VectorType::get(ElementType: ShrinkTy, Other: VecTy);
2122
2123 return ShrinkTy;
2124}
2125
2126// Determine if this is a vector of ConstantFPs and if so, return the minimal
2127// type we can safely truncate all elements to.
2128static Type *shrinkFPConstantVector(Value *V, bool PreferBFloat) {
2129 auto *CV = dyn_cast<Constant>(Val: V);
2130 auto *CVVTy = dyn_cast<FixedVectorType>(Val: V->getType());
2131 if (!CV || !CVVTy)
2132 return nullptr;
2133
2134 Type *MinType = nullptr;
2135
2136 unsigned NumElts = CVVTy->getNumElements();
2137
2138 // For fixed-width vectors we find the minimal type by looking
2139 // through the constant values of the vector.
2140 for (unsigned I = 0; I != NumElts; ++I) {
2141 if (match(V: CV->getAggregateElement(Elt: I), P: m_Poison()))
2142 continue;
2143
2144 auto *CFP = dyn_cast_or_null<ConstantFP>(Val: CV->getAggregateElement(Elt: I));
2145 if (!CFP)
2146 return nullptr;
2147
2148 Type *T = shrinkFPConstant(CFP, PreferBFloat);
2149 if (!T)
2150 return nullptr;
2151
2152 // If we haven't found a type yet or this type has a larger mantissa than
2153 // our previous type, this is our new minimal type.
2154 if (!MinType || T->getFPMantissaWidth() > MinType->getFPMantissaWidth())
2155 MinType = T;
2156 }
2157
2158 // Make a vector type from the minimal type.
2159 return MinType ? FixedVectorType::get(ElementType: MinType, NumElts) : nullptr;
2160}
2161
2162/// Find the minimum FP type we can safely truncate to.
2163static Type *getMinimumFPType(Value *V, Type *PreferredTy, InstCombiner &IC) {
2164 if (auto *FPExt = dyn_cast<FPExtInst>(Val: V))
2165 return FPExt->getOperand(i_nocapture: 0)->getType();
2166
2167 Value *Src;
2168 if (match(V, P: m_IToFP(Op: m_Value(V&: Src))) &&
2169 IC.canBeCastedExactlyIntToFP(V: Src, FPTy: PreferredTy, IsSigned: isa<SIToFPInst>(Val: V),
2170 CxtI: cast<Instruction>(Val: V)))
2171 return PreferredTy;
2172
2173 bool PreferBFloat = PreferredTy->getScalarType()->isBFloatTy();
2174 // If this value is a constant, return the constant in the smallest FP type
2175 // that can accurately represent it. This allows us to turn
2176 // (float)((double)X+2.0) into x+2.0f.
2177 if (auto *CFP = dyn_cast<ConstantFP>(Val: V))
2178 if (Type *T = shrinkFPConstant(CFP, PreferBFloat))
2179 return T;
2180
2181 // Try to shrink scalable and fixed splat vectors.
2182 if (auto *FPC = dyn_cast<Constant>(Val: V))
2183 if (auto *VTy = dyn_cast<VectorType>(Val: V->getType()))
2184 if (auto *Splat = dyn_cast_or_null<ConstantFP>(Val: FPC->getSplatValue()))
2185 if (Type *T = shrinkFPConstant(CFP: Splat, PreferBFloat))
2186 return VectorType::get(ElementType: T, Other: VTy);
2187
2188 // Try to shrink a vector of FP constants. This returns nullptr on scalable
2189 // vectors
2190 if (Type *T = shrinkFPConstantVector(V, PreferBFloat))
2191 return T;
2192
2193 return V->getType();
2194}
2195
2196bool InstCombiner::canBeCastedExactlyIntToFP(Value *V, Type *FPTy,
2197 bool IsSigned,
2198 const Instruction *CxtI) const {
2199 Type *SrcTy = V->getType();
2200 assert(SrcTy->isIntOrIntVectorTy() && "Expected an integer type");
2201 int SrcSize = (int)SrcTy->getScalarSizeInBits() - IsSigned;
2202 int DestNumSigBits = FPTy->getFPMantissaWidth();
2203
2204 // Easy case - if the source integer type has less bits than the FP mantissa,
2205 // then the cast must be exact.
2206 if (SrcSize <= DestNumSigBits)
2207 return true;
2208
2209 // Cast from FP to integer and back to FP is independent of the intermediate
2210 // integer width because of poison on overflow.
2211 Value *F;
2212 if (match(V, P: m_FPToI(Op: m_Value(V&: F)))) {
2213 // If this is uitofp (fptosi F), the source needs an extra bit to avoid
2214 // potential rounding of negative FP input values.
2215 int SrcNumSigBits = F->getType()->getFPMantissaWidth();
2216 if (!IsSigned && match(V, P: m_FPToSI(Op: m_Value())))
2217 SrcNumSigBits++;
2218
2219 // [su]itofp (fpto[su]i F) --> exact if the source type has less or equal
2220 // significant bits than the destination (and make sure neither type is
2221 // weird -- ppc_fp128).
2222 if (SrcNumSigBits > 0 && DestNumSigBits > 0 &&
2223 SrcNumSigBits <= DestNumSigBits)
2224 return true;
2225 }
2226
2227 // Try harder to find if the source integer type has less significant bits.
2228 // Compute number of sign bits or determine trailing zeros.
2229 KnownBits SrcKnown = computeKnownBits(V, CxtI);
2230 int SigBits = (int)SrcTy->getScalarSizeInBits() -
2231 SrcKnown.countMinLeadingZeros() -
2232 SrcKnown.countMinTrailingZeros();
2233 if (SigBits <= DestNumSigBits)
2234 return true;
2235
2236 // For sitofp, the sign maps to the FP sign bit, so only magnitude bits
2237 // (BitWidth - NumSignBits) consume mantissa.
2238 if (IsSigned) {
2239 SigBits = (int)SrcTy->getScalarSizeInBits() - ComputeNumSignBits(Op: V, CxtI);
2240 if (SigBits <= DestNumSigBits)
2241 return true;
2242 }
2243
2244 return false;
2245}
2246
2247bool InstCombiner::isKnownExactCastIntToFP(CastInst &I) const {
2248 CastInst::CastOps Opcode = I.getOpcode();
2249 assert((Opcode == CastInst::SIToFP || Opcode == CastInst::UIToFP) &&
2250 "Unexpected cast");
2251 Value *Src = I.getOperand(i_nocapture: 0);
2252 Type *FPTy = I.getType();
2253 return canBeCastedExactlyIntToFP(V: Src, FPTy, IsSigned: Opcode == CastInst::SIToFP, CxtI: &I);
2254}
2255
2256Instruction *InstCombinerImpl::visitFPTrunc(FPTruncInst &FPT) {
2257 if (Instruction *I = commonCastTransforms(CI&: FPT))
2258 return I;
2259
2260 // If we have fptrunc(OpI (fpextend x), (fpextend y)), we would like to
2261 // simplify this expression to avoid one or more of the trunc/extend
2262 // operations if we can do so without changing the numerical results.
2263 //
2264 // The exact manner in which the widths of the operands interact to limit
2265 // what we can and cannot do safely varies from operation to operation, and
2266 // is explained below in the various case statements.
2267 Type *Ty = FPT.getType();
2268 auto *BO = dyn_cast<BinaryOperator>(Val: FPT.getOperand(i_nocapture: 0));
2269 if (BO && BO->hasOneUse()) {
2270 Type *LHSMinType = getMinimumFPType(V: BO->getOperand(i_nocapture: 0), PreferredTy: Ty, IC&: *this);
2271 Type *RHSMinType = getMinimumFPType(V: BO->getOperand(i_nocapture: 1), PreferredTy: Ty, IC&: *this);
2272 unsigned OpWidth = BO->getType()->getFPMantissaWidth();
2273 unsigned LHSWidth = LHSMinType->getFPMantissaWidth();
2274 unsigned RHSWidth = RHSMinType->getFPMantissaWidth();
2275 unsigned SrcWidth = std::max(a: LHSWidth, b: RHSWidth);
2276 unsigned DstWidth = Ty->getFPMantissaWidth();
2277
2278 // Narrowing recomputes the binop in a smaller type, which can overflow to
2279 // inf where the wide op was finite. Therefore we can only keep ninf if
2280 // both the binop and the fptrunc have that flag.
2281 FastMathFlags NarrowFMF = BO->getFastMathFlags();
2282 NarrowFMF.setNoInfs(NarrowFMF.noInfs() && FPT.hasNoInfs());
2283
2284 switch (BO->getOpcode()) {
2285 default: break;
2286 case Instruction::FAdd:
2287 case Instruction::FSub:
2288 // For addition and subtraction, the infinitely precise result can
2289 // essentially be arbitrarily wide; proving that double rounding
2290 // will not occur because the result of OpI is exact (as we will for
2291 // FMul, for example) is hopeless. However, we *can* nonetheless
2292 // frequently know that double rounding cannot occur (or that it is
2293 // innocuous) by taking advantage of the specific structure of
2294 // infinitely-precise results that admit double rounding.
2295 //
2296 // Specifically, if OpWidth >= 2*DstWdith+1 and DstWidth is sufficient
2297 // to represent both sources, we can guarantee that the double
2298 // rounding is innocuous (See p50 of Figueroa's 2000 PhD thesis,
2299 // "A Rigorous Framework for Fully Supporting the IEEE Standard ..."
2300 // for proof of this fact).
2301 //
2302 // Note: Figueroa does not consider the case where DstFormat !=
2303 // SrcFormat. It's possible (likely even!) that this analysis
2304 // could be tightened for those cases, but they are rare (the main
2305 // case of interest here is (float)((double)float + float)).
2306 if (OpWidth >= 2*DstWidth+1 && DstWidth >= SrcWidth) {
2307 Value *LHS = Builder.CreateFPTrunc(V: BO->getOperand(i_nocapture: 0), DestTy: Ty);
2308 Value *RHS = Builder.CreateFPTrunc(V: BO->getOperand(i_nocapture: 1), DestTy: Ty);
2309 Instruction *RI = BinaryOperator::Create(Op: BO->getOpcode(), S1: LHS, S2: RHS);
2310 RI->setFastMathFlags(NarrowFMF);
2311 return RI;
2312 }
2313 break;
2314 case Instruction::FMul:
2315 // For multiplication, the infinitely precise result has at most
2316 // LHSWidth + RHSWidth significant bits; if OpWidth is sufficient
2317 // that such a value can be exactly represented, then no double
2318 // rounding can possibly occur; we can safely perform the operation
2319 // in the destination format if it can represent both sources.
2320 if (OpWidth >= LHSWidth + RHSWidth && DstWidth >= SrcWidth) {
2321 Value *LHS = Builder.CreateFPTrunc(V: BO->getOperand(i_nocapture: 0), DestTy: Ty);
2322 Value *RHS = Builder.CreateFPTrunc(V: BO->getOperand(i_nocapture: 1), DestTy: Ty);
2323 return BinaryOperator::CreateFMulFMF(V1: LHS, V2: RHS, FMF: NarrowFMF);
2324 }
2325 break;
2326 case Instruction::FDiv:
2327 // For division, we use again use the bound from Figueroa's
2328 // dissertation. I am entirely certain that this bound can be
2329 // tightened in the unbalanced operand case by an analysis based on
2330 // the diophantine rational approximation bound, but the well-known
2331 // condition used here is a good conservative first pass.
2332 // TODO: Tighten bound via rigorous analysis of the unbalanced case.
2333 if (OpWidth >= 2*DstWidth && DstWidth >= SrcWidth) {
2334 Value *LHS = Builder.CreateFPTrunc(V: BO->getOperand(i_nocapture: 0), DestTy: Ty);
2335 Value *RHS = Builder.CreateFPTrunc(V: BO->getOperand(i_nocapture: 1), DestTy: Ty);
2336 return BinaryOperator::CreateFDivFMF(V1: LHS, V2: RHS, FMF: NarrowFMF);
2337 }
2338 break;
2339 case Instruction::FRem: {
2340 // Remainder is straightforward. Remainder is always exact, so the
2341 // type of OpI doesn't enter into things at all. We simply evaluate
2342 // in whichever source type is larger, then convert to the
2343 // destination type.
2344 if (SrcWidth == OpWidth)
2345 break;
2346 Value *LHS, *RHS;
2347 if (LHSWidth == SrcWidth) {
2348 LHS = Builder.CreateFPTrunc(V: BO->getOperand(i_nocapture: 0), DestTy: LHSMinType);
2349 RHS = Builder.CreateFPTrunc(V: BO->getOperand(i_nocapture: 1), DestTy: LHSMinType);
2350 } else {
2351 LHS = Builder.CreateFPTrunc(V: BO->getOperand(i_nocapture: 0), DestTy: RHSMinType);
2352 RHS = Builder.CreateFPTrunc(V: BO->getOperand(i_nocapture: 1), DestTy: RHSMinType);
2353 }
2354
2355 Value *ExactResult = Builder.CreateFRemFMF(L: LHS, R: RHS, FMFSource: BO);
2356 return CastInst::CreateFPCast(S: ExactResult, Ty);
2357 }
2358 }
2359 }
2360
2361 // (fptrunc (fneg x)) -> (fneg (fptrunc x))
2362 Value *X;
2363 Instruction *Op = dyn_cast<Instruction>(Val: FPT.getOperand(i_nocapture: 0));
2364 if (Op && Op->hasOneUse()) {
2365 FastMathFlags FMF = FPT.getFastMathFlags();
2366 if (auto *FPMO = dyn_cast<FPMathOperator>(Val: Op))
2367 FMF &= FPMO->getFastMathFlags();
2368
2369 if (match(V: Op, P: m_FNeg(X: m_Value(V&: X)))) {
2370 Value *InnerTrunc = Builder.CreateFPTruncFMF(V: X, DestTy: Ty, FMFSource: FMF);
2371 Value *Neg = Builder.CreateFNegFMF(V: InnerTrunc, FMFSource: FMF);
2372 return replaceInstUsesWith(I&: FPT, V: Neg);
2373 }
2374
2375 // If we are truncating a select that has an extended operand, we can
2376 // narrow the other operand and do the select as a narrow op.
2377 Value *Cond, *X, *Y;
2378 if (match(V: Op, P: m_Select(C: m_Value(V&: Cond), L: m_FPExt(Op: m_SpecificType(RefTy: Ty, V&: X)),
2379 R: m_Value(V&: Y)))) {
2380 // fptrunc (select Cond, (fpext X), Y --> select Cond, X, (fptrunc Y)
2381 Value *NarrowY = Builder.CreateFPTruncFMF(V: Y, DestTy: Ty, FMFSource: FMF);
2382 Value *Sel =
2383 Builder.CreateSelectFMF(C: Cond, True: X, False: NarrowY, FMFSource: FMF, Name: "narrow.sel", MDFrom: Op);
2384 return replaceInstUsesWith(I&: FPT, V: Sel);
2385 }
2386 if (match(V: Op, P: m_Select(C: m_Value(V&: Cond), L: m_Value(V&: Y),
2387 R: m_FPExt(Op: m_SpecificType(RefTy: Ty, V&: X))))) {
2388 // fptrunc (select Cond, Y, (fpext X) --> select Cond, (fptrunc Y), X
2389 Value *NarrowY = Builder.CreateFPTruncFMF(V: Y, DestTy: Ty, FMFSource: FMF);
2390 Value *Sel =
2391 Builder.CreateSelectFMF(C: Cond, True: NarrowY, False: X, FMFSource: FMF, Name: "narrow.sel", MDFrom: Op);
2392 return replaceInstUsesWith(I&: FPT, V: Sel);
2393 }
2394 }
2395
2396 if (auto *II = dyn_cast<IntrinsicInst>(Val: FPT.getOperand(i_nocapture: 0))) {
2397 switch (II->getIntrinsicID()) {
2398 default: break;
2399 case Intrinsic::ceil:
2400 case Intrinsic::fabs:
2401 case Intrinsic::floor:
2402 case Intrinsic::nearbyint:
2403 case Intrinsic::rint:
2404 case Intrinsic::round:
2405 case Intrinsic::roundeven:
2406 case Intrinsic::trunc: {
2407 Value *Src = II->getArgOperand(i: 0);
2408 if (!Src->hasOneUse())
2409 break;
2410
2411 // Except for fabs, this transformation requires the input of the unary FP
2412 // operation to be itself an fpext from the type to which we're
2413 // truncating.
2414 if (II->getIntrinsicID() != Intrinsic::fabs) {
2415 FPExtInst *FPExtSrc = dyn_cast<FPExtInst>(Val: Src);
2416 if (!FPExtSrc || FPExtSrc->getSrcTy() != Ty)
2417 break;
2418 }
2419
2420 // Do unary FP operation on smaller type.
2421 // (fptrunc (fabs x)) -> (fabs (fptrunc x))
2422 Value *InnerTrunc = Builder.CreateFPTrunc(V: Src, DestTy: Ty);
2423 Function *Overload = Intrinsic::getOrInsertDeclaration(
2424 M: FPT.getModule(), id: II->getIntrinsicID(), OverloadTys: Ty);
2425 SmallVector<OperandBundleDef, 1> OpBundles;
2426 II->getOperandBundlesAsDefs(Defs&: OpBundles);
2427 CallInst *NewCI =
2428 CallInst::Create(Func: Overload, Args: {InnerTrunc}, Bundles: OpBundles, NameStr: II->getName());
2429 // A normal value may be converted to an infinity. It means that we cannot
2430 // propagate ninf from the intrinsic. So we propagate FMF from fptrunc.
2431 NewCI->copyFastMathFlags(I: &FPT);
2432 return NewCI;
2433 }
2434 }
2435 }
2436
2437 if (Instruction *I = shrinkInsertElt(Trunc&: FPT, Builder))
2438 return I;
2439
2440 Value *Src = FPT.getOperand(i_nocapture: 0);
2441 if (isa<SIToFPInst>(Val: Src) || isa<UIToFPInst>(Val: Src)) {
2442 auto *FPCast = cast<CastInst>(Val: Src);
2443 if (isKnownExactCastIntToFP(I&: *FPCast))
2444 return CastInst::Create(FPCast->getOpcode(), S: FPCast->getOperand(i_nocapture: 0), Ty);
2445 }
2446
2447 return nullptr;
2448}
2449
2450Instruction *InstCombinerImpl::visitFPExt(CastInst &FPExt) {
2451 // If the source operand is a cast from integer to FP and known exact, then
2452 // cast the integer operand directly to the destination type.
2453 Type *Ty = FPExt.getType();
2454 Value *Src = FPExt.getOperand(i_nocapture: 0);
2455 if (isa<SIToFPInst>(Val: Src) || isa<UIToFPInst>(Val: Src)) {
2456 auto *FPCast = cast<CastInst>(Val: Src);
2457 if (isKnownExactCastIntToFP(I&: *FPCast))
2458 return CastInst::Create(FPCast->getOpcode(), S: FPCast->getOperand(i_nocapture: 0), Ty);
2459 }
2460
2461 return commonCastTransforms(CI&: FPExt);
2462}
2463
2464/// fpto{s/u}i[.sat]({u/s}itofp(X)) --> X or zext(X) or sext(X) or trunc(X)
2465/// This is safe if the intermediate type has enough bits in its mantissa to
2466/// accurately represent all values of X. For example, this won't work with
2467/// i64 -> float -> i64.
2468template <typename FPToIntTy>
2469Instruction *InstCombinerImpl::foldItoFPtoI(FPToIntTy &FI) {
2470 constexpr bool IsSaturating = std::is_same_v<FPToIntTy, IntrinsicInst>;
2471
2472 if (!isa<UIToFPInst>(FI.getOperand(0)) && !isa<SIToFPInst>(FI.getOperand(0)))
2473 return nullptr;
2474
2475 auto *OpI = cast<CastInst>(FI.getOperand(0));
2476 Value *X = OpI->getOperand(0);
2477 Type *XType = X->getType();
2478 Type *DestType = FI.getType();
2479 bool IsInputSigned = isa<SIToFPInst>(OpI);
2480
2481 bool IsOutputSigned;
2482 if constexpr (IsSaturating)
2483 IsOutputSigned = FI.getIntrinsicID() == Intrinsic::fptosi_sat;
2484 else
2485 IsOutputSigned = isa<FPToSIInst>(FI);
2486
2487 // Since we can assume the conversion won't overflow, our decision as to
2488 // whether the input will fit in the float should depend on the minimum
2489 // of the input range and output range.
2490
2491 // This means this is also safe for a signed input and unsigned output, since
2492 // a negative input would lead to undefined behavior.
2493 if (!isKnownExactCastIntToFP(I&: *OpI)) {
2494 if constexpr (!IsSaturating) {
2495 // The first cast may not round exactly based on the source integer width
2496 // and FP width, but the overflow UB rules can still allow this to fold.
2497 // If the destination type is narrow, that means the intermediate FP value
2498 // must be large enough to hold the source value exactly.
2499 //
2500 // For example, (uint8_t)((float)(uint32_t 16777217) is UB.
2501 int OutputSize = (int)DestType->getScalarSizeInBits();
2502 if (OutputSize > OpI->getType()->getFPMantissaWidth())
2503 return nullptr;
2504 } else {
2505 // Sat intrinsics produce a defined saturated value on overflow, so
2506 // the UB-based shortcut is invalid. Require exactness.
2507 return nullptr;
2508 }
2509 }
2510
2511 unsigned SrcWidth = XType->getScalarSizeInBits();
2512 unsigned DestWidth = DestType->getScalarSizeInBits();
2513
2514 if constexpr (IsSaturating) {
2515 // TODO: cross-sign and narrowing cases could be handled with range
2516 // analysis to prove the source fits in the destination.
2517 if (IsInputSigned != IsOutputSigned || DestWidth < SrcWidth)
2518 return nullptr;
2519 }
2520
2521 if (DestWidth > SrcWidth) {
2522 if (IsInputSigned && IsOutputSigned)
2523 return new SExtInst(X, DestType);
2524 return new ZExtInst(X, DestType);
2525 }
2526 if (DestWidth < SrcWidth)
2527 return new TruncInst(X, DestType);
2528
2529 assert(XType == DestType && "Unexpected types for int to FP to int casts");
2530 return replaceInstUsesWith(I&: FI, V: X);
2531}
2532
2533template Instruction *InstCombinerImpl::foldItoFPtoI<CastInst>(CastInst &);
2534template Instruction *
2535InstCombinerImpl::foldItoFPtoI<IntrinsicInst>(IntrinsicInst &);
2536
2537static Instruction *foldFPtoI(Instruction &FI, InstCombiner &IC) {
2538 // fpto{u/s}i non-norm --> 0
2539 FPClassTest Mask =
2540 FI.getOpcode() == Instruction::FPToUI ? fcPosNormal : fcNormal;
2541 KnownFPClass FPClass = computeKnownFPClass(
2542 V: FI.getOperand(i: 0), InterestedClasses: Mask, SQ: IC.getSimplifyQuery().getWithInstruction(I: &FI));
2543 if (FPClass.isKnownNever(Mask))
2544 return IC.replaceInstUsesWith(I&: FI, V: ConstantInt::getNullValue(Ty: FI.getType()));
2545
2546 // fpto{u/s}i (fdiv ({u/s}itofp X to F), C_fp) --> {u/s}div X, C
2547 //
2548 // F has precision p (significand bits incl. hidden bit); C_fp is the exact FP
2549 // value of the integer constant C. Given N = integer width, this is safe if:
2550 // Unsigned: C > 0 and N <= p.
2551 // Signed: C != 0 and N - 1 <= p, excluding (X == INT_MIN, C == -1) since
2552 // sdiv INT_MIN, -1 is UB while the FP path only yields poison.
2553 // fdiv X, -1 gets transformed to fneg in InstCombine regardless.
2554 //
2555 // The bounds make {u/s}itofp and C_fp exact (every |int| <= 2^p is exact),
2556 // and ensure the rounded quotient never crosses an integer boundary:
2557 // Rounding lemma: for 0 <= A <= 2^p, 1 <= B <= 2^p, q = floor(A/B),
2558 // trunc(R_p(A/B)) = q.
2559 // For r = A - qB > 0, m = q+1, half-gap H(m) <= q/2^p and
2560 // m - A/B = (B-r)/B >= 1/B > q/2^p >= H(m), so R_p(A/B) < m; q = 0 is
2561 // similar (H(1) = 2^(-p-1) < 2^-p <= 1/B).
2562 // Signed case: by symmetry R_p(-z) = -R_p(z), so fptosi yields s*q = sdiv.
2563 bool IsSigned = FI.getOpcode() == Instruction::FPToSI;
2564 Value *X;
2565 const APFloat *APF;
2566 if (IsSigned) {
2567 if (!match(V: FI.getOperand(i: 0),
2568 P: m_OneUse(SubPattern: m_FDiv(L: m_SIToFP(Op: m_Value(V&: X)), R: m_APFloat(Res&: APF)))))
2569 return nullptr;
2570 } else {
2571 if (!match(V: FI.getOperand(i: 0),
2572 P: m_OneUse(SubPattern: m_FDiv(L: m_UIToFP(Op: m_Value(V&: X)), R: m_APFloat(Res&: APF)))))
2573 return nullptr;
2574 }
2575 Type *IntTy = X->getType();
2576 if (FI.getType() != IntTy)
2577 return nullptr;
2578
2579 unsigned IntWidth = IntTy->getScalarSizeInBits();
2580 unsigned Precision = APFloat::semanticsPrecision(APF->getSemantics());
2581 if (Precision + IsSigned < IntWidth)
2582 return nullptr;
2583
2584 if (!APF->isInteger())
2585 return nullptr;
2586
2587 APSInt Divisor(IntWidth, !IsSigned);
2588 bool IsExact = false;
2589 APF->convertToInteger(Result&: Divisor, RM: APFloat::rmTowardZero, IsExact: &IsExact);
2590 if (!IsExact)
2591 return nullptr;
2592
2593 if (Divisor.isZero())
2594 return nullptr;
2595
2596 // sdiv INT_MIN, -1 is UB, not poison, so this isn't valid if X == INT_MIN.
2597 // fdiv X, -1 gets transformed to fneg anyways, so we do not handle C == -1.
2598 if (IsSigned && Divisor.isAllOnes())
2599 return nullptr;
2600
2601 Constant *C = ConstantInt::get(Ty: IntTy, V: Divisor);
2602 return IsSigned ? BinaryOperator::CreateSDiv(V1: X, V2: C)
2603 : BinaryOperator::CreateUDiv(V1: X, V2: C);
2604}
2605
2606Instruction *InstCombinerImpl::visitFPToUI(FPToUIInst &FI) {
2607 if (Instruction *I = foldItoFPtoI(FI))
2608 return I;
2609
2610 if (Instruction *I = foldFPtoI(FI, IC&: *this))
2611 return I;
2612
2613 return commonCastTransforms(CI&: FI);
2614}
2615
2616Instruction *InstCombinerImpl::visitFPToSI(FPToSIInst &FI) {
2617 if (Instruction *I = foldItoFPtoI(FI))
2618 return I;
2619
2620 if (Instruction *I = foldFPtoI(FI, IC&: *this))
2621 return I;
2622
2623 return commonCastTransforms(CI&: FI);
2624}
2625
2626Instruction *InstCombinerImpl::visitUIToFP(CastInst &CI) {
2627 if (Instruction *R = commonCastTransforms(CI))
2628 return R;
2629 if (!CI.hasNonNeg() && isKnownNonNegative(V: CI.getOperand(i_nocapture: 0), SQ)) {
2630 CI.setNonNeg();
2631 return &CI;
2632 }
2633
2634 // uitofp (and (trunc X), Mask) --> uitofp (and X, zext(Mask))
2635 Value *Src = CI.getOperand(i_nocapture: 0);
2636 Value *X;
2637 Constant *Mask;
2638 if (match(V: Src, P: m_OneUse(SubPattern: m_And(L: m_OneUse(SubPattern: m_Trunc(Op: m_Value(V&: X))),
2639 R: m_ImmConstant(C&: Mask))))) {
2640 unsigned SourceWidth = Src->getType()->getScalarSizeInBits();
2641 unsigned InputWidth = X->getType()->getScalarSizeInBits();
2642 if (!DL.isLegalInteger(Width: SourceWidth) &&
2643 shouldChangeType(FromBitWidth: SourceWidth, ToBitWidth: InputWidth)) {
2644 Value *MaskedX =
2645 Builder.CreateAnd(LHS: X, RHS: Builder.CreateZExt(V: Mask, DestTy: X->getType()));
2646 auto *NewUIToFP =
2647 CastInst::Create(Instruction::UIToFP, S: MaskedX, Ty: CI.getType());
2648 NewUIToFP->setNonNeg(CI.hasNonNeg());
2649 return NewUIToFP;
2650 }
2651 }
2652
2653 return nullptr;
2654}
2655
2656Instruction *InstCombinerImpl::visitSIToFP(CastInst &CI) {
2657 if (Instruction *R = commonCastTransforms(CI))
2658 return R;
2659 if (isKnownNonNegative(V: CI.getOperand(i_nocapture: 0), SQ)) {
2660 auto *UI =
2661 CastInst::Create(Instruction::UIToFP, S: CI.getOperand(i_nocapture: 0), Ty: CI.getType());
2662 UI->setNonNeg(true);
2663 // nnan/afn/reassoc/contract/arcp carry no meaning for a value-preserving
2664 // cast, but ninf/nsz are semantically meaningful for {u,s}itofp and
2665 // remain valid after reinterpreting the operand as unsigned.
2666 UI->setHasNoInfs(CI.hasNoInfs());
2667 UI->setHasNoSignedZeros(CI.hasNoSignedZeros());
2668 return UI;
2669 }
2670 return nullptr;
2671}
2672
2673Instruction *InstCombinerImpl::visitIntToPtr(IntToPtrInst &CI) {
2674 // If the source integer type is not the intptr_t type for this target, do a
2675 // trunc or zext to the intptr_t type, then inttoptr of it. This allows the
2676 // cast to be exposed to other transforms.
2677 unsigned AS = CI.getAddressSpace();
2678 if (CI.getOperand(i_nocapture: 0)->getType()->getScalarSizeInBits() !=
2679 DL.getPointerSizeInBits(AS)) {
2680 Type *Ty = CI.getOperand(i_nocapture: 0)->getType()->getWithNewType(
2681 EltTy: DL.getIntPtrType(C&: CI.getContext(), AddressSpace: AS));
2682 Value *P = Builder.CreateZExtOrTrunc(V: CI.getOperand(i_nocapture: 0), DestTy: Ty);
2683 return new IntToPtrInst(P, CI.getType());
2684 }
2685
2686 // Replace (inttoptr (add (ptrtoint %Base), %Offset)) with
2687 // (getelementptr i8, %Base, %Offset) if the pointer is only used as integer
2688 // value.
2689 Value *Base;
2690 Value *Offset;
2691 auto UsesPointerAsInt = [](User *U) {
2692 if (isa<ICmpInst, PtrToIntInst>(Val: U))
2693 return true;
2694 if (auto *P = dyn_cast<PHINode>(Val: U))
2695 return P->hasOneUse() && isa<ICmpInst, PtrToIntInst>(Val: *P->user_begin());
2696 return false;
2697 };
2698 if (match(V: CI.getOperand(i_nocapture: 0),
2699 P: m_OneUse(SubPattern: m_c_Add(L: m_PtrToIntSameSize(DL, Op: m_Value(V&: Base)),
2700 R: m_Value(V&: Offset)))) &&
2701 CI.getType()->getPointerAddressSpace() ==
2702 Base->getType()->getPointerAddressSpace() &&
2703 all_of(Range: CI.users(), P: UsesPointerAsInt)) {
2704 return GetElementPtrInst::Create(PointeeType: Builder.getInt8Ty(), Ptr: Base, IdxList: Offset);
2705 }
2706
2707 if (Instruction *I = commonCastTransforms(CI))
2708 return I;
2709
2710 return nullptr;
2711}
2712
2713Value *InstCombinerImpl::foldPtrToIntOrAddrOfGEP(Type *IntTy, Value *Ptr) {
2714 // Look through chain of one-use GEPs.
2715 Type *PtrTy = Ptr->getType();
2716 SmallVector<GEPOperator *> GEPs;
2717 while (true) {
2718 auto *GEP = dyn_cast<GEPOperator>(Val: Ptr);
2719 if (!GEP || !GEP->hasOneUse())
2720 break;
2721 GEPs.push_back(Elt: GEP);
2722 Ptr = GEP->getPointerOperand();
2723 }
2724
2725 // Don't handle case where GEP converts from pointer to vector.
2726 if (GEPs.empty() || PtrTy != Ptr->getType())
2727 return nullptr;
2728
2729 // Check whether we know the integer value of the base pointer.
2730 Value *Res;
2731 Type *IdxTy = DL.getIndexType(PtrTy);
2732 if (match(V: Ptr, P: m_OneUse(SubPattern: m_IntToPtr(Op: m_Value(V&: Res)))) &&
2733 Res->getType() == IntTy && IntTy == IdxTy) {
2734 // pass
2735 } else if (isa<ConstantPointerNull>(Val: Ptr)) {
2736 Res = Constant::getNullValue(Ty: IdxTy);
2737 } else {
2738 return nullptr;
2739 }
2740
2741 // Perform the entire operation on integers instead.
2742 for (GEPOperator *GEP : reverse(C&: GEPs)) {
2743 Value *Offset = EmitGEPOffset(GEP);
2744 Res = Builder.CreateAdd(LHS: Res, RHS: Offset, Name: "", HasNUW: GEP->hasNoUnsignedWrap());
2745 }
2746 return Builder.CreateZExtOrTrunc(V: Res, DestTy: IntTy);
2747}
2748
2749Instruction *InstCombinerImpl::visitPtrToInt(PtrToIntInst &CI) {
2750 // If the destination integer type is not the intptr_t type for this target,
2751 // do a ptrtoint to intptr_t then do a trunc or zext. This allows the cast
2752 // to be exposed to other transforms.
2753 Value *SrcOp = CI.getPointerOperand();
2754 Type *SrcTy = SrcOp->getType();
2755 Type *Ty = CI.getType();
2756 unsigned AS = CI.getPointerAddressSpace();
2757 unsigned TySize = Ty->getScalarSizeInBits();
2758 unsigned PtrSize = DL.getPointerSizeInBits(AS);
2759 if (TySize != PtrSize) {
2760 Type *IntPtrTy =
2761 SrcTy->getWithNewType(EltTy: DL.getIntPtrType(C&: CI.getContext(), AddressSpace: AS));
2762 Value *P = Builder.CreatePtrToInt(V: SrcOp, DestTy: IntPtrTy);
2763 return CastInst::CreateIntegerCast(S: P, Ty, /*isSigned=*/false);
2764 }
2765
2766 // (ptrtoint (ptrmask P, M))
2767 // -> (and (ptrtoint P), M)
2768 // This is generally beneficial as `and` is better supported than `ptrmask`.
2769 Value *Ptr, *Mask;
2770 if (match(V: SrcOp, P: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::ptrmask>(
2771 Ops: m_Value(V&: Ptr), Ops: m_SpecificType(RefTy: Ty, V&: Mask)))))
2772 return BinaryOperator::CreateAnd(V1: Builder.CreatePtrToInt(V: Ptr, DestTy: Ty), V2: Mask);
2773
2774 if (Value *V = foldPtrToIntOrAddrOfGEP(IntTy: Ty, Ptr: SrcOp))
2775 return replaceInstUsesWith(I&: CI, V);
2776
2777 Value *Vec, *Scalar, *Index;
2778 if (match(V: SrcOp, P: m_OneUse(SubPattern: m_InsertElt(Val: m_IntToPtr(Op: m_SpecificType(RefTy: Ty, V&: Vec)),
2779 Elt: m_Value(V&: Scalar), Idx: m_Value(V&: Index))))) {
2780 assert(Vec->getType()->getScalarSizeInBits() == PtrSize && "Wrong type");
2781 // Convert the scalar to int followed by insert to eliminate one cast:
2782 // p2i (ins (i2p Vec), Scalar, Index --> ins Vec, (p2i Scalar), Index
2783 Value *NewCast = Builder.CreatePtrToInt(V: Scalar, DestTy: Ty->getScalarType());
2784 return InsertElementInst::Create(Vec, NewElt: NewCast, Idx: Index);
2785 }
2786
2787 return commonCastTransforms(CI);
2788}
2789
2790Instruction *InstCombinerImpl::visitPtrToAddr(PtrToAddrInst &CI) {
2791 Value *SrcOp = CI.getPointerOperand();
2792 Type *Ty = CI.getType();
2793
2794 // (ptrtoaddr (ptrmask P, M))
2795 // -> (and (ptrtoaddr P), M)
2796 // This is generally beneficial as `and` is better supported than `ptrmask`.
2797 Value *Ptr, *Mask;
2798 if (match(V: SrcOp, P: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::ptrmask>(
2799 Ops: m_Value(V&: Ptr), Ops: m_SpecificType(RefTy: Ty, V&: Mask)))))
2800 return BinaryOperator::CreateAnd(V1: Builder.CreatePtrToAddr(V: Ptr), V2: Mask);
2801
2802 if (Value *V = foldPtrToIntOrAddrOfGEP(IntTy: Ty, Ptr: SrcOp))
2803 return replaceInstUsesWith(I&: CI, V);
2804
2805 // FIXME: Implement variants of ptrtoint folds.
2806 return commonCastTransforms(CI);
2807}
2808
2809/// This input value (which is known to have vector type) is being zero extended
2810/// or truncated to the specified vector type. Since the zext/trunc is done
2811/// using an integer type, we have a (bitcast(cast(bitcast))) pattern,
2812/// endianness will impact which end of the vector that is extended or
2813/// truncated.
2814///
2815/// A vector is always stored with index 0 at the lowest address, which
2816/// corresponds to the most significant bits for a big endian stored integer and
2817/// the least significant bits for little endian. A trunc/zext of an integer
2818/// impacts the big end of the integer. Thus, we need to add/remove elements at
2819/// the front of the vector for big endian targets, and the back of the vector
2820/// for little endian targets.
2821///
2822/// Try to replace it with a shuffle (and vector/vector bitcast) if possible.
2823///
2824/// The source and destination vector types may have different element types.
2825static Instruction *
2826optimizeVectorResizeWithIntegerBitCasts(Value *InVal, VectorType *DestTy,
2827 InstCombinerImpl &IC) {
2828 // We can only do this optimization if the output is a multiple of the input
2829 // element size, or the input is a multiple of the output element size.
2830 // Convert the input type to have the same element type as the output.
2831 VectorType *SrcTy = cast<VectorType>(Val: InVal->getType());
2832
2833 if (SrcTy->getElementType() != DestTy->getElementType()) {
2834 // The input types don't need to be identical, but for now they must be the
2835 // same size. There is no specific reason we couldn't handle things like
2836 // <4 x i16> -> <4 x i32> by bitcasting to <2 x i32> but haven't gotten
2837 // there yet.
2838 if (SrcTy->getElementType()->getPrimitiveSizeInBits() !=
2839 DestTy->getElementType()->getPrimitiveSizeInBits())
2840 return nullptr;
2841
2842 SrcTy =
2843 FixedVectorType::get(ElementType: DestTy->getElementType(),
2844 NumElts: cast<FixedVectorType>(Val: SrcTy)->getNumElements());
2845 InVal = IC.Builder.CreateBitCast(V: InVal, DestTy: SrcTy);
2846 }
2847
2848 bool IsBigEndian = IC.getDataLayout().isBigEndian();
2849 unsigned SrcElts = cast<FixedVectorType>(Val: SrcTy)->getNumElements();
2850 unsigned DestElts = cast<FixedVectorType>(Val: DestTy)->getNumElements();
2851
2852 assert(SrcElts != DestElts && "Element counts should be different.");
2853
2854 // Now that the element types match, get the shuffle mask and RHS of the
2855 // shuffle to use, which depends on whether we're increasing or decreasing the
2856 // size of the input.
2857 auto ShuffleMaskStorage = llvm::to_vector<16>(Range: llvm::seq<int>(Begin: 0, End: SrcElts));
2858 ArrayRef<int> ShuffleMask;
2859 Value *V2;
2860
2861 if (SrcElts > DestElts) {
2862 // If we're shrinking the number of elements (rewriting an integer
2863 // truncate), just shuffle in the elements corresponding to the least
2864 // significant bits from the input and use poison as the second shuffle
2865 // input.
2866 V2 = PoisonValue::get(T: SrcTy);
2867 // Make sure the shuffle mask selects the "least significant bits" by
2868 // keeping elements from back of the src vector for big endian, and from the
2869 // front for little endian.
2870 ShuffleMask = ShuffleMaskStorage;
2871 if (IsBigEndian)
2872 ShuffleMask = ShuffleMask.take_back(N: DestElts);
2873 else
2874 ShuffleMask = ShuffleMask.take_front(N: DestElts);
2875 } else {
2876 // If we're increasing the number of elements (rewriting an integer zext),
2877 // shuffle in all of the elements from InVal. Fill the rest of the result
2878 // elements with zeros from a constant zero.
2879 V2 = Constant::getNullValue(Ty: SrcTy);
2880 // Use first elt from V2 when indicating zero in the shuffle mask.
2881 uint32_t NullElt = SrcElts;
2882 // Extend with null values in the "most significant bits" by adding elements
2883 // in front of the src vector for big endian, and at the back for little
2884 // endian.
2885 unsigned DeltaElts = DestElts - SrcElts;
2886 if (IsBigEndian)
2887 ShuffleMaskStorage.insert(I: ShuffleMaskStorage.begin(), NumToInsert: DeltaElts, Elt: NullElt);
2888 else
2889 ShuffleMaskStorage.append(NumInputs: DeltaElts, Elt: NullElt);
2890 ShuffleMask = ShuffleMaskStorage;
2891 }
2892
2893 return new ShuffleVectorInst(InVal, V2, ShuffleMask);
2894}
2895
2896static bool isMultipleOfTypeSize(unsigned Value, Type *Ty) {
2897 return Value % Ty->getPrimitiveSizeInBits() == 0;
2898}
2899
2900static unsigned getTypeSizeIndex(unsigned Value, Type *Ty) {
2901 return Value / Ty->getPrimitiveSizeInBits();
2902}
2903
2904/// V is a value which is inserted into a vector of VecEltTy.
2905/// Look through the value to see if we can decompose it into
2906/// insertions into the vector. See the example in the comment for
2907/// OptimizeIntegerToVectorInsertions for the pattern this handles.
2908/// The type of V is always a non-zero multiple of VecEltTy's size.
2909/// Shift is the number of bits between the lsb of V and the lsb of
2910/// the vector.
2911///
2912/// This returns false if the pattern can't be matched or true if it can,
2913/// filling in Elements with the elements found here.
2914static bool collectInsertionElements(Value *V, unsigned Shift,
2915 SmallVectorImpl<Value *> &Elements,
2916 Type *VecEltTy, bool isBigEndian) {
2917 assert(isMultipleOfTypeSize(Shift, VecEltTy) &&
2918 "Shift should be a multiple of the element type size");
2919
2920 // Poison values never contribute useful bits to the result.
2921 if (match(V, P: m_Poison()))
2922 return true;
2923
2924 // If we got down to a value of the right type, we win, try inserting into the
2925 // right element.
2926 if (V->getType() == VecEltTy) {
2927 // Inserting null doesn't actually insert any elements.
2928 if (Constant *C = dyn_cast<Constant>(Val: V))
2929 if (C->isNullValue())
2930 return true;
2931
2932 unsigned ElementIndex = getTypeSizeIndex(Value: Shift, Ty: VecEltTy);
2933 if (isBigEndian)
2934 ElementIndex = Elements.size() - ElementIndex - 1;
2935
2936 // Fail if multiple elements are inserted into this slot.
2937 if (Elements[ElementIndex])
2938 return false;
2939
2940 Elements[ElementIndex] = V;
2941 return true;
2942 }
2943
2944 if (Constant *C = dyn_cast<Constant>(Val: V)) {
2945 // Figure out the # elements this provides, and bitcast it or slice it up
2946 // as required.
2947 unsigned NumElts = getTypeSizeIndex(Value: C->getType()->getPrimitiveSizeInBits(),
2948 Ty: VecEltTy);
2949 // If the constant is the size of a vector element, we just need to bitcast
2950 // it to the right type so it gets properly inserted.
2951 if (NumElts == 1)
2952 return collectInsertionElements(V: ConstantExpr::getBitCast(C, Ty: VecEltTy),
2953 Shift, Elements, VecEltTy, isBigEndian);
2954
2955 // Okay, this is a constant that covers multiple elements. Slice it up into
2956 // pieces and insert each element-sized piece into the vector.
2957 if (!isa<IntegerType>(Val: C->getType()))
2958 C = ConstantExpr::getBitCast(C, Ty: IntegerType::get(C&: V->getContext(),
2959 NumBits: C->getType()->getPrimitiveSizeInBits()));
2960 unsigned ElementSize = VecEltTy->getPrimitiveSizeInBits();
2961 Type *ElementIntTy = IntegerType::get(C&: C->getContext(), NumBits: ElementSize);
2962
2963 for (unsigned i = 0; i != NumElts; ++i) {
2964 unsigned ShiftI = i * ElementSize;
2965 Constant *Piece = ConstantFoldBinaryInstruction(
2966 Opcode: Instruction::LShr, V1: C, V2: ConstantInt::get(Ty: C->getType(), V: ShiftI));
2967 if (!Piece)
2968 return false;
2969
2970 Piece = ConstantExpr::getTrunc(C: Piece, Ty: ElementIntTy);
2971 if (!collectInsertionElements(V: Piece, Shift: ShiftI + Shift, Elements, VecEltTy,
2972 isBigEndian))
2973 return false;
2974 }
2975 return true;
2976 }
2977
2978 if (!V->hasOneUse()) return false;
2979
2980 Instruction *I = dyn_cast<Instruction>(Val: V);
2981 if (!I) return false;
2982 switch (I->getOpcode()) {
2983 default: return false; // Unhandled case.
2984 case Instruction::BitCast:
2985 if (I->getOperand(i: 0)->getType()->isVectorTy())
2986 return false;
2987 return collectInsertionElements(V: I->getOperand(i: 0), Shift, Elements, VecEltTy,
2988 isBigEndian);
2989 case Instruction::ZExt:
2990 if (!isMultipleOfTypeSize(
2991 Value: I->getOperand(i: 0)->getType()->getPrimitiveSizeInBits(),
2992 Ty: VecEltTy))
2993 return false;
2994 return collectInsertionElements(V: I->getOperand(i: 0), Shift, Elements, VecEltTy,
2995 isBigEndian);
2996 case Instruction::Or:
2997 return collectInsertionElements(V: I->getOperand(i: 0), Shift, Elements, VecEltTy,
2998 isBigEndian) &&
2999 collectInsertionElements(V: I->getOperand(i: 1), Shift, Elements, VecEltTy,
3000 isBigEndian);
3001 case Instruction::Shl: {
3002 // Must be shifting by a constant that is a multiple of the element size.
3003 ConstantInt *CI = dyn_cast<ConstantInt>(Val: I->getOperand(i: 1));
3004 if (!CI) return false;
3005 Shift += CI->getZExtValue();
3006 if (!isMultipleOfTypeSize(Value: Shift, Ty: VecEltTy)) return false;
3007 return collectInsertionElements(V: I->getOperand(i: 0), Shift, Elements, VecEltTy,
3008 isBigEndian);
3009 }
3010
3011 }
3012}
3013
3014
3015/// If the input is an 'or' instruction, we may be doing shifts and ors to
3016/// assemble the elements of the vector manually.
3017/// Try to rip the code out and replace it with insertelements. This is to
3018/// optimize code like this:
3019///
3020/// %tmp37 = bitcast float %inc to i32
3021/// %tmp38 = zext i32 %tmp37 to i64
3022/// %tmp31 = bitcast float %inc5 to i32
3023/// %tmp32 = zext i32 %tmp31 to i64
3024/// %tmp33 = shl i64 %tmp32, 32
3025/// %ins35 = or i64 %tmp33, %tmp38
3026/// %tmp43 = bitcast i64 %ins35 to <2 x float>
3027///
3028/// Into two insertelements that do "buildvector{%inc, %inc5}".
3029static Value *optimizeIntegerToVectorInsertions(BitCastInst &CI,
3030 InstCombinerImpl &IC) {
3031 auto *DestVecTy = cast<FixedVectorType>(Val: CI.getType());
3032 Value *IntInput = CI.getOperand(i_nocapture: 0);
3033
3034 // if the int input is just an undef value do not try to optimize to vector
3035 // insertions as it will prevent undef propagation
3036 if (isa<UndefValue>(Val: IntInput))
3037 return nullptr;
3038
3039 SmallVector<Value*, 8> Elements(DestVecTy->getNumElements());
3040 if (!collectInsertionElements(V: IntInput, Shift: 0, Elements,
3041 VecEltTy: DestVecTy->getElementType(),
3042 isBigEndian: IC.getDataLayout().isBigEndian()))
3043 return nullptr;
3044
3045 // If we succeeded, we know that all of the element are specified by Elements
3046 // or are zero if Elements has a null entry. Recast this as a set of
3047 // insertions.
3048 Value *Result = Constant::getNullValue(Ty: CI.getType());
3049 for (unsigned i = 0, e = Elements.size(); i != e; ++i) {
3050 if (!Elements[i]) continue; // Unset element.
3051
3052 Result = IC.Builder.CreateInsertElement(Vec: Result, NewElt: Elements[i], Idx: i);
3053 }
3054
3055 return Result;
3056}
3057
3058/// Canonicalize scalar bitcasts of extracted elements into a bitcast of the
3059/// vector followed by extract element. The backend tends to handle bitcasts of
3060/// vectors better than bitcasts of scalars because vector registers are
3061/// usually not type-specific like scalar integer or scalar floating-point.
3062static Instruction *canonicalizeBitCastExtElt(BitCastInst &BitCast,
3063 InstCombinerImpl &IC) {
3064 Value *VecOp, *Index;
3065 if (!match(V: BitCast.getOperand(i_nocapture: 0),
3066 P: m_OneUse(SubPattern: m_ExtractElt(Val: m_Value(V&: VecOp), Idx: m_Value(V&: Index)))))
3067 return nullptr;
3068
3069 // The bitcast must be to a vectorizable type, otherwise we can't make a new
3070 // type to extract from.
3071 Type *DestType = BitCast.getType();
3072 VectorType *VecType = cast<VectorType>(Val: VecOp->getType());
3073 if (VectorType::isValidElementType(ElemTy: DestType)) {
3074 auto *NewVecType = VectorType::get(ElementType: DestType, Other: VecType);
3075 auto *NewBC = IC.Builder.CreateBitCast(V: VecOp, DestTy: NewVecType, Name: "bc");
3076 return ExtractElementInst::Create(Vec: NewBC, Idx: Index);
3077 }
3078
3079 // Only solve DestType is vector to avoid inverse transform in visitBitCast.
3080 // bitcast (extractelement <1 x elt>, dest) -> bitcast(<1 x elt>, dest)
3081 auto *FixedVType = dyn_cast<FixedVectorType>(Val: VecType);
3082 if (DestType->isVectorTy() && FixedVType && FixedVType->getNumElements() == 1)
3083 return CastInst::Create(Instruction::BitCast, S: VecOp, Ty: DestType);
3084
3085 return nullptr;
3086}
3087
3088/// Change the type of a bitwise logic operation if we can eliminate a bitcast.
3089static Instruction *foldBitCastBitwiseLogic(BitCastInst &BitCast,
3090 InstCombiner::BuilderTy &Builder) {
3091 Type *DestTy = BitCast.getType();
3092 BinaryOperator *BO;
3093
3094 if (!match(V: BitCast.getOperand(i_nocapture: 0), P: m_OneUse(SubPattern: m_BinOp(I&: BO))) ||
3095 !BO->isBitwiseLogicOp())
3096 return nullptr;
3097
3098 // FIXME: This transform is restricted to vector types to avoid backend
3099 // problems caused by creating potentially illegal operations. If a fix-up is
3100 // added to handle that situation, we can remove this check.
3101 if (!DestTy->isVectorTy() || !BO->getType()->isVectorTy())
3102 return nullptr;
3103
3104 if (DestTy->isFPOrFPVectorTy()) {
3105 Value *X, *Y;
3106 // bitcast(logic(bitcast(X), bitcast(Y))) -> bitcast'(logic(bitcast'(X), Y))
3107 if (match(V: BO->getOperand(i_nocapture: 0), P: m_OneUse(SubPattern: m_BitCast(Op: m_Value(V&: X)))) &&
3108 match(V: BO->getOperand(i_nocapture: 1), P: m_OneUse(SubPattern: m_BitCast(Op: m_Value(V&: Y))))) {
3109 if (X->getType()->isFPOrFPVectorTy() &&
3110 Y->getType()->isIntOrIntVectorTy()) {
3111 Value *CastedOp =
3112 Builder.CreateBitCast(V: BO->getOperand(i_nocapture: 0), DestTy: Y->getType());
3113 Value *NewBO = Builder.CreateBinOp(Opc: BO->getOpcode(), LHS: CastedOp, RHS: Y);
3114 return CastInst::CreateBitOrPointerCast(S: NewBO, Ty: DestTy);
3115 }
3116 if (X->getType()->isIntOrIntVectorTy() &&
3117 Y->getType()->isFPOrFPVectorTy()) {
3118 Value *CastedOp =
3119 Builder.CreateBitCast(V: BO->getOperand(i_nocapture: 1), DestTy: X->getType());
3120 Value *NewBO = Builder.CreateBinOp(Opc: BO->getOpcode(), LHS: CastedOp, RHS: X);
3121 return CastInst::CreateBitOrPointerCast(S: NewBO, Ty: DestTy);
3122 }
3123 }
3124 return nullptr;
3125 }
3126
3127 if (!DestTy->isIntOrIntVectorTy())
3128 return nullptr;
3129
3130 Value *X;
3131 if (match(V: BO->getOperand(i_nocapture: 0),
3132 P: m_OneUse(SubPattern: m_BitCast(Op: m_SpecificType(RefTy: DestTy, V&: X)))) &&
3133 !isa<Constant>(Val: X)) {
3134 // bitcast(logic(bitcast(X), Y)) --> logic'(X, bitcast(Y))
3135 Value *CastedOp1 = Builder.CreateBitCast(V: BO->getOperand(i_nocapture: 1), DestTy);
3136 return BinaryOperator::Create(Op: BO->getOpcode(), S1: X, S2: CastedOp1);
3137 }
3138
3139 if (match(V: BO->getOperand(i_nocapture: 1),
3140 P: m_OneUse(SubPattern: m_BitCast(Op: m_SpecificType(RefTy: DestTy, V&: X)))) &&
3141 !isa<Constant>(Val: X)) {
3142 // bitcast(logic(Y, bitcast(X))) --> logic'(bitcast(Y), X)
3143 Value *CastedOp0 = Builder.CreateBitCast(V: BO->getOperand(i_nocapture: 0), DestTy);
3144 return BinaryOperator::Create(Op: BO->getOpcode(), S1: CastedOp0, S2: X);
3145 }
3146
3147 // Canonicalize vector bitcasts to come before vector bitwise logic with a
3148 // constant. This eases recognition of special constants for later ops.
3149 // Example:
3150 // icmp u/s (a ^ signmask), (b ^ signmask) --> icmp s/u a, b
3151 Constant *C;
3152 if (match(V: BO->getOperand(i_nocapture: 1), P: m_Constant(C))) {
3153 // bitcast (logic X, C) --> logic (bitcast X, C')
3154 Value *CastedOp0 = Builder.CreateBitCast(V: BO->getOperand(i_nocapture: 0), DestTy);
3155 Value *CastedC = Builder.CreateBitCast(V: C, DestTy);
3156 return BinaryOperator::Create(Op: BO->getOpcode(), S1: CastedOp0, S2: CastedC);
3157 }
3158
3159 return nullptr;
3160}
3161
3162/// Change the type of a select if we can eliminate a bitcast.
3163static Instruction *foldBitCastSelect(BitCastInst &BitCast,
3164 InstCombiner::BuilderTy &Builder) {
3165 Value *Cond, *TVal, *FVal;
3166 if (!match(V: BitCast.getOperand(i_nocapture: 0),
3167 P: m_OneUse(SubPattern: m_Select(C: m_Value(V&: Cond), L: m_Value(V&: TVal), R: m_Value(V&: FVal)))))
3168 return nullptr;
3169
3170 // A vector select must maintain the same number of elements in its operands.
3171 Type *CondTy = Cond->getType();
3172 Type *DestTy = BitCast.getType();
3173
3174 auto *DestVecTy = dyn_cast<VectorType>(Val: DestTy);
3175
3176 if (auto *CondVTy = dyn_cast<VectorType>(Val: CondTy))
3177 if (!DestVecTy ||
3178 CondVTy->getElementCount() != DestVecTy->getElementCount())
3179 return nullptr;
3180
3181 auto *Sel = cast<Instruction>(Val: BitCast.getOperand(i_nocapture: 0));
3182 auto *SrcVecTy = dyn_cast<VectorType>(Val: TVal->getType());
3183
3184 if ((isa<Constant>(Val: TVal) || isa<Constant>(Val: FVal)) &&
3185 (!DestVecTy ||
3186 (SrcVecTy && ElementCount::isKnownLE(LHS: DestVecTy->getElementCount(),
3187 RHS: SrcVecTy->getElementCount())))) {
3188 // Avoid introducing select of vector (or select of vector with more
3189 // elements) until the backend can undo this transformation.
3190 Value *CastedTVal = Builder.CreateBitCast(V: TVal, DestTy);
3191 Value *CastedFVal = Builder.CreateBitCast(V: FVal, DestTy);
3192 return SelectInst::Create(C: Cond, S1: CastedTVal, S2: CastedFVal, NameStr: "", InsertBefore: nullptr, MDFrom: Sel);
3193 }
3194
3195 // FIXME: This transform is restricted from changing the select between
3196 // scalars and vectors to avoid backend problems caused by creating
3197 // potentially illegal operations. If a fix-up is added to handle that
3198 // situation, we can remove this check.
3199 if ((DestVecTy != nullptr) != (SrcVecTy != nullptr))
3200 return nullptr;
3201
3202 Value *X;
3203 if (match(V: TVal, P: m_OneUse(SubPattern: m_BitCast(Op: m_SpecificType(RefTy: DestTy, V&: X)))) &&
3204 !isa<Constant>(Val: X)) {
3205 // bitcast(select(Cond, bitcast(X), Y)) --> select'(Cond, X, bitcast(Y))
3206 Value *CastedVal = Builder.CreateBitCast(V: FVal, DestTy);
3207 return SelectInst::Create(C: Cond, S1: X, S2: CastedVal, NameStr: "", InsertBefore: nullptr, MDFrom: Sel);
3208 }
3209
3210 if (match(V: FVal, P: m_OneUse(SubPattern: m_BitCast(Op: m_SpecificType(RefTy: DestTy, V&: X)))) &&
3211 !isa<Constant>(Val: X)) {
3212 // bitcast(select(Cond, Y, bitcast(X))) --> select'(Cond, bitcast(Y), X)
3213 Value *CastedVal = Builder.CreateBitCast(V: TVal, DestTy);
3214 return SelectInst::Create(C: Cond, S1: CastedVal, S2: X, NameStr: "", InsertBefore: nullptr, MDFrom: Sel);
3215 }
3216
3217 return nullptr;
3218}
3219
3220/// Check if all users of CI are StoreInsts.
3221static bool hasStoreUsersOnly(CastInst &CI) {
3222 for (User *U : CI.users()) {
3223 if (!isa<StoreInst>(Val: U))
3224 return false;
3225 }
3226 return true;
3227}
3228
3229/// This function handles following case
3230///
3231/// A -> B cast
3232/// PHI
3233/// B -> A cast
3234///
3235/// All the related PHI nodes can be replaced by new PHI nodes with type A.
3236/// The uses of \p CI can be changed to the new PHI node corresponding to \p PN.
3237Instruction *InstCombinerImpl::optimizeBitCastFromPhi(CastInst &CI,
3238 PHINode *PN) {
3239 // BitCast used by Store can be handled in InstCombineLoadStoreAlloca.cpp.
3240 if (hasStoreUsersOnly(CI))
3241 return nullptr;
3242
3243 Value *Src = CI.getOperand(i_nocapture: 0);
3244 Type *SrcTy = Src->getType(); // Type B
3245 Type *DestTy = CI.getType(); // Type A
3246
3247 SmallVector<PHINode *, 4> PhiWorklist;
3248 SmallSetVector<PHINode *, 4> OldPhiNodes;
3249
3250 // Find all of the A->B casts and PHI nodes.
3251 // We need to inspect all related PHI nodes, but PHIs can be cyclic, so
3252 // OldPhiNodes is used to track all known PHI nodes, before adding a new
3253 // PHI to PhiWorklist, it is checked against and added to OldPhiNodes first.
3254 PhiWorklist.push_back(Elt: PN);
3255 OldPhiNodes.insert(X: PN);
3256 while (!PhiWorklist.empty()) {
3257 auto *OldPN = PhiWorklist.pop_back_val();
3258 for (Value *IncValue : OldPN->incoming_values()) {
3259 if (isa<Constant>(Val: IncValue))
3260 continue;
3261
3262 if (auto *LI = dyn_cast<LoadInst>(Val: IncValue)) {
3263 // If there is a sequence of one or more load instructions, each loaded
3264 // value is used as address of later load instruction, bitcast is
3265 // necessary to change the value type, don't optimize it. For
3266 // simplicity we give up if the load address comes from another load.
3267 Value *Addr = LI->getOperand(i_nocapture: 0);
3268 if (Addr == &CI || isa<LoadInst>(Val: Addr))
3269 return nullptr;
3270 // Don't tranform "load <256 x i32>, <256 x i32>*" to
3271 // "load x86_amx, x86_amx*", because x86_amx* is invalid.
3272 // TODO: Remove this check when bitcast between vector and x86_amx
3273 // is replaced with a specific intrinsic.
3274 if (DestTy->isX86_AMXTy())
3275 return nullptr;
3276 if (LI->hasOneUse() && LI->isSimple())
3277 continue;
3278 // If a LoadInst has more than one use, changing the type of loaded
3279 // value may create another bitcast.
3280 return nullptr;
3281 }
3282
3283 if (auto *PNode = dyn_cast<PHINode>(Val: IncValue)) {
3284 if (OldPhiNodes.insert(X: PNode))
3285 PhiWorklist.push_back(Elt: PNode);
3286 continue;
3287 }
3288
3289 auto *BCI = dyn_cast<BitCastInst>(Val: IncValue);
3290 // We can't handle other instructions.
3291 if (!BCI)
3292 return nullptr;
3293
3294 // Verify it's a A->B cast.
3295 Type *TyA = BCI->getOperand(i_nocapture: 0)->getType();
3296 Type *TyB = BCI->getType();
3297 if (TyA != DestTy || TyB != SrcTy)
3298 return nullptr;
3299 }
3300 }
3301
3302 // Check that each user of each old PHI node is something that we can
3303 // rewrite, so that all of the old PHI nodes can be cleaned up afterwards.
3304 for (auto *OldPN : OldPhiNodes) {
3305 for (User *V : OldPN->users()) {
3306 if (auto *SI = dyn_cast<StoreInst>(Val: V)) {
3307 if (!SI->isSimple() || SI->getOperand(i_nocapture: 0) != OldPN)
3308 return nullptr;
3309 } else if (auto *BCI = dyn_cast<BitCastInst>(Val: V)) {
3310 // Verify it's a B->A cast.
3311 Type *TyB = BCI->getOperand(i_nocapture: 0)->getType();
3312 Type *TyA = BCI->getType();
3313 if (TyA != DestTy || TyB != SrcTy)
3314 return nullptr;
3315 } else if (auto *PHI = dyn_cast<PHINode>(Val: V)) {
3316 // As long as the user is another old PHI node, then even if we don't
3317 // rewrite it, the PHI web we're considering won't have any users
3318 // outside itself, so it'll be dead.
3319 if (!OldPhiNodes.contains(key: PHI))
3320 return nullptr;
3321 } else {
3322 return nullptr;
3323 }
3324 }
3325 }
3326
3327 // For each old PHI node, create a corresponding new PHI node with a type A.
3328 SmallDenseMap<PHINode *, PHINode *> NewPNodes;
3329 for (auto *OldPN : OldPhiNodes) {
3330 Builder.SetInsertPoint(OldPN);
3331 PHINode *NewPN = Builder.CreatePHI(Ty: DestTy, NumReservedValues: OldPN->getNumOperands());
3332 NewPNodes[OldPN] = NewPN;
3333 }
3334
3335 // Fill in the operands of new PHI nodes.
3336 for (auto *OldPN : OldPhiNodes) {
3337 PHINode *NewPN = NewPNodes[OldPN];
3338 for (unsigned j = 0, e = OldPN->getNumOperands(); j != e; ++j) {
3339 Value *V = OldPN->getOperand(i_nocapture: j);
3340 Value *NewV = nullptr;
3341 if (auto *C = dyn_cast<Constant>(Val: V)) {
3342 NewV = ConstantExpr::getBitCast(C, Ty: DestTy);
3343 } else if (auto *LI = dyn_cast<LoadInst>(Val: V)) {
3344 // Explicitly perform load combine to make sure no opposing transform
3345 // can remove the bitcast in the meantime and trigger an infinite loop.
3346 Builder.SetInsertPoint(LI);
3347 NewV = combineLoadToNewType(LI&: *LI, NewTy: DestTy);
3348 // Remove the old load and its use in the old phi, which itself becomes
3349 // dead once the whole transform finishes.
3350 replaceInstUsesWith(I&: *LI, V: PoisonValue::get(T: LI->getType()));
3351 eraseInstFromFunction(I&: *LI);
3352 } else if (auto *BCI = dyn_cast<BitCastInst>(Val: V)) {
3353 NewV = BCI->getOperand(i_nocapture: 0);
3354 } else if (auto *PrevPN = dyn_cast<PHINode>(Val: V)) {
3355 NewV = NewPNodes[PrevPN];
3356 }
3357 assert(NewV);
3358 NewPN->addIncoming(V: NewV, BB: OldPN->getIncomingBlock(i: j));
3359 }
3360 }
3361
3362 // Traverse all accumulated PHI nodes and process its users,
3363 // which are Stores and BitcCasts. Without this processing
3364 // NewPHI nodes could be replicated and could lead to extra
3365 // moves generated after DeSSA.
3366 // If there is a store with type B, change it to type A.
3367
3368
3369 // Replace users of BitCast B->A with NewPHI. These will help
3370 // later to get rid off a closure formed by OldPHI nodes.
3371 Instruction *RetVal = nullptr;
3372 for (auto *OldPN : OldPhiNodes) {
3373 PHINode *NewPN = NewPNodes[OldPN];
3374 for (User *V : make_early_inc_range(Range: OldPN->users())) {
3375 if (auto *SI = dyn_cast<StoreInst>(Val: V)) {
3376 assert(SI->isSimple() && SI->getOperand(0) == OldPN);
3377 Builder.SetInsertPoint(SI);
3378 auto *NewBC =
3379 cast<BitCastInst>(Val: Builder.CreateBitCast(V: NewPN, DestTy: SrcTy));
3380 SI->setOperand(i_nocapture: 0, Val_nocapture: NewBC);
3381 Worklist.push(I: SI);
3382 assert(hasStoreUsersOnly(*NewBC));
3383 }
3384 else if (auto *BCI = dyn_cast<BitCastInst>(Val: V)) {
3385 Type *TyB = BCI->getOperand(i_nocapture: 0)->getType();
3386 Type *TyA = BCI->getType();
3387 assert(TyA == DestTy && TyB == SrcTy);
3388 (void) TyA;
3389 (void) TyB;
3390 Instruction *I = replaceInstUsesWith(I&: *BCI, V: NewPN);
3391 if (BCI == &CI)
3392 RetVal = I;
3393 } else if (auto *PHI = dyn_cast<PHINode>(Val: V)) {
3394 assert(OldPhiNodes.contains(PHI));
3395 (void) PHI;
3396 } else {
3397 llvm_unreachable("all uses should be handled");
3398 }
3399 }
3400 }
3401
3402 return RetVal;
3403}
3404
3405/// Fold (bitcast (or (and (bitcast X to int), signmask), nneg Y) to fp) to
3406/// copysign((bitcast Y to fp), X)
3407static Value *foldCopySignIdioms(BitCastInst &CI,
3408 InstCombiner::BuilderTy &Builder,
3409 const SimplifyQuery &SQ) {
3410 Value *X, *Y;
3411 Type *FTy = CI.getType();
3412 if (!FTy->isFPOrFPVectorTy())
3413 return nullptr;
3414 if (!match(V: &CI, P: m_ElementWiseBitCast(Op: m_c_Or(
3415 L: m_And(L: m_ElementWiseBitCast(Op: m_Value(V&: X)), R: m_SignMask()),
3416 R: m_Value(V&: Y)))))
3417 return nullptr;
3418 if (X->getType() != FTy)
3419 return nullptr;
3420 if (!isKnownNonNegative(V: Y, SQ))
3421 return nullptr;
3422
3423 return Builder.CreateCopySign(LHS: Builder.CreateBitCast(V: Y, DestTy: FTy), RHS: X);
3424}
3425
3426Instruction *InstCombinerImpl::visitBitCast(BitCastInst &CI) {
3427 // If the operands are integer typed then apply the integer transforms,
3428 // otherwise just apply the common ones.
3429 Value *Src = CI.getOperand(i_nocapture: 0);
3430 Type *SrcTy = Src->getType();
3431 Type *DestTy = CI.getType();
3432
3433 // Get rid of casts from one type to the same type. These are useless and can
3434 // be replaced by the operand.
3435 if (DestTy == Src->getType())
3436 return replaceInstUsesWith(I&: CI, V: Src);
3437
3438 if (isa<FixedVectorType>(Val: DestTy)) {
3439 if (isa<IntegerType>(Val: SrcTy)) {
3440 // If this is a cast from an integer to vector, check to see if the input
3441 // is a trunc or zext of a bitcast from vector. If so, we can replace all
3442 // the casts with a shuffle and (potentially) a bitcast.
3443 if (isa<TruncInst>(Val: Src) || isa<ZExtInst>(Val: Src)) {
3444 CastInst *SrcCast = cast<CastInst>(Val: Src);
3445 if (BitCastInst *BCIn = dyn_cast<BitCastInst>(Val: SrcCast->getOperand(i_nocapture: 0)))
3446 if (isa<VectorType>(Val: BCIn->getOperand(i_nocapture: 0)->getType()))
3447 if (Instruction *I = optimizeVectorResizeWithIntegerBitCasts(
3448 InVal: BCIn->getOperand(i_nocapture: 0), DestTy: cast<VectorType>(Val: DestTy), IC&: *this))
3449 return I;
3450 }
3451
3452 // If the input is an 'or' instruction, we may be doing shifts and ors to
3453 // assemble the elements of the vector manually. Try to rip the code out
3454 // and replace it with insertelements.
3455 if (Value *V = optimizeIntegerToVectorInsertions(CI, IC&: *this))
3456 return replaceInstUsesWith(I&: CI, V);
3457 }
3458 }
3459
3460 if (FixedVectorType *SrcVTy = dyn_cast<FixedVectorType>(Val: SrcTy)) {
3461 if (SrcVTy->getNumElements() == 1) {
3462 // If our destination is not a vector, then make this a straight
3463 // scalar-scalar cast.
3464 if (!DestTy->isVectorTy()) {
3465 Value *Elem = Builder.CreateExtractElement(Vec: Src, Idx: uint64_t{0});
3466 return CastInst::Create(Instruction::BitCast, S: Elem, Ty: DestTy);
3467 }
3468
3469 // Otherwise, see if our source is an insert. If so, then use the scalar
3470 // component directly:
3471 // bitcast (inselt <1 x elt> V, X, 0) to <n x m> --> bitcast X to <n x m>
3472 if (auto *InsElt = dyn_cast<InsertElementInst>(Val: Src))
3473 return new BitCastInst(InsElt->getOperand(i_nocapture: 1), DestTy);
3474 }
3475
3476 // Convert an artificial vector insert into more analyzable bitwise logic.
3477 unsigned BitWidth = DestTy->getScalarSizeInBits();
3478 Value *X, *Y;
3479 uint64_t IndexC;
3480 if (match(V: Src, P: m_OneUse(SubPattern: m_InsertElt(
3481 Val: m_OneUse(SubPattern: m_BitCast(Op: m_SpecificType(RefTy: DestTy, V&: X))),
3482 Elt: m_Value(V&: Y), Idx: m_ConstantInt(V&: IndexC)))) &&
3483 DestTy->isIntegerTy() && Y->getType()->isIntegerTy() &&
3484 isDesirableIntType(BitWidth)) {
3485 // Adjust for big endian - the LSBs are at the high index.
3486 if (DL.isBigEndian())
3487 IndexC = SrcVTy->getNumElements() - 1 - IndexC;
3488
3489 // We only handle (endian-normalized) insert to index 0. Any other insert
3490 // would require a left-shift, so that is an extra instruction.
3491 if (IndexC == 0) {
3492 // bitcast (inselt (bitcast X), Y, 0) --> or (and X, MaskC), (zext Y)
3493 unsigned EltWidth = Y->getType()->getScalarSizeInBits();
3494 APInt MaskC = APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: BitWidth - EltWidth);
3495 Value *AndX = Builder.CreateAnd(LHS: X, RHS: MaskC);
3496 Value *ZextY = Builder.CreateZExt(V: Y, DestTy);
3497 return BinaryOperator::CreateOr(V1: AndX, V2: ZextY);
3498 }
3499 }
3500 }
3501
3502 if (auto *Shuf = dyn_cast<ShuffleVectorInst>(Val: Src)) {
3503 // Okay, we have (bitcast (shuffle ..)). Check to see if this is
3504 // a bitcast to a vector with the same # elts.
3505 Value *ShufOp0 = Shuf->getOperand(i_nocapture: 0);
3506 Value *ShufOp1 = Shuf->getOperand(i_nocapture: 1);
3507 auto ShufElts = cast<VectorType>(Val: Shuf->getType())->getElementCount();
3508 auto SrcVecElts = cast<VectorType>(Val: ShufOp0->getType())->getElementCount();
3509 if (Shuf->hasOneUse() && DestTy->isVectorTy() &&
3510 cast<VectorType>(Val: DestTy)->getElementCount() == ShufElts &&
3511 ShufElts == SrcVecElts) {
3512 BitCastInst *Tmp;
3513 // If either of the operands is a cast from CI.getType(), then
3514 // evaluating the shuffle in the casted destination's type will allow
3515 // us to eliminate at least one cast.
3516 if (((Tmp = dyn_cast<BitCastInst>(Val: ShufOp0)) &&
3517 Tmp->getOperand(i_nocapture: 0)->getType() == DestTy) ||
3518 ((Tmp = dyn_cast<BitCastInst>(Val: ShufOp1)) &&
3519 Tmp->getOperand(i_nocapture: 0)->getType() == DestTy)) {
3520 Value *LHS = Builder.CreateBitCast(V: ShufOp0, DestTy);
3521 Value *RHS = Builder.CreateBitCast(V: ShufOp1, DestTy);
3522 // Return a new shuffle vector. Use the same element ID's, as we
3523 // know the vector types match #elts.
3524 return new ShuffleVectorInst(LHS, RHS, Shuf->getShuffleMask());
3525 }
3526 }
3527
3528 // A bitcasted-to-scalar and byte/bit reversing shuffle is better recognized
3529 // as a byte/bit swap:
3530 // bitcast <N x i8> (shuf X, undef, <N, N-1,...0>) -> bswap (bitcast X)
3531 // bitcast <N x i1> (shuf X, undef, <N, N-1,...0>) -> bitreverse (bitcast X)
3532 if (DestTy->isIntegerTy() && ShufElts.getKnownMinValue() % 2 == 0 &&
3533 Shuf->hasOneUse() && Shuf->isReverse() && match(V: ShufOp1, P: m_Poison())) {
3534 unsigned IntrinsicNum = 0;
3535 if (DL.isLegalInteger(Width: DestTy->getScalarSizeInBits()) &&
3536 SrcTy->getScalarSizeInBits() == 8) {
3537 IntrinsicNum = Intrinsic::bswap;
3538 } else if (SrcTy->getScalarSizeInBits() == 1) {
3539 IntrinsicNum = Intrinsic::bitreverse;
3540 }
3541 if (IntrinsicNum != 0) {
3542 assert(ShufOp0->getType() == SrcTy && "Unexpected shuffle mask");
3543 Function *BswapOrBitreverse = Intrinsic::getOrInsertDeclaration(
3544 M: CI.getModule(), id: IntrinsicNum, OverloadTys: DestTy);
3545 Value *ScalarX = Builder.CreateBitCast(V: ShufOp0, DestTy);
3546 return CallInst::Create(Func: BswapOrBitreverse, Args: {ScalarX});
3547 }
3548 }
3549 }
3550
3551 // Handle the A->B->A cast, and there is an intervening PHI node.
3552 if (PHINode *PN = dyn_cast<PHINode>(Val: Src))
3553 if (Instruction *I = optimizeBitCastFromPhi(CI, PN))
3554 return I;
3555
3556 if (Instruction *I = canonicalizeBitCastExtElt(BitCast&: CI, IC&: *this))
3557 return I;
3558
3559 if (Instruction *I = foldBitCastBitwiseLogic(BitCast&: CI, Builder))
3560 return I;
3561
3562 if (Instruction *I = foldBitCastSelect(BitCast&: CI, Builder))
3563 return I;
3564
3565 if (Value *V = foldCopySignIdioms(CI, Builder, SQ: SQ.getWithInstruction(I: &CI)))
3566 return replaceInstUsesWith(I&: CI, V);
3567
3568 return commonCastTransforms(CI);
3569}
3570
3571Instruction *InstCombinerImpl::visitAddrSpaceCast(AddrSpaceCastInst &CI) {
3572 return commonCastTransforms(CI);
3573}
3574