InstCombineShifts.cpp revision 212904
151078Speter//===- InstCombineShifts.cpp ----------------------------------------------===// 251078Speter// 351078Speter// The LLVM Compiler Infrastructure 451078Speter// 551078Speter// This file is distributed under the University of Illinois Open Source 651078Speter// License. See LICENSE.TXT for details. 751078Speter// 851078Speter//===----------------------------------------------------------------------===// 951078Speter// 1051078Speter// This file implements the visitShl, visitLShr, and visitAShr functions. 1151078Speter// 1251078Speter//===----------------------------------------------------------------------===// 1351078Speter 1451078Speter#include "InstCombine.h" 1551078Speter#include "llvm/IntrinsicInst.h" 1651078Speter#include "llvm/Support/PatternMatch.h" 1751078Speterusing namespace llvm; 1851078Speterusing namespace PatternMatch; 1951078Speter 2051078SpeterInstruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) { 2151078Speter assert(I.getOperand(1)->getType() == I.getOperand(0)->getType()); 2251078Speter Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 2351078Speter 2451078Speter // shl X, 0 == X and shr X, 0 == X 2551078Speter // shl 0, X == 0 and shr 0, X == 0 2651078Speter if (Op1 == Constant::getNullValue(Op1->getType()) || 2751078Speter Op0 == Constant::getNullValue(Op0->getType())) 2851078Speter return ReplaceInstUsesWith(I, Op0); 2951078Speter 3051078Speter if (isa<UndefValue>(Op0)) { 3151078Speter if (I.getOpcode() == Instruction::AShr) // undef >>s X -> undef 3251078Speter return ReplaceInstUsesWith(I, Op0); 33119419Sobrien else // undef << X -> 0, undef >>u X -> 0 34119419Sobrien return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 35119419Sobrien } 3651078Speter if (isa<UndefValue>(Op1)) { 37131939Smarcel if (I.getOpcode() == Instruction::AShr) // X >>s undef -> X 38131939Smarcel return ReplaceInstUsesWith(I, Op0); 3951078Speter else // X << undef, X >>u undef -> 0 4051078Speter return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 4151078Speter } 4251078Speter 4351078Speter // See if we can fold away this shift. 4451078Speter if (SimplifyDemandedInstructionBits(I)) 4551078Speter return &I; 4651078Speter 47150460Simp // Try to fold constant and into select arguments. 48150460Simp if (isa<Constant>(Op0)) 4951078Speter if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 5051078Speter if (Instruction *R = FoldOpIntoSelect(I, SI)) 5176166Smarkm return R; 5265822Sjhb 5351078Speter if (ConstantInt *CUI = dyn_cast<ConstantInt>(Op1)) 5451078Speter if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I)) 5551078Speter return Res; 56131939Smarcel return 0; 5751078Speter} 58114216Skan 5976166Smarkm/// CanEvaluateShifted - See if we can compute the specified value, but shifted 6076166Smarkm/// logically to the left or right by some number of bits. This should return 6176166Smarkm/// true if the expression can be computed for the same cost as the current 6276166Smarkm/// expression tree. This is used to eliminate extraneous shifting from things 6376166Smarkm/// like: 6476166Smarkm/// %C = shl i128 %A, 64 65131094Sphk/// %D = shl i128 %B, 96 6676166Smarkm/// %E = or i128 %C, %D 6751078Speter/// %F = lshr i128 %E, 64 6876166Smarkm/// where the client will ask if E can be computed shifted right by 64-bits. If 6951078Speter/// this succeeds, the GetShiftedValue function will be called to produce the 7051078Speter/// value. 7151078Speterstatic bool CanEvaluateShifted(Value *V, unsigned NumBits, bool isLeftShift, 7293466Sbde InstCombiner &IC) { 73119485Snjl // We can always evaluate constants shifted. 7451078Speter if (isa<Constant>(V)) 7586909Simp return true; 7686909Simp 7751078Speter Instruction *I = dyn_cast<Instruction>(V); 7851078Speter if (!I) return false; 7985302Simp 8085365Simp // If this is the opposite shift, we can directly reuse the input of the shift 8151078Speter // if the needed bits are already zero in the input. This allows us to reuse 8251078Speter // the value which means that we don't care if the shift has multiple uses. 8377726Sjoerg // TODO: Handle opposite shift by exact value. 8451078Speter ConstantInt *CI; 8577726Sjoerg if ((isLeftShift && match(I, m_LShr(m_Value(), m_ConstantInt(CI)))) || 8651078Speter (!isLeftShift && match(I, m_Shl(m_Value(), m_ConstantInt(CI))))) { 8751078Speter if (CI->getZExtValue() == NumBits) { 8851078Speter // TODO: Check that the input bits are already zero with MaskedValueIsZero 8951078Speter#if 0 9051078Speter // If this is a truncate of a logical shr, we can truncate it to a smaller 9151078Speter // lshr iff we know that the bits we would otherwise be shifting in are 9251078Speter // already zeros. 9351078Speter uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); 9451078Speter uint32_t BitWidth = Ty->getScalarSizeInBits(); 9551078Speter if (MaskedValueIsZero(I->getOperand(0), 96104067Sphk APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) && 97104067Sphk CI->getLimitedValue(BitWidth) < BitWidth) { 9851078Speter return CanEvaluateTruncated(I->getOperand(0), Ty); 9951078Speter } 100120175Sbde#endif 10151078Speter 102120175Sbde } 103120175Sbde } 10451078Speter 105120175Sbde // We can't mutate something that has multiple uses: doing so would 10651078Speter // require duplicating the instruction in general, which isn't profitable. 10751078Speter if (!I->hasOneUse()) return false; 108120175Sbde 109120175Sbde switch (I->getOpcode()) { 110120175Sbde default: return false; 111111613Sphk case Instruction::And: 112120175Sbde case Instruction::Or: 113112384Ssobomax case Instruction::Xor: 11451078Speter // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted. 11560471Snyan return CanEvaluateShifted(I->getOperand(0), NumBits, isLeftShift, IC) && 11660471Snyan CanEvaluateShifted(I->getOperand(1), NumBits, isLeftShift, IC); 11760471Snyan 11860471Snyan case Instruction::Shl: { 11960471Snyan // We can often fold the shift into shifts-by-a-constant. 12051078Speter CI = dyn_cast<ConstantInt>(I->getOperand(1)); 12151078Speter if (CI == 0) return false; 12251078Speter 12351078Speter // We can always fold shl(c1)+shl(c2) -> shl(c1+c2). 12451078Speter if (isLeftShift) return true; 12551078Speter 12651078Speter // We can always turn shl(c)+shr(c) -> and(c2). 12751078Speter if (CI->getValue() == NumBits) return true; 12853344Speter 12951078Speter unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 13051078Speter 13151078Speter // We can turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but it isn't 13251078Speter // profitable unless we know the and'd out bits are already zero. 13351078Speter if (CI->getZExtValue() > NumBits) { 13451078Speter unsigned HighBits = CI->getZExtValue() - NumBits; 13551078Speter if (MaskedValueIsZero(I->getOperand(0), 13651078Speter APInt::getHighBitsSet(TypeWidth, HighBits))) 13751078Speter return true; 13851078Speter } 13951078Speter 14051078Speter return false; 14151078Speter } 14251078Speter case Instruction::LShr: { 14351078Speter // We can often fold the shift into shifts-by-a-constant. 14451078Speter CI = dyn_cast<ConstantInt>(I->getOperand(1)); 14551078Speter if (CI == 0) return false; 14651078Speter 14751078Speter // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2). 14851078Speter if (!isLeftShift) return true; 14951078Speter 15051078Speter // We can always turn lshr(c)+shl(c) -> and(c2). 15151078Speter if (CI->getValue() == NumBits) return true; 15251078Speter 15351078Speter unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 15486909Simp 15551078Speter // We can always turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but it isn't 15651078Speter // profitable unless we know the and'd out bits are already zero. 15786909Simp if (CI->getZExtValue() > NumBits) { 15886909Simp unsigned LowBits = CI->getZExtValue() - NumBits; 15986909Simp if (MaskedValueIsZero(I->getOperand(0), 16086909Simp APInt::getLowBitsSet(TypeWidth, LowBits))) 16186909Simp return true; 16286909Simp } 16386909Simp 16486909Simp return false; 16586909Simp } 16686909Simp case Instruction::Select: { 16786909Simp SelectInst *SI = cast<SelectInst>(I); 16886909Simp return CanEvaluateShifted(SI->getTrueValue(), NumBits, isLeftShift, IC) && 16986909Simp CanEvaluateShifted(SI->getFalseValue(), NumBits, isLeftShift, IC); 17086909Simp } 17186909Simp case Instruction::PHI: { 17286909Simp // We can change a phi if we can change all operands. Note that we never 17351078Speter // get into trouble with cyclic PHIs here because we only consider 17486909Simp // instructions with a single use. 17586909Simp PHINode *PN = cast<PHINode>(I); 17686909Simp for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 17786909Simp if (!CanEvaluateShifted(PN->getIncomingValue(i), NumBits, isLeftShift,IC)) 17886909Simp return false; 17986909Simp return true; 18086909Simp } 18186909Simp } 18286909Simp} 18386909Simp 18486909Simp/// GetShiftedValue - When CanEvaluateShifted returned true for an expression, 18586909Simp/// this value inserts the new computation that produces the shifted value. 18686909Simpstatic Value *GetShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, 18786909Simp InstCombiner &IC) { 188120175Sbde // We can always evaluate constants shifted. 18986909Simp if (Constant *C = dyn_cast<Constant>(V)) { 190120189Sbde if (isLeftShift) 19186909Simp V = IC.Builder->CreateShl(C, NumBits); 19286909Simp else 19386909Simp V = IC.Builder->CreateLShr(C, NumBits); 19486909Simp // If we got a constantexpr back, try to simplify it with TD info. 19586909Simp if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 19686909Simp V = ConstantFoldConstantExpression(CE, IC.getTargetData()); 19786909Simp return V; 19886909Simp } 19986909Simp 20086909Simp Instruction *I = cast<Instruction>(V); 20186909Simp IC.Worklist.Add(I); 20286909Simp 20386909Simp switch (I->getOpcode()) { 20486909Simp default: assert(0 && "Inconsistency with CanEvaluateShifted"); 20586909Simp case Instruction::And: 20686909Simp case Instruction::Or: 20786909Simp case Instruction::Xor: 20886909Simp // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted. 20986909Simp I->setOperand(0, GetShiftedValue(I->getOperand(0), NumBits,isLeftShift,IC)); 21086909Simp I->setOperand(1, GetShiftedValue(I->getOperand(1), NumBits,isLeftShift,IC)); 21186909Simp return I; 21286909Simp 21386909Simp case Instruction::Shl: { 21486909Simp unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 21586909Simp 21686909Simp // We only accept shifts-by-a-constant in CanEvaluateShifted. 21786909Simp ConstantInt *CI = cast<ConstantInt>(I->getOperand(1)); 21886909Simp 21986909Simp // We can always fold shl(c1)+shl(c2) -> shl(c1+c2). 220120189Sbde if (isLeftShift) { 22186909Simp // If this is oversized composite shift, then unsigned shifts get 0. 22286909Simp unsigned NewShAmt = NumBits+CI->getZExtValue(); 22386909Simp if (NewShAmt >= TypeWidth) 22486909Simp return Constant::getNullValue(I->getType()); 22586909Simp 22686909Simp I->setOperand(1, ConstantInt::get(I->getType(), NewShAmt)); 22786909Simp return I; 22886909Simp } 229111613Sphk 230225203Srwatson // We turn shl(c)+lshr(c) -> and(c2) if the input doesn't already have 231119485Snjl // zeros. 232119485Snjl if (CI->getValue() == NumBits) { 23386909Simp APInt Mask(APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits)); 23486909Simp V = IC.Builder->CreateAnd(I->getOperand(0), 23586909Simp ConstantInt::get(I->getContext(), Mask)); 23686909Simp if (Instruction *VI = dyn_cast<Instruction>(V)) { 23786909Simp VI->moveBefore(I); 23886909Simp VI->takeName(I); 23989986Sjhay } 24089986Sjhay return V; 24186909Simp } 24286909Simp 243116120Sscottl // We turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but only when we know that 244116120Sscottl // the and won't be needed. 24586909Simp assert(CI->getZExtValue() > NumBits); 24686909Simp I->setOperand(1, ConstantInt::get(I->getType(), 24786909Simp CI->getZExtValue() - NumBits)); 24886909Simp return I; 24986909Simp } 25086909Simp case Instruction::LShr: { 25186909Simp unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 25286909Simp // We only accept shifts-by-a-constant in CanEvaluateShifted. 25386909Simp ConstantInt *CI = cast<ConstantInt>(I->getOperand(1)); 25486909Simp 25593010Sbde // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2). 25651078Speter if (!isLeftShift) { 25751078Speter // If this is oversized composite shift, then unsigned shifts get 0. 258131373Sphk unsigned NewShAmt = NumBits+CI->getZExtValue(); 25951078Speter if (NewShAmt >= TypeWidth) 26093010Sbde return Constant::getNullValue(I->getType()); 261136478Sphk 262136478Sphk I->setOperand(1, ConstantInt::get(I->getType(), NewShAmt)); 26393010Sbde return I; 26493010Sbde } 265166901Spiso 266131094Sphk // We turn lshr(c)+shl(c) -> and(c2) if the input doesn't already have 26793010Sbde // zeros. 26893010Sbde if (CI->getValue() == NumBits) { 26993010Sbde APInt Mask(APInt::getHighBitsSet(TypeWidth, TypeWidth - NumBits)); 27093010Sbde V = IC.Builder->CreateAnd(I->getOperand(0), 27193010Sbde ConstantInt::get(I->getContext(), Mask)); 27293010Sbde if (Instruction *VI = dyn_cast<Instruction>(V)) { 27351078Speter VI->moveBefore(I); 27451078Speter VI->takeName(I); 27585365Simp } 27670174Sjhb return V; 27770174Sjhb } 27851078Speter 27951078Speter // We turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but only when we know that 28085365Simp // the and won't be needed. 28151078Speter assert(CI->getZExtValue() > NumBits); 28286909Simp I->setOperand(1, ConstantInt::get(I->getType(), 28351078Speter CI->getZExtValue() - NumBits)); 284114722Sobrien return I; 28551078Speter } 28689986Sjhay 28789986Sjhay case Instruction::Select: 28898401Sn_hibma I->setOperand(1, GetShiftedValue(I->getOperand(1), NumBits,isLeftShift,IC)); 28998401Sn_hibma I->setOperand(2, GetShiftedValue(I->getOperand(2), NumBits,isLeftShift,IC)); 29098401Sn_hibma return I; 29151078Speter case Instruction::PHI: { 29251078Speter // We can change a phi if we can change all operands. Note that we never 29398401Sn_hibma // get into trouble with cyclic PHIs here because we only consider 29472238Sjhb // instructions with a single use. 29572238Sjhb PHINode *PN = cast<PHINode>(I); 29651078Speter for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 29751078Speter PN->setIncomingValue(i, GetShiftedValue(PN->getIncomingValue(i), 29851078Speter NumBits, isLeftShift, IC)); 29951078Speter return PN; 30053344Speter } 30151078Speter } 302131939Smarcel} 303131939Smarcel 304131939Smarcel 305131939Smarcel 30651078SpeterInstruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1, 30751078Speter BinaryOperator &I) { 30886909Simp bool isLeftShift = I.getOpcode() == Instruction::Shl; 30951078Speter 31051078Speter 31151078Speter // See if we can propagate this shift into the input, this covers the trivial 31251078Speter // cast of lshr(shl(x,c1),c2) as well as other more complex cases. 31351078Speter if (I.getOpcode() != Instruction::AShr && 31451078Speter CanEvaluateShifted(Op0, Op1->getZExtValue(), isLeftShift, *this)) { 31551078Speter DEBUG(dbgs() << "ICE: GetShiftedValue propagating shift through expression" 31651078Speter " to eliminate shift:\n IN: " << *Op0 << "\n SH: " << I <<"\n"); 31751078Speter 31851078Speter return ReplaceInstUsesWith(I, 31951078Speter GetShiftedValue(Op0, Op1->getZExtValue(), isLeftShift, *this)); 32051078Speter } 32151078Speter 32251078Speter 32351078Speter // See if we can simplify any instructions used by the instruction whose sole 32462573Sphk // purpose is to compute bits we don't care about. 32551078Speter uint32_t TypeBits = Op0->getType()->getScalarSizeInBits(); 32651078Speter 32751078Speter // shl i32 X, 32 = 0 and srl i8 Y, 9 = 0, ... just don't eliminate 32851078Speter // a signed shift. 32951078Speter // 33051078Speter if (Op1->uge(TypeBits)) { 33151078Speter if (I.getOpcode() != Instruction::AShr) 33251078Speter return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType())); 33351078Speter // ashr i32 X, 32 --> ashr i32 X, 31 33451078Speter I.setOperand(1, ConstantInt::get(I.getType(), TypeBits-1)); 33551078Speter return &I; 33651078Speter } 33751078Speter 33851078Speter // ((X*C1) << C2) == (X * (C1 << C2)) 33951078Speter if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) 34051078Speter if (BO->getOpcode() == Instruction::Mul && isLeftShift) 34151078Speter if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1))) 34251078Speter return BinaryOperator::CreateMul(BO->getOperand(0), 34357915Simp ConstantExpr::getShl(BOOp, Op1)); 34451078Speter 34551078Speter // Try to fold constant and into select arguments. 346135329Sphk if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 347135516Snyan if (Instruction *R = FoldOpIntoSelect(I, SI)) 348135516Snyan return R; 349135516Snyan if (isa<PHINode>(Op0)) 35051078Speter if (Instruction *NV = FoldOpIntoPhi(I)) 35151078Speter return NV; 35251078Speter 35351078Speter // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2)) 35451078Speter if (TruncInst *TI = dyn_cast<TruncInst>(Op0)) { 355135329Sphk Instruction *TrOp = dyn_cast<Instruction>(TI->getOperand(0)); 356135329Sphk // If 'shift2' is an ashr, we would have to get the sign bit into a funny 357135329Sphk // place. Don't try to do this transformation in this case. Also, we 358135329Sphk // require that the input operand is a shift-by-constant so that we have 35951078Speter // confidence that the shifts will get folded together. We could do this 360135516Snyan // xform in more cases, but it is unlikely to be profitable. 36151078Speter if (TrOp && I.isLogicalShift() && TrOp->isShift() && 36251078Speter isa<ConstantInt>(TrOp->getOperand(1))) { 36351078Speter // Okay, we'll do this xform. Make the shift of shift. 36451078Speter Constant *ShAmt = ConstantExpr::getZExt(Op1, TrOp->getType()); 36551078Speter // (shift2 (shift1 & 0x00FF), c2) 36651078Speter Value *NSh = Builder->CreateBinOp(I.getOpcode(), TrOp, ShAmt,I.getName()); 36751078Speter 36851078Speter // For logical shifts, the truncation has the effect of making the high 36951078Speter // part of the register be zeros. Emulate this by inserting an AND to 37051078Speter // clear the top bits as needed. This 'and' will usually be zapped by 37151078Speter // other xforms later if dead. 372153195Simp unsigned SrcSize = TrOp->getType()->getScalarSizeInBits(); 37351078Speter unsigned DstSize = TI->getType()->getScalarSizeInBits(); 37486909Simp APInt MaskV(APInt::getLowBitsSet(SrcSize, DstSize)); 37586909Simp 37686909Simp // The mask we constructed says what the trunc would do if occurring 37786909Simp // between the shifts. We want to know the effect *after* the second 37886909Simp // shift. We know that it is a logical shift by a constant, so adjust the 37986909Simp // mask as appropriate. 38086909Simp if (I.getOpcode() == Instruction::Shl) 38186909Simp MaskV <<= Op1->getZExtValue(); 382104933Simp else { 38386909Simp assert(I.getOpcode() == Instruction::LShr && "Unknown logical shift"); 38486909Simp MaskV = MaskV.lshr(Op1->getZExtValue()); 38586909Simp } 38686909Simp 38785365Simp // shift1 & 0x00FF 388136478Sphk Value *And = Builder->CreateAnd(NSh, 38951078Speter ConstantInt::get(I.getContext(), MaskV), 39051078Speter TI->getName()); 39151078Speter 39252471Simp // Return the value truncated to the interesting size. 39357915Simp return new TruncInst(And, I.getType()); 39452471Simp } 39554386Simp } 39651078Speter 397120175Sbde if (Op0->hasOneUse()) { 398132561Simp if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) { 399136478Sphk // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 40054386Simp Value *V1, *V2; 40154386Simp ConstantInt *CC; 40254386Simp switch (Op0BO->getOpcode()) { 40354386Simp default: break; 40454386Simp case Instruction::Add: 405116120Sscottl case Instruction::And: 406116120Sscottl case Instruction::Or: 407136478Sphk case Instruction::Xor: { 408136478Sphk // These operators commute. 409136478Sphk // Turn (Y + (X >> C)) << C -> (X + (Y << C)) & (~0 << C) 410136478Sphk if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() && 411136478Sphk match(Op0BO->getOperand(1), m_Shr(m_Value(V1), 41253978Simp m_Specific(Op1)))) { 41351078Speter Value *YS = // (Y << C) 41451078Speter Builder->CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName()); 41585365Simp // (X + (Y << C)) 41689986Sjhay Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), YS, V1, 41758885Simp Op0BO->getOperand(1)->getName()); 41858885Simp uint32_t Op1Val = Op1->getLimitedValue(TypeBits); 41989986Sjhay return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(), 42085365Simp APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val))); 42151078Speter } 42253344Speter 42351078Speter // Turn (Y + ((X >> C) & CC)) << C -> ((X & (CC << C)) + (Y << C)) 42453344Speter Value *Op0BOOp1 = Op0BO->getOperand(1); 42553344Speter if (isLeftShift && Op0BOOp1->hasOneUse() && 42660471Snyan match(Op0BOOp1, 42789986Sjhay m_And(m_Shr(m_Value(V1), m_Specific(Op1)), 42851078Speter m_ConstantInt(CC))) && 42951078Speter cast<BinaryOperator>(Op0BOOp1)->getOperand(0)->hasOneUse()) { 43051078Speter Value *YS = // (Y << C) 43151078Speter Builder->CreateShl(Op0BO->getOperand(0), Op1, 43251078Speter Op0BO->getName()); 43351078Speter // X & (CC << C) 43451078Speter Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1), 43551078Speter V1->getName()+".mask"); 43654206Speter return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM); 43751088Speter } 43851078Speter } 43951078Speter 44051078Speter // FALL THROUGH. 44158885Simp case Instruction::Sub: { 44251078Speter // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 44351078Speter if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 44451078Speter match(Op0BO->getOperand(0), m_Shr(m_Value(V1), 44557915Simp m_Specific(Op1)))) { 44651078Speter Value *YS = // (Y << C) 44786909Simp Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 448124669Sru // (X + (Y << C)) 449124669Sru Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), V1, YS, 45086909Simp Op0BO->getOperand(0)->getName()); 451124669Sru uint32_t Op1Val = Op1->getLimitedValue(TypeBits); 45286909Simp return BinaryOperator::CreateAnd(X, ConstantInt::get(I.getContext(), 45360471Snyan APInt::getHighBitsSet(TypeBits, TypeBits-Op1Val))); 45460471Snyan } 45589986Sjhay 45689986Sjhay // Turn (((X >> C)&CC) + Y) << C -> (X + (Y << C)) & (CC << C) 45789986Sjhay if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 45860471Snyan match(Op0BO->getOperand(0), 45985209Sjhb m_And(m_Shr(m_Value(V1), m_Value(V2)), 46085209Sjhb m_ConstantInt(CC))) && V2 == Op1 && 46193818Sjhb cast<BinaryOperator>(Op0BO->getOperand(0)) 46293818Sjhb ->getOperand(0)->hasOneUse()) { 46385209Sjhb Value *YS = // (Y << C) 46485209Sjhb Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 46585209Sjhb // X & (CC << C) 46670174Sjhb Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1), 46753344Speter V1->getName()+".mask"); 46853344Speter 46953344Speter return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS); 47053344Speter } 47153344Speter 47253344Speter break; 47353344Speter } 47453344Speter } 47551078Speter 47651078Speter 47751078Speter // If the operand is an bitwise operator with a constant RHS, and the 47851078Speter // shift is the only use, we can pull it out of the shift. 47951078Speter if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) { 48051078Speter bool isValid = true; // Valid only for And, Or, Xor 48151078Speter bool highBitSet = false; // Transform if high bit of constant set? 48251078Speter 48353344Speter switch (Op0BO->getOpcode()) { 48451078Speter default: isValid = false; break; // Do not perform transform! 48551078Speter case Instruction::Add: 48651078Speter isValid = isLeftShift; 48751078Speter break; 48854194Speter case Instruction::Or: 48954194Speter case Instruction::Xor: 49054194Speter highBitSet = false; 49153344Speter break; 49251078Speter case Instruction::And: 49351078Speter highBitSet = true; 49451078Speter break; 49551078Speter } 49653344Speter 49751078Speter // If this is a signed shift right, and the high bit is modified 49851078Speter // by the logical operation, do not perform the transformation. 49951078Speter // The highBitSet boolean indicates the value of the high bit of 50051078Speter // the constant which would cause it to be modified for this 50156788Sbde // operation. 50286909Simp // 50386909Simp if (isValid && I.getOpcode() == Instruction::AShr) 50451078Speter isValid = Op0C->getValue()[TypeBits-1] == highBitSet; 50551078Speter 50651078Speter if (isValid) { 50751078Speter Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, Op1); 50851078Speter 50951078Speter Value *NewShift = 51051078Speter Builder->CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1); 51151078Speter NewShift->takeName(Op0BO); 51251078Speter 51351078Speter return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, 51451078Speter NewRHS); 51551078Speter } 51651078Speter } 51751078Speter } 51857234Sbde } 51954206Speter 52054206Speter // Find out if this is a shift of a shift by a constant. 52154206Speter BinaryOperator *ShiftOp = dyn_cast<BinaryOperator>(Op0); 52251078Speter if (ShiftOp && !ShiftOp->isShift()) 52351078Speter ShiftOp = 0; 52451078Speter 52551078Speter if (ShiftOp && isa<ConstantInt>(ShiftOp->getOperand(1))) { 52651078Speter ConstantInt *ShiftAmt1C = cast<ConstantInt>(ShiftOp->getOperand(1)); 52751078Speter uint32_t ShiftAmt1 = ShiftAmt1C->getLimitedValue(TypeBits); 52857234Sbde uint32_t ShiftAmt2 = Op1->getLimitedValue(TypeBits); 52957234Sbde assert(ShiftAmt2 != 0 && "Should have been simplified earlier"); 53057234Sbde if (ShiftAmt1 == 0) return 0; // Will be simplified in the future. 53157234Sbde Value *X = ShiftOp->getOperand(0); 53257234Sbde 53357234Sbde uint32_t AmtSum = ShiftAmt1+ShiftAmt2; // Fold into one big shift. 53457234Sbde 53557234Sbde const IntegerType *Ty = cast<IntegerType>(I.getType()); 53657234Sbde 53757234Sbde // Check for (X << c1) << c2 and (X >> c1) >> c2 53857234Sbde if (I.getOpcode() == ShiftOp->getOpcode()) { 53951078Speter // If this is oversized composite shift, then unsigned shifts get 0, ashr 54051078Speter // saturates. 54151078Speter if (AmtSum >= TypeBits) { 54254194Speter if (I.getOpcode() != Instruction::AShr) 54351078Speter return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 54451078Speter AmtSum = TypeBits-1; // Saturate to 31 for i32 ashr. 54551078Speter } 54651078Speter 54751078Speter return BinaryOperator::Create(I.getOpcode(), X, 54851078Speter ConstantInt::get(Ty, AmtSum)); 54951078Speter } 55051078Speter 55151078Speter if (ShiftAmt1 == ShiftAmt2) { 55251078Speter // If we have ((X >>? C) << C), turn this into X & (-1 << C). 55351078Speter if (I.getOpcode() == Instruction::Shl && 55472200Sbmilekic ShiftOp->getOpcode() != Instruction::Shl) { 55551078Speter APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt1)); 55651078Speter return BinaryOperator::CreateAnd(X, 55751078Speter ConstantInt::get(I.getContext(),Mask)); 558112384Ssobomax } 559112384Ssobomax // If we have ((X << C) >>u C), turn this into X & (-1 >>u C). 560112270Ssobomax if (I.getOpcode() == Instruction::LShr && 561112270Ssobomax ShiftOp->getOpcode() == Instruction::Shl) { 562112270Ssobomax APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt1)); 563112384Ssobomax return BinaryOperator::CreateAnd(X, 564112270Ssobomax ConstantInt::get(I.getContext(), Mask)); 565112384Ssobomax } 566112384Ssobomax } else if (ShiftAmt1 < ShiftAmt2) { 567112384Ssobomax uint32_t ShiftDiff = ShiftAmt2-ShiftAmt1; 568112384Ssobomax 569112384Ssobomax // (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2) 570112384Ssobomax if (I.getOpcode() == Instruction::Shl && 571112384Ssobomax ShiftOp->getOpcode() != Instruction::Shl) { 572112384Ssobomax assert(ShiftOp->getOpcode() == Instruction::LShr || 573112384Ssobomax ShiftOp->getOpcode() == Instruction::AShr); 574112384Ssobomax Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff)); 575112384Ssobomax 576112384Ssobomax APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2)); 577112384Ssobomax return BinaryOperator::CreateAnd(Shift, 578112270Ssobomax ConstantInt::get(I.getContext(),Mask)); 579112384Ssobomax } 580112270Ssobomax 58151078Speter // (X << C1) >>u C2 --> X >>u (C2-C1) & (-1 >> C2) 58251078Speter if (I.getOpcode() == Instruction::LShr && 58351078Speter ShiftOp->getOpcode() == Instruction::Shl) { 58451078Speter assert(ShiftOp->getOpcode() == Instruction::Shl); 58551078Speter Value *Shift = Builder->CreateLShr(X, ConstantInt::get(Ty, ShiftDiff)); 58651078Speter 58751078Speter APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 58851078Speter return BinaryOperator::CreateAnd(Shift, 58951078Speter ConstantInt::get(I.getContext(),Mask)); 59051078Speter } 59151078Speter 59251078Speter // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in. 59360471Snyan } else { 59489986Sjhay assert(ShiftAmt2 < ShiftAmt1); 59589986Sjhay uint32_t ShiftDiff = ShiftAmt1-ShiftAmt2; 59689986Sjhay 59760471Snyan // (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2) 59851078Speter if (I.getOpcode() == Instruction::Shl && 59951078Speter ShiftOp->getOpcode() != Instruction::Shl) { 60051078Speter Value *Shift = Builder->CreateBinOp(ShiftOp->getOpcode(), X, 60151078Speter ConstantInt::get(Ty, ShiftDiff)); 602172568Skevlo 60351078Speter APInt Mask(APInt::getHighBitsSet(TypeBits, TypeBits - ShiftAmt2)); 60451078Speter return BinaryOperator::CreateAnd(Shift, 60551078Speter ConstantInt::get(I.getContext(),Mask)); 60651078Speter } 60760471Snyan 60860471Snyan // (X << C1) >>u C2 --> X << (C1-C2) & (-1 >> C2) 60951078Speter if (I.getOpcode() == Instruction::LShr && 61051078Speter ShiftOp->getOpcode() == Instruction::Shl) { 61151078Speter Value *Shift = Builder->CreateShl(X, ConstantInt::get(Ty, ShiftDiff)); 61251078Speter 61351078Speter APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 61451078Speter return BinaryOperator::CreateAnd(Shift, 61551078Speter ConstantInt::get(I.getContext(),Mask)); 61651078Speter } 61760471Snyan 61851078Speter // We can't handle (X << C1) >>a C2, it shifts arbitrary bits in. 61951078Speter } 62051078Speter } 62151078Speter return 0; 62251078Speter} 62351078Speter 62451078SpeterInstruction *InstCombiner::visitShl(BinaryOperator &I) { 62551078Speter return commonShiftTransforms(I); 62651078Speter} 62760471Snyan 62851078SpeterInstruction *InstCombiner::visitLShr(BinaryOperator &I) { 62951078Speter if (Instruction *R = commonShiftTransforms(I)) 63051078Speter return R; 63151078Speter 63251078Speter Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 63351078Speter 63451078Speter if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) 63560471Snyan if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) { 636120468Sbde unsigned BitWidth = Op0->getType()->getScalarSizeInBits(); 637120468Sbde // ctlz.i32(x)>>5 --> zext(x == 0) 638120468Sbde // cttz.i32(x)>>5 --> zext(x == 0) 639120468Sbde // ctpop.i32(x)>>5 --> zext(x == -1) 64051078Speter if ((II->getIntrinsicID() == Intrinsic::ctlz || 64151078Speter II->getIntrinsicID() == Intrinsic::cttz || 64251078Speter II->getIntrinsicID() == Intrinsic::ctpop) && 64351078Speter isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == Op1C->getZExtValue()){ 64451078Speter bool isCtPop = II->getIntrinsicID() == Intrinsic::ctpop; 64551078Speter Constant *RHS = ConstantInt::getSigned(Op0->getType(), isCtPop ? -1:0); 64651078Speter Value *Cmp = Builder->CreateICmpEQ(II->getArgOperand(0), RHS); 64751078Speter return new ZExtInst(Cmp, II->getType()); 64851078Speter } 64960471Snyan } 65092401Simp 65192401Simp return 0; 65292401Simp} 65392401Simp 65492401SimpInstruction *InstCombiner::visitAShr(BinaryOperator &I) { 65592401Simp if (Instruction *R = commonShiftTransforms(I)) 65692401Simp return R; 65751078Speter 65851078Speter Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 659120189Sbde 660120189Sbde if (ConstantInt *CSI = dyn_cast<ConstantInt>(Op0)) { 661120189Sbde // ashr int -1, X = -1 (for any arithmetic shift rights of ~0) 662120189Sbde if (CSI->isAllOnesValue()) 663120189Sbde return ReplaceInstUsesWith(I, CSI); 66451078Speter } 66585365Simp 666120189Sbde if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 66753370Speter // If the input is a SHL by the same constant (ashr (shl X, C), C), then we 66853370Speter // have a sign-extend idiom. 66960471Snyan Value *X; 67053370Speter if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1)))) { 671120189Sbde // If the input value is known to already be sign extended enough, delete 672120189Sbde // the extension. 67353370Speter if (ComputeNumSignBits(X) > Op1C->getZExtValue()) 67453370Speter return ReplaceInstUsesWith(I, X); 675120189Sbde 676120189Sbde // If the input is an extension from the shifted amount value, e.g. 677120189Sbde // %x = zext i8 %A to i32 678120189Sbde // %y = shl i32 %x, 24 67960471Snyan // %z = ashr %y, 24 68060471Snyan // then turn this into "z = sext i8 A to i32". 681120189Sbde if (ZExtInst *ZI = dyn_cast<ZExtInst>(X)) { 68253370Speter uint32_t SrcBits = ZI->getOperand(0)->getType()->getScalarSizeInBits(); 68353370Speter uint32_t DestBits = ZI->getType()->getScalarSizeInBits(); 684120189Sbde if (Op1C->getZExtValue() == DestBits-SrcBits) 68553370Speter return new SExtInst(ZI->getOperand(0), ZI->getType()); 68681793Simp } 68753370Speter } 68851078Speter } 689120189Sbde 69053370Speter // See if we can turn a signed shr into an unsigned shr. 69151078Speter if (MaskedValueIsZero(Op0, 69281793Simp APInt::getSignBit(I.getType()->getScalarSizeInBits()))) 69360471Snyan return BinaryOperator::CreateLShr(Op0, Op1); 69472200Sbmilekic 69553344Speter // Arithmetic shifting an all-sign-bit value is a no-op. 696128899Sambrisko unsigned NumSignBits = ComputeNumSignBits(Op0); 69786909Simp if (NumSignBits == Op0->getType()->getScalarSizeInBits()) 698183692Simp return ReplaceInstUsesWith(I, Op0); 699183692Simp 700183692Simp return 0; 701183692Simp} 702183692Simp 703183692Simp