InstCombineShifts.cpp revision 212904
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 59212904Sdim/// CanEvaluateShifted - See if we can compute the specified value, but shifted 60212904Sdim/// logically to the left or right by some number of bits. This should return 61212904Sdim/// true if the expression can be computed for the same cost as the current 62212904Sdim/// expression tree. This is used to eliminate extraneous shifting from things 63212904Sdim/// like: 64212904Sdim/// %C = shl i128 %A, 64 65212904Sdim/// %D = shl i128 %B, 96 66212904Sdim/// %E = or i128 %C, %D 67212904Sdim/// %F = lshr i128 %E, 64 68212904Sdim/// where the client will ask if E can be computed shifted right by 64-bits. If 69212904Sdim/// this succeeds, the GetShiftedValue function will be called to produce the 70212904Sdim/// value. 71212904Sdimstatic bool CanEvaluateShifted(Value *V, unsigned NumBits, bool isLeftShift, 72212904Sdim InstCombiner &IC) { 73212904Sdim // We can always evaluate constants shifted. 74212904Sdim if (isa<Constant>(V)) 75212904Sdim return true; 76212904Sdim 77212904Sdim Instruction *I = dyn_cast<Instruction>(V); 78212904Sdim if (!I) return false; 79212904Sdim 80212904Sdim // If this is the opposite shift, we can directly reuse the input of the shift 81212904Sdim // if the needed bits are already zero in the input. This allows us to reuse 82212904Sdim // the value which means that we don't care if the shift has multiple uses. 83212904Sdim // TODO: Handle opposite shift by exact value. 84212904Sdim ConstantInt *CI; 85212904Sdim if ((isLeftShift && match(I, m_LShr(m_Value(), m_ConstantInt(CI)))) || 86212904Sdim (!isLeftShift && match(I, m_Shl(m_Value(), m_ConstantInt(CI))))) { 87212904Sdim if (CI->getZExtValue() == NumBits) { 88212904Sdim // TODO: Check that the input bits are already zero with MaskedValueIsZero 89212904Sdim#if 0 90212904Sdim // If this is a truncate of a logical shr, we can truncate it to a smaller 91212904Sdim // lshr iff we know that the bits we would otherwise be shifting in are 92212904Sdim // already zeros. 93212904Sdim uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); 94212904Sdim uint32_t BitWidth = Ty->getScalarSizeInBits(); 95212904Sdim if (MaskedValueIsZero(I->getOperand(0), 96212904Sdim APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) && 97212904Sdim CI->getLimitedValue(BitWidth) < BitWidth) { 98212904Sdim return CanEvaluateTruncated(I->getOperand(0), Ty); 99212904Sdim } 100212904Sdim#endif 101212904Sdim 102212904Sdim } 103212904Sdim } 104212904Sdim 105212904Sdim // We can't mutate something that has multiple uses: doing so would 106212904Sdim // require duplicating the instruction in general, which isn't profitable. 107212904Sdim if (!I->hasOneUse()) return false; 108212904Sdim 109212904Sdim switch (I->getOpcode()) { 110212904Sdim default: return false; 111212904Sdim case Instruction::And: 112212904Sdim case Instruction::Or: 113212904Sdim case Instruction::Xor: 114212904Sdim // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted. 115212904Sdim return CanEvaluateShifted(I->getOperand(0), NumBits, isLeftShift, IC) && 116212904Sdim CanEvaluateShifted(I->getOperand(1), NumBits, isLeftShift, IC); 117212904Sdim 118212904Sdim case Instruction::Shl: { 119212904Sdim // We can often fold the shift into shifts-by-a-constant. 120212904Sdim CI = dyn_cast<ConstantInt>(I->getOperand(1)); 121212904Sdim if (CI == 0) return false; 122212904Sdim 123212904Sdim // We can always fold shl(c1)+shl(c2) -> shl(c1+c2). 124212904Sdim if (isLeftShift) return true; 125212904Sdim 126212904Sdim // We can always turn shl(c)+shr(c) -> and(c2). 127212904Sdim if (CI->getValue() == NumBits) return true; 128212904Sdim 129212904Sdim unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 130212904Sdim 131212904Sdim // We can turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but it isn't 132212904Sdim // profitable unless we know the and'd out bits are already zero. 133212904Sdim if (CI->getZExtValue() > NumBits) { 134212904Sdim unsigned HighBits = CI->getZExtValue() - NumBits; 135212904Sdim if (MaskedValueIsZero(I->getOperand(0), 136212904Sdim APInt::getHighBitsSet(TypeWidth, HighBits))) 137212904Sdim return true; 138212904Sdim } 139212904Sdim 140212904Sdim return false; 141212904Sdim } 142212904Sdim case Instruction::LShr: { 143212904Sdim // We can often fold the shift into shifts-by-a-constant. 144212904Sdim CI = dyn_cast<ConstantInt>(I->getOperand(1)); 145212904Sdim if (CI == 0) return false; 146212904Sdim 147212904Sdim // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2). 148212904Sdim if (!isLeftShift) return true; 149212904Sdim 150212904Sdim // We can always turn lshr(c)+shl(c) -> and(c2). 151212904Sdim if (CI->getValue() == NumBits) return true; 152212904Sdim 153212904Sdim unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 154212904Sdim 155212904Sdim // We can always turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but it isn't 156212904Sdim // profitable unless we know the and'd out bits are already zero. 157212904Sdim if (CI->getZExtValue() > NumBits) { 158212904Sdim unsigned LowBits = CI->getZExtValue() - NumBits; 159212904Sdim if (MaskedValueIsZero(I->getOperand(0), 160212904Sdim APInt::getLowBitsSet(TypeWidth, LowBits))) 161212904Sdim return true; 162212904Sdim } 163212904Sdim 164212904Sdim return false; 165212904Sdim } 166212904Sdim case Instruction::Select: { 167212904Sdim SelectInst *SI = cast<SelectInst>(I); 168212904Sdim return CanEvaluateShifted(SI->getTrueValue(), NumBits, isLeftShift, IC) && 169212904Sdim CanEvaluateShifted(SI->getFalseValue(), NumBits, isLeftShift, IC); 170212904Sdim } 171212904Sdim case Instruction::PHI: { 172212904Sdim // We can change a phi if we can change all operands. Note that we never 173212904Sdim // get into trouble with cyclic PHIs here because we only consider 174212904Sdim // instructions with a single use. 175212904Sdim PHINode *PN = cast<PHINode>(I); 176212904Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 177212904Sdim if (!CanEvaluateShifted(PN->getIncomingValue(i), NumBits, isLeftShift,IC)) 178212904Sdim return false; 179212904Sdim return true; 180212904Sdim } 181212904Sdim } 182212904Sdim} 183212904Sdim 184212904Sdim/// GetShiftedValue - When CanEvaluateShifted returned true for an expression, 185212904Sdim/// this value inserts the new computation that produces the shifted value. 186212904Sdimstatic Value *GetShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, 187212904Sdim InstCombiner &IC) { 188212904Sdim // We can always evaluate constants shifted. 189212904Sdim if (Constant *C = dyn_cast<Constant>(V)) { 190212904Sdim if (isLeftShift) 191212904Sdim V = IC.Builder->CreateShl(C, NumBits); 192212904Sdim else 193212904Sdim V = IC.Builder->CreateLShr(C, NumBits); 194212904Sdim // If we got a constantexpr back, try to simplify it with TD info. 195212904Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 196212904Sdim V = ConstantFoldConstantExpression(CE, IC.getTargetData()); 197212904Sdim return V; 198212904Sdim } 199212904Sdim 200212904Sdim Instruction *I = cast<Instruction>(V); 201212904Sdim IC.Worklist.Add(I); 202212904Sdim 203212904Sdim switch (I->getOpcode()) { 204212904Sdim default: assert(0 && "Inconsistency with CanEvaluateShifted"); 205212904Sdim case Instruction::And: 206212904Sdim case Instruction::Or: 207212904Sdim case Instruction::Xor: 208212904Sdim // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted. 209212904Sdim I->setOperand(0, GetShiftedValue(I->getOperand(0), NumBits,isLeftShift,IC)); 210212904Sdim I->setOperand(1, GetShiftedValue(I->getOperand(1), NumBits,isLeftShift,IC)); 211212904Sdim return I; 212212904Sdim 213212904Sdim case Instruction::Shl: { 214212904Sdim unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 215212904Sdim 216212904Sdim // We only accept shifts-by-a-constant in CanEvaluateShifted. 217212904Sdim ConstantInt *CI = cast<ConstantInt>(I->getOperand(1)); 218212904Sdim 219212904Sdim // We can always fold shl(c1)+shl(c2) -> shl(c1+c2). 220212904Sdim if (isLeftShift) { 221212904Sdim // If this is oversized composite shift, then unsigned shifts get 0. 222212904Sdim unsigned NewShAmt = NumBits+CI->getZExtValue(); 223212904Sdim if (NewShAmt >= TypeWidth) 224212904Sdim return Constant::getNullValue(I->getType()); 225212904Sdim 226212904Sdim I->setOperand(1, ConstantInt::get(I->getType(), NewShAmt)); 227212904Sdim return I; 228212904Sdim } 229212904Sdim 230212904Sdim // We turn shl(c)+lshr(c) -> and(c2) if the input doesn't already have 231212904Sdim // zeros. 232212904Sdim if (CI->getValue() == NumBits) { 233212904Sdim APInt Mask(APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits)); 234212904Sdim V = IC.Builder->CreateAnd(I->getOperand(0), 235212904Sdim ConstantInt::get(I->getContext(), Mask)); 236212904Sdim if (Instruction *VI = dyn_cast<Instruction>(V)) { 237212904Sdim VI->moveBefore(I); 238212904Sdim VI->takeName(I); 239212904Sdim } 240212904Sdim return V; 241212904Sdim } 242212904Sdim 243212904Sdim // We turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but only when we know that 244212904Sdim // the and won't be needed. 245212904Sdim assert(CI->getZExtValue() > NumBits); 246212904Sdim I->setOperand(1, ConstantInt::get(I->getType(), 247212904Sdim CI->getZExtValue() - NumBits)); 248212904Sdim return I; 249212904Sdim } 250212904Sdim case Instruction::LShr: { 251212904Sdim unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 252212904Sdim // We only accept shifts-by-a-constant in CanEvaluateShifted. 253212904Sdim ConstantInt *CI = cast<ConstantInt>(I->getOperand(1)); 254212904Sdim 255212904Sdim // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2). 256212904Sdim if (!isLeftShift) { 257212904Sdim // If this is oversized composite shift, then unsigned shifts get 0. 258212904Sdim unsigned NewShAmt = NumBits+CI->getZExtValue(); 259212904Sdim if (NewShAmt >= TypeWidth) 260212904Sdim return Constant::getNullValue(I->getType()); 261212904Sdim 262212904Sdim I->setOperand(1, ConstantInt::get(I->getType(), NewShAmt)); 263212904Sdim return I; 264212904Sdim } 265212904Sdim 266212904Sdim // We turn lshr(c)+shl(c) -> and(c2) if the input doesn't already have 267212904Sdim // zeros. 268212904Sdim if (CI->getValue() == NumBits) { 269212904Sdim APInt Mask(APInt::getHighBitsSet(TypeWidth, TypeWidth - NumBits)); 270212904Sdim V = IC.Builder->CreateAnd(I->getOperand(0), 271212904Sdim ConstantInt::get(I->getContext(), Mask)); 272212904Sdim if (Instruction *VI = dyn_cast<Instruction>(V)) { 273212904Sdim VI->moveBefore(I); 274212904Sdim VI->takeName(I); 275212904Sdim } 276212904Sdim return V; 277212904Sdim } 278212904Sdim 279212904Sdim // We turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but only when we know that 280212904Sdim // the and won't be needed. 281212904Sdim assert(CI->getZExtValue() > NumBits); 282212904Sdim I->setOperand(1, ConstantInt::get(I->getType(), 283212904Sdim CI->getZExtValue() - NumBits)); 284212904Sdim return I; 285212904Sdim } 286212904Sdim 287212904Sdim case Instruction::Select: 288212904Sdim I->setOperand(1, GetShiftedValue(I->getOperand(1), NumBits,isLeftShift,IC)); 289212904Sdim I->setOperand(2, GetShiftedValue(I->getOperand(2), NumBits,isLeftShift,IC)); 290212904Sdim return I; 291212904Sdim case Instruction::PHI: { 292212904Sdim // We can change a phi if we can change all operands. Note that we never 293212904Sdim // get into trouble with cyclic PHIs here because we only consider 294212904Sdim // instructions with a single use. 295212904Sdim PHINode *PN = cast<PHINode>(I); 296212904Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 297212904Sdim PN->setIncomingValue(i, GetShiftedValue(PN->getIncomingValue(i), 298212904Sdim NumBits, isLeftShift, IC)); 299212904Sdim return PN; 300212904Sdim } 301212904Sdim } 302212904Sdim} 303212904Sdim 304212904Sdim 305212904Sdim 306202375SrdivackyInstruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1, 307202375Srdivacky BinaryOperator &I) { 308202375Srdivacky bool isLeftShift = I.getOpcode() == Instruction::Shl; 309212904Sdim 310212904Sdim 311212904Sdim // See if we can propagate this shift into the input, this covers the trivial 312212904Sdim // cast of lshr(shl(x,c1),c2) as well as other more complex cases. 313212904Sdim if (I.getOpcode() != Instruction::AShr && 314212904Sdim CanEvaluateShifted(Op0, Op1->getZExtValue(), isLeftShift, *this)) { 315212904Sdim DEBUG(dbgs() << "ICE: GetShiftedValue propagating shift through expression" 316212904Sdim " to eliminate shift:\n IN: " << *Op0 << "\n SH: " << I <<"\n"); 317212904Sdim 318212904Sdim return ReplaceInstUsesWith(I, 319212904Sdim GetShiftedValue(Op0, Op1->getZExtValue(), isLeftShift, *this)); 320212904Sdim } 321212904Sdim 322212904Sdim 323202375Srdivacky // See if we can simplify any instructions used by the instruction whose sole 324202375Srdivacky // purpose is to compute bits we don't care about. 325202375Srdivacky uint32_t TypeBits = Op0->getType()->getScalarSizeInBits(); 326202375Srdivacky 327202375Srdivacky // shl i32 X, 32 = 0 and srl i8 Y, 9 = 0, ... just don't eliminate 328202375Srdivacky // a signed shift. 329202375Srdivacky // 330202375Srdivacky if (Op1->uge(TypeBits)) { 331202375Srdivacky if (I.getOpcode() != Instruction::AShr) 332202375Srdivacky return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType())); 333203954Srdivacky // ashr i32 X, 32 --> ashr i32 X, 31 334203954Srdivacky I.setOperand(1, ConstantInt::get(I.getType(), TypeBits-1)); 335203954Srdivacky return &I; 336202375Srdivacky } 337202375Srdivacky 338202375Srdivacky // ((X*C1) << C2) == (X * (C1 << C2)) 339202375Srdivacky if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) 340202375Srdivacky if (BO->getOpcode() == Instruction::Mul && isLeftShift) 341202375Srdivacky if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1))) 342202375Srdivacky return BinaryOperator::CreateMul(BO->getOperand(0), 343202375Srdivacky ConstantExpr::getShl(BOOp, Op1)); 344202375Srdivacky 345202375Srdivacky // Try to fold constant and into select arguments. 346202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 347202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 348202375Srdivacky return R; 349202375Srdivacky if (isa<PHINode>(Op0)) 350202375Srdivacky if (Instruction *NV = FoldOpIntoPhi(I)) 351202375Srdivacky return NV; 352202375Srdivacky 353202375Srdivacky // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2)) 354202375Srdivacky if (TruncInst *TI = dyn_cast<TruncInst>(Op0)) { 355202375Srdivacky Instruction *TrOp = dyn_cast<Instruction>(TI->getOperand(0)); 356202375Srdivacky // If 'shift2' is an ashr, we would have to get the sign bit into a funny 357202375Srdivacky // place. Don't try to do this transformation in this case. Also, we 358202375Srdivacky // require that the input operand is a shift-by-constant so that we have 359202375Srdivacky // confidence that the shifts will get folded together. We could do this 360202375Srdivacky // xform in more cases, but it is unlikely to be profitable. 361202375Srdivacky if (TrOp && I.isLogicalShift() && TrOp->isShift() && 362202375Srdivacky isa<ConstantInt>(TrOp->getOperand(1))) { 363202375Srdivacky // Okay, we'll do this xform. Make the shift of shift. 364202375Srdivacky Constant *ShAmt = ConstantExpr::getZExt(Op1, TrOp->getType()); 365202375Srdivacky // (shift2 (shift1 & 0x00FF), c2) 366202375Srdivacky Value *NSh = Builder->CreateBinOp(I.getOpcode(), TrOp, ShAmt,I.getName()); 367202375Srdivacky 368202375Srdivacky // For logical shifts, the truncation has the effect of making the high 369202375Srdivacky // part of the register be zeros. Emulate this by inserting an AND to 370202375Srdivacky // clear the top bits as needed. This 'and' will usually be zapped by 371202375Srdivacky // other xforms later if dead. 372202375Srdivacky unsigned SrcSize = TrOp->getType()->getScalarSizeInBits(); 373202375Srdivacky unsigned DstSize = TI->getType()->getScalarSizeInBits(); 374202375Srdivacky APInt MaskV(APInt::getLowBitsSet(SrcSize, DstSize)); 375202375Srdivacky 376202375Srdivacky // The mask we constructed says what the trunc would do if occurring 377202375Srdivacky // between the shifts. We want to know the effect *after* the second 378202375Srdivacky // shift. We know that it is a logical shift by a constant, so adjust the 379202375Srdivacky // mask as appropriate. 380202375Srdivacky if (I.getOpcode() == Instruction::Shl) 381202375Srdivacky MaskV <<= Op1->getZExtValue(); 382202375Srdivacky else { 383202375Srdivacky assert(I.getOpcode() == Instruction::LShr && "Unknown logical shift"); 384202375Srdivacky MaskV = MaskV.lshr(Op1->getZExtValue()); 385202375Srdivacky } 386202375Srdivacky 387202375Srdivacky // shift1 & 0x00FF 388202375Srdivacky Value *And = Builder->CreateAnd(NSh, 389202375Srdivacky ConstantInt::get(I.getContext(), MaskV), 390202375Srdivacky TI->getName()); 391202375Srdivacky 392202375Srdivacky // Return the value truncated to the interesting size. 393202375Srdivacky return new TruncInst(And, I.getType()); 394202375Srdivacky } 395202375Srdivacky } 396202375Srdivacky 397202375Srdivacky if (Op0->hasOneUse()) { 398202375Srdivacky if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) { 399202375Srdivacky // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 400202375Srdivacky Value *V1, *V2; 401202375Srdivacky ConstantInt *CC; 402202375Srdivacky switch (Op0BO->getOpcode()) { 403202375Srdivacky default: break; 404202375Srdivacky case Instruction::Add: 405202375Srdivacky case Instruction::And: 406202375Srdivacky case Instruction::Or: 407202375Srdivacky case Instruction::Xor: { 408202375Srdivacky // These operators commute. 409202375Srdivacky // Turn (Y + (X >> C)) << C -> (X + (Y << C)) & (~0 << C) 410202375Srdivacky if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() && 411202375Srdivacky match(Op0BO->getOperand(1), m_Shr(m_Value(V1), 412202375Srdivacky m_Specific(Op1)))) { 413202375Srdivacky Value *YS = // (Y << C) 414202375Srdivacky Builder->CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName()); 415202375Srdivacky // (X + (Y << C)) 416202375Srdivacky Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), YS, V1, 417202375Srdivacky Op0BO->getOperand(1)->getName()); 418202375Srdivacky uint32_t Op1Val = Op1->getLimitedValue(TypeBits); 419202375Srdivacky return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(), 420202375Srdivacky APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val))); 421202375Srdivacky } 422202375Srdivacky 423202375Srdivacky // Turn (Y + ((X >> C) & CC)) << C -> ((X & (CC << C)) + (Y << C)) 424202375Srdivacky Value *Op0BOOp1 = Op0BO->getOperand(1); 425202375Srdivacky if (isLeftShift && Op0BOOp1->hasOneUse() && 426202375Srdivacky match(Op0BOOp1, 427202375Srdivacky m_And(m_Shr(m_Value(V1), m_Specific(Op1)), 428202375Srdivacky m_ConstantInt(CC))) && 429202375Srdivacky cast<BinaryOperator>(Op0BOOp1)->getOperand(0)->hasOneUse()) { 430202375Srdivacky Value *YS = // (Y << C) 431202375Srdivacky Builder->CreateShl(Op0BO->getOperand(0), Op1, 432202375Srdivacky Op0BO->getName()); 433202375Srdivacky // X & (CC << C) 434202375Srdivacky Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1), 435202375Srdivacky V1->getName()+".mask"); 436202375Srdivacky return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM); 437202375Srdivacky } 438202375Srdivacky } 439202375Srdivacky 440202375Srdivacky // FALL THROUGH. 441202375Srdivacky case Instruction::Sub: { 442202375Srdivacky // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 443202375Srdivacky if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 444202375Srdivacky match(Op0BO->getOperand(0), m_Shr(m_Value(V1), 445202375Srdivacky m_Specific(Op1)))) { 446202375Srdivacky Value *YS = // (Y << C) 447202375Srdivacky Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 448202375Srdivacky // (X + (Y << C)) 449202375Srdivacky Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), V1, YS, 450202375Srdivacky Op0BO->getOperand(0)->getName()); 451202375Srdivacky uint32_t Op1Val = Op1->getLimitedValue(TypeBits); 452202375Srdivacky return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(), 453202375Srdivacky APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val))); 454202375Srdivacky } 455202375Srdivacky 456202375Srdivacky // Turn (((X >> C)&CC) + Y) << C -> (X + (Y << C)) & (CC << C) 457202375Srdivacky if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 458202375Srdivacky match(Op0BO->getOperand(0), 459202375Srdivacky m_And(m_Shr(m_Value(V1), m_Value(V2)), 460202375Srdivacky m_ConstantInt(CC))) && V2 == Op1 && 461202375Srdivacky cast<BinaryOperator>(Op0BO->getOperand(0)) 462202375Srdivacky ->getOperand(0)->hasOneUse()) { 463202375Srdivacky Value *YS = // (Y << C) 464202375Srdivacky Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 465202375Srdivacky // X & (CC << C) 466202375Srdivacky Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1), 467202375Srdivacky V1->getName()+".mask"); 468202375Srdivacky 469202375Srdivacky return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS); 470202375Srdivacky } 471202375Srdivacky 472202375Srdivacky break; 473202375Srdivacky } 474202375Srdivacky } 475202375Srdivacky 476202375Srdivacky 477202375Srdivacky // If the operand is an bitwise operator with a constant RHS, and the 478202375Srdivacky // shift is the only use, we can pull it out of the shift. 479202375Srdivacky if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) { 480202375Srdivacky bool isValid = true; // Valid only for And, Or, Xor 481202375Srdivacky bool highBitSet = false; // Transform if high bit of constant set? 482202375Srdivacky 483202375Srdivacky switch (Op0BO->getOpcode()) { 484202375Srdivacky default: isValid = false; break; // Do not perform transform! 485202375Srdivacky case Instruction::Add: 486202375Srdivacky isValid = isLeftShift; 487202375Srdivacky break; 488202375Srdivacky case Instruction::Or: 489202375Srdivacky case Instruction::Xor: 490202375Srdivacky highBitSet = false; 491202375Srdivacky break; 492202375Srdivacky case Instruction::And: 493202375Srdivacky highBitSet = true; 494202375Srdivacky break; 495202375Srdivacky } 496202375Srdivacky 497202375Srdivacky // If this is a signed shift right, and the high bit is modified 498202375Srdivacky // by the logical operation, do not perform the transformation. 499202375Srdivacky // The highBitSet boolean indicates the value of the high bit of 500202375Srdivacky // the constant which would cause it to be modified for this 501202375Srdivacky // operation. 502202375Srdivacky // 503202375Srdivacky if (isValid && I.getOpcode() == Instruction::AShr) 504202375Srdivacky isValid = Op0C->getValue()[TypeBits-1] == highBitSet; 505202375Srdivacky 506202375Srdivacky if (isValid) { 507202375Srdivacky Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, Op1); 508202375Srdivacky 509202375Srdivacky Value *NewShift = 510202375Srdivacky Builder->CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1); 511202375Srdivacky NewShift->takeName(Op0BO); 512202375Srdivacky 513202375Srdivacky return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, 514202375Srdivacky NewRHS); 515202375Srdivacky } 516202375Srdivacky } 517202375Srdivacky } 518202375Srdivacky } 519202375Srdivacky 520202375Srdivacky // Find out if this is a shift of a shift by a constant. 521202375Srdivacky BinaryOperator *ShiftOp = dyn_cast<BinaryOperator>(Op0); 522202375Srdivacky if (ShiftOp && !ShiftOp->isShift()) 523202375Srdivacky ShiftOp = 0; 524202375Srdivacky 525202375Srdivacky if (ShiftOp && isa<ConstantInt>(ShiftOp->getOperand(1))) { 526202375Srdivacky ConstantInt *ShiftAmt1C = cast<ConstantInt>(ShiftOp->getOperand(1)); 527202375Srdivacky uint32_t ShiftAmt1 = ShiftAmt1C->getLimitedValue(TypeBits); 528202375Srdivacky uint32_t ShiftAmt2 = Op1->getLimitedValue(TypeBits); 529202375Srdivacky assert(ShiftAmt2 != 0 && "Should have been simplified earlier"); 530202375Srdivacky if (ShiftAmt1 == 0) return 0; // Will be simplified in the future. 531202375Srdivacky Value *X = ShiftOp->getOperand(0); 532202375Srdivacky 533202375Srdivacky uint32_t AmtSum = ShiftAmt1+ShiftAmt2; // Fold into one big shift. 534202375Srdivacky 535202375Srdivacky const IntegerType *Ty = cast<IntegerType>(I.getType()); 536202375Srdivacky 537202375Srdivacky // Check for (X << c1) << c2 and (X >> c1) >> c2 538202375Srdivacky if (I.getOpcode() == ShiftOp->getOpcode()) { 539202375Srdivacky // If this is oversized composite shift, then unsigned shifts get 0, ashr 540202375Srdivacky // saturates. 541202375Srdivacky if (AmtSum >= TypeBits) { 542202375Srdivacky if (I.getOpcode() != Instruction::AShr) 543202375Srdivacky return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 544202375Srdivacky AmtSum = TypeBits-1; // Saturate to 31 for i32 ashr. 545202375Srdivacky } 546202375Srdivacky 547202375Srdivacky return BinaryOperator::Create(I.getOpcode(), X, 548202375Srdivacky ConstantInt::get(Ty, AmtSum)); 549202375Srdivacky } 550202375Srdivacky 551202375Srdivacky if (ShiftAmt1 == ShiftAmt2) { 552202375Srdivacky // If we have ((X >>? C) << C), turn this into X & (-1 << C). 553212904Sdim if (I.getOpcode() == Instruction::Shl && 554212904Sdim ShiftOp->getOpcode() != Instruction::Shl) { 555202375Srdivacky APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt1)); 556202375Srdivacky return BinaryOperator::CreateAnd(X, 557202375Srdivacky ConstantInt::get(I.getContext(),Mask)); 558202375Srdivacky } 559202375Srdivacky // If we have ((X << C) >>u C), turn this into X & (-1 >>u C). 560212904Sdim if (I.getOpcode() == Instruction::LShr && 561212904Sdim ShiftOp->getOpcode() == Instruction::Shl) { 562202375Srdivacky APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt1)); 563202375Srdivacky return BinaryOperator::CreateAnd(X, 564202375Srdivacky ConstantInt::get(I.getContext(), Mask)); 565202375Srdivacky } 566202375Srdivacky } else if (ShiftAmt1 < ShiftAmt2) { 567202375Srdivacky uint32_t ShiftDiff = ShiftAmt2-ShiftAmt1; 568202375Srdivacky 569202375Srdivacky // (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2) 570212904Sdim if (I.getOpcode() == Instruction::Shl && 571212904Sdim ShiftOp->getOpcode() != Instruction::Shl) { 572202375Srdivacky assert(ShiftOp->getOpcode() == Instruction::LShr || 573202375Srdivacky ShiftOp->getOpcode() == Instruction::AShr); 574202375Srdivacky Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff)); 575202375Srdivacky 576202375Srdivacky APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2)); 577202375Srdivacky return BinaryOperator::CreateAnd(Shift, 578202375Srdivacky ConstantInt::get(I.getContext(),Mask)); 579202375Srdivacky } 580202375Srdivacky 581202375Srdivacky // (X << C1) >>u C2 --> X >>u (C2-C1) & (-1 >> C2) 582212904Sdim if (I.getOpcode() == Instruction::LShr && 583212904Sdim ShiftOp->getOpcode() == Instruction::Shl) { 584202375Srdivacky assert(ShiftOp->getOpcode() == Instruction::Shl); 585202375Srdivacky Value *Shift = Builder->CreateLShr(X, ConstantInt::get(Ty, ShiftDiff)); 586202375Srdivacky 587202375Srdivacky APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 588202375Srdivacky return BinaryOperator::CreateAnd(Shift, 589202375Srdivacky ConstantInt::get(I.getContext(),Mask)); 590202375Srdivacky } 591202375Srdivacky 592202375Srdivacky // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in. 593202375Srdivacky } else { 594202375Srdivacky assert(ShiftAmt2 < ShiftAmt1); 595202375Srdivacky uint32_t ShiftDiff = ShiftAmt1-ShiftAmt2; 596202375Srdivacky 597202375Srdivacky // (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2) 598212904Sdim if (I.getOpcode() == Instruction::Shl && 599212904Sdim ShiftOp->getOpcode() != Instruction::Shl) { 600202375Srdivacky Value *Shift = Builder->CreateBinOp(ShiftOp->getOpcode(), X, 601202375Srdivacky ConstantInt::get(Ty, ShiftDiff)); 602202375Srdivacky 603202375Srdivacky APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2)); 604202375Srdivacky return BinaryOperator::CreateAnd(Shift, 605202375Srdivacky ConstantInt::get(I.getContext(),Mask)); 606202375Srdivacky } 607202375Srdivacky 608202375Srdivacky // (X << C1) >>u C2 --> X << (C1-C2) & (-1 >> C2) 609212904Sdim if (I.getOpcode() == Instruction::LShr && 610212904Sdim ShiftOp->getOpcode() == Instruction::Shl) { 611202375Srdivacky Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff)); 612202375Srdivacky 613202375Srdivacky APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 614202375Srdivacky return BinaryOperator::CreateAnd(Shift, 615202375Srdivacky ConstantInt::get(I.getContext(),Mask)); 616202375Srdivacky } 617202375Srdivacky 618202375Srdivacky // We can't handle (X << C1) >>a C2, it shifts arbitrary bits in. 619202375Srdivacky } 620202375Srdivacky } 621202375Srdivacky return 0; 622202375Srdivacky} 623202375Srdivacky 624202375SrdivackyInstruction *InstCombiner::visitShl(BinaryOperator &I) { 625202375Srdivacky return commonShiftTransforms(I); 626202375Srdivacky} 627202375Srdivacky 628202375SrdivackyInstruction *InstCombiner::visitLShr(BinaryOperator &I) { 629203954Srdivacky if (Instruction *R = commonShiftTransforms(I)) 630203954Srdivacky return R; 631203954Srdivacky 632203954Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 633203954Srdivacky 634203954Srdivacky if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) 635203954Srdivacky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) { 636203954Srdivacky unsigned BitWidth = Op0->getType()->getScalarSizeInBits(); 637203954Srdivacky // ctlz.i32(x)>>5 --> zext(x == 0) 638203954Srdivacky // cttz.i32(x)>>5 --> zext(x == 0) 639203954Srdivacky // ctpop.i32(x)>>5 --> zext(x == -1) 640203954Srdivacky if ((II->getIntrinsicID() == Intrinsic::ctlz || 641203954Srdivacky II->getIntrinsicID() == Intrinsic::cttz || 642203954Srdivacky II->getIntrinsicID() == Intrinsic::ctpop) && 643203954Srdivacky isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == Op1C->getZExtValue()){ 644203954Srdivacky bool isCtPop = II->getIntrinsicID() == Intrinsic::ctpop; 645203954Srdivacky Constant *RHS = ConstantInt::getSigned(Op0->getType(), isCtPop ? -1:0); 646210299Sed Value *Cmp = Builder->CreateICmpEQ(II->getArgOperand(0), RHS); 647203954Srdivacky return new ZExtInst(Cmp, II->getType()); 648203954Srdivacky } 649203954Srdivacky } 650203954Srdivacky 651203954Srdivacky return 0; 652202375Srdivacky} 653202375Srdivacky 654202375SrdivackyInstruction *InstCombiner::visitAShr(BinaryOperator &I) { 655202375Srdivacky if (Instruction *R = commonShiftTransforms(I)) 656202375Srdivacky return R; 657202375Srdivacky 658202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 659202375Srdivacky 660202375Srdivacky if (ConstantInt *CSI = dyn_cast<ConstantInt>(Op0)) { 661202375Srdivacky // ashr int -1, X = -1 (for any arithmetic shift rights of ~0) 662202375Srdivacky if (CSI->isAllOnesValue()) 663202375Srdivacky return ReplaceInstUsesWith(I, CSI); 664202375Srdivacky } 665202375Srdivacky 666202375Srdivacky if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 667202375Srdivacky // If the input is a SHL by the same constant (ashr (shl X, C), C), then we 668202878Srdivacky // have a sign-extend idiom. 669202375Srdivacky Value *X; 670202878Srdivacky if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1)))) { 671202878Srdivacky // If the input value is known to already be sign extended enough, delete 672202878Srdivacky // the extension. 673202878Srdivacky if (ComputeNumSignBits(X) > Op1C->getZExtValue()) 674202878Srdivacky return ReplaceInstUsesWith(I, X); 675202878Srdivacky 676202878Srdivacky // If the input is an extension from the shifted amount value, e.g. 677202878Srdivacky // %x = zext i8 %A to i32 678202878Srdivacky // %y = shl i32 %x, 24 679202878Srdivacky // %z = ashr %y, 24 680202878Srdivacky // then turn this into "z = sext i8 A to i32". 681202878Srdivacky if (ZExtInst *ZI = dyn_cast<ZExtInst>(X)) { 682202878Srdivacky uint32_t SrcBits = ZI->getOperand(0)->getType()->getScalarSizeInBits(); 683202878Srdivacky uint32_t DestBits = ZI->getType()->getScalarSizeInBits(); 684202878Srdivacky if (Op1C->getZExtValue() == DestBits-SrcBits) 685202878Srdivacky return new SExtInst(ZI->getOperand(0), ZI->getType()); 686202878Srdivacky } 687202878Srdivacky } 688202375Srdivacky } 689202375Srdivacky 690202375Srdivacky // See if we can turn a signed shr into an unsigned shr. 691202375Srdivacky if (MaskedValueIsZero(Op0, 692202375Srdivacky APInt::getSignBit(I.getType()->getScalarSizeInBits()))) 693202375Srdivacky return BinaryOperator::CreateLShr(Op0, Op1); 694202375Srdivacky 695202375Srdivacky // Arithmetic shifting an all-sign-bit value is a no-op. 696202375Srdivacky unsigned NumSignBits = ComputeNumSignBits(Op0); 697202375Srdivacky if (NumSignBits == Op0->getType()->getScalarSizeInBits()) 698202375Srdivacky return ReplaceInstUsesWith(I, Op0); 699202375Srdivacky 700202375Srdivacky return 0; 701202375Srdivacky} 702202375Srdivacky 703