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