InstCombineShifts.cpp revision 234353
1202375Srdivacky//===- InstCombineShifts.cpp ----------------------------------------------===//
2202375Srdivacky//
3202375Srdivacky//                     The LLVM Compiler Infrastructure
4202375Srdivacky//
5202375Srdivacky// This file is distributed under the University of Illinois Open Source
6202375Srdivacky// License. See LICENSE.TXT for details.
7202375Srdivacky//
8202375Srdivacky//===----------------------------------------------------------------------===//
9202375Srdivacky//
10202375Srdivacky// This file implements the visitShl, visitLShr, and visitAShr functions.
11202375Srdivacky//
12202375Srdivacky//===----------------------------------------------------------------------===//
13202375Srdivacky
14202375Srdivacky#include "InstCombine.h"
15203954Srdivacky#include "llvm/IntrinsicInst.h"
16226633Sdim#include "llvm/Analysis/ConstantFolding.h"
17218893Sdim#include "llvm/Analysis/InstructionSimplify.h"
18202375Srdivacky#include "llvm/Support/PatternMatch.h"
19202375Srdivackyusing namespace llvm;
20202375Srdivackyusing namespace PatternMatch;
21202375Srdivacky
22202375SrdivackyInstruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) {
23202375Srdivacky  assert(I.getOperand(1)->getType() == I.getOperand(0)->getType());
24202375Srdivacky  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
25202375Srdivacky
26202375Srdivacky  // See if we can fold away this shift.
27202375Srdivacky  if (SimplifyDemandedInstructionBits(I))
28202375Srdivacky    return &I;
29202375Srdivacky
30202375Srdivacky  // Try to fold constant and into select arguments.
31202375Srdivacky  if (isa<Constant>(Op0))
32202375Srdivacky    if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
33202375Srdivacky      if (Instruction *R = FoldOpIntoSelect(I, SI))
34202375Srdivacky        return R;
35202375Srdivacky
36202375Srdivacky  if (ConstantInt *CUI = dyn_cast<ConstantInt>(Op1))
37202375Srdivacky    if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
38202375Srdivacky      return Res;
39218893Sdim
40218893Sdim  // X shift (A srem B) -> X shift (A and B-1) iff B is a power of 2.
41218893Sdim  // Because shifts by negative values (which could occur if A were negative)
42218893Sdim  // are undefined.
43218893Sdim  Value *A; const APInt *B;
44218893Sdim  if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Power2(B)))) {
45218893Sdim    // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't
46218893Sdim    // demand the sign bit (and many others) here??
47218893Sdim    Value *Rem = Builder->CreateAnd(A, ConstantInt::get(I.getType(), *B-1),
48218893Sdim                                    Op1->getName());
49218893Sdim    I.setOperand(1, Rem);
50218893Sdim    return &I;
51218893Sdim  }
52218893Sdim
53202375Srdivacky  return 0;
54202375Srdivacky}
55202375Srdivacky
56212904Sdim/// CanEvaluateShifted - See if we can compute the specified value, but shifted
57212904Sdim/// logically to the left or right by some number of bits.  This should return
58212904Sdim/// true if the expression can be computed for the same cost as the current
59212904Sdim/// expression tree.  This is used to eliminate extraneous shifting from things
60212904Sdim/// like:
61212904Sdim///      %C = shl i128 %A, 64
62212904Sdim///      %D = shl i128 %B, 96
63212904Sdim///      %E = or i128 %C, %D
64212904Sdim///      %F = lshr i128 %E, 64
65212904Sdim/// where the client will ask if E can be computed shifted right by 64-bits.  If
66212904Sdim/// this succeeds, the GetShiftedValue function will be called to produce the
67212904Sdim/// value.
68212904Sdimstatic bool CanEvaluateShifted(Value *V, unsigned NumBits, bool isLeftShift,
69212904Sdim                               InstCombiner &IC) {
70212904Sdim  // We can always evaluate constants shifted.
71212904Sdim  if (isa<Constant>(V))
72212904Sdim    return true;
73212904Sdim
74212904Sdim  Instruction *I = dyn_cast<Instruction>(V);
75212904Sdim  if (!I) return false;
76212904Sdim
77212904Sdim  // If this is the opposite shift, we can directly reuse the input of the shift
78212904Sdim  // if the needed bits are already zero in the input.  This allows us to reuse
79212904Sdim  // the value which means that we don't care if the shift has multiple uses.
80212904Sdim  //  TODO:  Handle opposite shift by exact value.
81218893Sdim  ConstantInt *CI = 0;
82212904Sdim  if ((isLeftShift && match(I, m_LShr(m_Value(), m_ConstantInt(CI)))) ||
83212904Sdim      (!isLeftShift && match(I, m_Shl(m_Value(), m_ConstantInt(CI))))) {
84212904Sdim    if (CI->getZExtValue() == NumBits) {
85212904Sdim      // TODO: Check that the input bits are already zero with MaskedValueIsZero
86212904Sdim#if 0
87212904Sdim      // If this is a truncate of a logical shr, we can truncate it to a smaller
88212904Sdim      // lshr iff we know that the bits we would otherwise be shifting in are
89212904Sdim      // already zeros.
90212904Sdim      uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
91212904Sdim      uint32_t BitWidth = Ty->getScalarSizeInBits();
92212904Sdim      if (MaskedValueIsZero(I->getOperand(0),
93212904Sdim            APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) &&
94212904Sdim          CI->getLimitedValue(BitWidth) < BitWidth) {
95212904Sdim        return CanEvaluateTruncated(I->getOperand(0), Ty);
96212904Sdim      }
97212904Sdim#endif
98212904Sdim
99212904Sdim    }
100212904Sdim  }
101212904Sdim
102212904Sdim  // We can't mutate something that has multiple uses: doing so would
103212904Sdim  // require duplicating the instruction in general, which isn't profitable.
104212904Sdim  if (!I->hasOneUse()) return false;
105212904Sdim
106212904Sdim  switch (I->getOpcode()) {
107212904Sdim  default: return false;
108212904Sdim  case Instruction::And:
109212904Sdim  case Instruction::Or:
110212904Sdim  case Instruction::Xor:
111212904Sdim    // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
112212904Sdim    return CanEvaluateShifted(I->getOperand(0), NumBits, isLeftShift, IC) &&
113212904Sdim           CanEvaluateShifted(I->getOperand(1), NumBits, isLeftShift, IC);
114212904Sdim
115212904Sdim  case Instruction::Shl: {
116212904Sdim    // We can often fold the shift into shifts-by-a-constant.
117212904Sdim    CI = dyn_cast<ConstantInt>(I->getOperand(1));
118212904Sdim    if (CI == 0) return false;
119212904Sdim
120212904Sdim    // We can always fold shl(c1)+shl(c2) -> shl(c1+c2).
121212904Sdim    if (isLeftShift) return true;
122212904Sdim
123212904Sdim    // We can always turn shl(c)+shr(c) -> and(c2).
124212904Sdim    if (CI->getValue() == NumBits) return true;
125212904Sdim
126212904Sdim    unsigned TypeWidth = I->getType()->getScalarSizeInBits();
127212904Sdim
128212904Sdim    // We can turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but it isn't
129212904Sdim    // profitable unless we know the and'd out bits are already zero.
130212904Sdim    if (CI->getZExtValue() > NumBits) {
131218893Sdim      unsigned LowBits = TypeWidth - CI->getZExtValue();
132212904Sdim      if (MaskedValueIsZero(I->getOperand(0),
133218893Sdim                       APInt::getLowBitsSet(TypeWidth, NumBits) << LowBits))
134212904Sdim        return true;
135212904Sdim    }
136212904Sdim
137212904Sdim    return false;
138212904Sdim  }
139212904Sdim  case Instruction::LShr: {
140212904Sdim    // We can often fold the shift into shifts-by-a-constant.
141212904Sdim    CI = dyn_cast<ConstantInt>(I->getOperand(1));
142212904Sdim    if (CI == 0) return false;
143212904Sdim
144212904Sdim    // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2).
145212904Sdim    if (!isLeftShift) return true;
146212904Sdim
147212904Sdim    // We can always turn lshr(c)+shl(c) -> and(c2).
148212904Sdim    if (CI->getValue() == NumBits) return true;
149212904Sdim
150212904Sdim    unsigned TypeWidth = I->getType()->getScalarSizeInBits();
151212904Sdim
152212904Sdim    // We can always turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but it isn't
153212904Sdim    // profitable unless we know the and'd out bits are already zero.
154212904Sdim    if (CI->getZExtValue() > NumBits) {
155212904Sdim      unsigned LowBits = CI->getZExtValue() - NumBits;
156212904Sdim      if (MaskedValueIsZero(I->getOperand(0),
157218893Sdim                          APInt::getLowBitsSet(TypeWidth, NumBits) << LowBits))
158212904Sdim        return true;
159212904Sdim    }
160212904Sdim
161212904Sdim    return false;
162212904Sdim  }
163212904Sdim  case Instruction::Select: {
164212904Sdim    SelectInst *SI = cast<SelectInst>(I);
165212904Sdim    return CanEvaluateShifted(SI->getTrueValue(), NumBits, isLeftShift, IC) &&
166212904Sdim           CanEvaluateShifted(SI->getFalseValue(), NumBits, isLeftShift, IC);
167212904Sdim  }
168212904Sdim  case Instruction::PHI: {
169212904Sdim    // We can change a phi if we can change all operands.  Note that we never
170212904Sdim    // get into trouble with cyclic PHIs here because we only consider
171212904Sdim    // instructions with a single use.
172212904Sdim    PHINode *PN = cast<PHINode>(I);
173212904Sdim    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
174212904Sdim      if (!CanEvaluateShifted(PN->getIncomingValue(i), NumBits, isLeftShift,IC))
175212904Sdim        return false;
176212904Sdim    return true;
177212904Sdim  }
178212904Sdim  }
179212904Sdim}
180212904Sdim
181212904Sdim/// GetShiftedValue - When CanEvaluateShifted returned true for an expression,
182212904Sdim/// this value inserts the new computation that produces the shifted value.
183212904Sdimstatic Value *GetShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,
184212904Sdim                              InstCombiner &IC) {
185212904Sdim  // We can always evaluate constants shifted.
186212904Sdim  if (Constant *C = dyn_cast<Constant>(V)) {
187212904Sdim    if (isLeftShift)
188212904Sdim      V = IC.Builder->CreateShl(C, NumBits);
189212904Sdim    else
190212904Sdim      V = IC.Builder->CreateLShr(C, NumBits);
191212904Sdim    // If we got a constantexpr back, try to simplify it with TD info.
192212904Sdim    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
193234353Sdim      V = ConstantFoldConstantExpression(CE, IC.getTargetData(),
194234353Sdim                                         IC.getTargetLibraryInfo());
195212904Sdim    return V;
196212904Sdim  }
197212904Sdim
198212904Sdim  Instruction *I = cast<Instruction>(V);
199212904Sdim  IC.Worklist.Add(I);
200212904Sdim
201212904Sdim  switch (I->getOpcode()) {
202234353Sdim  default: llvm_unreachable("Inconsistency with CanEvaluateShifted");
203212904Sdim  case Instruction::And:
204212904Sdim  case Instruction::Or:
205212904Sdim  case Instruction::Xor:
206212904Sdim    // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
207212904Sdim    I->setOperand(0, GetShiftedValue(I->getOperand(0), NumBits,isLeftShift,IC));
208212904Sdim    I->setOperand(1, GetShiftedValue(I->getOperand(1), NumBits,isLeftShift,IC));
209212904Sdim    return I;
210212904Sdim
211212904Sdim  case Instruction::Shl: {
212226633Sdim    BinaryOperator *BO = cast<BinaryOperator>(I);
213226633Sdim    unsigned TypeWidth = BO->getType()->getScalarSizeInBits();
214212904Sdim
215212904Sdim    // We only accept shifts-by-a-constant in CanEvaluateShifted.
216226633Sdim    ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1));
217226633Sdim
218212904Sdim    // We can always fold shl(c1)+shl(c2) -> shl(c1+c2).
219212904Sdim    if (isLeftShift) {
220212904Sdim      // If this is oversized composite shift, then unsigned shifts get 0.
221212904Sdim      unsigned NewShAmt = NumBits+CI->getZExtValue();
222212904Sdim      if (NewShAmt >= TypeWidth)
223212904Sdim        return Constant::getNullValue(I->getType());
224212904Sdim
225226633Sdim      BO->setOperand(1, ConstantInt::get(BO->getType(), NewShAmt));
226226633Sdim      BO->setHasNoUnsignedWrap(false);
227226633Sdim      BO->setHasNoSignedWrap(false);
228212904Sdim      return I;
229212904Sdim    }
230212904Sdim
231212904Sdim    // We turn shl(c)+lshr(c) -> and(c2) if the input doesn't already have
232212904Sdim    // zeros.
233212904Sdim    if (CI->getValue() == NumBits) {
234212904Sdim      APInt Mask(APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits));
235226633Sdim      V = IC.Builder->CreateAnd(BO->getOperand(0),
236226633Sdim                                ConstantInt::get(BO->getContext(), Mask));
237212904Sdim      if (Instruction *VI = dyn_cast<Instruction>(V)) {
238226633Sdim        VI->moveBefore(BO);
239226633Sdim        VI->takeName(BO);
240212904Sdim      }
241212904Sdim      return V;
242212904Sdim    }
243212904Sdim
244212904Sdim    // We turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but only when we know that
245212904Sdim    // the and won't be needed.
246212904Sdim    assert(CI->getZExtValue() > NumBits);
247226633Sdim    BO->setOperand(1, ConstantInt::get(BO->getType(),
248226633Sdim                                       CI->getZExtValue() - NumBits));
249226633Sdim    BO->setHasNoUnsignedWrap(false);
250226633Sdim    BO->setHasNoSignedWrap(false);
251226633Sdim    return BO;
252212904Sdim  }
253212904Sdim  case Instruction::LShr: {
254226633Sdim    BinaryOperator *BO = cast<BinaryOperator>(I);
255226633Sdim    unsigned TypeWidth = BO->getType()->getScalarSizeInBits();
256212904Sdim    // We only accept shifts-by-a-constant in CanEvaluateShifted.
257226633Sdim    ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1));
258212904Sdim
259212904Sdim    // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2).
260212904Sdim    if (!isLeftShift) {
261212904Sdim      // If this is oversized composite shift, then unsigned shifts get 0.
262212904Sdim      unsigned NewShAmt = NumBits+CI->getZExtValue();
263212904Sdim      if (NewShAmt >= TypeWidth)
264226633Sdim        return Constant::getNullValue(BO->getType());
265212904Sdim
266226633Sdim      BO->setOperand(1, ConstantInt::get(BO->getType(), NewShAmt));
267226633Sdim      BO->setIsExact(false);
268212904Sdim      return I;
269212904Sdim    }
270212904Sdim
271212904Sdim    // We turn lshr(c)+shl(c) -> and(c2) if the input doesn't already have
272212904Sdim    // zeros.
273212904Sdim    if (CI->getValue() == NumBits) {
274212904Sdim      APInt Mask(APInt::getHighBitsSet(TypeWidth, TypeWidth - NumBits));
275212904Sdim      V = IC.Builder->CreateAnd(I->getOperand(0),
276226633Sdim                                ConstantInt::get(BO->getContext(), Mask));
277212904Sdim      if (Instruction *VI = dyn_cast<Instruction>(V)) {
278212904Sdim        VI->moveBefore(I);
279212904Sdim        VI->takeName(I);
280212904Sdim      }
281212904Sdim      return V;
282212904Sdim    }
283212904Sdim
284212904Sdim    // We turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but only when we know that
285212904Sdim    // the and won't be needed.
286212904Sdim    assert(CI->getZExtValue() > NumBits);
287226633Sdim    BO->setOperand(1, ConstantInt::get(BO->getType(),
288226633Sdim                                       CI->getZExtValue() - NumBits));
289226633Sdim    BO->setIsExact(false);
290226633Sdim    return BO;
291212904Sdim  }
292212904Sdim
293212904Sdim  case Instruction::Select:
294212904Sdim    I->setOperand(1, GetShiftedValue(I->getOperand(1), NumBits,isLeftShift,IC));
295212904Sdim    I->setOperand(2, GetShiftedValue(I->getOperand(2), NumBits,isLeftShift,IC));
296212904Sdim    return I;
297212904Sdim  case Instruction::PHI: {
298212904Sdim    // We can change a phi if we can change all operands.  Note that we never
299212904Sdim    // get into trouble with cyclic PHIs here because we only consider
300212904Sdim    // instructions with a single use.
301212904Sdim    PHINode *PN = cast<PHINode>(I);
302212904Sdim    for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
303212904Sdim      PN->setIncomingValue(i, GetShiftedValue(PN->getIncomingValue(i),
304212904Sdim                                              NumBits, isLeftShift, IC));
305212904Sdim    return PN;
306212904Sdim  }
307212904Sdim  }
308212904Sdim}
309212904Sdim
310212904Sdim
311212904Sdim
312202375SrdivackyInstruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
313202375Srdivacky                                               BinaryOperator &I) {
314202375Srdivacky  bool isLeftShift = I.getOpcode() == Instruction::Shl;
315212904Sdim
316212904Sdim
317212904Sdim  // See if we can propagate this shift into the input, this covers the trivial
318212904Sdim  // cast of lshr(shl(x,c1),c2) as well as other more complex cases.
319212904Sdim  if (I.getOpcode() != Instruction::AShr &&
320212904Sdim      CanEvaluateShifted(Op0, Op1->getZExtValue(), isLeftShift, *this)) {
321212904Sdim    DEBUG(dbgs() << "ICE: GetShiftedValue propagating shift through expression"
322212904Sdim              " to eliminate shift:\n  IN: " << *Op0 << "\n  SH: " << I <<"\n");
323212904Sdim
324212904Sdim    return ReplaceInstUsesWith(I,
325212904Sdim                 GetShiftedValue(Op0, Op1->getZExtValue(), isLeftShift, *this));
326212904Sdim  }
327212904Sdim
328212904Sdim
329202375Srdivacky  // See if we can simplify any instructions used by the instruction whose sole
330202375Srdivacky  // purpose is to compute bits we don't care about.
331202375Srdivacky  uint32_t TypeBits = Op0->getType()->getScalarSizeInBits();
332202375Srdivacky
333202375Srdivacky  // shl i32 X, 32 = 0 and srl i8 Y, 9 = 0, ... just don't eliminate
334202375Srdivacky  // a signed shift.
335202375Srdivacky  //
336202375Srdivacky  if (Op1->uge(TypeBits)) {
337202375Srdivacky    if (I.getOpcode() != Instruction::AShr)
338202375Srdivacky      return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
339203954Srdivacky    // ashr i32 X, 32 --> ashr i32 X, 31
340203954Srdivacky    I.setOperand(1, ConstantInt::get(I.getType(), TypeBits-1));
341203954Srdivacky    return &I;
342202375Srdivacky  }
343202375Srdivacky
344202375Srdivacky  // ((X*C1) << C2) == (X * (C1 << C2))
345202375Srdivacky  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
346202375Srdivacky    if (BO->getOpcode() == Instruction::Mul && isLeftShift)
347202375Srdivacky      if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1)))
348202375Srdivacky        return BinaryOperator::CreateMul(BO->getOperand(0),
349202375Srdivacky                                        ConstantExpr::getShl(BOOp, Op1));
350202375Srdivacky
351202375Srdivacky  // Try to fold constant and into select arguments.
352202375Srdivacky  if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
353202375Srdivacky    if (Instruction *R = FoldOpIntoSelect(I, SI))
354202375Srdivacky      return R;
355202375Srdivacky  if (isa<PHINode>(Op0))
356202375Srdivacky    if (Instruction *NV = FoldOpIntoPhi(I))
357202375Srdivacky      return NV;
358202375Srdivacky
359202375Srdivacky  // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2))
360202375Srdivacky  if (TruncInst *TI = dyn_cast<TruncInst>(Op0)) {
361202375Srdivacky    Instruction *TrOp = dyn_cast<Instruction>(TI->getOperand(0));
362202375Srdivacky    // If 'shift2' is an ashr, we would have to get the sign bit into a funny
363202375Srdivacky    // place.  Don't try to do this transformation in this case.  Also, we
364202375Srdivacky    // require that the input operand is a shift-by-constant so that we have
365202375Srdivacky    // confidence that the shifts will get folded together.  We could do this
366202375Srdivacky    // xform in more cases, but it is unlikely to be profitable.
367202375Srdivacky    if (TrOp && I.isLogicalShift() && TrOp->isShift() &&
368202375Srdivacky        isa<ConstantInt>(TrOp->getOperand(1))) {
369202375Srdivacky      // Okay, we'll do this xform.  Make the shift of shift.
370202375Srdivacky      Constant *ShAmt = ConstantExpr::getZExt(Op1, TrOp->getType());
371202375Srdivacky      // (shift2 (shift1 & 0x00FF), c2)
372202375Srdivacky      Value *NSh = Builder->CreateBinOp(I.getOpcode(), TrOp, ShAmt,I.getName());
373202375Srdivacky
374202375Srdivacky      // For logical shifts, the truncation has the effect of making the high
375202375Srdivacky      // part of the register be zeros.  Emulate this by inserting an AND to
376202375Srdivacky      // clear the top bits as needed.  This 'and' will usually be zapped by
377202375Srdivacky      // other xforms later if dead.
378202375Srdivacky      unsigned SrcSize = TrOp->getType()->getScalarSizeInBits();
379202375Srdivacky      unsigned DstSize = TI->getType()->getScalarSizeInBits();
380202375Srdivacky      APInt MaskV(APInt::getLowBitsSet(SrcSize, DstSize));
381202375Srdivacky
382202375Srdivacky      // The mask we constructed says what the trunc would do if occurring
383202375Srdivacky      // between the shifts.  We want to know the effect *after* the second
384202375Srdivacky      // shift.  We know that it is a logical shift by a constant, so adjust the
385202375Srdivacky      // mask as appropriate.
386202375Srdivacky      if (I.getOpcode() == Instruction::Shl)
387202375Srdivacky        MaskV <<= Op1->getZExtValue();
388202375Srdivacky      else {
389202375Srdivacky        assert(I.getOpcode() == Instruction::LShr && "Unknown logical shift");
390202375Srdivacky        MaskV = MaskV.lshr(Op1->getZExtValue());
391202375Srdivacky      }
392202375Srdivacky
393202375Srdivacky      // shift1 & 0x00FF
394202375Srdivacky      Value *And = Builder->CreateAnd(NSh,
395202375Srdivacky                                      ConstantInt::get(I.getContext(), MaskV),
396202375Srdivacky                                      TI->getName());
397202375Srdivacky
398202375Srdivacky      // Return the value truncated to the interesting size.
399202375Srdivacky      return new TruncInst(And, I.getType());
400202375Srdivacky    }
401202375Srdivacky  }
402202375Srdivacky
403202375Srdivacky  if (Op0->hasOneUse()) {
404202375Srdivacky    if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
405202375Srdivacky      // Turn ((X >> C) + Y) << C  ->  (X + (Y << C)) & (~0 << C)
406202375Srdivacky      Value *V1, *V2;
407202375Srdivacky      ConstantInt *CC;
408202375Srdivacky      switch (Op0BO->getOpcode()) {
409202375Srdivacky      default: break;
410202375Srdivacky      case Instruction::Add:
411202375Srdivacky      case Instruction::And:
412202375Srdivacky      case Instruction::Or:
413202375Srdivacky      case Instruction::Xor: {
414202375Srdivacky        // These operators commute.
415202375Srdivacky        // Turn (Y + (X >> C)) << C  ->  (X + (Y << C)) & (~0 << C)
416202375Srdivacky        if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() &&
417202375Srdivacky            match(Op0BO->getOperand(1), m_Shr(m_Value(V1),
418202375Srdivacky                  m_Specific(Op1)))) {
419202375Srdivacky          Value *YS =         // (Y << C)
420202375Srdivacky            Builder->CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName());
421202375Srdivacky          // (X + (Y << C))
422202375Srdivacky          Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), YS, V1,
423202375Srdivacky                                          Op0BO->getOperand(1)->getName());
424202375Srdivacky          uint32_t Op1Val = Op1->getLimitedValue(TypeBits);
425202375Srdivacky          return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(),
426202375Srdivacky                     APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val)));
427202375Srdivacky        }
428202375Srdivacky
429202375Srdivacky        // Turn (Y + ((X >> C) & CC)) << C  ->  ((X & (CC << C)) + (Y << C))
430202375Srdivacky        Value *Op0BOOp1 = Op0BO->getOperand(1);
431202375Srdivacky        if (isLeftShift && Op0BOOp1->hasOneUse() &&
432202375Srdivacky            match(Op0BOOp1,
433202375Srdivacky                  m_And(m_Shr(m_Value(V1), m_Specific(Op1)),
434202375Srdivacky                        m_ConstantInt(CC))) &&
435202375Srdivacky            cast<BinaryOperator>(Op0BOOp1)->getOperand(0)->hasOneUse()) {
436202375Srdivacky          Value *YS =   // (Y << C)
437202375Srdivacky            Builder->CreateShl(Op0BO->getOperand(0), Op1,
438202375Srdivacky                                         Op0BO->getName());
439202375Srdivacky          // X & (CC << C)
440202375Srdivacky          Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1),
441202375Srdivacky                                         V1->getName()+".mask");
442202375Srdivacky          return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM);
443202375Srdivacky        }
444202375Srdivacky      }
445202375Srdivacky
446202375Srdivacky      // FALL THROUGH.
447202375Srdivacky      case Instruction::Sub: {
448202375Srdivacky        // Turn ((X >> C) + Y) << C  ->  (X + (Y << C)) & (~0 << C)
449202375Srdivacky        if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
450202375Srdivacky            match(Op0BO->getOperand(0), m_Shr(m_Value(V1),
451202375Srdivacky                  m_Specific(Op1)))) {
452202375Srdivacky          Value *YS =  // (Y << C)
453202375Srdivacky            Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName());
454202375Srdivacky          // (X + (Y << C))
455202375Srdivacky          Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), V1, YS,
456202375Srdivacky                                          Op0BO->getOperand(0)->getName());
457202375Srdivacky          uint32_t Op1Val = Op1->getLimitedValue(TypeBits);
458202375Srdivacky          return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(),
459202375Srdivacky                     APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val)));
460202375Srdivacky        }
461202375Srdivacky
462202375Srdivacky        // Turn (((X >> C)&CC) + Y) << C  ->  (X + (Y << C)) & (CC << C)
463202375Srdivacky        if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
464202375Srdivacky            match(Op0BO->getOperand(0),
465202375Srdivacky                  m_And(m_Shr(m_Value(V1), m_Value(V2)),
466202375Srdivacky                        m_ConstantInt(CC))) && V2 == Op1 &&
467202375Srdivacky            cast<BinaryOperator>(Op0BO->getOperand(0))
468202375Srdivacky                ->getOperand(0)->hasOneUse()) {
469202375Srdivacky          Value *YS = // (Y << C)
470202375Srdivacky            Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName());
471202375Srdivacky          // X & (CC << C)
472202375Srdivacky          Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1),
473202375Srdivacky                                         V1->getName()+".mask");
474202375Srdivacky
475202375Srdivacky          return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS);
476202375Srdivacky        }
477202375Srdivacky
478202375Srdivacky        break;
479202375Srdivacky      }
480202375Srdivacky      }
481202375Srdivacky
482202375Srdivacky
483202375Srdivacky      // If the operand is an bitwise operator with a constant RHS, and the
484202375Srdivacky      // shift is the only use, we can pull it out of the shift.
485202375Srdivacky      if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
486202375Srdivacky        bool isValid = true;     // Valid only for And, Or, Xor
487202375Srdivacky        bool highBitSet = false; // Transform if high bit of constant set?
488202375Srdivacky
489202375Srdivacky        switch (Op0BO->getOpcode()) {
490202375Srdivacky        default: isValid = false; break;   // Do not perform transform!
491202375Srdivacky        case Instruction::Add:
492202375Srdivacky          isValid = isLeftShift;
493202375Srdivacky          break;
494202375Srdivacky        case Instruction::Or:
495202375Srdivacky        case Instruction::Xor:
496202375Srdivacky          highBitSet = false;
497202375Srdivacky          break;
498202375Srdivacky        case Instruction::And:
499202375Srdivacky          highBitSet = true;
500202375Srdivacky          break;
501202375Srdivacky        }
502202375Srdivacky
503202375Srdivacky        // If this is a signed shift right, and the high bit is modified
504202375Srdivacky        // by the logical operation, do not perform the transformation.
505202375Srdivacky        // The highBitSet boolean indicates the value of the high bit of
506202375Srdivacky        // the constant which would cause it to be modified for this
507202375Srdivacky        // operation.
508202375Srdivacky        //
509202375Srdivacky        if (isValid && I.getOpcode() == Instruction::AShr)
510202375Srdivacky          isValid = Op0C->getValue()[TypeBits-1] == highBitSet;
511202375Srdivacky
512202375Srdivacky        if (isValid) {
513202375Srdivacky          Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, Op1);
514202375Srdivacky
515202375Srdivacky          Value *NewShift =
516202375Srdivacky            Builder->CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1);
517202375Srdivacky          NewShift->takeName(Op0BO);
518202375Srdivacky
519202375Srdivacky          return BinaryOperator::Create(Op0BO->getOpcode(), NewShift,
520202375Srdivacky                                        NewRHS);
521202375Srdivacky        }
522202375Srdivacky      }
523202375Srdivacky    }
524202375Srdivacky  }
525202375Srdivacky
526202375Srdivacky  // Find out if this is a shift of a shift by a constant.
527202375Srdivacky  BinaryOperator *ShiftOp = dyn_cast<BinaryOperator>(Op0);
528202375Srdivacky  if (ShiftOp && !ShiftOp->isShift())
529202375Srdivacky    ShiftOp = 0;
530202375Srdivacky
531202375Srdivacky  if (ShiftOp && isa<ConstantInt>(ShiftOp->getOperand(1))) {
532202375Srdivacky    ConstantInt *ShiftAmt1C = cast<ConstantInt>(ShiftOp->getOperand(1));
533202375Srdivacky    uint32_t ShiftAmt1 = ShiftAmt1C->getLimitedValue(TypeBits);
534202375Srdivacky    uint32_t ShiftAmt2 = Op1->getLimitedValue(TypeBits);
535202375Srdivacky    assert(ShiftAmt2 != 0 && "Should have been simplified earlier");
536202375Srdivacky    if (ShiftAmt1 == 0) return 0;  // Will be simplified in the future.
537202375Srdivacky    Value *X = ShiftOp->getOperand(0);
538202375Srdivacky
539226633Sdim    IntegerType *Ty = cast<IntegerType>(I.getType());
540202375Srdivacky
541202375Srdivacky    // Check for (X << c1) << c2  and  (X >> c1) >> c2
542202375Srdivacky    if (I.getOpcode() == ShiftOp->getOpcode()) {
543234353Sdim      uint32_t AmtSum = ShiftAmt1+ShiftAmt2;   // Fold into one big shift.
544202375Srdivacky      // If this is oversized composite shift, then unsigned shifts get 0, ashr
545202375Srdivacky      // saturates.
546202375Srdivacky      if (AmtSum >= TypeBits) {
547202375Srdivacky        if (I.getOpcode() != Instruction::AShr)
548202375Srdivacky          return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
549202375Srdivacky        AmtSum = TypeBits-1;  // Saturate to 31 for i32 ashr.
550202375Srdivacky      }
551202375Srdivacky
552202375Srdivacky      return BinaryOperator::Create(I.getOpcode(), X,
553202375Srdivacky                                    ConstantInt::get(Ty, AmtSum));
554202375Srdivacky    }
555202375Srdivacky
556202375Srdivacky    if (ShiftAmt1 == ShiftAmt2) {
557202375Srdivacky      // If we have ((X >>? C) << C), turn this into X & (-1 << C).
558212904Sdim      if (I.getOpcode() == Instruction::Shl &&
559212904Sdim          ShiftOp->getOpcode() != Instruction::Shl) {
560202375Srdivacky        APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt1));
561202375Srdivacky        return BinaryOperator::CreateAnd(X,
562202375Srdivacky                                         ConstantInt::get(I.getContext(),Mask));
563202375Srdivacky      }
564202375Srdivacky      // If we have ((X << C) >>u C), turn this into X & (-1 >>u C).
565212904Sdim      if (I.getOpcode() == Instruction::LShr &&
566212904Sdim          ShiftOp->getOpcode() == Instruction::Shl) {
567202375Srdivacky        APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt1));
568202375Srdivacky        return BinaryOperator::CreateAnd(X,
569202375Srdivacky                                        ConstantInt::get(I.getContext(), Mask));
570202375Srdivacky      }
571202375Srdivacky    } else if (ShiftAmt1 < ShiftAmt2) {
572202375Srdivacky      uint32_t ShiftDiff = ShiftAmt2-ShiftAmt1;
573202375Srdivacky
574202375Srdivacky      // (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2)
575212904Sdim      if (I.getOpcode() == Instruction::Shl &&
576212904Sdim          ShiftOp->getOpcode() != Instruction::Shl) {
577202375Srdivacky        assert(ShiftOp->getOpcode() == Instruction::LShr ||
578202375Srdivacky               ShiftOp->getOpcode() == Instruction::AShr);
579234353Sdim        ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff);
580234353Sdim        if (ShiftOp->isExact()) {
581234353Sdim          // (X >>?,exact C1) << C2 --> X << (C2-C1)
582234353Sdim          BinaryOperator *NewShl = BinaryOperator::Create(Instruction::Shl,
583234353Sdim                                                          X, ShiftDiffCst);
584234353Sdim          NewShl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
585234353Sdim          NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
586234353Sdim          return NewShl;
587234353Sdim        }
588234353Sdim        Value *Shift = Builder->CreateShl(X, ShiftDiffCst);
589202375Srdivacky
590202375Srdivacky        APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2));
591202375Srdivacky        return BinaryOperator::CreateAnd(Shift,
592202375Srdivacky                                         ConstantInt::get(I.getContext(),Mask));
593202375Srdivacky      }
594202375Srdivacky
595202375Srdivacky      // (X << C1) >>u C2  --> X >>u (C2-C1) & (-1 >> C2)
596212904Sdim      if (I.getOpcode() == Instruction::LShr &&
597212904Sdim          ShiftOp->getOpcode() == Instruction::Shl) {
598234353Sdim        ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff);
599234353Sdim        // (X <<nuw C1) >>u C2 --> X >>u (C2-C1)
600234353Sdim        if (ShiftOp->hasNoUnsignedWrap()) {
601234353Sdim          BinaryOperator *NewLShr = BinaryOperator::Create(Instruction::LShr,
602234353Sdim                                                           X, ShiftDiffCst);
603234353Sdim          NewLShr->setIsExact(I.isExact());
604234353Sdim          return NewLShr;
605234353Sdim        }
606234353Sdim        Value *Shift = Builder->CreateLShr(X, ShiftDiffCst);
607202375Srdivacky
608202375Srdivacky        APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2));
609202375Srdivacky        return BinaryOperator::CreateAnd(Shift,
610202375Srdivacky                                         ConstantInt::get(I.getContext(),Mask));
611202375Srdivacky      }
612234353Sdim
613234353Sdim      // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in. However,
614234353Sdim      // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits.
615234353Sdim      if (I.getOpcode() == Instruction::AShr &&
616234353Sdim          ShiftOp->getOpcode() == Instruction::Shl) {
617234353Sdim        if (ShiftOp->hasNoSignedWrap()) {
618234353Sdim          // (X <<nsw C1) >>s C2 --> X >>s (C2-C1)
619234353Sdim          ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff);
620234353Sdim          BinaryOperator *NewAShr = BinaryOperator::Create(Instruction::AShr,
621234353Sdim                                                           X, ShiftDiffCst);
622234353Sdim          NewAShr->setIsExact(I.isExact());
623234353Sdim          return NewAShr;
624234353Sdim        }
625234353Sdim      }
626202375Srdivacky    } else {
627202375Srdivacky      assert(ShiftAmt2 < ShiftAmt1);
628202375Srdivacky      uint32_t ShiftDiff = ShiftAmt1-ShiftAmt2;
629202375Srdivacky
630202375Srdivacky      // (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2)
631212904Sdim      if (I.getOpcode() == Instruction::Shl &&
632212904Sdim          ShiftOp->getOpcode() != Instruction::Shl) {
633234353Sdim        ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff);
634234353Sdim        if (ShiftOp->isExact()) {
635234353Sdim          // (X >>?exact C1) << C2 --> X >>?exact (C1-C2)
636234353Sdim          BinaryOperator *NewShr = BinaryOperator::Create(ShiftOp->getOpcode(),
637234353Sdim                                                          X, ShiftDiffCst);
638234353Sdim          NewShr->setIsExact(true);
639234353Sdim          return NewShr;
640234353Sdim        }
641234353Sdim        Value *Shift = Builder->CreateBinOp(ShiftOp->getOpcode(),
642234353Sdim                                            X, ShiftDiffCst);
643202375Srdivacky        APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2));
644202375Srdivacky        return BinaryOperator::CreateAnd(Shift,
645202375Srdivacky                                         ConstantInt::get(I.getContext(),Mask));
646202375Srdivacky      }
647202375Srdivacky
648202375Srdivacky      // (X << C1) >>u C2  --> X << (C1-C2) & (-1 >> C2)
649212904Sdim      if (I.getOpcode() == Instruction::LShr &&
650212904Sdim          ShiftOp->getOpcode() == Instruction::Shl) {
651234353Sdim        ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff);
652234353Sdim        if (ShiftOp->hasNoUnsignedWrap()) {
653234353Sdim          // (X <<nuw C1) >>u C2 --> X <<nuw (C1-C2)
654234353Sdim          BinaryOperator *NewShl = BinaryOperator::Create(Instruction::Shl,
655234353Sdim                                                          X, ShiftDiffCst);
656234353Sdim          NewShl->setHasNoUnsignedWrap(true);
657234353Sdim          return NewShl;
658234353Sdim        }
659234353Sdim        Value *Shift = Builder->CreateShl(X, ShiftDiffCst);
660202375Srdivacky
661202375Srdivacky        APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2));
662202375Srdivacky        return BinaryOperator::CreateAnd(Shift,
663202375Srdivacky                                         ConstantInt::get(I.getContext(),Mask));
664202375Srdivacky      }
665202375Srdivacky
666234353Sdim      // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in. However,
667234353Sdim      // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits.
668234353Sdim      if (I.getOpcode() == Instruction::AShr &&
669234353Sdim          ShiftOp->getOpcode() == Instruction::Shl) {
670234353Sdim        if (ShiftOp->hasNoSignedWrap()) {
671234353Sdim          // (X <<nsw C1) >>s C2 --> X <<nsw (C1-C2)
672234353Sdim          ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff);
673234353Sdim          BinaryOperator *NewShl = BinaryOperator::Create(Instruction::Shl,
674234353Sdim                                                          X, ShiftDiffCst);
675234353Sdim          NewShl->setHasNoSignedWrap(true);
676234353Sdim          return NewShl;
677234353Sdim        }
678234353Sdim      }
679202375Srdivacky    }
680202375Srdivacky  }
681202375Srdivacky  return 0;
682202375Srdivacky}
683202375Srdivacky
684202375SrdivackyInstruction *InstCombiner::visitShl(BinaryOperator &I) {
685218893Sdim  if (Value *V = SimplifyShlInst(I.getOperand(0), I.getOperand(1),
686218893Sdim                                 I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
687218893Sdim                                 TD))
688218893Sdim    return ReplaceInstUsesWith(I, V);
689218893Sdim
690218893Sdim  if (Instruction *V = commonShiftTransforms(I))
691218893Sdim    return V;
692218893Sdim
693218893Sdim  if (ConstantInt *Op1C = dyn_cast<ConstantInt>(I.getOperand(1))) {
694218893Sdim    unsigned ShAmt = Op1C->getZExtValue();
695218893Sdim
696218893Sdim    // If the shifted-out value is known-zero, then this is a NUW shift.
697218893Sdim    if (!I.hasNoUnsignedWrap() &&
698218893Sdim        MaskedValueIsZero(I.getOperand(0),
699218893Sdim                          APInt::getHighBitsSet(Op1C->getBitWidth(), ShAmt))) {
700218893Sdim          I.setHasNoUnsignedWrap();
701218893Sdim          return &I;
702218893Sdim        }
703218893Sdim
704218893Sdim    // If the shifted out value is all signbits, this is a NSW shift.
705218893Sdim    if (!I.hasNoSignedWrap() &&
706218893Sdim        ComputeNumSignBits(I.getOperand(0)) > ShAmt) {
707218893Sdim      I.setHasNoSignedWrap();
708218893Sdim      return &I;
709218893Sdim    }
710218893Sdim  }
711221345Sdim
712221345Sdim  // (C1 << A) << C2 -> (C1 << C2) << A
713221345Sdim  Constant *C1, *C2;
714221345Sdim  Value *A;
715221345Sdim  if (match(I.getOperand(0), m_OneUse(m_Shl(m_Constant(C1), m_Value(A)))) &&
716221345Sdim      match(I.getOperand(1), m_Constant(C2)))
717221345Sdim    return BinaryOperator::CreateShl(ConstantExpr::getShl(C1, C2), A);
718221345Sdim
719218893Sdim  return 0;
720202375Srdivacky}
721202375Srdivacky
722202375SrdivackyInstruction *InstCombiner::visitLShr(BinaryOperator &I) {
723218893Sdim  if (Value *V = SimplifyLShrInst(I.getOperand(0), I.getOperand(1),
724218893Sdim                                  I.isExact(), TD))
725218893Sdim    return ReplaceInstUsesWith(I, V);
726218893Sdim
727203954Srdivacky  if (Instruction *R = commonShiftTransforms(I))
728203954Srdivacky    return R;
729203954Srdivacky
730203954Srdivacky  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
731203954Srdivacky
732218893Sdim  if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
733218893Sdim    unsigned ShAmt = Op1C->getZExtValue();
734218893Sdim
735203954Srdivacky    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) {
736203954Srdivacky      unsigned BitWidth = Op0->getType()->getScalarSizeInBits();
737203954Srdivacky      // ctlz.i32(x)>>5  --> zext(x == 0)
738203954Srdivacky      // cttz.i32(x)>>5  --> zext(x == 0)
739203954Srdivacky      // ctpop.i32(x)>>5 --> zext(x == -1)
740203954Srdivacky      if ((II->getIntrinsicID() == Intrinsic::ctlz ||
741203954Srdivacky           II->getIntrinsicID() == Intrinsic::cttz ||
742203954Srdivacky           II->getIntrinsicID() == Intrinsic::ctpop) &&
743218893Sdim          isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == ShAmt) {
744203954Srdivacky        bool isCtPop = II->getIntrinsicID() == Intrinsic::ctpop;
745203954Srdivacky        Constant *RHS = ConstantInt::getSigned(Op0->getType(), isCtPop ? -1:0);
746210299Sed        Value *Cmp = Builder->CreateICmpEQ(II->getArgOperand(0), RHS);
747203954Srdivacky        return new ZExtInst(Cmp, II->getType());
748203954Srdivacky      }
749203954Srdivacky    }
750203954Srdivacky
751218893Sdim    // If the shifted-out value is known-zero, then this is an exact shift.
752218893Sdim    if (!I.isExact() &&
753218893Sdim        MaskedValueIsZero(Op0,APInt::getLowBitsSet(Op1C->getBitWidth(),ShAmt))){
754218893Sdim      I.setIsExact();
755218893Sdim      return &I;
756218893Sdim    }
757218893Sdim  }
758218893Sdim
759203954Srdivacky  return 0;
760202375Srdivacky}
761202375Srdivacky
762202375SrdivackyInstruction *InstCombiner::visitAShr(BinaryOperator &I) {
763218893Sdim  if (Value *V = SimplifyAShrInst(I.getOperand(0), I.getOperand(1),
764218893Sdim                                  I.isExact(), TD))
765218893Sdim    return ReplaceInstUsesWith(I, V);
766218893Sdim
767202375Srdivacky  if (Instruction *R = commonShiftTransforms(I))
768202375Srdivacky    return R;
769202375Srdivacky
770202375Srdivacky  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
771218893Sdim
772202375Srdivacky  if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
773218893Sdim    unsigned ShAmt = Op1C->getZExtValue();
774218893Sdim
775202375Srdivacky    // If the input is a SHL by the same constant (ashr (shl X, C), C), then we
776202878Srdivacky    // have a sign-extend idiom.
777202375Srdivacky    Value *X;
778202878Srdivacky    if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1)))) {
779218893Sdim      // If the left shift is just shifting out partial signbits, delete the
780218893Sdim      // extension.
781218893Sdim      if (cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap())
782202878Srdivacky        return ReplaceInstUsesWith(I, X);
783202878Srdivacky
784202878Srdivacky      // If the input is an extension from the shifted amount value, e.g.
785202878Srdivacky      //   %x = zext i8 %A to i32
786202878Srdivacky      //   %y = shl i32 %x, 24
787202878Srdivacky      //   %z = ashr %y, 24
788202878Srdivacky      // then turn this into "z = sext i8 A to i32".
789202878Srdivacky      if (ZExtInst *ZI = dyn_cast<ZExtInst>(X)) {
790202878Srdivacky        uint32_t SrcBits = ZI->getOperand(0)->getType()->getScalarSizeInBits();
791202878Srdivacky        uint32_t DestBits = ZI->getType()->getScalarSizeInBits();
792202878Srdivacky        if (Op1C->getZExtValue() == DestBits-SrcBits)
793202878Srdivacky          return new SExtInst(ZI->getOperand(0), ZI->getType());
794202878Srdivacky      }
795202878Srdivacky    }
796218893Sdim
797218893Sdim    // If the shifted-out value is known-zero, then this is an exact shift.
798218893Sdim    if (!I.isExact() &&
799218893Sdim        MaskedValueIsZero(Op0,APInt::getLowBitsSet(Op1C->getBitWidth(),ShAmt))){
800218893Sdim      I.setIsExact();
801218893Sdim      return &I;
802218893Sdim    }
803202375Srdivacky  }
804202375Srdivacky
805202375Srdivacky  // See if we can turn a signed shr into an unsigned shr.
806202375Srdivacky  if (MaskedValueIsZero(Op0,
807202375Srdivacky                        APInt::getSignBit(I.getType()->getScalarSizeInBits())))
808202375Srdivacky    return BinaryOperator::CreateLShr(Op0, Op1);
809202375Srdivacky
810202375Srdivacky  // Arithmetic shifting an all-sign-bit value is a no-op.
811202375Srdivacky  unsigned NumSignBits = ComputeNumSignBits(Op0);
812202375Srdivacky  if (NumSignBits == Op0->getType()->getScalarSizeInBits())
813202375Srdivacky    return ReplaceInstUsesWith(I, Op0);
814202375Srdivacky
815202375Srdivacky  return 0;
816202375Srdivacky}
817202375Srdivacky
818