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