1d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner//===- InstCombineMulDivRem.cpp -------------------------------------------===// 2d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner// 3d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner// The LLVM Compiler Infrastructure 4d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner// 5d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner// This file is distributed under the University of Illinois Open Source 6d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner// License. See LICENSE.TXT for details. 7d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner// 8d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner//===----------------------------------------------------------------------===// 9d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner// 10d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner// This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv, 11d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner// srem, urem, frem. 12d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner// 13d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner//===----------------------------------------------------------------------===// 14d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 15ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "InstCombineInternal.h" 1682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands#include "llvm/Analysis/InstructionSimplify.h" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/PatternMatch.h" 19d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattnerusing namespace llvm; 20d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattnerusing namespace PatternMatch; 21d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "instcombine" 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 241add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner 251add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner/// simplifyValueKnownNonZero - The specific integer value is used in a context 261add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner/// where it is known to be non-zero. If this allows us to simplify the 271add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner/// computation, do so and return the new operand, otherwise return null. 2837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstatic Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC, 294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Instruction &CxtI) { 301add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner // If V has multiple uses, then we would have to do more analysis to determine 311add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner // if this is safe. For example, the use could be in dynamically unreached 321add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner // code. 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!V->hasOneUse()) return nullptr; 3403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 35613f1a3994ef6f009c93264f6708830249130896Chris Lattner bool MadeChange = false; 36613f1a3994ef6f009c93264f6708830249130896Chris Lattner 37613f1a3994ef6f009c93264f6708830249130896Chris Lattner // ((1 << A) >>u B) --> (1 << (A-B)) 38613f1a3994ef6f009c93264f6708830249130896Chris Lattner // Because V cannot be zero, we know that B is less than A. 3937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Value *A = nullptr, *B = nullptr, *One = nullptr; 4037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) && 4137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines match(One, m_One())) { 42a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer A = IC.Builder->CreateSub(A, B); 4337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return IC.Builder->CreateShl(One, A); 44613f1a3994ef6f009c93264f6708830249130896Chris Lattner } 4503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 4605cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it 4705cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner // inexact. Similarly for <<. 4805cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner if (BinaryOperator *I = dyn_cast<BinaryOperator>(V)) 49ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I->isLogicalShift() && 504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar isKnownToBeAPowerOfTwo(I->getOperand(0), IC.getDataLayout(), false, 0, 514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar IC.getAssumptionCache(), &CxtI, 52ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines IC.getDominatorTree())) { 53613f1a3994ef6f009c93264f6708830249130896Chris Lattner // We know that this is an exact/nuw shift and that the input is a 54613f1a3994ef6f009c93264f6708830249130896Chris Lattner // non-zero context as well. 5537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) { 56613f1a3994ef6f009c93264f6708830249130896Chris Lattner I->setOperand(0, V2); 57613f1a3994ef6f009c93264f6708830249130896Chris Lattner MadeChange = true; 58613f1a3994ef6f009c93264f6708830249130896Chris Lattner } 5903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 6005cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner if (I->getOpcode() == Instruction::LShr && !I->isExact()) { 6105cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner I->setIsExact(); 62613f1a3994ef6f009c93264f6708830249130896Chris Lattner MadeChange = true; 6305cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner } 6403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 6505cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) { 6605cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner I->setHasNoUnsignedWrap(); 67613f1a3994ef6f009c93264f6708830249130896Chris Lattner MadeChange = true; 6805cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner } 6905cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner } 70613f1a3994ef6f009c93264f6708830249130896Chris Lattner 716c9b8d3d411b0ee65263dc41d2b953fe118cf31eChris Lattner // TODO: Lots more we could do here: 726c9b8d3d411b0ee65263dc41d2b953fe118cf31eChris Lattner // If V is a phi node, we can call this on each of its operands. 736c9b8d3d411b0ee65263dc41d2b953fe118cf31eChris Lattner // "select cond, X, 0" can simplify to "X". 7403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return MadeChange ? V : nullptr; 761add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner} 771add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner 781add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner 79d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// MultiplyOverflows - True if the multiply can not be expressed in an int 80d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// this size. 8137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstatic bool MultiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product, 8237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool IsSigned) { 8337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool Overflow; 8437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (IsSigned) 8537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Product = C1.smul_ov(C2, Overflow); 8637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines else 8737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Product = C1.umul_ov(C2, Overflow); 8837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 8937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Overflow; 9037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 9103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 9237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// \brief True if C2 is a multiple of C1. Quotient contains C2/C1. 9337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstatic bool IsMultiple(const APInt &C1, const APInt &C2, APInt &Quotient, 9437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool IsSigned) { 9537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(C1.getBitWidth() == C2.getBitWidth() && 9637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines "Inconsistent width of constants!"); 9703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 9837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt Remainder(C1.getBitWidth(), /*Val=*/0ULL, IsSigned); 9937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (IsSigned) 10037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt::sdivrem(C1, C2, Quotient, Remainder); 10137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines else 10237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt::udivrem(C1, C2, Quotient, Remainder); 10303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 10437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Remainder.isMinValue(); 105d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 106d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1074f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola/// \brief A helper routine of InstCombiner::visitMul(). 1084f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola/// 1094f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola/// If C is a vector of known powers of 2, then this function returns 1104f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola/// a new vector obtained from C replacing each element with its logBase2. 1114f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola/// Return a null pointer otherwise. 1124f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindolastatic Constant *getLogBase2Vector(ConstantDataVector *CV) { 1134f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola const APInt *IVal; 1144f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola SmallVector<Constant *, 4> Elts; 1154f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola 1164f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) { 1174f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola Constant *Elt = CV->getElementAsConstant(I); 1184f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2()) 119dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1204f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2())); 1214f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola } 1224f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola 1234f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola return ConstantVector::get(Elts); 1244f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola} 1254f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola 126ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// \brief Return true if we can prove that: 127ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// (mul LHS, RHS) === (mul nsw LHS, RHS) 128ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesbool InstCombiner::WillNotOverflowSignedMul(Value *LHS, Value *RHS, 1294c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar Instruction &CxtI) { 130ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Multiplying n * m significant bits yields a result of n + m significant 131ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // bits. If the total number of significant bits does not exceed the 132ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // result bit width (minus 1), there is no overflow. 133ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // This means if we have enough leading sign bits in the operands 134ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // we can guarantee that the result does not overflow. 135ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Ref: "Hacker's Delight" by Henry Warren 136ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines unsigned BitWidth = LHS->getType()->getScalarSizeInBits(); 137ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 138ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Note that underestimating the number of sign bits gives a more 139ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // conservative answer. 1404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar unsigned SignBits = 1414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ComputeNumSignBits(LHS, 0, &CxtI) + ComputeNumSignBits(RHS, 0, &CxtI); 142ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 143ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // First handle the easy case: if we have enough sign bits there's 144ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // definitely no overflow. 145ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (SignBits > BitWidth + 1) 146ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return true; 147ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 148ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // There are two ambiguous cases where there can be no overflow: 149ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // SignBits == BitWidth + 1 and 150ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // SignBits == BitWidth 151ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The second case is difficult to check, therefore we only handle the 152ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // first case. 153ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (SignBits == BitWidth + 1) { 154ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // It overflows only when both arguments are negative and the true 155ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // product is exactly the minimum negative number. 156ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000 157ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // For simplicity we just check if at least one side is not negative. 158ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool LHSNonNegative, LHSNegative; 159ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool RHSNonNegative, RHSNegative; 1604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ComputeSignBit(LHS, LHSNonNegative, LHSNegative, /*Depth=*/0, &CxtI); 1614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ComputeSignBit(RHS, RHSNonNegative, RHSNegative, /*Depth=*/0, &CxtI); 162ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (LHSNonNegative || RHSNonNegative) 163ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return true; 164ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 165ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return false; 166ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} 167ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 168d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitMul(BinaryOperator &I) { 169096aa79276b8527a3cbbb3691e40e729dea09523Duncan Sands bool Changed = SimplifyAssociativeOrCommutative(I); 170d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 171d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 172dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 174dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 175ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = SimplifyMulInst(Op0, Op1, DL, TLI, DT, AC)) 17682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return ReplaceInstUsesWith(I, V); 177d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 17837bf92b5238434b00fde79347ba5336e7554e562Duncan Sands if (Value *V = SimplifyUsingDistributiveLaws(I)) 17937bf92b5238434b00fde79347ba5336e7554e562Duncan Sands return ReplaceInstUsesWith(I, V); 18037bf92b5238434b00fde79347ba5336e7554e562Duncan Sands 181ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // X * -1 == 0 - X 182ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (match(Op1, m_AllOnes())) { 183ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BinaryOperator *BO = BinaryOperator::CreateNeg(Op0, I.getName()); 184ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I.hasNoSignedWrap()) 185ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO->setHasNoSignedWrap(); 186ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return BO; 187ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 18803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1894f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola // Also allow combining multiply instructions on vectors. 1904f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola { 1914f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola Value *NewOp; 1924f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola Constant *C1, *C2; 1934f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola const APInt *IVal; 1944f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)), 1954f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola m_Constant(C1))) && 196ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines match(C1, m_APInt(IVal))) { 197ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // ((X << C2)*C1) == (X * (C1 << C2)) 198ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Constant *Shl = ConstantExpr::getShl(C1, C2); 199ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0)); 200ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl); 201ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap()) 202ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO->setHasNoUnsignedWrap(); 203ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() && 204ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Shl->isNotMinSignedValue()) 205ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO->setHasNoSignedWrap(); 206ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return BO; 207ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 2084f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola 2094f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) { 210dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *NewCst = nullptr; 2114f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2()) 2124f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola // Replace X*(2^C) with X << C, where C is either a scalar or a splat. 2134f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2()); 2144f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1)) 2154f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola // Replace X*(2^C) with X << C, where C is a vector of known 2164f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola // constant powers of 2. 2174f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola NewCst = getLogBase2Vector(CV); 2184f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola 2194f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola if (NewCst) { 2204f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst); 22137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 22237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (I.hasNoUnsignedWrap()) 22337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Shl->setHasNoUnsignedWrap(); 224ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I.hasNoSignedWrap() && NewCst->isNotMinSignedValue()) 225ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Shl->setHasNoSignedWrap(); 22637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 2274f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola return Shl; 2284f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola } 229d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 2304f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola } 23103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 2324f3d7eea048c5d665436b8bd7a59739bcba5ec0bRafael Espindola if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 233f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n 234f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n 235f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings // The "* (2**n)" thus becomes a potential shifting opportunity. 236acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings { 237acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings const APInt & Val = CI->getValue(); 238acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings const APInt &PosVal = Val.abs(); 239acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings if (Val.isNegative() && PosVal.isPowerOf2()) { 240dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *X = nullptr, *Y = nullptr; 241f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings if (Op0->hasOneUse()) { 242f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings ConstantInt *C1; 243dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *Sub = nullptr; 244f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings if (match(Op0, m_Sub(m_Value(Y), m_Value(X)))) 245f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings Sub = Builder->CreateSub(X, Y, "suba"); 246f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1)))) 247f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings Sub = Builder->CreateSub(Builder->CreateNeg(C1), Y, "subc"); 248f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings if (Sub) 249f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings return 250f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings BinaryOperator::CreateMul(Sub, 251f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings ConstantInt::get(Y->getType(), PosVal)); 252acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings } 253acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings } 254acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings } 2557a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 25603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 2577a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // Simplify mul instructions with a constant RHS. 25803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach if (isa<Constant>(Op1)) { 259d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Try to fold constant mul into select arguments. 260d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 261d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 262d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return R; 263d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 264d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (isa<PHINode>(Op0)) 265d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 266d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return NV; 26736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Canonicalize (X+C1)*CI -> X*CI+C1*CI. 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines { 27036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *X; 27136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C1; 27236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) { 273c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines Value *Mul = Builder->CreateMul(C1, Op1); 274c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // Only go forward with the transform if C1*CI simplifies to a tidier 275c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // constant. 276c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (!match(Mul, m_Mul(m_Value(), m_Value()))) 277c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return BinaryOperator::CreateAdd(Builder->CreateMul(X, Op1), Mul); 27836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 27936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 280d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 281d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 282ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *Op0v = dyn_castNegVal(Op0)) { // -X * -Y = X*Y 283ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *Op1v = dyn_castNegVal(Op1)) { 284ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BinaryOperator *BO = BinaryOperator::CreateMul(Op0v, Op1v); 285ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I.hasNoSignedWrap() && 286ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines match(Op0, m_NSWSub(m_Value(), m_Value())) && 287ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines match(Op1, m_NSWSub(m_Value(), m_Value()))) 288ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO->setHasNoSignedWrap(); 289ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return BO; 290ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 291ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 292d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 293d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // (X / Y) * Y = X - (X % Y) 294d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // (X / Y) * -Y = (X % Y) - X 295d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner { 296d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op1C = Op1; 297d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0); 298d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (!BO || 29903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach (BO->getOpcode() != Instruction::UDiv && 300d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BO->getOpcode() != Instruction::SDiv)) { 301d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Op1C = Op0; 302d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BO = dyn_cast<BinaryOperator>(Op1); 303d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 304d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Neg = dyn_castNegVal(Op1C); 305d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (BO && BO->hasOneUse() && 306d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) && 307d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner (BO->getOpcode() == Instruction::UDiv || 308d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BO->getOpcode() == Instruction::SDiv)) { 309d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1); 310d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 31135bda8914c0d1c02a6f90f42e7810c83150737e1Chris Lattner // If the division is exact, X % Y is zero, so we end up with X or -X. 31235bda8914c0d1c02a6f90f42e7810c83150737e1Chris Lattner if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO)) 313d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SDiv->isExact()) { 314d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Op1BO == Op1C) 315d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return ReplaceInstUsesWith(I, Op0BO); 316d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateNeg(Op0BO); 317d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 318d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 319d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Rem; 320d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (BO->getOpcode() == Instruction::UDiv) 321d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Rem = Builder->CreateURem(Op0BO, Op1BO); 322d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner else 323d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Rem = Builder->CreateSRem(Op0BO, Op1BO); 324d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Rem->takeName(BO); 325d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 326d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Op1BO == Op1C) 327d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateSub(Op0BO, Rem); 328d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateSub(Rem, Op0BO); 329d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 330d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 331d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 332d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner /// i1 mul -> i1 and. 33336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I.getType()->getScalarType()->isIntegerTy(1)) 334d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateAnd(Op0, Op1); 335d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 336d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X*(1 << Y) --> X << Y 337d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // (1 << Y)*X --> X << Y 338d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner { 339d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Y; 340ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BinaryOperator *BO = nullptr; 341ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool ShlNSW = false; 342ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (match(Op0, m_Shl(m_One(), m_Value(Y)))) { 343ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO = BinaryOperator::CreateShl(Op1, Y); 344ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap(); 345ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) { 346ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO = BinaryOperator::CreateShl(Op0, Y); 347ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap(); 348ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 349ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (BO) { 350ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I.hasNoUnsignedWrap()) 351ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO->setHasNoUnsignedWrap(); 352ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I.hasNoSignedWrap() && ShlNSW) 353ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO->setHasNoSignedWrap(); 354ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return BO; 355ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 356d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 35703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 358d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If one of the operands of the multiply is a cast from a boolean value, then 359d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // we know the bool is either zero or one, so this is a 'masking' multiply. 360d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X * Y (where Y is 0 or 1) -> X & (0-Y) 3611df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (!I.getType()->isVectorTy()) { 362d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // -2 is "-1 << 1" so it is all bits set except the low one. 363d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true); 36403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 365dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *BoolCast = nullptr, *OtherOp = nullptr; 36637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (MaskedValueIsZero(Op0, Negative2, 0, &I)) 367d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BoolCast = Op0, OtherOp = Op1; 36837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines else if (MaskedValueIsZero(Op1, Negative2, 0, &I)) 369d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BoolCast = Op1, OtherOp = Op0; 370d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 371d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (BoolCast) { 372d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()), 373a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer BoolCast); 374d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateAnd(V, OtherOp); 375d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 376d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 377d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 3784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (!I.hasNoSignedWrap() && WillNotOverflowSignedMul(Op0, Op1, I)) { 379ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Changed = true; 380ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines I.setHasNoSignedWrap(true); 381ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 382ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 383ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!I.hasNoUnsignedWrap() && 384ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines computeOverflowForUnsignedMul(Op0, Op1, &I) == 385ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OverflowResult::NeverOverflows) { 386ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Changed = true; 387ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines I.setHasNoUnsignedWrap(true); 388ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 389ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 390dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Changed ? &I : nullptr; 391d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 392d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 39337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// Detect pattern log2(Y * 0.5) with corresponding fast math flags. 394c2a08d28eb1199d67dff5b66061cf7f6a25d2527Pedro Artigasstatic void detectLog2OfHalf(Value *&Op, Value *&Y, IntrinsicInst *&Log2) { 39537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!Op->hasOneUse()) 39637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 39737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 39837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op); 39937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!II) 40037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 40137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (II->getIntrinsicID() != Intrinsic::log2 || !II->hasUnsafeAlgebra()) 40237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 40337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Log2 = II; 40437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 40537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Value *OpLog2Of = II->getArgOperand(0); 40637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!OpLog2Of->hasOneUse()) 40737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 40837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 40937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Instruction *I = dyn_cast<Instruction>(OpLog2Of); 41037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!I) 41137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 41237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (I->getOpcode() != Instruction::FMul || !I->hasUnsafeAlgebra()) 41337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 41437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 41537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (match(I->getOperand(0), m_SpecificFP(0.5))) 41637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Y = I->getOperand(1); 41737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines else if (match(I->getOperand(1), m_SpecificFP(0.5))) 41837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Y = I->getOperand(0); 41903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach} 420c2a08d28eb1199d67dff5b66061cf7f6a25d2527Pedro Artigas 42136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool isFiniteNonZeroFp(Constant *C) { 42236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (C->getType()->isVectorTy()) { 42336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; 42436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++I) { 4254c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getAggregateElement(I)); 42636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!CFP || !CFP->getValueAPF().isFiniteNonZero()) 42736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 42836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 42936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 43036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 43136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 43236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return isa<ConstantFP>(C) && 43336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cast<ConstantFP>(C)->getValueAPF().isFiniteNonZero(); 43436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 43536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 43636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool isNormalFp(Constant *C) { 43736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (C->getType()->isVectorTy()) { 43836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; 43936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++I) { 4404c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getAggregateElement(I)); 44136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!CFP || !CFP->getValueAPF().isNormal()) 44236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 44336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 44436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 44536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 44636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 44736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return isa<ConstantFP>(C) && cast<ConstantFP>(C)->getValueAPF().isNormal(); 44836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 44936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 450d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang/// Helper function of InstCombiner::visitFMul(BinaryOperator(). It returns 451d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang/// true iff the given value is FMul or FDiv with one and only one operand 452d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang/// being a normal constant (i.e. not Zero/NaN/Infinity). 453d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yangstatic bool isFMulOrFDivWithConstant(Value *V) { 454d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang Instruction *I = dyn_cast<Instruction>(V); 45503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach if (!I || (I->getOpcode() != Instruction::FMul && 456f279731b7629ff1add3dbc91a8a63720c9064230Shuxin Yang I->getOpcode() != Instruction::FDiv)) 457d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang return false; 458d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 45936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C0 = dyn_cast<Constant>(I->getOperand(0)); 46036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C1 = dyn_cast<Constant>(I->getOperand(1)); 461d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 462d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang if (C0 && C1) 463d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang return false; 464d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 46536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return (C0 && isFiniteNonZeroFp(C0)) || (C1 && isFiniteNonZeroFp(C1)); 466d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang} 467d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 468d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang/// foldFMulConst() is a helper routine of InstCombiner::visitFMul(). 469d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang/// The input \p FMulOrDiv is a FMul/FDiv with one and only one operand 470d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang/// being a constant (i.e. isFMulOrFDivWithConstant(FMulOrDiv) == true). 47103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach/// This function is to simplify "FMulOrDiv * C" and returns the 472d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang/// resulting expression. Note that this function could return NULL in 473d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang/// case the constants cannot be folded into a normal floating-point. 47403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach/// 47536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesValue *InstCombiner::foldFMulConst(Instruction *FMulOrDiv, Constant *C, 476f279731b7629ff1add3dbc91a8a63720c9064230Shuxin Yang Instruction *InsertBefore) { 477d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang assert(isFMulOrFDivWithConstant(FMulOrDiv) && "V is invalid"); 478d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 479d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang Value *Opnd0 = FMulOrDiv->getOperand(0); 480d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang Value *Opnd1 = FMulOrDiv->getOperand(1); 481d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 48236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C0 = dyn_cast<Constant>(Opnd0); 48336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C1 = dyn_cast<Constant>(Opnd1); 484d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 485dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BinaryOperator *R = nullptr; 486d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 487d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang // (X * C0) * C => X * (C0*C) 488d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang if (FMulOrDiv->getOpcode() == Instruction::FMul) { 489d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang Constant *F = ConstantExpr::getFMul(C1 ? C1 : C0, C); 49036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isNormalFp(F)) 491d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang R = BinaryOperator::CreateFMul(C1 ? Opnd0 : Opnd1, F); 492d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } else { 493d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang if (C0) { 494d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang // (C0 / X) * C => (C0 * C) / X 495b1ccfb3a548e122e282cd62c534c4d47f5310bf6Shuxin Yang if (FMulOrDiv->hasOneUse()) { 496b1ccfb3a548e122e282cd62c534c4d47f5310bf6Shuxin Yang // It would otherwise introduce another div. 49736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *F = ConstantExpr::getFMul(C0, C); 498b1ccfb3a548e122e282cd62c534c4d47f5310bf6Shuxin Yang if (isNormalFp(F)) 499b1ccfb3a548e122e282cd62c534c4d47f5310bf6Shuxin Yang R = BinaryOperator::CreateFDiv(F, Opnd1); 500b1ccfb3a548e122e282cd62c534c4d47f5310bf6Shuxin Yang } 501d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } else { 502d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang // (X / C1) * C => X * (C/C1) if C/C1 is not a denormal 50336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *F = ConstantExpr::getFDiv(C, C1); 504d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang if (isNormalFp(F)) { 505d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang R = BinaryOperator::CreateFMul(Opnd0, F); 506d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } else { 50703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // (X / C1) * C => X / (C1/C) 508d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang Constant *F = ConstantExpr::getFDiv(C1, C); 50936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isNormalFp(F)) 510d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang R = BinaryOperator::CreateFDiv(Opnd0, F); 511d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } 512d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } 513d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } 514d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 515d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang if (R) { 516d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang R->setHasUnsafeAlgebra(true); 517d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang InsertNewInstWith(R, *InsertBefore); 518d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } 519d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 520d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang return R; 521d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang} 522d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 523d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitFMul(BinaryOperator &I) { 524096aa79276b8527a3cbbb3691e40e729dea09523Duncan Sands bool Changed = SimplifyAssociativeOrCommutative(I); 525d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 526d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 527dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 528dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 529dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 530d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang if (isa<Constant>(Op0)) 531d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang std::swap(Op0, Op1); 532d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 533ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = 534ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SimplifyFMulInst(Op0, Op1, I.getFastMathFlags(), DL, TLI, DT, AC)) 535c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman return ReplaceInstUsesWith(I, V); 536d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 537a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang bool AllowReassociate = I.hasUnsafeAlgebra(); 538a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang 539c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman // Simplify mul instructions with a constant RHS. 540c244f381768e2e6ab9daa807adbee18de4756a07Michael Ilseman if (isa<Constant>(Op1)) { 541d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Try to fold constant mul into select arguments. 542d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 543d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 544d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return R; 545d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 546d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (isa<PHINode>(Op0)) 547d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 548d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return NV; 549d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 55036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // (fmul X, -1.0) --> (fsub -0.0, X) 55136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op1, m_SpecificFP(-1.0))) { 55236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *NegZero = ConstantFP::getNegativeZero(Op1->getType()); 55336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *RI = BinaryOperator::CreateFSub(NegZero, Op0); 55436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RI->copyFastMathFlags(&I); 55536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return RI; 55636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 55736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 55836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C = cast<Constant>(Op1); 55936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (AllowReassociate && isFiniteNonZeroFp(C)) { 560d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang // Let MDC denote an expression in one of these forms: 561d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang // X * C, C/X, X/C, where C is a constant. 562d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang // 563d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang // Try to simplify "MDC * Constant" 56436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isFMulOrFDivWithConstant(Op0)) 56536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Value *V = foldFMulConst(cast<Instruction>(Op0), C, &I)) 566d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang return ReplaceInstUsesWith(I, V); 567d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 568c5a4c25b8780434a00968ed93634974a0b796a06Quentin Colombet // (MDC +/- C1) * C => (MDC * C) +/- (C1 * C) 569d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang Instruction *FAddSub = dyn_cast<Instruction>(Op0); 570d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang if (FAddSub && 571d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang (FAddSub->getOpcode() == Instruction::FAdd || 572d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang FAddSub->getOpcode() == Instruction::FSub)) { 573d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang Value *Opnd0 = FAddSub->getOperand(0); 574d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang Value *Opnd1 = FAddSub->getOperand(1); 57536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C0 = dyn_cast<Constant>(Opnd0); 57636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C1 = dyn_cast<Constant>(Opnd1); 577d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang bool Swap = false; 578d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang if (C0) { 579f279731b7629ff1add3dbc91a8a63720c9064230Shuxin Yang std::swap(C0, C1); 580f279731b7629ff1add3dbc91a8a63720c9064230Shuxin Yang std::swap(Opnd0, Opnd1); 58103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach Swap = true; 582d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } 583d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 58436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (C1 && isFiniteNonZeroFp(C1) && isFMulOrFDivWithConstant(Opnd0)) { 585c5a4c25b8780434a00968ed93634974a0b796a06Quentin Colombet Value *M1 = ConstantExpr::getFMul(C1, C); 58636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *M0 = isNormalFp(cast<Constant>(M1)) ? 587d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang foldFMulConst(cast<Instruction>(Opnd0), C, &I) : 588dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines nullptr; 589d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang if (M0 && M1) { 590d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang if (Swap && FAddSub->getOpcode() == Instruction::FSub) 591d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang std::swap(M0, M1); 592d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang 5936dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer Instruction *RI = (FAddSub->getOpcode() == Instruction::FAdd) 5946dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer ? BinaryOperator::CreateFAdd(M0, M1) 5956dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer : BinaryOperator::CreateFSub(M0, M1); 596a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang RI->copyFastMathFlags(&I); 597d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang return RI; 598d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } 599d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } 600d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } 601d3ae2866d105f6da6375544eb41aea0dad75a9f2Shuxin Yang } 602d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 603d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 60437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // sqrt(X) * sqrt(X) -> X 60537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (AllowReassociate && (Op0 == Op1)) 60637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) 60737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (II->getIntrinsicID() == Intrinsic::sqrt) 60837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return ReplaceInstUsesWith(I, II->getOperand(0)); 609d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 61084030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas // Under unsafe algebra do: 61184030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas // X * log2(0.5*Y) = X*log2(Y) - X 61237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (AllowReassociate) { 613dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *OpX = nullptr; 614dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *OpY = nullptr; 61584030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas IntrinsicInst *Log2; 616c2a08d28eb1199d67dff5b66061cf7f6a25d2527Pedro Artigas detectLog2OfHalf(Op0, OpY, Log2); 617c2a08d28eb1199d67dff5b66061cf7f6a25d2527Pedro Artigas if (OpY) { 618c2a08d28eb1199d67dff5b66061cf7f6a25d2527Pedro Artigas OpX = Op1; 619c2a08d28eb1199d67dff5b66061cf7f6a25d2527Pedro Artigas } else { 620c2a08d28eb1199d67dff5b66061cf7f6a25d2527Pedro Artigas detectLog2OfHalf(Op1, OpY, Log2); 621c2a08d28eb1199d67dff5b66061cf7f6a25d2527Pedro Artigas if (OpY) { 622c2a08d28eb1199d67dff5b66061cf7f6a25d2527Pedro Artigas OpX = Op0; 62384030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas } 62484030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas } 62584030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas // if pattern detected emit alternate sequence 62684030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas if (OpX && OpY) { 6276dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer BuilderTy::FastMathFlagGuard Guard(*Builder); 6286dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer Builder->SetFastMathFlags(Log2->getFastMathFlags()); 62984030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas Log2->setArgOperand(0, OpY); 63084030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas Value *FMulVal = Builder->CreateFMul(OpX, Log2); 6316dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer Value *FSub = Builder->CreateFSub(FMulVal, OpX); 6326dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer FSub->takeName(&I); 6336dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer return ReplaceInstUsesWith(I, FSub); 63484030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas } 63584030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas } 63684030dcb3f532f66b13d54da7bdef9621527c5c5Pedro Artigas 637a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang // Handle symmetric situation in a 2-iteration loop 638a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang Value *Opnd0 = Op0; 639a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang Value *Opnd1 = Op1; 640a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang for (int i = 0; i < 2; i++) { 641a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang bool IgnoreZeroSign = I.hasNoSignedZeros(); 642a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang if (BinaryOperator::isFNeg(Opnd0, IgnoreZeroSign)) { 6436dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer BuilderTy::FastMathFlagGuard Guard(*Builder); 6446dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer Builder->SetFastMathFlags(I.getFastMathFlags()); 6456dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer 646a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang Value *N0 = dyn_castFNegVal(Opnd0, IgnoreZeroSign); 647a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang Value *N1 = dyn_castFNegVal(Opnd1, IgnoreZeroSign); 648a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang 649a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang // -X * -Y => X*Y 65036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (N1) { 65136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *FMul = Builder->CreateFMul(N0, N1); 65236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FMul->takeName(&I); 65336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return ReplaceInstUsesWith(I, FMul); 65436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 655a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang 656a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang if (Opnd0->hasOneUse()) { 657a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang // -X * Y => -(X*Y) (Promote negation as high as possible) 658a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang Value *T = Builder->CreateFMul(N0, Opnd1); 6596dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer Value *Neg = Builder->CreateFNeg(T); 6606dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer Neg->takeName(&I); 6616dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer return ReplaceInstUsesWith(I, Neg); 662a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang } 663a5ed031fbcec67081d4857c9000f0180840fe2d5Shuxin Yang } 664a5ed031fbcec67081d4857c9000f0180840fe2d5Shuxin Yang 665a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang // (X*Y) * X => (X*X) * Y where Y != X 66603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach // The purpose is two-fold: 667a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang // 1) to form a power expression (of X). 668a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang // 2) potentially shorten the critical path: After transformation, the 669a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang // latency of the instruction Y is amortized by the expression of X*X, 670a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang // and therefore Y is in a "less critical" position compared to what it 671a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang // was before the transformation. 672a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang // 673a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang if (AllowReassociate) { 674a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang Value *Opnd0_0, *Opnd0_1; 675a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang if (Opnd0->hasOneUse() && 676a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang match(Opnd0, m_FMul(m_Value(Opnd0_0), m_Value(Opnd0_1)))) { 677dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *Y = nullptr; 678a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang if (Opnd0_0 == Opnd1 && Opnd0_1 != Opnd1) 679a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang Y = Opnd0_1; 680a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang else if (Opnd0_1 == Opnd1 && Opnd0_0 != Opnd1) 681a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang Y = Opnd0_0; 682a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang 683a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang if (Y) { 6846dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer BuilderTy::FastMathFlagGuard Guard(*Builder); 6856dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer Builder->SetFastMathFlags(I.getFastMathFlags()); 6866dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer Value *T = Builder->CreateFMul(Opnd1, Opnd1); 687a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang 6886dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer Value *R = Builder->CreateFMul(T, Y); 6896dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer R->takeName(&I); 6906dc5c6b8792dd599257eb78c5891ede95bbc6085Benjamin Kramer return ReplaceInstUsesWith(I, R); 691a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang } 692a5ed031fbcec67081d4857c9000f0180840fe2d5Shuxin Yang } 693a5ed031fbcec67081d4857c9000f0180840fe2d5Shuxin Yang } 694a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang 695a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang if (!isa<Constant>(Op1)) 696a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang std::swap(Opnd0, Opnd1); 697a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang else 698a1444219b271cab6fbfe340c1328b0ab10d8f7b6Shuxin Yang break; 699a5ed031fbcec67081d4857c9000f0180840fe2d5Shuxin Yang } 700a5ed031fbcec67081d4857c9000f0180840fe2d5Shuxin Yang 701dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Changed ? &I : nullptr; 702d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 703d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 704d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select 705d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// instruction. 706d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattnerbool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { 707d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner SelectInst *SI = cast<SelectInst>(I.getOperand(1)); 70803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 709d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 710d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner int NonNullOperand = -1; 711d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) 712d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (ST->isNullValue()) 713d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner NonNullOperand = 2; 714d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 715d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) 716d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (ST->isNullValue()) 717d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner NonNullOperand = 1; 71803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 719d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (NonNullOperand == -1) 720d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return false; 72103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 722d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *SelectCond = SI->getOperand(0); 72303fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 724d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Change the div/rem to use 'Y' instead of the select. 725d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner I.setOperand(1, SI->getOperand(NonNullOperand)); 72603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 727d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Okay, we know we replace the operand of the div/rem with 'Y' with no 728d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // problem. However, the select, or the condition of the select may have 729d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // multiple uses. Based on our knowledge that the operand must be non-zero, 730d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // propagate the known value for the select into other uses of it, and 731d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // propagate a known value of the condition into its other users. 73203fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 733d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If the select and condition only have a single use, don't bother with this, 734d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // early exit. 735d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SI->use_empty() && SelectCond->hasOneUse()) 736d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return true; 73703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 738d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Scan the current block backward, looking for other uses of SI. 739d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin(); 74003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 741d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner while (BBI != BBFront) { 742d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner --BBI; 743d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If we found a call to a function, we can't assume it will return, so 744d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // information from below it cannot be propagated above it. 745d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) 746d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner break; 74703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 748d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Replace uses of the select or its condition with the known values. 749d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); 750d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner I != E; ++I) { 751d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (*I == SI) { 752d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner *I = SI->getOperand(NonNullOperand); 753d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Worklist.Add(BBI); 754d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } else if (*I == SelectCond) { 7556a72c84b161c176da91ddae1bd97bae7aab6d968Jakub Staszak *I = Builder->getInt1(NonNullOperand == 1); 756d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Worklist.Add(BBI); 757d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 758d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 75903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 760d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If we past the instruction, quit looking for it. 761d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (&*BBI == SI) 762dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SI = nullptr; 763d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (&*BBI == SelectCond) 764dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SelectCond = nullptr; 76503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 766d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If we ran out of things to eliminate, break out of the loop. 767dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!SelectCond && !SI) 768d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner break; 76903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 770d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 771d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return true; 772d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 773d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 774d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 775d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// This function implements the transforms common to both integer division 776d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// instructions (udiv and sdiv). It is called by the visitors to those integer 777d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// division instructions. 778d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// @brief Common integer divide transforms 779d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { 780d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 781d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 7821add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner // The RHS is known non-zero. 7834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) { 7841add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner I.setOperand(1, V); 7851add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner return &I; 7861add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner } 78703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 788d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Handle cases involving: [su]div X, (select Cond, Y, Z) 789d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // This does not apply for fdiv. 790d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 791d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return &I; 792d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 79337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Instruction *LHS = dyn_cast<Instruction>(Op0)) { 79437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const APInt *C2; 79537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (match(Op1, m_APInt(C2))) { 79637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Value *X; 79737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const APInt *C1; 79837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool IsSigned = I.getOpcode() == Instruction::SDiv; 79937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 80037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // (X / C1) / C2 -> X / (C1*C2) 80137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if ((IsSigned && match(LHS, m_SDiv(m_Value(X), m_APInt(C1)))) || 80237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (!IsSigned && match(LHS, m_UDiv(m_Value(X), m_APInt(C1))))) { 80337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt Product(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); 80437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!MultiplyOverflows(*C1, *C2, Product, IsSigned)) 80537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return BinaryOperator::Create(I.getOpcode(), X, 80637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ConstantInt::get(I.getType(), Product)); 80737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 80837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 80937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if ((IsSigned && match(LHS, m_NSWMul(m_Value(X), m_APInt(C1)))) || 81037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (!IsSigned && match(LHS, m_NUWMul(m_Value(X), m_APInt(C1))))) { 81137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); 81237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 81337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1. 81437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (IsMultiple(*C2, *C1, Quotient, IsSigned)) { 81537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BinaryOperator *BO = BinaryOperator::Create( 81637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient)); 81737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BO->setIsExact(I.isExact()); 81837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return BO; 819d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 820d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 82137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2. 82237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (IsMultiple(*C1, *C2, Quotient, IsSigned)) { 82337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BinaryOperator *BO = BinaryOperator::Create( 82437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient)); 82537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BO->setHasNoUnsignedWrap( 82637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines !IsSigned && 82737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap()); 82837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BO->setHasNoSignedWrap( 82937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap()); 83037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return BO; 83137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 83237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 83337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 83437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if ((IsSigned && match(LHS, m_NSWShl(m_Value(X), m_APInt(C1))) && 83537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines *C1 != C1->getBitWidth() - 1) || 83637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (!IsSigned && match(LHS, m_NUWShl(m_Value(X), m_APInt(C1))))) { 83737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); 83837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt C1Shifted = APInt::getOneBitSet( 83937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue())); 84037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 84137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of C1. 84237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (IsMultiple(*C2, C1Shifted, Quotient, IsSigned)) { 84337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BinaryOperator *BO = BinaryOperator::Create( 84437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient)); 84537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BO->setIsExact(I.isExact()); 84637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return BO; 84737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 84837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 84937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // (X << C1) / C2 -> X * (C2 >> C1) if C1 is a multiple of C2. 85037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (IsMultiple(C1Shifted, *C2, Quotient, IsSigned)) { 85137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BinaryOperator *BO = BinaryOperator::Create( 85237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient)); 85337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BO->setHasNoUnsignedWrap( 85437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines !IsSigned && 85537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap()); 85637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BO->setHasNoSignedWrap( 85737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap()); 85837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return BO; 85937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 86037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 86137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 86237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (*C2 != 0) { // avoid X udiv 0 86337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 86437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Instruction *R = FoldOpIntoSelect(I, SI)) 86537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return R; 86637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (isa<PHINode>(Op0)) 86737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (Instruction *NV = FoldOpIntoPhi(I)) 86837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return NV; 86937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 870d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 871d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 872d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 873dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (ConstantInt *One = dyn_cast<ConstantInt>(Op0)) { 874dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (One->isOne() && !I.getType()->isIntegerTy(1)) { 875dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool isSigned = I.getOpcode() == Instruction::SDiv; 876dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (isSigned) { 877dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the 878dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // result is one, if Op1 is -1 then the result is minus one, otherwise 879dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // it's zero. 880dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *Inc = Builder->CreateAdd(Op1, One); 881dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *Cmp = Builder->CreateICmpULT( 882dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Inc, ConstantInt::get(I.getType(), 3)); 883dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return SelectInst::Create(Cmp, Op1, ConstantInt::get(I.getType(), 0)); 884dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } else { 885dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the 886dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // result is one, otherwise it's zero. 887dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return new ZExtInst(Builder->CreateICmpEQ(Op1, One), I.getType()); 888dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 889dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 890dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 891dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 89223b02cd0315625d9d586118abcc972053298d50bBenjamin Kramer // See if we can fold away this div instruction. 89323b02cd0315625d9d586118abcc972053298d50bBenjamin Kramer if (SimplifyDemandedInstructionBits(I)) 89423b02cd0315625d9d586118abcc972053298d50bBenjamin Kramer return &I; 89523b02cd0315625d9d586118abcc972053298d50bBenjamin Kramer 896593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y 897dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *X = nullptr, *Z = nullptr; 898593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 899593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands bool isSigned = I.getOpcode() == Instruction::SDiv; 900593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || 901593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) 902593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return BinaryOperator::Create(I.getOpcode(), X, Op1); 903d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 904d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 905dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 906d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 907d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 9087d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer/// dyn_castZExtVal - Checks if V is a zext or constant that can 9097d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer/// be truncated to Ty without losing bits. 910db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnerstatic Value *dyn_castZExtVal(Value *V, Type *Ty) { 9117d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) { 9127d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (Z->getSrcTy() == Ty) 9137d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer return Z->getOperand(0); 9147d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) { 9157d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth()) 9167d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer return ConstantExpr::getTrunc(C, Ty); 9177d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer } 918dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 9197d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer} 9207d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer 921e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemernamespace { 922e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemerconst unsigned MaxDepth = 6; 923e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemertypedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1, 924e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer const BinaryOperator &I, 925e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer InstCombiner &IC); 926e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 927e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer/// \brief Used to maintain state for visitUDivOperand(). 928e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemerstruct UDivFoldAction { 929e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this 930e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer ///< operand. This can be zero if this action 931e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer ///< joins two actions together. 932e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 933e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Value *OperandToFold; ///< Which operand to fold. 934e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer union { 935e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Instruction *FoldResult; ///< The instruction returned when FoldAction is 936e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer ///< invoked. 937e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 938e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer size_t SelectLHSIdx; ///< Stores the LHS action index if this action 939e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer ///< joins two actions together. 940e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer }; 941e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 942e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand) 943dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {} 944e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS) 945e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {} 946e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer}; 947e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer} 948b19dd2bcaf219a3b5f144815c40b3f1b11a3d35dHal Finkel 949e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer// X udiv 2^C -> X >> C 950e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemerstatic Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1, 951e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer const BinaryOperator &I, InstCombiner &IC) { 952e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer const APInt &C = cast<Constant>(Op1)->getUniqueInteger(); 953e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer BinaryOperator *LShr = BinaryOperator::CreateLShr( 954e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Op0, ConstantInt::get(Op0->getType(), C.logBase2())); 95537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (I.isExact()) 95637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LShr->setIsExact(); 957e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return LShr; 958e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer} 959b19dd2bcaf219a3b5f144815c40b3f1b11a3d35dHal Finkel 960e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer// X udiv C, where C >= signbit 961e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemerstatic Instruction *foldUDivNegCst(Value *Op0, Value *Op1, 962e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer const BinaryOperator &I, InstCombiner &IC) { 963e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Value *ICI = IC.Builder->CreateICmpULT(Op0, cast<ConstantInt>(Op1)); 96403fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 965e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return SelectInst::Create(ICI, Constant::getNullValue(I.getType()), 966e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer ConstantInt::get(I.getType(), 1)); 967e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer} 968e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 969e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer// X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 970e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemerstatic Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I, 971e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer InstCombiner &IC) { 972e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Instruction *ShiftLeft = cast<Instruction>(Op1); 973e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (isa<ZExtInst>(ShiftLeft)) 974e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer ShiftLeft = cast<Instruction>(ShiftLeft->getOperand(0)); 975e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 976e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer const APInt &CI = 977e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer cast<Constant>(ShiftLeft->getOperand(0))->getUniqueInteger(); 978e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Value *N = ShiftLeft->getOperand(1); 979e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (CI != 1) 980e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer N = IC.Builder->CreateAdd(N, ConstantInt::get(N->getType(), CI.logBase2())); 981e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1)) 982e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer N = IC.Builder->CreateZExt(N, Z->getDestTy()); 983e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N); 98437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (I.isExact()) 98537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines LShr->setIsExact(); 986e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return LShr; 987e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer} 988e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 989e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer// \brief Recursively visits the possible right hand operands of a udiv 990e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer// instruction, seeing through select instructions, to determine if we can 991e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer// replace the udiv with something simpler. If we find that an operand is not 992e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer// able to simplify the udiv, we abort the entire transformation. 993e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemerstatic size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I, 994e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer SmallVectorImpl<UDivFoldAction> &Actions, 995e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer unsigned Depth = 0) { 996e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // Check to see if this is an unsigned division with an exact power of 2, 997e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // if so, convert to a right shift. 998e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (match(Op1, m_Power2())) { 999e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1)); 1000e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return Actions.size(); 1001a29fc806fe02cea76f7896b7e344bb919dd7ac25Pete Cooper } 1002d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1003e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) 1004d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X udiv C, where C >= signbit 1005d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (C->getValue().isNegative()) { 1006e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Actions.push_back(UDivFoldAction(foldUDivNegCst, C)); 1007e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return Actions.size(); 1008d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1009e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 1010e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 1011e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (match(Op1, m_Shl(m_Power2(), m_Value())) || 1012e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) { 1013e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Actions.push_back(UDivFoldAction(foldUDivShl, Op1)); 1014e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return Actions.size(); 1015d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1016d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1017e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // The remaining tests are all recursive, so bail out if we hit the limit. 1018e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (Depth++ == MaxDepth) 1019e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return 0; 1020e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 1021e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 102237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (size_t LHSIdx = 102337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth)) 102437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) { 102537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1)); 1026e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return Actions.size(); 1027e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer } 1028e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 1029e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return 0; 1030e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer} 1031e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 1032e7006bb04bd881478fe24d6fbb3051ba3f63d746David MajnemerInstruction *InstCombiner::visitUDiv(BinaryOperator &I) { 1033e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1034e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 1035dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 1036dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 1037dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1038ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = SimplifyUDivInst(Op0, Op1, DL, TLI, DT, AC)) 1039e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return ReplaceInstUsesWith(I, V); 1040e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 1041e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // Handle the integer div common cases 1042e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (Instruction *Common = commonIDivTransforms(I)) 1043e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return Common; 1044e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 1045b19dd2bcaf219a3b5f144815c40b3f1b11a3d35dHal Finkel // (x lshr C1) udiv C2 --> x udiv (C2 << C1) 104637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines { 1047b19dd2bcaf219a3b5f144815c40b3f1b11a3d35dHal Finkel Value *X; 104837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const APInt *C1, *C2; 104937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && 105037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines match(Op1, m_APInt(C2))) { 105137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines bool Overflow; 105237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow); 1053ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!Overflow) { 1054ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value())); 1055ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BinaryOperator *BO = BinaryOperator::CreateUDiv( 105637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines X, ConstantInt::get(X->getType(), C2ShlC1)); 1057ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (IsExact) 1058ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO->setIsExact(); 1059ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return BO; 1060ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 106137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 1062b19dd2bcaf219a3b5f144815c40b3f1b11a3d35dHal Finkel } 1063b19dd2bcaf219a3b5f144815c40b3f1b11a3d35dHal Finkel 10647d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer // (zext A) udiv (zext B) --> zext (A udiv B) 10657d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 10667d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 106737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return new ZExtInst( 106837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", I.isExact()), 106937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines I.getType()); 10707d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer 1071e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...)))) 1072e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer SmallVector<UDivFoldAction, 6> UDivActions; 1073e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (visitUDivOperand(Op0, Op1, I, UDivActions)) 1074e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) { 1075e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer FoldUDivOperandCb Action = UDivActions[i].FoldAction; 1076e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Value *ActionOp1 = UDivActions[i].OperandToFold; 1077e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Instruction *Inst; 1078e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (Action) 1079e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Inst = Action(Op0, ActionOp1, I, *this); 1080e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer else { 1081e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // This action joins two actions together. The RHS of this action is 1082e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // simply the last action we processed, we saved the LHS action index in 1083e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // the joining action. 1084e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer size_t SelectRHSIdx = i - 1; 1085e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult; 1086e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx; 1087e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult; 1088e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(), 1089e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer SelectLHS, SelectRHS); 1090e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer } 1091e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 1092e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // If this is the last action to process, return it to the InstCombiner. 1093e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // Otherwise, we insert it before the UDiv and record it so that we may 1094e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer // use it as part of a joining action (i.e., a SelectInst). 1095e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer if (e - i != 1) { 1096e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer Inst->insertBefore(&I); 1097e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer UDivActions[i].FoldResult = Inst; 1098e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer } else 1099e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer return Inst; 1100e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer } 1101e7006bb04bd881478fe24d6fbb3051ba3f63d746David Majnemer 1102dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1103d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 1104d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1105d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitSDiv(BinaryOperator &I) { 1106d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1107d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1108dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 1109dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 1110dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1111ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = SimplifySDivInst(Op0, Op1, DL, TLI, DT, AC)) 1112593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return ReplaceInstUsesWith(I, V); 1113593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 1114d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Handle the integer div common cases 1115d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *Common = commonIDivTransforms(I)) 1116d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return Common; 1117d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 111836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // sdiv X, -1 == -X 111936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op1, m_AllOnes())) 112036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return BinaryOperator::CreateNeg(Op0); 1121d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 112236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 11237a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // sdiv X, C --> ashr exact X, log2(C) 11247a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (I.isExact() && RHS->getValue().isNonNegative() && 1125d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner RHS->getValue().isPowerOf2()) { 1126d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *ShAmt = llvm::ConstantInt::get(RHS->getType(), 1127d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner RHS->getValue().exactLogBase2()); 11287a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName()); 1129d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 113036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 1131d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 113236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Constant *RHS = dyn_cast<Constant>(Op1)) { 1133c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines // X/INT_MIN -> X == INT_MIN 1134c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines if (RHS->isMinSignedValue()) 1135c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return new ZExtInst(Builder->CreateICmpEQ(Op0, Op1), I.getType()); 1136c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines 1137d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // -X/C --> X/-C provided the negation doesn't overflow. 1138ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *X; 1139ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) { 1140ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *BO = BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(RHS)); 1141ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO->setIsExact(I.isExact()); 1142ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return BO; 1143ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 1144d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1145d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1146d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If the sign bits of both operands are zero (i.e. we can prove they are 1147d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // unsigned inputs), turn this into a udiv. 1148b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy()) { 1149d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 115037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (MaskedValueIsZero(Op0, Mask, 0, &I)) { 115137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (MaskedValueIsZero(Op1, Mask, 0, &I)) { 115294c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set 1153ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 1154ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO->setIsExact(I.isExact()); 1155ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return BO; 1156d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 115703fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 11584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (isKnownToBeAPowerOfTwo(Op1, DL, /*OrZero*/ true, 0, AC, &I, DT)) { 1159d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 1160d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Safe because the only negative value (1 << Y) can take on is 1161d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 1162d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // the sign bit set. 1163ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 1164ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BO->setIsExact(I.isExact()); 1165ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return BO; 1166d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1167d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1168d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 116903fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1170dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1171d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 1172d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 11737d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang/// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special 11747d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang/// FP value and: 117503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach/// 1) 1/C is exact, or 11767d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang/// 2) reciprocal is allowed. 1177da2ed458b4e7066fc414c403173b882ccc2c8833Sylvestre Ledru/// If the conversion was successful, the simplified expression "X * 1/C" is 11787d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang/// returned; otherwise, NULL is returned. 11797d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang/// 118037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstatic Instruction *CvtFDivConstToReciprocal(Value *Dividend, Constant *Divisor, 11817d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang bool AllowReciprocal) { 118236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!isa<ConstantFP>(Divisor)) // TODO: handle vectors. 1183dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 118436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 118536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const APFloat &FpVal = cast<ConstantFP>(Divisor)->getValueAPF(); 11867d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang APFloat Reciprocal(FpVal.getSemantics()); 11877d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang bool Cvt = FpVal.getExactInverse(&Reciprocal); 118803fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 118907969dc8aed62fcd5c5760b2ec331275479f4a80Michael Gottesman if (!Cvt && AllowReciprocal && FpVal.isFiniteNonZero()) { 11907d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Reciprocal = APFloat(FpVal.getSemantics(), 1.0f); 11917d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang (void)Reciprocal.divide(FpVal, APFloat::rmNearestTiesToEven); 11927d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Cvt = !Reciprocal.isDenormal(); 11937d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 11947d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 11957d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang if (!Cvt) 1196dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 11977d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 11987d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang ConstantFP *R; 11997d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal); 12007d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang return BinaryOperator::CreateFMul(Dividend, R); 12017d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang} 12027d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 120331726c154dafa9fef08b1bcac9822c2a4618ec19Frits van BommelInstruction *InstCombiner::visitFDiv(BinaryOperator &I) { 120431726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 120531726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel 1206dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 1207dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 1208dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1209ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = SimplifyFDivInst(Op0, Op1, I.getFastMathFlags(), 1210ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DL, TLI, DT, AC)) 121131726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel return ReplaceInstUsesWith(I, V); 121231726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel 1213a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (isa<Constant>(Op0)) 1214a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1215a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (Instruction *R = FoldOpIntoSelect(I, SI)) 1216a98ce503b958821fd2530aad585c21e730695a9eStephen Lin return R; 1217a98ce503b958821fd2530aad585c21e730695a9eStephen Lin 12187d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang bool AllowReassociate = I.hasUnsafeAlgebra(); 12197d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang bool AllowReciprocal = I.hasAllowReciprocal(); 12207d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 122136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 1222a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 1223a98ce503b958821fd2530aad585c21e730695a9eStephen Lin if (Instruction *R = FoldOpIntoSelect(I, SI)) 1224a98ce503b958821fd2530aad585c21e730695a9eStephen Lin return R; 1225a98ce503b958821fd2530aad585c21e730695a9eStephen Lin 12267d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang if (AllowReassociate) { 1227dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *C1 = nullptr; 122836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C2 = Op1C; 12297d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Value *X; 1230dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Instruction *Res = nullptr; 12317d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 123236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op0, m_FMul(m_Value(X), m_Constant(C1)))) { 12337d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // (X*C1)/C2 => X * (C1/C2) 12347d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // 12357d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Constant *C = ConstantExpr::getFDiv(C1, C2); 123636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isNormalFp(C)) 12377d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Res = BinaryOperator::CreateFMul(X, C); 123836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) { 12397d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed] 12407d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // 12417d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Constant *C = ConstantExpr::getFMul(C1, C2); 124236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isNormalFp(C)) { 124336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Res = CvtFDivConstToReciprocal(X, C, AllowReciprocal); 12447d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang if (!Res) 124503fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach Res = BinaryOperator::CreateFDiv(X, C); 12467d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 12477d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 12487d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 12497d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang if (Res) { 12507d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Res->setFastMathFlags(I.getFastMathFlags()); 12517d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang return Res; 12527d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 12537d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 12547d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 12557d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // X / C => X * 1/C 125636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Instruction *T = CvtFDivConstToReciprocal(Op0, Op1C, AllowReciprocal)) { 125736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines T->copyFastMathFlags(&I); 12587d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang return T; 125936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 12607d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 1261dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 12627d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 12637d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 126436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (AllowReassociate && isa<Constant>(Op0)) { 126536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *C1 = cast<Constant>(Op0), *C2; 1266dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *Fold = nullptr; 12677d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Value *X; 12687d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang bool CreateDiv = true; 12697d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 12707d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // C1 / (X*C2) => (C1/C2) / X 127136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op1, m_FMul(m_Value(X), m_Constant(C2)))) 12727d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Fold = ConstantExpr::getFDiv(C1, C2); 127336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else if (match(Op1, m_FDiv(m_Value(X), m_Constant(C2)))) { 12747d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // C1 / (X/C2) => (C1*C2) / X 12757d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Fold = ConstantExpr::getFMul(C1, C2); 127636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else if (match(Op1, m_FDiv(m_Constant(C2), m_Value(X)))) { 12777d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // C1 / (C2/X) => (C1/C2) * X 12787d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Fold = ConstantExpr::getFDiv(C1, C2); 12797d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang CreateDiv = false; 12807d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 12817d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 128236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Fold && isNormalFp(Fold)) { 128336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *R = CreateDiv ? BinaryOperator::CreateFDiv(Fold, X) 128436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : BinaryOperator::CreateFMul(X, Fold); 128536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines R->setFastMathFlags(I.getFastMathFlags()); 128636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return R; 12877d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 1288dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 12897d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 12907d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 12917d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang if (AllowReassociate) { 12927d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang Value *X, *Y; 1293dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *NewInst = nullptr; 1294dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Instruction *SimpR = nullptr; 12957d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 12967d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang if (Op0->hasOneUse() && match(Op0, m_FDiv(m_Value(X), m_Value(Y)))) { 12977d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // (X/Y) / Z => X / (Y*Z) 12987d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // 129936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!isa<Constant>(Y) || !isa<Constant>(Op1)) { 13007d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang NewInst = Builder->CreateFMul(Y, Op1); 130136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Instruction *RI = dyn_cast<Instruction>(NewInst)) { 130236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FastMathFlags Flags = I.getFastMathFlags(); 130336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Flags &= cast<Instruction>(Op0)->getFastMathFlags(); 130436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RI->setFastMathFlags(Flags); 130536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 13067d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang SimpR = BinaryOperator::CreateFDiv(X, NewInst); 13077d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 13087d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } else if (Op1->hasOneUse() && match(Op1, m_FDiv(m_Value(X), m_Value(Y)))) { 13097d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // Z / (X/Y) => Z*Y / X 13107d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang // 131136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!isa<Constant>(Y) || !isa<Constant>(Op0)) { 13127d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang NewInst = Builder->CreateFMul(Op0, Y); 131336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Instruction *RI = dyn_cast<Instruction>(NewInst)) { 131436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FastMathFlags Flags = I.getFastMathFlags(); 131536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Flags &= cast<Instruction>(Op1)->getFastMathFlags(); 131636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RI->setFastMathFlags(Flags); 131736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 13187d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang SimpR = BinaryOperator::CreateFDiv(NewInst, X); 13197d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 13207d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang } 13217d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang 13227d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang if (NewInst) { 13237d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang if (Instruction *T = dyn_cast<Instruction>(NewInst)) 13247d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang T->setDebugLoc(I.getDebugLoc()); 13257d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang SimpR->setFastMathFlags(I.getFastMathFlags()); 13267d72cf892ec745d916af34cf9e68703010b4ded8Shuxin Yang return SimpR; 1327546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer } 1328546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer } 1329546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer 1330dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 133131726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel} 133231726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel 1333d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// This function implements the transforms common to both integer remainder 1334d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// instructions (urem and srem). It is called by the visitors to those integer 1335d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// remainder instructions. 1336d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// @brief Common integer remainder transforms 1337d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { 1338d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1339d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 13401add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner // The RHS is known non-zero. 13414c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) { 13421add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner I.setOperand(1, V); 13431add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner return &I; 13441add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner } 13451add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner 1346f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands // Handle cases involving: rem X, (select Cond, Y, Z) 1347f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 1348f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return &I; 1349d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 135036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<Constant>(Op1)) { 1351d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 1352d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 1353d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 1354d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return R; 1355d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } else if (isa<PHINode>(Op0I)) { 1356d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 1357d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return NV; 1358d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1359d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1360d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // See if we can fold away this rem instruction. 1361d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SimplifyDemandedInstructionBits(I)) 1362d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return &I; 1363d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1364d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1365d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1366dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1367d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 1368d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1369d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitURem(BinaryOperator &I) { 1370d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1371d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1372dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 1373dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 1374dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1375ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = SimplifyURemInst(Op0, Op1, DL, TLI, DT, AC)) 1376f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return ReplaceInstUsesWith(I, V); 1377f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands 1378d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *common = commonIRemTransforms(I)) 1379d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return common; 138003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1381fa49d7d6e4384381e4307a0d2495e6e5b15821e3David Majnemer // (zext A) urem (zext B) --> zext (A urem B) 1382fa49d7d6e4384381e4307a0d2495e6e5b15821e3David Majnemer if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 1383fa49d7d6e4384381e4307a0d2495e6e5b15821e3David Majnemer if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 1384fa49d7d6e4384381e4307a0d2495e6e5b15821e3David Majnemer return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), 1385fa49d7d6e4384381e4307a0d2495e6e5b15821e3David Majnemer I.getType()); 1386fa49d7d6e4384381e4307a0d2495e6e5b15821e3David Majnemer 1387a8ccefc0a31c868c79cfc028e2a957269de5aba6David Majnemer // X urem Y -> X and Y-1, where Y is a power of 2, 13884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (isKnownToBeAPowerOfTwo(Op1, DL, /*OrZero*/ true, 0, AC, &I, DT)) { 13897a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Constant *N1 = Constant::getAllOnesValue(I.getType()); 1390a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer Value *Add = Builder->CreateAdd(Op1, N1); 13917a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::CreateAnd(Op0, Add); 1392d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1393d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 139475681bb302e524460edb7c8c5c6e98792b5027a2Nick Lewycky // 1 urem X -> zext(X != 1) 139575681bb302e524460edb7c8c5c6e98792b5027a2Nick Lewycky if (match(Op0, m_One())) { 139675681bb302e524460edb7c8c5c6e98792b5027a2Nick Lewycky Value *Cmp = Builder->CreateICmpNE(Op1, Op0); 139775681bb302e524460edb7c8c5c6e98792b5027a2Nick Lewycky Value *Ext = Builder->CreateZExt(Cmp, I.getType()); 139875681bb302e524460edb7c8c5c6e98792b5027a2Nick Lewycky return ReplaceInstUsesWith(I, Ext); 139975681bb302e524460edb7c8c5c6e98792b5027a2Nick Lewycky } 140075681bb302e524460edb7c8c5c6e98792b5027a2Nick Lewycky 1401dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1402d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 1403d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1404d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitSRem(BinaryOperator &I) { 1405d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1406d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1407dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 1408dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 1409dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1410ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = SimplifySRemInst(Op0, Op1, DL, TLI, DT, AC)) 1411f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return ReplaceInstUsesWith(I, V); 1412f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands 1413d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Handle the integer rem common cases 1414d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *Common = commonIRemTransforms(I)) 1415d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return Common; 141603fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 141737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines { 141837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const APInt *Y; 141937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // X % -Y -> X % Y 142037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (match(Op1, m_APInt(Y)) && Y->isNegative() && !Y->isMinSignedValue()) { 1421d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Worklist.AddValue(I.getOperand(1)); 142237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines I.setOperand(1, ConstantInt::get(I.getType(), -*Y)); 1423d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return &I; 1424d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 142537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 1426d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1427d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If the sign bits of both operands are zero (i.e. we can prove they are 1428d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // unsigned inputs), turn this into a urem. 1429b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy()) { 1430d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 143137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (MaskedValueIsZero(Op1, Mask, 0, &I) && 143237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines MaskedValueIsZero(Op0, Mask, 0, &I)) { 143394c22716d60ff5edf6a98a3c67e0faa001be1142Sylvestre Ledru // X srem Y -> X urem Y, iff X and Y don't have sign bit set 1434d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 1435d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1436d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1437d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1438d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If it's a constant vector, flip any negative values positive. 1439a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) { 1440a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner Constant *C = cast<Constant>(Op1); 1441a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner unsigned VWidth = C->getType()->getVectorNumElements(); 1442d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1443d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner bool hasNegative = false; 1444a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner bool hasMissing = false; 1445a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner for (unsigned i = 0; i != VWidth; ++i) { 1446a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner Constant *Elt = C->getAggregateElement(i); 1447dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Elt) { 1448a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner hasMissing = true; 1449a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner break; 1450a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner } 1451a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner 1452a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt)) 1453c73b24db5f6226ed44ebc44ce1c25bb357206623Chris Lattner if (RHS->isNegative()) 1454d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner hasNegative = true; 1455a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner } 1456d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1457a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (hasNegative && !hasMissing) { 14584ca829e89567f002fc74eb0e3e532a7c7662e031Chris Lattner SmallVector<Constant *, 16> Elts(VWidth); 1459d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner for (unsigned i = 0; i != VWidth; ++i) { 14607302d80490feabfc8a01bee0fa698aab55169544Chris Lattner Elts[i] = C->getAggregateElement(i); // Handle undef, etc. 1461a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) { 1462c73b24db5f6226ed44ebc44ce1c25bb357206623Chris Lattner if (RHS->isNegative()) 1463d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 1464d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1465d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1466d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1467d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Constant *NewRHSV = ConstantVector::get(Elts); 1468a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (NewRHSV != C) { // Don't loop on -MININT 1469d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Worklist.AddValue(I.getOperand(1)); 1470d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner I.setOperand(1, NewRHSV); 1471d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return &I; 1472d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1473d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1474d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1475d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1476dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1477d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 1478d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1479d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitFRem(BinaryOperator &I) { 1480f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1481d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1482dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyVectorOp(I)) 1483dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, V); 1484dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1485ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Value *V = SimplifyFRemInst(Op0, Op1, I.getFastMathFlags(), 1486ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines DL, TLI, DT, AC)) 1487f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return ReplaceInstUsesWith(I, V); 1488f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands 1489f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands // Handle cases involving: rem X, (select Cond, Y, Z) 1490f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 1491f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return &I; 1492f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands 1493dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 1494f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands} 1495