blob: 4b5c96ccbf125dd9947ee25bf965484d42c06ba6 [file] [log] [blame]
Chris Lattnerdc67e132010-01-05 07:44:46 +00001//===- InstCombineShifts.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 visitShl, visitLShr, and visitAShr functions.
11//
12//===----------------------------------------------------------------------===//
13
Chandler Carrutha9174582015-01-22 05:25:13 +000014#include "InstCombineInternal.h"
Eli Friedman911e12f2011-07-20 21:57:23 +000015#include "llvm/Analysis/ConstantFolding.h"
Duncan Sands7f60dc12011-01-14 00:37:45 +000016#include "llvm/Analysis/InstructionSimplify.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000017#include "llvm/IR/IntrinsicInst.h"
Chandler Carruth820a9082014-03-04 11:08:18 +000018#include "llvm/IR/PatternMatch.h"
Chris Lattnerdc67e132010-01-05 07:44:46 +000019using namespace llvm;
20using namespace PatternMatch;
21
Chandler Carruth964daaa2014-04-22 02:55:47 +000022#define DEBUG_TYPE "instcombine"
23
Chris Lattnerdc67e132010-01-05 07:44:46 +000024Instruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) {
Chris Lattnerdc67e132010-01-05 07:44:46 +000025 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
Sanjay Patelcf082032017-01-13 18:08:25 +000026 assert(Op0->getType() == Op1->getType());
Chris Lattnerdc67e132010-01-05 07:44:46 +000027
Chris Lattnerdc67e132010-01-05 07:44:46 +000028 // See if we can fold away this shift.
29 if (SimplifyDemandedInstructionBits(I))
30 return &I;
31
32 // Try to fold constant and into select arguments.
33 if (isa<Constant>(Op0))
34 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
35 if (Instruction *R = FoldOpIntoSelect(I, SI))
36 return R;
37
Matt Arsenaultfed3dc82014-04-14 21:50:37 +000038 if (Constant *CUI = dyn_cast<Constant>(Op1))
Chris Lattnerdc67e132010-01-05 07:44:46 +000039 if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
40 return Res;
Benjamin Kramerb5afa652010-11-23 18:52:42 +000041
Simon Pilgrim6dd8fab2016-11-01 15:40:30 +000042 // (C1 shift (A add C2)) -> (C1 shift C2) shift A)
43 // iff A and C2 are both positive.
44 Value *A;
45 Constant *C;
46 if (match(Op0, m_Constant()) && match(Op1, m_Add(m_Value(A), m_Constant(C))))
Craig Topperd45185f2017-05-26 18:23:57 +000047 if (isKnownNonNegative(A, DL, 0, &AC, &I, &DT) &&
48 isKnownNonNegative(C, DL, 0, &AC, &I, &DT))
Simon Pilgrim6dd8fab2016-11-01 15:40:30 +000049 return BinaryOperator::Create(
Craig Topperbb4069e2017-07-07 23:16:26 +000050 I.getOpcode(), Builder.CreateBinOp(I.getOpcode(), Op0, C), A);
Simon Pilgrim6dd8fab2016-11-01 15:40:30 +000051
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +000052 // X shift (A srem B) -> X shift (A and B-1) iff B is a power of 2.
Chris Lattner6b657ae2011-02-10 05:36:31 +000053 // Because shifts by negative values (which could occur if A were negative)
54 // are undefined.
Simon Pilgrim6dd8fab2016-11-01 15:40:30 +000055 const APInt *B;
Chris Lattner6b657ae2011-02-10 05:36:31 +000056 if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Power2(B)))) {
57 // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't
58 // demand the sign bit (and many others) here??
Craig Topperbb4069e2017-07-07 23:16:26 +000059 Value *Rem = Builder.CreateAnd(A, ConstantInt::get(I.getType(), *B - 1),
60 Op1->getName());
Chris Lattner6b657ae2011-02-10 05:36:31 +000061 I.setOperand(1, Rem);
62 return &I;
63 }
Jakub Staszak538e3862012-12-09 15:37:46 +000064
Craig Topperf40110f2014-04-25 05:29:35 +000065 return nullptr;
Chris Lattnerdc67e132010-01-05 07:44:46 +000066}
67
Sanjay Patel6eaff5c2016-04-11 15:43:41 +000068/// Return true if we can simplify two logical (either left or right) shifts
Sanjay Patel65cce202017-01-16 20:05:26 +000069/// that have constant shift amounts: OuterShift (InnerShift X, C1), C2.
70static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl,
71 Instruction *InnerShift, InstCombiner &IC,
Sanjay Patel6eaff5c2016-04-11 15:43:41 +000072 Instruction *CxtI) {
Sanjay Patel65cce202017-01-16 20:05:26 +000073 assert(InnerShift->isLogicalShift() && "Unexpected instruction type");
Sanjay Patelb91bcd72016-04-11 17:35:57 +000074
Sanjay Patelab8b32d2017-01-16 19:35:45 +000075 // We need constant scalar or constant splat shifts.
Sanjay Patel65cce202017-01-16 20:05:26 +000076 const APInt *InnerShiftConst;
77 if (!match(InnerShift->getOperand(1), m_APInt(InnerShiftConst)))
Sanjay Patel6eaff5c2016-04-11 15:43:41 +000078 return false;
79
Sanjay Patel65cce202017-01-16 20:05:26 +000080 // Two logical shifts in the same direction:
81 // shl (shl X, C1), C2 --> shl X, C1 + C2
82 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
83 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
84 if (IsInnerShl == IsOuterShl)
Sanjay Patel6eaff5c2016-04-11 15:43:41 +000085 return true;
86
Sanjay Patel65cce202017-01-16 20:05:26 +000087 // Equal shift amounts in opposite directions become bitwise 'and':
88 // lshr (shl X, C), C --> and X, C'
89 // shl (lshr X, C), C --> and X, C'
Simon Pilgrim3bf2d642018-01-03 18:28:20 +000090 if (*InnerShiftConst == OuterShAmt)
Sanjay Patel6eaff5c2016-04-11 15:43:41 +000091 return true;
92
Sanjay Patelbd8b7792016-04-11 16:11:07 +000093 // If the 2nd shift is bigger than the 1st, we can fold:
Sanjay Patel65cce202017-01-16 20:05:26 +000094 // lshr (shl X, C1), C2 --> and (shl X, C1 - C2), C3
95 // shl (lshr X, C1), C2 --> and (lshr X, C1 - C2), C3
Sanjay Patelbd8b7792016-04-11 16:11:07 +000096 // but it isn't profitable unless we know the and'd out bits are already zero.
Sanjay Patel65cce202017-01-16 20:05:26 +000097 // Also, check that the inner shift is valid (less than the type width) or
98 // we'll crash trying to produce the bit mask for the 'and'.
99 unsigned TypeWidth = InnerShift->getType()->getScalarSizeInBits();
Simon Pilgrim3bf2d642018-01-03 18:28:20 +0000100 if (InnerShiftConst->ugt(OuterShAmt) && InnerShiftConst->ult(TypeWidth)) {
101 unsigned InnerShAmt = InnerShiftConst->getZExtValue();
Sanjay Patel65cce202017-01-16 20:05:26 +0000102 unsigned MaskShift =
103 IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt;
104 APInt Mask = APInt::getLowBitsSet(TypeWidth, OuterShAmt) << MaskShift;
105 if (IC.MaskedValueIsZero(InnerShift->getOperand(0), Mask, 0, CxtI))
Sanjay Patel6eaff5c2016-04-11 15:43:41 +0000106 return true;
107 }
108
109 return false;
110}
111
Sanjay Patel20aaf582017-01-15 17:55:35 +0000112/// See if we can compute the specified value, but shifted logically to the left
113/// or right by some number of bits. This should return true if the expression
114/// can be computed for the same cost as the current expression tree. This is
115/// used to eliminate extraneous shifting from things like:
Chris Lattner18d7fc82010-08-27 22:24:38 +0000116/// %C = shl i128 %A, 64
117/// %D = shl i128 %B, 96
118/// %E = or i128 %C, %D
119/// %F = lshr i128 %E, 64
Sanjay Patel20aaf582017-01-15 17:55:35 +0000120/// where the client will ask if E can be computed shifted right by 64-bits. If
121/// this succeeds, getShiftedValue() will be called to produce the value.
122static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift,
Hal Finkel60db0582014-09-07 18:57:58 +0000123 InstCombiner &IC, Instruction *CxtI) {
Chris Lattner18d7fc82010-08-27 22:24:38 +0000124 // We can always evaluate constants shifted.
125 if (isa<Constant>(V))
126 return true;
Jakub Staszak538e3862012-12-09 15:37:46 +0000127
Chris Lattner18d7fc82010-08-27 22:24:38 +0000128 Instruction *I = dyn_cast<Instruction>(V);
129 if (!I) return false;
Jakub Staszak538e3862012-12-09 15:37:46 +0000130
Chris Lattner18d7fc82010-08-27 22:24:38 +0000131 // If this is the opposite shift, we can directly reuse the input of the shift
132 // if the needed bits are already zero in the input. This allows us to reuse
133 // the value which means that we don't care if the shift has multiple uses.
134 // TODO: Handle opposite shift by exact value.
Craig Topperf40110f2014-04-25 05:29:35 +0000135 ConstantInt *CI = nullptr;
Sanjay Patel4b9c6822016-04-11 17:25:23 +0000136 if ((IsLeftShift && match(I, m_LShr(m_Value(), m_ConstantInt(CI)))) ||
137 (!IsLeftShift && match(I, m_Shl(m_Value(), m_ConstantInt(CI))))) {
Simon Pilgrim3bf2d642018-01-03 18:28:20 +0000138 if (CI->getValue() == NumBits) {
Chris Lattner18d7fc82010-08-27 22:24:38 +0000139 // TODO: Check that the input bits are already zero with MaskedValueIsZero
140#if 0
141 // If this is a truncate of a logical shr, we can truncate it to a smaller
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +0000142 // lshr iff we know that the bits we would otherwise be shifting in are
Chris Lattner18d7fc82010-08-27 22:24:38 +0000143 // already zeros.
144 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
145 uint32_t BitWidth = Ty->getScalarSizeInBits();
146 if (MaskedValueIsZero(I->getOperand(0),
147 APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) &&
148 CI->getLimitedValue(BitWidth) < BitWidth) {
149 return CanEvaluateTruncated(I->getOperand(0), Ty);
150 }
151#endif
Jakub Staszak538e3862012-12-09 15:37:46 +0000152
Chris Lattner18d7fc82010-08-27 22:24:38 +0000153 }
154 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000155
Chris Lattner18d7fc82010-08-27 22:24:38 +0000156 // We can't mutate something that has multiple uses: doing so would
157 // require duplicating the instruction in general, which isn't profitable.
158 if (!I->hasOneUse()) return false;
Jakub Staszak538e3862012-12-09 15:37:46 +0000159
Chris Lattner18d7fc82010-08-27 22:24:38 +0000160 switch (I->getOpcode()) {
161 default: return false;
162 case Instruction::And:
163 case Instruction::Or:
164 case Instruction::Xor:
165 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
Sanjay Patel20aaf582017-01-15 17:55:35 +0000166 return canEvaluateShifted(I->getOperand(0), NumBits, IsLeftShift, IC, I) &&
167 canEvaluateShifted(I->getOperand(1), NumBits, IsLeftShift, IC, I);
Jakub Staszak538e3862012-12-09 15:37:46 +0000168
Sanjay Patel6eaff5c2016-04-11 15:43:41 +0000169 case Instruction::Shl:
Sanjay Patel37129072016-04-11 17:11:55 +0000170 case Instruction::LShr:
Sanjay Patel4b9c6822016-04-11 17:25:23 +0000171 return canEvaluateShiftedShift(NumBits, IsLeftShift, I, IC, CxtI);
Chris Lattner18d7fc82010-08-27 22:24:38 +0000172
Chris Lattner18d7fc82010-08-27 22:24:38 +0000173 case Instruction::Select: {
174 SelectInst *SI = cast<SelectInst>(I);
Sanjay Patel690955f2016-01-31 16:34:11 +0000175 Value *TrueVal = SI->getTrueValue();
176 Value *FalseVal = SI->getFalseValue();
Sanjay Patel20aaf582017-01-15 17:55:35 +0000177 return canEvaluateShifted(TrueVal, NumBits, IsLeftShift, IC, SI) &&
178 canEvaluateShifted(FalseVal, NumBits, IsLeftShift, IC, SI);
Chris Lattner18d7fc82010-08-27 22:24:38 +0000179 }
180 case Instruction::PHI: {
181 // We can change a phi if we can change all operands. Note that we never
182 // get into trouble with cyclic PHIs here because we only consider
183 // instructions with a single use.
184 PHINode *PN = cast<PHINode>(I);
Pete Cooper833f34d2015-05-12 20:05:31 +0000185 for (Value *IncValue : PN->incoming_values())
Sanjay Patel20aaf582017-01-15 17:55:35 +0000186 if (!canEvaluateShifted(IncValue, NumBits, IsLeftShift, IC, PN))
Chris Lattner18d7fc82010-08-27 22:24:38 +0000187 return false;
188 return true;
189 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000190 }
Chris Lattner18d7fc82010-08-27 22:24:38 +0000191}
192
Sanjay Patel646734a2017-01-16 17:27:50 +0000193/// Fold OuterShift (InnerShift X, C1), C2.
194/// See canEvaluateShiftedShift() for the constraints on these instructions.
195static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt,
196 bool IsOuterShl,
197 InstCombiner::BuilderTy &Builder) {
198 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
199 Type *ShType = InnerShift->getType();
200 unsigned TypeWidth = ShType->getScalarSizeInBits();
201
202 // We only accept shifts-by-a-constant in canEvaluateShifted().
Sanjay Patelab8b32d2017-01-16 19:35:45 +0000203 const APInt *C1;
204 match(InnerShift->getOperand(1), m_APInt(C1));
Sanjay Patel646734a2017-01-16 17:27:50 +0000205 unsigned InnerShAmt = C1->getZExtValue();
206
207 // Change the shift amount and clear the appropriate IR flags.
208 auto NewInnerShift = [&](unsigned ShAmt) {
209 InnerShift->setOperand(1, ConstantInt::get(ShType, ShAmt));
210 if (IsInnerShl) {
211 InnerShift->setHasNoUnsignedWrap(false);
212 InnerShift->setHasNoSignedWrap(false);
213 } else {
214 InnerShift->setIsExact(false);
215 }
216 return InnerShift;
217 };
218
219 // Two logical shifts in the same direction:
220 // shl (shl X, C1), C2 --> shl X, C1 + C2
221 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
222 if (IsInnerShl == IsOuterShl) {
223 // If this is an oversized composite shift, then unsigned shifts get 0.
224 if (InnerShAmt + OuterShAmt >= TypeWidth)
225 return Constant::getNullValue(ShType);
226
227 return NewInnerShift(InnerShAmt + OuterShAmt);
228 }
229
230 // Equal shift amounts in opposite directions become bitwise 'and':
231 // lshr (shl X, C), C --> and X, C'
232 // shl (lshr X, C), C --> and X, C'
233 if (InnerShAmt == OuterShAmt) {
234 APInt Mask = IsInnerShl
235 ? APInt::getLowBitsSet(TypeWidth, TypeWidth - OuterShAmt)
236 : APInt::getHighBitsSet(TypeWidth, TypeWidth - OuterShAmt);
237 Value *And = Builder.CreateAnd(InnerShift->getOperand(0),
238 ConstantInt::get(ShType, Mask));
239 if (auto *AndI = dyn_cast<Instruction>(And)) {
240 AndI->moveBefore(InnerShift);
241 AndI->takeName(InnerShift);
242 }
243 return And;
244 }
245
246 assert(InnerShAmt > OuterShAmt &&
247 "Unexpected opposite direction logical shift pair");
248
249 // In general, we would need an 'and' for this transform, but
250 // canEvaluateShiftedShift() guarantees that the masked-off bits are not used.
251 // lshr (shl X, C1), C2 --> shl X, C1 - C2
252 // shl (lshr X, C1), C2 --> lshr X, C1 - C2
253 return NewInnerShift(InnerShAmt - OuterShAmt);
254}
255
Sanjay Patel20aaf582017-01-15 17:55:35 +0000256/// When canEvaluateShifted() returns true for an expression, this function
257/// inserts the new computation that produces the shifted value.
258static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000259 InstCombiner &IC, const DataLayout &DL) {
Chris Lattner18d7fc82010-08-27 22:24:38 +0000260 // We can always evaluate constants shifted.
261 if (Constant *C = dyn_cast<Constant>(V)) {
262 if (isLeftShift)
Craig Topperbb4069e2017-07-07 23:16:26 +0000263 V = IC.Builder.CreateShl(C, NumBits);
Chris Lattner18d7fc82010-08-27 22:24:38 +0000264 else
Craig Topperbb4069e2017-07-07 23:16:26 +0000265 V = IC.Builder.CreateLShr(C, NumBits);
Chris Lattner18d7fc82010-08-27 22:24:38 +0000266 // If we got a constantexpr back, try to simplify it with TD info.
David Majnemerd536f232016-07-29 03:27:26 +0000267 if (auto *C = dyn_cast<Constant>(V))
268 if (auto *FoldedC =
Justin Bogner99798402016-08-05 01:06:44 +0000269 ConstantFoldConstant(C, DL, &IC.getTargetLibraryInfo()))
David Majnemerd536f232016-07-29 03:27:26 +0000270 V = FoldedC;
Chris Lattner18d7fc82010-08-27 22:24:38 +0000271 return V;
272 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000273
Chris Lattner18d7fc82010-08-27 22:24:38 +0000274 Instruction *I = cast<Instruction>(V);
275 IC.Worklist.Add(I);
276
277 switch (I->getOpcode()) {
Craig Toppera2886c22012-02-07 05:05:23 +0000278 default: llvm_unreachable("Inconsistency with CanEvaluateShifted");
Chris Lattner18d7fc82010-08-27 22:24:38 +0000279 case Instruction::And:
280 case Instruction::Or:
281 case Instruction::Xor:
282 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000283 I->setOperand(
Sanjay Patel20aaf582017-01-15 17:55:35 +0000284 0, getShiftedValue(I->getOperand(0), NumBits, isLeftShift, IC, DL));
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000285 I->setOperand(
Sanjay Patel20aaf582017-01-15 17:55:35 +0000286 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
Chris Lattner18d7fc82010-08-27 22:24:38 +0000287 return I;
Jakub Staszak538e3862012-12-09 15:37:46 +0000288
Sanjay Patel646734a2017-01-16 17:27:50 +0000289 case Instruction::Shl:
290 case Instruction::LShr:
291 return foldShiftedShift(cast<BinaryOperator>(I), NumBits, isLeftShift,
Craig Topperbb4069e2017-07-07 23:16:26 +0000292 IC.Builder);
Jakub Staszak538e3862012-12-09 15:37:46 +0000293
Chris Lattner18d7fc82010-08-27 22:24:38 +0000294 case Instruction::Select:
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000295 I->setOperand(
Sanjay Patel20aaf582017-01-15 17:55:35 +0000296 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000297 I->setOperand(
Sanjay Patel20aaf582017-01-15 17:55:35 +0000298 2, getShiftedValue(I->getOperand(2), NumBits, isLeftShift, IC, DL));
Chris Lattner18d7fc82010-08-27 22:24:38 +0000299 return I;
300 case Instruction::PHI: {
301 // We can change a phi if we can change all operands. Note that we never
302 // get into trouble with cyclic PHIs here because we only consider
303 // instructions with a single use.
304 PHINode *PN = cast<PHINode>(I);
305 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
Sanjay Patel20aaf582017-01-15 17:55:35 +0000306 PN->setIncomingValue(i, getShiftedValue(PN->getIncomingValue(i), NumBits,
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000307 isLeftShift, IC, DL));
Chris Lattner18d7fc82010-08-27 22:24:38 +0000308 return PN;
309 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000310 }
Chris Lattner18d7fc82010-08-27 22:24:38 +0000311}
312
Craig Topper7dd4d322017-11-07 18:47:24 +0000313// If this is a bitwise operator or add with a constant RHS we might be able
314// to pull it through a shift.
315static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift,
316 BinaryOperator *BO,
317 const APInt &C) {
318 bool IsValid = true; // Valid only for And, Or Xor,
319 bool HighBitSet = false; // Transform ifhigh bit of constant set?
320
321 switch (BO->getOpcode()) {
322 default: IsValid = false; break; // Do not perform transform!
323 case Instruction::Add:
324 IsValid = Shift.getOpcode() == Instruction::Shl;
325 break;
326 case Instruction::Or:
327 case Instruction::Xor:
328 HighBitSet = false;
329 break;
330 case Instruction::And:
331 HighBitSet = true;
332 break;
333 }
334
335 // If this is a signed shift right, and the high bit is modified
336 // by the logical operation, do not perform the transformation.
337 // The HighBitSet boolean indicates the value of the high bit of
338 // the constant which would cause it to be modified for this
339 // operation.
340 //
341 if (IsValid && Shift.getOpcode() == Instruction::AShr)
342 IsValid = C.isNegative() == HighBitSet;
343
344 return IsValid;
345}
346
Matt Arsenaultfed3dc82014-04-14 21:50:37 +0000347Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1,
Chris Lattnerdc67e132010-01-05 07:44:46 +0000348 BinaryOperator &I) {
349 bool isLeftShift = I.getOpcode() == Instruction::Shl;
Jakub Staszak538e3862012-12-09 15:37:46 +0000350
Sanjay Patelda5682a2017-01-16 21:24:41 +0000351 const APInt *Op1C;
352 if (!match(Op1, m_APInt(Op1C)))
Matt Arsenaultfed3dc82014-04-14 21:50:37 +0000353 return nullptr;
Jakub Staszak538e3862012-12-09 15:37:46 +0000354
Chris Lattner18d7fc82010-08-27 22:24:38 +0000355 // See if we can propagate this shift into the input, this covers the trivial
356 // cast of lshr(shl(x,c1),c2) as well as other more complex cases.
357 if (I.getOpcode() != Instruction::AShr &&
Sanjay Patelda5682a2017-01-16 21:24:41 +0000358 canEvaluateShifted(Op0, Op1C->getZExtValue(), isLeftShift, *this, &I)) {
Chris Lattnerdd660102010-08-28 01:20:38 +0000359 DEBUG(dbgs() << "ICE: GetShiftedValue propagating shift through expression"
360 " to eliminate shift:\n IN: " << *Op0 << "\n SH: " << I <<"\n");
Jakub Staszak538e3862012-12-09 15:37:46 +0000361
Sanjay Patel4b198802016-02-01 22:23:39 +0000362 return replaceInstUsesWith(
Sanjay Patelda5682a2017-01-16 21:24:41 +0000363 I, getShiftedValue(Op0, Op1C->getZExtValue(), isLeftShift, *this, DL));
Chris Lattner18d7fc82010-08-27 22:24:38 +0000364 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000365
Jakub Staszak538e3862012-12-09 15:37:46 +0000366 // See if we can simplify any instructions used by the instruction whose sole
Chris Lattnerdc67e132010-01-05 07:44:46 +0000367 // purpose is to compute bits we don't care about.
Sanjay Patelda5682a2017-01-16 21:24:41 +0000368 unsigned TypeBits = Op0->getType()->getScalarSizeInBits();
Jakub Staszak538e3862012-12-09 15:37:46 +0000369
Sanjay Patelda5682a2017-01-16 21:24:41 +0000370 assert(!Op1C->uge(TypeBits) &&
Matt Arsenault6b4bed42014-04-23 16:48:40 +0000371 "Shift over the type width should have been removed already");
Jakub Staszak538e3862012-12-09 15:37:46 +0000372
Sanjay Patel8fdd87f2018-02-28 16:36:24 +0000373 if (Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I))
Sanjay Pateldb0938f2017-01-10 23:49:07 +0000374 return FoldedShift;
Jakub Staszak538e3862012-12-09 15:37:46 +0000375
Chris Lattnerdc67e132010-01-05 07:44:46 +0000376 // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2))
377 if (TruncInst *TI = dyn_cast<TruncInst>(Op0)) {
378 Instruction *TrOp = dyn_cast<Instruction>(TI->getOperand(0));
379 // If 'shift2' is an ashr, we would have to get the sign bit into a funny
380 // place. Don't try to do this transformation in this case. Also, we
381 // require that the input operand is a shift-by-constant so that we have
382 // confidence that the shifts will get folded together. We could do this
383 // xform in more cases, but it is unlikely to be profitable.
Jakub Staszak538e3862012-12-09 15:37:46 +0000384 if (TrOp && I.isLogicalShift() && TrOp->isShift() &&
Chris Lattnerdc67e132010-01-05 07:44:46 +0000385 isa<ConstantInt>(TrOp->getOperand(1))) {
386 // Okay, we'll do this xform. Make the shift of shift.
Sanjay Patelda5682a2017-01-16 21:24:41 +0000387 Constant *ShAmt =
388 ConstantExpr::getZExt(cast<Constant>(Op1), TrOp->getType());
Chris Lattnerdc67e132010-01-05 07:44:46 +0000389 // (shift2 (shift1 & 0x00FF), c2)
Craig Topperbb4069e2017-07-07 23:16:26 +0000390 Value *NSh = Builder.CreateBinOp(I.getOpcode(), TrOp, ShAmt, I.getName());
Chris Lattnerdc67e132010-01-05 07:44:46 +0000391
392 // For logical shifts, the truncation has the effect of making the high
393 // part of the register be zeros. Emulate this by inserting an AND to
394 // clear the top bits as needed. This 'and' will usually be zapped by
395 // other xforms later if dead.
396 unsigned SrcSize = TrOp->getType()->getScalarSizeInBits();
397 unsigned DstSize = TI->getType()->getScalarSizeInBits();
398 APInt MaskV(APInt::getLowBitsSet(SrcSize, DstSize));
Jakub Staszak538e3862012-12-09 15:37:46 +0000399
Chris Lattnerdc67e132010-01-05 07:44:46 +0000400 // The mask we constructed says what the trunc would do if occurring
401 // between the shifts. We want to know the effect *after* the second
402 // shift. We know that it is a logical shift by a constant, so adjust the
403 // mask as appropriate.
404 if (I.getOpcode() == Instruction::Shl)
Sanjay Patelda5682a2017-01-16 21:24:41 +0000405 MaskV <<= Op1C->getZExtValue();
Chris Lattnerdc67e132010-01-05 07:44:46 +0000406 else {
407 assert(I.getOpcode() == Instruction::LShr && "Unknown logical shift");
Craig Topperfc947bc2017-04-18 17:14:21 +0000408 MaskV.lshrInPlace(Op1C->getZExtValue());
Chris Lattnerdc67e132010-01-05 07:44:46 +0000409 }
410
411 // shift1 & 0x00FF
Craig Topperbb4069e2017-07-07 23:16:26 +0000412 Value *And = Builder.CreateAnd(NSh,
413 ConstantInt::get(I.getContext(), MaskV),
414 TI->getName());
Chris Lattnerdc67e132010-01-05 07:44:46 +0000415
416 // Return the value truncated to the interesting size.
417 return new TruncInst(And, I.getType());
418 }
419 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000420
Chris Lattnerdc67e132010-01-05 07:44:46 +0000421 if (Op0->hasOneUse()) {
422 if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
423 // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C)
424 Value *V1, *V2;
425 ConstantInt *CC;
426 switch (Op0BO->getOpcode()) {
Chris Lattner2b459fe2010-01-10 06:59:55 +0000427 default: break;
428 case Instruction::Add:
429 case Instruction::And:
430 case Instruction::Or:
431 case Instruction::Xor: {
432 // These operators commute.
433 // Turn (Y + (X >> C)) << C -> (X + (Y << C)) & (~0 << C)
434 if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() &&
435 match(Op0BO->getOperand(1), m_Shr(m_Value(V1),
436 m_Specific(Op1)))) {
437 Value *YS = // (Y << C)
Craig Topperbb4069e2017-07-07 23:16:26 +0000438 Builder.CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName());
Chris Lattner2b459fe2010-01-10 06:59:55 +0000439 // (X + (Y << C))
Craig Topperbb4069e2017-07-07 23:16:26 +0000440 Value *X = Builder.CreateBinOp(Op0BO->getOpcode(), YS, V1,
441 Op0BO->getOperand(1)->getName());
Sanjay Patelda5682a2017-01-16 21:24:41 +0000442 unsigned Op1Val = Op1C->getLimitedValue(TypeBits);
Matt Arsenaultfed3dc82014-04-14 21:50:37 +0000443
444 APInt Bits = APInt::getHighBitsSet(TypeBits, TypeBits - Op1Val);
445 Constant *Mask = ConstantInt::get(I.getContext(), Bits);
446 if (VectorType *VT = dyn_cast<VectorType>(X->getType()))
447 Mask = ConstantVector::getSplat(VT->getNumElements(), Mask);
448 return BinaryOperator::CreateAnd(X, Mask);
Chris Lattnerdc67e132010-01-05 07:44:46 +0000449 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000450
Chris Lattner2b459fe2010-01-10 06:59:55 +0000451 // Turn (Y + ((X >> C) & CC)) << C -> ((X & (CC << C)) + (Y << C))
452 Value *Op0BOOp1 = Op0BO->getOperand(1);
453 if (isLeftShift && Op0BOOp1->hasOneUse() &&
Jakub Staszak538e3862012-12-09 15:37:46 +0000454 match(Op0BOOp1,
Jakub Staszak84321852012-12-09 16:06:44 +0000455 m_And(m_OneUse(m_Shr(m_Value(V1), m_Specific(Op1))),
456 m_ConstantInt(CC)))) {
Chris Lattner2b459fe2010-01-10 06:59:55 +0000457 Value *YS = // (Y << C)
Craig Topperbb4069e2017-07-07 23:16:26 +0000458 Builder.CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName());
Chris Lattner2b459fe2010-01-10 06:59:55 +0000459 // X & (CC << C)
Craig Topperbb4069e2017-07-07 23:16:26 +0000460 Value *XM = Builder.CreateAnd(V1, ConstantExpr::getShl(CC, Op1),
461 V1->getName()+".mask");
Chris Lattner2b459fe2010-01-10 06:59:55 +0000462 return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM);
Chris Lattnerdc67e132010-01-05 07:44:46 +0000463 }
Justin Bognercd1d5aa2016-08-17 20:30:52 +0000464 LLVM_FALLTHROUGH;
Chris Lattnerdc67e132010-01-05 07:44:46 +0000465 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000466
Chris Lattner2b459fe2010-01-10 06:59:55 +0000467 case Instruction::Sub: {
468 // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C)
469 if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
470 match(Op0BO->getOperand(0), m_Shr(m_Value(V1),
471 m_Specific(Op1)))) {
472 Value *YS = // (Y << C)
Craig Topperbb4069e2017-07-07 23:16:26 +0000473 Builder.CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName());
Chris Lattner2b459fe2010-01-10 06:59:55 +0000474 // (X + (Y << C))
Craig Topperbb4069e2017-07-07 23:16:26 +0000475 Value *X = Builder.CreateBinOp(Op0BO->getOpcode(), V1, YS,
476 Op0BO->getOperand(0)->getName());
Sanjay Patelda5682a2017-01-16 21:24:41 +0000477 unsigned Op1Val = Op1C->getLimitedValue(TypeBits);
Matt Arsenaultfed3dc82014-04-14 21:50:37 +0000478
479 APInt Bits = APInt::getHighBitsSet(TypeBits, TypeBits - Op1Val);
480 Constant *Mask = ConstantInt::get(I.getContext(), Bits);
481 if (VectorType *VT = dyn_cast<VectorType>(X->getType()))
482 Mask = ConstantVector::getSplat(VT->getNumElements(), Mask);
483 return BinaryOperator::CreateAnd(X, Mask);
Chris Lattner2b459fe2010-01-10 06:59:55 +0000484 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000485
Chris Lattner2b459fe2010-01-10 06:59:55 +0000486 // Turn (((X >> C)&CC) + Y) << C -> (X + (Y << C)) & (CC << C)
487 if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
488 match(Op0BO->getOperand(0),
Jakub Staszak84321852012-12-09 16:06:44 +0000489 m_And(m_OneUse(m_Shr(m_Value(V1), m_Value(V2))),
490 m_ConstantInt(CC))) && V2 == Op1) {
Chris Lattner2b459fe2010-01-10 06:59:55 +0000491 Value *YS = // (Y << C)
Craig Topperbb4069e2017-07-07 23:16:26 +0000492 Builder.CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName());
Chris Lattner2b459fe2010-01-10 06:59:55 +0000493 // X & (CC << C)
Craig Topperbb4069e2017-07-07 23:16:26 +0000494 Value *XM = Builder.CreateAnd(V1, ConstantExpr::getShl(CC, Op1),
495 V1->getName()+".mask");
Jakub Staszak538e3862012-12-09 15:37:46 +0000496
Chris Lattner2b459fe2010-01-10 06:59:55 +0000497 return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS);
498 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000499
Chris Lattner2b459fe2010-01-10 06:59:55 +0000500 break;
501 }
502 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000503
504
Sanjay Patelfc3d8f02014-07-22 04:57:06 +0000505 // If the operand is a bitwise operator with a constant RHS, and the
Chris Lattnerdc67e132010-01-05 07:44:46 +0000506 // shift is the only use, we can pull it out of the shift.
Craig Topper65dd32a2017-08-05 20:00:42 +0000507 const APInt *Op0C;
508 if (match(Op0BO->getOperand(1), m_APInt(Op0C))) {
Craig Topper7dd4d322017-11-07 18:47:24 +0000509 if (canShiftBinOpWithConstantRHS(I, Op0BO, *Op0C)) {
Craig Topper65dd32a2017-08-05 20:00:42 +0000510 Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
511 cast<Constant>(Op0BO->getOperand(1)), Op1);
Jakub Staszak538e3862012-12-09 15:37:46 +0000512
Chris Lattnerdc67e132010-01-05 07:44:46 +0000513 Value *NewShift =
Craig Topperbb4069e2017-07-07 23:16:26 +0000514 Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1);
Chris Lattnerdc67e132010-01-05 07:44:46 +0000515 NewShift->takeName(Op0BO);
Jakub Staszak538e3862012-12-09 15:37:46 +0000516
Chris Lattnerdc67e132010-01-05 07:44:46 +0000517 return BinaryOperator::Create(Op0BO->getOpcode(), NewShift,
518 NewRHS);
519 }
520 }
Craig Topper364359e2017-08-08 20:14:11 +0000521
522 // If the operand is a subtract with a constant LHS, and the shift
523 // is the only use, we can pull it out of the shift.
524 // This folds (shl (sub C1, X), C2) -> (sub (C1 << C2), (shl X, C2))
525 if (isLeftShift && Op0BO->getOpcode() == Instruction::Sub &&
526 match(Op0BO->getOperand(0), m_APInt(Op0C))) {
527 Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
528 cast<Constant>(Op0BO->getOperand(0)), Op1);
529
530 Value *NewShift = Builder.CreateShl(Op0BO->getOperand(1), Op1);
531 NewShift->takeName(Op0BO);
532
533 return BinaryOperator::CreateSub(NewRHS, NewShift);
534 }
Chris Lattnerdc67e132010-01-05 07:44:46 +0000535 }
Craig Topper7dd4d322017-11-07 18:47:24 +0000536
537 // If we have a select that conditionally executes some binary operator,
538 // see if we can pull it the select and operator through the shift.
539 //
540 // For example, turning:
541 // shl (select C, (add X, C1), X), C2
542 // Into:
543 // Y = shl X, C2
544 // select C, (add Y, C1 << C2), Y
545 Value *Cond;
546 BinaryOperator *TBO;
547 Value *FalseVal;
548 if (match(Op0, m_Select(m_Value(Cond), m_OneUse(m_BinOp(TBO)),
549 m_Value(FalseVal)))) {
550 const APInt *C;
551 if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal &&
552 match(TBO->getOperand(1), m_APInt(C)) &&
553 canShiftBinOpWithConstantRHS(I, TBO, *C)) {
554 Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
555 cast<Constant>(TBO->getOperand(1)), Op1);
556
557 Value *NewShift =
558 Builder.CreateBinOp(I.getOpcode(), FalseVal, Op1);
559 Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift,
560 NewRHS);
561 return SelectInst::Create(Cond, NewOp, NewShift);
562 }
563 }
564
565 BinaryOperator *FBO;
566 Value *TrueVal;
567 if (match(Op0, m_Select(m_Value(Cond), m_Value(TrueVal),
568 m_OneUse(m_BinOp(FBO))))) {
569 const APInt *C;
570 if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal &&
571 match(FBO->getOperand(1), m_APInt(C)) &&
572 canShiftBinOpWithConstantRHS(I, FBO, *C)) {
573 Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
574 cast<Constant>(FBO->getOperand(1)), Op1);
575
576 Value *NewShift =
577 Builder.CreateBinOp(I.getOpcode(), TrueVal, Op1);
578 Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift,
579 NewRHS);
580 return SelectInst::Create(Cond, NewShift, NewOp);
581 }
582 }
Chris Lattnerdc67e132010-01-05 07:44:46 +0000583 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000584
Craig Topperf40110f2014-04-25 05:29:35 +0000585 return nullptr;
Chris Lattnerdc67e132010-01-05 07:44:46 +0000586}
587
588Instruction *InstCombiner::visitShl(BinaryOperator &I) {
Serge Pavlov9ef66a82014-05-11 08:46:12 +0000589 if (Value *V = SimplifyVectorOp(I))
Sanjay Patel4b198802016-02-01 22:23:39 +0000590 return replaceInstUsesWith(I, V);
Serge Pavlov9ef66a82014-05-11 08:46:12 +0000591
Sanjay Patelcf082032017-01-13 18:08:25 +0000592 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
Craig Toppera4205622017-06-09 03:21:29 +0000593 if (Value *V =
594 SimplifyShlInst(Op0, Op1, I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
595 SQ.getWithInstruction(&I)))
Sanjay Patel4b198802016-02-01 22:23:39 +0000596 return replaceInstUsesWith(I, V);
Jakub Staszak538e3862012-12-09 15:37:46 +0000597
Chris Lattner6b657ae2011-02-10 05:36:31 +0000598 if (Instruction *V = commonShiftTransforms(I))
599 return V;
Jakub Staszak538e3862012-12-09 15:37:46 +0000600
Sanjay Patelb22f6c52017-01-13 18:39:09 +0000601 const APInt *ShAmtAPInt;
602 if (match(Op1, m_APInt(ShAmtAPInt))) {
603 unsigned ShAmt = ShAmtAPInt->getZExtValue();
Sanjay Patel50753f02017-01-26 22:08:10 +0000604 unsigned BitWidth = I.getType()->getScalarSizeInBits();
Sanjay Patel062adaa2017-01-29 17:11:18 +0000605 Type *Ty = I.getType();
Jakub Staszak538e3862012-12-09 15:37:46 +0000606
Sanjay Patelacd24c72017-01-13 18:52:10 +0000607 // shl (zext X), ShAmt --> zext (shl X, ShAmt)
608 // This is only valid if X would have zeros shifted out.
609 Value *X;
610 if (match(Op0, m_ZExt(m_Value(X)))) {
611 unsigned SrcWidth = X->getType()->getScalarSizeInBits();
612 if (ShAmt < SrcWidth &&
613 MaskedValueIsZero(X, APInt::getHighBitsSet(SrcWidth, ShAmt), 0, &I))
Craig Topperbb4069e2017-07-07 23:16:26 +0000614 return new ZExtInst(Builder.CreateShl(X, ShAmt), Ty);
David Majnemercb892e92017-01-04 02:21:34 +0000615 }
616
Amjad Aboud0464c5d2017-08-15 19:33:14 +0000617 // (X >> C) << C --> X & (-1 << C)
618 if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1)))) {
Sanjay Patel50753f02017-01-26 22:08:10 +0000619 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmt));
Sanjay Patel062adaa2017-01-29 17:11:18 +0000620 return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));
621 }
622
Sanjay Patel8c5f2362017-01-30 23:35:52 +0000623 // Be careful about hiding shl instructions behind bit masks. They are used
624 // to represent multiplies by a constant, and it is important that simple
625 // arithmetic expressions are still recognizable by scalar evolution.
Sanjay Patel373db5b2017-01-30 18:40:23 +0000626 // The inexact versions are deferred to DAGCombine, so we don't hide shl
627 // behind a bit mask.
Sanjay Patelc56d1cc2017-02-01 21:31:34 +0000628 const APInt *ShOp1;
Craig Topper7b66ffe2017-06-24 06:24:04 +0000629 if (match(Op0, m_Exact(m_Shr(m_Value(X), m_APInt(ShOp1))))) {
Sanjay Patelc56d1cc2017-02-01 21:31:34 +0000630 unsigned ShrAmt = ShOp1->getZExtValue();
Sanjay Patel373db5b2017-01-30 18:40:23 +0000631 if (ShrAmt < ShAmt) {
632 // If C1 < C2: (X >>?,exact C1) << C2 --> X << (C2 - C1)
633 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShrAmt);
634 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
635 NewShl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
636 NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
637 return NewShl;
638 }
639 if (ShrAmt > ShAmt) {
640 // If C1 > C2: (X >>?exact C1) << C2 --> X >>?exact (C1 - C2)
641 Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmt);
642 auto *NewShr = BinaryOperator::Create(
643 cast<BinaryOperator>(Op0)->getOpcode(), X, ShiftDiff);
644 NewShr->setIsExact(true);
645 return NewShr;
646 }
Sanjay Patel50753f02017-01-26 22:08:10 +0000647 }
648
Sanjay Patelc56d1cc2017-02-01 21:31:34 +0000649 if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1)))) {
650 unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
651 // Oversized shifts are simplified to zero in InstSimplify.
652 if (AmtSum < BitWidth)
653 // (X << C1) << C2 --> X << (C1 + C2)
654 return BinaryOperator::CreateShl(X, ConstantInt::get(Ty, AmtSum));
655 }
656
Chris Lattner6b657ae2011-02-10 05:36:31 +0000657 // If the shifted-out value is known-zero, then this is a NUW shift.
Jakub Staszak538e3862012-12-09 15:37:46 +0000658 if (!I.hasNoUnsignedWrap() &&
Sanjay Patel50753f02017-01-26 22:08:10 +0000659 MaskedValueIsZero(Op0, APInt::getHighBitsSet(BitWidth, ShAmt), 0, &I)) {
Sanjay Patel690955f2016-01-31 16:34:11 +0000660 I.setHasNoUnsignedWrap();
661 return &I;
662 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000663
Sanjay Patelcf082032017-01-13 18:08:25 +0000664 // If the shifted-out value is all signbits, then this is a NSW shift.
665 if (!I.hasNoSignedWrap() && ComputeNumSignBits(Op0, 0, &I) > ShAmt) {
Chris Lattner6b657ae2011-02-10 05:36:31 +0000666 I.setHasNoSignedWrap();
667 return &I;
668 }
669 }
Benjamin Kramer16f18ed2011-04-29 08:15:41 +0000670
Sanjay Patelf38bab72017-02-09 23:13:04 +0000671 Constant *C1;
672 if (match(Op1, m_Constant(C1))) {
673 Constant *C2;
674 Value *X;
675 // (C2 << X) << C1 --> (C2 << C1) << X
676 if (match(Op0, m_OneUse(m_Shl(m_Constant(C2), m_Value(X)))))
677 return BinaryOperator::CreateShl(ConstantExpr::getShl(C2, C1), X);
678
679 // (X * C2) << C1 --> X * (C2 << C1)
680 if (match(Op0, m_Mul(m_Value(X), m_Constant(C2))))
681 return BinaryOperator::CreateMul(X, ConstantExpr::getShl(C2, C1));
682 }
Benjamin Kramer16f18ed2011-04-29 08:15:41 +0000683
Craig Topperf40110f2014-04-25 05:29:35 +0000684 return nullptr;
Chris Lattnerdc67e132010-01-05 07:44:46 +0000685}
686
687Instruction *InstCombiner::visitLShr(BinaryOperator &I) {
Serge Pavlov9ef66a82014-05-11 08:46:12 +0000688 if (Value *V = SimplifyVectorOp(I))
Sanjay Patel4b198802016-02-01 22:23:39 +0000689 return replaceInstUsesWith(I, V);
Serge Pavlov9ef66a82014-05-11 08:46:12 +0000690
Sanjay Patelcf082032017-01-13 18:08:25 +0000691 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
Craig Toppera4205622017-06-09 03:21:29 +0000692 if (Value *V =
693 SimplifyLShrInst(Op0, Op1, I.isExact(), SQ.getWithInstruction(&I)))
Sanjay Patel4b198802016-02-01 22:23:39 +0000694 return replaceInstUsesWith(I, V);
Duncan Sands7f60dc12011-01-14 00:37:45 +0000695
Chris Lattner249da5c2010-01-23 18:49:30 +0000696 if (Instruction *R = commonShiftTransforms(I))
697 return R;
Jakub Staszak538e3862012-12-09 15:37:46 +0000698
Sanjay Patel1196d7c2017-01-30 16:11:40 +0000699 Type *Ty = I.getType();
Sanjay Patel2d4b4562017-01-13 23:04:10 +0000700 const APInt *ShAmtAPInt;
701 if (match(Op1, m_APInt(ShAmtAPInt))) {
702 unsigned ShAmt = ShAmtAPInt->getZExtValue();
Sanjay Patel1196d7c2017-01-30 16:11:40 +0000703 unsigned BitWidth = Ty->getScalarSizeInBits();
Sanjay Patel2d4b4562017-01-13 23:04:10 +0000704 auto *II = dyn_cast<IntrinsicInst>(Op0);
705 if (II && isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == ShAmt &&
706 (II->getIntrinsicID() == Intrinsic::ctlz ||
707 II->getIntrinsicID() == Intrinsic::cttz ||
708 II->getIntrinsicID() == Intrinsic::ctpop)) {
Chris Lattner249da5c2010-01-23 18:49:30 +0000709 // ctlz.i32(x)>>5 --> zext(x == 0)
710 // cttz.i32(x)>>5 --> zext(x == 0)
711 // ctpop.i32(x)>>5 --> zext(x == -1)
Sanjay Patel2d4b4562017-01-13 23:04:10 +0000712 bool IsPop = II->getIntrinsicID() == Intrinsic::ctpop;
Sanjay Patel1196d7c2017-01-30 16:11:40 +0000713 Constant *RHS = ConstantInt::getSigned(Ty, IsPop ? -1 : 0);
Craig Topperbb4069e2017-07-07 23:16:26 +0000714 Value *Cmp = Builder.CreateICmpEQ(II->getArgOperand(0), RHS);
Sanjay Patel1196d7c2017-01-30 16:11:40 +0000715 return new ZExtInst(Cmp, Ty);
Chris Lattner249da5c2010-01-23 18:49:30 +0000716 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000717
Sanjay Patel50753f02017-01-26 22:08:10 +0000718 Value *X;
Sanjay Patelc56d1cc2017-02-01 21:31:34 +0000719 const APInt *ShOp1;
720 if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1)))) {
721 unsigned ShlAmt = ShOp1->getZExtValue();
Sanjay Patel1196d7c2017-01-30 16:11:40 +0000722 if (ShlAmt < ShAmt) {
723 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);
724 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
725 // (X <<nuw C1) >>u C2 --> X >>u (C2 - C1)
Sanjay Patel062c14a2017-01-30 17:38:55 +0000726 auto *NewLShr = BinaryOperator::CreateLShr(X, ShiftDiff);
Sanjay Patel1196d7c2017-01-30 16:11:40 +0000727 NewLShr->setIsExact(I.isExact());
728 return NewLShr;
729 }
730 // (X << C1) >>u C2 --> (X >>u (C2 - C1)) & (-1 >> C2)
Craig Topperbb4069e2017-07-07 23:16:26 +0000731 Value *NewLShr = Builder.CreateLShr(X, ShiftDiff, "", I.isExact());
Sanjay Patel1196d7c2017-01-30 16:11:40 +0000732 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt));
733 return BinaryOperator::CreateAnd(NewLShr, ConstantInt::get(Ty, Mask));
734 }
Sanjay Patel0c39d562017-01-30 23:01:05 +0000735 if (ShlAmt > ShAmt) {
736 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);
737 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
738 // (X <<nuw C1) >>u C2 --> X <<nuw (C1 - C2)
739 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
740 NewShl->setHasNoUnsignedWrap(true);
741 return NewShl;
742 }
743 // (X << C1) >>u C2 --> X << (C1 - C2) & (-1 >> C2)
Craig Topperbb4069e2017-07-07 23:16:26 +0000744 Value *NewShl = Builder.CreateShl(X, ShiftDiff);
Sanjay Patel0c39d562017-01-30 23:01:05 +0000745 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt));
746 return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));
747 }
748 assert(ShlAmt == ShAmt);
749 // (X << C) >>u C --> X & (-1 >>u C)
750 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt));
751 return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));
Sanjay Patel50753f02017-01-26 22:08:10 +0000752 }
753
Sanjay Patel79e7f6b2017-08-04 15:42:47 +0000754 if (match(Op0, m_OneUse(m_ZExt(m_Value(X)))) &&
755 (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) {
Benjamin Kramerbda212a2017-08-04 16:08:41 +0000756 assert(ShAmt < X->getType()->getScalarSizeInBits() &&
757 "Big shift not simplified to zero?");
Sanjay Patel79e7f6b2017-08-04 15:42:47 +0000758 // lshr (zext iM X to iN), C --> zext (lshr X, C) to iN
759 Value *NewLShr = Builder.CreateLShr(X, ShAmt);
760 return new ZExtInst(NewLShr, Ty);
761 }
762
Sanjay Patel2e33bba2017-06-12 14:23:43 +0000763 if (match(Op0, m_SExt(m_Value(X))) &&
764 (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) {
Sanjay Patel66f7fdb2017-06-07 20:32:08 +0000765 // Are we moving the sign bit to the low bit and widening with high zeros?
766 unsigned SrcTyBitWidth = X->getType()->getScalarSizeInBits();
Sanjay Patel2e33bba2017-06-12 14:23:43 +0000767 if (ShAmt == BitWidth - 1) {
Sanjay Patel66f7fdb2017-06-07 20:32:08 +0000768 // lshr (sext i1 X to iN), N-1 --> zext X to iN
769 if (SrcTyBitWidth == 1)
770 return new ZExtInst(X, Ty);
771
772 // lshr (sext iM X to iN), N-1 --> zext (lshr X, M-1) to iN
773 if (Op0->hasOneUse()) {
Craig Topperbb4069e2017-07-07 23:16:26 +0000774 Value *NewLShr = Builder.CreateLShr(X, SrcTyBitWidth - 1);
Sanjay Patel66f7fdb2017-06-07 20:32:08 +0000775 return new ZExtInst(NewLShr, Ty);
776 }
777 }
778
Sanjay Patel2e33bba2017-06-12 14:23:43 +0000779 // lshr (sext iM X to iN), N-M --> zext (ashr X, min(N-M, M-1)) to iN
780 if (ShAmt == BitWidth - SrcTyBitWidth && Op0->hasOneUse()) {
781 // The new shift amount can't be more than the narrow source type.
782 unsigned NewShAmt = std::min(ShAmt, SrcTyBitWidth - 1);
Craig Topperbb4069e2017-07-07 23:16:26 +0000783 Value *AShr = Builder.CreateAShr(X, NewShAmt);
Sanjay Patel2e33bba2017-06-12 14:23:43 +0000784 return new ZExtInst(AShr, Ty);
785 }
Sanjay Patel66f7fdb2017-06-07 20:32:08 +0000786 }
787
Sanjay Patelc56d1cc2017-02-01 21:31:34 +0000788 if (match(Op0, m_LShr(m_Value(X), m_APInt(ShOp1)))) {
789 unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
790 // Oversized shifts are simplified to zero in InstSimplify.
791 if (AmtSum < BitWidth)
792 // (X >>u C1) >>u C2 --> X >>u (C1 + C2)
793 return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, AmtSum));
794 }
795
Chris Lattner6b657ae2011-02-10 05:36:31 +0000796 // If the shifted-out value is known-zero, then this is an exact shift.
Jakub Staszak538e3862012-12-09 15:37:46 +0000797 if (!I.isExact() &&
Sanjay Patel2d4b4562017-01-13 23:04:10 +0000798 MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) {
Chris Lattner6b657ae2011-02-10 05:36:31 +0000799 I.setIsExact();
800 return &I;
Jakub Staszak538e3862012-12-09 15:37:46 +0000801 }
Chris Lattner6b657ae2011-02-10 05:36:31 +0000802 }
Craig Topperf40110f2014-04-25 05:29:35 +0000803 return nullptr;
Chris Lattnerdc67e132010-01-05 07:44:46 +0000804}
805
806Instruction *InstCombiner::visitAShr(BinaryOperator &I) {
Serge Pavlov9ef66a82014-05-11 08:46:12 +0000807 if (Value *V = SimplifyVectorOp(I))
Sanjay Patel4b198802016-02-01 22:23:39 +0000808 return replaceInstUsesWith(I, V);
Serge Pavlov9ef66a82014-05-11 08:46:12 +0000809
Sanjay Patelcf082032017-01-13 18:08:25 +0000810 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
Craig Toppera4205622017-06-09 03:21:29 +0000811 if (Value *V =
812 SimplifyAShrInst(Op0, Op1, I.isExact(), SQ.getWithInstruction(&I)))
Sanjay Patel4b198802016-02-01 22:23:39 +0000813 return replaceInstUsesWith(I, V);
Duncan Sands7f60dc12011-01-14 00:37:45 +0000814
Chris Lattnerdc67e132010-01-05 07:44:46 +0000815 if (Instruction *R = commonShiftTransforms(I))
816 return R;
Jakub Staszak538e3862012-12-09 15:37:46 +0000817
Sanjay Patel77732d52017-01-30 17:19:32 +0000818 Type *Ty = I.getType();
819 unsigned BitWidth = Ty->getScalarSizeInBits();
Sanjay Patel5f8451a2017-01-15 16:38:19 +0000820 const APInt *ShAmtAPInt;
Simon Pilgrim5d909be2018-01-09 14:23:46 +0000821 if (match(Op1, m_APInt(ShAmtAPInt)) && ShAmtAPInt->ult(BitWidth)) {
Sanjay Patel5f8451a2017-01-15 16:38:19 +0000822 unsigned ShAmt = ShAmtAPInt->getZExtValue();
Jakub Staszak538e3862012-12-09 15:37:46 +0000823
Sanjay Patelca3124f2017-01-14 23:13:50 +0000824 // If the shift amount equals the difference in width of the destination
Sanjay Patel5f8451a2017-01-15 16:38:19 +0000825 // and source scalar types:
Sanjay Patelca3124f2017-01-14 23:13:50 +0000826 // ashr (shl (zext X), C), C --> sext X
Chris Lattnera1e223e2010-01-08 19:04:21 +0000827 Value *X;
Sanjay Patelca3124f2017-01-14 23:13:50 +0000828 if (match(Op0, m_Shl(m_ZExt(m_Value(X)), m_Specific(Op1))) &&
829 ShAmt == BitWidth - X->getType()->getScalarSizeInBits())
Sanjay Patel77732d52017-01-30 17:19:32 +0000830 return new SExtInst(X, Ty);
831
832 // We can't handle (X << C1) >>s C2. It shifts arbitrary bits in. However,
833 // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits.
Sanjay Patelc56d1cc2017-02-01 21:31:34 +0000834 const APInt *ShOp1;
Simon Pilgrim5d909be2018-01-09 14:23:46 +0000835 if (match(Op0, m_NSWShl(m_Value(X), m_APInt(ShOp1))) &&
836 ShOp1->ult(BitWidth)) {
Sanjay Patelc56d1cc2017-02-01 21:31:34 +0000837 unsigned ShlAmt = ShOp1->getZExtValue();
Sanjay Patel8c5f2362017-01-30 23:35:52 +0000838 if (ShlAmt < ShAmt) {
839 // (X <<nsw C1) >>s C2 --> X >>s (C2 - C1)
840 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);
841 auto *NewAShr = BinaryOperator::CreateAShr(X, ShiftDiff);
842 NewAShr->setIsExact(I.isExact());
843 return NewAShr;
844 }
845 if (ShlAmt > ShAmt) {
846 // (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2)
847 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);
848 auto *NewShl = BinaryOperator::Create(Instruction::Shl, X, ShiftDiff);
849 NewShl->setHasNoSignedWrap(true);
850 return NewShl;
851 }
Sanjay Patel77732d52017-01-30 17:19:32 +0000852 }
Chris Lattner6b657ae2011-02-10 05:36:31 +0000853
Simon Pilgrim5d909be2018-01-09 14:23:46 +0000854 if (match(Op0, m_AShr(m_Value(X), m_APInt(ShOp1))) &&
855 ShOp1->ult(BitWidth)) {
Sanjay Patelc56d1cc2017-02-01 21:31:34 +0000856 unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
857 // Oversized arithmetic shifts replicate the sign bit.
858 AmtSum = std::min(AmtSum, BitWidth - 1);
859 // (X >>s C1) >>s C2 --> X >>s (C1 + C2)
860 return BinaryOperator::CreateAShr(X, ConstantInt::get(Ty, AmtSum));
861 }
862
Sanjay Patelf69b7d52017-08-15 18:25:52 +0000863 if (match(Op0, m_OneUse(m_SExt(m_Value(X)))) &&
864 (Ty->isVectorTy() || shouldChangeType(Ty, X->getType()))) {
865 // ashr (sext X), C --> sext (ashr X, C')
866 Type *SrcTy = X->getType();
867 ShAmt = std::min(ShAmt, SrcTy->getScalarSizeInBits() - 1);
868 Value *NewSh = Builder.CreateAShr(X, ConstantInt::get(SrcTy, ShAmt));
869 return new SExtInst(NewSh, Ty);
870 }
871
Chris Lattner6b657ae2011-02-10 05:36:31 +0000872 // If the shifted-out value is known-zero, then this is an exact shift.
Jakub Staszak538e3862012-12-09 15:37:46 +0000873 if (!I.isExact() &&
Sanjay Patelca3124f2017-01-14 23:13:50 +0000874 MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) {
Chris Lattner6b657ae2011-02-10 05:36:31 +0000875 I.setIsExact();
876 return &I;
877 }
Jakub Staszak538e3862012-12-09 15:37:46 +0000878 }
879
Chris Lattnerdc67e132010-01-05 07:44:46 +0000880 // See if we can turn a signed shr into an unsigned shr.
Craig Topperbcfd2d12017-04-20 16:56:25 +0000881 if (MaskedValueIsZero(Op0, APInt::getSignMask(BitWidth), 0, &I))
Chris Lattnera1e223e2010-01-08 19:04:21 +0000882 return BinaryOperator::CreateLShr(Op0, Op1);
Jakub Staszak538e3862012-12-09 15:37:46 +0000883
Craig Topperf40110f2014-04-25 05:29:35 +0000884 return nullptr;
Chris Lattnerdc67e132010-01-05 07:44:46 +0000885}