InstCombineShifts.cpp revision 203954
1193326Sed//===- InstCombineShifts.cpp ----------------------------------------------===// 2193326Sed// 3193326Sed// The LLVM Compiler Infrastructure 4193326Sed// 5193326Sed// This file is distributed under the University of Illinois Open Source 6193326Sed// License. See LICENSE.TXT for details. 7193326Sed// 8193326Sed//===----------------------------------------------------------------------===// 9193326Sed// 10193326Sed// This file implements the visitShl, visitLShr, and visitAShr functions. 11193326Sed// 12193326Sed//===----------------------------------------------------------------------===// 13193326Sed 14193326Sed#include "InstCombine.h" 15193326Sed#include "llvm/IntrinsicInst.h" 16193326Sed#include "llvm/Support/PatternMatch.h" 17219077Sdimusing namespace llvm; 18193326Sedusing namespace PatternMatch; 19193326Sed 20219077SdimInstruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) { 21239462Sdim assert(I.getOperand(1)->getType() == I.getOperand(0)->getType()); 22193326Sed Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 23193326Sed 24193326Sed // shl X, 0 == X and shr X, 0 == X 25193326Sed // shl 0, X == 0 and shr 0, X == 0 26193326Sed if (Op1 == Constant::getNullValue(Op1->getType()) || 27193326Sed Op0 == Constant::getNullValue(Op0->getType())) 28218893Sdim return ReplaceInstUsesWith(I, Op0); 29193326Sed 30193326Sed if (isa<UndefValue>(Op0)) { 31193326Sed if (I.getOpcode() == Instruction::AShr) // undef >>s X -> undef 32193326Sed return ReplaceInstUsesWith(I, Op0); 33193326Sed else // undef << X -> 0, undef >>u X -> 0 34198092Srdivacky return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 35193326Sed } 36193326Sed if (isa<UndefValue>(Op1)) { 37239462Sdim if (I.getOpcode() == Instruction::AShr) // X >>s undef -> X 38239462Sdim return ReplaceInstUsesWith(I, Op0); 39193326Sed else // X << undef, X >>u undef -> 0 40193326Sed return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 41193326Sed } 42193326Sed 43193326Sed // See if we can fold away this shift. 44193326Sed if (SimplifyDemandedInstructionBits(I)) 45193326Sed return &I; 46218893Sdim 47218893Sdim // Try to fold constant and into select arguments. 48193326Sed if (isa<Constant>(Op0)) 49198092Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 50193326Sed if (Instruction *R = FoldOpIntoSelect(I, SI)) 51193326Sed return R; 52193326Sed 53219077Sdim if (ConstantInt *CUI = dyn_cast<ConstantInt>(Op1)) 54193326Sed if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I)) 55193326Sed return Res; 56193326Sed return 0; 57193326Sed} 58193326Sed 59218893SdimInstruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1, 60249423Sdim BinaryOperator &I) { 61249423Sdim bool isLeftShift = I.getOpcode() == Instruction::Shl; 62193326Sed 63198092Srdivacky // See if we can simplify any instructions used by the instruction whose sole 64193326Sed // purpose is to compute bits we don't care about. 65193326Sed uint32_t TypeBits = Op0->getType()->getScalarSizeInBits(); 66193326Sed 67193326Sed // shl i32 X, 32 = 0 and srl i8 Y, 9 = 0, ... just don't eliminate 68219077Sdim // a signed shift. 69249423Sdim // 70193326Sed if (Op1->uge(TypeBits)) { 71193326Sed if (I.getOpcode() != Instruction::AShr) 72193326Sed return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType())); 73193326Sed // ashr i32 X, 32 --> ashr i32 X, 31 74218893Sdim I.setOperand(1, ConstantInt::get(I.getType(), TypeBits-1)); 75219077Sdim return &I; 76219077Sdim } 77219077Sdim 78219077Sdim // ((X*C1) << C2) == (X * (C1 << C2)) 79219077Sdim if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) 80219077Sdim if (BO->getOpcode() == Instruction::Mul && isLeftShift) 81219077Sdim if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1))) 82219077Sdim return BinaryOperator::CreateMul(BO->getOperand(0), 83219077Sdim ConstantExpr::getShl(BOOp, Op1)); 84219077Sdim 85219077Sdim // Try to fold constant and into select arguments. 86219077Sdim if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 87219077Sdim if (Instruction *R = FoldOpIntoSelect(I, SI)) 88219077Sdim return R; 89219077Sdim if (isa<PHINode>(Op0)) 90218893Sdim if (Instruction *NV = FoldOpIntoPhi(I)) 91218893Sdim return NV; 92193326Sed 93193326Sed // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2)) 94193326Sed if (TruncInst *TI = dyn_cast<TruncInst>(Op0)) { 95219077Sdim Instruction *TrOp = dyn_cast<Instruction>(TI->getOperand(0)); 96218893Sdim // If 'shift2' is an ashr, we would have to get the sign bit into a funny 97193326Sed // place. Don't try to do this transformation in this case. Also, we 98193326Sed // require that the input operand is a shift-by-constant so that we have 99198092Srdivacky // confidence that the shifts will get folded together. We could do this 100198092Srdivacky // xform in more cases, but it is unlikely to be profitable. 101218893Sdim if (TrOp && I.isLogicalShift() && TrOp->isShift() && 102198092Srdivacky isa<ConstantInt>(TrOp->getOperand(1))) { 103198092Srdivacky // Okay, we'll do this xform. Make the shift of shift. 104198092Srdivacky Constant *ShAmt = ConstantExpr::getZExt(Op1, TrOp->getType()); 105219077Sdim // (shift2 (shift1 & 0x00FF), c2) 106198092Srdivacky Value *NSh = Builder->CreateBinOp(I.getOpcode(), TrOp, ShAmt,I.getName()); 107198092Srdivacky 108198092Srdivacky // For logical shifts, the truncation has the effect of making the high 109198092Srdivacky // part of the register be zeros. Emulate this by inserting an AND to 110218893Sdim // clear the top bits as needed. This 'and' will usually be zapped by 111218893Sdim // other xforms later if dead. 112193326Sed unsigned SrcSize = TrOp->getType()->getScalarSizeInBits(); 113239462Sdim unsigned DstSize = TI->getType()->getScalarSizeInBits(); 114239462Sdim APInt MaskV(APInt::getLowBitsSet(SrcSize, DstSize)); 115239462Sdim 116193326Sed // The mask we constructed says what the trunc would do if occurring 117193326Sed // between the shifts. We want to know the effect *after* the second 118193326Sed // shift. We know that it is a logical shift by a constant, so adjust the 119219077Sdim // mask as appropriate. 120219077Sdim if (I.getOpcode() == Instruction::Shl) 121219077Sdim MaskV <<= Op1->getZExtValue(); 122219077Sdim else { 123219077Sdim assert(I.getOpcode() == Instruction::LShr && "Unknown logical shift"); 124219077Sdim MaskV = MaskV.lshr(Op1->getZExtValue()); 125219077Sdim } 126219077Sdim 127219077Sdim // shift1 & 0x00FF 128219077Sdim Value *And = Builder->CreateAnd(NSh, 129219077Sdim ConstantInt::get(I.getContext(), MaskV), 130219077Sdim TI->getName()); 131219077Sdim 132219077Sdim // Return the value truncated to the interesting size. 133219077Sdim return new TruncInst(And, I.getType()); 134219077Sdim } 135219077Sdim } 136219077Sdim 137219077Sdim if (Op0->hasOneUse()) { 138234353Sdim if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) { 139219077Sdim // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 140219077Sdim Value *V1, *V2; 141219077Sdim ConstantInt *CC; 142219077Sdim switch (Op0BO->getOpcode()) { 143219077Sdim default: break; 144219077Sdim case Instruction::Add: 145219077Sdim case Instruction::And: 146219077Sdim case Instruction::Or: 147219077Sdim case Instruction::Xor: { 148219077Sdim // These operators commute. 149219077Sdim // Turn (Y + (X >> C)) << C -> (X + (Y << C)) & (~0 << C) 150219077Sdim if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() && 151219077Sdim match(Op0BO->getOperand(1), m_Shr(m_Value(V1), 152219077Sdim m_Specific(Op1)))) { 153219077Sdim Value *YS = // (Y << C) 154219077Sdim Builder->CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName()); 155219077Sdim // (X + (Y << C)) 156219077Sdim Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), YS, V1, 157219077Sdim Op0BO->getOperand(1)->getName()); 158219077Sdim uint32_t Op1Val = Op1->getLimitedValue(TypeBits); 159219077Sdim return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(), 160193326Sed APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val))); 161193326Sed } 162193326Sed 163193326Sed // Turn (Y + ((X >> C) & CC)) << C -> ((X & (CC << C)) + (Y << C)) 164193326Sed Value *Op0BOOp1 = Op0BO->getOperand(1); 165193326Sed if (isLeftShift && Op0BOOp1->hasOneUse() && 166193326Sed match(Op0BOOp1, 167193326Sed m_And(m_Shr(m_Value(V1), m_Specific(Op1)), 168193326Sed m_ConstantInt(CC))) && 169219077Sdim cast<BinaryOperator>(Op0BOOp1)->getOperand(0)->hasOneUse()) { 170193326Sed Value *YS = // (Y << C) 171193326Sed Builder->CreateShl(Op0BO->getOperand(0), Op1, 172193326Sed Op0BO->getName()); 173193326Sed // X & (CC << C) 174193326Sed Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1), 175193326Sed V1->getName()+".mask"); 176193326Sed return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM); 177193326Sed } 178234353Sdim } 179193326Sed 180193326Sed // FALL THROUGH. 181224145Sdim case Instruction::Sub: { 182224145Sdim // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 183224145Sdim if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 184224145Sdim match(Op0BO->getOperand(0), m_Shr(m_Value(V1), 185224145Sdim m_Specific(Op1)))) { 186224145Sdim Value *YS = // (Y << C) 187224145Sdim Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 188224145Sdim // (X + (Y << C)) 189224145Sdim Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), V1, YS, 190224145Sdim Op0BO->getOperand(0)->getName()); 191224145Sdim uint32_t Op1Val = Op1->getLimitedValue(TypeBits); 192224145Sdim return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(), 193224145Sdim APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val))); 194224145Sdim } 195224145Sdim 196224145Sdim // Turn (((X >> C)&CC) + Y) << C -> (X + (Y << C)) & (CC << C) 197224145Sdim if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 198234353Sdim match(Op0BO->getOperand(0), 199234353Sdim m_And(m_Shr(m_Value(V1), m_Value(V2)), 200224145Sdim m_ConstantInt(CC))) && V2 == Op1 && 201224145Sdim cast<BinaryOperator>(Op0BO->getOperand(0)) 202218893Sdim ->getOperand(0)->hasOneUse()) { 203218893Sdim Value *YS = // (Y << C) 204218893Sdim Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 205218893Sdim // X & (CC << C) 206218893Sdim Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1), 207218893Sdim V1->getName()+".mask"); 208219077Sdim 209218893Sdim return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS); 210218893Sdim } 211218893Sdim 212218893Sdim break; 213218893Sdim } 214218893Sdim } 215218893Sdim 216218893Sdim 217234353Sdim // If the operand is an bitwise operator with a constant RHS, and the 218218893Sdim // shift is the only use, we can pull it out of the shift. 219218893Sdim if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) { 220193326Sed bool isValid = true; // Valid only for And, Or, Xor 221193326Sed bool highBitSet = false; // Transform if high bit of constant set? 222198092Srdivacky 223226633Sdim switch (Op0BO->getOpcode()) { 224193326Sed default: isValid = false; break; // Do not perform transform! 225193326Sed case Instruction::Add: 226193326Sed isValid = isLeftShift; 227193326Sed break; 228193326Sed case Instruction::Or: 229193326Sed case Instruction::Xor: 230193326Sed highBitSet = false; 231193326Sed break; 232193326Sed case Instruction::And: 233193326Sed highBitSet = true; 234234353Sdim break; 235234353Sdim } 236234353Sdim 237219077Sdim // If this is a signed shift right, and the high bit is modified 238193326Sed // by the logical operation, do not perform the transformation. 239193326Sed // The highBitSet boolean indicates the value of the high bit of 240219077Sdim // the constant which would cause it to be modified for this 241219077Sdim // operation. 242219077Sdim // 243219077Sdim if (isValid && I.getOpcode() == Instruction::AShr) 244193326Sed isValid = Op0C->getValue()[TypeBits-1] == highBitSet; 245193326Sed 246193326Sed if (isValid) { 247193326Sed Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, Op1); 248193326Sed 249193326Sed Value *NewShift = 250193326Sed Builder->CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1); 251193326Sed NewShift->takeName(Op0BO); 252218893Sdim 253193326Sed return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, 254193326Sed NewRHS); 255198092Srdivacky } 256198092Srdivacky } 257198092Srdivacky } 258208600Srdivacky } 259198092Srdivacky 260198092Srdivacky // Find out if this is a shift of a shift by a constant. 261198092Srdivacky BinaryOperator *ShiftOp = dyn_cast<BinaryOperator>(Op0); 262198092Srdivacky if (ShiftOp && !ShiftOp->isShift()) 263198092Srdivacky ShiftOp = 0; 264208600Srdivacky 265208600Srdivacky if (ShiftOp && isa<ConstantInt>(ShiftOp->getOperand(1))) { 266198092Srdivacky ConstantInt *ShiftAmt1C = cast<ConstantInt>(ShiftOp->getOperand(1)); 267198092Srdivacky uint32_t ShiftAmt1 = ShiftAmt1C->getLimitedValue(TypeBits); 268198092Srdivacky uint32_t ShiftAmt2 = Op1->getLimitedValue(TypeBits); 269198092Srdivacky assert(ShiftAmt2 != 0 && "Should have been simplified earlier"); 270198092Srdivacky if (ShiftAmt1 == 0) return 0; // Will be simplified in the future. 271198092Srdivacky Value *X = ShiftOp->getOperand(0); 272198092Srdivacky 273249423Sdim uint32_t AmtSum = ShiftAmt1+ShiftAmt2; // Fold into one big shift. 274249423Sdim 275198092Srdivacky const IntegerType *Ty = cast<IntegerType>(I.getType()); 276198092Srdivacky 277249423Sdim // Check for (X << c1) << c2 and (X >> c1) >> c2 278198092Srdivacky if (I.getOpcode() == ShiftOp->getOpcode()) { 279193326Sed // If this is oversized composite shift, then unsigned shifts get 0, ashr 280193326Sed // saturates. 281193326Sed if (AmtSum >= TypeBits) { 282193326Sed if (I.getOpcode() != Instruction::AShr) 283193326Sed return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 284193326Sed AmtSum = TypeBits-1; // Saturate to 31 for i32 ashr. 285193326Sed } 286195341Sed 287195341Sed return BinaryOperator::Create(I.getOpcode(), X, 288193326Sed ConstantInt::get(Ty, AmtSum)); 289219077Sdim } 290219077Sdim 291219077Sdim if (ShiftOp->getOpcode() == Instruction::LShr && 292219077Sdim I.getOpcode() == Instruction::AShr) { 293219077Sdim if (AmtSum >= TypeBits) 294219077Sdim return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 295219077Sdim 296219077Sdim // ((X >>u C1) >>s C2) -> (X >>u (C1+C2)) since C1 != 0. 297219077Sdim return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, AmtSum)); 298219077Sdim } 299219077Sdim 300219077Sdim if (ShiftOp->getOpcode() == Instruction::AShr && 301219077Sdim I.getOpcode() == Instruction::LShr) { 302219077Sdim // ((X >>s C1) >>u C2) -> ((X >>s (C1+C2)) & mask) since C1 != 0. 303219077Sdim if (AmtSum >= TypeBits) 304219077Sdim AmtSum = TypeBits-1; 305219077Sdim 306219077Sdim Value *Shift = Builder->CreateAShr(X, ConstantInt::get(Ty, AmtSum)); 307219077Sdim 308219077Sdim APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 309219077Sdim return BinaryOperator::CreateAnd(Shift, 310219077Sdim ConstantInt::get(I.getContext(), Mask)); 311219077Sdim } 312219077Sdim 313219077Sdim // Okay, if we get here, one shift must be left, and the other shift must be 314219077Sdim // right. See if the amounts are equal. 315219077Sdim if (ShiftAmt1 == ShiftAmt2) { 316219077Sdim // If we have ((X >>? C) << C), turn this into X & (-1 << C). 317219077Sdim if (I.getOpcode() == Instruction::Shl) { 318219077Sdim APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt1)); 319219077Sdim return BinaryOperator::CreateAnd(X, 320219077Sdim ConstantInt::get(I.getContext(),Mask)); 321219077Sdim } 322219077Sdim // If we have ((X << C) >>u C), turn this into X & (-1 >>u C). 323219077Sdim if (I.getOpcode() == Instruction::LShr) { 324219077Sdim APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt1)); 325219077Sdim return BinaryOperator::CreateAnd(X, 326219077Sdim ConstantInt::get(I.getContext(), Mask)); 327219077Sdim } 328219077Sdim } else if (ShiftAmt1 < ShiftAmt2) { 329219077Sdim uint32_t ShiftDiff = ShiftAmt2-ShiftAmt1; 330219077Sdim 331219077Sdim // (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2) 332219077Sdim if (I.getOpcode() == Instruction::Shl) { 333219077Sdim assert(ShiftOp->getOpcode() == Instruction::LShr || 334219077Sdim ShiftOp->getOpcode() == Instruction::AShr); 335219077Sdim Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff)); 336219077Sdim 337219077Sdim APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2)); 338219077Sdim return BinaryOperator::CreateAnd(Shift, 339219077Sdim ConstantInt::get(I.getContext(),Mask)); 340219077Sdim } 341219077Sdim 342219077Sdim // (X << C1) >>u C2 --> X >>u (C2-C1) & (-1 >> C2) 343219077Sdim if (I.getOpcode() == Instruction::LShr) { 344219077Sdim assert(ShiftOp->getOpcode() == Instruction::Shl); 345219077Sdim Value *Shift = Builder->CreateLShr(X, ConstantInt::get(Ty, ShiftDiff)); 346219077Sdim 347219077Sdim APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 348219077Sdim return BinaryOperator::CreateAnd(Shift, 349219077Sdim ConstantInt::get(I.getContext(),Mask)); 350219077Sdim } 351219077Sdim 352219077Sdim // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in. 353219077Sdim } else { 354219077Sdim assert(ShiftAmt2 < ShiftAmt1); 355219077Sdim uint32_t ShiftDiff = ShiftAmt1-ShiftAmt2; 356219077Sdim 357219077Sdim // (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2) 358219077Sdim if (I.getOpcode() == Instruction::Shl) { 359219077Sdim assert(ShiftOp->getOpcode() == Instruction::LShr || 360219077Sdim ShiftOp->getOpcode() == Instruction::AShr); 361219077Sdim Value *Shift = Builder->CreateBinOp(ShiftOp->getOpcode(), X, 362219077Sdim ConstantInt::get(Ty, ShiftDiff)); 363219077Sdim 364219077Sdim APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2)); 365219077Sdim return BinaryOperator::CreateAnd(Shift, 366219077Sdim ConstantInt::get(I.getContext(),Mask)); 367219077Sdim } 368219077Sdim 369219077Sdim // (X << C1) >>u C2 --> X << (C1-C2) & (-1 >> C2) 370219077Sdim if (I.getOpcode() == Instruction::LShr) { 371219077Sdim assert(ShiftOp->getOpcode() == Instruction::Shl); 372219077Sdim Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff)); 373219077Sdim 374219077Sdim APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 375219077Sdim return BinaryOperator::CreateAnd(Shift, 376219077Sdim ConstantInt::get(I.getContext(),Mask)); 377219077Sdim } 378219077Sdim 379219077Sdim // We can't handle (X << C1) >>a C2, it shifts arbitrary bits in. 380219077Sdim } 381219077Sdim } 382219077Sdim return 0; 383234353Sdim} 384234353Sdim 385219077SdimInstruction *InstCombiner::visitShl(BinaryOperator &I) { 386219077Sdim return commonShiftTransforms(I); 387219077Sdim} 388219077Sdim 389219077SdimInstruction *InstCombiner::visitLShr(BinaryOperator &I) { 390219077Sdim if (Instruction *R = commonShiftTransforms(I)) 391219077Sdim return R; 392219077Sdim 393219077Sdim Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 394219077Sdim 395219077Sdim if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) 396219077Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) { 397221345Sdim unsigned BitWidth = Op0->getType()->getScalarSizeInBits(); 398221345Sdim // ctlz.i32(x)>>5 --> zext(x == 0) 399221345Sdim // cttz.i32(x)>>5 --> zext(x == 0) 400221345Sdim // ctpop.i32(x)>>5 --> zext(x == -1) 401221345Sdim if ((II->getIntrinsicID() == Intrinsic::ctlz || 402221345Sdim II->getIntrinsicID() == Intrinsic::cttz || 403221345Sdim II->getIntrinsicID() == Intrinsic::ctpop) && 404221345Sdim isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == Op1C->getZExtValue()){ 405221345Sdim bool isCtPop = II->getIntrinsicID() == Intrinsic::ctpop; 406221345Sdim Constant *RHS = ConstantInt::getSigned(Op0->getType(), isCtPop ? -1:0); 407221345Sdim Value *Cmp = Builder->CreateICmpEQ(II->getOperand(1), RHS); 408221345Sdim return new ZExtInst(Cmp, II->getType()); 409221345Sdim } 410221345Sdim } 411221345Sdim 412221345Sdim return 0; 413221345Sdim} 414221345Sdim 415221345SdimInstruction *InstCombiner::visitAShr(BinaryOperator &I) { 416221345Sdim if (Instruction *R = commonShiftTransforms(I)) 417221345Sdim return R; 418221345Sdim 419221345Sdim Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 420221345Sdim 421221345Sdim if (ConstantInt *CSI = dyn_cast<ConstantInt>(Op0)) { 422221345Sdim // ashr int -1, X = -1 (for any arithmetic shift rights of ~0) 423221345Sdim if (CSI->isAllOnesValue()) 424221345Sdim return ReplaceInstUsesWith(I, CSI); 425221345Sdim } 426221345Sdim 427221345Sdim if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 428221345Sdim // If the input is a SHL by the same constant (ashr (shl X, C), C), then we 429221345Sdim // have a sign-extend idiom. 430221345Sdim Value *X; 431221345Sdim if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1)))) { 432221345Sdim // If the input value is known to already be sign extended enough, delete 433221345Sdim // the extension. 434221345Sdim if (ComputeNumSignBits(X) > Op1C->getZExtValue()) 435221345Sdim return ReplaceInstUsesWith(I, X); 436221345Sdim 437221345Sdim // If the input is an extension from the shifted amount value, e.g. 438221345Sdim // %x = zext i8 %A to i32 439221345Sdim // %y = shl i32 %x, 24 440221345Sdim // %z = ashr %y, 24 441221345Sdim // then turn this into "z = sext i8 A to i32". 442221345Sdim if (ZExtInst *ZI = dyn_cast<ZExtInst>(X)) { 443221345Sdim uint32_t SrcBits = ZI->getOperand(0)->getType()->getScalarSizeInBits(); 444221345Sdim uint32_t DestBits = ZI->getType()->getScalarSizeInBits(); 445221345Sdim if (Op1C->getZExtValue() == DestBits-SrcBits) 446221345Sdim return new SExtInst(ZI->getOperand(0), ZI->getType()); 447221345Sdim } 448221345Sdim } 449221345Sdim } 450221345Sdim 451221345Sdim // See if we can turn a signed shr into an unsigned shr. 452221345Sdim if (MaskedValueIsZero(Op0, 453221345Sdim APInt::getSignBit(I.getType()->getScalarSizeInBits()))) 454221345Sdim return BinaryOperator::CreateLShr(Op0, Op1); 455221345Sdim 456221345Sdim // Arithmetic shifting an all-sign-bit value is a no-op. 457221345Sdim unsigned NumSignBits = ComputeNumSignBits(Op0); 458221345Sdim if (NumSignBits == Op0->getType()->getScalarSizeInBits()) 459221345Sdim return ReplaceInstUsesWith(I, Op0); 460221345Sdim 461221345Sdim return 0; 462221345Sdim} 463221345Sdim 464221345Sdim