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/SetVector.h"
15 #include "llvm/Analysis/ConstantFolding.h"
16 #include "llvm/Analysis/TargetLibraryInfo.h"
17 #include "llvm/IR/DIBuilder.h"
18 #include "llvm/IR/DataLayout.h"
19 #include "llvm/IR/PatternMatch.h"
20 #include "llvm/Support/KnownBits.h"
21 #include "llvm/Transforms/InstCombine/InstCombiner.h"
22 #include <numeric>
23 using namespace llvm;
24 using namespace PatternMatch;
25
26 #define DEBUG_TYPE "instcombine"
27
28 /// Analyze 'Val', seeing if it is a simple linear expression.
29 /// If so, decompose it, returning some value X, such that Val is
30 /// X*Scale+Offset.
31 ///
decomposeSimpleLinearExpr(Value * Val,unsigned & Scale,uint64_t & Offset)32 static Value *decomposeSimpleLinearExpr(Value *Val, unsigned &Scale,
33 uint64_t &Offset) {
34 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val)) {
35 Offset = CI->getZExtValue();
36 Scale = 0;
37 return ConstantInt::get(Val->getType(), 0);
38 }
39
40 if (BinaryOperator *I = dyn_cast<BinaryOperator>(Val)) {
41 // Cannot look past anything that might overflow.
42 OverflowingBinaryOperator *OBI = dyn_cast<OverflowingBinaryOperator>(Val);
43 if (OBI && !OBI->hasNoUnsignedWrap() && !OBI->hasNoSignedWrap()) {
44 Scale = 1;
45 Offset = 0;
46 return Val;
47 }
48
49 if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
50 if (I->getOpcode() == Instruction::Shl) {
51 // This is a value scaled by '1 << the shift amt'.
52 Scale = UINT64_C(1) << RHS->getZExtValue();
53 Offset = 0;
54 return I->getOperand(0);
55 }
56
57 if (I->getOpcode() == Instruction::Mul) {
58 // This value is scaled by 'RHS'.
59 Scale = RHS->getZExtValue();
60 Offset = 0;
61 return I->getOperand(0);
62 }
63
64 if (I->getOpcode() == Instruction::Add) {
65 // We have X+C. Check to see if we really have (X*C2)+C1,
66 // where C1 is divisible by C2.
67 unsigned SubScale;
68 Value *SubVal =
69 decomposeSimpleLinearExpr(I->getOperand(0), SubScale, Offset);
70 Offset += RHS->getZExtValue();
71 Scale = SubScale;
72 return SubVal;
73 }
74 }
75 }
76
77 // Otherwise, we can't look past this.
78 Scale = 1;
79 Offset = 0;
80 return Val;
81 }
82
83 /// If we find a cast of an allocation instruction, try to eliminate the cast by
84 /// moving the type information into the alloc.
PromoteCastOfAllocation(BitCastInst & CI,AllocaInst & AI)85 Instruction *InstCombinerImpl::PromoteCastOfAllocation(BitCastInst &CI,
86 AllocaInst &AI) {
87 PointerType *PTy = cast<PointerType>(CI.getType());
88
89 IRBuilderBase::InsertPointGuard Guard(Builder);
90 Builder.SetInsertPoint(&AI);
91
92 // Get the type really allocated and the type casted to.
93 Type *AllocElTy = AI.getAllocatedType();
94 Type *CastElTy = PTy->getElementType();
95 if (!AllocElTy->isSized() || !CastElTy->isSized()) return nullptr;
96
97 // This optimisation does not work for cases where the cast type
98 // is scalable and the allocated type is not. This because we need to
99 // know how many times the casted type fits into the allocated type.
100 // For the opposite case where the allocated type is scalable and the
101 // cast type is not this leads to poor code quality due to the
102 // introduction of 'vscale' into the calculations. It seems better to
103 // bail out for this case too until we've done a proper cost-benefit
104 // analysis.
105 bool AllocIsScalable = isa<ScalableVectorType>(AllocElTy);
106 bool CastIsScalable = isa<ScalableVectorType>(CastElTy);
107 if (AllocIsScalable != CastIsScalable) return nullptr;
108
109 Align AllocElTyAlign = DL.getABITypeAlign(AllocElTy);
110 Align CastElTyAlign = DL.getABITypeAlign(CastElTy);
111 if (CastElTyAlign < AllocElTyAlign) return nullptr;
112
113 // If the allocation has multiple uses, only promote it if we are strictly
114 // increasing the alignment of the resultant allocation. If we keep it the
115 // same, we open the door to infinite loops of various kinds.
116 if (!AI.hasOneUse() && CastElTyAlign == AllocElTyAlign) return nullptr;
117
118 // The alloc and cast types should be either both fixed or both scalable.
119 uint64_t AllocElTySize = DL.getTypeAllocSize(AllocElTy).getKnownMinSize();
120 uint64_t CastElTySize = DL.getTypeAllocSize(CastElTy).getKnownMinSize();
121 if (CastElTySize == 0 || AllocElTySize == 0) return nullptr;
122
123 // If the allocation has multiple uses, only promote it if we're not
124 // shrinking the amount of memory being allocated.
125 uint64_t AllocElTyStoreSize = DL.getTypeStoreSize(AllocElTy).getKnownMinSize();
126 uint64_t CastElTyStoreSize = DL.getTypeStoreSize(CastElTy).getKnownMinSize();
127 if (!AI.hasOneUse() && CastElTyStoreSize < AllocElTyStoreSize) return nullptr;
128
129 // See if we can satisfy the modulus by pulling a scale out of the array
130 // size argument.
131 unsigned ArraySizeScale;
132 uint64_t ArrayOffset;
133 Value *NumElements = // See if the array size is a decomposable linear expr.
134 decomposeSimpleLinearExpr(AI.getOperand(0), ArraySizeScale, ArrayOffset);
135
136 // If we can now satisfy the modulus, by using a non-1 scale, we really can
137 // do the xform.
138 if ((AllocElTySize*ArraySizeScale) % CastElTySize != 0 ||
139 (AllocElTySize*ArrayOffset ) % CastElTySize != 0) return nullptr;
140
141 // We don't currently support arrays of scalable types.
142 assert(!AllocIsScalable || (ArrayOffset == 1 && ArraySizeScale == 0));
143
144 unsigned Scale = (AllocElTySize*ArraySizeScale)/CastElTySize;
145 Value *Amt = nullptr;
146 if (Scale == 1) {
147 Amt = NumElements;
148 } else {
149 Amt = ConstantInt::get(AI.getArraySize()->getType(), Scale);
150 // Insert before the alloca, not before the cast.
151 Amt = Builder.CreateMul(Amt, NumElements);
152 }
153
154 if (uint64_t Offset = (AllocElTySize*ArrayOffset)/CastElTySize) {
155 Value *Off = ConstantInt::get(AI.getArraySize()->getType(),
156 Offset, true);
157 Amt = Builder.CreateAdd(Amt, Off);
158 }
159
160 AllocaInst *New = Builder.CreateAlloca(CastElTy, Amt);
161 New->setAlignment(AI.getAlign());
162 New->takeName(&AI);
163 New->setUsedWithInAlloca(AI.isUsedWithInAlloca());
164
165 // If the allocation has multiple real uses, insert a cast and change all
166 // things that used it to use the new cast. This will also hack on CI, but it
167 // will die soon.
168 if (!AI.hasOneUse()) {
169 // New is the allocation instruction, pointer typed. AI is the original
170 // allocation instruction, also pointer typed. Thus, cast to use is BitCast.
171 Value *NewCast = Builder.CreateBitCast(New, AI.getType(), "tmpcast");
172 replaceInstUsesWith(AI, NewCast);
173 eraseInstFromFunction(AI);
174 }
175 return replaceInstUsesWith(CI, New);
176 }
177
178 /// Given an expression that CanEvaluateTruncated or CanEvaluateSExtd returns
179 /// true for, actually insert the code to evaluate the expression.
EvaluateInDifferentType(Value * V,Type * Ty,bool isSigned)180 Value *InstCombinerImpl::EvaluateInDifferentType(Value *V, Type *Ty,
181 bool isSigned) {
182 if (Constant *C = dyn_cast<Constant>(V)) {
183 C = ConstantExpr::getIntegerCast(C, Ty, isSigned /*Sext or ZExt*/);
184 // If we got a constantexpr back, try to simplify it with DL info.
185 return ConstantFoldConstant(C, DL, &TLI);
186 }
187
188 // Otherwise, it must be an instruction.
189 Instruction *I = cast<Instruction>(V);
190 Instruction *Res = nullptr;
191 unsigned Opc = I->getOpcode();
192 switch (Opc) {
193 case Instruction::Add:
194 case Instruction::Sub:
195 case Instruction::Mul:
196 case Instruction::And:
197 case Instruction::Or:
198 case Instruction::Xor:
199 case Instruction::AShr:
200 case Instruction::LShr:
201 case Instruction::Shl:
202 case Instruction::UDiv:
203 case Instruction::URem: {
204 Value *LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
205 Value *RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
206 Res = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
207 break;
208 }
209 case Instruction::Trunc:
210 case Instruction::ZExt:
211 case Instruction::SExt:
212 // If the source type of the cast is the type we're trying for then we can
213 // just return the source. There's no need to insert it because it is not
214 // new.
215 if (I->getOperand(0)->getType() == Ty)
216 return I->getOperand(0);
217
218 // Otherwise, must be the same type of cast, so just reinsert a new one.
219 // This also handles the case of zext(trunc(x)) -> zext(x).
220 Res = CastInst::CreateIntegerCast(I->getOperand(0), Ty,
221 Opc == Instruction::SExt);
222 break;
223 case Instruction::Select: {
224 Value *True = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
225 Value *False = EvaluateInDifferentType(I->getOperand(2), Ty, isSigned);
226 Res = SelectInst::Create(I->getOperand(0), True, False);
227 break;
228 }
229 case Instruction::PHI: {
230 PHINode *OPN = cast<PHINode>(I);
231 PHINode *NPN = PHINode::Create(Ty, OPN->getNumIncomingValues());
232 for (unsigned i = 0, e = OPN->getNumIncomingValues(); i != e; ++i) {
233 Value *V =
234 EvaluateInDifferentType(OPN->getIncomingValue(i), Ty, isSigned);
235 NPN->addIncoming(V, OPN->getIncomingBlock(i));
236 }
237 Res = NPN;
238 break;
239 }
240 default:
241 // TODO: Can handle more cases here.
242 llvm_unreachable("Unreachable!");
243 }
244
245 Res->takeName(I);
246 return InsertNewInstWith(Res, *I);
247 }
248
249 Instruction::CastOps
isEliminableCastPair(const CastInst * CI1,const CastInst * CI2)250 InstCombinerImpl::isEliminableCastPair(const CastInst *CI1,
251 const CastInst *CI2) {
252 Type *SrcTy = CI1->getSrcTy();
253 Type *MidTy = CI1->getDestTy();
254 Type *DstTy = CI2->getDestTy();
255
256 Instruction::CastOps firstOp = CI1->getOpcode();
257 Instruction::CastOps secondOp = CI2->getOpcode();
258 Type *SrcIntPtrTy =
259 SrcTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(SrcTy) : nullptr;
260 Type *MidIntPtrTy =
261 MidTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(MidTy) : nullptr;
262 Type *DstIntPtrTy =
263 DstTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(DstTy) : nullptr;
264 unsigned Res = CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy,
265 DstTy, SrcIntPtrTy, MidIntPtrTy,
266 DstIntPtrTy);
267
268 // We don't want to form an inttoptr or ptrtoint that converts to an integer
269 // type that differs from the pointer size.
270 if ((Res == Instruction::IntToPtr && SrcTy != DstIntPtrTy) ||
271 (Res == Instruction::PtrToInt && DstTy != SrcIntPtrTy))
272 Res = 0;
273
274 return Instruction::CastOps(Res);
275 }
276
277 /// Implement the transforms common to all CastInst visitors.
commonCastTransforms(CastInst & CI)278 Instruction *InstCombinerImpl::commonCastTransforms(CastInst &CI) {
279 Value *Src = CI.getOperand(0);
280
281 // Try to eliminate a cast of a cast.
282 if (auto *CSrc = dyn_cast<CastInst>(Src)) { // A->B->C cast
283 if (Instruction::CastOps NewOpc = isEliminableCastPair(CSrc, &CI)) {
284 // The first cast (CSrc) is eliminable so we need to fix up or replace
285 // the second cast (CI). CSrc will then have a good chance of being dead.
286 auto *Ty = CI.getType();
287 auto *Res = CastInst::Create(NewOpc, CSrc->getOperand(0), Ty);
288 // Point debug users of the dying cast to the new one.
289 if (CSrc->hasOneUse())
290 replaceAllDbgUsesWith(*CSrc, *Res, CI, DT);
291 return Res;
292 }
293 }
294
295 if (auto *Sel = dyn_cast<SelectInst>(Src)) {
296 // We are casting a select. Try to fold the cast into the select if the
297 // select does not have a compare instruction with matching operand types
298 // or the select is likely better done in a narrow type.
299 // Creating a select with operands that are different sizes than its
300 // condition may inhibit other folds and lead to worse codegen.
301 auto *Cmp = dyn_cast<CmpInst>(Sel->getCondition());
302 if (!Cmp || Cmp->getOperand(0)->getType() != Sel->getType() ||
303 (CI.getOpcode() == Instruction::Trunc &&
304 shouldChangeType(CI.getSrcTy(), CI.getType()))) {
305 if (Instruction *NV = FoldOpIntoSelect(CI, Sel)) {
306 replaceAllDbgUsesWith(*Sel, *NV, CI, DT);
307 return NV;
308 }
309 }
310 }
311
312 // If we are casting a PHI, then fold the cast into the PHI.
313 if (auto *PN = dyn_cast<PHINode>(Src)) {
314 // Don't do this if it would create a PHI node with an illegal type from a
315 // legal type.
316 if (!Src->getType()->isIntegerTy() || !CI.getType()->isIntegerTy() ||
317 shouldChangeType(CI.getSrcTy(), CI.getType()))
318 if (Instruction *NV = foldOpIntoPhi(CI, PN))
319 return NV;
320 }
321
322 return nullptr;
323 }
324
325 /// Constants and extensions/truncates from the destination type are always
326 /// free to be evaluated in that type. This is a helper for canEvaluate*.
canAlwaysEvaluateInType(Value * V,Type * Ty)327 static bool canAlwaysEvaluateInType(Value *V, Type *Ty) {
328 if (isa<Constant>(V))
329 return true;
330 Value *X;
331 if ((match(V, m_ZExtOrSExt(m_Value(X))) || match(V, m_Trunc(m_Value(X)))) &&
332 X->getType() == Ty)
333 return true;
334
335 return false;
336 }
337
338 /// Filter out values that we can not evaluate in the destination type for free.
339 /// This is a helper for canEvaluate*.
canNotEvaluateInType(Value * V,Type * Ty)340 static bool canNotEvaluateInType(Value *V, Type *Ty) {
341 assert(!isa<Constant>(V) && "Constant should already be handled.");
342 if (!isa<Instruction>(V))
343 return true;
344 // We don't extend or shrink something that has multiple uses -- doing so
345 // would require duplicating the instruction which isn't profitable.
346 if (!V->hasOneUse())
347 return true;
348
349 return false;
350 }
351
352 /// Return true if we can evaluate the specified expression tree as type Ty
353 /// instead of its larger type, and arrive with the same value.
354 /// This is used by code that tries to eliminate truncates.
355 ///
356 /// Ty will always be a type smaller than V. We should return true if trunc(V)
357 /// can be computed by computing V in the smaller type. If V is an instruction,
358 /// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only
359 /// makes sense if x and y can be efficiently truncated.
360 ///
361 /// This function works on both vectors and scalars.
362 ///
canEvaluateTruncated(Value * V,Type * Ty,InstCombinerImpl & IC,Instruction * CxtI)363 static bool canEvaluateTruncated(Value *V, Type *Ty, InstCombinerImpl &IC,
364 Instruction *CxtI) {
365 if (canAlwaysEvaluateInType(V, Ty))
366 return true;
367 if (canNotEvaluateInType(V, Ty))
368 return false;
369
370 auto *I = cast<Instruction>(V);
371 Type *OrigTy = V->getType();
372 switch (I->getOpcode()) {
373 case Instruction::Add:
374 case Instruction::Sub:
375 case Instruction::Mul:
376 case Instruction::And:
377 case Instruction::Or:
378 case Instruction::Xor:
379 // These operators can all arbitrarily be extended or truncated.
380 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
381 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
382
383 case Instruction::UDiv:
384 case Instruction::URem: {
385 // UDiv and URem can be truncated if all the truncated bits are zero.
386 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
387 uint32_t BitWidth = Ty->getScalarSizeInBits();
388 assert(BitWidth < OrigBitWidth && "Unexpected bitwidths!");
389 APInt Mask = APInt::getBitsSetFrom(OrigBitWidth, BitWidth);
390 if (IC.MaskedValueIsZero(I->getOperand(0), Mask, 0, CxtI) &&
391 IC.MaskedValueIsZero(I->getOperand(1), Mask, 0, CxtI)) {
392 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
393 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
394 }
395 break;
396 }
397 case Instruction::Shl: {
398 // If we are truncating the result of this SHL, and if it's a shift of an
399 // inrange amount, we can always perform a SHL in a smaller type.
400 uint32_t BitWidth = Ty->getScalarSizeInBits();
401 KnownBits AmtKnownBits =
402 llvm::computeKnownBits(I->getOperand(1), IC.getDataLayout());
403 if (AmtKnownBits.getMaxValue().ult(BitWidth))
404 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
405 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
406 break;
407 }
408 case Instruction::LShr: {
409 // If this is a truncate of a logical shr, we can truncate it to a smaller
410 // lshr iff we know that the bits we would otherwise be shifting in are
411 // already zeros.
412 // TODO: It is enough to check that the bits we would be shifting in are
413 // zero - use AmtKnownBits.getMaxValue().
414 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
415 uint32_t BitWidth = Ty->getScalarSizeInBits();
416 KnownBits AmtKnownBits =
417 llvm::computeKnownBits(I->getOperand(1), IC.getDataLayout());
418 APInt ShiftedBits = APInt::getBitsSetFrom(OrigBitWidth, BitWidth);
419 if (AmtKnownBits.getMaxValue().ult(BitWidth) &&
420 IC.MaskedValueIsZero(I->getOperand(0), ShiftedBits, 0, CxtI)) {
421 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
422 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
423 }
424 break;
425 }
426 case Instruction::AShr: {
427 // If this is a truncate of an arithmetic shr, we can truncate it to a
428 // smaller ashr iff we know that all the bits from the sign bit of the
429 // original type and the sign bit of the truncate type are similar.
430 // TODO: It is enough to check that the bits we would be shifting in are
431 // similar to sign bit of the truncate type.
432 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
433 uint32_t BitWidth = Ty->getScalarSizeInBits();
434 KnownBits AmtKnownBits =
435 llvm::computeKnownBits(I->getOperand(1), IC.getDataLayout());
436 unsigned ShiftedBits = OrigBitWidth - BitWidth;
437 if (AmtKnownBits.getMaxValue().ult(BitWidth) &&
438 ShiftedBits < IC.ComputeNumSignBits(I->getOperand(0), 0, CxtI))
439 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
440 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
441 break;
442 }
443 case Instruction::Trunc:
444 // trunc(trunc(x)) -> trunc(x)
445 return true;
446 case Instruction::ZExt:
447 case Instruction::SExt:
448 // trunc(ext(x)) -> ext(x) if the source type is smaller than the new dest
449 // trunc(ext(x)) -> trunc(x) if the source type is larger than the new dest
450 return true;
451 case Instruction::Select: {
452 SelectInst *SI = cast<SelectInst>(I);
453 return canEvaluateTruncated(SI->getTrueValue(), Ty, IC, CxtI) &&
454 canEvaluateTruncated(SI->getFalseValue(), Ty, IC, CxtI);
455 }
456 case Instruction::PHI: {
457 // We can change a phi if we can change all operands. Note that we never
458 // get into trouble with cyclic PHIs here because we only consider
459 // instructions with a single use.
460 PHINode *PN = cast<PHINode>(I);
461 for (Value *IncValue : PN->incoming_values())
462 if (!canEvaluateTruncated(IncValue, Ty, IC, CxtI))
463 return false;
464 return true;
465 }
466 default:
467 // TODO: Can handle more cases here.
468 break;
469 }
470
471 return false;
472 }
473
474 /// Given a vector that is bitcast to an integer, optionally logically
475 /// right-shifted, and truncated, convert it to an extractelement.
476 /// Example (big endian):
477 /// trunc (lshr (bitcast <4 x i32> %X to i128), 32) to i32
478 /// --->
479 /// extractelement <4 x i32> %X, 1
foldVecTruncToExtElt(TruncInst & Trunc,InstCombinerImpl & IC)480 static Instruction *foldVecTruncToExtElt(TruncInst &Trunc,
481 InstCombinerImpl &IC) {
482 Value *TruncOp = Trunc.getOperand(0);
483 Type *DestType = Trunc.getType();
484 if (!TruncOp->hasOneUse() || !isa<IntegerType>(DestType))
485 return nullptr;
486
487 Value *VecInput = nullptr;
488 ConstantInt *ShiftVal = nullptr;
489 if (!match(TruncOp, m_CombineOr(m_BitCast(m_Value(VecInput)),
490 m_LShr(m_BitCast(m_Value(VecInput)),
491 m_ConstantInt(ShiftVal)))) ||
492 !isa<VectorType>(VecInput->getType()))
493 return nullptr;
494
495 VectorType *VecType = cast<VectorType>(VecInput->getType());
496 unsigned VecWidth = VecType->getPrimitiveSizeInBits();
497 unsigned DestWidth = DestType->getPrimitiveSizeInBits();
498 unsigned ShiftAmount = ShiftVal ? ShiftVal->getZExtValue() : 0;
499
500 if ((VecWidth % DestWidth != 0) || (ShiftAmount % DestWidth != 0))
501 return nullptr;
502
503 // If the element type of the vector doesn't match the result type,
504 // bitcast it to a vector type that we can extract from.
505 unsigned NumVecElts = VecWidth / DestWidth;
506 if (VecType->getElementType() != DestType) {
507 VecType = FixedVectorType::get(DestType, NumVecElts);
508 VecInput = IC.Builder.CreateBitCast(VecInput, VecType, "bc");
509 }
510
511 unsigned Elt = ShiftAmount / DestWidth;
512 if (IC.getDataLayout().isBigEndian())
513 Elt = NumVecElts - 1 - Elt;
514
515 return ExtractElementInst::Create(VecInput, IC.Builder.getInt32(Elt));
516 }
517
518 /// Funnel/Rotate left/right may occur in a wider type than necessary because of
519 /// type promotion rules. Try to narrow the inputs and convert to funnel shift.
narrowFunnelShift(TruncInst & Trunc)520 Instruction *InstCombinerImpl::narrowFunnelShift(TruncInst &Trunc) {
521 assert((isa<VectorType>(Trunc.getSrcTy()) ||
522 shouldChangeType(Trunc.getSrcTy(), Trunc.getType())) &&
523 "Don't narrow to an illegal scalar type");
524
525 // Bail out on strange types. It is possible to handle some of these patterns
526 // even with non-power-of-2 sizes, but it is not a likely scenario.
527 Type *DestTy = Trunc.getType();
528 unsigned NarrowWidth = DestTy->getScalarSizeInBits();
529 if (!isPowerOf2_32(NarrowWidth))
530 return nullptr;
531
532 // First, find an or'd pair of opposite shifts:
533 // trunc (or (lshr ShVal0, ShAmt0), (shl ShVal1, ShAmt1))
534 BinaryOperator *Or0, *Or1;
535 if (!match(Trunc.getOperand(0), m_OneUse(m_Or(m_BinOp(Or0), m_BinOp(Or1)))))
536 return nullptr;
537
538 Value *ShVal0, *ShVal1, *ShAmt0, *ShAmt1;
539 if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal0), m_Value(ShAmt0)))) ||
540 !match(Or1, m_OneUse(m_LogicalShift(m_Value(ShVal1), m_Value(ShAmt1)))) ||
541 Or0->getOpcode() == Or1->getOpcode())
542 return nullptr;
543
544 // Canonicalize to or(shl(ShVal0, ShAmt0), lshr(ShVal1, ShAmt1)).
545 if (Or0->getOpcode() == BinaryOperator::LShr) {
546 std::swap(Or0, Or1);
547 std::swap(ShVal0, ShVal1);
548 std::swap(ShAmt0, ShAmt1);
549 }
550 assert(Or0->getOpcode() == BinaryOperator::Shl &&
551 Or1->getOpcode() == BinaryOperator::LShr &&
552 "Illegal or(shift,shift) pair");
553
554 // Match the shift amount operands for a funnel/rotate pattern. This always
555 // matches a subtraction on the R operand.
556 auto matchShiftAmount = [&](Value *L, Value *R, unsigned Width) -> Value * {
557 // The shift amounts may add up to the narrow bit width:
558 // (shl ShVal0, L) | (lshr ShVal1, Width - L)
559 if (match(R, m_OneUse(m_Sub(m_SpecificInt(Width), m_Specific(L)))))
560 return L;
561
562 // The following patterns currently only work for rotation patterns.
563 // TODO: Add more general funnel-shift compatible patterns.
564 if (ShVal0 != ShVal1)
565 return nullptr;
566
567 // The shift amount may be masked with negation:
568 // (shl ShVal0, (X & (Width - 1))) | (lshr ShVal1, ((-X) & (Width - 1)))
569 Value *X;
570 unsigned Mask = Width - 1;
571 if (match(L, m_And(m_Value(X), m_SpecificInt(Mask))) &&
572 match(R, m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask))))
573 return X;
574
575 // Same as above, but the shift amount may be extended after masking:
576 if (match(L, m_ZExt(m_And(m_Value(X), m_SpecificInt(Mask)))) &&
577 match(R, m_ZExt(m_And(m_Neg(m_Specific(X)), m_SpecificInt(Mask)))))
578 return X;
579
580 return nullptr;
581 };
582
583 Value *ShAmt = matchShiftAmount(ShAmt0, ShAmt1, NarrowWidth);
584 bool IsFshl = true; // Sub on LSHR.
585 if (!ShAmt) {
586 ShAmt = matchShiftAmount(ShAmt1, ShAmt0, NarrowWidth);
587 IsFshl = false; // Sub on SHL.
588 }
589 if (!ShAmt)
590 return nullptr;
591
592 // The shifted value must have high zeros in the wide type. Typically, this
593 // will be a zext, but it could also be the result of an 'and' or 'shift'.
594 unsigned WideWidth = Trunc.getSrcTy()->getScalarSizeInBits();
595 APInt HiBitMask = APInt::getHighBitsSet(WideWidth, WideWidth - NarrowWidth);
596 if (!MaskedValueIsZero(ShVal0, HiBitMask, 0, &Trunc) ||
597 !MaskedValueIsZero(ShVal1, HiBitMask, 0, &Trunc))
598 return nullptr;
599
600 // We have an unnecessarily wide rotate!
601 // trunc (or (lshr ShVal0, ShAmt), (shl ShVal1, BitWidth - ShAmt))
602 // Narrow the inputs and convert to funnel shift intrinsic:
603 // llvm.fshl.i8(trunc(ShVal), trunc(ShVal), trunc(ShAmt))
604 Value *NarrowShAmt = Builder.CreateTrunc(ShAmt, DestTy);
605 Value *X, *Y;
606 X = Y = Builder.CreateTrunc(ShVal0, DestTy);
607 if (ShVal0 != ShVal1)
608 Y = Builder.CreateTrunc(ShVal1, DestTy);
609 Intrinsic::ID IID = IsFshl ? Intrinsic::fshl : Intrinsic::fshr;
610 Function *F = Intrinsic::getDeclaration(Trunc.getModule(), IID, DestTy);
611 return IntrinsicInst::Create(F, {X, Y, NarrowShAmt});
612 }
613
614 /// Try to narrow the width of math or bitwise logic instructions by pulling a
615 /// truncate ahead of binary operators.
616 /// TODO: Transforms for truncated shifts should be moved into here.
narrowBinOp(TruncInst & Trunc)617 Instruction *InstCombinerImpl::narrowBinOp(TruncInst &Trunc) {
618 Type *SrcTy = Trunc.getSrcTy();
619 Type *DestTy = Trunc.getType();
620 if (!isa<VectorType>(SrcTy) && !shouldChangeType(SrcTy, DestTy))
621 return nullptr;
622
623 BinaryOperator *BinOp;
624 if (!match(Trunc.getOperand(0), m_OneUse(m_BinOp(BinOp))))
625 return nullptr;
626
627 Value *BinOp0 = BinOp->getOperand(0);
628 Value *BinOp1 = BinOp->getOperand(1);
629 switch (BinOp->getOpcode()) {
630 case Instruction::And:
631 case Instruction::Or:
632 case Instruction::Xor:
633 case Instruction::Add:
634 case Instruction::Sub:
635 case Instruction::Mul: {
636 Constant *C;
637 if (match(BinOp0, m_Constant(C))) {
638 // trunc (binop C, X) --> binop (trunc C', X)
639 Constant *NarrowC = ConstantExpr::getTrunc(C, DestTy);
640 Value *TruncX = Builder.CreateTrunc(BinOp1, DestTy);
641 return BinaryOperator::Create(BinOp->getOpcode(), NarrowC, TruncX);
642 }
643 if (match(BinOp1, m_Constant(C))) {
644 // trunc (binop X, C) --> binop (trunc X, C')
645 Constant *NarrowC = ConstantExpr::getTrunc(C, DestTy);
646 Value *TruncX = Builder.CreateTrunc(BinOp0, DestTy);
647 return BinaryOperator::Create(BinOp->getOpcode(), TruncX, NarrowC);
648 }
649 Value *X;
650 if (match(BinOp0, m_ZExtOrSExt(m_Value(X))) && X->getType() == DestTy) {
651 // trunc (binop (ext X), Y) --> binop X, (trunc Y)
652 Value *NarrowOp1 = Builder.CreateTrunc(BinOp1, DestTy);
653 return BinaryOperator::Create(BinOp->getOpcode(), X, NarrowOp1);
654 }
655 if (match(BinOp1, m_ZExtOrSExt(m_Value(X))) && X->getType() == DestTy) {
656 // trunc (binop Y, (ext X)) --> binop (trunc Y), X
657 Value *NarrowOp0 = Builder.CreateTrunc(BinOp0, DestTy);
658 return BinaryOperator::Create(BinOp->getOpcode(), NarrowOp0, X);
659 }
660 break;
661 }
662
663 default: break;
664 }
665
666 if (Instruction *NarrowOr = narrowFunnelShift(Trunc))
667 return NarrowOr;
668
669 return nullptr;
670 }
671
672 /// Try to narrow the width of a splat shuffle. This could be generalized to any
673 /// shuffle with a constant operand, but we limit the transform to avoid
674 /// creating a shuffle type that targets may not be able to lower effectively.
shrinkSplatShuffle(TruncInst & Trunc,InstCombiner::BuilderTy & Builder)675 static Instruction *shrinkSplatShuffle(TruncInst &Trunc,
676 InstCombiner::BuilderTy &Builder) {
677 auto *Shuf = dyn_cast<ShuffleVectorInst>(Trunc.getOperand(0));
678 if (Shuf && Shuf->hasOneUse() && isa<UndefValue>(Shuf->getOperand(1)) &&
679 is_splat(Shuf->getShuffleMask()) &&
680 Shuf->getType() == Shuf->getOperand(0)->getType()) {
681 // trunc (shuf X, Undef, SplatMask) --> shuf (trunc X), Undef, SplatMask
682 Constant *NarrowUndef = UndefValue::get(Trunc.getType());
683 Value *NarrowOp = Builder.CreateTrunc(Shuf->getOperand(0), Trunc.getType());
684 return new ShuffleVectorInst(NarrowOp, NarrowUndef, Shuf->getShuffleMask());
685 }
686
687 return nullptr;
688 }
689
690 /// Try to narrow the width of an insert element. This could be generalized for
691 /// any vector constant, but we limit the transform to insertion into undef to
692 /// avoid potential backend problems from unsupported insertion widths. This
693 /// could also be extended to handle the case of inserting a scalar constant
694 /// into a vector variable.
shrinkInsertElt(CastInst & Trunc,InstCombiner::BuilderTy & Builder)695 static Instruction *shrinkInsertElt(CastInst &Trunc,
696 InstCombiner::BuilderTy &Builder) {
697 Instruction::CastOps Opcode = Trunc.getOpcode();
698 assert((Opcode == Instruction::Trunc || Opcode == Instruction::FPTrunc) &&
699 "Unexpected instruction for shrinking");
700
701 auto *InsElt = dyn_cast<InsertElementInst>(Trunc.getOperand(0));
702 if (!InsElt || !InsElt->hasOneUse())
703 return nullptr;
704
705 Type *DestTy = Trunc.getType();
706 Type *DestScalarTy = DestTy->getScalarType();
707 Value *VecOp = InsElt->getOperand(0);
708 Value *ScalarOp = InsElt->getOperand(1);
709 Value *Index = InsElt->getOperand(2);
710
711 if (isa<UndefValue>(VecOp)) {
712 // trunc (inselt undef, X, Index) --> inselt undef, (trunc X), Index
713 // fptrunc (inselt undef, X, Index) --> inselt undef, (fptrunc X), Index
714 UndefValue *NarrowUndef = UndefValue::get(DestTy);
715 Value *NarrowOp = Builder.CreateCast(Opcode, ScalarOp, DestScalarTy);
716 return InsertElementInst::Create(NarrowUndef, NarrowOp, Index);
717 }
718
719 return nullptr;
720 }
721
visitTrunc(TruncInst & Trunc)722 Instruction *InstCombinerImpl::visitTrunc(TruncInst &Trunc) {
723 if (Instruction *Result = commonCastTransforms(Trunc))
724 return Result;
725
726 Value *Src = Trunc.getOperand(0);
727 Type *DestTy = Trunc.getType(), *SrcTy = Src->getType();
728 unsigned DestWidth = DestTy->getScalarSizeInBits();
729 unsigned SrcWidth = SrcTy->getScalarSizeInBits();
730
731 // Attempt to truncate the entire input expression tree to the destination
732 // type. Only do this if the dest type is a simple type, don't convert the
733 // expression tree to something weird like i93 unless the source is also
734 // strange.
735 if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) &&
736 canEvaluateTruncated(Src, DestTy, *this, &Trunc)) {
737
738 // If this cast is a truncate, evaluting in a different type always
739 // eliminates the cast, so it is always a win.
740 LLVM_DEBUG(
741 dbgs() << "ICE: EvaluateInDifferentType converting expression type"
742 " to avoid cast: "
743 << Trunc << '\n');
744 Value *Res = EvaluateInDifferentType(Src, DestTy, false);
745 assert(Res->getType() == DestTy);
746 return replaceInstUsesWith(Trunc, Res);
747 }
748
749 // For integer types, check if we can shorten the entire input expression to
750 // DestWidth * 2, which won't allow removing the truncate, but reducing the
751 // width may enable further optimizations, e.g. allowing for larger
752 // vectorization factors.
753 if (auto *DestITy = dyn_cast<IntegerType>(DestTy)) {
754 if (DestWidth * 2 < SrcWidth) {
755 auto *NewDestTy = DestITy->getExtendedType();
756 if (shouldChangeType(SrcTy, NewDestTy) &&
757 canEvaluateTruncated(Src, NewDestTy, *this, &Trunc)) {
758 LLVM_DEBUG(
759 dbgs() << "ICE: EvaluateInDifferentType converting expression type"
760 " to reduce the width of operand of"
761 << Trunc << '\n');
762 Value *Res = EvaluateInDifferentType(Src, NewDestTy, false);
763 return new TruncInst(Res, DestTy);
764 }
765 }
766 }
767
768 // Test if the trunc is the user of a select which is part of a
769 // minimum or maximum operation. If so, don't do any more simplification.
770 // Even simplifying demanded bits can break the canonical form of a
771 // min/max.
772 Value *LHS, *RHS;
773 if (SelectInst *Sel = dyn_cast<SelectInst>(Src))
774 if (matchSelectPattern(Sel, LHS, RHS).Flavor != SPF_UNKNOWN)
775 return nullptr;
776
777 // See if we can simplify any instructions used by the input whose sole
778 // purpose is to compute bits we don't care about.
779 if (SimplifyDemandedInstructionBits(Trunc))
780 return &Trunc;
781
782 if (DestWidth == 1) {
783 Value *Zero = Constant::getNullValue(SrcTy);
784 if (DestTy->isIntegerTy()) {
785 // Canonicalize trunc x to i1 -> icmp ne (and x, 1), 0 (scalar only).
786 // TODO: We canonicalize to more instructions here because we are probably
787 // lacking equivalent analysis for trunc relative to icmp. There may also
788 // be codegen concerns. If those trunc limitations were removed, we could
789 // remove this transform.
790 Value *And = Builder.CreateAnd(Src, ConstantInt::get(SrcTy, 1));
791 return new ICmpInst(ICmpInst::ICMP_NE, And, Zero);
792 }
793
794 // For vectors, we do not canonicalize all truncs to icmp, so optimize
795 // patterns that would be covered within visitICmpInst.
796 Value *X;
797 Constant *C;
798 if (match(Src, m_OneUse(m_LShr(m_Value(X), m_Constant(C))))) {
799 // trunc (lshr X, C) to i1 --> icmp ne (and X, C'), 0
800 Constant *One = ConstantInt::get(SrcTy, APInt(SrcWidth, 1));
801 Constant *MaskC = ConstantExpr::getShl(One, C);
802 Value *And = Builder.CreateAnd(X, MaskC);
803 return new ICmpInst(ICmpInst::ICMP_NE, And, Zero);
804 }
805 if (match(Src, m_OneUse(m_c_Or(m_LShr(m_Value(X), m_Constant(C)),
806 m_Deferred(X))))) {
807 // trunc (or (lshr X, C), X) to i1 --> icmp ne (and X, C'), 0
808 Constant *One = ConstantInt::get(SrcTy, APInt(SrcWidth, 1));
809 Constant *MaskC = ConstantExpr::getShl(One, C);
810 MaskC = ConstantExpr::getOr(MaskC, One);
811 Value *And = Builder.CreateAnd(X, MaskC);
812 return new ICmpInst(ICmpInst::ICMP_NE, And, Zero);
813 }
814 }
815
816 Value *A;
817 Constant *C;
818 if (match(Src, m_LShr(m_SExt(m_Value(A)), m_Constant(C)))) {
819 unsigned AWidth = A->getType()->getScalarSizeInBits();
820 unsigned MaxShiftAmt = SrcWidth - std::max(DestWidth, AWidth);
821 auto *OldSh = cast<Instruction>(Src);
822 bool IsExact = OldSh->isExact();
823
824 // If the shift is small enough, all zero bits created by the shift are
825 // removed by the trunc.
826 if (match(C, m_SpecificInt_ICMP(ICmpInst::ICMP_ULE,
827 APInt(SrcWidth, MaxShiftAmt)))) {
828 // trunc (lshr (sext A), C) --> ashr A, C
829 if (A->getType() == DestTy) {
830 Constant *MaxAmt = ConstantInt::get(SrcTy, DestWidth - 1, false);
831 Constant *ShAmt = ConstantExpr::getUMin(C, MaxAmt);
832 ShAmt = ConstantExpr::getTrunc(ShAmt, A->getType());
833 ShAmt = Constant::mergeUndefsWith(ShAmt, C);
834 return IsExact ? BinaryOperator::CreateExactAShr(A, ShAmt)
835 : BinaryOperator::CreateAShr(A, ShAmt);
836 }
837 // The types are mismatched, so create a cast after shifting:
838 // trunc (lshr (sext A), C) --> sext/trunc (ashr A, C)
839 if (Src->hasOneUse()) {
840 Constant *MaxAmt = ConstantInt::get(SrcTy, AWidth - 1, false);
841 Constant *ShAmt = ConstantExpr::getUMin(C, MaxAmt);
842 ShAmt = ConstantExpr::getTrunc(ShAmt, A->getType());
843 Value *Shift = Builder.CreateAShr(A, ShAmt, "", IsExact);
844 return CastInst::CreateIntegerCast(Shift, DestTy, true);
845 }
846 }
847 // TODO: Mask high bits with 'and'.
848 }
849
850 // trunc (*shr (trunc A), C) --> trunc(*shr A, C)
851 if (match(Src, m_OneUse(m_Shr(m_Trunc(m_Value(A)), m_Constant(C))))) {
852 unsigned MaxShiftAmt = SrcWidth - DestWidth;
853
854 // If the shift is small enough, all zero/sign bits created by the shift are
855 // removed by the trunc.
856 if (match(C, m_SpecificInt_ICMP(ICmpInst::ICMP_ULE,
857 APInt(SrcWidth, MaxShiftAmt)))) {
858 auto *OldShift = cast<Instruction>(Src);
859 bool IsExact = OldShift->isExact();
860 auto *ShAmt = ConstantExpr::getIntegerCast(C, A->getType(), true);
861 ShAmt = Constant::mergeUndefsWith(ShAmt, C);
862 Value *Shift =
863 OldShift->getOpcode() == Instruction::AShr
864 ? Builder.CreateAShr(A, ShAmt, OldShift->getName(), IsExact)
865 : Builder.CreateLShr(A, ShAmt, OldShift->getName(), IsExact);
866 return CastInst::CreateTruncOrBitCast(Shift, DestTy);
867 }
868 }
869
870 if (Instruction *I = narrowBinOp(Trunc))
871 return I;
872
873 if (Instruction *I = shrinkSplatShuffle(Trunc, Builder))
874 return I;
875
876 if (Instruction *I = shrinkInsertElt(Trunc, Builder))
877 return I;
878
879 if (Src->hasOneUse() &&
880 (isa<VectorType>(SrcTy) || shouldChangeType(SrcTy, DestTy))) {
881 // Transform "trunc (shl X, cst)" -> "shl (trunc X), cst" so long as the
882 // dest type is native and cst < dest size.
883 if (match(Src, m_Shl(m_Value(A), m_Constant(C))) &&
884 !match(A, m_Shr(m_Value(), m_Constant()))) {
885 // Skip shifts of shift by constants. It undoes a combine in
886 // FoldShiftByConstant and is the extend in reg pattern.
887 APInt Threshold = APInt(C->getType()->getScalarSizeInBits(), DestWidth);
888 if (match(C, m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, Threshold))) {
889 Value *NewTrunc = Builder.CreateTrunc(A, DestTy, A->getName() + ".tr");
890 return BinaryOperator::Create(Instruction::Shl, NewTrunc,
891 ConstantExpr::getTrunc(C, DestTy));
892 }
893 }
894 }
895
896 if (Instruction *I = foldVecTruncToExtElt(Trunc, *this))
897 return I;
898
899 // Whenever an element is extracted from a vector, and then truncated,
900 // canonicalize by converting it to a bitcast followed by an
901 // extractelement.
902 //
903 // Example (little endian):
904 // trunc (extractelement <4 x i64> %X, 0) to i32
905 // --->
906 // extractelement <8 x i32> (bitcast <4 x i64> %X to <8 x i32>), i32 0
907 Value *VecOp;
908 ConstantInt *Cst;
909 if (match(Src, m_OneUse(m_ExtractElt(m_Value(VecOp), m_ConstantInt(Cst))))) {
910 auto *VecOpTy = cast<VectorType>(VecOp->getType());
911 auto VecElts = VecOpTy->getElementCount();
912
913 // A badly fit destination size would result in an invalid cast.
914 if (SrcWidth % DestWidth == 0) {
915 uint64_t TruncRatio = SrcWidth / DestWidth;
916 uint64_t BitCastNumElts = VecElts.getKnownMinValue() * TruncRatio;
917 uint64_t VecOpIdx = Cst->getZExtValue();
918 uint64_t NewIdx = DL.isBigEndian() ? (VecOpIdx + 1) * TruncRatio - 1
919 : VecOpIdx * TruncRatio;
920 assert(BitCastNumElts <= std::numeric_limits<uint32_t>::max() &&
921 "overflow 32-bits");
922
923 auto *BitCastTo =
924 VectorType::get(DestTy, BitCastNumElts, VecElts.isScalable());
925 Value *BitCast = Builder.CreateBitCast(VecOp, BitCastTo);
926 return ExtractElementInst::Create(BitCast, Builder.getInt32(NewIdx));
927 }
928 }
929
930 return nullptr;
931 }
932
transformZExtICmp(ICmpInst * Cmp,ZExtInst & Zext,bool DoTransform)933 Instruction *InstCombinerImpl::transformZExtICmp(ICmpInst *Cmp, ZExtInst &Zext,
934 bool DoTransform) {
935 // If we are just checking for a icmp eq of a single bit and zext'ing it
936 // to an integer, then shift the bit to the appropriate place and then
937 // cast to integer to avoid the comparison.
938 const APInt *Op1CV;
939 if (match(Cmp->getOperand(1), m_APInt(Op1CV))) {
940
941 // zext (x <s 0) to i32 --> x>>u31 true if signbit set.
942 // zext (x >s -1) to i32 --> (x>>u31)^1 true if signbit clear.
943 if ((Cmp->getPredicate() == ICmpInst::ICMP_SLT && Op1CV->isNullValue()) ||
944 (Cmp->getPredicate() == ICmpInst::ICMP_SGT && Op1CV->isAllOnesValue())) {
945 if (!DoTransform) return Cmp;
946
947 Value *In = Cmp->getOperand(0);
948 Value *Sh = ConstantInt::get(In->getType(),
949 In->getType()->getScalarSizeInBits() - 1);
950 In = Builder.CreateLShr(In, Sh, In->getName() + ".lobit");
951 if (In->getType() != Zext.getType())
952 In = Builder.CreateIntCast(In, Zext.getType(), false /*ZExt*/);
953
954 if (Cmp->getPredicate() == ICmpInst::ICMP_SGT) {
955 Constant *One = ConstantInt::get(In->getType(), 1);
956 In = Builder.CreateXor(In, One, In->getName() + ".not");
957 }
958
959 return replaceInstUsesWith(Zext, In);
960 }
961
962 // zext (X == 0) to i32 --> X^1 iff X has only the low bit set.
963 // zext (X == 0) to i32 --> (X>>1)^1 iff X has only the 2nd bit set.
964 // zext (X == 1) to i32 --> X iff X has only the low bit set.
965 // zext (X == 2) to i32 --> X>>1 iff X has only the 2nd bit set.
966 // zext (X != 0) to i32 --> X iff X has only the low bit set.
967 // zext (X != 0) to i32 --> X>>1 iff X has only the 2nd bit set.
968 // zext (X != 1) to i32 --> X^1 iff X has only the low bit set.
969 // zext (X != 2) to i32 --> (X>>1)^1 iff X has only the 2nd bit set.
970 if ((Op1CV->isNullValue() || Op1CV->isPowerOf2()) &&
971 // This only works for EQ and NE
972 Cmp->isEquality()) {
973 // If Op1C some other power of two, convert:
974 KnownBits Known = computeKnownBits(Cmp->getOperand(0), 0, &Zext);
975
976 APInt KnownZeroMask(~Known.Zero);
977 if (KnownZeroMask.isPowerOf2()) { // Exactly 1 possible 1?
978 if (!DoTransform) return Cmp;
979
980 bool isNE = Cmp->getPredicate() == ICmpInst::ICMP_NE;
981 if (!Op1CV->isNullValue() && (*Op1CV != KnownZeroMask)) {
982 // (X&4) == 2 --> false
983 // (X&4) != 2 --> true
984 Constant *Res = ConstantInt::get(Zext.getType(), isNE);
985 return replaceInstUsesWith(Zext, Res);
986 }
987
988 uint32_t ShAmt = KnownZeroMask.logBase2();
989 Value *In = Cmp->getOperand(0);
990 if (ShAmt) {
991 // Perform a logical shr by shiftamt.
992 // Insert the shift to put the result in the low bit.
993 In = Builder.CreateLShr(In, ConstantInt::get(In->getType(), ShAmt),
994 In->getName() + ".lobit");
995 }
996
997 if (!Op1CV->isNullValue() == isNE) { // Toggle the low bit.
998 Constant *One = ConstantInt::get(In->getType(), 1);
999 In = Builder.CreateXor(In, One);
1000 }
1001
1002 if (Zext.getType() == In->getType())
1003 return replaceInstUsesWith(Zext, In);
1004
1005 Value *IntCast = Builder.CreateIntCast(In, Zext.getType(), false);
1006 return replaceInstUsesWith(Zext, IntCast);
1007 }
1008 }
1009 }
1010
1011 // icmp ne A, B is equal to xor A, B when A and B only really have one bit.
1012 // It is also profitable to transform icmp eq into not(xor(A, B)) because that
1013 // may lead to additional simplifications.
1014 if (Cmp->isEquality() && Zext.getType() == Cmp->getOperand(0)->getType()) {
1015 if (IntegerType *ITy = dyn_cast<IntegerType>(Zext.getType())) {
1016 Value *LHS = Cmp->getOperand(0);
1017 Value *RHS = Cmp->getOperand(1);
1018
1019 KnownBits KnownLHS = computeKnownBits(LHS, 0, &Zext);
1020 KnownBits KnownRHS = computeKnownBits(RHS, 0, &Zext);
1021
1022 if (KnownLHS.Zero == KnownRHS.Zero && KnownLHS.One == KnownRHS.One) {
1023 APInt KnownBits = KnownLHS.Zero | KnownLHS.One;
1024 APInt UnknownBit = ~KnownBits;
1025 if (UnknownBit.countPopulation() == 1) {
1026 if (!DoTransform) return Cmp;
1027
1028 Value *Result = Builder.CreateXor(LHS, RHS);
1029
1030 // Mask off any bits that are set and won't be shifted away.
1031 if (KnownLHS.One.uge(UnknownBit))
1032 Result = Builder.CreateAnd(Result,
1033 ConstantInt::get(ITy, UnknownBit));
1034
1035 // Shift the bit we're testing down to the lsb.
1036 Result = Builder.CreateLShr(
1037 Result, ConstantInt::get(ITy, UnknownBit.countTrailingZeros()));
1038
1039 if (Cmp->getPredicate() == ICmpInst::ICMP_EQ)
1040 Result = Builder.CreateXor(Result, ConstantInt::get(ITy, 1));
1041 Result->takeName(Cmp);
1042 return replaceInstUsesWith(Zext, Result);
1043 }
1044 }
1045 }
1046 }
1047
1048 return nullptr;
1049 }
1050
1051 /// Determine if the specified value can be computed in the specified wider type
1052 /// and produce the same low bits. If not, return false.
1053 ///
1054 /// If this function returns true, it can also return a non-zero number of bits
1055 /// (in BitsToClear) which indicates that the value it computes is correct for
1056 /// the zero extend, but that the additional BitsToClear bits need to be zero'd
1057 /// out. For example, to promote something like:
1058 ///
1059 /// %B = trunc i64 %A to i32
1060 /// %C = lshr i32 %B, 8
1061 /// %E = zext i32 %C to i64
1062 ///
1063 /// CanEvaluateZExtd for the 'lshr' will return true, and BitsToClear will be
1064 /// set to 8 to indicate that the promoted value needs to have bits 24-31
1065 /// cleared in addition to bits 32-63. Since an 'and' will be generated to
1066 /// clear the top bits anyway, doing this has no extra cost.
1067 ///
1068 /// This function works on both vectors and scalars.
canEvaluateZExtd(Value * V,Type * Ty,unsigned & BitsToClear,InstCombinerImpl & IC,Instruction * CxtI)1069 static bool canEvaluateZExtd(Value *V, Type *Ty, unsigned &BitsToClear,
1070 InstCombinerImpl &IC, Instruction *CxtI) {
1071 BitsToClear = 0;
1072 if (canAlwaysEvaluateInType(V, Ty))
1073 return true;
1074 if (canNotEvaluateInType(V, Ty))
1075 return false;
1076
1077 auto *I = cast<Instruction>(V);
1078 unsigned Tmp;
1079 switch (I->getOpcode()) {
1080 case Instruction::ZExt: // zext(zext(x)) -> zext(x).
1081 case Instruction::SExt: // zext(sext(x)) -> sext(x).
1082 case Instruction::Trunc: // zext(trunc(x)) -> trunc(x) or zext(x)
1083 return true;
1084 case Instruction::And:
1085 case Instruction::Or:
1086 case Instruction::Xor:
1087 case Instruction::Add:
1088 case Instruction::Sub:
1089 case Instruction::Mul:
1090 if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI) ||
1091 !canEvaluateZExtd(I->getOperand(1), Ty, Tmp, IC, CxtI))
1092 return false;
1093 // These can all be promoted if neither operand has 'bits to clear'.
1094 if (BitsToClear == 0 && Tmp == 0)
1095 return true;
1096
1097 // If the operation is an AND/OR/XOR and the bits to clear are zero in the
1098 // other side, BitsToClear is ok.
1099 if (Tmp == 0 && I->isBitwiseLogicOp()) {
1100 // We use MaskedValueIsZero here for generality, but the case we care
1101 // about the most is constant RHS.
1102 unsigned VSize = V->getType()->getScalarSizeInBits();
1103 if (IC.MaskedValueIsZero(I->getOperand(1),
1104 APInt::getHighBitsSet(VSize, BitsToClear),
1105 0, CxtI)) {
1106 // If this is an And instruction and all of the BitsToClear are
1107 // known to be zero we can reset BitsToClear.
1108 if (I->getOpcode() == Instruction::And)
1109 BitsToClear = 0;
1110 return true;
1111 }
1112 }
1113
1114 // Otherwise, we don't know how to analyze this BitsToClear case yet.
1115 return false;
1116
1117 case Instruction::Shl: {
1118 // We can promote shl(x, cst) if we can promote x. Since shl overwrites the
1119 // upper bits we can reduce BitsToClear by the shift amount.
1120 const APInt *Amt;
1121 if (match(I->getOperand(1), m_APInt(Amt))) {
1122 if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI))
1123 return false;
1124 uint64_t ShiftAmt = Amt->getZExtValue();
1125 BitsToClear = ShiftAmt < BitsToClear ? BitsToClear - ShiftAmt : 0;
1126 return true;
1127 }
1128 return false;
1129 }
1130 case Instruction::LShr: {
1131 // We can promote lshr(x, cst) if we can promote x. This requires the
1132 // ultimate 'and' to clear out the high zero bits we're clearing out though.
1133 const APInt *Amt;
1134 if (match(I->getOperand(1), m_APInt(Amt))) {
1135 if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI))
1136 return false;
1137 BitsToClear += Amt->getZExtValue();
1138 if (BitsToClear > V->getType()->getScalarSizeInBits())
1139 BitsToClear = V->getType()->getScalarSizeInBits();
1140 return true;
1141 }
1142 // Cannot promote variable LSHR.
1143 return false;
1144 }
1145 case Instruction::Select:
1146 if (!canEvaluateZExtd(I->getOperand(1), Ty, Tmp, IC, CxtI) ||
1147 !canEvaluateZExtd(I->getOperand(2), Ty, BitsToClear, IC, CxtI) ||
1148 // TODO: If important, we could handle the case when the BitsToClear are
1149 // known zero in the disagreeing side.
1150 Tmp != BitsToClear)
1151 return false;
1152 return true;
1153
1154 case Instruction::PHI: {
1155 // We can change a phi if we can change all operands. Note that we never
1156 // get into trouble with cyclic PHIs here because we only consider
1157 // instructions with a single use.
1158 PHINode *PN = cast<PHINode>(I);
1159 if (!canEvaluateZExtd(PN->getIncomingValue(0), Ty, BitsToClear, IC, CxtI))
1160 return false;
1161 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
1162 if (!canEvaluateZExtd(PN->getIncomingValue(i), Ty, Tmp, IC, CxtI) ||
1163 // TODO: If important, we could handle the case when the BitsToClear
1164 // are known zero in the disagreeing input.
1165 Tmp != BitsToClear)
1166 return false;
1167 return true;
1168 }
1169 default:
1170 // TODO: Can handle more cases here.
1171 return false;
1172 }
1173 }
1174
visitZExt(ZExtInst & CI)1175 Instruction *InstCombinerImpl::visitZExt(ZExtInst &CI) {
1176 // If this zero extend is only used by a truncate, let the truncate be
1177 // eliminated before we try to optimize this zext.
1178 if (CI.hasOneUse() && isa<TruncInst>(CI.user_back()))
1179 return nullptr;
1180
1181 // If one of the common conversion will work, do it.
1182 if (Instruction *Result = commonCastTransforms(CI))
1183 return Result;
1184
1185 Value *Src = CI.getOperand(0);
1186 Type *SrcTy = Src->getType(), *DestTy = CI.getType();
1187
1188 // Try to extend the entire expression tree to the wide destination type.
1189 unsigned BitsToClear;
1190 if (shouldChangeType(SrcTy, DestTy) &&
1191 canEvaluateZExtd(Src, DestTy, BitsToClear, *this, &CI)) {
1192 assert(BitsToClear <= SrcTy->getScalarSizeInBits() &&
1193 "Can't clear more bits than in SrcTy");
1194
1195 // Okay, we can transform this! Insert the new expression now.
1196 LLVM_DEBUG(
1197 dbgs() << "ICE: EvaluateInDifferentType converting expression type"
1198 " to avoid zero extend: "
1199 << CI << '\n');
1200 Value *Res = EvaluateInDifferentType(Src, DestTy, false);
1201 assert(Res->getType() == DestTy);
1202
1203 // Preserve debug values referring to Src if the zext is its last use.
1204 if (auto *SrcOp = dyn_cast<Instruction>(Src))
1205 if (SrcOp->hasOneUse())
1206 replaceAllDbgUsesWith(*SrcOp, *Res, CI, DT);
1207
1208 uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits()-BitsToClear;
1209 uint32_t DestBitSize = DestTy->getScalarSizeInBits();
1210
1211 // If the high bits are already filled with zeros, just replace this
1212 // cast with the result.
1213 if (MaskedValueIsZero(Res,
1214 APInt::getHighBitsSet(DestBitSize,
1215 DestBitSize-SrcBitsKept),
1216 0, &CI))
1217 return replaceInstUsesWith(CI, Res);
1218
1219 // We need to emit an AND to clear the high bits.
1220 Constant *C = ConstantInt::get(Res->getType(),
1221 APInt::getLowBitsSet(DestBitSize, SrcBitsKept));
1222 return BinaryOperator::CreateAnd(Res, C);
1223 }
1224
1225 // If this is a TRUNC followed by a ZEXT then we are dealing with integral
1226 // types and if the sizes are just right we can convert this into a logical
1227 // 'and' which will be much cheaper than the pair of casts.
1228 if (TruncInst *CSrc = dyn_cast<TruncInst>(Src)) { // A->B->C cast
1229 // TODO: Subsume this into EvaluateInDifferentType.
1230
1231 // Get the sizes of the types involved. We know that the intermediate type
1232 // will be smaller than A or C, but don't know the relation between A and C.
1233 Value *A = CSrc->getOperand(0);
1234 unsigned SrcSize = A->getType()->getScalarSizeInBits();
1235 unsigned MidSize = CSrc->getType()->getScalarSizeInBits();
1236 unsigned DstSize = CI.getType()->getScalarSizeInBits();
1237 // If we're actually extending zero bits, then if
1238 // SrcSize < DstSize: zext(a & mask)
1239 // SrcSize == DstSize: a & mask
1240 // SrcSize > DstSize: trunc(a) & mask
1241 if (SrcSize < DstSize) {
1242 APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize));
1243 Constant *AndConst = ConstantInt::get(A->getType(), AndValue);
1244 Value *And = Builder.CreateAnd(A, AndConst, CSrc->getName() + ".mask");
1245 return new ZExtInst(And, CI.getType());
1246 }
1247
1248 if (SrcSize == DstSize) {
1249 APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize));
1250 return BinaryOperator::CreateAnd(A, ConstantInt::get(A->getType(),
1251 AndValue));
1252 }
1253 if (SrcSize > DstSize) {
1254 Value *Trunc = Builder.CreateTrunc(A, CI.getType());
1255 APInt AndValue(APInt::getLowBitsSet(DstSize, MidSize));
1256 return BinaryOperator::CreateAnd(Trunc,
1257 ConstantInt::get(Trunc->getType(),
1258 AndValue));
1259 }
1260 }
1261
1262 if (ICmpInst *Cmp = dyn_cast<ICmpInst>(Src))
1263 return transformZExtICmp(Cmp, CI);
1264
1265 BinaryOperator *SrcI = dyn_cast<BinaryOperator>(Src);
1266 if (SrcI && SrcI->getOpcode() == Instruction::Or) {
1267 // zext (or icmp, icmp) -> or (zext icmp), (zext icmp) if at least one
1268 // of the (zext icmp) can be eliminated. If so, immediately perform the
1269 // according elimination.
1270 ICmpInst *LHS = dyn_cast<ICmpInst>(SrcI->getOperand(0));
1271 ICmpInst *RHS = dyn_cast<ICmpInst>(SrcI->getOperand(1));
1272 if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() &&
1273 LHS->getOperand(0)->getType() == RHS->getOperand(0)->getType() &&
1274 (transformZExtICmp(LHS, CI, false) ||
1275 transformZExtICmp(RHS, CI, false))) {
1276 // zext (or icmp, icmp) -> or (zext icmp), (zext icmp)
1277 Value *LCast = Builder.CreateZExt(LHS, CI.getType(), LHS->getName());
1278 Value *RCast = Builder.CreateZExt(RHS, CI.getType(), RHS->getName());
1279 Value *Or = Builder.CreateOr(LCast, RCast, CI.getName());
1280 if (auto *OrInst = dyn_cast<Instruction>(Or))
1281 Builder.SetInsertPoint(OrInst);
1282
1283 // Perform the elimination.
1284 if (auto *LZExt = dyn_cast<ZExtInst>(LCast))
1285 transformZExtICmp(LHS, *LZExt);
1286 if (auto *RZExt = dyn_cast<ZExtInst>(RCast))
1287 transformZExtICmp(RHS, *RZExt);
1288
1289 return replaceInstUsesWith(CI, Or);
1290 }
1291 }
1292
1293 // zext(trunc(X) & C) -> (X & zext(C)).
1294 Constant *C;
1295 Value *X;
1296 if (SrcI &&
1297 match(SrcI, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Constant(C)))) &&
1298 X->getType() == CI.getType())
1299 return BinaryOperator::CreateAnd(X, ConstantExpr::getZExt(C, CI.getType()));
1300
1301 // zext((trunc(X) & C) ^ C) -> ((X & zext(C)) ^ zext(C)).
1302 Value *And;
1303 if (SrcI && match(SrcI, m_OneUse(m_Xor(m_Value(And), m_Constant(C)))) &&
1304 match(And, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Specific(C)))) &&
1305 X->getType() == CI.getType()) {
1306 Constant *ZC = ConstantExpr::getZExt(C, CI.getType());
1307 return BinaryOperator::CreateXor(Builder.CreateAnd(X, ZC), ZC);
1308 }
1309
1310 return nullptr;
1311 }
1312
1313 /// Transform (sext icmp) to bitwise / integer operations to eliminate the icmp.
transformSExtICmp(ICmpInst * ICI,Instruction & CI)1314 Instruction *InstCombinerImpl::transformSExtICmp(ICmpInst *ICI,
1315 Instruction &CI) {
1316 Value *Op0 = ICI->getOperand(0), *Op1 = ICI->getOperand(1);
1317 ICmpInst::Predicate Pred = ICI->getPredicate();
1318
1319 // Don't bother if Op1 isn't of vector or integer type.
1320 if (!Op1->getType()->isIntOrIntVectorTy())
1321 return nullptr;
1322
1323 if ((Pred == ICmpInst::ICMP_SLT && match(Op1, m_ZeroInt())) ||
1324 (Pred == ICmpInst::ICMP_SGT && match(Op1, m_AllOnes()))) {
1325 // (x <s 0) ? -1 : 0 -> ashr x, 31 -> all ones if negative
1326 // (x >s -1) ? -1 : 0 -> not (ashr x, 31) -> all ones if positive
1327 Value *Sh = ConstantInt::get(Op0->getType(),
1328 Op0->getType()->getScalarSizeInBits() - 1);
1329 Value *In = Builder.CreateAShr(Op0, Sh, Op0->getName() + ".lobit");
1330 if (In->getType() != CI.getType())
1331 In = Builder.CreateIntCast(In, CI.getType(), true /*SExt*/);
1332
1333 if (Pred == ICmpInst::ICMP_SGT)
1334 In = Builder.CreateNot(In, In->getName() + ".not");
1335 return replaceInstUsesWith(CI, In);
1336 }
1337
1338 if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
1339 // If we know that only one bit of the LHS of the icmp can be set and we
1340 // have an equality comparison with zero or a power of 2, we can transform
1341 // the icmp and sext into bitwise/integer operations.
1342 if (ICI->hasOneUse() &&
1343 ICI->isEquality() && (Op1C->isZero() || Op1C->getValue().isPowerOf2())){
1344 KnownBits Known = computeKnownBits(Op0, 0, &CI);
1345
1346 APInt KnownZeroMask(~Known.Zero);
1347 if (KnownZeroMask.isPowerOf2()) {
1348 Value *In = ICI->getOperand(0);
1349
1350 // If the icmp tests for a known zero bit we can constant fold it.
1351 if (!Op1C->isZero() && Op1C->getValue() != KnownZeroMask) {
1352 Value *V = Pred == ICmpInst::ICMP_NE ?
1353 ConstantInt::getAllOnesValue(CI.getType()) :
1354 ConstantInt::getNullValue(CI.getType());
1355 return replaceInstUsesWith(CI, V);
1356 }
1357
1358 if (!Op1C->isZero() == (Pred == ICmpInst::ICMP_NE)) {
1359 // sext ((x & 2^n) == 0) -> (x >> n) - 1
1360 // sext ((x & 2^n) != 2^n) -> (x >> n) - 1
1361 unsigned ShiftAmt = KnownZeroMask.countTrailingZeros();
1362 // Perform a right shift to place the desired bit in the LSB.
1363 if (ShiftAmt)
1364 In = Builder.CreateLShr(In,
1365 ConstantInt::get(In->getType(), ShiftAmt));
1366
1367 // At this point "In" is either 1 or 0. Subtract 1 to turn
1368 // {1, 0} -> {0, -1}.
1369 In = Builder.CreateAdd(In,
1370 ConstantInt::getAllOnesValue(In->getType()),
1371 "sext");
1372 } else {
1373 // sext ((x & 2^n) != 0) -> (x << bitwidth-n) a>> bitwidth-1
1374 // sext ((x & 2^n) == 2^n) -> (x << bitwidth-n) a>> bitwidth-1
1375 unsigned ShiftAmt = KnownZeroMask.countLeadingZeros();
1376 // Perform a left shift to place the desired bit in the MSB.
1377 if (ShiftAmt)
1378 In = Builder.CreateShl(In,
1379 ConstantInt::get(In->getType(), ShiftAmt));
1380
1381 // Distribute the bit over the whole bit width.
1382 In = Builder.CreateAShr(In, ConstantInt::get(In->getType(),
1383 KnownZeroMask.getBitWidth() - 1), "sext");
1384 }
1385
1386 if (CI.getType() == In->getType())
1387 return replaceInstUsesWith(CI, In);
1388 return CastInst::CreateIntegerCast(In, CI.getType(), true/*SExt*/);
1389 }
1390 }
1391 }
1392
1393 return nullptr;
1394 }
1395
1396 /// Return true if we can take the specified value and return it as type Ty
1397 /// without inserting any new casts and without changing the value of the common
1398 /// low bits. This is used by code that tries to promote integer operations to
1399 /// a wider types will allow us to eliminate the extension.
1400 ///
1401 /// This function works on both vectors and scalars.
1402 ///
canEvaluateSExtd(Value * V,Type * Ty)1403 static bool canEvaluateSExtd(Value *V, Type *Ty) {
1404 assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() &&
1405 "Can't sign extend type to a smaller type");
1406 if (canAlwaysEvaluateInType(V, Ty))
1407 return true;
1408 if (canNotEvaluateInType(V, Ty))
1409 return false;
1410
1411 auto *I = cast<Instruction>(V);
1412 switch (I->getOpcode()) {
1413 case Instruction::SExt: // sext(sext(x)) -> sext(x)
1414 case Instruction::ZExt: // sext(zext(x)) -> zext(x)
1415 case Instruction::Trunc: // sext(trunc(x)) -> trunc(x) or sext(x)
1416 return true;
1417 case Instruction::And:
1418 case Instruction::Or:
1419 case Instruction::Xor:
1420 case Instruction::Add:
1421 case Instruction::Sub:
1422 case Instruction::Mul:
1423 // These operators can all arbitrarily be extended if their inputs can.
1424 return canEvaluateSExtd(I->getOperand(0), Ty) &&
1425 canEvaluateSExtd(I->getOperand(1), Ty);
1426
1427 //case Instruction::Shl: TODO
1428 //case Instruction::LShr: TODO
1429
1430 case Instruction::Select:
1431 return canEvaluateSExtd(I->getOperand(1), Ty) &&
1432 canEvaluateSExtd(I->getOperand(2), Ty);
1433
1434 case Instruction::PHI: {
1435 // We can change a phi if we can change all operands. Note that we never
1436 // get into trouble with cyclic PHIs here because we only consider
1437 // instructions with a single use.
1438 PHINode *PN = cast<PHINode>(I);
1439 for (Value *IncValue : PN->incoming_values())
1440 if (!canEvaluateSExtd(IncValue, Ty)) return false;
1441 return true;
1442 }
1443 default:
1444 // TODO: Can handle more cases here.
1445 break;
1446 }
1447
1448 return false;
1449 }
1450
visitSExt(SExtInst & CI)1451 Instruction *InstCombinerImpl::visitSExt(SExtInst &CI) {
1452 // If this sign extend is only used by a truncate, let the truncate be
1453 // eliminated before we try to optimize this sext.
1454 if (CI.hasOneUse() && isa<TruncInst>(CI.user_back()))
1455 return nullptr;
1456
1457 if (Instruction *I = commonCastTransforms(CI))
1458 return I;
1459
1460 Value *Src = CI.getOperand(0);
1461 Type *SrcTy = Src->getType(), *DestTy = CI.getType();
1462
1463 // If we know that the value being extended is positive, we can use a zext
1464 // instead.
1465 KnownBits Known = computeKnownBits(Src, 0, &CI);
1466 if (Known.isNonNegative())
1467 return CastInst::Create(Instruction::ZExt, Src, DestTy);
1468
1469 // Try to extend the entire expression tree to the wide destination type.
1470 if (shouldChangeType(SrcTy, DestTy) && canEvaluateSExtd(Src, DestTy)) {
1471 // Okay, we can transform this! Insert the new expression now.
1472 LLVM_DEBUG(
1473 dbgs() << "ICE: EvaluateInDifferentType converting expression type"
1474 " to avoid sign extend: "
1475 << CI << '\n');
1476 Value *Res = EvaluateInDifferentType(Src, DestTy, true);
1477 assert(Res->getType() == DestTy);
1478
1479 uint32_t SrcBitSize = SrcTy->getScalarSizeInBits();
1480 uint32_t DestBitSize = DestTy->getScalarSizeInBits();
1481
1482 // If the high bits are already filled with sign bit, just replace this
1483 // cast with the result.
1484 if (ComputeNumSignBits(Res, 0, &CI) > DestBitSize - SrcBitSize)
1485 return replaceInstUsesWith(CI, Res);
1486
1487 // We need to emit a shl + ashr to do the sign extend.
1488 Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize);
1489 return BinaryOperator::CreateAShr(Builder.CreateShl(Res, ShAmt, "sext"),
1490 ShAmt);
1491 }
1492
1493 // If the input is a trunc from the destination type, then turn sext(trunc(x))
1494 // into shifts.
1495 Value *X;
1496 if (match(Src, m_OneUse(m_Trunc(m_Value(X)))) && X->getType() == DestTy) {
1497 // sext(trunc(X)) --> ashr(shl(X, C), C)
1498 unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1499 unsigned DestBitSize = DestTy->getScalarSizeInBits();
1500 Constant *ShAmt = ConstantInt::get(DestTy, DestBitSize - SrcBitSize);
1501 return BinaryOperator::CreateAShr(Builder.CreateShl(X, ShAmt), ShAmt);
1502 }
1503
1504 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src))
1505 return transformSExtICmp(ICI, CI);
1506
1507 // If the input is a shl/ashr pair of a same constant, then this is a sign
1508 // extension from a smaller value. If we could trust arbitrary bitwidth
1509 // integers, we could turn this into a truncate to the smaller bit and then
1510 // use a sext for the whole extension. Since we don't, look deeper and check
1511 // for a truncate. If the source and dest are the same type, eliminate the
1512 // trunc and extend and just do shifts. For example, turn:
1513 // %a = trunc i32 %i to i8
1514 // %b = shl i8 %a, C
1515 // %c = ashr i8 %b, C
1516 // %d = sext i8 %c to i32
1517 // into:
1518 // %a = shl i32 %i, 32-(8-C)
1519 // %d = ashr i32 %a, 32-(8-C)
1520 Value *A = nullptr;
1521 // TODO: Eventually this could be subsumed by EvaluateInDifferentType.
1522 Constant *BA = nullptr, *CA = nullptr;
1523 if (match(Src, m_AShr(m_Shl(m_Trunc(m_Value(A)), m_Constant(BA)),
1524 m_Constant(CA))) &&
1525 BA->isElementWiseEqual(CA) && A->getType() == DestTy) {
1526 Constant *WideCurrShAmt = ConstantExpr::getSExt(CA, DestTy);
1527 Constant *NumLowbitsLeft = ConstantExpr::getSub(
1528 ConstantInt::get(DestTy, SrcTy->getScalarSizeInBits()), WideCurrShAmt);
1529 Constant *NewShAmt = ConstantExpr::getSub(
1530 ConstantInt::get(DestTy, DestTy->getScalarSizeInBits()),
1531 NumLowbitsLeft);
1532 NewShAmt =
1533 Constant::mergeUndefsWith(Constant::mergeUndefsWith(NewShAmt, BA), CA);
1534 A = Builder.CreateShl(A, NewShAmt, CI.getName());
1535 return BinaryOperator::CreateAShr(A, NewShAmt);
1536 }
1537
1538 return nullptr;
1539 }
1540
1541 /// Return a Constant* for the specified floating-point constant if it fits
1542 /// in the specified FP type without changing its value.
fitsInFPType(ConstantFP * CFP,const fltSemantics & Sem)1543 static bool fitsInFPType(ConstantFP *CFP, const fltSemantics &Sem) {
1544 bool losesInfo;
1545 APFloat F = CFP->getValueAPF();
1546 (void)F.convert(Sem, APFloat::rmNearestTiesToEven, &losesInfo);
1547 return !losesInfo;
1548 }
1549
shrinkFPConstant(ConstantFP * CFP)1550 static Type *shrinkFPConstant(ConstantFP *CFP) {
1551 if (CFP->getType() == Type::getPPC_FP128Ty(CFP->getContext()))
1552 return nullptr; // No constant folding of this.
1553 // See if the value can be truncated to half and then reextended.
1554 if (fitsInFPType(CFP, APFloat::IEEEhalf()))
1555 return Type::getHalfTy(CFP->getContext());
1556 // See if the value can be truncated to float and then reextended.
1557 if (fitsInFPType(CFP, APFloat::IEEEsingle()))
1558 return Type::getFloatTy(CFP->getContext());
1559 if (CFP->getType()->isDoubleTy())
1560 return nullptr; // Won't shrink.
1561 if (fitsInFPType(CFP, APFloat::IEEEdouble()))
1562 return Type::getDoubleTy(CFP->getContext());
1563 // Don't try to shrink to various long double types.
1564 return nullptr;
1565 }
1566
1567 // Determine if this is a vector of ConstantFPs and if so, return the minimal
1568 // type we can safely truncate all elements to.
1569 // TODO: Make these support undef elements.
shrinkFPConstantVector(Value * V)1570 static Type *shrinkFPConstantVector(Value *V) {
1571 auto *CV = dyn_cast<Constant>(V);
1572 auto *CVVTy = dyn_cast<VectorType>(V->getType());
1573 if (!CV || !CVVTy)
1574 return nullptr;
1575
1576 Type *MinType = nullptr;
1577
1578 unsigned NumElts = cast<FixedVectorType>(CVVTy)->getNumElements();
1579 for (unsigned i = 0; i != NumElts; ++i) {
1580 auto *CFP = dyn_cast_or_null<ConstantFP>(CV->getAggregateElement(i));
1581 if (!CFP)
1582 return nullptr;
1583
1584 Type *T = shrinkFPConstant(CFP);
1585 if (!T)
1586 return nullptr;
1587
1588 // If we haven't found a type yet or this type has a larger mantissa than
1589 // our previous type, this is our new minimal type.
1590 if (!MinType || T->getFPMantissaWidth() > MinType->getFPMantissaWidth())
1591 MinType = T;
1592 }
1593
1594 // Make a vector type from the minimal type.
1595 return FixedVectorType::get(MinType, NumElts);
1596 }
1597
1598 /// Find the minimum FP type we can safely truncate to.
getMinimumFPType(Value * V)1599 static Type *getMinimumFPType(Value *V) {
1600 if (auto *FPExt = dyn_cast<FPExtInst>(V))
1601 return FPExt->getOperand(0)->getType();
1602
1603 // If this value is a constant, return the constant in the smallest FP type
1604 // that can accurately represent it. This allows us to turn
1605 // (float)((double)X+2.0) into x+2.0f.
1606 if (auto *CFP = dyn_cast<ConstantFP>(V))
1607 if (Type *T = shrinkFPConstant(CFP))
1608 return T;
1609
1610 // Try to shrink a vector of FP constants.
1611 if (Type *T = shrinkFPConstantVector(V))
1612 return T;
1613
1614 return V->getType();
1615 }
1616
1617 /// Return true if the cast from integer to FP can be proven to be exact for all
1618 /// possible inputs (the conversion does not lose any precision).
isKnownExactCastIntToFP(CastInst & I)1619 static bool isKnownExactCastIntToFP(CastInst &I) {
1620 CastInst::CastOps Opcode = I.getOpcode();
1621 assert((Opcode == CastInst::SIToFP || Opcode == CastInst::UIToFP) &&
1622 "Unexpected cast");
1623 Value *Src = I.getOperand(0);
1624 Type *SrcTy = Src->getType();
1625 Type *FPTy = I.getType();
1626 bool IsSigned = Opcode == Instruction::SIToFP;
1627 int SrcSize = (int)SrcTy->getScalarSizeInBits() - IsSigned;
1628
1629 // Easy case - if the source integer type has less bits than the FP mantissa,
1630 // then the cast must be exact.
1631 int DestNumSigBits = FPTy->getFPMantissaWidth();
1632 if (SrcSize <= DestNumSigBits)
1633 return true;
1634
1635 // Cast from FP to integer and back to FP is independent of the intermediate
1636 // integer width because of poison on overflow.
1637 Value *F;
1638 if (match(Src, m_FPToSI(m_Value(F))) || match(Src, m_FPToUI(m_Value(F)))) {
1639 // If this is uitofp (fptosi F), the source needs an extra bit to avoid
1640 // potential rounding of negative FP input values.
1641 int SrcNumSigBits = F->getType()->getFPMantissaWidth();
1642 if (!IsSigned && match(Src, m_FPToSI(m_Value())))
1643 SrcNumSigBits++;
1644
1645 // [su]itofp (fpto[su]i F) --> exact if the source type has less or equal
1646 // significant bits than the destination (and make sure neither type is
1647 // weird -- ppc_fp128).
1648 if (SrcNumSigBits > 0 && DestNumSigBits > 0 &&
1649 SrcNumSigBits <= DestNumSigBits)
1650 return true;
1651 }
1652
1653 // TODO:
1654 // Try harder to find if the source integer type has less significant bits.
1655 // For example, compute number of sign bits or compute low bit mask.
1656 return false;
1657 }
1658
visitFPTrunc(FPTruncInst & FPT)1659 Instruction *InstCombinerImpl::visitFPTrunc(FPTruncInst &FPT) {
1660 if (Instruction *I = commonCastTransforms(FPT))
1661 return I;
1662
1663 // If we have fptrunc(OpI (fpextend x), (fpextend y)), we would like to
1664 // simplify this expression to avoid one or more of the trunc/extend
1665 // operations if we can do so without changing the numerical results.
1666 //
1667 // The exact manner in which the widths of the operands interact to limit
1668 // what we can and cannot do safely varies from operation to operation, and
1669 // is explained below in the various case statements.
1670 Type *Ty = FPT.getType();
1671 auto *BO = dyn_cast<BinaryOperator>(FPT.getOperand(0));
1672 if (BO && BO->hasOneUse()) {
1673 Type *LHSMinType = getMinimumFPType(BO->getOperand(0));
1674 Type *RHSMinType = getMinimumFPType(BO->getOperand(1));
1675 unsigned OpWidth = BO->getType()->getFPMantissaWidth();
1676 unsigned LHSWidth = LHSMinType->getFPMantissaWidth();
1677 unsigned RHSWidth = RHSMinType->getFPMantissaWidth();
1678 unsigned SrcWidth = std::max(LHSWidth, RHSWidth);
1679 unsigned DstWidth = Ty->getFPMantissaWidth();
1680 switch (BO->getOpcode()) {
1681 default: break;
1682 case Instruction::FAdd:
1683 case Instruction::FSub:
1684 // For addition and subtraction, the infinitely precise result can
1685 // essentially be arbitrarily wide; proving that double rounding
1686 // will not occur because the result of OpI is exact (as we will for
1687 // FMul, for example) is hopeless. However, we *can* nonetheless
1688 // frequently know that double rounding cannot occur (or that it is
1689 // innocuous) by taking advantage of the specific structure of
1690 // infinitely-precise results that admit double rounding.
1691 //
1692 // Specifically, if OpWidth >= 2*DstWdith+1 and DstWidth is sufficient
1693 // to represent both sources, we can guarantee that the double
1694 // rounding is innocuous (See p50 of Figueroa's 2000 PhD thesis,
1695 // "A Rigorous Framework for Fully Supporting the IEEE Standard ..."
1696 // for proof of this fact).
1697 //
1698 // Note: Figueroa does not consider the case where DstFormat !=
1699 // SrcFormat. It's possible (likely even!) that this analysis
1700 // could be tightened for those cases, but they are rare (the main
1701 // case of interest here is (float)((double)float + float)).
1702 if (OpWidth >= 2*DstWidth+1 && DstWidth >= SrcWidth) {
1703 Value *LHS = Builder.CreateFPTrunc(BO->getOperand(0), Ty);
1704 Value *RHS = Builder.CreateFPTrunc(BO->getOperand(1), Ty);
1705 Instruction *RI = BinaryOperator::Create(BO->getOpcode(), LHS, RHS);
1706 RI->copyFastMathFlags(BO);
1707 return RI;
1708 }
1709 break;
1710 case Instruction::FMul:
1711 // For multiplication, the infinitely precise result has at most
1712 // LHSWidth + RHSWidth significant bits; if OpWidth is sufficient
1713 // that such a value can be exactly represented, then no double
1714 // rounding can possibly occur; we can safely perform the operation
1715 // in the destination format if it can represent both sources.
1716 if (OpWidth >= LHSWidth + RHSWidth && DstWidth >= SrcWidth) {
1717 Value *LHS = Builder.CreateFPTrunc(BO->getOperand(0), Ty);
1718 Value *RHS = Builder.CreateFPTrunc(BO->getOperand(1), Ty);
1719 return BinaryOperator::CreateFMulFMF(LHS, RHS, BO);
1720 }
1721 break;
1722 case Instruction::FDiv:
1723 // For division, we use again use the bound from Figueroa's
1724 // dissertation. I am entirely certain that this bound can be
1725 // tightened in the unbalanced operand case by an analysis based on
1726 // the diophantine rational approximation bound, but the well-known
1727 // condition used here is a good conservative first pass.
1728 // TODO: Tighten bound via rigorous analysis of the unbalanced case.
1729 if (OpWidth >= 2*DstWidth && DstWidth >= SrcWidth) {
1730 Value *LHS = Builder.CreateFPTrunc(BO->getOperand(0), Ty);
1731 Value *RHS = Builder.CreateFPTrunc(BO->getOperand(1), Ty);
1732 return BinaryOperator::CreateFDivFMF(LHS, RHS, BO);
1733 }
1734 break;
1735 case Instruction::FRem: {
1736 // Remainder is straightforward. Remainder is always exact, so the
1737 // type of OpI doesn't enter into things at all. We simply evaluate
1738 // in whichever source type is larger, then convert to the
1739 // destination type.
1740 if (SrcWidth == OpWidth)
1741 break;
1742 Value *LHS, *RHS;
1743 if (LHSWidth == SrcWidth) {
1744 LHS = Builder.CreateFPTrunc(BO->getOperand(0), LHSMinType);
1745 RHS = Builder.CreateFPTrunc(BO->getOperand(1), LHSMinType);
1746 } else {
1747 LHS = Builder.CreateFPTrunc(BO->getOperand(0), RHSMinType);
1748 RHS = Builder.CreateFPTrunc(BO->getOperand(1), RHSMinType);
1749 }
1750
1751 Value *ExactResult = Builder.CreateFRemFMF(LHS, RHS, BO);
1752 return CastInst::CreateFPCast(ExactResult, Ty);
1753 }
1754 }
1755 }
1756
1757 // (fptrunc (fneg x)) -> (fneg (fptrunc x))
1758 Value *X;
1759 Instruction *Op = dyn_cast<Instruction>(FPT.getOperand(0));
1760 if (Op && Op->hasOneUse()) {
1761 // FIXME: The FMF should propagate from the fptrunc, not the source op.
1762 IRBuilder<>::FastMathFlagGuard FMFG(Builder);
1763 if (isa<FPMathOperator>(Op))
1764 Builder.setFastMathFlags(Op->getFastMathFlags());
1765
1766 if (match(Op, m_FNeg(m_Value(X)))) {
1767 Value *InnerTrunc = Builder.CreateFPTrunc(X, Ty);
1768
1769 return UnaryOperator::CreateFNegFMF(InnerTrunc, Op);
1770 }
1771
1772 // If we are truncating a select that has an extended operand, we can
1773 // narrow the other operand and do the select as a narrow op.
1774 Value *Cond, *X, *Y;
1775 if (match(Op, m_Select(m_Value(Cond), m_FPExt(m_Value(X)), m_Value(Y))) &&
1776 X->getType() == Ty) {
1777 // fptrunc (select Cond, (fpext X), Y --> select Cond, X, (fptrunc Y)
1778 Value *NarrowY = Builder.CreateFPTrunc(Y, Ty);
1779 Value *Sel = Builder.CreateSelect(Cond, X, NarrowY, "narrow.sel", Op);
1780 return replaceInstUsesWith(FPT, Sel);
1781 }
1782 if (match(Op, m_Select(m_Value(Cond), m_Value(Y), m_FPExt(m_Value(X)))) &&
1783 X->getType() == Ty) {
1784 // fptrunc (select Cond, Y, (fpext X) --> select Cond, (fptrunc Y), X
1785 Value *NarrowY = Builder.CreateFPTrunc(Y, Ty);
1786 Value *Sel = Builder.CreateSelect(Cond, NarrowY, X, "narrow.sel", Op);
1787 return replaceInstUsesWith(FPT, Sel);
1788 }
1789 }
1790
1791 if (auto *II = dyn_cast<IntrinsicInst>(FPT.getOperand(0))) {
1792 switch (II->getIntrinsicID()) {
1793 default: break;
1794 case Intrinsic::ceil:
1795 case Intrinsic::fabs:
1796 case Intrinsic::floor:
1797 case Intrinsic::nearbyint:
1798 case Intrinsic::rint:
1799 case Intrinsic::round:
1800 case Intrinsic::roundeven:
1801 case Intrinsic::trunc: {
1802 Value *Src = II->getArgOperand(0);
1803 if (!Src->hasOneUse())
1804 break;
1805
1806 // Except for fabs, this transformation requires the input of the unary FP
1807 // operation to be itself an fpext from the type to which we're
1808 // truncating.
1809 if (II->getIntrinsicID() != Intrinsic::fabs) {
1810 FPExtInst *FPExtSrc = dyn_cast<FPExtInst>(Src);
1811 if (!FPExtSrc || FPExtSrc->getSrcTy() != Ty)
1812 break;
1813 }
1814
1815 // Do unary FP operation on smaller type.
1816 // (fptrunc (fabs x)) -> (fabs (fptrunc x))
1817 Value *InnerTrunc = Builder.CreateFPTrunc(Src, Ty);
1818 Function *Overload = Intrinsic::getDeclaration(FPT.getModule(),
1819 II->getIntrinsicID(), Ty);
1820 SmallVector<OperandBundleDef, 1> OpBundles;
1821 II->getOperandBundlesAsDefs(OpBundles);
1822 CallInst *NewCI =
1823 CallInst::Create(Overload, {InnerTrunc}, OpBundles, II->getName());
1824 NewCI->copyFastMathFlags(II);
1825 return NewCI;
1826 }
1827 }
1828 }
1829
1830 if (Instruction *I = shrinkInsertElt(FPT, Builder))
1831 return I;
1832
1833 Value *Src = FPT.getOperand(0);
1834 if (isa<SIToFPInst>(Src) || isa<UIToFPInst>(Src)) {
1835 auto *FPCast = cast<CastInst>(Src);
1836 if (isKnownExactCastIntToFP(*FPCast))
1837 return CastInst::Create(FPCast->getOpcode(), FPCast->getOperand(0), Ty);
1838 }
1839
1840 return nullptr;
1841 }
1842
visitFPExt(CastInst & FPExt)1843 Instruction *InstCombinerImpl::visitFPExt(CastInst &FPExt) {
1844 // If the source operand is a cast from integer to FP and known exact, then
1845 // cast the integer operand directly to the destination type.
1846 Type *Ty = FPExt.getType();
1847 Value *Src = FPExt.getOperand(0);
1848 if (isa<SIToFPInst>(Src) || isa<UIToFPInst>(Src)) {
1849 auto *FPCast = cast<CastInst>(Src);
1850 if (isKnownExactCastIntToFP(*FPCast))
1851 return CastInst::Create(FPCast->getOpcode(), FPCast->getOperand(0), Ty);
1852 }
1853
1854 return commonCastTransforms(FPExt);
1855 }
1856
1857 /// fpto{s/u}i({u/s}itofp(X)) --> X or zext(X) or sext(X) or trunc(X)
1858 /// This is safe if the intermediate type has enough bits in its mantissa to
1859 /// accurately represent all values of X. For example, this won't work with
1860 /// i64 -> float -> i64.
foldItoFPtoI(CastInst & FI)1861 Instruction *InstCombinerImpl::foldItoFPtoI(CastInst &FI) {
1862 if (!isa<UIToFPInst>(FI.getOperand(0)) && !isa<SIToFPInst>(FI.getOperand(0)))
1863 return nullptr;
1864
1865 auto *OpI = cast<CastInst>(FI.getOperand(0));
1866 Value *X = OpI->getOperand(0);
1867 Type *XType = X->getType();
1868 Type *DestType = FI.getType();
1869 bool IsOutputSigned = isa<FPToSIInst>(FI);
1870
1871 // Since we can assume the conversion won't overflow, our decision as to
1872 // whether the input will fit in the float should depend on the minimum
1873 // of the input range and output range.
1874
1875 // This means this is also safe for a signed input and unsigned output, since
1876 // a negative input would lead to undefined behavior.
1877 if (!isKnownExactCastIntToFP(*OpI)) {
1878 // The first cast may not round exactly based on the source integer width
1879 // and FP width, but the overflow UB rules can still allow this to fold.
1880 // If the destination type is narrow, that means the intermediate FP value
1881 // must be large enough to hold the source value exactly.
1882 // For example, (uint8_t)((float)(uint32_t 16777217) is undefined behavior.
1883 int OutputSize = (int)DestType->getScalarSizeInBits() - IsOutputSigned;
1884 if (OutputSize > OpI->getType()->getFPMantissaWidth())
1885 return nullptr;
1886 }
1887
1888 if (DestType->getScalarSizeInBits() > XType->getScalarSizeInBits()) {
1889 bool IsInputSigned = isa<SIToFPInst>(OpI);
1890 if (IsInputSigned && IsOutputSigned)
1891 return new SExtInst(X, DestType);
1892 return new ZExtInst(X, DestType);
1893 }
1894 if (DestType->getScalarSizeInBits() < XType->getScalarSizeInBits())
1895 return new TruncInst(X, DestType);
1896
1897 assert(XType == DestType && "Unexpected types for int to FP to int casts");
1898 return replaceInstUsesWith(FI, X);
1899 }
1900
visitFPToUI(FPToUIInst & FI)1901 Instruction *InstCombinerImpl::visitFPToUI(FPToUIInst &FI) {
1902 if (Instruction *I = foldItoFPtoI(FI))
1903 return I;
1904
1905 return commonCastTransforms(FI);
1906 }
1907
visitFPToSI(FPToSIInst & FI)1908 Instruction *InstCombinerImpl::visitFPToSI(FPToSIInst &FI) {
1909 if (Instruction *I = foldItoFPtoI(FI))
1910 return I;
1911
1912 return commonCastTransforms(FI);
1913 }
1914
visitUIToFP(CastInst & CI)1915 Instruction *InstCombinerImpl::visitUIToFP(CastInst &CI) {
1916 return commonCastTransforms(CI);
1917 }
1918
visitSIToFP(CastInst & CI)1919 Instruction *InstCombinerImpl::visitSIToFP(CastInst &CI) {
1920 return commonCastTransforms(CI);
1921 }
1922
visitIntToPtr(IntToPtrInst & CI)1923 Instruction *InstCombinerImpl::visitIntToPtr(IntToPtrInst &CI) {
1924 // If the source integer type is not the intptr_t type for this target, do a
1925 // trunc or zext to the intptr_t type, then inttoptr of it. This allows the
1926 // cast to be exposed to other transforms.
1927 unsigned AS = CI.getAddressSpace();
1928 if (CI.getOperand(0)->getType()->getScalarSizeInBits() !=
1929 DL.getPointerSizeInBits(AS)) {
1930 Type *Ty = DL.getIntPtrType(CI.getContext(), AS);
1931 // Handle vectors of pointers.
1932 if (auto *CIVTy = dyn_cast<VectorType>(CI.getType()))
1933 Ty = VectorType::get(Ty, CIVTy->getElementCount());
1934
1935 Value *P = Builder.CreateZExtOrTrunc(CI.getOperand(0), Ty);
1936 return new IntToPtrInst(P, CI.getType());
1937 }
1938
1939 if (Instruction *I = commonCastTransforms(CI))
1940 return I;
1941
1942 return nullptr;
1943 }
1944
1945 /// Implement the transforms for cast of pointer (bitcast/ptrtoint)
commonPointerCastTransforms(CastInst & CI)1946 Instruction *InstCombinerImpl::commonPointerCastTransforms(CastInst &CI) {
1947 Value *Src = CI.getOperand(0);
1948
1949 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
1950 // If casting the result of a getelementptr instruction with no offset, turn
1951 // this into a cast of the original pointer!
1952 if (GEP->hasAllZeroIndices() &&
1953 // If CI is an addrspacecast and GEP changes the poiner type, merging
1954 // GEP into CI would undo canonicalizing addrspacecast with different
1955 // pointer types, causing infinite loops.
1956 (!isa<AddrSpaceCastInst>(CI) ||
1957 GEP->getType() == GEP->getPointerOperandType())) {
1958 // Changing the cast operand is usually not a good idea but it is safe
1959 // here because the pointer operand is being replaced with another
1960 // pointer operand so the opcode doesn't need to change.
1961 return replaceOperand(CI, 0, GEP->getOperand(0));
1962 }
1963 }
1964
1965 return commonCastTransforms(CI);
1966 }
1967
visitPtrToInt(PtrToIntInst & CI)1968 Instruction *InstCombinerImpl::visitPtrToInt(PtrToIntInst &CI) {
1969 // If the destination integer type is not the intptr_t type for this target,
1970 // do a ptrtoint to intptr_t then do a trunc or zext. This allows the cast
1971 // to be exposed to other transforms.
1972 Value *SrcOp = CI.getPointerOperand();
1973 Type *Ty = CI.getType();
1974 unsigned AS = CI.getPointerAddressSpace();
1975 unsigned TySize = Ty->getScalarSizeInBits();
1976 unsigned PtrSize = DL.getPointerSizeInBits(AS);
1977 if (TySize != PtrSize) {
1978 Type *IntPtrTy = DL.getIntPtrType(CI.getContext(), AS);
1979 // Handle vectors of pointers.
1980 if (auto *VecTy = dyn_cast<VectorType>(Ty))
1981 IntPtrTy = VectorType::get(IntPtrTy, VecTy->getElementCount());
1982
1983 Value *P = Builder.CreatePtrToInt(SrcOp, IntPtrTy);
1984 return CastInst::CreateIntegerCast(P, Ty, /*isSigned=*/false);
1985 }
1986
1987 Value *Vec, *Scalar, *Index;
1988 if (match(SrcOp, m_OneUse(m_InsertElt(m_IntToPtr(m_Value(Vec)),
1989 m_Value(Scalar), m_Value(Index)))) &&
1990 Vec->getType() == Ty) {
1991 assert(Vec->getType()->getScalarSizeInBits() == PtrSize && "Wrong type");
1992 // Convert the scalar to int followed by insert to eliminate one cast:
1993 // p2i (ins (i2p Vec), Scalar, Index --> ins Vec, (p2i Scalar), Index
1994 Value *NewCast = Builder.CreatePtrToInt(Scalar, Ty->getScalarType());
1995 return InsertElementInst::Create(Vec, NewCast, Index);
1996 }
1997
1998 return commonPointerCastTransforms(CI);
1999 }
2000
2001 /// This input value (which is known to have vector type) is being zero extended
2002 /// or truncated to the specified vector type. Since the zext/trunc is done
2003 /// using an integer type, we have a (bitcast(cast(bitcast))) pattern,
2004 /// endianness will impact which end of the vector that is extended or
2005 /// truncated.
2006 ///
2007 /// A vector is always stored with index 0 at the lowest address, which
2008 /// corresponds to the most significant bits for a big endian stored integer and
2009 /// the least significant bits for little endian. A trunc/zext of an integer
2010 /// impacts the big end of the integer. Thus, we need to add/remove elements at
2011 /// the front of the vector for big endian targets, and the back of the vector
2012 /// for little endian targets.
2013 ///
2014 /// Try to replace it with a shuffle (and vector/vector bitcast) if possible.
2015 ///
2016 /// The source and destination vector types may have different element types.
2017 static Instruction *
optimizeVectorResizeWithIntegerBitCasts(Value * InVal,VectorType * DestTy,InstCombinerImpl & IC)2018 optimizeVectorResizeWithIntegerBitCasts(Value *InVal, VectorType *DestTy,
2019 InstCombinerImpl &IC) {
2020 // We can only do this optimization if the output is a multiple of the input
2021 // element size, or the input is a multiple of the output element size.
2022 // Convert the input type to have the same element type as the output.
2023 VectorType *SrcTy = cast<VectorType>(InVal->getType());
2024
2025 if (SrcTy->getElementType() != DestTy->getElementType()) {
2026 // The input types don't need to be identical, but for now they must be the
2027 // same size. There is no specific reason we couldn't handle things like
2028 // <4 x i16> -> <4 x i32> by bitcasting to <2 x i32> but haven't gotten
2029 // there yet.
2030 if (SrcTy->getElementType()->getPrimitiveSizeInBits() !=
2031 DestTy->getElementType()->getPrimitiveSizeInBits())
2032 return nullptr;
2033
2034 SrcTy =
2035 FixedVectorType::get(DestTy->getElementType(),
2036 cast<FixedVectorType>(SrcTy)->getNumElements());
2037 InVal = IC.Builder.CreateBitCast(InVal, SrcTy);
2038 }
2039
2040 bool IsBigEndian = IC.getDataLayout().isBigEndian();
2041 unsigned SrcElts = cast<FixedVectorType>(SrcTy)->getNumElements();
2042 unsigned DestElts = cast<FixedVectorType>(DestTy)->getNumElements();
2043
2044 assert(SrcElts != DestElts && "Element counts should be different.");
2045
2046 // Now that the element types match, get the shuffle mask and RHS of the
2047 // shuffle to use, which depends on whether we're increasing or decreasing the
2048 // size of the input.
2049 SmallVector<int, 16> ShuffleMaskStorage;
2050 ArrayRef<int> ShuffleMask;
2051 Value *V2;
2052
2053 // Produce an identify shuffle mask for the src vector.
2054 ShuffleMaskStorage.resize(SrcElts);
2055 std::iota(ShuffleMaskStorage.begin(), ShuffleMaskStorage.end(), 0);
2056
2057 if (SrcElts > DestElts) {
2058 // If we're shrinking the number of elements (rewriting an integer
2059 // truncate), just shuffle in the elements corresponding to the least
2060 // significant bits from the input and use undef as the second shuffle
2061 // input.
2062 V2 = UndefValue::get(SrcTy);
2063 // Make sure the shuffle mask selects the "least significant bits" by
2064 // keeping elements from back of the src vector for big endian, and from the
2065 // front for little endian.
2066 ShuffleMask = ShuffleMaskStorage;
2067 if (IsBigEndian)
2068 ShuffleMask = ShuffleMask.take_back(DestElts);
2069 else
2070 ShuffleMask = ShuffleMask.take_front(DestElts);
2071 } else {
2072 // If we're increasing the number of elements (rewriting an integer zext),
2073 // shuffle in all of the elements from InVal. Fill the rest of the result
2074 // elements with zeros from a constant zero.
2075 V2 = Constant::getNullValue(SrcTy);
2076 // Use first elt from V2 when indicating zero in the shuffle mask.
2077 uint32_t NullElt = SrcElts;
2078 // Extend with null values in the "most significant bits" by adding elements
2079 // in front of the src vector for big endian, and at the back for little
2080 // endian.
2081 unsigned DeltaElts = DestElts - SrcElts;
2082 if (IsBigEndian)
2083 ShuffleMaskStorage.insert(ShuffleMaskStorage.begin(), DeltaElts, NullElt);
2084 else
2085 ShuffleMaskStorage.append(DeltaElts, NullElt);
2086 ShuffleMask = ShuffleMaskStorage;
2087 }
2088
2089 return new ShuffleVectorInst(InVal, V2, ShuffleMask);
2090 }
2091
isMultipleOfTypeSize(unsigned Value,Type * Ty)2092 static bool isMultipleOfTypeSize(unsigned Value, Type *Ty) {
2093 return Value % Ty->getPrimitiveSizeInBits() == 0;
2094 }
2095
getTypeSizeIndex(unsigned Value,Type * Ty)2096 static unsigned getTypeSizeIndex(unsigned Value, Type *Ty) {
2097 return Value / Ty->getPrimitiveSizeInBits();
2098 }
2099
2100 /// V is a value which is inserted into a vector of VecEltTy.
2101 /// Look through the value to see if we can decompose it into
2102 /// insertions into the vector. See the example in the comment for
2103 /// OptimizeIntegerToVectorInsertions for the pattern this handles.
2104 /// The type of V is always a non-zero multiple of VecEltTy's size.
2105 /// Shift is the number of bits between the lsb of V and the lsb of
2106 /// the vector.
2107 ///
2108 /// This returns false if the pattern can't be matched or true if it can,
2109 /// filling in Elements with the elements found here.
collectInsertionElements(Value * V,unsigned Shift,SmallVectorImpl<Value * > & Elements,Type * VecEltTy,bool isBigEndian)2110 static bool collectInsertionElements(Value *V, unsigned Shift,
2111 SmallVectorImpl<Value *> &Elements,
2112 Type *VecEltTy, bool isBigEndian) {
2113 assert(isMultipleOfTypeSize(Shift, VecEltTy) &&
2114 "Shift should be a multiple of the element type size");
2115
2116 // Undef values never contribute useful bits to the result.
2117 if (isa<UndefValue>(V)) return true;
2118
2119 // If we got down to a value of the right type, we win, try inserting into the
2120 // right element.
2121 if (V->getType() == VecEltTy) {
2122 // Inserting null doesn't actually insert any elements.
2123 if (Constant *C = dyn_cast<Constant>(V))
2124 if (C->isNullValue())
2125 return true;
2126
2127 unsigned ElementIndex = getTypeSizeIndex(Shift, VecEltTy);
2128 if (isBigEndian)
2129 ElementIndex = Elements.size() - ElementIndex - 1;
2130
2131 // Fail if multiple elements are inserted into this slot.
2132 if (Elements[ElementIndex])
2133 return false;
2134
2135 Elements[ElementIndex] = V;
2136 return true;
2137 }
2138
2139 if (Constant *C = dyn_cast<Constant>(V)) {
2140 // Figure out the # elements this provides, and bitcast it or slice it up
2141 // as required.
2142 unsigned NumElts = getTypeSizeIndex(C->getType()->getPrimitiveSizeInBits(),
2143 VecEltTy);
2144 // If the constant is the size of a vector element, we just need to bitcast
2145 // it to the right type so it gets properly inserted.
2146 if (NumElts == 1)
2147 return collectInsertionElements(ConstantExpr::getBitCast(C, VecEltTy),
2148 Shift, Elements, VecEltTy, isBigEndian);
2149
2150 // Okay, this is a constant that covers multiple elements. Slice it up into
2151 // pieces and insert each element-sized piece into the vector.
2152 if (!isa<IntegerType>(C->getType()))
2153 C = ConstantExpr::getBitCast(C, IntegerType::get(V->getContext(),
2154 C->getType()->getPrimitiveSizeInBits()));
2155 unsigned ElementSize = VecEltTy->getPrimitiveSizeInBits();
2156 Type *ElementIntTy = IntegerType::get(C->getContext(), ElementSize);
2157
2158 for (unsigned i = 0; i != NumElts; ++i) {
2159 unsigned ShiftI = Shift+i*ElementSize;
2160 Constant *Piece = ConstantExpr::getLShr(C, ConstantInt::get(C->getType(),
2161 ShiftI));
2162 Piece = ConstantExpr::getTrunc(Piece, ElementIntTy);
2163 if (!collectInsertionElements(Piece, ShiftI, Elements, VecEltTy,
2164 isBigEndian))
2165 return false;
2166 }
2167 return true;
2168 }
2169
2170 if (!V->hasOneUse()) return false;
2171
2172 Instruction *I = dyn_cast<Instruction>(V);
2173 if (!I) return false;
2174 switch (I->getOpcode()) {
2175 default: return false; // Unhandled case.
2176 case Instruction::BitCast:
2177 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
2178 isBigEndian);
2179 case Instruction::ZExt:
2180 if (!isMultipleOfTypeSize(
2181 I->getOperand(0)->getType()->getPrimitiveSizeInBits(),
2182 VecEltTy))
2183 return false;
2184 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
2185 isBigEndian);
2186 case Instruction::Or:
2187 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
2188 isBigEndian) &&
2189 collectInsertionElements(I->getOperand(1), Shift, Elements, VecEltTy,
2190 isBigEndian);
2191 case Instruction::Shl: {
2192 // Must be shifting by a constant that is a multiple of the element size.
2193 ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1));
2194 if (!CI) return false;
2195 Shift += CI->getZExtValue();
2196 if (!isMultipleOfTypeSize(Shift, VecEltTy)) return false;
2197 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
2198 isBigEndian);
2199 }
2200
2201 }
2202 }
2203
2204
2205 /// If the input is an 'or' instruction, we may be doing shifts and ors to
2206 /// assemble the elements of the vector manually.
2207 /// Try to rip the code out and replace it with insertelements. This is to
2208 /// optimize code like this:
2209 ///
2210 /// %tmp37 = bitcast float %inc to i32
2211 /// %tmp38 = zext i32 %tmp37 to i64
2212 /// %tmp31 = bitcast float %inc5 to i32
2213 /// %tmp32 = zext i32 %tmp31 to i64
2214 /// %tmp33 = shl i64 %tmp32, 32
2215 /// %ins35 = or i64 %tmp33, %tmp38
2216 /// %tmp43 = bitcast i64 %ins35 to <2 x float>
2217 ///
2218 /// Into two insertelements that do "buildvector{%inc, %inc5}".
optimizeIntegerToVectorInsertions(BitCastInst & CI,InstCombinerImpl & IC)2219 static Value *optimizeIntegerToVectorInsertions(BitCastInst &CI,
2220 InstCombinerImpl &IC) {
2221 auto *DestVecTy = cast<FixedVectorType>(CI.getType());
2222 Value *IntInput = CI.getOperand(0);
2223
2224 SmallVector<Value*, 8> Elements(DestVecTy->getNumElements());
2225 if (!collectInsertionElements(IntInput, 0, Elements,
2226 DestVecTy->getElementType(),
2227 IC.getDataLayout().isBigEndian()))
2228 return nullptr;
2229
2230 // If we succeeded, we know that all of the element are specified by Elements
2231 // or are zero if Elements has a null entry. Recast this as a set of
2232 // insertions.
2233 Value *Result = Constant::getNullValue(CI.getType());
2234 for (unsigned i = 0, e = Elements.size(); i != e; ++i) {
2235 if (!Elements[i]) continue; // Unset element.
2236
2237 Result = IC.Builder.CreateInsertElement(Result, Elements[i],
2238 IC.Builder.getInt32(i));
2239 }
2240
2241 return Result;
2242 }
2243
2244 /// Canonicalize scalar bitcasts of extracted elements into a bitcast of the
2245 /// vector followed by extract element. The backend tends to handle bitcasts of
2246 /// vectors better than bitcasts of scalars because vector registers are
2247 /// usually not type-specific like scalar integer or scalar floating-point.
canonicalizeBitCastExtElt(BitCastInst & BitCast,InstCombinerImpl & IC)2248 static Instruction *canonicalizeBitCastExtElt(BitCastInst &BitCast,
2249 InstCombinerImpl &IC) {
2250 // TODO: Create and use a pattern matcher for ExtractElementInst.
2251 auto *ExtElt = dyn_cast<ExtractElementInst>(BitCast.getOperand(0));
2252 if (!ExtElt || !ExtElt->hasOneUse())
2253 return nullptr;
2254
2255 // The bitcast must be to a vectorizable type, otherwise we can't make a new
2256 // type to extract from.
2257 Type *DestType = BitCast.getType();
2258 if (!VectorType::isValidElementType(DestType))
2259 return nullptr;
2260
2261 auto *NewVecType = VectorType::get(DestType, ExtElt->getVectorOperandType());
2262 auto *NewBC = IC.Builder.CreateBitCast(ExtElt->getVectorOperand(),
2263 NewVecType, "bc");
2264 return ExtractElementInst::Create(NewBC, ExtElt->getIndexOperand());
2265 }
2266
2267 /// Change the type of a bitwise logic operation if we can eliminate a bitcast.
foldBitCastBitwiseLogic(BitCastInst & BitCast,InstCombiner::BuilderTy & Builder)2268 static Instruction *foldBitCastBitwiseLogic(BitCastInst &BitCast,
2269 InstCombiner::BuilderTy &Builder) {
2270 Type *DestTy = BitCast.getType();
2271 BinaryOperator *BO;
2272 if (!DestTy->isIntOrIntVectorTy() ||
2273 !match(BitCast.getOperand(0), m_OneUse(m_BinOp(BO))) ||
2274 !BO->isBitwiseLogicOp())
2275 return nullptr;
2276
2277 // FIXME: This transform is restricted to vector types to avoid backend
2278 // problems caused by creating potentially illegal operations. If a fix-up is
2279 // added to handle that situation, we can remove this check.
2280 if (!DestTy->isVectorTy() || !BO->getType()->isVectorTy())
2281 return nullptr;
2282
2283 Value *X;
2284 if (match(BO->getOperand(0), m_OneUse(m_BitCast(m_Value(X)))) &&
2285 X->getType() == DestTy && !isa<Constant>(X)) {
2286 // bitcast(logic(bitcast(X), Y)) --> logic'(X, bitcast(Y))
2287 Value *CastedOp1 = Builder.CreateBitCast(BO->getOperand(1), DestTy);
2288 return BinaryOperator::Create(BO->getOpcode(), X, CastedOp1);
2289 }
2290
2291 if (match(BO->getOperand(1), m_OneUse(m_BitCast(m_Value(X)))) &&
2292 X->getType() == DestTy && !isa<Constant>(X)) {
2293 // bitcast(logic(Y, bitcast(X))) --> logic'(bitcast(Y), X)
2294 Value *CastedOp0 = Builder.CreateBitCast(BO->getOperand(0), DestTy);
2295 return BinaryOperator::Create(BO->getOpcode(), CastedOp0, X);
2296 }
2297
2298 // Canonicalize vector bitcasts to come before vector bitwise logic with a
2299 // constant. This eases recognition of special constants for later ops.
2300 // Example:
2301 // icmp u/s (a ^ signmask), (b ^ signmask) --> icmp s/u a, b
2302 Constant *C;
2303 if (match(BO->getOperand(1), m_Constant(C))) {
2304 // bitcast (logic X, C) --> logic (bitcast X, C')
2305 Value *CastedOp0 = Builder.CreateBitCast(BO->getOperand(0), DestTy);
2306 Value *CastedC = Builder.CreateBitCast(C, DestTy);
2307 return BinaryOperator::Create(BO->getOpcode(), CastedOp0, CastedC);
2308 }
2309
2310 return nullptr;
2311 }
2312
2313 /// Change the type of a select if we can eliminate a bitcast.
foldBitCastSelect(BitCastInst & BitCast,InstCombiner::BuilderTy & Builder)2314 static Instruction *foldBitCastSelect(BitCastInst &BitCast,
2315 InstCombiner::BuilderTy &Builder) {
2316 Value *Cond, *TVal, *FVal;
2317 if (!match(BitCast.getOperand(0),
2318 m_OneUse(m_Select(m_Value(Cond), m_Value(TVal), m_Value(FVal)))))
2319 return nullptr;
2320
2321 // A vector select must maintain the same number of elements in its operands.
2322 Type *CondTy = Cond->getType();
2323 Type *DestTy = BitCast.getType();
2324 if (auto *CondVTy = dyn_cast<VectorType>(CondTy))
2325 if (!DestTy->isVectorTy() ||
2326 CondVTy->getElementCount() !=
2327 cast<VectorType>(DestTy)->getElementCount())
2328 return nullptr;
2329
2330 // FIXME: This transform is restricted from changing the select between
2331 // scalars and vectors to avoid backend problems caused by creating
2332 // potentially illegal operations. If a fix-up is added to handle that
2333 // situation, we can remove this check.
2334 if (DestTy->isVectorTy() != TVal->getType()->isVectorTy())
2335 return nullptr;
2336
2337 auto *Sel = cast<Instruction>(BitCast.getOperand(0));
2338 Value *X;
2339 if (match(TVal, m_OneUse(m_BitCast(m_Value(X)))) && X->getType() == DestTy &&
2340 !isa<Constant>(X)) {
2341 // bitcast(select(Cond, bitcast(X), Y)) --> select'(Cond, X, bitcast(Y))
2342 Value *CastedVal = Builder.CreateBitCast(FVal, DestTy);
2343 return SelectInst::Create(Cond, X, CastedVal, "", nullptr, Sel);
2344 }
2345
2346 if (match(FVal, m_OneUse(m_BitCast(m_Value(X)))) && X->getType() == DestTy &&
2347 !isa<Constant>(X)) {
2348 // bitcast(select(Cond, Y, bitcast(X))) --> select'(Cond, bitcast(Y), X)
2349 Value *CastedVal = Builder.CreateBitCast(TVal, DestTy);
2350 return SelectInst::Create(Cond, CastedVal, X, "", nullptr, Sel);
2351 }
2352
2353 return nullptr;
2354 }
2355
2356 /// Check if all users of CI are StoreInsts.
hasStoreUsersOnly(CastInst & CI)2357 static bool hasStoreUsersOnly(CastInst &CI) {
2358 for (User *U : CI.users()) {
2359 if (!isa<StoreInst>(U))
2360 return false;
2361 }
2362 return true;
2363 }
2364
2365 /// This function handles following case
2366 ///
2367 /// A -> B cast
2368 /// PHI
2369 /// B -> A cast
2370 ///
2371 /// All the related PHI nodes can be replaced by new PHI nodes with type A.
2372 /// The uses of \p CI can be changed to the new PHI node corresponding to \p PN.
optimizeBitCastFromPhi(CastInst & CI,PHINode * PN)2373 Instruction *InstCombinerImpl::optimizeBitCastFromPhi(CastInst &CI,
2374 PHINode *PN) {
2375 // BitCast used by Store can be handled in InstCombineLoadStoreAlloca.cpp.
2376 if (hasStoreUsersOnly(CI))
2377 return nullptr;
2378
2379 Value *Src = CI.getOperand(0);
2380 Type *SrcTy = Src->getType(); // Type B
2381 Type *DestTy = CI.getType(); // Type A
2382
2383 SmallVector<PHINode *, 4> PhiWorklist;
2384 SmallSetVector<PHINode *, 4> OldPhiNodes;
2385
2386 // Find all of the A->B casts and PHI nodes.
2387 // We need to inspect all related PHI nodes, but PHIs can be cyclic, so
2388 // OldPhiNodes is used to track all known PHI nodes, before adding a new
2389 // PHI to PhiWorklist, it is checked against and added to OldPhiNodes first.
2390 PhiWorklist.push_back(PN);
2391 OldPhiNodes.insert(PN);
2392 while (!PhiWorklist.empty()) {
2393 auto *OldPN = PhiWorklist.pop_back_val();
2394 for (Value *IncValue : OldPN->incoming_values()) {
2395 if (isa<Constant>(IncValue))
2396 continue;
2397
2398 if (auto *LI = dyn_cast<LoadInst>(IncValue)) {
2399 // If there is a sequence of one or more load instructions, each loaded
2400 // value is used as address of later load instruction, bitcast is
2401 // necessary to change the value type, don't optimize it. For
2402 // simplicity we give up if the load address comes from another load.
2403 Value *Addr = LI->getOperand(0);
2404 if (Addr == &CI || isa<LoadInst>(Addr))
2405 return nullptr;
2406 if (LI->hasOneUse() && LI->isSimple())
2407 continue;
2408 // If a LoadInst has more than one use, changing the type of loaded
2409 // value may create another bitcast.
2410 return nullptr;
2411 }
2412
2413 if (auto *PNode = dyn_cast<PHINode>(IncValue)) {
2414 if (OldPhiNodes.insert(PNode))
2415 PhiWorklist.push_back(PNode);
2416 continue;
2417 }
2418
2419 auto *BCI = dyn_cast<BitCastInst>(IncValue);
2420 // We can't handle other instructions.
2421 if (!BCI)
2422 return nullptr;
2423
2424 // Verify it's a A->B cast.
2425 Type *TyA = BCI->getOperand(0)->getType();
2426 Type *TyB = BCI->getType();
2427 if (TyA != DestTy || TyB != SrcTy)
2428 return nullptr;
2429 }
2430 }
2431
2432 // Check that each user of each old PHI node is something that we can
2433 // rewrite, so that all of the old PHI nodes can be cleaned up afterwards.
2434 for (auto *OldPN : OldPhiNodes) {
2435 for (User *V : OldPN->users()) {
2436 if (auto *SI = dyn_cast<StoreInst>(V)) {
2437 if (!SI->isSimple() || SI->getOperand(0) != OldPN)
2438 return nullptr;
2439 } else if (auto *BCI = dyn_cast<BitCastInst>(V)) {
2440 // Verify it's a B->A cast.
2441 Type *TyB = BCI->getOperand(0)->getType();
2442 Type *TyA = BCI->getType();
2443 if (TyA != DestTy || TyB != SrcTy)
2444 return nullptr;
2445 } else if (auto *PHI = dyn_cast<PHINode>(V)) {
2446 // As long as the user is another old PHI node, then even if we don't
2447 // rewrite it, the PHI web we're considering won't have any users
2448 // outside itself, so it'll be dead.
2449 if (OldPhiNodes.count(PHI) == 0)
2450 return nullptr;
2451 } else {
2452 return nullptr;
2453 }
2454 }
2455 }
2456
2457 // For each old PHI node, create a corresponding new PHI node with a type A.
2458 SmallDenseMap<PHINode *, PHINode *> NewPNodes;
2459 for (auto *OldPN : OldPhiNodes) {
2460 Builder.SetInsertPoint(OldPN);
2461 PHINode *NewPN = Builder.CreatePHI(DestTy, OldPN->getNumOperands());
2462 NewPNodes[OldPN] = NewPN;
2463 }
2464
2465 // Fill in the operands of new PHI nodes.
2466 for (auto *OldPN : OldPhiNodes) {
2467 PHINode *NewPN = NewPNodes[OldPN];
2468 for (unsigned j = 0, e = OldPN->getNumOperands(); j != e; ++j) {
2469 Value *V = OldPN->getOperand(j);
2470 Value *NewV = nullptr;
2471 if (auto *C = dyn_cast<Constant>(V)) {
2472 NewV = ConstantExpr::getBitCast(C, DestTy);
2473 } else if (auto *LI = dyn_cast<LoadInst>(V)) {
2474 // Explicitly perform load combine to make sure no opposing transform
2475 // can remove the bitcast in the meantime and trigger an infinite loop.
2476 Builder.SetInsertPoint(LI);
2477 NewV = combineLoadToNewType(*LI, DestTy);
2478 // Remove the old load and its use in the old phi, which itself becomes
2479 // dead once the whole transform finishes.
2480 replaceInstUsesWith(*LI, UndefValue::get(LI->getType()));
2481 eraseInstFromFunction(*LI);
2482 } else if (auto *BCI = dyn_cast<BitCastInst>(V)) {
2483 NewV = BCI->getOperand(0);
2484 } else if (auto *PrevPN = dyn_cast<PHINode>(V)) {
2485 NewV = NewPNodes[PrevPN];
2486 }
2487 assert(NewV);
2488 NewPN->addIncoming(NewV, OldPN->getIncomingBlock(j));
2489 }
2490 }
2491
2492 // Traverse all accumulated PHI nodes and process its users,
2493 // which are Stores and BitcCasts. Without this processing
2494 // NewPHI nodes could be replicated and could lead to extra
2495 // moves generated after DeSSA.
2496 // If there is a store with type B, change it to type A.
2497
2498
2499 // Replace users of BitCast B->A with NewPHI. These will help
2500 // later to get rid off a closure formed by OldPHI nodes.
2501 Instruction *RetVal = nullptr;
2502 for (auto *OldPN : OldPhiNodes) {
2503 PHINode *NewPN = NewPNodes[OldPN];
2504 for (User *V : make_early_inc_range(OldPN->users())) {
2505 if (auto *SI = dyn_cast<StoreInst>(V)) {
2506 assert(SI->isSimple() && SI->getOperand(0) == OldPN);
2507 Builder.SetInsertPoint(SI);
2508 auto *NewBC =
2509 cast<BitCastInst>(Builder.CreateBitCast(NewPN, SrcTy));
2510 SI->setOperand(0, NewBC);
2511 Worklist.push(SI);
2512 assert(hasStoreUsersOnly(*NewBC));
2513 }
2514 else if (auto *BCI = dyn_cast<BitCastInst>(V)) {
2515 Type *TyB = BCI->getOperand(0)->getType();
2516 Type *TyA = BCI->getType();
2517 assert(TyA == DestTy && TyB == SrcTy);
2518 (void) TyA;
2519 (void) TyB;
2520 Instruction *I = replaceInstUsesWith(*BCI, NewPN);
2521 if (BCI == &CI)
2522 RetVal = I;
2523 } else if (auto *PHI = dyn_cast<PHINode>(V)) {
2524 assert(OldPhiNodes.contains(PHI));
2525 (void) PHI;
2526 } else {
2527 llvm_unreachable("all uses should be handled");
2528 }
2529 }
2530 }
2531
2532 return RetVal;
2533 }
2534
visitBitCast(BitCastInst & CI)2535 Instruction *InstCombinerImpl::visitBitCast(BitCastInst &CI) {
2536 // If the operands are integer typed then apply the integer transforms,
2537 // otherwise just apply the common ones.
2538 Value *Src = CI.getOperand(0);
2539 Type *SrcTy = Src->getType();
2540 Type *DestTy = CI.getType();
2541
2542 // Get rid of casts from one type to the same type. These are useless and can
2543 // be replaced by the operand.
2544 if (DestTy == Src->getType())
2545 return replaceInstUsesWith(CI, Src);
2546
2547 if (isa<PointerType>(SrcTy) && isa<PointerType>(DestTy)) {
2548 PointerType *SrcPTy = cast<PointerType>(SrcTy);
2549 PointerType *DstPTy = cast<PointerType>(DestTy);
2550 Type *DstElTy = DstPTy->getElementType();
2551 Type *SrcElTy = SrcPTy->getElementType();
2552
2553 // Casting pointers between the same type, but with different address spaces
2554 // is an addrspace cast rather than a bitcast.
2555 if ((DstElTy == SrcElTy) &&
2556 (DstPTy->getAddressSpace() != SrcPTy->getAddressSpace()))
2557 return new AddrSpaceCastInst(Src, DestTy);
2558
2559 // If we are casting a alloca to a pointer to a type of the same
2560 // size, rewrite the allocation instruction to allocate the "right" type.
2561 // There is no need to modify malloc calls because it is their bitcast that
2562 // needs to be cleaned up.
2563 if (AllocaInst *AI = dyn_cast<AllocaInst>(Src))
2564 if (Instruction *V = PromoteCastOfAllocation(CI, *AI))
2565 return V;
2566
2567 // When the type pointed to is not sized the cast cannot be
2568 // turned into a gep.
2569 Type *PointeeType =
2570 cast<PointerType>(Src->getType()->getScalarType())->getElementType();
2571 if (!PointeeType->isSized())
2572 return nullptr;
2573
2574 // If the source and destination are pointers, and this cast is equivalent
2575 // to a getelementptr X, 0, 0, 0... turn it into the appropriate gep.
2576 // This can enhance SROA and other transforms that want type-safe pointers.
2577 unsigned NumZeros = 0;
2578 while (SrcElTy && SrcElTy != DstElTy) {
2579 SrcElTy = GetElementPtrInst::getTypeAtIndex(SrcElTy, (uint64_t)0);
2580 ++NumZeros;
2581 }
2582
2583 // If we found a path from the src to dest, create the getelementptr now.
2584 if (SrcElTy == DstElTy) {
2585 SmallVector<Value *, 8> Idxs(NumZeros + 1, Builder.getInt32(0));
2586 GetElementPtrInst *GEP =
2587 GetElementPtrInst::Create(SrcPTy->getElementType(), Src, Idxs);
2588
2589 // If the source pointer is dereferenceable, then assume it points to an
2590 // allocated object and apply "inbounds" to the GEP.
2591 bool CanBeNull;
2592 if (Src->getPointerDereferenceableBytes(DL, CanBeNull)) {
2593 // In a non-default address space (not 0), a null pointer can not be
2594 // assumed inbounds, so ignore that case (dereferenceable_or_null).
2595 // The reason is that 'null' is not treated differently in these address
2596 // spaces, and we consequently ignore the 'gep inbounds' special case
2597 // for 'null' which allows 'inbounds' on 'null' if the indices are
2598 // zeros.
2599 if (SrcPTy->getAddressSpace() == 0 || !CanBeNull)
2600 GEP->setIsInBounds();
2601 }
2602 return GEP;
2603 }
2604 }
2605
2606 if (FixedVectorType *DestVTy = dyn_cast<FixedVectorType>(DestTy)) {
2607 // Beware: messing with this target-specific oddity may cause trouble.
2608 if (DestVTy->getNumElements() == 1 && SrcTy->isX86_MMXTy()) {
2609 Value *Elem = Builder.CreateBitCast(Src, DestVTy->getElementType());
2610 return InsertElementInst::Create(UndefValue::get(DestTy), Elem,
2611 Constant::getNullValue(Type::getInt32Ty(CI.getContext())));
2612 }
2613
2614 if (isa<IntegerType>(SrcTy)) {
2615 // If this is a cast from an integer to vector, check to see if the input
2616 // is a trunc or zext of a bitcast from vector. If so, we can replace all
2617 // the casts with a shuffle and (potentially) a bitcast.
2618 if (isa<TruncInst>(Src) || isa<ZExtInst>(Src)) {
2619 CastInst *SrcCast = cast<CastInst>(Src);
2620 if (BitCastInst *BCIn = dyn_cast<BitCastInst>(SrcCast->getOperand(0)))
2621 if (isa<VectorType>(BCIn->getOperand(0)->getType()))
2622 if (Instruction *I = optimizeVectorResizeWithIntegerBitCasts(
2623 BCIn->getOperand(0), cast<VectorType>(DestTy), *this))
2624 return I;
2625 }
2626
2627 // If the input is an 'or' instruction, we may be doing shifts and ors to
2628 // assemble the elements of the vector manually. Try to rip the code out
2629 // and replace it with insertelements.
2630 if (Value *V = optimizeIntegerToVectorInsertions(CI, *this))
2631 return replaceInstUsesWith(CI, V);
2632 }
2633 }
2634
2635 if (FixedVectorType *SrcVTy = dyn_cast<FixedVectorType>(SrcTy)) {
2636 if (SrcVTy->getNumElements() == 1) {
2637 // If our destination is not a vector, then make this a straight
2638 // scalar-scalar cast.
2639 if (!DestTy->isVectorTy()) {
2640 Value *Elem =
2641 Builder.CreateExtractElement(Src,
2642 Constant::getNullValue(Type::getInt32Ty(CI.getContext())));
2643 return CastInst::Create(Instruction::BitCast, Elem, DestTy);
2644 }
2645
2646 // Otherwise, see if our source is an insert. If so, then use the scalar
2647 // component directly:
2648 // bitcast (inselt <1 x elt> V, X, 0) to <n x m> --> bitcast X to <n x m>
2649 if (auto *InsElt = dyn_cast<InsertElementInst>(Src))
2650 return new BitCastInst(InsElt->getOperand(1), DestTy);
2651 }
2652 }
2653
2654 if (auto *Shuf = dyn_cast<ShuffleVectorInst>(Src)) {
2655 // Okay, we have (bitcast (shuffle ..)). Check to see if this is
2656 // a bitcast to a vector with the same # elts.
2657 Value *ShufOp0 = Shuf->getOperand(0);
2658 Value *ShufOp1 = Shuf->getOperand(1);
2659 auto ShufElts = cast<VectorType>(Shuf->getType())->getElementCount();
2660 auto SrcVecElts = cast<VectorType>(ShufOp0->getType())->getElementCount();
2661 if (Shuf->hasOneUse() && DestTy->isVectorTy() &&
2662 cast<VectorType>(DestTy)->getElementCount() == ShufElts &&
2663 ShufElts == SrcVecElts) {
2664 BitCastInst *Tmp;
2665 // If either of the operands is a cast from CI.getType(), then
2666 // evaluating the shuffle in the casted destination's type will allow
2667 // us to eliminate at least one cast.
2668 if (((Tmp = dyn_cast<BitCastInst>(ShufOp0)) &&
2669 Tmp->getOperand(0)->getType() == DestTy) ||
2670 ((Tmp = dyn_cast<BitCastInst>(ShufOp1)) &&
2671 Tmp->getOperand(0)->getType() == DestTy)) {
2672 Value *LHS = Builder.CreateBitCast(ShufOp0, DestTy);
2673 Value *RHS = Builder.CreateBitCast(ShufOp1, DestTy);
2674 // Return a new shuffle vector. Use the same element ID's, as we
2675 // know the vector types match #elts.
2676 return new ShuffleVectorInst(LHS, RHS, Shuf->getShuffleMask());
2677 }
2678 }
2679
2680 // A bitcasted-to-scalar and byte-reversing shuffle is better recognized as
2681 // a byte-swap:
2682 // bitcast <N x i8> (shuf X, undef, <N, N-1,...0>) --> bswap (bitcast X)
2683 // TODO: We should match the related pattern for bitreverse.
2684 if (DestTy->isIntegerTy() &&
2685 DL.isLegalInteger(DestTy->getScalarSizeInBits()) &&
2686 SrcTy->getScalarSizeInBits() == 8 &&
2687 ShufElts.getKnownMinValue() % 2 == 0 && Shuf->hasOneUse() &&
2688 Shuf->isReverse()) {
2689 assert(ShufOp0->getType() == SrcTy && "Unexpected shuffle mask");
2690 assert(isa<UndefValue>(ShufOp1) && "Unexpected shuffle op");
2691 Function *Bswap =
2692 Intrinsic::getDeclaration(CI.getModule(), Intrinsic::bswap, DestTy);
2693 Value *ScalarX = Builder.CreateBitCast(ShufOp0, DestTy);
2694 return IntrinsicInst::Create(Bswap, { ScalarX });
2695 }
2696 }
2697
2698 // Handle the A->B->A cast, and there is an intervening PHI node.
2699 if (PHINode *PN = dyn_cast<PHINode>(Src))
2700 if (Instruction *I = optimizeBitCastFromPhi(CI, PN))
2701 return I;
2702
2703 if (Instruction *I = canonicalizeBitCastExtElt(CI, *this))
2704 return I;
2705
2706 if (Instruction *I = foldBitCastBitwiseLogic(CI, Builder))
2707 return I;
2708
2709 if (Instruction *I = foldBitCastSelect(CI, Builder))
2710 return I;
2711
2712 if (SrcTy->isPointerTy())
2713 return commonPointerCastTransforms(CI);
2714 return commonCastTransforms(CI);
2715 }
2716
visitAddrSpaceCast(AddrSpaceCastInst & CI)2717 Instruction *InstCombinerImpl::visitAddrSpaceCast(AddrSpaceCastInst &CI) {
2718 // If the destination pointer element type is not the same as the source's
2719 // first do a bitcast to the destination type, and then the addrspacecast.
2720 // This allows the cast to be exposed to other transforms.
2721 Value *Src = CI.getOperand(0);
2722 PointerType *SrcTy = cast<PointerType>(Src->getType()->getScalarType());
2723 PointerType *DestTy = cast<PointerType>(CI.getType()->getScalarType());
2724
2725 Type *DestElemTy = DestTy->getElementType();
2726 if (SrcTy->getElementType() != DestElemTy) {
2727 Type *MidTy = PointerType::get(DestElemTy, SrcTy->getAddressSpace());
2728 // Handle vectors of pointers.
2729 if (VectorType *VT = dyn_cast<VectorType>(CI.getType()))
2730 MidTy = VectorType::get(MidTy, VT->getElementCount());
2731
2732 Value *NewBitCast = Builder.CreateBitCast(Src, MidTy);
2733 return new AddrSpaceCastInst(NewBitCast, CI.getType());
2734 }
2735
2736 return commonPointerCastTransforms(CI);
2737 }
2738