InstCombineShifts.cpp revision 210299
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" 16202375Srdivacky#include "llvm/Support/PatternMatch.h" 17202375Srdivackyusing namespace llvm; 18202375Srdivackyusing namespace PatternMatch; 19202375Srdivacky 20202375SrdivackyInstruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) { 21202375Srdivacky assert(I.getOperand(1)->getType() == I.getOperand(0)->getType()); 22202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 23202375Srdivacky 24202375Srdivacky // shl X, 0 == X and shr X, 0 == X 25202375Srdivacky // shl 0, X == 0 and shr 0, X == 0 26202375Srdivacky if (Op1 == Constant::getNullValue(Op1->getType()) || 27202375Srdivacky Op0 == Constant::getNullValue(Op0->getType())) 28202375Srdivacky return ReplaceInstUsesWith(I, Op0); 29202375Srdivacky 30202375Srdivacky if (isa<UndefValue>(Op0)) { 31202375Srdivacky if (I.getOpcode() == Instruction::AShr) // undef >>s X -> undef 32202375Srdivacky return ReplaceInstUsesWith(I, Op0); 33202375Srdivacky else // undef << X -> 0, undef >>u X -> 0 34202375Srdivacky return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 35202375Srdivacky } 36202375Srdivacky if (isa<UndefValue>(Op1)) { 37202375Srdivacky if (I.getOpcode() == Instruction::AShr) // X >>s undef -> X 38202375Srdivacky return ReplaceInstUsesWith(I, Op0); 39202375Srdivacky else // X << undef, X >>u undef -> 0 40202375Srdivacky return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 41202375Srdivacky } 42202375Srdivacky 43202375Srdivacky // See if we can fold away this shift. 44202375Srdivacky if (SimplifyDemandedInstructionBits(I)) 45202375Srdivacky return &I; 46202375Srdivacky 47202375Srdivacky // Try to fold constant and into select arguments. 48202375Srdivacky if (isa<Constant>(Op0)) 49202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 50202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 51202375Srdivacky return R; 52202375Srdivacky 53202375Srdivacky if (ConstantInt *CUI = dyn_cast<ConstantInt>(Op1)) 54202375Srdivacky if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I)) 55202375Srdivacky return Res; 56202375Srdivacky return 0; 57202375Srdivacky} 58202375Srdivacky 59202375SrdivackyInstruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1, 60202375Srdivacky BinaryOperator &I) { 61202375Srdivacky bool isLeftShift = I.getOpcode() == Instruction::Shl; 62202375Srdivacky 63202375Srdivacky // See if we can simplify any instructions used by the instruction whose sole 64202375Srdivacky // purpose is to compute bits we don't care about. 65202375Srdivacky uint32_t TypeBits = Op0->getType()->getScalarSizeInBits(); 66202375Srdivacky 67202375Srdivacky // shl i32 X, 32 = 0 and srl i8 Y, 9 = 0, ... just don't eliminate 68202375Srdivacky // a signed shift. 69202375Srdivacky // 70202375Srdivacky if (Op1->uge(TypeBits)) { 71202375Srdivacky if (I.getOpcode() != Instruction::AShr) 72202375Srdivacky return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType())); 73203954Srdivacky // ashr i32 X, 32 --> ashr i32 X, 31 74203954Srdivacky I.setOperand(1, ConstantInt::get(I.getType(), TypeBits-1)); 75203954Srdivacky return &I; 76202375Srdivacky } 77202375Srdivacky 78202375Srdivacky // ((X*C1) << C2) == (X * (C1 << C2)) 79202375Srdivacky if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) 80202375Srdivacky if (BO->getOpcode() == Instruction::Mul && isLeftShift) 81202375Srdivacky if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1))) 82202375Srdivacky return BinaryOperator::CreateMul(BO->getOperand(0), 83202375Srdivacky ConstantExpr::getShl(BOOp, Op1)); 84202375Srdivacky 85202375Srdivacky // Try to fold constant and into select arguments. 86202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 87202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 88202375Srdivacky return R; 89202375Srdivacky if (isa<PHINode>(Op0)) 90202375Srdivacky if (Instruction *NV = FoldOpIntoPhi(I)) 91202375Srdivacky return NV; 92202375Srdivacky 93202375Srdivacky // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2)) 94202375Srdivacky if (TruncInst *TI = dyn_cast<TruncInst>(Op0)) { 95202375Srdivacky Instruction *TrOp = dyn_cast<Instruction>(TI->getOperand(0)); 96202375Srdivacky // If 'shift2' is an ashr, we would have to get the sign bit into a funny 97202375Srdivacky // place. Don't try to do this transformation in this case. Also, we 98202375Srdivacky // require that the input operand is a shift-by-constant so that we have 99202375Srdivacky // confidence that the shifts will get folded together. We could do this 100202375Srdivacky // xform in more cases, but it is unlikely to be profitable. 101202375Srdivacky if (TrOp && I.isLogicalShift() && TrOp->isShift() && 102202375Srdivacky isa<ConstantInt>(TrOp->getOperand(1))) { 103202375Srdivacky // Okay, we'll do this xform. Make the shift of shift. 104202375Srdivacky Constant *ShAmt = ConstantExpr::getZExt(Op1, TrOp->getType()); 105202375Srdivacky // (shift2 (shift1 & 0x00FF), c2) 106202375Srdivacky Value *NSh = Builder->CreateBinOp(I.getOpcode(), TrOp, ShAmt,I.getName()); 107202375Srdivacky 108202375Srdivacky // For logical shifts, the truncation has the effect of making the high 109202375Srdivacky // part of the register be zeros. Emulate this by inserting an AND to 110202375Srdivacky // clear the top bits as needed. This 'and' will usually be zapped by 111202375Srdivacky // other xforms later if dead. 112202375Srdivacky unsigned SrcSize = TrOp->getType()->getScalarSizeInBits(); 113202375Srdivacky unsigned DstSize = TI->getType()->getScalarSizeInBits(); 114202375Srdivacky APInt MaskV(APInt::getLowBitsSet(SrcSize, DstSize)); 115202375Srdivacky 116202375Srdivacky // The mask we constructed says what the trunc would do if occurring 117202375Srdivacky // between the shifts. We want to know the effect *after* the second 118202375Srdivacky // shift. We know that it is a logical shift by a constant, so adjust the 119202375Srdivacky // mask as appropriate. 120202375Srdivacky if (I.getOpcode() == Instruction::Shl) 121202375Srdivacky MaskV <<= Op1->getZExtValue(); 122202375Srdivacky else { 123202375Srdivacky assert(I.getOpcode() == Instruction::LShr && "Unknown logical shift"); 124202375Srdivacky MaskV = MaskV.lshr(Op1->getZExtValue()); 125202375Srdivacky } 126202375Srdivacky 127202375Srdivacky // shift1 & 0x00FF 128202375Srdivacky Value *And = Builder->CreateAnd(NSh, 129202375Srdivacky ConstantInt::get(I.getContext(), MaskV), 130202375Srdivacky TI->getName()); 131202375Srdivacky 132202375Srdivacky // Return the value truncated to the interesting size. 133202375Srdivacky return new TruncInst(And, I.getType()); 134202375Srdivacky } 135202375Srdivacky } 136202375Srdivacky 137202375Srdivacky if (Op0->hasOneUse()) { 138202375Srdivacky if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) { 139202375Srdivacky // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 140202375Srdivacky Value *V1, *V2; 141202375Srdivacky ConstantInt *CC; 142202375Srdivacky switch (Op0BO->getOpcode()) { 143202375Srdivacky default: break; 144202375Srdivacky case Instruction::Add: 145202375Srdivacky case Instruction::And: 146202375Srdivacky case Instruction::Or: 147202375Srdivacky case Instruction::Xor: { 148202375Srdivacky // These operators commute. 149202375Srdivacky // Turn (Y + (X >> C)) << C -> (X + (Y << C)) & (~0 << C) 150202375Srdivacky if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() && 151202375Srdivacky match(Op0BO->getOperand(1), m_Shr(m_Value(V1), 152202375Srdivacky m_Specific(Op1)))) { 153202375Srdivacky Value *YS = // (Y << C) 154202375Srdivacky Builder->CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName()); 155202375Srdivacky // (X + (Y << C)) 156202375Srdivacky Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), YS, V1, 157202375Srdivacky Op0BO->getOperand(1)->getName()); 158202375Srdivacky uint32_t Op1Val = Op1->getLimitedValue(TypeBits); 159202375Srdivacky return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(), 160202375Srdivacky APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val))); 161202375Srdivacky } 162202375Srdivacky 163202375Srdivacky // Turn (Y + ((X >> C) & CC)) << C -> ((X & (CC << C)) + (Y << C)) 164202375Srdivacky Value *Op0BOOp1 = Op0BO->getOperand(1); 165202375Srdivacky if (isLeftShift && Op0BOOp1->hasOneUse() && 166202375Srdivacky match(Op0BOOp1, 167202375Srdivacky m_And(m_Shr(m_Value(V1), m_Specific(Op1)), 168202375Srdivacky m_ConstantInt(CC))) && 169202375Srdivacky cast<BinaryOperator>(Op0BOOp1)->getOperand(0)->hasOneUse()) { 170202375Srdivacky Value *YS = // (Y << C) 171202375Srdivacky Builder->CreateShl(Op0BO->getOperand(0), Op1, 172202375Srdivacky Op0BO->getName()); 173202375Srdivacky // X & (CC << C) 174202375Srdivacky Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1), 175202375Srdivacky V1->getName()+".mask"); 176202375Srdivacky return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM); 177202375Srdivacky } 178202375Srdivacky } 179202375Srdivacky 180202375Srdivacky // FALL THROUGH. 181202375Srdivacky case Instruction::Sub: { 182202375Srdivacky // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 183202375Srdivacky if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 184202375Srdivacky match(Op0BO->getOperand(0), m_Shr(m_Value(V1), 185202375Srdivacky m_Specific(Op1)))) { 186202375Srdivacky Value *YS = // (Y << C) 187202375Srdivacky Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 188202375Srdivacky // (X + (Y << C)) 189202375Srdivacky Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), V1, YS, 190202375Srdivacky Op0BO->getOperand(0)->getName()); 191202375Srdivacky uint32_t Op1Val = Op1->getLimitedValue(TypeBits); 192202375Srdivacky return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(), 193202375Srdivacky APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val))); 194202375Srdivacky } 195202375Srdivacky 196202375Srdivacky // Turn (((X >> C)&CC) + Y) << C -> (X + (Y << C)) & (CC << C) 197202375Srdivacky if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 198202375Srdivacky match(Op0BO->getOperand(0), 199202375Srdivacky m_And(m_Shr(m_Value(V1), m_Value(V2)), 200202375Srdivacky m_ConstantInt(CC))) && V2 == Op1 && 201202375Srdivacky cast<BinaryOperator>(Op0BO->getOperand(0)) 202202375Srdivacky ->getOperand(0)->hasOneUse()) { 203202375Srdivacky Value *YS = // (Y << C) 204202375Srdivacky Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 205202375Srdivacky // X & (CC << C) 206202375Srdivacky Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1), 207202375Srdivacky V1->getName()+".mask"); 208202375Srdivacky 209202375Srdivacky return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS); 210202375Srdivacky } 211202375Srdivacky 212202375Srdivacky break; 213202375Srdivacky } 214202375Srdivacky } 215202375Srdivacky 216202375Srdivacky 217202375Srdivacky // If the operand is an bitwise operator with a constant RHS, and the 218202375Srdivacky // shift is the only use, we can pull it out of the shift. 219202375Srdivacky if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) { 220202375Srdivacky bool isValid = true; // Valid only for And, Or, Xor 221202375Srdivacky bool highBitSet = false; // Transform if high bit of constant set? 222202375Srdivacky 223202375Srdivacky switch (Op0BO->getOpcode()) { 224202375Srdivacky default: isValid = false; break; // Do not perform transform! 225202375Srdivacky case Instruction::Add: 226202375Srdivacky isValid = isLeftShift; 227202375Srdivacky break; 228202375Srdivacky case Instruction::Or: 229202375Srdivacky case Instruction::Xor: 230202375Srdivacky highBitSet = false; 231202375Srdivacky break; 232202375Srdivacky case Instruction::And: 233202375Srdivacky highBitSet = true; 234202375Srdivacky break; 235202375Srdivacky } 236202375Srdivacky 237202375Srdivacky // If this is a signed shift right, and the high bit is modified 238202375Srdivacky // by the logical operation, do not perform the transformation. 239202375Srdivacky // The highBitSet boolean indicates the value of the high bit of 240202375Srdivacky // the constant which would cause it to be modified for this 241202375Srdivacky // operation. 242202375Srdivacky // 243202375Srdivacky if (isValid && I.getOpcode() == Instruction::AShr) 244202375Srdivacky isValid = Op0C->getValue()[TypeBits-1] == highBitSet; 245202375Srdivacky 246202375Srdivacky if (isValid) { 247202375Srdivacky Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, Op1); 248202375Srdivacky 249202375Srdivacky Value *NewShift = 250202375Srdivacky Builder->CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1); 251202375Srdivacky NewShift->takeName(Op0BO); 252202375Srdivacky 253202375Srdivacky return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, 254202375Srdivacky NewRHS); 255202375Srdivacky } 256202375Srdivacky } 257202375Srdivacky } 258202375Srdivacky } 259202375Srdivacky 260202375Srdivacky // Find out if this is a shift of a shift by a constant. 261202375Srdivacky BinaryOperator *ShiftOp = dyn_cast<BinaryOperator>(Op0); 262202375Srdivacky if (ShiftOp && !ShiftOp->isShift()) 263202375Srdivacky ShiftOp = 0; 264202375Srdivacky 265202375Srdivacky if (ShiftOp && isa<ConstantInt>(ShiftOp->getOperand(1))) { 266202375Srdivacky ConstantInt *ShiftAmt1C = cast<ConstantInt>(ShiftOp->getOperand(1)); 267202375Srdivacky uint32_t ShiftAmt1 = ShiftAmt1C->getLimitedValue(TypeBits); 268202375Srdivacky uint32_t ShiftAmt2 = Op1->getLimitedValue(TypeBits); 269202375Srdivacky assert(ShiftAmt2 != 0 && "Should have been simplified earlier"); 270202375Srdivacky if (ShiftAmt1 == 0) return 0; // Will be simplified in the future. 271202375Srdivacky Value *X = ShiftOp->getOperand(0); 272202375Srdivacky 273202375Srdivacky uint32_t AmtSum = ShiftAmt1+ShiftAmt2; // Fold into one big shift. 274202375Srdivacky 275202375Srdivacky const IntegerType *Ty = cast<IntegerType>(I.getType()); 276202375Srdivacky 277202375Srdivacky // Check for (X << c1) << c2 and (X >> c1) >> c2 278202375Srdivacky if (I.getOpcode() == ShiftOp->getOpcode()) { 279202375Srdivacky // If this is oversized composite shift, then unsigned shifts get 0, ashr 280202375Srdivacky // saturates. 281202375Srdivacky if (AmtSum >= TypeBits) { 282202375Srdivacky if (I.getOpcode() != Instruction::AShr) 283202375Srdivacky return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 284202375Srdivacky AmtSum = TypeBits-1; // Saturate to 31 for i32 ashr. 285202375Srdivacky } 286202375Srdivacky 287202375Srdivacky return BinaryOperator::Create(I.getOpcode(), X, 288202375Srdivacky ConstantInt::get(Ty, AmtSum)); 289202375Srdivacky } 290202375Srdivacky 291202375Srdivacky if (ShiftOp->getOpcode() == Instruction::LShr && 292202375Srdivacky I.getOpcode() == Instruction::AShr) { 293202375Srdivacky if (AmtSum >= TypeBits) 294202375Srdivacky return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 295202375Srdivacky 296202375Srdivacky // ((X >>u C1) >>s C2) -> (X >>u (C1+C2)) since C1 != 0. 297202375Srdivacky return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, AmtSum)); 298202375Srdivacky } 299202375Srdivacky 300202375Srdivacky if (ShiftOp->getOpcode() == Instruction::AShr && 301202375Srdivacky I.getOpcode() == Instruction::LShr) { 302202375Srdivacky // ((X >>s C1) >>u C2) -> ((X >>s (C1+C2)) & mask) since C1 != 0. 303202375Srdivacky if (AmtSum >= TypeBits) 304202375Srdivacky AmtSum = TypeBits-1; 305202375Srdivacky 306202375Srdivacky Value *Shift = Builder->CreateAShr(X, ConstantInt::get(Ty, AmtSum)); 307202375Srdivacky 308202375Srdivacky APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 309202375Srdivacky return BinaryOperator::CreateAnd(Shift, 310202375Srdivacky ConstantInt::get(I.getContext(), Mask)); 311202375Srdivacky } 312202375Srdivacky 313202375Srdivacky // Okay, if we get here, one shift must be left, and the other shift must be 314202375Srdivacky // right. See if the amounts are equal. 315202375Srdivacky if (ShiftAmt1 == ShiftAmt2) { 316202375Srdivacky // If we have ((X >>? C) << C), turn this into X & (-1 << C). 317202375Srdivacky if (I.getOpcode() == Instruction::Shl) { 318202375Srdivacky APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt1)); 319202375Srdivacky return BinaryOperator::CreateAnd(X, 320202375Srdivacky ConstantInt::get(I.getContext(),Mask)); 321202375Srdivacky } 322202375Srdivacky // If we have ((X << C) >>u C), turn this into X & (-1 >>u C). 323202375Srdivacky if (I.getOpcode() == Instruction::LShr) { 324202375Srdivacky APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt1)); 325202375Srdivacky return BinaryOperator::CreateAnd(X, 326202375Srdivacky ConstantInt::get(I.getContext(), Mask)); 327202375Srdivacky } 328202375Srdivacky } else if (ShiftAmt1 < ShiftAmt2) { 329202375Srdivacky uint32_t ShiftDiff = ShiftAmt2-ShiftAmt1; 330202375Srdivacky 331202375Srdivacky // (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2) 332202375Srdivacky if (I.getOpcode() == Instruction::Shl) { 333202375Srdivacky assert(ShiftOp->getOpcode() == Instruction::LShr || 334202375Srdivacky ShiftOp->getOpcode() == Instruction::AShr); 335202375Srdivacky Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff)); 336202375Srdivacky 337202375Srdivacky APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2)); 338202375Srdivacky return BinaryOperator::CreateAnd(Shift, 339202375Srdivacky ConstantInt::get(I.getContext(),Mask)); 340202375Srdivacky } 341202375Srdivacky 342202375Srdivacky // (X << C1) >>u C2 --> X >>u (C2-C1) & (-1 >> C2) 343202375Srdivacky if (I.getOpcode() == Instruction::LShr) { 344202375Srdivacky assert(ShiftOp->getOpcode() == Instruction::Shl); 345202375Srdivacky Value *Shift = Builder->CreateLShr(X, ConstantInt::get(Ty, ShiftDiff)); 346202375Srdivacky 347202375Srdivacky APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 348202375Srdivacky return BinaryOperator::CreateAnd(Shift, 349202375Srdivacky ConstantInt::get(I.getContext(),Mask)); 350202375Srdivacky } 351202375Srdivacky 352202375Srdivacky // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in. 353202375Srdivacky } else { 354202375Srdivacky assert(ShiftAmt2 < ShiftAmt1); 355202375Srdivacky uint32_t ShiftDiff = ShiftAmt1-ShiftAmt2; 356202375Srdivacky 357202375Srdivacky // (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2) 358202375Srdivacky if (I.getOpcode() == Instruction::Shl) { 359202375Srdivacky assert(ShiftOp->getOpcode() == Instruction::LShr || 360202375Srdivacky ShiftOp->getOpcode() == Instruction::AShr); 361202375Srdivacky Value *Shift = Builder->CreateBinOp(ShiftOp->getOpcode(), X, 362202375Srdivacky ConstantInt::get(Ty, ShiftDiff)); 363202375Srdivacky 364202375Srdivacky APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2)); 365202375Srdivacky return BinaryOperator::CreateAnd(Shift, 366202375Srdivacky ConstantInt::get(I.getContext(),Mask)); 367202375Srdivacky } 368202375Srdivacky 369202375Srdivacky // (X << C1) >>u C2 --> X << (C1-C2) & (-1 >> C2) 370202375Srdivacky if (I.getOpcode() == Instruction::LShr) { 371202375Srdivacky assert(ShiftOp->getOpcode() == Instruction::Shl); 372202375Srdivacky Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff)); 373202375Srdivacky 374202375Srdivacky APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 375202375Srdivacky return BinaryOperator::CreateAnd(Shift, 376202375Srdivacky ConstantInt::get(I.getContext(),Mask)); 377202375Srdivacky } 378202375Srdivacky 379202375Srdivacky // We can't handle (X << C1) >>a C2, it shifts arbitrary bits in. 380202375Srdivacky } 381202375Srdivacky } 382202375Srdivacky return 0; 383202375Srdivacky} 384202375Srdivacky 385202375SrdivackyInstruction *InstCombiner::visitShl(BinaryOperator &I) { 386202375Srdivacky return commonShiftTransforms(I); 387202375Srdivacky} 388202375Srdivacky 389202375SrdivackyInstruction *InstCombiner::visitLShr(BinaryOperator &I) { 390203954Srdivacky if (Instruction *R = commonShiftTransforms(I)) 391203954Srdivacky return R; 392203954Srdivacky 393203954Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 394203954Srdivacky 395203954Srdivacky if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) 396203954Srdivacky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) { 397203954Srdivacky unsigned BitWidth = Op0->getType()->getScalarSizeInBits(); 398203954Srdivacky // ctlz.i32(x)>>5 --> zext(x == 0) 399203954Srdivacky // cttz.i32(x)>>5 --> zext(x == 0) 400203954Srdivacky // ctpop.i32(x)>>5 --> zext(x == -1) 401203954Srdivacky if ((II->getIntrinsicID() == Intrinsic::ctlz || 402203954Srdivacky II->getIntrinsicID() == Intrinsic::cttz || 403203954Srdivacky II->getIntrinsicID() == Intrinsic::ctpop) && 404203954Srdivacky isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == Op1C->getZExtValue()){ 405203954Srdivacky bool isCtPop = II->getIntrinsicID() == Intrinsic::ctpop; 406203954Srdivacky Constant *RHS = ConstantInt::getSigned(Op0->getType(), isCtPop ? -1:0); 407210299Sed Value *Cmp = Builder->CreateICmpEQ(II->getArgOperand(0), RHS); 408203954Srdivacky return new ZExtInst(Cmp, II->getType()); 409203954Srdivacky } 410203954Srdivacky } 411203954Srdivacky 412203954Srdivacky return 0; 413202375Srdivacky} 414202375Srdivacky 415202375SrdivackyInstruction *InstCombiner::visitAShr(BinaryOperator &I) { 416202375Srdivacky if (Instruction *R = commonShiftTransforms(I)) 417202375Srdivacky return R; 418202375Srdivacky 419202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 420202375Srdivacky 421202375Srdivacky if (ConstantInt *CSI = dyn_cast<ConstantInt>(Op0)) { 422202375Srdivacky // ashr int -1, X = -1 (for any arithmetic shift rights of ~0) 423202375Srdivacky if (CSI->isAllOnesValue()) 424202375Srdivacky return ReplaceInstUsesWith(I, CSI); 425202375Srdivacky } 426202375Srdivacky 427202375Srdivacky if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 428202375Srdivacky // If the input is a SHL by the same constant (ashr (shl X, C), C), then we 429202878Srdivacky // have a sign-extend idiom. 430202375Srdivacky Value *X; 431202878Srdivacky if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1)))) { 432202878Srdivacky // If the input value is known to already be sign extended enough, delete 433202878Srdivacky // the extension. 434202878Srdivacky if (ComputeNumSignBits(X) > Op1C->getZExtValue()) 435202878Srdivacky return ReplaceInstUsesWith(I, X); 436202878Srdivacky 437202878Srdivacky // If the input is an extension from the shifted amount value, e.g. 438202878Srdivacky // %x = zext i8 %A to i32 439202878Srdivacky // %y = shl i32 %x, 24 440202878Srdivacky // %z = ashr %y, 24 441202878Srdivacky // then turn this into "z = sext i8 A to i32". 442202878Srdivacky if (ZExtInst *ZI = dyn_cast<ZExtInst>(X)) { 443202878Srdivacky uint32_t SrcBits = ZI->getOperand(0)->getType()->getScalarSizeInBits(); 444202878Srdivacky uint32_t DestBits = ZI->getType()->getScalarSizeInBits(); 445202878Srdivacky if (Op1C->getZExtValue() == DestBits-SrcBits) 446202878Srdivacky return new SExtInst(ZI->getOperand(0), ZI->getType()); 447202878Srdivacky } 448202878Srdivacky } 449202375Srdivacky } 450202375Srdivacky 451202375Srdivacky // See if we can turn a signed shr into an unsigned shr. 452202375Srdivacky if (MaskedValueIsZero(Op0, 453202375Srdivacky APInt::getSignBit(I.getType()->getScalarSizeInBits()))) 454202375Srdivacky return BinaryOperator::CreateLShr(Op0, Op1); 455202375Srdivacky 456202375Srdivacky // Arithmetic shifting an all-sign-bit value is a no-op. 457202375Srdivacky unsigned NumSignBits = ComputeNumSignBits(Op0); 458202375Srdivacky if (NumSignBits == Op0->getType()->getScalarSizeInBits()) 459202375Srdivacky return ReplaceInstUsesWith(I, Op0); 460202375Srdivacky 461202375Srdivacky return 0; 462202375Srdivacky} 463202375Srdivacky 464