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