blob: 298120e1f6965ff05facafaa1e7145457a8e979f [file] [log] [blame]
Chris Lattner2b295a02010-01-04 07:53:58 +00001//===- InstCombineCasts.cpp -----------------------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the visit functions for cast operations.
11//
12//===----------------------------------------------------------------------===//
13
Chandler Carrutha9174582015-01-22 05:25:13 +000014#include "InstCombineInternal.h"
Guozhi Weiae541f62016-10-25 20:43:42 +000015#include "llvm/ADT/SetVector.h"
Eli Friedman911e12f2011-07-20 21:57:23 +000016#include "llvm/Analysis/ConstantFolding.h"
Craig Topperb45eabc2017-04-26 16:39:58 +000017#include "llvm/Analysis/TargetLibraryInfo.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000018#include "llvm/IR/DataLayout.h"
Chandler Carruth820a9082014-03-04 11:08:18 +000019#include "llvm/IR/PatternMatch.h"
Craig Topperb45eabc2017-04-26 16:39:58 +000020#include "llvm/Support/KnownBits.h"
Chris Lattner2b295a02010-01-04 07:53:58 +000021using namespace llvm;
22using namespace PatternMatch;
23
Chandler Carruth964daaa2014-04-22 02:55:47 +000024#define DEBUG_TYPE "instcombine"
25
Sanjay Patel2fbab9d82015-09-09 14:34:26 +000026/// Analyze 'Val', seeing if it is a simple linear expression.
27/// If so, decompose it, returning some value X, such that Val is
Chris Lattner59d95742010-01-04 07:59:07 +000028/// X*Scale+Offset.
29///
Sanjay Patele2834412015-09-09 14:54:29 +000030static Value *decomposeSimpleLinearExpr(Value *Val, unsigned &Scale,
Dan Gohman05a65552010-05-28 04:33:04 +000031 uint64_t &Offset) {
Chris Lattner59d95742010-01-04 07:59:07 +000032 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val)) {
33 Offset = CI->getZExtValue();
34 Scale = 0;
Dan Gohman05a65552010-05-28 04:33:04 +000035 return ConstantInt::get(Val->getType(), 0);
Chris Lattneraaccc8d2010-01-05 20:57:30 +000036 }
Craig Topper3529aa52013-01-24 05:22:40 +000037
Chris Lattneraaccc8d2010-01-05 20:57:30 +000038 if (BinaryOperator *I = dyn_cast<BinaryOperator>(Val)) {
Bob Wilson3c68b622011-07-08 22:09:33 +000039 // Cannot look past anything that might overflow.
40 OverflowingBinaryOperator *OBI = dyn_cast<OverflowingBinaryOperator>(Val);
Stepan Dyatkovskiycb2a1a32012-05-05 07:09:40 +000041 if (OBI && !OBI->hasNoUnsignedWrap() && !OBI->hasNoSignedWrap()) {
Bob Wilson3c68b622011-07-08 22:09:33 +000042 Scale = 1;
43 Offset = 0;
44 return Val;
45 }
46
Chris Lattner59d95742010-01-04 07:59:07 +000047 if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
48 if (I->getOpcode() == Instruction::Shl) {
49 // This is a value scaled by '1 << the shift amt'.
Dan Gohman05a65552010-05-28 04:33:04 +000050 Scale = UINT64_C(1) << RHS->getZExtValue();
Chris Lattner59d95742010-01-04 07:59:07 +000051 Offset = 0;
52 return I->getOperand(0);
Chris Lattneraaccc8d2010-01-05 20:57:30 +000053 }
Craig Topper3529aa52013-01-24 05:22:40 +000054
Chris Lattneraaccc8d2010-01-05 20:57:30 +000055 if (I->getOpcode() == Instruction::Mul) {
Chris Lattner59d95742010-01-04 07:59:07 +000056 // This value is scaled by 'RHS'.
57 Scale = RHS->getZExtValue();
58 Offset = 0;
59 return I->getOperand(0);
Chris Lattneraaccc8d2010-01-05 20:57:30 +000060 }
Craig Topper3529aa52013-01-24 05:22:40 +000061
Chris Lattneraaccc8d2010-01-05 20:57:30 +000062 if (I->getOpcode() == Instruction::Add) {
Craig Topper3529aa52013-01-24 05:22:40 +000063 // We have X+C. Check to see if we really have (X*C2)+C1,
Chris Lattner59d95742010-01-04 07:59:07 +000064 // where C1 is divisible by C2.
65 unsigned SubScale;
Craig Topper3529aa52013-01-24 05:22:40 +000066 Value *SubVal =
Sanjay Patele2834412015-09-09 14:54:29 +000067 decomposeSimpleLinearExpr(I->getOperand(0), SubScale, Offset);
Chris Lattner59d95742010-01-04 07:59:07 +000068 Offset += RHS->getZExtValue();
69 Scale = SubScale;
70 return SubVal;
71 }
72 }
73 }
74
75 // Otherwise, we can't look past this.
76 Scale = 1;
77 Offset = 0;
78 return Val;
79}
80
Sanjay Patel2fbab9d82015-09-09 14:34:26 +000081/// If we find a cast of an allocation instruction, try to eliminate the cast by
82/// moving the type information into the alloc.
Chris Lattner59d95742010-01-04 07:59:07 +000083Instruction *InstCombiner::PromoteCastOfAllocation(BitCastInst &CI,
84 AllocaInst &AI) {
Chris Lattner229907c2011-07-18 04:54:35 +000085 PointerType *PTy = cast<PointerType>(CI.getType());
Craig Topper3529aa52013-01-24 05:22:40 +000086
Craig Topperbb4069e2017-07-07 23:16:26 +000087 BuilderTy AllocaBuilder(Builder);
Duncan P. N. Exon Smith9f8aaf22015-10-13 16:59:33 +000088 AllocaBuilder.SetInsertPoint(&AI);
Chris Lattner59d95742010-01-04 07:59:07 +000089
90 // Get the type really allocated and the type casted to.
Chris Lattner229907c2011-07-18 04:54:35 +000091 Type *AllocElTy = AI.getAllocatedType();
92 Type *CastElTy = PTy->getElementType();
Craig Topperf40110f2014-04-25 05:29:35 +000093 if (!AllocElTy->isSized() || !CastElTy->isSized()) return nullptr;
Chris Lattner59d95742010-01-04 07:59:07 +000094
Mehdi Aminia28d91d2015-03-10 02:37:25 +000095 unsigned AllocElTyAlign = DL.getABITypeAlignment(AllocElTy);
96 unsigned CastElTyAlign = DL.getABITypeAlignment(CastElTy);
Craig Topperf40110f2014-04-25 05:29:35 +000097 if (CastElTyAlign < AllocElTyAlign) return nullptr;
Chris Lattner59d95742010-01-04 07:59:07 +000098
99 // If the allocation has multiple uses, only promote it if we are strictly
100 // increasing the alignment of the resultant allocation. If we keep it the
Devang Patelfbb482b2011-03-08 22:12:11 +0000101 // same, we open the door to infinite loops of various kinds.
Craig Topperf40110f2014-04-25 05:29:35 +0000102 if (!AI.hasOneUse() && CastElTyAlign == AllocElTyAlign) return nullptr;
Chris Lattner59d95742010-01-04 07:59:07 +0000103
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000104 uint64_t AllocElTySize = DL.getTypeAllocSize(AllocElTy);
105 uint64_t CastElTySize = DL.getTypeAllocSize(CastElTy);
Craig Topperf40110f2014-04-25 05:29:35 +0000106 if (CastElTySize == 0 || AllocElTySize == 0) return nullptr;
Chris Lattner59d95742010-01-04 07:59:07 +0000107
Jim Grosbach95d2eb92013-03-06 05:44:53 +0000108 // If the allocation has multiple uses, only promote it if we're not
109 // shrinking the amount of memory being allocated.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000110 uint64_t AllocElTyStoreSize = DL.getTypeStoreSize(AllocElTy);
111 uint64_t CastElTyStoreSize = DL.getTypeStoreSize(CastElTy);
Craig Topperf40110f2014-04-25 05:29:35 +0000112 if (!AI.hasOneUse() && CastElTyStoreSize < AllocElTyStoreSize) return nullptr;
Jim Grosbach95d2eb92013-03-06 05:44:53 +0000113
Chris Lattner59d95742010-01-04 07:59:07 +0000114 // See if we can satisfy the modulus by pulling a scale out of the array
115 // size argument.
116 unsigned ArraySizeScale;
Dan Gohman05a65552010-05-28 04:33:04 +0000117 uint64_t ArrayOffset;
Chris Lattner59d95742010-01-04 07:59:07 +0000118 Value *NumElements = // See if the array size is a decomposable linear expr.
Sanjay Patele2834412015-09-09 14:54:29 +0000119 decomposeSimpleLinearExpr(AI.getOperand(0), ArraySizeScale, ArrayOffset);
Craig Topper3529aa52013-01-24 05:22:40 +0000120
Chris Lattner59d95742010-01-04 07:59:07 +0000121 // If we can now satisfy the modulus, by using a non-1 scale, we really can
122 // do the xform.
123 if ((AllocElTySize*ArraySizeScale) % CastElTySize != 0 ||
Craig Topperf40110f2014-04-25 05:29:35 +0000124 (AllocElTySize*ArrayOffset ) % CastElTySize != 0) return nullptr;
Chris Lattner59d95742010-01-04 07:59:07 +0000125
126 unsigned Scale = (AllocElTySize*ArraySizeScale)/CastElTySize;
Craig Topperf40110f2014-04-25 05:29:35 +0000127 Value *Amt = nullptr;
Chris Lattner59d95742010-01-04 07:59:07 +0000128 if (Scale == 1) {
129 Amt = NumElements;
130 } else {
Dan Gohman05a65552010-05-28 04:33:04 +0000131 Amt = ConstantInt::get(AI.getArraySize()->getType(), Scale);
Chris Lattner59d95742010-01-04 07:59:07 +0000132 // Insert before the alloca, not before the cast.
Benjamin Kramer547b6c52011-09-27 20:39:19 +0000133 Amt = AllocaBuilder.CreateMul(Amt, NumElements);
Chris Lattner59d95742010-01-04 07:59:07 +0000134 }
Craig Topper3529aa52013-01-24 05:22:40 +0000135
Dan Gohman05a65552010-05-28 04:33:04 +0000136 if (uint64_t Offset = (AllocElTySize*ArrayOffset)/CastElTySize) {
137 Value *Off = ConstantInt::get(AI.getArraySize()->getType(),
Chris Lattner59d95742010-01-04 07:59:07 +0000138 Offset, true);
Benjamin Kramer547b6c52011-09-27 20:39:19 +0000139 Amt = AllocaBuilder.CreateAdd(Amt, Off);
Chris Lattner59d95742010-01-04 07:59:07 +0000140 }
Craig Topper3529aa52013-01-24 05:22:40 +0000141
Chris Lattner59d95742010-01-04 07:59:07 +0000142 AllocaInst *New = AllocaBuilder.CreateAlloca(CastElTy, Amt);
143 New->setAlignment(AI.getAlignment());
144 New->takeName(&AI);
Hans Wennborge36e1162014-04-28 17:40:03 +0000145 New->setUsedWithInAlloca(AI.isUsedWithInAlloca());
Craig Topper3529aa52013-01-24 05:22:40 +0000146
Chris Lattner59d95742010-01-04 07:59:07 +0000147 // If the allocation has multiple real uses, insert a cast and change all
148 // things that used it to use the new cast. This will also hack on CI, but it
149 // will die soon.
Devang Patelfbb482b2011-03-08 22:12:11 +0000150 if (!AI.hasOneUse()) {
Chris Lattner59d95742010-01-04 07:59:07 +0000151 // New is the allocation instruction, pointer typed. AI is the original
152 // allocation instruction, also pointer typed. Thus, cast to use is BitCast.
153 Value *NewCast = AllocaBuilder.CreateBitCast(New, AI.getType(), "tmpcast");
Sanjay Patel4b198802016-02-01 22:23:39 +0000154 replaceInstUsesWith(AI, NewCast);
Chris Lattner59d95742010-01-04 07:59:07 +0000155 }
Sanjay Patel4b198802016-02-01 22:23:39 +0000156 return replaceInstUsesWith(CI, New);
Chris Lattner59d95742010-01-04 07:59:07 +0000157}
158
Sanjay Patel2fbab9d82015-09-09 14:34:26 +0000159/// Given an expression that CanEvaluateTruncated or CanEvaluateSExtd returns
160/// true for, actually insert the code to evaluate the expression.
Craig Topper3529aa52013-01-24 05:22:40 +0000161Value *InstCombiner::EvaluateInDifferentType(Value *V, Type *Ty,
Chris Lattner92be2ad2010-01-04 07:54:59 +0000162 bool isSigned) {
Chris Lattner9242ae02010-01-08 19:28:47 +0000163 if (Constant *C = dyn_cast<Constant>(V)) {
164 C = ConstantExpr::getIntegerCast(C, Ty, isSigned /*Sext or ZExt*/);
Rafael Espindola37dc9e12014-02-21 00:06:31 +0000165 // If we got a constantexpr back, try to simplify it with DL info.
Justin Bogner99798402016-08-05 01:06:44 +0000166 if (Constant *FoldedC = ConstantFoldConstant(C, DL, &TLI))
David Majnemerd536f232016-07-29 03:27:26 +0000167 C = FoldedC;
Chris Lattner9242ae02010-01-08 19:28:47 +0000168 return C;
169 }
Chris Lattner92be2ad2010-01-04 07:54:59 +0000170
171 // Otherwise, it must be an instruction.
172 Instruction *I = cast<Instruction>(V);
Craig Topperf40110f2014-04-25 05:29:35 +0000173 Instruction *Res = nullptr;
Chris Lattner92be2ad2010-01-04 07:54:59 +0000174 unsigned Opc = I->getOpcode();
175 switch (Opc) {
176 case Instruction::Add:
177 case Instruction::Sub:
178 case Instruction::Mul:
179 case Instruction::And:
180 case Instruction::Or:
181 case Instruction::Xor:
182 case Instruction::AShr:
183 case Instruction::LShr:
184 case Instruction::Shl:
185 case Instruction::UDiv:
186 case Instruction::URem: {
187 Value *LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
188 Value *RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
189 Res = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
190 break;
Craig Topper3529aa52013-01-24 05:22:40 +0000191 }
Chris Lattner92be2ad2010-01-04 07:54:59 +0000192 case Instruction::Trunc:
193 case Instruction::ZExt:
194 case Instruction::SExt:
195 // If the source type of the cast is the type we're trying for then we can
196 // just return the source. There's no need to insert it because it is not
197 // new.
198 if (I->getOperand(0)->getType() == Ty)
199 return I->getOperand(0);
Craig Topper3529aa52013-01-24 05:22:40 +0000200
Chris Lattner92be2ad2010-01-04 07:54:59 +0000201 // Otherwise, must be the same type of cast, so just reinsert a new one.
Chris Lattner39d2daa2010-01-10 20:25:54 +0000202 // This also handles the case of zext(trunc(x)) -> zext(x).
203 Res = CastInst::CreateIntegerCast(I->getOperand(0), Ty,
204 Opc == Instruction::SExt);
Chris Lattner92be2ad2010-01-04 07:54:59 +0000205 break;
206 case Instruction::Select: {
207 Value *True = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
208 Value *False = EvaluateInDifferentType(I->getOperand(2), Ty, isSigned);
209 Res = SelectInst::Create(I->getOperand(0), True, False);
210 break;
211 }
212 case Instruction::PHI: {
213 PHINode *OPN = cast<PHINode>(I);
Jay Foad52131342011-03-30 11:28:46 +0000214 PHINode *NPN = PHINode::Create(Ty, OPN->getNumIncomingValues());
Chris Lattner92be2ad2010-01-04 07:54:59 +0000215 for (unsigned i = 0, e = OPN->getNumIncomingValues(); i != e; ++i) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000216 Value *V =
217 EvaluateInDifferentType(OPN->getIncomingValue(i), Ty, isSigned);
Chris Lattner92be2ad2010-01-04 07:54:59 +0000218 NPN->addIncoming(V, OPN->getIncomingBlock(i));
219 }
220 Res = NPN;
221 break;
222 }
Craig Topper3529aa52013-01-24 05:22:40 +0000223 default:
Chris Lattner92be2ad2010-01-04 07:54:59 +0000224 // TODO: Can handle more cases here.
225 llvm_unreachable("Unreachable!");
Chris Lattner92be2ad2010-01-04 07:54:59 +0000226 }
Craig Topper3529aa52013-01-24 05:22:40 +0000227
Chris Lattner92be2ad2010-01-04 07:54:59 +0000228 Res->takeName(I);
Eli Friedman35211c62011-05-27 00:19:40 +0000229 return InsertNewInstWith(Res, *I);
Chris Lattner92be2ad2010-01-04 07:54:59 +0000230}
Chris Lattner2b295a02010-01-04 07:53:58 +0000231
Tobias Grosser8ef834c2016-07-19 09:06:08 +0000232Instruction::CastOps InstCombiner::isEliminableCastPair(const CastInst *CI1,
233 const CastInst *CI2) {
234 Type *SrcTy = CI1->getSrcTy();
235 Type *MidTy = CI1->getDestTy();
236 Type *DstTy = CI2->getDestTy();
Chris Lattner2b295a02010-01-04 07:53:58 +0000237
Craig Toppera86ca082017-08-04 05:12:35 +0000238 Instruction::CastOps firstOp = CI1->getOpcode();
239 Instruction::CastOps secondOp = CI2->getOpcode();
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000240 Type *SrcIntPtrTy =
241 SrcTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(SrcTy) : nullptr;
242 Type *MidIntPtrTy =
243 MidTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(MidTy) : nullptr;
244 Type *DstIntPtrTy =
245 DstTy->isPtrOrPtrVectorTy() ? DL.getIntPtrType(DstTy) : nullptr;
Chris Lattner2b295a02010-01-04 07:53:58 +0000246 unsigned Res = CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy,
Duncan Sandse2395dc2012-10-30 16:03:32 +0000247 DstTy, SrcIntPtrTy, MidIntPtrTy,
248 DstIntPtrTy);
Micah Villmow12d91272012-10-24 15:52:52 +0000249
Chris Lattner2b295a02010-01-04 07:53:58 +0000250 // We don't want to form an inttoptr or ptrtoint that converts to an integer
251 // type that differs from the pointer size.
Duncan Sandse2395dc2012-10-30 16:03:32 +0000252 if ((Res == Instruction::IntToPtr && SrcTy != DstIntPtrTy) ||
253 (Res == Instruction::PtrToInt && DstTy != SrcIntPtrTy))
Chris Lattner2b295a02010-01-04 07:53:58 +0000254 Res = 0;
Craig Topper3529aa52013-01-24 05:22:40 +0000255
Chris Lattner2b295a02010-01-04 07:53:58 +0000256 return Instruction::CastOps(Res);
257}
258
Chris Lattner2b295a02010-01-04 07:53:58 +0000259/// @brief Implement the transforms common to all CastInst visitors.
260Instruction *InstCombiner::commonCastTransforms(CastInst &CI) {
261 Value *Src = CI.getOperand(0);
262
Sanjay Patel8d7196b2016-10-26 14:52:35 +0000263 // Try to eliminate a cast of a cast.
264 if (auto *CSrc = dyn_cast<CastInst>(Src)) { // A->B->C cast
265 if (Instruction::CastOps NewOpc = isEliminableCastPair(CSrc, &CI)) {
Chris Lattner2b295a02010-01-04 07:53:58 +0000266 // The first cast (CSrc) is eliminable so we need to fix up or replace
267 // the second cast (CI). CSrc will then have a good chance of being dead.
Sanjay Patel8d7196b2016-10-26 14:52:35 +0000268 return CastInst::Create(NewOpc, CSrc->getOperand(0), CI.getType());
Chris Lattner2b295a02010-01-04 07:53:58 +0000269 }
270 }
271
Sanjay Patel8d7196b2016-10-26 14:52:35 +0000272 // If we are casting a select, then fold the cast into the select.
273 if (auto *SI = dyn_cast<SelectInst>(Src))
Chris Lattner2b295a02010-01-04 07:53:58 +0000274 if (Instruction *NV = FoldOpIntoSelect(CI, SI))
275 return NV;
276
Sanjay Patel8d7196b2016-10-26 14:52:35 +0000277 // If we are casting a PHI, then fold the cast into the PHI.
Craig Topperfb71b7d2017-04-14 19:20:12 +0000278 if (auto *PN = dyn_cast<PHINode>(Src)) {
Sanjay Patel8d7196b2016-10-26 14:52:35 +0000279 // Don't do this if it would create a PHI node with an illegal type from a
280 // legal type.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000281 if (!Src->getType()->isIntegerTy() || !CI.getType()->isIntegerTy() ||
Sanjay Patel2217f752017-01-31 17:25:42 +0000282 shouldChangeType(CI.getType(), Src->getType()))
Craig Topperfb71b7d2017-04-14 19:20:12 +0000283 if (Instruction *NV = foldOpIntoPhi(CI, PN))
Chris Lattner2b295a02010-01-04 07:53:58 +0000284 return NV;
285 }
Craig Topper3529aa52013-01-24 05:22:40 +0000286
Craig Topperf40110f2014-04-25 05:29:35 +0000287 return nullptr;
Chris Lattner2b295a02010-01-04 07:53:58 +0000288}
289
Sanjay Patel2fbab9d82015-09-09 14:34:26 +0000290/// Return true if we can evaluate the specified expression tree as type Ty
291/// instead of its larger type, and arrive with the same value.
292/// This is used by code that tries to eliminate truncates.
Chris Lattnerc3aca382010-01-10 00:58:42 +0000293///
294/// Ty will always be a type smaller than V. We should return true if trunc(V)
295/// can be computed by computing V in the smaller type. If V is an instruction,
296/// then trunc(inst(x,y)) can be computed as inst(trunc(x),trunc(y)), which only
297/// makes sense if x and y can be efficiently truncated.
298///
Chris Lattner172630a2010-01-11 02:43:35 +0000299/// This function works on both vectors and scalars.
300///
Sanjay Patele2834412015-09-09 14:54:29 +0000301static bool canEvaluateTruncated(Value *V, Type *Ty, InstCombiner &IC,
Hal Finkel60db0582014-09-07 18:57:58 +0000302 Instruction *CxtI) {
Chris Lattnerc3aca382010-01-10 00:58:42 +0000303 // We can always evaluate constants in another type.
304 if (isa<Constant>(V))
305 return true;
Craig Topper3529aa52013-01-24 05:22:40 +0000306
Chris Lattnerc3aca382010-01-10 00:58:42 +0000307 Instruction *I = dyn_cast<Instruction>(V);
308 if (!I) return false;
Craig Topper3529aa52013-01-24 05:22:40 +0000309
Chris Lattner229907c2011-07-18 04:54:35 +0000310 Type *OrigTy = V->getType();
Craig Topper3529aa52013-01-24 05:22:40 +0000311
Chris Lattnera6b13562010-01-11 22:45:25 +0000312 // If this is an extension from the dest type, we can eliminate it, even if it
313 // has multiple uses.
Craig Topper3529aa52013-01-24 05:22:40 +0000314 if ((isa<ZExtInst>(I) || isa<SExtInst>(I)) &&
Chris Lattnerc3aca382010-01-10 00:58:42 +0000315 I->getOperand(0)->getType() == Ty)
316 return true;
317
318 // We can't extend or shrink something that has multiple uses: doing so would
319 // require duplicating the instruction in general, which isn't profitable.
320 if (!I->hasOneUse()) return false;
321
322 unsigned Opc = I->getOpcode();
323 switch (Opc) {
324 case Instruction::Add:
325 case Instruction::Sub:
326 case Instruction::Mul:
327 case Instruction::And:
328 case Instruction::Or:
329 case Instruction::Xor:
330 // These operators can all arbitrarily be extended or truncated.
Sanjay Patele2834412015-09-09 14:54:29 +0000331 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
332 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
Chris Lattnerc3aca382010-01-10 00:58:42 +0000333
334 case Instruction::UDiv:
335 case Instruction::URem: {
336 // UDiv and URem can be truncated if all the truncated bits are zero.
337 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
338 uint32_t BitWidth = Ty->getScalarSizeInBits();
339 if (BitWidth < OrigBitWidth) {
340 APInt Mask = APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth);
Hal Finkel60db0582014-09-07 18:57:58 +0000341 if (IC.MaskedValueIsZero(I->getOperand(0), Mask, 0, CxtI) &&
342 IC.MaskedValueIsZero(I->getOperand(1), Mask, 0, CxtI)) {
Sanjay Patele2834412015-09-09 14:54:29 +0000343 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI) &&
344 canEvaluateTruncated(I->getOperand(1), Ty, IC, CxtI);
Chris Lattnerc3aca382010-01-10 00:58:42 +0000345 }
346 }
347 break;
348 }
Craig Topper0a1a2762017-08-15 22:48:41 +0000349 case Instruction::Shl: {
Chris Lattnerc3aca382010-01-10 00:58:42 +0000350 // If we are truncating the result of this SHL, and if it's a shift of a
351 // constant amount, we can always perform a SHL in a smaller type.
Craig Topper0a1a2762017-08-15 22:48:41 +0000352 const APInt *Amt;
353 if (match(I->getOperand(1), m_APInt(Amt))) {
Chris Lattnerc3aca382010-01-10 00:58:42 +0000354 uint32_t BitWidth = Ty->getScalarSizeInBits();
Craig Topper0a1a2762017-08-15 22:48:41 +0000355 if (Amt->getLimitedValue(BitWidth) < BitWidth)
Sanjay Patele2834412015-09-09 14:54:29 +0000356 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI);
Chris Lattnerc3aca382010-01-10 00:58:42 +0000357 }
358 break;
Craig Topper0a1a2762017-08-15 22:48:41 +0000359 }
360 case Instruction::LShr: {
Chris Lattnerc3aca382010-01-10 00:58:42 +0000361 // If this is a truncate of a logical shr, we can truncate it to a smaller
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +0000362 // lshr iff we know that the bits we would otherwise be shifting in are
Chris Lattnerc3aca382010-01-10 00:58:42 +0000363 // already zeros.
Craig Topper0a1a2762017-08-15 22:48:41 +0000364 const APInt *Amt;
365 if (match(I->getOperand(1), m_APInt(Amt))) {
Chris Lattnerc3aca382010-01-10 00:58:42 +0000366 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
367 uint32_t BitWidth = Ty->getScalarSizeInBits();
Hal Finkel60db0582014-09-07 18:57:58 +0000368 if (IC.MaskedValueIsZero(I->getOperand(0),
369 APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth), 0, CxtI) &&
Craig Topper0a1a2762017-08-15 22:48:41 +0000370 Amt->getLimitedValue(BitWidth) < BitWidth) {
Sanjay Patele2834412015-09-09 14:54:29 +0000371 return canEvaluateTruncated(I->getOperand(0), Ty, IC, CxtI);
Chris Lattnerc3aca382010-01-10 00:58:42 +0000372 }
373 }
374 break;
Craig Topper0a1a2762017-08-15 22:48:41 +0000375 }
Chris Lattnerc3aca382010-01-10 00:58:42 +0000376 case Instruction::Trunc:
377 // trunc(trunc(x)) -> trunc(x)
378 return true;
Chris Lattner73984342010-08-27 20:32:06 +0000379 case Instruction::ZExt:
380 case Instruction::SExt:
381 // trunc(ext(x)) -> ext(x) if the source type is smaller than the new dest
382 // trunc(ext(x)) -> trunc(x) if the source type is larger than the new dest
383 return true;
Chris Lattnerc3aca382010-01-10 00:58:42 +0000384 case Instruction::Select: {
385 SelectInst *SI = cast<SelectInst>(I);
Sanjay Patele2834412015-09-09 14:54:29 +0000386 return canEvaluateTruncated(SI->getTrueValue(), Ty, IC, CxtI) &&
387 canEvaluateTruncated(SI->getFalseValue(), Ty, IC, CxtI);
Chris Lattnerc3aca382010-01-10 00:58:42 +0000388 }
389 case Instruction::PHI: {
390 // We can change a phi if we can change all operands. Note that we never
391 // get into trouble with cyclic PHIs here because we only consider
392 // instructions with a single use.
393 PHINode *PN = cast<PHINode>(I);
Pete Cooper833f34d2015-05-12 20:05:31 +0000394 for (Value *IncValue : PN->incoming_values())
Sanjay Patele2834412015-09-09 14:54:29 +0000395 if (!canEvaluateTruncated(IncValue, Ty, IC, CxtI))
Chris Lattnerc3aca382010-01-10 00:58:42 +0000396 return false;
397 return true;
398 }
399 default:
400 // TODO: Can handle more cases here.
401 break;
402 }
Craig Topper3529aa52013-01-24 05:22:40 +0000403
Chris Lattnerc3aca382010-01-10 00:58:42 +0000404 return false;
405}
406
Sanjay Patelf727e382015-12-14 16:16:54 +0000407/// Given a vector that is bitcast to an integer, optionally logically
408/// right-shifted, and truncated, convert it to an extractelement.
409/// Example (big endian):
410/// trunc (lshr (bitcast <4 x i32> %X to i128), 32) to i32
411/// --->
412/// extractelement <4 x i32> %X, 1
Craig Toppercb220392017-07-06 23:18:43 +0000413static Instruction *foldVecTruncToExtElt(TruncInst &Trunc, InstCombiner &IC) {
Sanjay Patelf727e382015-12-14 16:16:54 +0000414 Value *TruncOp = Trunc.getOperand(0);
415 Type *DestType = Trunc.getType();
416 if (!TruncOp->hasOneUse() || !isa<IntegerType>(DestType))
417 return nullptr;
418
419 Value *VecInput = nullptr;
420 ConstantInt *ShiftVal = nullptr;
421 if (!match(TruncOp, m_CombineOr(m_BitCast(m_Value(VecInput)),
422 m_LShr(m_BitCast(m_Value(VecInput)),
423 m_ConstantInt(ShiftVal)))) ||
424 !isa<VectorType>(VecInput->getType()))
425 return nullptr;
426
427 VectorType *VecType = cast<VectorType>(VecInput->getType());
428 unsigned VecWidth = VecType->getPrimitiveSizeInBits();
429 unsigned DestWidth = DestType->getPrimitiveSizeInBits();
430 unsigned ShiftAmount = ShiftVal ? ShiftVal->getZExtValue() : 0;
431
432 if ((VecWidth % DestWidth != 0) || (ShiftAmount % DestWidth != 0))
433 return nullptr;
434
435 // If the element type of the vector doesn't match the result type,
436 // bitcast it to a vector type that we can extract from.
437 unsigned NumVecElts = VecWidth / DestWidth;
438 if (VecType->getElementType() != DestType) {
439 VecType = VectorType::get(DestType, NumVecElts);
Craig Topperbb4069e2017-07-07 23:16:26 +0000440 VecInput = IC.Builder.CreateBitCast(VecInput, VecType, "bc");
Sanjay Patelf727e382015-12-14 16:16:54 +0000441 }
442
443 unsigned Elt = ShiftAmount / DestWidth;
Craig Toppercb220392017-07-06 23:18:43 +0000444 if (IC.getDataLayout().isBigEndian())
Sanjay Patelf727e382015-12-14 16:16:54 +0000445 Elt = NumVecElts - 1 - Elt;
446
Craig Topperbb4069e2017-07-07 23:16:26 +0000447 return ExtractElementInst::Create(VecInput, IC.Builder.getInt32(Elt));
Sanjay Patelf727e382015-12-14 16:16:54 +0000448}
449
Sanjay Patelc50e55d2017-08-09 18:37:41 +0000450/// Rotate left/right may occur in a wider type than necessary because of type
451/// promotion rules. Try to narrow all of the component instructions.
452Instruction *InstCombiner::narrowRotate(TruncInst &Trunc) {
453 assert((isa<VectorType>(Trunc.getSrcTy()) ||
454 shouldChangeType(Trunc.getSrcTy(), Trunc.getType())) &&
455 "Don't narrow to an illegal scalar type");
456
457 // First, find an or'd pair of opposite shifts with the same shifted operand:
458 // trunc (or (lshr ShVal, ShAmt0), (shl ShVal, ShAmt1))
459 Value *Or0, *Or1;
460 if (!match(Trunc.getOperand(0), m_OneUse(m_Or(m_Value(Or0), m_Value(Or1)))))
461 return nullptr;
462
463 Value *ShVal, *ShAmt0, *ShAmt1;
464 if (!match(Or0, m_OneUse(m_LogicalShift(m_Value(ShVal), m_Value(ShAmt0)))) ||
465 !match(Or1, m_OneUse(m_LogicalShift(m_Specific(ShVal), m_Value(ShAmt1)))))
466 return nullptr;
467
468 auto ShiftOpcode0 = cast<BinaryOperator>(Or0)->getOpcode();
469 auto ShiftOpcode1 = cast<BinaryOperator>(Or1)->getOpcode();
470 if (ShiftOpcode0 == ShiftOpcode1)
471 return nullptr;
472
473 // The shift amounts must add up to the narrow bit width.
474 Value *ShAmt;
475 bool SubIsOnLHS;
476 Type *DestTy = Trunc.getType();
477 unsigned NarrowWidth = DestTy->getScalarSizeInBits();
478 if (match(ShAmt0,
479 m_OneUse(m_Sub(m_SpecificInt(NarrowWidth), m_Specific(ShAmt1))))) {
480 ShAmt = ShAmt1;
481 SubIsOnLHS = true;
482 } else if (match(ShAmt1, m_OneUse(m_Sub(m_SpecificInt(NarrowWidth),
483 m_Specific(ShAmt0))))) {
484 ShAmt = ShAmt0;
485 SubIsOnLHS = false;
486 } else {
487 return nullptr;
488 }
489
490 // The shifted value must have high zeros in the wide type. Typically, this
491 // will be a zext, but it could also be the result of an 'and' or 'shift'.
492 unsigned WideWidth = Trunc.getSrcTy()->getScalarSizeInBits();
493 APInt HiBitMask = APInt::getHighBitsSet(WideWidth, WideWidth - NarrowWidth);
494 if (!MaskedValueIsZero(ShVal, HiBitMask, 0, &Trunc))
495 return nullptr;
496
497 // We have an unnecessarily wide rotate!
498 // trunc (or (lshr ShVal, ShAmt), (shl ShVal, BitWidth - ShAmt))
499 // Narrow it down to eliminate the zext/trunc:
500 // or (lshr trunc(ShVal), ShAmt0'), (shl trunc(ShVal), ShAmt1')
501 Value *NarrowShAmt = Builder.CreateTrunc(ShAmt, DestTy);
502 Value *NegShAmt = Builder.CreateNeg(NarrowShAmt);
503
504 // Mask both shift amounts to ensure there's no UB from oversized shifts.
505 Constant *MaskC = ConstantInt::get(DestTy, NarrowWidth - 1);
506 Value *MaskedShAmt = Builder.CreateAnd(NarrowShAmt, MaskC);
507 Value *MaskedNegShAmt = Builder.CreateAnd(NegShAmt, MaskC);
508
509 // Truncate the original value and use narrow ops.
510 Value *X = Builder.CreateTrunc(ShVal, DestTy);
511 Value *NarrowShAmt0 = SubIsOnLHS ? MaskedNegShAmt : MaskedShAmt;
512 Value *NarrowShAmt1 = SubIsOnLHS ? MaskedShAmt : MaskedNegShAmt;
513 Value *NarrowSh0 = Builder.CreateBinOp(ShiftOpcode0, X, NarrowShAmt0);
514 Value *NarrowSh1 = Builder.CreateBinOp(ShiftOpcode1, X, NarrowShAmt1);
515 return BinaryOperator::CreateOr(NarrowSh0, NarrowSh1);
516}
517
Sanjay Patel94da1de2017-08-05 15:19:18 +0000518/// Try to narrow the width of math or bitwise logic instructions by pulling a
519/// truncate ahead of binary operators.
520/// TODO: Transforms for truncated shifts should be moved into here.
521Instruction *InstCombiner::narrowBinOp(TruncInst &Trunc) {
Sanjay Patelaa8b28e2016-11-30 20:48:54 +0000522 Type *SrcTy = Trunc.getSrcTy();
523 Type *DestTy = Trunc.getType();
Sanjay Patelc50e55d2017-08-09 18:37:41 +0000524 if (!isa<VectorType>(SrcTy) && !shouldChangeType(SrcTy, DestTy))
Sanjay Patelaa8b28e2016-11-30 20:48:54 +0000525 return nullptr;
526
Sanjay Patel94da1de2017-08-05 15:19:18 +0000527 BinaryOperator *BinOp;
528 if (!match(Trunc.getOperand(0), m_OneUse(m_BinOp(BinOp))))
Sanjay Patelaa8b28e2016-11-30 20:48:54 +0000529 return nullptr;
530
Sanjay Patel94da1de2017-08-05 15:19:18 +0000531 switch (BinOp->getOpcode()) {
532 case Instruction::And:
533 case Instruction::Or:
534 case Instruction::Xor:
535 case Instruction::Add:
536 case Instruction::Mul: {
537 Constant *C;
538 if (match(BinOp->getOperand(1), m_Constant(C))) {
539 // trunc (binop X, C) --> binop (trunc X, C')
540 Constant *NarrowC = ConstantExpr::getTrunc(C, DestTy);
541 Value *TruncX = Builder.CreateTrunc(BinOp->getOperand(0), DestTy);
542 return BinaryOperator::Create(BinOp->getOpcode(), TruncX, NarrowC);
543 }
544 break;
545 }
546 case Instruction::Sub: {
547 Constant *C;
548 if (match(BinOp->getOperand(0), m_Constant(C))) {
549 // trunc (binop C, X) --> binop (trunc C', X)
550 Constant *NarrowC = ConstantExpr::getTrunc(C, DestTy);
551 Value *TruncX = Builder.CreateTrunc(BinOp->getOperand(1), DestTy);
552 return BinaryOperator::Create(BinOp->getOpcode(), NarrowC, TruncX);
553 }
554 break;
555 }
556
557 default: break;
558 }
559
Sanjay Patelc50e55d2017-08-09 18:37:41 +0000560 if (Instruction *NarrowOr = narrowRotate(Trunc))
561 return NarrowOr;
562
Sanjay Patel94da1de2017-08-05 15:19:18 +0000563 return nullptr;
Sanjay Patelaa8b28e2016-11-30 20:48:54 +0000564}
565
Sanjay Patel53fa17a2017-03-07 21:45:16 +0000566/// Try to narrow the width of a splat shuffle. This could be generalized to any
567/// shuffle with a constant operand, but we limit the transform to avoid
568/// creating a shuffle type that targets may not be able to lower effectively.
569static Instruction *shrinkSplatShuffle(TruncInst &Trunc,
570 InstCombiner::BuilderTy &Builder) {
571 auto *Shuf = dyn_cast<ShuffleVectorInst>(Trunc.getOperand(0));
572 if (Shuf && Shuf->hasOneUse() && isa<UndefValue>(Shuf->getOperand(1)) &&
Sanjay Patel62906af2017-03-08 15:02:23 +0000573 Shuf->getMask()->getSplatValue() &&
574 Shuf->getType() == Shuf->getOperand(0)->getType()) {
Sanjay Patel53fa17a2017-03-07 21:45:16 +0000575 // trunc (shuf X, Undef, SplatMask) --> shuf (trunc X), Undef, SplatMask
576 Constant *NarrowUndef = UndefValue::get(Trunc.getType());
577 Value *NarrowOp = Builder.CreateTrunc(Shuf->getOperand(0), Trunc.getType());
578 return new ShuffleVectorInst(NarrowOp, NarrowUndef, Shuf->getMask());
579 }
580
581 return nullptr;
582}
583
Sanjay Patelfe970512017-03-07 23:27:14 +0000584/// Try to narrow the width of an insert element. This could be generalized for
585/// any vector constant, but we limit the transform to insertion into undef to
586/// avoid potential backend problems from unsupported insertion widths. This
587/// could also be extended to handle the case of inserting a scalar constant
588/// into a vector variable.
589static Instruction *shrinkInsertElt(CastInst &Trunc,
590 InstCombiner::BuilderTy &Builder) {
591 Instruction::CastOps Opcode = Trunc.getOpcode();
592 assert((Opcode == Instruction::Trunc || Opcode == Instruction::FPTrunc) &&
593 "Unexpected instruction for shrinking");
594
595 auto *InsElt = dyn_cast<InsertElementInst>(Trunc.getOperand(0));
596 if (!InsElt || !InsElt->hasOneUse())
597 return nullptr;
598
599 Type *DestTy = Trunc.getType();
600 Type *DestScalarTy = DestTy->getScalarType();
601 Value *VecOp = InsElt->getOperand(0);
602 Value *ScalarOp = InsElt->getOperand(1);
603 Value *Index = InsElt->getOperand(2);
604
605 if (isa<UndefValue>(VecOp)) {
606 // trunc (inselt undef, X, Index) --> inselt undef, (trunc X), Index
607 // fptrunc (inselt undef, X, Index) --> inselt undef, (fptrunc X), Index
608 UndefValue *NarrowUndef = UndefValue::get(DestTy);
609 Value *NarrowOp = Builder.CreateCast(Opcode, ScalarOp, DestScalarTy);
610 return InsertElementInst::Create(NarrowUndef, NarrowOp, Index);
611 }
612
613 return nullptr;
614}
615
Chris Lattnerc3aca382010-01-10 00:58:42 +0000616Instruction *InstCombiner::visitTrunc(TruncInst &CI) {
Chris Lattner883550a2010-01-10 01:00:46 +0000617 if (Instruction *Result = commonCastTransforms(CI))
Chris Lattnerc3aca382010-01-10 00:58:42 +0000618 return Result;
Craig Topper3529aa52013-01-24 05:22:40 +0000619
James Molloy2b21a7c2015-05-20 18:41:25 +0000620 // Test if the trunc is the user of a select which is part of a
621 // minimum or maximum operation. If so, don't do any more simplification.
Justin Bognerc7e4fbe2016-08-05 01:09:48 +0000622 // Even simplifying demanded bits can break the canonical form of a
James Molloy2b21a7c2015-05-20 18:41:25 +0000623 // min/max.
624 Value *LHS, *RHS;
625 if (SelectInst *SI = dyn_cast<SelectInst>(CI.getOperand(0)))
James Molloy134bec22015-08-11 09:12:57 +0000626 if (matchSelectPattern(SI, LHS, RHS).Flavor != SPF_UNKNOWN)
James Molloy2b21a7c2015-05-20 18:41:25 +0000627 return nullptr;
Justin Bognerc7e4fbe2016-08-05 01:09:48 +0000628
Craig Topper3529aa52013-01-24 05:22:40 +0000629 // See if we can simplify any instructions used by the input whose sole
Chris Lattner883550a2010-01-10 01:00:46 +0000630 // purpose is to compute bits we don't care about.
631 if (SimplifyDemandedInstructionBits(CI))
632 return &CI;
Craig Topper3529aa52013-01-24 05:22:40 +0000633
Chris Lattnerc3aca382010-01-10 00:58:42 +0000634 Value *Src = CI.getOperand(0);
Chris Lattner229907c2011-07-18 04:54:35 +0000635 Type *DestTy = CI.getType(), *SrcTy = Src->getType();
Craig Topper3529aa52013-01-24 05:22:40 +0000636
Chris Lattnerc3aca382010-01-10 00:58:42 +0000637 // Attempt to truncate the entire input expression tree to the destination
638 // type. Only do this if the dest type is a simple type, don't convert the
Chris Lattner2b295a02010-01-04 07:53:58 +0000639 // expression tree to something weird like i93 unless the source is also
640 // strange.
Sanjay Patel2217f752017-01-31 17:25:42 +0000641 if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) &&
Sanjay Patele2834412015-09-09 14:54:29 +0000642 canEvaluateTruncated(Src, DestTy, *this, &CI)) {
Craig Topper3529aa52013-01-24 05:22:40 +0000643
Chris Lattner2b295a02010-01-04 07:53:58 +0000644 // If this cast is a truncate, evaluting in a different type always
Chris Lattner8600dd32010-01-05 23:00:30 +0000645 // eliminates the cast, so it is always a win.
Chris Lattner3057c372010-01-07 23:41:00 +0000646 DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
Dan Gohmana4abd032010-05-25 21:50:35 +0000647 " to avoid cast: " << CI << '\n');
Chris Lattner3057c372010-01-07 23:41:00 +0000648 Value *Res = EvaluateInDifferentType(Src, DestTy, false);
649 assert(Res->getType() == DestTy);
Sanjay Patel4b198802016-02-01 22:23:39 +0000650 return replaceInstUsesWith(CI, Res);
Chris Lattner3057c372010-01-07 23:41:00 +0000651 }
Chris Lattner2b295a02010-01-04 07:53:58 +0000652
Chris Lattnera93c63c2010-01-05 22:21:18 +0000653 // Canonicalize trunc x to i1 -> (icmp ne (and x, 1), 0), likewise for vector.
654 if (DestTy->getScalarSizeInBits() == 1) {
Sanjay Patelf09d1bf2015-11-17 18:37:23 +0000655 Constant *One = ConstantInt::get(SrcTy, 1);
Craig Topperbb4069e2017-07-07 23:16:26 +0000656 Src = Builder.CreateAnd(Src, One);
Chris Lattner2b295a02010-01-04 07:53:58 +0000657 Value *Zero = Constant::getNullValue(Src->getType());
658 return new ICmpInst(ICmpInst::ICMP_NE, Src, Zero);
659 }
Craig Topper3529aa52013-01-24 05:22:40 +0000660
Sanjay Patel6844e212017-05-09 16:24:59 +0000661 // FIXME: Maybe combine the next two transforms to handle the no cast case
662 // more efficiently. Support vector types. Cleanup code by using m_OneUse.
663
Chris Lattner90cd7462010-08-27 18:31:05 +0000664 // Transform trunc(lshr (zext A), Cst) to eliminate one type conversion.
Craig Topperf40110f2014-04-25 05:29:35 +0000665 Value *A = nullptr; ConstantInt *Cst = nullptr;
Chris Lattner9c10d582011-01-15 06:32:33 +0000666 if (Src->hasOneUse() &&
667 match(Src, m_LShr(m_ZExt(m_Value(A)), m_ConstantInt(Cst)))) {
Chris Lattner90cd7462010-08-27 18:31:05 +0000668 // We have three types to worry about here, the type of A, the source of
669 // the truncate (MidSize), and the destination of the truncate. We know that
670 // ASize < MidSize and MidSize > ResultSize, but don't know the relation
671 // between ASize and ResultSize.
672 unsigned ASize = A->getType()->getPrimitiveSizeInBits();
Craig Topper3529aa52013-01-24 05:22:40 +0000673
Chris Lattner90cd7462010-08-27 18:31:05 +0000674 // If the shift amount is larger than the size of A, then the result is
675 // known to be zero because all the input bits got shifted out.
676 if (Cst->getZExtValue() >= ASize)
Sanjay Patel4b198802016-02-01 22:23:39 +0000677 return replaceInstUsesWith(CI, Constant::getNullValue(DestTy));
Chris Lattner90cd7462010-08-27 18:31:05 +0000678
679 // Since we're doing an lshr and a zero extend, and know that the shift
680 // amount is smaller than ASize, it is always safe to do the shift in A's
681 // type, then zero extend or truncate to the result.
Craig Topperbb4069e2017-07-07 23:16:26 +0000682 Value *Shift = Builder.CreateLShr(A, Cst->getZExtValue());
Chris Lattner90cd7462010-08-27 18:31:05 +0000683 Shift->takeName(Src);
Sanjay Patelf09d1bf2015-11-17 18:37:23 +0000684 return CastInst::CreateIntegerCast(Shift, DestTy, false);
Chris Lattner90cd7462010-08-27 18:31:05 +0000685 }
Craig Topper3529aa52013-01-24 05:22:40 +0000686
Davide Italiano21a49dc2017-05-21 20:30:27 +0000687 // FIXME: We should canonicalize to zext/trunc and remove this transform.
Jakub Kuderski58ea4ee2015-09-10 11:31:20 +0000688 // Transform trunc(lshr (sext A), Cst) to ashr A, Cst to eliminate type
689 // conversion.
690 // It works because bits coming from sign extension have the same value as
Sanjay Patel1de794a2015-11-17 18:46:56 +0000691 // the sign bit of the original value; performing ashr instead of lshr
Jakub Kuderski58ea4ee2015-09-10 11:31:20 +0000692 // generates bits of the same value as the sign bit.
693 if (Src->hasOneUse() &&
Sanjay Patel6844e212017-05-09 16:24:59 +0000694 match(Src, m_LShr(m_SExt(m_Value(A)), m_ConstantInt(Cst)))) {
695 Value *SExt = cast<Instruction>(Src)->getOperand(0);
696 const unsigned SExtSize = SExt->getType()->getPrimitiveSizeInBits();
Jakub Kuderski58ea4ee2015-09-10 11:31:20 +0000697 const unsigned ASize = A->getType()->getPrimitiveSizeInBits();
Davide Italiano21a49dc2017-05-21 20:30:27 +0000698 const unsigned CISize = CI.getType()->getPrimitiveSizeInBits();
699 const unsigned MaxAmt = SExtSize - std::max(CISize, ASize);
Sanjay Patel6844e212017-05-09 16:24:59 +0000700 unsigned ShiftAmt = Cst->getZExtValue();
Davide Italiano21a49dc2017-05-21 20:30:27 +0000701
Jakub Kuderski58ea4ee2015-09-10 11:31:20 +0000702 // This optimization can be only performed when zero bits generated by
703 // the original lshr aren't pulled into the value after truncation, so we
Sanjay Patel6844e212017-05-09 16:24:59 +0000704 // can only shift by values no larger than the number of extension bits.
705 // FIXME: Instead of bailing when the shift is too large, use and to clear
706 // the extra bits.
Davide Italiano21a49dc2017-05-21 20:30:27 +0000707 if (ShiftAmt <= MaxAmt) {
708 if (CISize == ASize)
709 return BinaryOperator::CreateAShr(A, ConstantInt::get(CI.getType(),
710 std::min(ShiftAmt, ASize - 1)));
711 if (SExt->hasOneUse()) {
Craig Topperbb4069e2017-07-07 23:16:26 +0000712 Value *Shift = Builder.CreateAShr(A, std::min(ShiftAmt, ASize - 1));
Davide Italiano21a49dc2017-05-21 20:30:27 +0000713 Shift->takeName(Src);
714 return CastInst::CreateIntegerCast(Shift, CI.getType(), true);
715 }
Jakub Kuderski58ea4ee2015-09-10 11:31:20 +0000716 }
717 }
718
Sanjay Patel94da1de2017-08-05 15:19:18 +0000719 if (Instruction *I = narrowBinOp(CI))
Sanjay Patelaa8b28e2016-11-30 20:48:54 +0000720 return I;
721
Craig Topperbb4069e2017-07-07 23:16:26 +0000722 if (Instruction *I = shrinkSplatShuffle(CI, Builder))
Sanjay Patel53fa17a2017-03-07 21:45:16 +0000723 return I;
724
Craig Topperbb4069e2017-07-07 23:16:26 +0000725 if (Instruction *I = shrinkInsertElt(CI, Builder))
Sanjay Patelfe970512017-03-07 23:27:14 +0000726 return I;
727
Sanjay Patelf09d1bf2015-11-17 18:37:23 +0000728 if (Src->hasOneUse() && isa<IntegerType>(SrcTy) &&
Sanjay Patel2217f752017-01-31 17:25:42 +0000729 shouldChangeType(SrcTy, DestTy)) {
Matt Arsenaulte2e6cfe2016-09-13 19:43:57 +0000730 // Transform "trunc (shl X, cst)" -> "shl (trunc X), cst" so long as the
731 // dest type is native and cst < dest size.
732 if (match(Src, m_Shl(m_Value(A), m_ConstantInt(Cst))) &&
733 !match(A, m_Shr(m_Value(), m_Constant()))) {
734 // Skip shifts of shift by constants. It undoes a combine in
735 // FoldShiftByConstant and is the extend in reg pattern.
736 const unsigned DestSize = DestTy->getScalarSizeInBits();
737 if (Cst->getValue().ult(DestSize)) {
Craig Topperbb4069e2017-07-07 23:16:26 +0000738 Value *NewTrunc = Builder.CreateTrunc(A, DestTy, A->getName() + ".tr");
Matt Arsenaulte2e6cfe2016-09-13 19:43:57 +0000739
740 return BinaryOperator::Create(
741 Instruction::Shl, NewTrunc,
742 ConstantInt::get(DestTy, Cst->getValue().trunc(DestSize)));
743 }
744 }
Chris Lattner9c10d582011-01-15 06:32:33 +0000745 }
Chris Lattner2b295a02010-01-04 07:53:58 +0000746
Craig Toppercb220392017-07-06 23:18:43 +0000747 if (Instruction *I = foldVecTruncToExtElt(CI, *this))
Sanjay Patelf727e382015-12-14 16:16:54 +0000748 return I;
749
Craig Topperf40110f2014-04-25 05:29:35 +0000750 return nullptr;
Chris Lattner2b295a02010-01-04 07:53:58 +0000751}
752
Tobias Grosser8ef834c2016-07-19 09:06:08 +0000753Instruction *InstCombiner::transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
754 bool DoTransform) {
Chris Lattner2b295a02010-01-04 07:53:58 +0000755 // If we are just checking for a icmp eq of a single bit and zext'ing it
756 // to an integer, then shift the bit to the appropriate place and then
757 // cast to integer to avoid the comparison.
758 if (ConstantInt *Op1C = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
759 const APInt &Op1CV = Op1C->getValue();
Craig Topper3529aa52013-01-24 05:22:40 +0000760
Chris Lattner2b295a02010-01-04 07:53:58 +0000761 // zext (x <s 0) to i32 --> x>>u31 true if signbit set.
762 // zext (x >s -1) to i32 --> (x>>u31)^1 true if signbit clear.
Craig Topper73ba1c82017-06-07 07:40:37 +0000763 if ((ICI->getPredicate() == ICmpInst::ICMP_SLT && Op1CV.isNullValue()) ||
Sanjay Patel16395dd2015-12-30 18:31:30 +0000764 (ICI->getPredicate() == ICmpInst::ICMP_SGT && Op1CV.isAllOnesValue())) {
Tobias Grosser8ef834c2016-07-19 09:06:08 +0000765 if (!DoTransform) return ICI;
Chris Lattner2b295a02010-01-04 07:53:58 +0000766
767 Value *In = ICI->getOperand(0);
768 Value *Sh = ConstantInt::get(In->getType(),
Sanjay Patel16395dd2015-12-30 18:31:30 +0000769 In->getType()->getScalarSizeInBits() - 1);
Craig Topperbb4069e2017-07-07 23:16:26 +0000770 In = Builder.CreateLShr(In, Sh, In->getName() + ".lobit");
Chris Lattner2b295a02010-01-04 07:53:58 +0000771 if (In->getType() != CI.getType())
Craig Topperbb4069e2017-07-07 23:16:26 +0000772 In = Builder.CreateIntCast(In, CI.getType(), false /*ZExt*/);
Chris Lattner2b295a02010-01-04 07:53:58 +0000773
774 if (ICI->getPredicate() == ICmpInst::ICMP_SGT) {
775 Constant *One = ConstantInt::get(In->getType(), 1);
Craig Topperbb4069e2017-07-07 23:16:26 +0000776 In = Builder.CreateXor(In, One, In->getName() + ".not");
Chris Lattner2b295a02010-01-04 07:53:58 +0000777 }
778
Sanjay Patel4b198802016-02-01 22:23:39 +0000779 return replaceInstUsesWith(CI, In);
Chris Lattner2b295a02010-01-04 07:53:58 +0000780 }
Chad Rosier385d9f62011-11-30 01:59:59 +0000781
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +0000782 // zext (X == 0) to i32 --> X^1 iff X has only the low bit set.
783 // zext (X == 0) to i32 --> (X>>1)^1 iff X has only the 2nd bit set.
784 // zext (X == 1) to i32 --> X iff X has only the low bit set.
785 // zext (X == 2) to i32 --> X>>1 iff X has only the 2nd bit set.
786 // zext (X != 0) to i32 --> X iff X has only the low bit set.
787 // zext (X != 0) to i32 --> X>>1 iff X has only the 2nd bit set.
788 // zext (X != 1) to i32 --> X^1 iff X has only the low bit set.
789 // zext (X != 2) to i32 --> (X>>1)^1 iff X has only the 2nd bit set.
Craig Topper73ba1c82017-06-07 07:40:37 +0000790 if ((Op1CV.isNullValue() || Op1CV.isPowerOf2()) &&
Chris Lattner2b295a02010-01-04 07:53:58 +0000791 // This only works for EQ and NE
792 ICI->isEquality()) {
793 // If Op1C some other power of two, convert:
Craig Topper8205a1a2017-05-24 16:53:07 +0000794 KnownBits Known = computeKnownBits(ICI->getOperand(0), 0, &CI);
Craig Topper3529aa52013-01-24 05:22:40 +0000795
Craig Topperb45eabc2017-04-26 16:39:58 +0000796 APInt KnownZeroMask(~Known.Zero);
Chris Lattner2b295a02010-01-04 07:53:58 +0000797 if (KnownZeroMask.isPowerOf2()) { // Exactly 1 possible 1?
Tobias Grosser8ef834c2016-07-19 09:06:08 +0000798 if (!DoTransform) return ICI;
Chris Lattner2b295a02010-01-04 07:53:58 +0000799
800 bool isNE = ICI->getPredicate() == ICmpInst::ICMP_NE;
Craig Topper73ba1c82017-06-07 07:40:37 +0000801 if (!Op1CV.isNullValue() && (Op1CV != KnownZeroMask)) {
Chris Lattner2b295a02010-01-04 07:53:58 +0000802 // (X&4) == 2 --> false
803 // (X&4) != 2 --> true
804 Constant *Res = ConstantInt::get(Type::getInt1Ty(CI.getContext()),
805 isNE);
806 Res = ConstantExpr::getZExt(Res, CI.getType());
Sanjay Patel4b198802016-02-01 22:23:39 +0000807 return replaceInstUsesWith(CI, Res);
Chris Lattner2b295a02010-01-04 07:53:58 +0000808 }
Craig Topper3529aa52013-01-24 05:22:40 +0000809
Sanjay Patel16395dd2015-12-30 18:31:30 +0000810 uint32_t ShAmt = KnownZeroMask.logBase2();
Chris Lattner2b295a02010-01-04 07:53:58 +0000811 Value *In = ICI->getOperand(0);
Sanjay Patel16395dd2015-12-30 18:31:30 +0000812 if (ShAmt) {
Chris Lattner2b295a02010-01-04 07:53:58 +0000813 // Perform a logical shr by shiftamt.
814 // Insert the shift to put the result in the low bit.
Craig Topperbb4069e2017-07-07 23:16:26 +0000815 In = Builder.CreateLShr(In, ConstantInt::get(In->getType(), ShAmt),
816 In->getName() + ".lobit");
Chris Lattner2b295a02010-01-04 07:53:58 +0000817 }
Craig Topper3529aa52013-01-24 05:22:40 +0000818
Craig Topper73ba1c82017-06-07 07:40:37 +0000819 if (!Op1CV.isNullValue() == isNE) { // Toggle the low bit.
Chris Lattner2b295a02010-01-04 07:53:58 +0000820 Constant *One = ConstantInt::get(In->getType(), 1);
Craig Topperbb4069e2017-07-07 23:16:26 +0000821 In = Builder.CreateXor(In, One);
Chris Lattner2b295a02010-01-04 07:53:58 +0000822 }
Craig Topper3529aa52013-01-24 05:22:40 +0000823
Chris Lattner2b295a02010-01-04 07:53:58 +0000824 if (CI.getType() == In->getType())
Sanjay Patel4b198802016-02-01 22:23:39 +0000825 return replaceInstUsesWith(CI, In);
Tobias Grosser8757e382016-08-03 19:30:35 +0000826
Craig Topperbb4069e2017-07-07 23:16:26 +0000827 Value *IntCast = Builder.CreateIntCast(In, CI.getType(), false);
Tobias Grosser8757e382016-08-03 19:30:35 +0000828 return replaceInstUsesWith(CI, IntCast);
Chris Lattner2b295a02010-01-04 07:53:58 +0000829 }
830 }
831 }
832
833 // icmp ne A, B is equal to xor A, B when A and B only really have one bit.
834 // It is also profitable to transform icmp eq into not(xor(A, B)) because that
835 // may lead to additional simplifications.
836 if (ICI->isEquality() && CI.getType() == ICI->getOperand(0)->getType()) {
Chris Lattner229907c2011-07-18 04:54:35 +0000837 if (IntegerType *ITy = dyn_cast<IntegerType>(CI.getType())) {
Chris Lattner2b295a02010-01-04 07:53:58 +0000838 Value *LHS = ICI->getOperand(0);
839 Value *RHS = ICI->getOperand(1);
840
Craig Topper8205a1a2017-05-24 16:53:07 +0000841 KnownBits KnownLHS = computeKnownBits(LHS, 0, &CI);
842 KnownBits KnownRHS = computeKnownBits(RHS, 0, &CI);
Chris Lattner2b295a02010-01-04 07:53:58 +0000843
Craig Topperb45eabc2017-04-26 16:39:58 +0000844 if (KnownLHS.Zero == KnownRHS.Zero && KnownLHS.One == KnownRHS.One) {
845 APInt KnownBits = KnownLHS.Zero | KnownLHS.One;
Chris Lattner2b295a02010-01-04 07:53:58 +0000846 APInt UnknownBit = ~KnownBits;
847 if (UnknownBit.countPopulation() == 1) {
Tobias Grosser8ef834c2016-07-19 09:06:08 +0000848 if (!DoTransform) return ICI;
Chris Lattner2b295a02010-01-04 07:53:58 +0000849
Craig Topperbb4069e2017-07-07 23:16:26 +0000850 Value *Result = Builder.CreateXor(LHS, RHS);
Chris Lattner2b295a02010-01-04 07:53:58 +0000851
852 // Mask off any bits that are set and won't be shifted away.
Craig Topperb45eabc2017-04-26 16:39:58 +0000853 if (KnownLHS.One.uge(UnknownBit))
Craig Topperbb4069e2017-07-07 23:16:26 +0000854 Result = Builder.CreateAnd(Result,
Chris Lattner2b295a02010-01-04 07:53:58 +0000855 ConstantInt::get(ITy, UnknownBit));
856
857 // Shift the bit we're testing down to the lsb.
Craig Topperbb4069e2017-07-07 23:16:26 +0000858 Result = Builder.CreateLShr(
Chris Lattner2b295a02010-01-04 07:53:58 +0000859 Result, ConstantInt::get(ITy, UnknownBit.countTrailingZeros()));
860
861 if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
Craig Topperbb4069e2017-07-07 23:16:26 +0000862 Result = Builder.CreateXor(Result, ConstantInt::get(ITy, 1));
Chris Lattner2b295a02010-01-04 07:53:58 +0000863 Result->takeName(ICI);
Sanjay Patel4b198802016-02-01 22:23:39 +0000864 return replaceInstUsesWith(CI, Result);
Chris Lattner2b295a02010-01-04 07:53:58 +0000865 }
866 }
867 }
868 }
869
Craig Topperf40110f2014-04-25 05:29:35 +0000870 return nullptr;
Chris Lattner2b295a02010-01-04 07:53:58 +0000871}
872
Sanjay Patel2fbab9d82015-09-09 14:34:26 +0000873/// Determine if the specified value can be computed in the specified wider type
874/// and produce the same low bits. If not, return false.
Chris Lattner172630a2010-01-11 02:43:35 +0000875///
Chris Lattner12bd8992010-01-11 03:32:00 +0000876/// If this function returns true, it can also return a non-zero number of bits
877/// (in BitsToClear) which indicates that the value it computes is correct for
878/// the zero extend, but that the additional BitsToClear bits need to be zero'd
879/// out. For example, to promote something like:
880///
881/// %B = trunc i64 %A to i32
882/// %C = lshr i32 %B, 8
883/// %E = zext i32 %C to i64
884///
885/// CanEvaluateZExtd for the 'lshr' will return true, and BitsToClear will be
886/// set to 8 to indicate that the promoted value needs to have bits 24-31
887/// cleared in addition to bits 32-63. Since an 'and' will be generated to
888/// clear the top bits anyway, doing this has no extra cost.
889///
Chris Lattner172630a2010-01-11 02:43:35 +0000890/// This function works on both vectors and scalars.
Sanjay Patele2834412015-09-09 14:54:29 +0000891static bool canEvaluateZExtd(Value *V, Type *Ty, unsigned &BitsToClear,
Hal Finkel60db0582014-09-07 18:57:58 +0000892 InstCombiner &IC, Instruction *CxtI) {
Chris Lattner12bd8992010-01-11 03:32:00 +0000893 BitsToClear = 0;
Chris Lattnerb7be7cc2010-01-10 02:50:04 +0000894 if (isa<Constant>(V))
895 return true;
Craig Topper3529aa52013-01-24 05:22:40 +0000896
Chris Lattnerc3aca382010-01-10 00:58:42 +0000897 Instruction *I = dyn_cast<Instruction>(V);
Chris Lattnerb7be7cc2010-01-10 02:50:04 +0000898 if (!I) return false;
Craig Topper3529aa52013-01-24 05:22:40 +0000899
Chris Lattnerc3aca382010-01-10 00:58:42 +0000900 // If the input is a truncate from the destination type, we can trivially
Jakob Stoklund Olesenc5c4e962012-06-22 16:36:43 +0000901 // eliminate it.
902 if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty)
Chris Lattnerb7be7cc2010-01-10 02:50:04 +0000903 return true;
Craig Topper3529aa52013-01-24 05:22:40 +0000904
Chris Lattnerc3aca382010-01-10 00:58:42 +0000905 // We can't extend or shrink something that has multiple uses: doing so would
906 // require duplicating the instruction in general, which isn't profitable.
Chris Lattnerb7be7cc2010-01-10 02:50:04 +0000907 if (!I->hasOneUse()) return false;
Craig Topper3529aa52013-01-24 05:22:40 +0000908
Chris Lattner12bd8992010-01-11 03:32:00 +0000909 unsigned Opc = I->getOpcode(), Tmp;
Chris Lattnerc3aca382010-01-10 00:58:42 +0000910 switch (Opc) {
Chris Lattner39d2daa2010-01-10 20:25:54 +0000911 case Instruction::ZExt: // zext(zext(x)) -> zext(x).
912 case Instruction::SExt: // zext(sext(x)) -> sext(x).
913 case Instruction::Trunc: // zext(trunc(x)) -> trunc(x) or zext(x)
914 return true;
Chris Lattnerc3aca382010-01-10 00:58:42 +0000915 case Instruction::And:
Chris Lattnerc3aca382010-01-10 00:58:42 +0000916 case Instruction::Or:
917 case Instruction::Xor:
Chris Lattnerc3aca382010-01-10 00:58:42 +0000918 case Instruction::Add:
919 case Instruction::Sub:
920 case Instruction::Mul:
Sanjay Patele2834412015-09-09 14:54:29 +0000921 if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI) ||
922 !canEvaluateZExtd(I->getOperand(1), Ty, Tmp, IC, CxtI))
Chris Lattner12bd8992010-01-11 03:32:00 +0000923 return false;
924 // These can all be promoted if neither operand has 'bits to clear'.
925 if (BitsToClear == 0 && Tmp == 0)
926 return true;
Craig Topper3529aa52013-01-24 05:22:40 +0000927
Chris Lattner0a854202010-01-11 04:05:13 +0000928 // If the operation is an AND/OR/XOR and the bits to clear are zero in the
929 // other side, BitsToClear is ok.
Sanjay Patel1e6ca442016-11-22 22:54:36 +0000930 if (Tmp == 0 && I->isBitwiseLogicOp()) {
Chris Lattner0a854202010-01-11 04:05:13 +0000931 // We use MaskedValueIsZero here for generality, but the case we care
932 // about the most is constant RHS.
933 unsigned VSize = V->getType()->getScalarSizeInBits();
Hal Finkel60db0582014-09-07 18:57:58 +0000934 if (IC.MaskedValueIsZero(I->getOperand(1),
935 APInt::getHighBitsSet(VSize, BitsToClear),
936 0, CxtI))
Chris Lattner0a854202010-01-11 04:05:13 +0000937 return true;
938 }
Craig Topper3529aa52013-01-24 05:22:40 +0000939
Chris Lattner0a854202010-01-11 04:05:13 +0000940 // Otherwise, we don't know how to analyze this BitsToClear case yet.
Chris Lattner12bd8992010-01-11 03:32:00 +0000941 return false;
Craig Topper3529aa52013-01-24 05:22:40 +0000942
Craig Topper0a1a2762017-08-15 22:48:41 +0000943 case Instruction::Shl: {
Benjamin Kramer14e915f2013-05-10 16:26:37 +0000944 // We can promote shl(x, cst) if we can promote x. Since shl overwrites the
945 // upper bits we can reduce BitsToClear by the shift amount.
Craig Topper0a1a2762017-08-15 22:48:41 +0000946 const APInt *Amt;
947 if (match(I->getOperand(1), m_APInt(Amt))) {
Sanjay Patele2834412015-09-09 14:54:29 +0000948 if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI))
Benjamin Kramer14e915f2013-05-10 16:26:37 +0000949 return false;
950 uint64_t ShiftAmt = Amt->getZExtValue();
951 BitsToClear = ShiftAmt < BitsToClear ? BitsToClear - ShiftAmt : 0;
952 return true;
953 }
954 return false;
Craig Topper0a1a2762017-08-15 22:48:41 +0000955 }
956 case Instruction::LShr: {
Chris Lattner12bd8992010-01-11 03:32:00 +0000957 // We can promote lshr(x, cst) if we can promote x. This requires the
958 // ultimate 'and' to clear out the high zero bits we're clearing out though.
Craig Topper0a1a2762017-08-15 22:48:41 +0000959 const APInt *Amt;
960 if (match(I->getOperand(1), m_APInt(Amt))) {
Sanjay Patele2834412015-09-09 14:54:29 +0000961 if (!canEvaluateZExtd(I->getOperand(0), Ty, BitsToClear, IC, CxtI))
Chris Lattner12bd8992010-01-11 03:32:00 +0000962 return false;
963 BitsToClear += Amt->getZExtValue();
964 if (BitsToClear > V->getType()->getScalarSizeInBits())
965 BitsToClear = V->getType()->getScalarSizeInBits();
966 return true;
967 }
968 // Cannot promote variable LSHR.
969 return false;
Craig Topper0a1a2762017-08-15 22:48:41 +0000970 }
Chris Lattnerc3aca382010-01-10 00:58:42 +0000971 case Instruction::Select:
Sanjay Patele2834412015-09-09 14:54:29 +0000972 if (!canEvaluateZExtd(I->getOperand(1), Ty, Tmp, IC, CxtI) ||
973 !canEvaluateZExtd(I->getOperand(2), Ty, BitsToClear, IC, CxtI) ||
Chris Lattner0a854202010-01-11 04:05:13 +0000974 // TODO: If important, we could handle the case when the BitsToClear are
975 // known zero in the disagreeing side.
Chris Lattner12bd8992010-01-11 03:32:00 +0000976 Tmp != BitsToClear)
977 return false;
978 return true;
Craig Topper3529aa52013-01-24 05:22:40 +0000979
Chris Lattnerc3aca382010-01-10 00:58:42 +0000980 case Instruction::PHI: {
981 // We can change a phi if we can change all operands. Note that we never
982 // get into trouble with cyclic PHIs here because we only consider
983 // instructions with a single use.
984 PHINode *PN = cast<PHINode>(I);
Sanjay Patele2834412015-09-09 14:54:29 +0000985 if (!canEvaluateZExtd(PN->getIncomingValue(0), Ty, BitsToClear, IC, CxtI))
Chris Lattner12bd8992010-01-11 03:32:00 +0000986 return false;
Chris Lattnerb7be7cc2010-01-10 02:50:04 +0000987 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i)
Sanjay Patele2834412015-09-09 14:54:29 +0000988 if (!canEvaluateZExtd(PN->getIncomingValue(i), Ty, Tmp, IC, CxtI) ||
Chris Lattner0a854202010-01-11 04:05:13 +0000989 // TODO: If important, we could handle the case when the BitsToClear
990 // are known zero in the disagreeing input.
Chris Lattner12bd8992010-01-11 03:32:00 +0000991 Tmp != BitsToClear)
992 return false;
Chris Lattnerb7be7cc2010-01-10 02:50:04 +0000993 return true;
Chris Lattnerc3aca382010-01-10 00:58:42 +0000994 }
995 default:
996 // TODO: Can handle more cases here.
Chris Lattnerb7be7cc2010-01-10 02:50:04 +0000997 return false;
Chris Lattnerc3aca382010-01-10 00:58:42 +0000998 }
999}
1000
Chris Lattner2b295a02010-01-04 07:53:58 +00001001Instruction *InstCombiner::visitZExt(ZExtInst &CI) {
Nick Lewycky80ea0032013-01-14 20:56:10 +00001002 // If this zero extend is only used by a truncate, let the truncate be
Chris Lattner49d2c972010-01-10 02:39:31 +00001003 // eliminated before we try to optimize this zext.
Chandler Carruthcdf47882014-03-09 03:16:01 +00001004 if (CI.hasOneUse() && isa<TruncInst>(CI.user_back()))
Craig Topperf40110f2014-04-25 05:29:35 +00001005 return nullptr;
Craig Topper3529aa52013-01-24 05:22:40 +00001006
Chris Lattner2b295a02010-01-04 07:53:58 +00001007 // If one of the common conversion will work, do it.
Chris Lattner883550a2010-01-10 01:00:46 +00001008 if (Instruction *Result = commonCastTransforms(CI))
Chris Lattner2b295a02010-01-04 07:53:58 +00001009 return Result;
1010
Chris Lattner883550a2010-01-10 01:00:46 +00001011 Value *Src = CI.getOperand(0);
Chris Lattner229907c2011-07-18 04:54:35 +00001012 Type *SrcTy = Src->getType(), *DestTy = CI.getType();
Craig Topper3529aa52013-01-24 05:22:40 +00001013
Chris Lattnerc3aca382010-01-10 00:58:42 +00001014 // Attempt to extend the entire input expression tree to the destination
1015 // type. Only do this if the dest type is a simple type, don't convert the
1016 // expression tree to something weird like i93 unless the source is also
1017 // strange.
Chris Lattner12bd8992010-01-11 03:32:00 +00001018 unsigned BitsToClear;
Sanjay Patel2217f752017-01-31 17:25:42 +00001019 if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) &&
Sanjay Patele2834412015-09-09 14:54:29 +00001020 canEvaluateZExtd(Src, DestTy, BitsToClear, *this, &CI)) {
Bjorn Petterssonc98dabb2017-03-16 13:22:01 +00001021 assert(BitsToClear <= SrcTy->getScalarSizeInBits() &&
1022 "Can't clear more bits than in SrcTy");
Craig Topper3529aa52013-01-24 05:22:40 +00001023
Chris Lattner49d2c972010-01-10 02:39:31 +00001024 // Okay, we can transform this! Insert the new expression now.
1025 DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
Weiming Zhao24fbef52015-12-17 19:53:41 +00001026 " to avoid zero extend: " << CI << '\n');
Chris Lattner49d2c972010-01-10 02:39:31 +00001027 Value *Res = EvaluateInDifferentType(Src, DestTy, false);
1028 assert(Res->getType() == DestTy);
Craig Topper3529aa52013-01-24 05:22:40 +00001029
Chris Lattner12bd8992010-01-11 03:32:00 +00001030 uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits()-BitsToClear;
1031 uint32_t DestBitSize = DestTy->getScalarSizeInBits();
Craig Topper3529aa52013-01-24 05:22:40 +00001032
Chris Lattner49d2c972010-01-10 02:39:31 +00001033 // If the high bits are already filled with zeros, just replace this
1034 // cast with the result.
Hal Finkel60db0582014-09-07 18:57:58 +00001035 if (MaskedValueIsZero(Res,
1036 APInt::getHighBitsSet(DestBitSize,
1037 DestBitSize-SrcBitsKept),
1038 0, &CI))
Sanjay Patel4b198802016-02-01 22:23:39 +00001039 return replaceInstUsesWith(CI, Res);
Craig Topper3529aa52013-01-24 05:22:40 +00001040
Chris Lattner49d2c972010-01-10 02:39:31 +00001041 // We need to emit an AND to clear the high bits.
Chris Lattner39d2daa2010-01-10 20:25:54 +00001042 Constant *C = ConstantInt::get(Res->getType(),
Chris Lattner12bd8992010-01-11 03:32:00 +00001043 APInt::getLowBitsSet(DestBitSize, SrcBitsKept));
Chris Lattner49d2c972010-01-10 02:39:31 +00001044 return BinaryOperator::CreateAnd(Res, C);
Chris Lattnerc3aca382010-01-10 00:58:42 +00001045 }
Chris Lattner2b295a02010-01-04 07:53:58 +00001046
1047 // If this is a TRUNC followed by a ZEXT then we are dealing with integral
1048 // types and if the sizes are just right we can convert this into a logical
1049 // 'and' which will be much cheaper than the pair of casts.
1050 if (TruncInst *CSrc = dyn_cast<TruncInst>(Src)) { // A->B->C cast
Chris Lattnerd8509422010-01-10 07:08:30 +00001051 // TODO: Subsume this into EvaluateInDifferentType.
Craig Topper3529aa52013-01-24 05:22:40 +00001052
Chris Lattner2b295a02010-01-04 07:53:58 +00001053 // Get the sizes of the types involved. We know that the intermediate type
1054 // will be smaller than A or C, but don't know the relation between A and C.
1055 Value *A = CSrc->getOperand(0);
1056 unsigned SrcSize = A->getType()->getScalarSizeInBits();
1057 unsigned MidSize = CSrc->getType()->getScalarSizeInBits();
1058 unsigned DstSize = CI.getType()->getScalarSizeInBits();
1059 // If we're actually extending zero bits, then if
1060 // SrcSize < DstSize: zext(a & mask)
1061 // SrcSize == DstSize: a & mask
1062 // SrcSize > DstSize: trunc(a) & mask
1063 if (SrcSize < DstSize) {
1064 APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize));
1065 Constant *AndConst = ConstantInt::get(A->getType(), AndValue);
Craig Topperbb4069e2017-07-07 23:16:26 +00001066 Value *And = Builder.CreateAnd(A, AndConst, CSrc->getName() + ".mask");
Chris Lattner2b295a02010-01-04 07:53:58 +00001067 return new ZExtInst(And, CI.getType());
1068 }
Craig Topper3529aa52013-01-24 05:22:40 +00001069
Chris Lattner2b295a02010-01-04 07:53:58 +00001070 if (SrcSize == DstSize) {
1071 APInt AndValue(APInt::getLowBitsSet(SrcSize, MidSize));
1072 return BinaryOperator::CreateAnd(A, ConstantInt::get(A->getType(),
1073 AndValue));
1074 }
1075 if (SrcSize > DstSize) {
Craig Topperbb4069e2017-07-07 23:16:26 +00001076 Value *Trunc = Builder.CreateTrunc(A, CI.getType());
Chris Lattner2b295a02010-01-04 07:53:58 +00001077 APInt AndValue(APInt::getLowBitsSet(DstSize, MidSize));
Craig Topper3529aa52013-01-24 05:22:40 +00001078 return BinaryOperator::CreateAnd(Trunc,
Chris Lattner2b295a02010-01-04 07:53:58 +00001079 ConstantInt::get(Trunc->getType(),
Chris Lattnerd8509422010-01-10 07:08:30 +00001080 AndValue));
Chris Lattner2b295a02010-01-04 07:53:58 +00001081 }
1082 }
1083
1084 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src))
1085 return transformZExtICmp(ICI, CI);
1086
1087 BinaryOperator *SrcI = dyn_cast<BinaryOperator>(Src);
1088 if (SrcI && SrcI->getOpcode() == Instruction::Or) {
Tobias Grosser8757e382016-08-03 19:30:35 +00001089 // zext (or icmp, icmp) -> or (zext icmp), (zext icmp) if at least one
1090 // of the (zext icmp) can be eliminated. If so, immediately perform the
1091 // according elimination.
Chris Lattner2b295a02010-01-04 07:53:58 +00001092 ICmpInst *LHS = dyn_cast<ICmpInst>(SrcI->getOperand(0));
1093 ICmpInst *RHS = dyn_cast<ICmpInst>(SrcI->getOperand(1));
1094 if (LHS && RHS && LHS->hasOneUse() && RHS->hasOneUse() &&
1095 (transformZExtICmp(LHS, CI, false) ||
1096 transformZExtICmp(RHS, CI, false))) {
Tobias Grosser8757e382016-08-03 19:30:35 +00001097 // zext (or icmp, icmp) -> or (zext icmp), (zext icmp)
Craig Topperbb4069e2017-07-07 23:16:26 +00001098 Value *LCast = Builder.CreateZExt(LHS, CI.getType(), LHS->getName());
1099 Value *RCast = Builder.CreateZExt(RHS, CI.getType(), RHS->getName());
Tobias Grosser8757e382016-08-03 19:30:35 +00001100 BinaryOperator *Or = BinaryOperator::Create(Instruction::Or, LCast, RCast);
1101
1102 // Perform the elimination.
1103 if (auto *LZExt = dyn_cast<ZExtInst>(LCast))
1104 transformZExtICmp(LHS, *LZExt);
1105 if (auto *RZExt = dyn_cast<ZExtInst>(RCast))
1106 transformZExtICmp(RHS, *RZExt);
1107
1108 return Or;
Chris Lattner2b295a02010-01-04 07:53:58 +00001109 }
1110 }
1111
Benjamin Kramerb80e1692014-01-19 20:05:13 +00001112 // zext(trunc(X) & C) -> (X & zext(C)).
1113 Constant *C;
1114 Value *X;
1115 if (SrcI &&
1116 match(SrcI, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Constant(C)))) &&
1117 X->getType() == CI.getType())
1118 return BinaryOperator::CreateAnd(X, ConstantExpr::getZExt(C, CI.getType()));
Chris Lattner2b295a02010-01-04 07:53:58 +00001119
Benjamin Kramerb80e1692014-01-19 20:05:13 +00001120 // zext((trunc(X) & C) ^ C) -> ((X & zext(C)) ^ zext(C)).
1121 Value *And;
1122 if (SrcI && match(SrcI, m_OneUse(m_Xor(m_Value(And), m_Constant(C)))) &&
1123 match(And, m_OneUse(m_And(m_Trunc(m_Value(X)), m_Specific(C)))) &&
1124 X->getType() == CI.getType()) {
1125 Constant *ZC = ConstantExpr::getZExt(C, CI.getType());
Craig Topperbb4069e2017-07-07 23:16:26 +00001126 return BinaryOperator::CreateXor(Builder.CreateAnd(X, ZC), ZC);
Benjamin Kramerb80e1692014-01-19 20:05:13 +00001127 }
Chris Lattner2b295a02010-01-04 07:53:58 +00001128
Craig Topperf40110f2014-04-25 05:29:35 +00001129 return nullptr;
Chris Lattner2b295a02010-01-04 07:53:58 +00001130}
1131
Sanjay Patel2fbab9d82015-09-09 14:34:26 +00001132/// Transform (sext icmp) to bitwise / integer operations to eliminate the icmp.
Benjamin Kramer398b8c52011-04-01 20:09:03 +00001133Instruction *InstCombiner::transformSExtICmp(ICmpInst *ICI, Instruction &CI) {
1134 Value *Op0 = ICI->getOperand(0), *Op1 = ICI->getOperand(1);
1135 ICmpInst::Predicate Pred = ICI->getPredicate();
1136
David Majnemerc8bdd232014-10-27 05:47:49 +00001137 // Don't bother if Op1 isn't of vector or integer type.
1138 if (!Op1->getType()->isIntOrIntVectorTy())
1139 return nullptr;
1140
Benjamin Kramerb80e1692014-01-19 20:05:13 +00001141 if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
Benjamin Kramer8b94c292011-04-01 22:29:18 +00001142 // (x <s 0) ? -1 : 0 -> ashr x, 31 -> all ones if negative
1143 // (x >s -1) ? -1 : 0 -> not (ashr x, 31) -> all ones if positive
Benjamin Kramerb80e1692014-01-19 20:05:13 +00001144 if ((Pred == ICmpInst::ICMP_SLT && Op1C->isNullValue()) ||
Sanjay Patel5e4c46d2016-03-02 01:04:09 +00001145 (Pred == ICmpInst::ICMP_SGT && Op1C->isAllOnesValue())) {
Benjamin Kramer398b8c52011-04-01 20:09:03 +00001146
1147 Value *Sh = ConstantInt::get(Op0->getType(),
Sanjay Patel5e4c46d2016-03-02 01:04:09 +00001148 Op0->getType()->getScalarSizeInBits()-1);
Craig Topperbb4069e2017-07-07 23:16:26 +00001149 Value *In = Builder.CreateAShr(Op0, Sh, Op0->getName() + ".lobit");
Benjamin Kramer398b8c52011-04-01 20:09:03 +00001150 if (In->getType() != CI.getType())
Craig Topperbb4069e2017-07-07 23:16:26 +00001151 In = Builder.CreateIntCast(In, CI.getType(), true /*SExt*/);
Benjamin Kramer398b8c52011-04-01 20:09:03 +00001152
Sanjay Patel5e4c46d2016-03-02 01:04:09 +00001153 if (Pred == ICmpInst::ICMP_SGT)
Craig Topperbb4069e2017-07-07 23:16:26 +00001154 In = Builder.CreateNot(In, In->getName() + ".not");
Sanjay Patel4b198802016-02-01 22:23:39 +00001155 return replaceInstUsesWith(CI, In);
Benjamin Kramer398b8c52011-04-01 20:09:03 +00001156 }
Benjamin Kramerb80e1692014-01-19 20:05:13 +00001157 }
Benjamin Kramerd1217652011-04-01 20:09:10 +00001158
Benjamin Kramerb80e1692014-01-19 20:05:13 +00001159 if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
Benjamin Kramerd1217652011-04-01 20:09:10 +00001160 // If we know that only one bit of the LHS of the icmp can be set and we
1161 // have an equality comparison with zero or a power of 2, we can transform
1162 // the icmp and sext into bitwise/integer operations.
Benjamin Kramer5cad4532011-04-01 22:22:11 +00001163 if (ICI->hasOneUse() &&
1164 ICI->isEquality() && (Op1C->isZero() || Op1C->getValue().isPowerOf2())){
Craig Topper8205a1a2017-05-24 16:53:07 +00001165 KnownBits Known = computeKnownBits(Op0, 0, &CI);
Benjamin Kramerd1217652011-04-01 20:09:10 +00001166
Craig Topperb45eabc2017-04-26 16:39:58 +00001167 APInt KnownZeroMask(~Known.Zero);
Benjamin Kramerac2d5652011-04-01 20:15:16 +00001168 if (KnownZeroMask.isPowerOf2()) {
Benjamin Kramerd1217652011-04-01 20:09:10 +00001169 Value *In = ICI->getOperand(0);
1170
Benjamin Kramer50a281a2011-04-02 18:50:58 +00001171 // If the icmp tests for a known zero bit we can constant fold it.
1172 if (!Op1C->isZero() && Op1C->getValue() != KnownZeroMask) {
1173 Value *V = Pred == ICmpInst::ICMP_NE ?
1174 ConstantInt::getAllOnesValue(CI.getType()) :
1175 ConstantInt::getNullValue(CI.getType());
Sanjay Patel4b198802016-02-01 22:23:39 +00001176 return replaceInstUsesWith(CI, V);
Benjamin Kramer50a281a2011-04-02 18:50:58 +00001177 }
Benjamin Kramer5cad4532011-04-01 22:22:11 +00001178
Benjamin Kramerd1217652011-04-01 20:09:10 +00001179 if (!Op1C->isZero() == (Pred == ICmpInst::ICMP_NE)) {
1180 // sext ((x & 2^n) == 0) -> (x >> n) - 1
1181 // sext ((x & 2^n) != 2^n) -> (x >> n) - 1
1182 unsigned ShiftAmt = KnownZeroMask.countTrailingZeros();
1183 // Perform a right shift to place the desired bit in the LSB.
1184 if (ShiftAmt)
Craig Topperbb4069e2017-07-07 23:16:26 +00001185 In = Builder.CreateLShr(In,
1186 ConstantInt::get(In->getType(), ShiftAmt));
Benjamin Kramerd1217652011-04-01 20:09:10 +00001187
1188 // At this point "In" is either 1 or 0. Subtract 1 to turn
1189 // {1, 0} -> {0, -1}.
Craig Topperbb4069e2017-07-07 23:16:26 +00001190 In = Builder.CreateAdd(In,
1191 ConstantInt::getAllOnesValue(In->getType()),
1192 "sext");
Benjamin Kramerd1217652011-04-01 20:09:10 +00001193 } else {
1194 // sext ((x & 2^n) != 0) -> (x << bitwidth-n) a>> bitwidth-1
Benjamin Kramer5cad4532011-04-01 22:22:11 +00001195 // sext ((x & 2^n) == 2^n) -> (x << bitwidth-n) a>> bitwidth-1
Benjamin Kramerd1217652011-04-01 20:09:10 +00001196 unsigned ShiftAmt = KnownZeroMask.countLeadingZeros();
1197 // Perform a left shift to place the desired bit in the MSB.
1198 if (ShiftAmt)
Craig Topperbb4069e2017-07-07 23:16:26 +00001199 In = Builder.CreateShl(In,
1200 ConstantInt::get(In->getType(), ShiftAmt));
Benjamin Kramerd1217652011-04-01 20:09:10 +00001201
1202 // Distribute the bit over the whole bit width.
Craig Topperbb4069e2017-07-07 23:16:26 +00001203 In = Builder.CreateAShr(In, ConstantInt::get(In->getType(),
1204 KnownZeroMask.getBitWidth() - 1), "sext");
Benjamin Kramerd1217652011-04-01 20:09:10 +00001205 }
1206
1207 if (CI.getType() == In->getType())
Sanjay Patel4b198802016-02-01 22:23:39 +00001208 return replaceInstUsesWith(CI, In);
Benjamin Kramerd1217652011-04-01 20:09:10 +00001209 return CastInst::CreateIntegerCast(In, CI.getType(), true/*SExt*/);
1210 }
1211 }
Benjamin Kramer398b8c52011-04-01 20:09:03 +00001212 }
1213
Craig Topperf40110f2014-04-25 05:29:35 +00001214 return nullptr;
Benjamin Kramer398b8c52011-04-01 20:09:03 +00001215}
1216
Sanjay Patel2fbab9d82015-09-09 14:34:26 +00001217/// Return true if we can take the specified value and return it as type Ty
1218/// without inserting any new casts and without changing the value of the common
1219/// low bits. This is used by code that tries to promote integer operations to
1220/// a wider types will allow us to eliminate the extension.
Chris Lattnerc3aca382010-01-10 00:58:42 +00001221///
Chris Lattner1a05fdd2010-01-10 07:57:20 +00001222/// This function works on both vectors and scalars.
Chris Lattnerc3aca382010-01-10 00:58:42 +00001223///
Sanjay Patele2834412015-09-09 14:54:29 +00001224static bool canEvaluateSExtd(Value *V, Type *Ty) {
Chris Lattnerc3aca382010-01-10 00:58:42 +00001225 assert(V->getType()->getScalarSizeInBits() < Ty->getScalarSizeInBits() &&
1226 "Can't sign extend type to a smaller type");
Chris Lattner1a05fdd2010-01-10 07:57:20 +00001227 // If this is a constant, it can be trivially promoted.
1228 if (isa<Constant>(V))
1229 return true;
Craig Topper3529aa52013-01-24 05:22:40 +00001230
Chris Lattnerc3aca382010-01-10 00:58:42 +00001231 Instruction *I = dyn_cast<Instruction>(V);
Chris Lattner1a05fdd2010-01-10 07:57:20 +00001232 if (!I) return false;
Craig Topper3529aa52013-01-24 05:22:40 +00001233
Jakob Stoklund Olesenc5c4e962012-06-22 16:36:43 +00001234 // If this is a truncate from the dest type, we can trivially eliminate it.
1235 if (isa<TruncInst>(I) && I->getOperand(0)->getType() == Ty)
Chris Lattner1a05fdd2010-01-10 07:57:20 +00001236 return true;
Craig Topper3529aa52013-01-24 05:22:40 +00001237
Chris Lattnerc3aca382010-01-10 00:58:42 +00001238 // We can't extend or shrink something that has multiple uses: doing so would
1239 // require duplicating the instruction in general, which isn't profitable.
Chris Lattner1a05fdd2010-01-10 07:57:20 +00001240 if (!I->hasOneUse()) return false;
Chris Lattnerc3aca382010-01-10 00:58:42 +00001241
Chris Lattner1a05fdd2010-01-10 07:57:20 +00001242 switch (I->getOpcode()) {
Chris Lattner7dd540e2010-01-10 20:30:41 +00001243 case Instruction::SExt: // sext(sext(x)) -> sext(x)
1244 case Instruction::ZExt: // sext(zext(x)) -> zext(x)
1245 case Instruction::Trunc: // sext(trunc(x)) -> trunc(x) or sext(x)
1246 return true;
Chris Lattnerc3aca382010-01-10 00:58:42 +00001247 case Instruction::And:
1248 case Instruction::Or:
1249 case Instruction::Xor:
Chris Lattnerc3aca382010-01-10 00:58:42 +00001250 case Instruction::Add:
1251 case Instruction::Sub:
Chris Lattnerc3aca382010-01-10 00:58:42 +00001252 case Instruction::Mul:
Chris Lattner1a05fdd2010-01-10 07:57:20 +00001253 // These operators can all arbitrarily be extended if their inputs can.
Sanjay Patele2834412015-09-09 14:54:29 +00001254 return canEvaluateSExtd(I->getOperand(0), Ty) &&
1255 canEvaluateSExtd(I->getOperand(1), Ty);
Craig Topper3529aa52013-01-24 05:22:40 +00001256
Chris Lattnerc3aca382010-01-10 00:58:42 +00001257 //case Instruction::Shl: TODO
1258 //case Instruction::LShr: TODO
Craig Topper3529aa52013-01-24 05:22:40 +00001259
Chris Lattner1a05fdd2010-01-10 07:57:20 +00001260 case Instruction::Select:
Sanjay Patele2834412015-09-09 14:54:29 +00001261 return canEvaluateSExtd(I->getOperand(1), Ty) &&
1262 canEvaluateSExtd(I->getOperand(2), Ty);
Craig Topper3529aa52013-01-24 05:22:40 +00001263
Chris Lattnerc3aca382010-01-10 00:58:42 +00001264 case Instruction::PHI: {
1265 // We can change a phi if we can change all operands. Note that we never
1266 // get into trouble with cyclic PHIs here because we only consider
1267 // instructions with a single use.
1268 PHINode *PN = cast<PHINode>(I);
Pete Cooper833f34d2015-05-12 20:05:31 +00001269 for (Value *IncValue : PN->incoming_values())
Sanjay Patele2834412015-09-09 14:54:29 +00001270 if (!canEvaluateSExtd(IncValue, Ty)) return false;
Chris Lattner1a05fdd2010-01-10 07:57:20 +00001271 return true;
Chris Lattnerc3aca382010-01-10 00:58:42 +00001272 }
1273 default:
1274 // TODO: Can handle more cases here.
1275 break;
1276 }
Craig Topper3529aa52013-01-24 05:22:40 +00001277
Chris Lattner1a05fdd2010-01-10 07:57:20 +00001278 return false;
Chris Lattnerc3aca382010-01-10 00:58:42 +00001279}
1280
Chris Lattner2b295a02010-01-04 07:53:58 +00001281Instruction *InstCombiner::visitSExt(SExtInst &CI) {
Arnaud A. de Grandmaison2e4df4f2013-02-13 00:19:19 +00001282 // If this sign extend is only used by a truncate, let the truncate be
1283 // eliminated before we try to optimize this sext.
Chandler Carruthcdf47882014-03-09 03:16:01 +00001284 if (CI.hasOneUse() && isa<TruncInst>(CI.user_back()))
Craig Topperf40110f2014-04-25 05:29:35 +00001285 return nullptr;
Craig Topper3529aa52013-01-24 05:22:40 +00001286
Chris Lattner883550a2010-01-10 01:00:46 +00001287 if (Instruction *I = commonCastTransforms(CI))
Chris Lattner2b295a02010-01-04 07:53:58 +00001288 return I;
Craig Topper3529aa52013-01-24 05:22:40 +00001289
Chris Lattner2b295a02010-01-04 07:53:58 +00001290 Value *Src = CI.getOperand(0);
Chris Lattner229907c2011-07-18 04:54:35 +00001291 Type *SrcTy = Src->getType(), *DestTy = CI.getType();
Chris Lattnerc3aca382010-01-10 00:58:42 +00001292
Philip Reames9ae15202015-02-14 00:05:36 +00001293 // If we know that the value being extended is positive, we can use a zext
Justin Bognerc7e4fbe2016-08-05 01:09:48 +00001294 // instead.
Craig Topper1a36b7d2017-05-15 06:39:41 +00001295 KnownBits Known = computeKnownBits(Src, 0, &CI);
1296 if (Known.isNonNegative()) {
Craig Topperbb4069e2017-07-07 23:16:26 +00001297 Value *ZExt = Builder.CreateZExt(Src, DestTy);
Sanjay Patel4b198802016-02-01 22:23:39 +00001298 return replaceInstUsesWith(CI, ZExt);
Philip Reames9ae15202015-02-14 00:05:36 +00001299 }
1300
Chris Lattnerc3aca382010-01-10 00:58:42 +00001301 // Attempt to extend the entire input expression tree to the destination
1302 // type. Only do this if the dest type is a simple type, don't convert the
1303 // expression tree to something weird like i93 unless the source is also
1304 // strange.
Sanjay Patel2217f752017-01-31 17:25:42 +00001305 if ((DestTy->isVectorTy() || shouldChangeType(SrcTy, DestTy)) &&
Sanjay Patele2834412015-09-09 14:54:29 +00001306 canEvaluateSExtd(Src, DestTy)) {
Chris Lattner2fff10c2010-01-10 07:40:50 +00001307 // Okay, we can transform this! Insert the new expression now.
1308 DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"
Weiming Zhao24fbef52015-12-17 19:53:41 +00001309 " to avoid sign extend: " << CI << '\n');
Chris Lattner2fff10c2010-01-10 07:40:50 +00001310 Value *Res = EvaluateInDifferentType(Src, DestTy, true);
1311 assert(Res->getType() == DestTy);
1312
Chris Lattnerc3aca382010-01-10 00:58:42 +00001313 uint32_t SrcBitSize = SrcTy->getScalarSizeInBits();
1314 uint32_t DestBitSize = DestTy->getScalarSizeInBits();
Chris Lattner2fff10c2010-01-10 07:40:50 +00001315
1316 // If the high bits are already filled with sign bit, just replace this
1317 // cast with the result.
Hal Finkel60db0582014-09-07 18:57:58 +00001318 if (ComputeNumSignBits(Res, 0, &CI) > DestBitSize - SrcBitSize)
Sanjay Patel4b198802016-02-01 22:23:39 +00001319 return replaceInstUsesWith(CI, Res);
Craig Topper3529aa52013-01-24 05:22:40 +00001320
Chris Lattner2fff10c2010-01-10 07:40:50 +00001321 // We need to emit a shl + ashr to do the sign extend.
1322 Value *ShAmt = ConstantInt::get(DestTy, DestBitSize-SrcBitSize);
Craig Topperbb4069e2017-07-07 23:16:26 +00001323 return BinaryOperator::CreateAShr(Builder.CreateShl(Res, ShAmt, "sext"),
Chris Lattner2fff10c2010-01-10 07:40:50 +00001324 ShAmt);
Chris Lattnerc3aca382010-01-10 00:58:42 +00001325 }
Chris Lattner2b295a02010-01-04 07:53:58 +00001326
Sanjay Pateladf2ab12017-02-23 16:26:03 +00001327 // If the input is a trunc from the destination type, then turn sext(trunc(x))
Chris Lattner43f2fa62010-01-18 22:19:16 +00001328 // into shifts.
Sanjay Pateladf2ab12017-02-23 16:26:03 +00001329 Value *X;
1330 if (match(Src, m_OneUse(m_Trunc(m_Value(X)))) && X->getType() == DestTy) {
1331 // sext(trunc(X)) --> ashr(shl(X, C), C)
1332 unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
1333 unsigned DestBitSize = DestTy->getScalarSizeInBits();
1334 Constant *ShAmt = ConstantInt::get(DestTy, DestBitSize - SrcBitSize);
Craig Topperbb4069e2017-07-07 23:16:26 +00001335 return BinaryOperator::CreateAShr(Builder.CreateShl(X, ShAmt), ShAmt);
Sanjay Pateladf2ab12017-02-23 16:26:03 +00001336 }
Nate Begeman7aa18bf2010-12-17 23:12:19 +00001337
Benjamin Kramer398b8c52011-04-01 20:09:03 +00001338 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Src))
1339 return transformSExtICmp(ICI, CI);
Bill Wendling5e360552010-12-17 23:27:41 +00001340
Chris Lattner2b295a02010-01-04 07:53:58 +00001341 // If the input is a shl/ashr pair of a same constant, then this is a sign
1342 // extension from a smaller value. If we could trust arbitrary bitwidth
1343 // integers, we could turn this into a truncate to the smaller bit and then
1344 // use a sext for the whole extension. Since we don't, look deeper and check
1345 // for a truncate. If the source and dest are the same type, eliminate the
1346 // trunc and extend and just do shifts. For example, turn:
1347 // %a = trunc i32 %i to i8
1348 // %b = shl i8 %a, 6
1349 // %c = ashr i8 %b, 6
1350 // %d = sext i8 %c to i32
1351 // into:
1352 // %a = shl i32 %i, 30
1353 // %d = ashr i32 %a, 30
Craig Topperf40110f2014-04-25 05:29:35 +00001354 Value *A = nullptr;
Chris Lattnerc95a7a22010-01-10 01:04:31 +00001355 // TODO: Eventually this could be subsumed by EvaluateInDifferentType.
Craig Topperf40110f2014-04-25 05:29:35 +00001356 ConstantInt *BA = nullptr, *CA = nullptr;
Chris Lattnerc95a7a22010-01-10 01:04:31 +00001357 if (match(Src, m_AShr(m_Shl(m_Trunc(m_Value(A)), m_ConstantInt(BA)),
Chris Lattner2b295a02010-01-04 07:53:58 +00001358 m_ConstantInt(CA))) &&
Chris Lattnerc95a7a22010-01-10 01:04:31 +00001359 BA == CA && A->getType() == CI.getType()) {
1360 unsigned MidSize = Src->getType()->getScalarSizeInBits();
1361 unsigned SrcDstSize = CI.getType()->getScalarSizeInBits();
1362 unsigned ShAmt = CA->getZExtValue()+SrcDstSize-MidSize;
1363 Constant *ShAmtV = ConstantInt::get(CI.getType(), ShAmt);
Craig Topperbb4069e2017-07-07 23:16:26 +00001364 A = Builder.CreateShl(A, ShAmtV, CI.getName());
Chris Lattnerc95a7a22010-01-10 01:04:31 +00001365 return BinaryOperator::CreateAShr(A, ShAmtV);
Chris Lattner2b295a02010-01-04 07:53:58 +00001366 }
Craig Topper3529aa52013-01-24 05:22:40 +00001367
Craig Topperf40110f2014-04-25 05:29:35 +00001368 return nullptr;
Chris Lattner2b295a02010-01-04 07:53:58 +00001369}
1370
1371
Sanjay Patel2fbab9d82015-09-09 14:34:26 +00001372/// Return a Constant* for the specified floating-point constant if it fits
Chris Lattner2b295a02010-01-04 07:53:58 +00001373/// in the specified FP type without changing its value.
Sanjay Patele2834412015-09-09 14:54:29 +00001374static Constant *fitsInFPType(ConstantFP *CFP, const fltSemantics &Sem) {
Chris Lattner2b295a02010-01-04 07:53:58 +00001375 bool losesInfo;
1376 APFloat F = CFP->getValueAPF();
1377 (void)F.convert(Sem, APFloat::rmNearestTiesToEven, &losesInfo);
1378 if (!losesInfo)
1379 return ConstantFP::get(CFP->getContext(), F);
Craig Topperf40110f2014-04-25 05:29:35 +00001380 return nullptr;
Chris Lattner2b295a02010-01-04 07:53:58 +00001381}
1382
Sanjay Patel68e4cb32017-02-23 16:39:51 +00001383/// Look through floating-point extensions until we get the source value.
Sanjay Patele2834412015-09-09 14:54:29 +00001384static Value *lookThroughFPExtensions(Value *V) {
Sanjay Patel68e4cb32017-02-23 16:39:51 +00001385 while (auto *FPExt = dyn_cast<FPExtInst>(V))
1386 V = FPExt->getOperand(0);
Craig Topper3529aa52013-01-24 05:22:40 +00001387
Chris Lattner2b295a02010-01-04 07:53:58 +00001388 // If this value is a constant, return the constant in the smallest FP type
1389 // that can accurately represent it. This allows us to turn
1390 // (float)((double)X+2.0) into x+2.0f.
Sanjay Patel68e4cb32017-02-23 16:39:51 +00001391 if (auto *CFP = dyn_cast<ConstantFP>(V)) {
Chris Lattner2b295a02010-01-04 07:53:58 +00001392 if (CFP->getType() == Type::getPPC_FP128Ty(V->getContext()))
1393 return V; // No constant folding of this.
Dan Gohman518cda42011-12-17 00:04:22 +00001394 // See if the value can be truncated to half and then reextended.
Stephan Bergmann17c7f702016-12-14 11:57:17 +00001395 if (Value *V = fitsInFPType(CFP, APFloat::IEEEhalf()))
Dan Gohman518cda42011-12-17 00:04:22 +00001396 return V;
Chris Lattner2b295a02010-01-04 07:53:58 +00001397 // See if the value can be truncated to float and then reextended.
Stephan Bergmann17c7f702016-12-14 11:57:17 +00001398 if (Value *V = fitsInFPType(CFP, APFloat::IEEEsingle()))
Chris Lattner2b295a02010-01-04 07:53:58 +00001399 return V;
Benjamin Kramerccce8ba2010-01-05 13:12:22 +00001400 if (CFP->getType()->isDoubleTy())
Chris Lattner2b295a02010-01-04 07:53:58 +00001401 return V; // Won't shrink.
Stephan Bergmann17c7f702016-12-14 11:57:17 +00001402 if (Value *V = fitsInFPType(CFP, APFloat::IEEEdouble()))
Chris Lattner2b295a02010-01-04 07:53:58 +00001403 return V;
1404 // Don't try to shrink to various long double types.
1405 }
Craig Topper3529aa52013-01-24 05:22:40 +00001406
Chris Lattner2b295a02010-01-04 07:53:58 +00001407 return V;
1408}
1409
1410Instruction *InstCombiner::visitFPTrunc(FPTruncInst &CI) {
1411 if (Instruction *I = commonCastTransforms(CI))
1412 return I;
Stephen Canonc4549642013-11-28 21:38:05 +00001413 // If we have fptrunc(OpI (fpextend x), (fpextend y)), we would like to
Sanjay Patel5a7bdc92015-11-21 16:16:29 +00001414 // simplify this expression to avoid one or more of the trunc/extend
Stephen Canonc4549642013-11-28 21:38:05 +00001415 // operations if we can do so without changing the numerical results.
1416 //
1417 // The exact manner in which the widths of the operands interact to limit
1418 // what we can and cannot do safely varies from operation to operation, and
1419 // is explained below in the various case statements.
Chris Lattner2b295a02010-01-04 07:53:58 +00001420 BinaryOperator *OpI = dyn_cast<BinaryOperator>(CI.getOperand(0));
1421 if (OpI && OpI->hasOneUse()) {
Sanjay Patele2834412015-09-09 14:54:29 +00001422 Value *LHSOrig = lookThroughFPExtensions(OpI->getOperand(0));
1423 Value *RHSOrig = lookThroughFPExtensions(OpI->getOperand(1));
Stephen Canonc4549642013-11-28 21:38:05 +00001424 unsigned OpWidth = OpI->getType()->getFPMantissaWidth();
1425 unsigned LHSWidth = LHSOrig->getType()->getFPMantissaWidth();
1426 unsigned RHSWidth = RHSOrig->getType()->getFPMantissaWidth();
1427 unsigned SrcWidth = std::max(LHSWidth, RHSWidth);
1428 unsigned DstWidth = CI.getType()->getFPMantissaWidth();
Chris Lattner2b295a02010-01-04 07:53:58 +00001429 switch (OpI->getOpcode()) {
Stephen Canonc4549642013-11-28 21:38:05 +00001430 default: break;
1431 case Instruction::FAdd:
1432 case Instruction::FSub:
1433 // For addition and subtraction, the infinitely precise result can
1434 // essentially be arbitrarily wide; proving that double rounding
1435 // will not occur because the result of OpI is exact (as we will for
1436 // FMul, for example) is hopeless. However, we *can* nonetheless
1437 // frequently know that double rounding cannot occur (or that it is
Alp Tokercb402912014-01-24 17:20:08 +00001438 // innocuous) by taking advantage of the specific structure of
Stephen Canonc4549642013-11-28 21:38:05 +00001439 // infinitely-precise results that admit double rounding.
1440 //
Alp Tokercb402912014-01-24 17:20:08 +00001441 // Specifically, if OpWidth >= 2*DstWdith+1 and DstWidth is sufficient
Stephen Canonc4549642013-11-28 21:38:05 +00001442 // to represent both sources, we can guarantee that the double
1443 // rounding is innocuous (See p50 of Figueroa's 2000 PhD thesis,
1444 // "A Rigorous Framework for Fully Supporting the IEEE Standard ..."
1445 // for proof of this fact).
1446 //
1447 // Note: Figueroa does not consider the case where DstFormat !=
1448 // SrcFormat. It's possible (likely even!) that this analysis
1449 // could be tightened for those cases, but they are rare (the main
1450 // case of interest here is (float)((double)float + float)).
1451 if (OpWidth >= 2*DstWidth+1 && DstWidth >= SrcWidth) {
1452 if (LHSOrig->getType() != CI.getType())
Craig Topperbb4069e2017-07-07 23:16:26 +00001453 LHSOrig = Builder.CreateFPExt(LHSOrig, CI.getType());
Stephen Canonc4549642013-11-28 21:38:05 +00001454 if (RHSOrig->getType() != CI.getType())
Craig Topperbb4069e2017-07-07 23:16:26 +00001455 RHSOrig = Builder.CreateFPExt(RHSOrig, CI.getType());
Owen Anderson48b842e2014-01-18 00:48:14 +00001456 Instruction *RI =
1457 BinaryOperator::Create(OpI->getOpcode(), LHSOrig, RHSOrig);
1458 RI->copyFastMathFlags(OpI);
1459 return RI;
Chris Lattner2b295a02010-01-04 07:53:58 +00001460 }
Stephen Canonc4549642013-11-28 21:38:05 +00001461 break;
1462 case Instruction::FMul:
1463 // For multiplication, the infinitely precise result has at most
1464 // LHSWidth + RHSWidth significant bits; if OpWidth is sufficient
1465 // that such a value can be exactly represented, then no double
1466 // rounding can possibly occur; we can safely perform the operation
1467 // in the destination format if it can represent both sources.
1468 if (OpWidth >= LHSWidth + RHSWidth && DstWidth >= SrcWidth) {
1469 if (LHSOrig->getType() != CI.getType())
Craig Topperbb4069e2017-07-07 23:16:26 +00001470 LHSOrig = Builder.CreateFPExt(LHSOrig, CI.getType());
Stephen Canonc4549642013-11-28 21:38:05 +00001471 if (RHSOrig->getType() != CI.getType())
Craig Topperbb4069e2017-07-07 23:16:26 +00001472 RHSOrig = Builder.CreateFPExt(RHSOrig, CI.getType());
Owen Anderson48b842e2014-01-18 00:48:14 +00001473 Instruction *RI =
1474 BinaryOperator::CreateFMul(LHSOrig, RHSOrig);
1475 RI->copyFastMathFlags(OpI);
1476 return RI;
Stephen Canonc4549642013-11-28 21:38:05 +00001477 }
1478 break;
1479 case Instruction::FDiv:
1480 // For division, we use again use the bound from Figueroa's
1481 // dissertation. I am entirely certain that this bound can be
1482 // tightened in the unbalanced operand case by an analysis based on
1483 // the diophantine rational approximation bound, but the well-known
1484 // condition used here is a good conservative first pass.
1485 // TODO: Tighten bound via rigorous analysis of the unbalanced case.
1486 if (OpWidth >= 2*DstWidth && DstWidth >= SrcWidth) {
1487 if (LHSOrig->getType() != CI.getType())
Craig Topperbb4069e2017-07-07 23:16:26 +00001488 LHSOrig = Builder.CreateFPExt(LHSOrig, CI.getType());
Stephen Canonc4549642013-11-28 21:38:05 +00001489 if (RHSOrig->getType() != CI.getType())
Craig Topperbb4069e2017-07-07 23:16:26 +00001490 RHSOrig = Builder.CreateFPExt(RHSOrig, CI.getType());
Owen Anderson48b842e2014-01-18 00:48:14 +00001491 Instruction *RI =
1492 BinaryOperator::CreateFDiv(LHSOrig, RHSOrig);
1493 RI->copyFastMathFlags(OpI);
1494 return RI;
Stephen Canonc4549642013-11-28 21:38:05 +00001495 }
1496 break;
1497 case Instruction::FRem:
1498 // Remainder is straightforward. Remainder is always exact, so the
1499 // type of OpI doesn't enter into things at all. We simply evaluate
1500 // in whichever source type is larger, then convert to the
1501 // destination type.
Steven Wuf179d122014-12-12 18:48:37 +00001502 if (SrcWidth == OpWidth)
Steven Wu1f7402a2014-12-12 17:21:54 +00001503 break;
Steven Wu1f7402a2014-12-12 17:21:54 +00001504 if (LHSWidth < SrcWidth)
Craig Topperbb4069e2017-07-07 23:16:26 +00001505 LHSOrig = Builder.CreateFPExt(LHSOrig, RHSOrig->getType());
Steven Wu1f7402a2014-12-12 17:21:54 +00001506 else if (RHSWidth <= SrcWidth)
Craig Topperbb4069e2017-07-07 23:16:26 +00001507 RHSOrig = Builder.CreateFPExt(RHSOrig, LHSOrig->getType());
Steven Wu1f7402a2014-12-12 17:21:54 +00001508 if (LHSOrig != OpI->getOperand(0) || RHSOrig != OpI->getOperand(1)) {
Craig Topperbb4069e2017-07-07 23:16:26 +00001509 Value *ExactResult = Builder.CreateFRem(LHSOrig, RHSOrig);
Steven Wu1f7402a2014-12-12 17:21:54 +00001510 if (Instruction *RI = dyn_cast<Instruction>(ExactResult))
1511 RI->copyFastMathFlags(OpI);
1512 return CastInst::CreateFPCast(ExactResult, CI.getType());
1513 }
Chris Lattner2b295a02010-01-04 07:53:58 +00001514 }
Owen Andersondbf0ca52013-01-10 22:06:52 +00001515
1516 // (fptrunc (fneg x)) -> (fneg (fptrunc x))
1517 if (BinaryOperator::isFNeg(OpI)) {
Craig Topperbb4069e2017-07-07 23:16:26 +00001518 Value *InnerTrunc = Builder.CreateFPTrunc(OpI->getOperand(1),
1519 CI.getType());
Owen Anderson48b842e2014-01-18 00:48:14 +00001520 Instruction *RI = BinaryOperator::CreateFNeg(InnerTrunc);
1521 RI->copyFastMathFlags(OpI);
1522 return RI;
Owen Andersondbf0ca52013-01-10 22:06:52 +00001523 }
Chris Lattner2b295a02010-01-04 07:53:58 +00001524 }
Owen Andersondbf0ca52013-01-10 22:06:52 +00001525
Owen Anderson5797bfd2013-10-03 21:08:05 +00001526 // (fptrunc (select cond, R1, Cst)) -->
1527 // (select cond, (fptrunc R1), (fptrunc Cst))
James Molloy134bec22015-08-11 09:12:57 +00001528 //
1529 // - but only if this isn't part of a min/max operation, else we'll
1530 // ruin min/max canonical form which is to have the select and
1531 // compare's operands be of the same type with no casts to look through.
1532 Value *LHS, *RHS;
Owen Anderson5797bfd2013-10-03 21:08:05 +00001533 SelectInst *SI = dyn_cast<SelectInst>(CI.getOperand(0));
1534 if (SI &&
1535 (isa<ConstantFP>(SI->getOperand(1)) ||
James Molloy134bec22015-08-11 09:12:57 +00001536 isa<ConstantFP>(SI->getOperand(2))) &&
1537 matchSelectPattern(SI, LHS, RHS).Flavor == SPF_UNKNOWN) {
Craig Topperbb4069e2017-07-07 23:16:26 +00001538 Value *LHSTrunc = Builder.CreateFPTrunc(SI->getOperand(1), CI.getType());
1539 Value *RHSTrunc = Builder.CreateFPTrunc(SI->getOperand(2), CI.getType());
Owen Anderson5797bfd2013-10-03 21:08:05 +00001540 return SelectInst::Create(SI->getOperand(0), LHSTrunc, RHSTrunc);
1541 }
1542
Owen Andersondbf0ca52013-01-10 22:06:52 +00001543 IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI.getOperand(0));
1544 if (II) {
1545 switch (II->getIntrinsicID()) {
Matt Arsenault72333442017-01-17 00:10:40 +00001546 default: break;
Matt Arsenault954a6242017-01-23 23:55:08 +00001547 case Intrinsic::fabs:
1548 case Intrinsic::ceil:
1549 case Intrinsic::floor:
1550 case Intrinsic::rint:
1551 case Intrinsic::round:
1552 case Intrinsic::nearbyint:
1553 case Intrinsic::trunc: {
Matt Arsenault6b00d402017-03-20 21:59:24 +00001554 Value *Src = II->getArgOperand(0);
1555 if (!Src->hasOneUse())
1556 break;
1557
1558 // Except for fabs, this transformation requires the input of the unary FP
1559 // operation to be itself an fpext from the type to which we're
1560 // truncating.
1561 if (II->getIntrinsicID() != Intrinsic::fabs) {
1562 FPExtInst *FPExtSrc = dyn_cast<FPExtInst>(Src);
1563 if (!FPExtSrc || FPExtSrc->getOperand(0)->getType() != CI.getType())
1564 break;
1565 }
1566
Matt Arsenault954a6242017-01-23 23:55:08 +00001567 // Do unary FP operation on smaller type.
Matt Arsenault72333442017-01-17 00:10:40 +00001568 // (fptrunc (fabs x)) -> (fabs (fptrunc x))
Craig Topperbb4069e2017-07-07 23:16:26 +00001569 Value *InnerTrunc = Builder.CreateFPTrunc(Src, CI.getType());
Matt Arsenault72333442017-01-17 00:10:40 +00001570 Type *IntrinsicType[] = { CI.getType() };
1571 Function *Overload = Intrinsic::getDeclaration(
1572 CI.getModule(), II->getIntrinsicID(), IntrinsicType);
Owen Andersondbf0ca52013-01-10 22:06:52 +00001573
Matt Arsenault72333442017-01-17 00:10:40 +00001574 SmallVector<OperandBundleDef, 1> OpBundles;
1575 II->getOperandBundlesAsDefs(OpBundles);
David Majnemer231a68c2016-04-29 08:07:20 +00001576
Matt Arsenault72333442017-01-17 00:10:40 +00001577 Value *Args[] = { InnerTrunc };
1578 CallInst *NewCI = CallInst::Create(Overload, Args,
1579 OpBundles, II->getName());
1580 NewCI->copyFastMathFlags(II);
1581 return NewCI;
1582 }
Owen Andersondbf0ca52013-01-10 22:06:52 +00001583 }
1584 }
1585
Craig Topperbb4069e2017-07-07 23:16:26 +00001586 if (Instruction *I = shrinkInsertElt(CI, Builder))
Sanjay Patelfe970512017-03-07 23:27:14 +00001587 return I;
1588
Craig Topperf40110f2014-04-25 05:29:35 +00001589 return nullptr;
Chris Lattner2b295a02010-01-04 07:53:58 +00001590}
1591
1592Instruction *InstCombiner::visitFPExt(CastInst &CI) {
1593 return commonCastTransforms(CI);
1594}
1595
Mehdi Aminib9a0fa42015-02-16 21:47:54 +00001596// fpto{s/u}i({u/s}itofp(X)) --> X or zext(X) or sext(X) or trunc(X)
1597// This is safe if the intermediate type has enough bits in its mantissa to
1598// accurately represent all values of X. For example, this won't work with
1599// i64 -> float -> i64.
1600Instruction *InstCombiner::FoldItoFPtoI(Instruction &FI) {
1601 if (!isa<UIToFPInst>(FI.getOperand(0)) && !isa<SIToFPInst>(FI.getOperand(0)))
1602 return nullptr;
1603 Instruction *OpI = cast<Instruction>(FI.getOperand(0));
1604
1605 Value *SrcI = OpI->getOperand(0);
1606 Type *FITy = FI.getType();
1607 Type *OpITy = OpI->getType();
1608 Type *SrcTy = SrcI->getType();
1609 bool IsInputSigned = isa<SIToFPInst>(OpI);
1610 bool IsOutputSigned = isa<FPToSIInst>(FI);
1611
1612 // We can safely assume the conversion won't overflow the output range,
1613 // because (for example) (uint8_t)18293.f is undefined behavior.
1614
1615 // Since we can assume the conversion won't overflow, our decision as to
1616 // whether the input will fit in the float should depend on the minimum
1617 // of the input range and output range.
1618
1619 // This means this is also safe for a signed input and unsigned output, since
1620 // a negative input would lead to undefined behavior.
1621 int InputSize = (int)SrcTy->getScalarSizeInBits() - IsInputSigned;
1622 int OutputSize = (int)FITy->getScalarSizeInBits() - IsOutputSigned;
1623 int ActualSize = std::min(InputSize, OutputSize);
1624
1625 if (ActualSize <= OpITy->getFPMantissaWidth()) {
1626 if (FITy->getScalarSizeInBits() > SrcTy->getScalarSizeInBits()) {
1627 if (IsInputSigned && IsOutputSigned)
1628 return new SExtInst(SrcI, FITy);
1629 return new ZExtInst(SrcI, FITy);
1630 }
1631 if (FITy->getScalarSizeInBits() < SrcTy->getScalarSizeInBits())
1632 return new TruncInst(SrcI, FITy);
1633 if (SrcTy == FITy)
Sanjay Patel4b198802016-02-01 22:23:39 +00001634 return replaceInstUsesWith(FI, SrcI);
Mehdi Aminib9a0fa42015-02-16 21:47:54 +00001635 return new BitCastInst(SrcI, FITy);
1636 }
1637 return nullptr;
1638}
1639
Chris Lattner2b295a02010-01-04 07:53:58 +00001640Instruction *InstCombiner::visitFPToUI(FPToUIInst &FI) {
1641 Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0));
Craig Topperf40110f2014-04-25 05:29:35 +00001642 if (!OpI)
Chris Lattner2b295a02010-01-04 07:53:58 +00001643 return commonCastTransforms(FI);
1644
Mehdi Aminib9a0fa42015-02-16 21:47:54 +00001645 if (Instruction *I = FoldItoFPtoI(FI))
1646 return I;
Chris Lattner2b295a02010-01-04 07:53:58 +00001647
1648 return commonCastTransforms(FI);
1649}
1650
1651Instruction *InstCombiner::visitFPToSI(FPToSIInst &FI) {
1652 Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0));
Craig Topperf40110f2014-04-25 05:29:35 +00001653 if (!OpI)
Chris Lattner2b295a02010-01-04 07:53:58 +00001654 return commonCastTransforms(FI);
Craig Topper3529aa52013-01-24 05:22:40 +00001655
Mehdi Aminib9a0fa42015-02-16 21:47:54 +00001656 if (Instruction *I = FoldItoFPtoI(FI))
1657 return I;
Craig Topper3529aa52013-01-24 05:22:40 +00001658
Chris Lattner2b295a02010-01-04 07:53:58 +00001659 return commonCastTransforms(FI);
1660}
1661
1662Instruction *InstCombiner::visitUIToFP(CastInst &CI) {
1663 return commonCastTransforms(CI);
1664}
1665
1666Instruction *InstCombiner::visitSIToFP(CastInst &CI) {
1667 return commonCastTransforms(CI);
1668}
1669
Chris Lattner2b295a02010-01-04 07:53:58 +00001670Instruction *InstCombiner::visitIntToPtr(IntToPtrInst &CI) {
Dan Gohman949458d2010-02-02 01:44:02 +00001671 // If the source integer type is not the intptr_t type for this target, do a
1672 // trunc or zext to the intptr_t type, then inttoptr of it. This allows the
1673 // cast to be exposed to other transforms.
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001674 unsigned AS = CI.getAddressSpace();
1675 if (CI.getOperand(0)->getType()->getScalarSizeInBits() !=
1676 DL.getPointerSizeInBits(AS)) {
1677 Type *Ty = DL.getIntPtrType(CI.getContext(), AS);
1678 if (CI.getType()->isVectorTy()) // Handle vectors of pointers.
1679 Ty = VectorType::get(Ty, CI.getType()->getVectorNumElements());
Benjamin Kramer944e0ab2013-02-05 20:22:40 +00001680
Craig Topperbb4069e2017-07-07 23:16:26 +00001681 Value *P = Builder.CreateZExtOrTrunc(CI.getOperand(0), Ty);
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001682 return new IntToPtrInst(P, CI.getType());
Chris Lattner2b295a02010-01-04 07:53:58 +00001683 }
Craig Topper3529aa52013-01-24 05:22:40 +00001684
Chris Lattner2b295a02010-01-04 07:53:58 +00001685 if (Instruction *I = commonCastTransforms(CI))
1686 return I;
1687
Craig Topperf40110f2014-04-25 05:29:35 +00001688 return nullptr;
Chris Lattner2b295a02010-01-04 07:53:58 +00001689}
1690
Chris Lattnera93c63c2010-01-05 22:21:18 +00001691/// @brief Implement the transforms for cast of pointer (bitcast/ptrtoint)
1692Instruction *InstCombiner::commonPointerCastTransforms(CastInst &CI) {
1693 Value *Src = CI.getOperand(0);
Craig Topper3529aa52013-01-24 05:22:40 +00001694
Chris Lattnera93c63c2010-01-05 22:21:18 +00001695 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
1696 // If casting the result of a getelementptr instruction with no offset, turn
1697 // this into a cast of the original pointer!
Jingyue Wu77145d92014-06-06 21:52:55 +00001698 if (GEP->hasAllZeroIndices() &&
1699 // If CI is an addrspacecast and GEP changes the poiner type, merging
1700 // GEP into CI would undo canonicalizing addrspacecast with different
1701 // pointer types, causing infinite loops.
1702 (!isa<AddrSpaceCastInst>(CI) ||
Sanjoy Dasf09c1e32017-04-18 22:00:54 +00001703 GEP->getType() == GEP->getPointerOperandType())) {
Chris Lattnera93c63c2010-01-05 22:21:18 +00001704 // Changing the cast operand is usually not a good idea but it is safe
Craig Topper3529aa52013-01-24 05:22:40 +00001705 // here because the pointer operand is being replaced with another
Chris Lattnera93c63c2010-01-05 22:21:18 +00001706 // pointer operand so the opcode doesn't need to change.
1707 Worklist.Add(GEP);
1708 CI.setOperand(0, GEP->getOperand(0));
1709 return &CI;
1710 }
Chris Lattnera93c63c2010-01-05 22:21:18 +00001711 }
Craig Topper3529aa52013-01-24 05:22:40 +00001712
Chris Lattnera93c63c2010-01-05 22:21:18 +00001713 return commonCastTransforms(CI);
1714}
1715
1716Instruction *InstCombiner::visitPtrToInt(PtrToIntInst &CI) {
Dan Gohman949458d2010-02-02 01:44:02 +00001717 // If the destination integer type is not the intptr_t type for this target,
1718 // do a ptrtoint to intptr_t then do a trunc or zext. This allows the cast
1719 // to be exposed to other transforms.
Benjamin Kramere4778752013-02-05 19:21:56 +00001720
Matt Arsenault745101d2013-08-21 19:53:10 +00001721 Type *Ty = CI.getType();
1722 unsigned AS = CI.getPointerAddressSpace();
1723
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001724 if (Ty->getScalarSizeInBits() == DL.getPointerSizeInBits(AS))
Matt Arsenault745101d2013-08-21 19:53:10 +00001725 return commonPointerCastTransforms(CI);
1726
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001727 Type *PtrTy = DL.getIntPtrType(CI.getContext(), AS);
Matt Arsenault745101d2013-08-21 19:53:10 +00001728 if (Ty->isVectorTy()) // Handle vectors of pointers.
1729 PtrTy = VectorType::get(PtrTy, Ty->getVectorNumElements());
1730
Craig Topperbb4069e2017-07-07 23:16:26 +00001731 Value *P = Builder.CreatePtrToInt(CI.getOperand(0), PtrTy);
Matt Arsenault745101d2013-08-21 19:53:10 +00001732 return CastInst::CreateIntegerCast(P, Ty, /*isSigned=*/false);
Chris Lattnera93c63c2010-01-05 22:21:18 +00001733}
1734
Sanjay Patel2fbab9d82015-09-09 14:34:26 +00001735/// This input value (which is known to have vector type) is being zero extended
1736/// or truncated to the specified vector type.
1737/// Try to replace it with a shuffle (and vector/vector bitcast) if possible.
Chris Lattner02b0df52010-05-08 21:50:26 +00001738///
1739/// The source and destination vector types may have different element types.
Sanjay Patele2834412015-09-09 14:54:29 +00001740static Instruction *optimizeVectorResize(Value *InVal, VectorType *DestTy,
Chris Lattner02b0df52010-05-08 21:50:26 +00001741 InstCombiner &IC) {
1742 // We can only do this optimization if the output is a multiple of the input
1743 // element size, or the input is a multiple of the output element size.
1744 // Convert the input type to have the same element type as the output.
Chris Lattner229907c2011-07-18 04:54:35 +00001745 VectorType *SrcTy = cast<VectorType>(InVal->getType());
Craig Topper3529aa52013-01-24 05:22:40 +00001746
Chris Lattner02b0df52010-05-08 21:50:26 +00001747 if (SrcTy->getElementType() != DestTy->getElementType()) {
1748 // The input types don't need to be identical, but for now they must be the
1749 // same size. There is no specific reason we couldn't handle things like
1750 // <4 x i16> -> <4 x i32> by bitcasting to <2 x i32> but haven't gotten
Craig Topper3529aa52013-01-24 05:22:40 +00001751 // there yet.
Chris Lattner02b0df52010-05-08 21:50:26 +00001752 if (SrcTy->getElementType()->getPrimitiveSizeInBits() !=
1753 DestTy->getElementType()->getPrimitiveSizeInBits())
Craig Topperf40110f2014-04-25 05:29:35 +00001754 return nullptr;
Craig Topper3529aa52013-01-24 05:22:40 +00001755
Chris Lattner02b0df52010-05-08 21:50:26 +00001756 SrcTy = VectorType::get(DestTy->getElementType(), SrcTy->getNumElements());
Craig Topperbb4069e2017-07-07 23:16:26 +00001757 InVal = IC.Builder.CreateBitCast(InVal, SrcTy);
Chris Lattner02b0df52010-05-08 21:50:26 +00001758 }
Craig Topper3529aa52013-01-24 05:22:40 +00001759
Chris Lattner02b0df52010-05-08 21:50:26 +00001760 // Now that the element types match, get the shuffle mask and RHS of the
1761 // shuffle to use, which depends on whether we're increasing or decreasing the
1762 // size of the input.
Chris Lattner8213c8a2012-02-06 21:56:39 +00001763 SmallVector<uint32_t, 16> ShuffleMask;
Chris Lattner02b0df52010-05-08 21:50:26 +00001764 Value *V2;
Craig Topper3529aa52013-01-24 05:22:40 +00001765
Chris Lattner02b0df52010-05-08 21:50:26 +00001766 if (SrcTy->getNumElements() > DestTy->getNumElements()) {
1767 // If we're shrinking the number of elements, just shuffle in the low
1768 // elements from the input and use undef as the second shuffle input.
1769 V2 = UndefValue::get(SrcTy);
1770 for (unsigned i = 0, e = DestTy->getNumElements(); i != e; ++i)
Chris Lattner8213c8a2012-02-06 21:56:39 +00001771 ShuffleMask.push_back(i);
Craig Topper3529aa52013-01-24 05:22:40 +00001772
Chris Lattner02b0df52010-05-08 21:50:26 +00001773 } else {
1774 // If we're increasing the number of elements, shuffle in all of the
1775 // elements from InVal and fill the rest of the result elements with zeros
1776 // from a constant zero.
1777 V2 = Constant::getNullValue(SrcTy);
1778 unsigned SrcElts = SrcTy->getNumElements();
1779 for (unsigned i = 0, e = SrcElts; i != e; ++i)
Chris Lattner8213c8a2012-02-06 21:56:39 +00001780 ShuffleMask.push_back(i);
Chris Lattner02b0df52010-05-08 21:50:26 +00001781
1782 // The excess elements reference the first element of the zero input.
Chris Lattner8213c8a2012-02-06 21:56:39 +00001783 for (unsigned i = 0, e = DestTy->getNumElements()-SrcElts; i != e; ++i)
1784 ShuffleMask.push_back(SrcElts);
Chris Lattner02b0df52010-05-08 21:50:26 +00001785 }
Craig Topper3529aa52013-01-24 05:22:40 +00001786
Chris Lattner8213c8a2012-02-06 21:56:39 +00001787 return new ShuffleVectorInst(InVal, V2,
1788 ConstantDataVector::get(V2->getContext(),
1789 ShuffleMask));
Chris Lattner02b0df52010-05-08 21:50:26 +00001790}
1791
Chris Lattner229907c2011-07-18 04:54:35 +00001792static bool isMultipleOfTypeSize(unsigned Value, Type *Ty) {
Chris Lattnerdd660102010-08-28 01:20:38 +00001793 return Value % Ty->getPrimitiveSizeInBits() == 0;
1794}
1795
Chris Lattner229907c2011-07-18 04:54:35 +00001796static unsigned getTypeSizeIndex(unsigned Value, Type *Ty) {
Chris Lattnerdd660102010-08-28 01:20:38 +00001797 return Value / Ty->getPrimitiveSizeInBits();
1798}
1799
Sanjay Patel2fbab9d82015-09-09 14:34:26 +00001800/// V is a value which is inserted into a vector of VecEltTy.
1801/// Look through the value to see if we can decompose it into
Chris Lattnerdd660102010-08-28 01:20:38 +00001802/// insertions into the vector. See the example in the comment for
1803/// OptimizeIntegerToVectorInsertions for the pattern this handles.
1804/// The type of V is always a non-zero multiple of VecEltTy's size.
Richard Sandifordfeb34712013-08-12 07:26:09 +00001805/// Shift is the number of bits between the lsb of V and the lsb of
1806/// the vector.
Chris Lattnerdd660102010-08-28 01:20:38 +00001807///
1808/// This returns false if the pattern can't be matched or true if it can,
1809/// filling in Elements with the elements found here.
Sanjay Patele2834412015-09-09 14:54:29 +00001810static bool collectInsertionElements(Value *V, unsigned Shift,
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001811 SmallVectorImpl<Value *> &Elements,
1812 Type *VecEltTy, bool isBigEndian) {
Richard Sandifordfeb34712013-08-12 07:26:09 +00001813 assert(isMultipleOfTypeSize(Shift, VecEltTy) &&
1814 "Shift should be a multiple of the element type size");
1815
Chris Lattner50df36a2010-08-28 03:36:51 +00001816 // Undef values never contribute useful bits to the result.
1817 if (isa<UndefValue>(V)) return true;
Craig Topper3529aa52013-01-24 05:22:40 +00001818
Chris Lattnerdd660102010-08-28 01:20:38 +00001819 // If we got down to a value of the right type, we win, try inserting into the
1820 // right element.
1821 if (V->getType() == VecEltTy) {
Chris Lattnerd0214f32010-08-28 01:50:57 +00001822 // Inserting null doesn't actually insert any elements.
1823 if (Constant *C = dyn_cast<Constant>(V))
1824 if (C->isNullValue())
1825 return true;
Craig Topper3529aa52013-01-24 05:22:40 +00001826
Richard Sandifordfeb34712013-08-12 07:26:09 +00001827 unsigned ElementIndex = getTypeSizeIndex(Shift, VecEltTy);
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001828 if (isBigEndian)
Richard Sandifordfeb34712013-08-12 07:26:09 +00001829 ElementIndex = Elements.size() - ElementIndex - 1;
1830
Chris Lattnerdd660102010-08-28 01:20:38 +00001831 // Fail if multiple elements are inserted into this slot.
Craig Topperf40110f2014-04-25 05:29:35 +00001832 if (Elements[ElementIndex])
Chris Lattnerdd660102010-08-28 01:20:38 +00001833 return false;
Craig Topper3529aa52013-01-24 05:22:40 +00001834
Chris Lattnerdd660102010-08-28 01:20:38 +00001835 Elements[ElementIndex] = V;
1836 return true;
1837 }
Craig Topper3529aa52013-01-24 05:22:40 +00001838
Chris Lattnerd0214f32010-08-28 01:50:57 +00001839 if (Constant *C = dyn_cast<Constant>(V)) {
Chris Lattnerdd660102010-08-28 01:20:38 +00001840 // Figure out the # elements this provides, and bitcast it or slice it up
1841 // as required.
Chris Lattnerd0214f32010-08-28 01:50:57 +00001842 unsigned NumElts = getTypeSizeIndex(C->getType()->getPrimitiveSizeInBits(),
1843 VecEltTy);
1844 // If the constant is the size of a vector element, we just need to bitcast
1845 // it to the right type so it gets properly inserted.
1846 if (NumElts == 1)
Sanjay Patele2834412015-09-09 14:54:29 +00001847 return collectInsertionElements(ConstantExpr::getBitCast(C, VecEltTy),
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001848 Shift, Elements, VecEltTy, isBigEndian);
Craig Topper3529aa52013-01-24 05:22:40 +00001849
Chris Lattnerd0214f32010-08-28 01:50:57 +00001850 // Okay, this is a constant that covers multiple elements. Slice it up into
1851 // pieces and insert each element-sized piece into the vector.
1852 if (!isa<IntegerType>(C->getType()))
1853 C = ConstantExpr::getBitCast(C, IntegerType::get(V->getContext(),
1854 C->getType()->getPrimitiveSizeInBits()));
1855 unsigned ElementSize = VecEltTy->getPrimitiveSizeInBits();
Chris Lattner229907c2011-07-18 04:54:35 +00001856 Type *ElementIntTy = IntegerType::get(C->getContext(), ElementSize);
Craig Topper3529aa52013-01-24 05:22:40 +00001857
Chris Lattnerd0214f32010-08-28 01:50:57 +00001858 for (unsigned i = 0; i != NumElts; ++i) {
Richard Sandifordfeb34712013-08-12 07:26:09 +00001859 unsigned ShiftI = Shift+i*ElementSize;
Chris Lattnerd0214f32010-08-28 01:50:57 +00001860 Constant *Piece = ConstantExpr::getLShr(C, ConstantInt::get(C->getType(),
Richard Sandifordfeb34712013-08-12 07:26:09 +00001861 ShiftI));
Chris Lattnerd0214f32010-08-28 01:50:57 +00001862 Piece = ConstantExpr::getTrunc(Piece, ElementIntTy);
Sanjay Patele2834412015-09-09 14:54:29 +00001863 if (!collectInsertionElements(Piece, ShiftI, Elements, VecEltTy,
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001864 isBigEndian))
Chris Lattnerd0214f32010-08-28 01:50:57 +00001865 return false;
1866 }
1867 return true;
1868 }
Craig Topper3529aa52013-01-24 05:22:40 +00001869
Chris Lattnerdd660102010-08-28 01:20:38 +00001870 if (!V->hasOneUse()) return false;
Craig Topper3529aa52013-01-24 05:22:40 +00001871
Chris Lattnerdd660102010-08-28 01:20:38 +00001872 Instruction *I = dyn_cast<Instruction>(V);
Craig Topperf40110f2014-04-25 05:29:35 +00001873 if (!I) return false;
Chris Lattnerdd660102010-08-28 01:20:38 +00001874 switch (I->getOpcode()) {
1875 default: return false; // Unhandled case.
1876 case Instruction::BitCast:
Sanjay Patele2834412015-09-09 14:54:29 +00001877 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001878 isBigEndian);
Chris Lattnerdd660102010-08-28 01:20:38 +00001879 case Instruction::ZExt:
1880 if (!isMultipleOfTypeSize(
1881 I->getOperand(0)->getType()->getPrimitiveSizeInBits(),
1882 VecEltTy))
1883 return false;
Sanjay Patele2834412015-09-09 14:54:29 +00001884 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001885 isBigEndian);
Chris Lattnerdd660102010-08-28 01:20:38 +00001886 case Instruction::Or:
Sanjay Patele2834412015-09-09 14:54:29 +00001887 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001888 isBigEndian) &&
Sanjay Patele2834412015-09-09 14:54:29 +00001889 collectInsertionElements(I->getOperand(1), Shift, Elements, VecEltTy,
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001890 isBigEndian);
Chris Lattnerdd660102010-08-28 01:20:38 +00001891 case Instruction::Shl: {
1892 // Must be shifting by a constant that is a multiple of the element size.
1893 ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1));
Craig Topperf40110f2014-04-25 05:29:35 +00001894 if (!CI) return false;
Richard Sandifordfeb34712013-08-12 07:26:09 +00001895 Shift += CI->getZExtValue();
1896 if (!isMultipleOfTypeSize(Shift, VecEltTy)) return false;
Sanjay Patele2834412015-09-09 14:54:29 +00001897 return collectInsertionElements(I->getOperand(0), Shift, Elements, VecEltTy,
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001898 isBigEndian);
Chris Lattnerdd660102010-08-28 01:20:38 +00001899 }
Craig Topper3529aa52013-01-24 05:22:40 +00001900
Chris Lattnerdd660102010-08-28 01:20:38 +00001901 }
1902}
1903
1904
Sanjay Patel2fbab9d82015-09-09 14:34:26 +00001905/// If the input is an 'or' instruction, we may be doing shifts and ors to
1906/// assemble the elements of the vector manually.
Chris Lattnerdd660102010-08-28 01:20:38 +00001907/// Try to rip the code out and replace it with insertelements. This is to
1908/// optimize code like this:
1909///
1910/// %tmp37 = bitcast float %inc to i32
1911/// %tmp38 = zext i32 %tmp37 to i64
1912/// %tmp31 = bitcast float %inc5 to i32
1913/// %tmp32 = zext i32 %tmp31 to i64
1914/// %tmp33 = shl i64 %tmp32, 32
1915/// %ins35 = or i64 %tmp33, %tmp38
1916/// %tmp43 = bitcast i64 %ins35 to <2 x float>
1917///
1918/// Into two insertelements that do "buildvector{%inc, %inc5}".
Sanjay Patele2834412015-09-09 14:54:29 +00001919static Value *optimizeIntegerToVectorInsertions(BitCastInst &CI,
Chris Lattnerdd660102010-08-28 01:20:38 +00001920 InstCombiner &IC) {
Chris Lattner229907c2011-07-18 04:54:35 +00001921 VectorType *DestVecTy = cast<VectorType>(CI.getType());
Chris Lattnerdd660102010-08-28 01:20:38 +00001922 Value *IntInput = CI.getOperand(0);
1923
1924 SmallVector<Value*, 8> Elements(DestVecTy->getNumElements());
Sanjay Patele2834412015-09-09 14:54:29 +00001925 if (!collectInsertionElements(IntInput, 0, Elements,
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001926 DestVecTy->getElementType(),
1927 IC.getDataLayout().isBigEndian()))
Craig Topperf40110f2014-04-25 05:29:35 +00001928 return nullptr;
Chris Lattnerdd660102010-08-28 01:20:38 +00001929
1930 // If we succeeded, we know that all of the element are specified by Elements
1931 // or are zero if Elements has a null entry. Recast this as a set of
1932 // insertions.
1933 Value *Result = Constant::getNullValue(CI.getType());
1934 for (unsigned i = 0, e = Elements.size(); i != e; ++i) {
Craig Topperf40110f2014-04-25 05:29:35 +00001935 if (!Elements[i]) continue; // Unset element.
Craig Topper3529aa52013-01-24 05:22:40 +00001936
Craig Topperbb4069e2017-07-07 23:16:26 +00001937 Result = IC.Builder.CreateInsertElement(Result, Elements[i],
1938 IC.Builder.getInt32(i));
Chris Lattnerdd660102010-08-28 01:20:38 +00001939 }
Craig Topper3529aa52013-01-24 05:22:40 +00001940
Chris Lattnerdd660102010-08-28 01:20:38 +00001941 return Result;
1942}
1943
Sanjay Patel1d49fc92015-12-12 16:44:48 +00001944/// Canonicalize scalar bitcasts of extracted elements into a bitcast of the
1945/// vector followed by extract element. The backend tends to handle bitcasts of
1946/// vectors better than bitcasts of scalars because vector registers are
1947/// usually not type-specific like scalar integer or scalar floating-point.
1948static Instruction *canonicalizeBitCastExtElt(BitCastInst &BitCast,
Craig Toppercb220392017-07-06 23:18:43 +00001949 InstCombiner &IC) {
Sanjay Patelc83fd952015-12-10 17:09:28 +00001950 // TODO: Create and use a pattern matcher for ExtractElementInst.
1951 auto *ExtElt = dyn_cast<ExtractElementInst>(BitCast.getOperand(0));
1952 if (!ExtElt || !ExtElt->hasOneUse())
1953 return nullptr;
1954
Sanjay Patel1d49fc92015-12-12 16:44:48 +00001955 // The bitcast must be to a vectorizable type, otherwise we can't make a new
1956 // type to extract from.
1957 Type *DestType = BitCast.getType();
1958 if (!VectorType::isValidElementType(DestType))
Sanjay Patelc83fd952015-12-10 17:09:28 +00001959 return nullptr;
1960
Sanjay Patel1d49fc92015-12-12 16:44:48 +00001961 unsigned NumElts = ExtElt->getVectorOperandType()->getNumElements();
1962 auto *NewVecType = VectorType::get(DestType, NumElts);
Craig Topperbb4069e2017-07-07 23:16:26 +00001963 auto *NewBC = IC.Builder.CreateBitCast(ExtElt->getVectorOperand(),
1964 NewVecType, "bc");
Sanjay Patel1d49fc92015-12-12 16:44:48 +00001965 return ExtractElementInst::Create(NewBC, ExtElt->getIndexOperand());
Sanjay Patelc83fd952015-12-10 17:09:28 +00001966}
1967
Sanjay Patele359eaa2016-11-22 22:05:48 +00001968/// Change the type of a bitwise logic operation if we can eliminate a bitcast.
1969static Instruction *foldBitCastBitwiseLogic(BitCastInst &BitCast,
1970 InstCombiner::BuilderTy &Builder) {
Sanjay Patele359eaa2016-11-22 22:05:48 +00001971 Type *DestTy = BitCast.getType();
Sanjay Patel1e6ca442016-11-22 22:54:36 +00001972 BinaryOperator *BO;
Craig Topper95d23472017-07-09 07:04:00 +00001973 if (!DestTy->isIntOrIntVectorTy() ||
Sanjay Patel1e6ca442016-11-22 22:54:36 +00001974 !match(BitCast.getOperand(0), m_OneUse(m_BinOp(BO))) ||
1975 !BO->isBitwiseLogicOp())
Sanjay Patele359eaa2016-11-22 22:05:48 +00001976 return nullptr;
1977
1978 // FIXME: This transform is restricted to vector types to avoid backend
1979 // problems caused by creating potentially illegal operations. If a fix-up is
1980 // added to handle that situation, we can remove this check.
1981 if (!DestTy->isVectorTy() || !BO->getType()->isVectorTy())
1982 return nullptr;
1983
1984 Value *X;
1985 if (match(BO->getOperand(0), m_OneUse(m_BitCast(m_Value(X)))) &&
1986 X->getType() == DestTy && !isa<Constant>(X)) {
1987 // bitcast(logic(bitcast(X), Y)) --> logic'(X, bitcast(Y))
1988 Value *CastedOp1 = Builder.CreateBitCast(BO->getOperand(1), DestTy);
Sanjay Patel1e6ca442016-11-22 22:54:36 +00001989 return BinaryOperator::Create(BO->getOpcode(), X, CastedOp1);
Sanjay Patele359eaa2016-11-22 22:05:48 +00001990 }
1991
1992 if (match(BO->getOperand(1), m_OneUse(m_BitCast(m_Value(X)))) &&
1993 X->getType() == DestTy && !isa<Constant>(X)) {
1994 // bitcast(logic(Y, bitcast(X))) --> logic'(bitcast(Y), X)
1995 Value *CastedOp0 = Builder.CreateBitCast(BO->getOperand(0), DestTy);
Sanjay Patel1e6ca442016-11-22 22:54:36 +00001996 return BinaryOperator::Create(BO->getOpcode(), CastedOp0, X);
Sanjay Patele359eaa2016-11-22 22:05:48 +00001997 }
1998
Sanjay Pateld1e81192017-06-22 15:46:54 +00001999 // Canonicalize vector bitcasts to come before vector bitwise logic with a
2000 // constant. This eases recognition of special constants for later ops.
2001 // Example:
2002 // icmp u/s (a ^ signmask), (b ^ signmask) --> icmp s/u a, b
2003 Constant *C;
2004 if (match(BO->getOperand(1), m_Constant(C))) {
2005 // bitcast (logic X, C) --> logic (bitcast X, C')
2006 Value *CastedOp0 = Builder.CreateBitCast(BO->getOperand(0), DestTy);
2007 Value *CastedC = ConstantExpr::getBitCast(C, DestTy);
2008 return BinaryOperator::Create(BO->getOpcode(), CastedOp0, CastedC);
2009 }
2010
Sanjay Patele359eaa2016-11-22 22:05:48 +00002011 return nullptr;
2012}
2013
Sanjay Patelb7f8cb62016-12-03 15:25:16 +00002014/// Change the type of a select if we can eliminate a bitcast.
2015static Instruction *foldBitCastSelect(BitCastInst &BitCast,
2016 InstCombiner::BuilderTy &Builder) {
2017 Value *Cond, *TVal, *FVal;
2018 if (!match(BitCast.getOperand(0),
2019 m_OneUse(m_Select(m_Value(Cond), m_Value(TVal), m_Value(FVal)))))
2020 return nullptr;
2021
2022 // A vector select must maintain the same number of elements in its operands.
2023 Type *CondTy = Cond->getType();
2024 Type *DestTy = BitCast.getType();
2025 if (CondTy->isVectorTy()) {
2026 if (!DestTy->isVectorTy())
2027 return nullptr;
2028 if (DestTy->getVectorNumElements() != CondTy->getVectorNumElements())
2029 return nullptr;
2030 }
2031
2032 // FIXME: This transform is restricted from changing the select between
2033 // scalars and vectors to avoid backend problems caused by creating
2034 // potentially illegal operations. If a fix-up is added to handle that
2035 // situation, we can remove this check.
2036 if (DestTy->isVectorTy() != TVal->getType()->isVectorTy())
2037 return nullptr;
2038
2039 auto *Sel = cast<Instruction>(BitCast.getOperand(0));
2040 Value *X;
2041 if (match(TVal, m_OneUse(m_BitCast(m_Value(X)))) && X->getType() == DestTy &&
2042 !isa<Constant>(X)) {
2043 // bitcast(select(Cond, bitcast(X), Y)) --> select'(Cond, X, bitcast(Y))
2044 Value *CastedVal = Builder.CreateBitCast(FVal, DestTy);
2045 return SelectInst::Create(Cond, X, CastedVal, "", nullptr, Sel);
2046 }
2047
2048 if (match(FVal, m_OneUse(m_BitCast(m_Value(X)))) && X->getType() == DestTy &&
2049 !isa<Constant>(X)) {
2050 // bitcast(select(Cond, Y, bitcast(X))) --> select'(Cond, bitcast(Y), X)
2051 Value *CastedVal = Builder.CreateBitCast(TVal, DestTy);
2052 return SelectInst::Create(Cond, CastedVal, X, "", nullptr, Sel);
2053 }
2054
2055 return nullptr;
2056}
2057
Guozhi Weiae541f62016-10-25 20:43:42 +00002058/// Check if all users of CI are StoreInsts.
2059static bool hasStoreUsersOnly(CastInst &CI) {
2060 for (User *U : CI.users()) {
2061 if (!isa<StoreInst>(U))
2062 return false;
2063 }
2064 return true;
2065}
2066
2067/// This function handles following case
2068///
2069/// A -> B cast
2070/// PHI
2071/// B -> A cast
2072///
2073/// All the related PHI nodes can be replaced by new PHI nodes with type A.
2074/// The uses of \p CI can be changed to the new PHI node corresponding to \p PN.
2075Instruction *InstCombiner::optimizeBitCastFromPhi(CastInst &CI, PHINode *PN) {
2076 // BitCast used by Store can be handled in InstCombineLoadStoreAlloca.cpp.
2077 if (hasStoreUsersOnly(CI))
2078 return nullptr;
2079
2080 Value *Src = CI.getOperand(0);
2081 Type *SrcTy = Src->getType(); // Type B
2082 Type *DestTy = CI.getType(); // Type A
2083
2084 SmallVector<PHINode *, 4> PhiWorklist;
2085 SmallSetVector<PHINode *, 4> OldPhiNodes;
2086
2087 // Find all of the A->B casts and PHI nodes.
2088 // We need to inpect all related PHI nodes, but PHIs can be cyclic, so
2089 // OldPhiNodes is used to track all known PHI nodes, before adding a new
2090 // PHI to PhiWorklist, it is checked against and added to OldPhiNodes first.
2091 PhiWorklist.push_back(PN);
2092 OldPhiNodes.insert(PN);
2093 while (!PhiWorklist.empty()) {
2094 auto *OldPN = PhiWorklist.pop_back_val();
2095 for (Value *IncValue : OldPN->incoming_values()) {
2096 if (isa<Constant>(IncValue))
2097 continue;
2098
2099 if (auto *LI = dyn_cast<LoadInst>(IncValue)) {
2100 // If there is a sequence of one or more load instructions, each loaded
2101 // value is used as address of later load instruction, bitcast is
2102 // necessary to change the value type, don't optimize it. For
2103 // simplicity we give up if the load address comes from another load.
2104 Value *Addr = LI->getOperand(0);
2105 if (Addr == &CI || isa<LoadInst>(Addr))
2106 return nullptr;
2107 if (LI->hasOneUse() && LI->isSimple())
2108 continue;
2109 // If a LoadInst has more than one use, changing the type of loaded
2110 // value may create another bitcast.
2111 return nullptr;
2112 }
2113
2114 if (auto *PNode = dyn_cast<PHINode>(IncValue)) {
2115 if (OldPhiNodes.insert(PNode))
2116 PhiWorklist.push_back(PNode);
2117 continue;
2118 }
2119
2120 auto *BCI = dyn_cast<BitCastInst>(IncValue);
2121 // We can't handle other instructions.
2122 if (!BCI)
2123 return nullptr;
2124
2125 // Verify it's a A->B cast.
2126 Type *TyA = BCI->getOperand(0)->getType();
2127 Type *TyB = BCI->getType();
2128 if (TyA != DestTy || TyB != SrcTy)
2129 return nullptr;
2130 }
2131 }
2132
2133 // For each old PHI node, create a corresponding new PHI node with a type A.
2134 SmallDenseMap<PHINode *, PHINode *> NewPNodes;
2135 for (auto *OldPN : OldPhiNodes) {
Craig Topperbb4069e2017-07-07 23:16:26 +00002136 Builder.SetInsertPoint(OldPN);
2137 PHINode *NewPN = Builder.CreatePHI(DestTy, OldPN->getNumOperands());
Guozhi Weiae541f62016-10-25 20:43:42 +00002138 NewPNodes[OldPN] = NewPN;
2139 }
2140
2141 // Fill in the operands of new PHI nodes.
2142 for (auto *OldPN : OldPhiNodes) {
2143 PHINode *NewPN = NewPNodes[OldPN];
2144 for (unsigned j = 0, e = OldPN->getNumOperands(); j != e; ++j) {
2145 Value *V = OldPN->getOperand(j);
2146 Value *NewV = nullptr;
2147 if (auto *C = dyn_cast<Constant>(V)) {
2148 NewV = ConstantExpr::getBitCast(C, DestTy);
2149 } else if (auto *LI = dyn_cast<LoadInst>(V)) {
Craig Topperbb4069e2017-07-07 23:16:26 +00002150 Builder.SetInsertPoint(LI->getNextNode());
2151 NewV = Builder.CreateBitCast(LI, DestTy);
Guozhi Weiae541f62016-10-25 20:43:42 +00002152 Worklist.Add(LI);
2153 } else if (auto *BCI = dyn_cast<BitCastInst>(V)) {
2154 NewV = BCI->getOperand(0);
2155 } else if (auto *PrevPN = dyn_cast<PHINode>(V)) {
2156 NewV = NewPNodes[PrevPN];
2157 }
2158 assert(NewV);
2159 NewPN->addIncoming(NewV, OldPN->getIncomingBlock(j));
2160 }
2161 }
2162
2163 // If there is a store with type B, change it to type A.
2164 for (User *U : PN->users()) {
2165 auto *SI = dyn_cast<StoreInst>(U);
2166 if (SI && SI->isSimple() && SI->getOperand(0) == PN) {
Craig Topperbb4069e2017-07-07 23:16:26 +00002167 Builder.SetInsertPoint(SI);
Guozhi Weiae541f62016-10-25 20:43:42 +00002168 auto *NewBC =
Craig Topperbb4069e2017-07-07 23:16:26 +00002169 cast<BitCastInst>(Builder.CreateBitCast(NewPNodes[PN], SrcTy));
Guozhi Weiae541f62016-10-25 20:43:42 +00002170 SI->setOperand(0, NewBC);
2171 Worklist.Add(SI);
2172 assert(hasStoreUsersOnly(*NewBC));
2173 }
2174 }
2175
2176 return replaceInstUsesWith(CI, NewPNodes[PN]);
2177}
2178
Chris Lattner2b295a02010-01-04 07:53:58 +00002179Instruction *InstCombiner::visitBitCast(BitCastInst &CI) {
2180 // If the operands are integer typed then apply the integer transforms,
2181 // otherwise just apply the common ones.
2182 Value *Src = CI.getOperand(0);
Chris Lattner229907c2011-07-18 04:54:35 +00002183 Type *SrcTy = Src->getType();
2184 Type *DestTy = CI.getType();
Chris Lattner2b295a02010-01-04 07:53:58 +00002185
Chris Lattner2b295a02010-01-04 07:53:58 +00002186 // Get rid of casts from one type to the same type. These are useless and can
2187 // be replaced by the operand.
2188 if (DestTy == Src->getType())
Sanjay Patel4b198802016-02-01 22:23:39 +00002189 return replaceInstUsesWith(CI, Src);
Chris Lattner2b295a02010-01-04 07:53:58 +00002190
Chris Lattner229907c2011-07-18 04:54:35 +00002191 if (PointerType *DstPTy = dyn_cast<PointerType>(DestTy)) {
2192 PointerType *SrcPTy = cast<PointerType>(SrcTy);
2193 Type *DstElTy = DstPTy->getElementType();
2194 Type *SrcElTy = SrcPTy->getElementType();
Craig Topper3529aa52013-01-24 05:22:40 +00002195
Chris Lattner2b295a02010-01-04 07:53:58 +00002196 // If we are casting a alloca to a pointer to a type of the same
2197 // size, rewrite the allocation instruction to allocate the "right" type.
2198 // There is no need to modify malloc calls because it is their bitcast that
2199 // needs to be cleaned up.
2200 if (AllocaInst *AI = dyn_cast<AllocaInst>(Src))
2201 if (Instruction *V = PromoteCastOfAllocation(CI, *AI))
2202 return V;
Craig Topper3529aa52013-01-24 05:22:40 +00002203
Gerolf Hoflehner00e70922016-05-23 19:23:17 +00002204 // When the type pointed to is not sized the cast cannot be
2205 // turned into a gep.
2206 Type *PointeeType =
2207 cast<PointerType>(Src->getType()->getScalarType())->getElementType();
2208 if (!PointeeType->isSized())
2209 return nullptr;
2210
Chris Lattner2b295a02010-01-04 07:53:58 +00002211 // If the source and destination are pointers, and this cast is equivalent
2212 // to a getelementptr X, 0, 0, 0... turn it into the appropriate gep.
2213 // This can enhance SROA and other transforms that want type-safe pointers.
Chris Lattner2b295a02010-01-04 07:53:58 +00002214 unsigned NumZeros = 0;
Craig Topper3529aa52013-01-24 05:22:40 +00002215 while (SrcElTy != DstElTy &&
Duncan Sands19d0b472010-02-16 11:11:14 +00002216 isa<CompositeType>(SrcElTy) && !SrcElTy->isPointerTy() &&
Chris Lattner2b295a02010-01-04 07:53:58 +00002217 SrcElTy->getNumContainedTypes() /* not "{}" */) {
Benjamin Kramer2a7404a2015-04-18 16:52:08 +00002218 SrcElTy = cast<CompositeType>(SrcElTy)->getTypeAtIndex(0U);
Chris Lattner2b295a02010-01-04 07:53:58 +00002219 ++NumZeros;
2220 }
2221
2222 // If we found a path from the src to dest, create the getelementptr now.
2223 if (SrcElTy == DstElTy) {
Craig Topperbb4069e2017-07-07 23:16:26 +00002224 SmallVector<Value *, 8> Idxs(NumZeros + 1, Builder.getInt32(0));
Jay Foadd1b78492011-07-25 09:48:08 +00002225 return GetElementPtrInst::CreateInBounds(Src, Idxs);
Chris Lattner2b295a02010-01-04 07:53:58 +00002226 }
2227 }
Craig Topper3529aa52013-01-24 05:22:40 +00002228
Chris Lattner229907c2011-07-18 04:54:35 +00002229 if (VectorType *DestVTy = dyn_cast<VectorType>(DestTy)) {
Duncan Sands19d0b472010-02-16 11:11:14 +00002230 if (DestVTy->getNumElements() == 1 && !SrcTy->isVectorTy()) {
Craig Topperbb4069e2017-07-07 23:16:26 +00002231 Value *Elem = Builder.CreateBitCast(Src, DestVTy->getElementType());
Chris Lattnera93c63c2010-01-05 22:21:18 +00002232 return InsertElementInst::Create(UndefValue::get(DestTy), Elem,
Chris Lattner2b295a02010-01-04 07:53:58 +00002233 Constant::getNullValue(Type::getInt32Ty(CI.getContext())));
Chris Lattner2b295a02010-01-04 07:53:58 +00002234 // FIXME: Canonicalize bitcast(insertelement) -> insertelement(bitcast)
2235 }
Craig Topper3529aa52013-01-24 05:22:40 +00002236
Chris Lattnerdd660102010-08-28 01:20:38 +00002237 if (isa<IntegerType>(SrcTy)) {
2238 // If this is a cast from an integer to vector, check to see if the input
2239 // is a trunc or zext of a bitcast from vector. If so, we can replace all
2240 // the casts with a shuffle and (potentially) a bitcast.
2241 if (isa<TruncInst>(Src) || isa<ZExtInst>(Src)) {
2242 CastInst *SrcCast = cast<CastInst>(Src);
2243 if (BitCastInst *BCIn = dyn_cast<BitCastInst>(SrcCast->getOperand(0)))
2244 if (isa<VectorType>(BCIn->getOperand(0)->getType()))
Sanjay Patele2834412015-09-09 14:54:29 +00002245 if (Instruction *I = optimizeVectorResize(BCIn->getOperand(0),
Chris Lattner02b0df52010-05-08 21:50:26 +00002246 cast<VectorType>(DestTy), *this))
Chris Lattnerdd660102010-08-28 01:20:38 +00002247 return I;
2248 }
Craig Topper3529aa52013-01-24 05:22:40 +00002249
Chris Lattnerdd660102010-08-28 01:20:38 +00002250 // If the input is an 'or' instruction, we may be doing shifts and ors to
2251 // assemble the elements of the vector manually. Try to rip the code out
2252 // and replace it with insertelements.
Sanjay Patele2834412015-09-09 14:54:29 +00002253 if (Value *V = optimizeIntegerToVectorInsertions(CI, *this))
Sanjay Patel4b198802016-02-01 22:23:39 +00002254 return replaceInstUsesWith(CI, V);
Chris Lattner02b0df52010-05-08 21:50:26 +00002255 }
Chris Lattner2b295a02010-01-04 07:53:58 +00002256 }
2257
Chris Lattner229907c2011-07-18 04:54:35 +00002258 if (VectorType *SrcVTy = dyn_cast<VectorType>(SrcTy)) {
Michael Ilseman74a6da92013-02-11 21:41:44 +00002259 if (SrcVTy->getNumElements() == 1) {
2260 // If our destination is not a vector, then make this a straight
2261 // scalar-scalar cast.
2262 if (!DestTy->isVectorTy()) {
2263 Value *Elem =
Craig Topperbb4069e2017-07-07 23:16:26 +00002264 Builder.CreateExtractElement(Src,
Michael Ilseman74a6da92013-02-11 21:41:44 +00002265 Constant::getNullValue(Type::getInt32Ty(CI.getContext())));
2266 return CastInst::Create(Instruction::BitCast, Elem, DestTy);
2267 }
2268
2269 // Otherwise, see if our source is an insert. If so, then use the scalar
2270 // component directly.
2271 if (InsertElementInst *IEI =
2272 dyn_cast<InsertElementInst>(CI.getOperand(0)))
2273 return CastInst::Create(Instruction::BitCast, IEI->getOperand(1),
2274 DestTy);
Chris Lattner2b295a02010-01-04 07:53:58 +00002275 }
2276 }
2277
2278 if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(Src)) {
Chris Lattnera93c63c2010-01-05 22:21:18 +00002279 // Okay, we have (bitcast (shuffle ..)). Check to see if this is
Dan Gohmaneb7111b2010-04-07 23:22:42 +00002280 // a bitcast to a vector with the same # elts.
Craig Topper3529aa52013-01-24 05:22:40 +00002281 if (SVI->hasOneUse() && DestTy->isVectorTy() &&
Matt Arsenaultfc00f7e2013-08-14 00:24:34 +00002282 DestTy->getVectorNumElements() == SVI->getType()->getNumElements() &&
Chris Lattnera93c63c2010-01-05 22:21:18 +00002283 SVI->getType()->getNumElements() ==
Matt Arsenaultfc00f7e2013-08-14 00:24:34 +00002284 SVI->getOperand(0)->getType()->getVectorNumElements()) {
Chris Lattnera93c63c2010-01-05 22:21:18 +00002285 BitCastInst *Tmp;
2286 // If either of the operands is a cast from CI.getType(), then
2287 // evaluating the shuffle in the casted destination's type will allow
2288 // us to eliminate at least one cast.
Craig Topper3529aa52013-01-24 05:22:40 +00002289 if (((Tmp = dyn_cast<BitCastInst>(SVI->getOperand(0))) &&
Chris Lattnera93c63c2010-01-05 22:21:18 +00002290 Tmp->getOperand(0)->getType() == DestTy) ||
Craig Topper3529aa52013-01-24 05:22:40 +00002291 ((Tmp = dyn_cast<BitCastInst>(SVI->getOperand(1))) &&
Chris Lattnera93c63c2010-01-05 22:21:18 +00002292 Tmp->getOperand(0)->getType() == DestTy)) {
Craig Topperbb4069e2017-07-07 23:16:26 +00002293 Value *LHS = Builder.CreateBitCast(SVI->getOperand(0), DestTy);
2294 Value *RHS = Builder.CreateBitCast(SVI->getOperand(1), DestTy);
Chris Lattnera93c63c2010-01-05 22:21:18 +00002295 // Return a new shuffle vector. Use the same element ID's, as we
2296 // know the vector types match #elts.
2297 return new ShuffleVectorInst(LHS, RHS, SVI->getOperand(2));
Chris Lattner2b295a02010-01-04 07:53:58 +00002298 }
2299 }
2300 }
Craig Topper3529aa52013-01-24 05:22:40 +00002301
Guozhi Weiae541f62016-10-25 20:43:42 +00002302 // Handle the A->B->A cast, and there is an intervening PHI node.
2303 if (PHINode *PN = dyn_cast<PHINode>(Src))
2304 if (Instruction *I = optimizeBitCastFromPhi(CI, PN))
2305 return I;
2306
Craig Toppercb220392017-07-06 23:18:43 +00002307 if (Instruction *I = canonicalizeBitCastExtElt(CI, *this))
Sanjay Patelc83fd952015-12-10 17:09:28 +00002308 return I;
2309
Craig Topperbb4069e2017-07-07 23:16:26 +00002310 if (Instruction *I = foldBitCastBitwiseLogic(CI, Builder))
Sanjay Patele359eaa2016-11-22 22:05:48 +00002311 return I;
2312
Craig Topperbb4069e2017-07-07 23:16:26 +00002313 if (Instruction *I = foldBitCastSelect(CI, Builder))
Sanjay Patelb7f8cb62016-12-03 15:25:16 +00002314 return I;
2315
Duncan Sands19d0b472010-02-16 11:11:14 +00002316 if (SrcTy->isPointerTy())
Chris Lattnera93c63c2010-01-05 22:21:18 +00002317 return commonPointerCastTransforms(CI);
2318 return commonCastTransforms(CI);
Chris Lattner2b295a02010-01-04 07:53:58 +00002319}
Matt Arsenaulta9e95ab2013-11-15 05:45:08 +00002320
2321Instruction *InstCombiner::visitAddrSpaceCast(AddrSpaceCastInst &CI) {
Manuel Jacobb4db99c2014-07-16 01:34:21 +00002322 // If the destination pointer element type is not the same as the source's
2323 // first do a bitcast to the destination type, and then the addrspacecast.
2324 // This allows the cast to be exposed to other transforms.
Jingyue Wu77145d92014-06-06 21:52:55 +00002325 Value *Src = CI.getOperand(0);
2326 PointerType *SrcTy = cast<PointerType>(Src->getType()->getScalarType());
2327 PointerType *DestTy = cast<PointerType>(CI.getType()->getScalarType());
2328
2329 Type *DestElemTy = DestTy->getElementType();
2330 if (SrcTy->getElementType() != DestElemTy) {
2331 Type *MidTy = PointerType::get(DestElemTy, SrcTy->getAddressSpace());
Jingyue Wubaabe502014-06-15 21:40:57 +00002332 if (VectorType *VT = dyn_cast<VectorType>(CI.getType())) {
2333 // Handle vectors of pointers.
2334 MidTy = VectorType::get(MidTy, VT->getNumElements());
2335 }
Jingyue Wu77145d92014-06-06 21:52:55 +00002336
Craig Topperbb4069e2017-07-07 23:16:26 +00002337 Value *NewBitCast = Builder.CreateBitCast(Src, MidTy);
Jingyue Wu77145d92014-06-06 21:52:55 +00002338 return new AddrSpaceCastInst(NewBitCast, CI.getType());
2339 }
2340
Matt Arsenault2d353d12014-01-14 20:00:45 +00002341 return commonPointerCastTransforms(CI);
Matt Arsenaulta9e95ab2013-11-15 05:45:08 +00002342}