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