19cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner//===- InstCombineShifts.cpp ----------------------------------------------===// 29cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner// 39cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner// The LLVM Compiler Infrastructure 49cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner// 59cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner// This file is distributed under the University of Illinois Open Source 69cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner// License. See LICENSE.TXT for details. 79cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner// 89cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner//===----------------------------------------------------------------------===// 99cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner// 109cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner// This file implements the visitShl, visitLShr, and visitAShr functions. 119cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner// 129cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner//===----------------------------------------------------------------------===// 139cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 14ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "InstCombineInternal.h" 15747032522f9f3b2d9bae71aa303c1a0fd953eee9Eli Friedman#include "llvm/Analysis/ConstantFolding.h" 16c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands#include "llvm/Analysis/InstructionSimplify.h" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/PatternMatch.h" 199cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattnerusing namespace llvm; 209cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattnerusing namespace PatternMatch; 219cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "instcombine" 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 249cdd5f3fe3e857505012554d678fcd80f3f74617Chris LattnerInstruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) { 259cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner assert(I.getOperand(1)->getType() == I.getOperand(0)->getType()); 269cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 279cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 289cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // See if we can fold away this shift. 299cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (SimplifyDemandedInstructionBits(I)) 309cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return &I; 319cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 329cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // Try to fold constant and into select arguments. 339cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (isa<Constant>(Op0)) 349cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 359cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 369cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return R; 379cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 38dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Constant *CUI = dyn_cast<Constant>(Op1)) 399cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I)) 409cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return Res; 41b70ebd2aa3b6f4546d4734e7bcdbed2017036b4dBenjamin Kramer 4294c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // X shift (A srem B) -> X shift (A and B-1) iff B is a power of 2. 437a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // Because shifts by negative values (which could occur if A were negative) 447a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // are undefined. 457a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Value *A; const APInt *B; 467a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Power2(B)))) { 477a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't 487a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // demand the sign bit (and many others) here?? 497a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Value *Rem = Builder->CreateAnd(A, ConstantInt::get(I.getType(), *B-1), 507a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Op1->getName()); 517a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner I.setOperand(1, Rem); 527a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return &I; 537a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 540fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 569cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner} 579cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 5829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// CanEvaluateShifted - See if we can compute the specified value, but shifted 5929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// logically to the left or right by some number of bits. This should return 6029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// true if the expression can be computed for the same cost as the current 6129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// expression tree. This is used to eliminate extraneous shifting from things 6229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// like: 6329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// %C = shl i128 %A, 64 6429cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// %D = shl i128 %B, 96 6529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// %E = or i128 %C, %D 6629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// %F = lshr i128 %E, 64 6729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// where the client will ask if E can be computed shifted right by 64-bits. If 6829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// this succeeds, the GetShiftedValue function will be called to produce the 6929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// value. 7029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattnerstatic bool CanEvaluateShifted(Value *V, unsigned NumBits, bool isLeftShift, 7137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines InstCombiner &IC, Instruction *CxtI) { 7229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can always evaluate constants shifted. 7329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (isa<Constant>(V)) 7429cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return true; 750fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 7629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner Instruction *I = dyn_cast<Instruction>(V); 7729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (!I) return false; 780fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 7929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // If this is the opposite shift, we can directly reuse the input of the shift 8029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // if the needed bits are already zero in the input. This allows us to reuse 8129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // the value which means that we don't care if the shift has multiple uses. 8229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // TODO: Handle opposite shift by exact value. 83dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ConstantInt *CI = nullptr; 8429cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if ((isLeftShift && match(I, m_LShr(m_Value(), m_ConstantInt(CI)))) || 8529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner (!isLeftShift && match(I, m_Shl(m_Value(), m_ConstantInt(CI))))) { 8629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (CI->getZExtValue() == NumBits) { 8729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // TODO: Check that the input bits are already zero with MaskedValueIsZero 8829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner#if 0 8929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // If this is a truncate of a logical shr, we can truncate it to a smaller 9094c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // lshr iff we know that the bits we would otherwise be shifting in are 9129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // already zeros. 9229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits(); 9329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner uint32_t BitWidth = Ty->getScalarSizeInBits(); 9429cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (MaskedValueIsZero(I->getOperand(0), 9529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) && 9629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner CI->getLimitedValue(BitWidth) < BitWidth) { 9729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return CanEvaluateTruncated(I->getOperand(0), Ty); 9829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 9929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner#endif 1000fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 10129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 10229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 1030fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 10429cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can't mutate something that has multiple uses: doing so would 10529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // require duplicating the instruction in general, which isn't profitable. 10629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (!I->hasOneUse()) return false; 1070fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 10829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner switch (I->getOpcode()) { 10929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner default: return false; 11029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::And: 11129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::Or: 11229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::Xor: 11329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted. 11437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return CanEvaluateShifted(I->getOperand(0), NumBits, isLeftShift, IC, I) && 11537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines CanEvaluateShifted(I->getOperand(1), NumBits, isLeftShift, IC, I); 1160fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 1174ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner case Instruction::Shl: { 11829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can often fold the shift into shifts-by-a-constant. 11929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner CI = dyn_cast<ConstantInt>(I->getOperand(1)); 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!CI) return false; 12129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner 12229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can always fold shl(c1)+shl(c2) -> shl(c1+c2). 12329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (isLeftShift) return true; 1240fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 12529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can always turn shl(c)+shr(c) -> and(c2). 12629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (CI->getValue() == NumBits) return true; 1270fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 1284ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 1294ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner 1304ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner // We can turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but it isn't 13129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // profitable unless we know the and'd out bits are already zero. 1324ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner if (CI->getZExtValue() > NumBits) { 133201ab3acff18c0470950d43495419185e8a7afd3Dale Johannesen unsigned LowBits = TypeWidth - CI->getZExtValue(); 13437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (IC.MaskedValueIsZero(I->getOperand(0), 13537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt::getLowBitsSet(TypeWidth, NumBits) << LowBits, 13637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 0, CxtI)) 1374ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner return true; 1384ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner } 1390fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 14029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return false; 1414ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner } 1424ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner case Instruction::LShr: { 14329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can often fold the shift into shifts-by-a-constant. 14429cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner CI = dyn_cast<ConstantInt>(I->getOperand(1)); 145dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!CI) return false; 1460fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 14729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2). 14829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (!isLeftShift) return true; 1490fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 15029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can always turn lshr(c)+shl(c) -> and(c2). 15129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (CI->getValue() == NumBits) return true; 1520fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 1534ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner unsigned TypeWidth = I->getType()->getScalarSizeInBits(); 1544ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner 15529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can always turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but it isn't 15629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // profitable unless we know the and'd out bits are already zero. 15765195411ccb18ea8327d3eabdfa980eaf535d929Benjamin Kramer if (CI->getValue().ult(TypeWidth) && CI->getZExtValue() > NumBits) { 158ec3953ff95c6106185fc6509175b86cbdf3958f6Owen Anderson unsigned LowBits = CI->getZExtValue() - NumBits; 15937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (IC.MaskedValueIsZero(I->getOperand(0), 16037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt::getLowBitsSet(TypeWidth, NumBits) << LowBits, 16137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 0, CxtI)) 1624ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner return true; 1634ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner } 1640fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 1654ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner return false; 1664ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner } 16729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::Select: { 16829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner SelectInst *SI = cast<SelectInst>(I); 16937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return CanEvaluateShifted(SI->getTrueValue(), NumBits, isLeftShift, 17037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines IC, SI) && 17137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines CanEvaluateShifted(SI->getFalseValue(), NumBits, isLeftShift, IC, SI); 17229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 17329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::PHI: { 17429cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can change a phi if we can change all operands. Note that we never 17529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // get into trouble with cyclic PHIs here because we only consider 17629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // instructions with a single use. 17729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner PHINode *PN = cast<PHINode>(I); 17829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 17937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!CanEvaluateShifted(PN->getIncomingValue(i), NumBits, isLeftShift, 18037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines IC, PN)) 18129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return false; 18229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return true; 18329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 1840fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak } 18529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner} 18629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner 18729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// GetShiftedValue - When CanEvaluateShifted returned true for an expression, 18829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner/// this value inserts the new computation that produces the shifted value. 18929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattnerstatic Value *GetShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, 1904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar InstCombiner &IC, const DataLayout &DL) { 19129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can always evaluate constants shifted. 19229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (Constant *C = dyn_cast<Constant>(V)) { 19329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (isLeftShift) 19429cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner V = IC.Builder->CreateShl(C, NumBits); 19529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner else 19629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner V = IC.Builder->CreateLShr(C, NumBits); 19729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // If we got a constantexpr back, try to simplify it with TD info. 19829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 1994c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar V = ConstantFoldConstantExpression(CE, DL, IC.getTargetLibraryInfo()); 20029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return V; 20129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 2020fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 20329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner Instruction *I = cast<Instruction>(V); 20429cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner IC.Worklist.Add(I); 20529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner 20629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner switch (I->getOpcode()) { 207858143816d43e58b17bfd11cb1b57afbd7f0f893Craig Topper default: llvm_unreachable("Inconsistency with CanEvaluateShifted"); 20829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::And: 20929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::Or: 21029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::Xor: 21129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted. 2124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar I->setOperand( 2134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 0, GetShiftedValue(I->getOperand(0), NumBits, isLeftShift, IC, DL)); 2144c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar I->setOperand( 2154c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1, GetShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL)); 21629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return I; 2170fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 21829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::Shl: { 219ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BinaryOperator *BO = cast<BinaryOperator>(I); 220ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman unsigned TypeWidth = BO->getType()->getScalarSizeInBits(); 22129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner 22229cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We only accept shifts-by-a-constant in CanEvaluateShifted. 223ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1)); 224ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman 22529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can always fold shl(c1)+shl(c2) -> shl(c1+c2). 22629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (isLeftShift) { 22729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // If this is oversized composite shift, then unsigned shifts get 0. 22829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner unsigned NewShAmt = NumBits+CI->getZExtValue(); 22929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (NewShAmt >= TypeWidth) 23029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return Constant::getNullValue(I->getType()); 23129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner 232ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BO->setOperand(1, ConstantInt::get(BO->getType(), NewShAmt)); 233ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BO->setHasNoUnsignedWrap(false); 234ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BO->setHasNoSignedWrap(false); 23529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return I; 23629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 2370fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 23829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We turn shl(c)+lshr(c) -> and(c2) if the input doesn't already have 23929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // zeros. 2404ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner if (CI->getValue() == NumBits) { 2414ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner APInt Mask(APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits)); 242ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman V = IC.Builder->CreateAnd(BO->getOperand(0), 243ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman ConstantInt::get(BO->getContext(), Mask)); 2444ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner if (Instruction *VI = dyn_cast<Instruction>(V)) { 245ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman VI->moveBefore(BO); 246ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman VI->takeName(BO); 2474ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner } 2484ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner return V; 24929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 2500fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 2514ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner // We turn shl(c1)+shr(c2) -> shl(c3)+and(c4), but only when we know that 2524ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner // the and won't be needed. 2534ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner assert(CI->getZExtValue() > NumBits); 254ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BO->setOperand(1, ConstantInt::get(BO->getType(), 255ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman CI->getZExtValue() - NumBits)); 256ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BO->setHasNoUnsignedWrap(false); 257ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BO->setHasNoSignedWrap(false); 258ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman return BO; 25929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 26029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::LShr: { 261ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BinaryOperator *BO = cast<BinaryOperator>(I); 262ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman unsigned TypeWidth = BO->getType()->getScalarSizeInBits(); 26329cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We only accept shifts-by-a-constant in CanEvaluateShifted. 264ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1)); 2650fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 26629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can always fold lshr(c1)+lshr(c2) -> lshr(c1+c2). 26729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (!isLeftShift) { 26829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // If this is oversized composite shift, then unsigned shifts get 0. 26929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner unsigned NewShAmt = NumBits+CI->getZExtValue(); 27029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (NewShAmt >= TypeWidth) 271ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman return Constant::getNullValue(BO->getType()); 2720fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 273ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BO->setOperand(1, ConstantInt::get(BO->getType(), NewShAmt)); 274ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BO->setIsExact(false); 27529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return I; 27629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 2770fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 27829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We turn lshr(c)+shl(c) -> and(c2) if the input doesn't already have 27929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // zeros. 2804ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner if (CI->getValue() == NumBits) { 2814ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner APInt Mask(APInt::getHighBitsSet(TypeWidth, TypeWidth - NumBits)); 2824ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner V = IC.Builder->CreateAnd(I->getOperand(0), 283ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman ConstantInt::get(BO->getContext(), Mask)); 2844ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner if (Instruction *VI = dyn_cast<Instruction>(V)) { 2854ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner VI->moveBefore(I); 2864ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner VI->takeName(I); 2874ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner } 2884ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner return V; 28929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 2900fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 2914ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner // We turn lshr(c1)+shl(c2) -> lshr(c3)+and(c4), but only when we know that 2924ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner // the and won't be needed. 2934ece577019705e0a4d7f80f8e8fc1f3cfde276eeChris Lattner assert(CI->getZExtValue() > NumBits); 294ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BO->setOperand(1, ConstantInt::get(BO->getType(), 295ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman CI->getZExtValue() - NumBits)); 296ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman BO->setIsExact(false); 297ef715972423a57febb7aa9b056d9bf6320e74817Eli Friedman return BO; 29829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 2990fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 30029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::Select: 3014c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar I->setOperand( 3024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1, GetShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL)); 3034c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar I->setOperand( 3044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 2, GetShiftedValue(I->getOperand(2), NumBits, isLeftShift, IC, DL)); 30529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return I; 30629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner case Instruction::PHI: { 30729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // We can change a phi if we can change all operands. Note that we never 30829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // get into trouble with cyclic PHIs here because we only consider 30929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // instructions with a single use. 31029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner PHINode *PN = cast<PHINode>(I); 31129cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 3124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar PN->setIncomingValue(i, GetShiftedValue(PN->getIncomingValue(i), NumBits, 3134c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar isLeftShift, IC, DL)); 31429cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner return PN; 31529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 3160fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak } 31729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner} 31829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner 31929cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner 32029cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner 321dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesInstruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1, 3229cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner BinaryOperator &I) { 3239cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner bool isLeftShift = I.getOpcode() == Instruction::Shl; 3240fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 325dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ConstantInt *COp1 = nullptr; 326dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(Op1)) 327dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines COp1 = dyn_cast_or_null<ConstantInt>(CV->getSplatValue()); 328dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines else if (ConstantVector *CV = dyn_cast<ConstantVector>(Op1)) 329dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines COp1 = dyn_cast_or_null<ConstantInt>(CV->getSplatValue()); 330dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines else 331dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines COp1 = dyn_cast<ConstantInt>(Op1); 332dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 333dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!COp1) 334dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 3350fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 33629cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // See if we can propagate this shift into the input, this covers the trivial 33729cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner // cast of lshr(shl(x,c1),c2) as well as other more complex cases. 33829cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner if (I.getOpcode() != Instruction::AShr && 33937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines CanEvaluateShifted(Op0, COp1->getZExtValue(), isLeftShift, *this, &I)) { 3403dd08734c1812e47ae5f6aceba15f28865f75943Chris Lattner DEBUG(dbgs() << "ICE: GetShiftedValue propagating shift through expression" 3413dd08734c1812e47ae5f6aceba15f28865f75943Chris Lattner " to eliminate shift:\n IN: " << *Op0 << "\n SH: " << I <<"\n"); 3420fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 3434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return ReplaceInstUsesWith( 3444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar I, GetShiftedValue(Op0, COp1->getZExtValue(), isLeftShift, *this, DL)); 34529cc0b3660dc75df06679c4c49cf91ffe24615ffChris Lattner } 3460fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 3470fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak // See if we can simplify any instructions used by the instruction whose sole 3489cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // purpose is to compute bits we don't care about. 3499cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner uint32_t TypeBits = Op0->getType()->getScalarSizeInBits(); 3500fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 351dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(!COp1->uge(TypeBits) && 352dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "Shift over the type width should have been removed already"); 3530fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 3549cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // ((X*C1) << C2) == (X * (C1 << C2)) 3559cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) 3569cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (BO->getOpcode() == Instruction::Mul && isLeftShift) 3579cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1))) 3589cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return BinaryOperator::CreateMul(BO->getOperand(0), 3599cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner ConstantExpr::getShl(BOOp, Op1)); 3600fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 3619cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // Try to fold constant and into select arguments. 3629cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 3639cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 3649cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return R; 3659cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (isa<PHINode>(Op0)) 3669cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 3679cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return NV; 3680fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 3699cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2)) 3709cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (TruncInst *TI = dyn_cast<TruncInst>(Op0)) { 3719cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner Instruction *TrOp = dyn_cast<Instruction>(TI->getOperand(0)); 3729cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // If 'shift2' is an ashr, we would have to get the sign bit into a funny 3739cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // place. Don't try to do this transformation in this case. Also, we 3749cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // require that the input operand is a shift-by-constant so that we have 3759cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // confidence that the shifts will get folded together. We could do this 3769cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // xform in more cases, but it is unlikely to be profitable. 3770fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak if (TrOp && I.isLogicalShift() && TrOp->isShift() && 3789cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner isa<ConstantInt>(TrOp->getOperand(1))) { 3799cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // Okay, we'll do this xform. Make the shift of shift. 380dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *ShAmt = ConstantExpr::getZExt(COp1, TrOp->getType()); 3819cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // (shift2 (shift1 & 0x00FF), c2) 3829cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner Value *NSh = Builder->CreateBinOp(I.getOpcode(), TrOp, ShAmt,I.getName()); 3839cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 3849cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // For logical shifts, the truncation has the effect of making the high 3859cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // part of the register be zeros. Emulate this by inserting an AND to 3869cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // clear the top bits as needed. This 'and' will usually be zapped by 3879cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // other xforms later if dead. 3889cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner unsigned SrcSize = TrOp->getType()->getScalarSizeInBits(); 3899cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner unsigned DstSize = TI->getType()->getScalarSizeInBits(); 3909cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner APInt MaskV(APInt::getLowBitsSet(SrcSize, DstSize)); 3910fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 3929cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // The mask we constructed says what the trunc would do if occurring 3939cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // between the shifts. We want to know the effect *after* the second 3949cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // shift. We know that it is a logical shift by a constant, so adjust the 3959cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // mask as appropriate. 3969cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (I.getOpcode() == Instruction::Shl) 397dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MaskV <<= COp1->getZExtValue(); 3989cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner else { 3999cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner assert(I.getOpcode() == Instruction::LShr && "Unknown logical shift"); 400dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MaskV = MaskV.lshr(COp1->getZExtValue()); 4019cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 4029cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 4039cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // shift1 & 0x00FF 4049cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner Value *And = Builder->CreateAnd(NSh, 4059cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner ConstantInt::get(I.getContext(), MaskV), 4069cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner TI->getName()); 4079cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 4089cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // Return the value truncated to the interesting size. 4099cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return new TruncInst(And, I.getType()); 4109cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 4119cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 4120fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 4139cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (Op0->hasOneUse()) { 4149cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) { 4159cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 4169cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner Value *V1, *V2; 4179cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner ConstantInt *CC; 4189cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner switch (Op0BO->getOpcode()) { 419abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner default: break; 420abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner case Instruction::Add: 421abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner case Instruction::And: 422abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner case Instruction::Or: 423abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner case Instruction::Xor: { 424abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner // These operators commute. 425abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner // Turn (Y + (X >> C)) << C -> (X + (Y << C)) & (~0 << C) 426abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() && 427abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner match(Op0BO->getOperand(1), m_Shr(m_Value(V1), 428abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner m_Specific(Op1)))) { 429abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Value *YS = // (Y << C) 430abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Builder->CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName()); 431abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner // (X + (Y << C)) 432abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), YS, V1, 433abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Op0BO->getOperand(1)->getName()); 434dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint32_t Op1Val = COp1->getLimitedValue(TypeBits); 435dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 436dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines APInt Bits = APInt::getHighBitsSet(TypeBits, TypeBits - Op1Val); 437dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *Mask = ConstantInt::get(I.getContext(), Bits); 438dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (VectorType *VT = dyn_cast<VectorType>(X->getType())) 439dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Mask = ConstantVector::getSplat(VT->getNumElements(), Mask); 440dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return BinaryOperator::CreateAnd(X, Mask); 4419cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 4420fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 443abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner // Turn (Y + ((X >> C) & CC)) << C -> ((X & (CC << C)) + (Y << C)) 444abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Value *Op0BOOp1 = Op0BO->getOperand(1); 445abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner if (isLeftShift && Op0BOOp1->hasOneUse() && 4460fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak match(Op0BOOp1, 44704349516b28bdf0b218973e1d48f33e98f775577Jakub Staszak m_And(m_OneUse(m_Shr(m_Value(V1), m_Specific(Op1))), 44804349516b28bdf0b218973e1d48f33e98f775577Jakub Staszak m_ConstantInt(CC)))) { 449abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Value *YS = // (Y << C) 450abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Builder->CreateShl(Op0BO->getOperand(0), Op1, 451abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Op0BO->getName()); 452abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner // X & (CC << C) 453abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1), 454abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner V1->getName()+".mask"); 455abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM); 456abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner } 457abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner } 4580fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 459abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner // FALL THROUGH. 460abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner case Instruction::Sub: { 461abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C) 462abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 463abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner match(Op0BO->getOperand(0), m_Shr(m_Value(V1), 464abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner m_Specific(Op1)))) { 465abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Value *YS = // (Y << C) 466abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 467abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner // (X + (Y << C)) 468abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), V1, YS, 469abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Op0BO->getOperand(0)->getName()); 470dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint32_t Op1Val = COp1->getLimitedValue(TypeBits); 471dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 472dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines APInt Bits = APInt::getHighBitsSet(TypeBits, TypeBits - Op1Val); 473dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *Mask = ConstantInt::get(I.getContext(), Bits); 474dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (VectorType *VT = dyn_cast<VectorType>(X->getType())) 475dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Mask = ConstantVector::getSplat(VT->getNumElements(), Mask); 476dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return BinaryOperator::CreateAnd(X, Mask); 477abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner } 4780fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 479abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner // Turn (((X >> C)&CC) + Y) << C -> (X + (Y << C)) & (CC << C) 480abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() && 481abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner match(Op0BO->getOperand(0), 48204349516b28bdf0b218973e1d48f33e98f775577Jakub Staszak m_And(m_OneUse(m_Shr(m_Value(V1), m_Value(V2))), 48304349516b28bdf0b218973e1d48f33e98f775577Jakub Staszak m_ConstantInt(CC))) && V2 == Op1) { 484abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Value *YS = // (Y << C) 485abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName()); 486abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner // X & (CC << C) 487abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1), 488abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner V1->getName()+".mask"); 4890fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 490abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS); 4919cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 4920fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 493abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner break; 494abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner } 4959cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 4960fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 4970fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 49837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // If the operand is a bitwise operator with a constant RHS, and the 4999cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // shift is the only use, we can pull it out of the shift. 5009cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) { 5019cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner bool isValid = true; // Valid only for And, Or, Xor 5029cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner bool highBitSet = false; // Transform if high bit of constant set? 5030fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 5049cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner switch (Op0BO->getOpcode()) { 505abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner default: isValid = false; break; // Do not perform transform! 506abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner case Instruction::Add: 507abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner isValid = isLeftShift; 508abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner break; 509abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner case Instruction::Or: 510abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner case Instruction::Xor: 511abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner highBitSet = false; 512abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner break; 513abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner case Instruction::And: 514abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner highBitSet = true; 515abff82d99e8251774dfdc31f6c9ca0e10a146f5aChris Lattner break; 5169cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 5170fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 5189cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // If this is a signed shift right, and the high bit is modified 5199cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // by the logical operation, do not perform the transformation. 5209cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // The highBitSet boolean indicates the value of the high bit of 5219cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // the constant which would cause it to be modified for this 5229cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // operation. 5239cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // 5249cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (isValid && I.getOpcode() == Instruction::AShr) 5259cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner isValid = Op0C->getValue()[TypeBits-1] == highBitSet; 5260fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 5279cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (isValid) { 5289cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, Op1); 5290fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 5309cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner Value *NewShift = 5319cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner Builder->CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1); 5329cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner NewShift->takeName(Op0BO); 5330fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 5349cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, 5359cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner NewRHS); 5369cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 5379cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 5389cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 5399cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 5400fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 5419cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // Find out if this is a shift of a shift by a constant. 5429cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner BinaryOperator *ShiftOp = dyn_cast<BinaryOperator>(Op0); 5439cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (ShiftOp && !ShiftOp->isShift()) 544dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ShiftOp = nullptr; 5450fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 5469cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (ShiftOp && isa<ConstantInt>(ShiftOp->getOperand(1))) { 54772847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen 54872847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // This is a constant shift of a constant shift. Be careful about hiding 54972847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // shl instructions behind bit masks. They are used to represent multiplies 55072847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // by a constant, and it is important that simple arithmetic expressions 55172847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // are still recognizable by scalar evolution. 55272847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // 55372847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // The transforms applied to shl are very similar to the transforms applied 55472847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // to mul by constant. We can be more aggressive about optimizing right 55572847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // shifts. 55672847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // 55772847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // Combinations of right and left shifts will still be optimized in 55872847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // DAGCombine where scalar evolution no longer applies. 55972847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen 5609cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner ConstantInt *ShiftAmt1C = cast<ConstantInt>(ShiftOp->getOperand(1)); 5619cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner uint32_t ShiftAmt1 = ShiftAmt1C->getLimitedValue(TypeBits); 562dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint32_t ShiftAmt2 = COp1->getLimitedValue(TypeBits); 5639cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner assert(ShiftAmt2 != 0 && "Should have been simplified earlier"); 564dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (ShiftAmt1 == 0) return nullptr; // Will be simplified in the future. 5659cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner Value *X = ShiftOp->getOperand(0); 5660fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 567db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner IntegerType *Ty = cast<IntegerType>(I.getType()); 5680fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 5699cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // Check for (X << c1) << c2 and (X >> c1) >> c2 5709cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (I.getOpcode() == ShiftOp->getOpcode()) { 57157ed0948b87206beadce58c406f95dda345fe62cNick Lewycky uint32_t AmtSum = ShiftAmt1+ShiftAmt2; // Fold into one big shift. 5729cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // If this is oversized composite shift, then unsigned shifts get 0, ashr 5739cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // saturates. 5749cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (AmtSum >= TypeBits) { 5759cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (I.getOpcode() != Instruction::AShr) 5769cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 5779cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner AmtSum = TypeBits-1; // Saturate to 31 for i32 ashr. 5789cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 5790fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 5809cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return BinaryOperator::Create(I.getOpcode(), X, 5819cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner ConstantInt::get(Ty, AmtSum)); 5829cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 5830fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 5849cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (ShiftAmt1 == ShiftAmt2) { 5859cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // If we have ((X << C) >>u C), turn this into X & (-1 >>u C). 5862d0822a937a3b4d1c5096471a2af02ead2090b6eChris Lattner if (I.getOpcode() == Instruction::LShr && 5872d0822a937a3b4d1c5096471a2af02ead2090b6eChris Lattner ShiftOp->getOpcode() == Instruction::Shl) { 5889cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt1)); 5899cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return BinaryOperator::CreateAnd(X, 5909cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner ConstantInt::get(I.getContext(), Mask)); 5919cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 5929cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } else if (ShiftAmt1 < ShiftAmt2) { 5939cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner uint32_t ShiftDiff = ShiftAmt2-ShiftAmt1; 59472847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen 59572847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // (X >>?,exact C1) << C2 --> X << (C2-C1) 59672847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // The inexact version is deferred to DAGCombine so we don't hide shl 59772847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // behind a bit mask. 5982d0822a937a3b4d1c5096471a2af02ead2090b6eChris Lattner if (I.getOpcode() == Instruction::Shl && 59972847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen ShiftOp->getOpcode() != Instruction::Shl && 60072847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen ShiftOp->isExact()) { 6019cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner assert(ShiftOp->getOpcode() == Instruction::LShr || 6029cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner ShiftOp->getOpcode() == Instruction::AShr); 603148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff); 60472847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen BinaryOperator *NewShl = BinaryOperator::Create(Instruction::Shl, 60572847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen X, ShiftDiffCst); 60672847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen NewShl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 60772847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen NewShl->setHasNoSignedWrap(I.hasNoSignedWrap()); 60872847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen return NewShl; 6099cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 61072847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen 6119cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // (X << C1) >>u C2 --> X >>u (C2-C1) & (-1 >> C2) 6122d0822a937a3b4d1c5096471a2af02ead2090b6eChris Lattner if (I.getOpcode() == Instruction::LShr && 6132d0822a937a3b4d1c5096471a2af02ead2090b6eChris Lattner ShiftOp->getOpcode() == Instruction::Shl) { 614148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff); 615148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky // (X <<nuw C1) >>u C2 --> X >>u (C2-C1) 616148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky if (ShiftOp->hasNoUnsignedWrap()) { 617148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky BinaryOperator *NewLShr = BinaryOperator::Create(Instruction::LShr, 618148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky X, ShiftDiffCst); 619148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky NewLShr->setIsExact(I.isExact()); 620148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky return NewLShr; 621148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky } 622148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky Value *Shift = Builder->CreateLShr(X, ShiftDiffCst); 6230fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 6249cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 6259cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return BinaryOperator::CreateAnd(Shift, 6269cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner ConstantInt::get(I.getContext(),Mask)); 6279cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 628148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky 629148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in. However, 630148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits. 631148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky if (I.getOpcode() == Instruction::AShr && 632148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky ShiftOp->getOpcode() == Instruction::Shl) { 633148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky if (ShiftOp->hasNoSignedWrap()) { 634148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky // (X <<nsw C1) >>s C2 --> X >>s (C2-C1) 635148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff); 636148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky BinaryOperator *NewAShr = BinaryOperator::Create(Instruction::AShr, 637148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky X, ShiftDiffCst); 638148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky NewAShr->setIsExact(I.isExact()); 639148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky return NewAShr; 640148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky } 641148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky } 6429cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } else { 6439cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner assert(ShiftAmt2 < ShiftAmt1); 6449cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner uint32_t ShiftDiff = ShiftAmt1-ShiftAmt2; 6459cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 64672847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // (X >>?exact C1) << C2 --> X >>?exact (C1-C2) 64772847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // The inexact version is deferred to DAGCombine so we don't hide shl 64872847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen // behind a bit mask. 6492d0822a937a3b4d1c5096471a2af02ead2090b6eChris Lattner if (I.getOpcode() == Instruction::Shl && 65072847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen ShiftOp->getOpcode() != Instruction::Shl && 65172847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen ShiftOp->isExact()) { 65257ed0948b87206beadce58c406f95dda345fe62cNick Lewycky ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff); 65372847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen BinaryOperator *NewShr = BinaryOperator::Create(ShiftOp->getOpcode(), 65472847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen X, ShiftDiffCst); 65572847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen NewShr->setIsExact(true); 65672847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen return NewShr; 6579cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 65872847f3057a7d82be087d3aad7d13b7719409a32Jakob Stoklund Olesen 6599cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // (X << C1) >>u C2 --> X << (C1-C2) & (-1 >> C2) 6602d0822a937a3b4d1c5096471a2af02ead2090b6eChris Lattner if (I.getOpcode() == Instruction::LShr && 6612d0822a937a3b4d1c5096471a2af02ead2090b6eChris Lattner ShiftOp->getOpcode() == Instruction::Shl) { 662148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff); 663148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky if (ShiftOp->hasNoUnsignedWrap()) { 664148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky // (X <<nuw C1) >>u C2 --> X <<nuw (C1-C2) 665148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky BinaryOperator *NewShl = BinaryOperator::Create(Instruction::Shl, 666148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky X, ShiftDiffCst); 667148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky NewShl->setHasNoUnsignedWrap(true); 668148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky return NewShl; 669148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky } 670148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky Value *Shift = Builder->CreateShl(X, ShiftDiffCst); 6710fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 6729cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner APInt Mask(APInt::getLowBitsSet(TypeBits, TypeBits - ShiftAmt2)); 6739cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return BinaryOperator::CreateAnd(Shift, 6749cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner ConstantInt::get(I.getContext(),Mask)); 6759cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 6760fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 677148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in. However, 678148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits. 679148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky if (I.getOpcode() == Instruction::AShr && 680148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky ShiftOp->getOpcode() == Instruction::Shl) { 681148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky if (ShiftOp->hasNoSignedWrap()) { 682148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky // (X <<nsw C1) >>s C2 --> X <<nsw (C1-C2) 683148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky ConstantInt *ShiftDiffCst = ConstantInt::get(Ty, ShiftDiff); 684148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky BinaryOperator *NewShl = BinaryOperator::Create(Instruction::Shl, 685148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky X, ShiftDiffCst); 686148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky NewShl->setHasNoSignedWrap(true); 687148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky return NewShl; 688148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky } 689148fd55ef3b47e224539eac7342c936bbf138ed5Nick Lewycky } 6909cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 6919cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner } 692dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 6939cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner} 6949cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 6959cdd5f3fe3e857505012554d678fcd80f3f74617Chris LattnerInstruction *InstCombiner::visitShl(BinaryOperator &I) { 696dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 697dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 698dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 699ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = 700ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SimplifyShlInst(I.getOperand(0), I.getOperand(1), I.hasNoSignedWrap(), 701ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines I.hasNoUnsignedWrap(), DL, TLI, DT, AC)) 702c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return ReplaceInstUsesWith(I, V); 7030fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 7047a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (Instruction *V = commonShiftTransforms(I)) 7057a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return V; 7060fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 7077a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (ConstantInt *Op1C = dyn_cast<ConstantInt>(I.getOperand(1))) { 7087a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner unsigned ShAmt = Op1C->getZExtValue(); 7090fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 7107a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // If the shifted-out value is known-zero, then this is a NUW shift. 7110fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak if (!I.hasNoUnsignedWrap() && 7127a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner MaskedValueIsZero(I.getOperand(0), 71337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt::getHighBitsSet(Op1C->getBitWidth(), ShAmt), 71437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 0, &I)) { 7157a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner I.setHasNoUnsignedWrap(); 7167a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return &I; 7177a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 7180fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 7197a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // If the shifted out value is all signbits, this is a NSW shift. 7207a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (!I.hasNoSignedWrap() && 72137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ComputeNumSignBits(I.getOperand(0), 0, &I) > ShAmt) { 7227a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner I.setHasNoSignedWrap(); 7237a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return &I; 7247a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 7257a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 726c2e31c1461f96e3d8325e58ef396a865adf7b302Benjamin Kramer 727322480610939bca07506750571cb60f1497ec9a4Benjamin Kramer // (C1 << A) << C2 -> (C1 << C2) << A 728c2e31c1461f96e3d8325e58ef396a865adf7b302Benjamin Kramer Constant *C1, *C2; 729c2e31c1461f96e3d8325e58ef396a865adf7b302Benjamin Kramer Value *A; 730c2e31c1461f96e3d8325e58ef396a865adf7b302Benjamin Kramer if (match(I.getOperand(0), m_OneUse(m_Shl(m_Constant(C1), m_Value(A)))) && 731c2e31c1461f96e3d8325e58ef396a865adf7b302Benjamin Kramer match(I.getOperand(1), m_Constant(C2))) 732c2e31c1461f96e3d8325e58ef396a865adf7b302Benjamin Kramer return BinaryOperator::CreateShl(ConstantExpr::getShl(C1, C2), A); 733c2e31c1461f96e3d8325e58ef396a865adf7b302Benjamin Kramer 734dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 7359cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner} 7369cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 7379cdd5f3fe3e857505012554d678fcd80f3f74617Chris LattnerInstruction *InstCombiner::visitLShr(BinaryOperator &I) { 738dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 739dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 740dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 741ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = SimplifyLShrInst(I.getOperand(0), I.getOperand(1), I.isExact(), 742ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DL, TLI, DT, AC)) 743c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return ReplaceInstUsesWith(I, V); 744c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 745818ff34bc0841edda10951b7b043076b6e7159efChris Lattner if (Instruction *R = commonShiftTransforms(I)) 746818ff34bc0841edda10951b7b043076b6e7159efChris Lattner return R; 7470fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 748818ff34bc0841edda10951b7b043076b6e7159efChris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 7490fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 7507a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 7517a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner unsigned ShAmt = Op1C->getZExtValue(); 7527a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner 753818ff34bc0841edda10951b7b043076b6e7159efChris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) { 754f7d0d163c5962a51cf9eb32db093b5d1fd8114faChris Lattner unsigned BitWidth = Op0->getType()->getScalarSizeInBits(); 755818ff34bc0841edda10951b7b043076b6e7159efChris Lattner // ctlz.i32(x)>>5 --> zext(x == 0) 756818ff34bc0841edda10951b7b043076b6e7159efChris Lattner // cttz.i32(x)>>5 --> zext(x == 0) 757818ff34bc0841edda10951b7b043076b6e7159efChris Lattner // ctpop.i32(x)>>5 --> zext(x == -1) 758818ff34bc0841edda10951b7b043076b6e7159efChris Lattner if ((II->getIntrinsicID() == Intrinsic::ctlz || 759818ff34bc0841edda10951b7b043076b6e7159efChris Lattner II->getIntrinsicID() == Intrinsic::cttz || 760818ff34bc0841edda10951b7b043076b6e7159efChris Lattner II->getIntrinsicID() == Intrinsic::ctpop) && 7617a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == ShAmt) { 762818ff34bc0841edda10951b7b043076b6e7159efChris Lattner bool isCtPop = II->getIntrinsicID() == Intrinsic::ctpop; 763f7d0d163c5962a51cf9eb32db093b5d1fd8114faChris Lattner Constant *RHS = ConstantInt::getSigned(Op0->getType(), isCtPop ? -1:0); 764de9f5452d3ae894bb7fdd455cec5af50e2560aa5Gabor Greif Value *Cmp = Builder->CreateICmpEQ(II->getArgOperand(0), RHS); 765818ff34bc0841edda10951b7b043076b6e7159efChris Lattner return new ZExtInst(Cmp, II->getType()); 766818ff34bc0841edda10951b7b043076b6e7159efChris Lattner } 767818ff34bc0841edda10951b7b043076b6e7159efChris Lattner } 7680fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 7697a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // If the shifted-out value is known-zero, then this is an exact shift. 7700fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak if (!I.isExact() && 77137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines MaskedValueIsZero(Op0, APInt::getLowBitsSet(Op1C->getBitWidth(), ShAmt), 77237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 0, &I)){ 7737a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner I.setIsExact(); 7747a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return &I; 7750fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak } 7767a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 7770fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 778dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 7799cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner} 7809cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner 7819cdd5f3fe3e857505012554d678fcd80f3f74617Chris LattnerInstruction *InstCombiner::visitAShr(BinaryOperator &I) { 782dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 783dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 784dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 785ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = SimplifyAShrInst(I.getOperand(0), I.getOperand(1), I.isExact(), 786ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DL, TLI, DT, AC)) 787c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return ReplaceInstUsesWith(I, V); 788c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 7899cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (Instruction *R = commonShiftTransforms(I)) 7909cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner return R; 7910fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 792a85732fa3bf17dd48b897f76533142ac0f2ec140Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 793c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 794a85732fa3bf17dd48b897f76533142ac0f2ec140Chris Lattner if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 7957a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner unsigned ShAmt = Op1C->getZExtValue(); 7960fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 797a85732fa3bf17dd48b897f76533142ac0f2ec140Chris Lattner // If the input is a SHL by the same constant (ashr (shl X, C), C), then we 798cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner // have a sign-extend idiom. 799a85732fa3bf17dd48b897f76533142ac0f2ec140Chris Lattner Value *X; 800cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1)))) { 801cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner // If the input is an extension from the shifted amount value, e.g. 802cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner // %x = zext i8 %A to i32 803cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner // %y = shl i32 %x, 24 804cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner // %z = ashr %y, 24 805cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner // then turn this into "z = sext i8 A to i32". 806cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner if (ZExtInst *ZI = dyn_cast<ZExtInst>(X)) { 807cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner uint32_t SrcBits = ZI->getOperand(0)->getType()->getScalarSizeInBits(); 808cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner uint32_t DestBits = ZI->getType()->getScalarSizeInBits(); 809cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner if (Op1C->getZExtValue() == DestBits-SrcBits) 810cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner return new SExtInst(ZI->getOperand(0), ZI->getType()); 811cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner } 812cd5adbbc0cef6ddf20c476ad2049104426198e15Chris Lattner } 8137a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner 8147a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // If the shifted-out value is known-zero, then this is an exact shift. 8150fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak if (!I.isExact() && 81637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines MaskedValueIsZero(Op0,APInt::getLowBitsSet(Op1C->getBitWidth(),ShAmt), 81737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 0, &I)){ 8187a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner I.setIsExact(); 8197a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return &I; 8207a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 8210fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak } 8220fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 8239cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner // See if we can turn a signed shr into an unsigned shr. 8249cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner if (MaskedValueIsZero(Op0, 82537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt::getSignBit(I.getType()->getScalarSizeInBits()), 82637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 0, &I)) 827a85732fa3bf17dd48b897f76533142ac0f2ec140Chris Lattner return BinaryOperator::CreateLShr(Op0, Op1); 8280fb7687b61888c1198310a43069c0fa9c7dabc38Jakub Staszak 829dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 8309cdd5f3fe3e857505012554d678fcd80f3f74617Chris Lattner} 831