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 15d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner#include "InstCombine.h" 16d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner#include "llvm/IntrinsicInst.h" 1782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands#include "llvm/Analysis/InstructionSimplify.h" 18d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner#include "llvm/Support/PatternMatch.h" 19d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattnerusing namespace llvm; 20d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattnerusing namespace PatternMatch; 21d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 221add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner 231add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner/// simplifyValueKnownNonZero - The specific integer value is used in a context 241add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner/// where it is known to be non-zero. If this allows us to simplify the 251add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner/// computation, do so and return the new operand, otherwise return null. 261add46ddfa38f23669cb02de342fdb59a8709245Chris Lattnerstatic Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC) { 271add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner // If V has multiple uses, then we would have to do more analysis to determine 281add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner // if this is safe. For example, the use could be in dynamically unreached 291add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner // code. 301add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner if (!V->hasOneUse()) return 0; 311add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner 32613f1a3994ef6f009c93264f6708830249130896Chris Lattner bool MadeChange = false; 33613f1a3994ef6f009c93264f6708830249130896Chris Lattner 34613f1a3994ef6f009c93264f6708830249130896Chris Lattner // ((1 << A) >>u B) --> (1 << (A-B)) 35613f1a3994ef6f009c93264f6708830249130896Chris Lattner // Because V cannot be zero, we know that B is less than A. 36613f1a3994ef6f009c93264f6708830249130896Chris Lattner Value *A = 0, *B = 0, *PowerOf2 = 0; 37613f1a3994ef6f009c93264f6708830249130896Chris Lattner if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(PowerOf2), m_Value(A))), 38613f1a3994ef6f009c93264f6708830249130896Chris Lattner m_Value(B))) && 39613f1a3994ef6f009c93264f6708830249130896Chris Lattner // The "1" can be any value known to be a power of 2. 40613f1a3994ef6f009c93264f6708830249130896Chris Lattner isPowerOfTwo(PowerOf2, IC.getTargetData())) { 41a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer A = IC.Builder->CreateSub(A, B); 42613f1a3994ef6f009c93264f6708830249130896Chris Lattner return IC.Builder->CreateShl(PowerOf2, A); 43613f1a3994ef6f009c93264f6708830249130896Chris Lattner } 4405cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner 4505cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it 4605cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner // inexact. Similarly for <<. 4705cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner if (BinaryOperator *I = dyn_cast<BinaryOperator>(V)) 4805cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner if (I->isLogicalShift() && 4905cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner isPowerOfTwo(I->getOperand(0), IC.getTargetData())) { 50613f1a3994ef6f009c93264f6708830249130896Chris Lattner // We know that this is an exact/nuw shift and that the input is a 51613f1a3994ef6f009c93264f6708830249130896Chris Lattner // non-zero context as well. 52613f1a3994ef6f009c93264f6708830249130896Chris Lattner if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC)) { 53613f1a3994ef6f009c93264f6708830249130896Chris Lattner I->setOperand(0, V2); 54613f1a3994ef6f009c93264f6708830249130896Chris Lattner MadeChange = true; 55613f1a3994ef6f009c93264f6708830249130896Chris Lattner } 56613f1a3994ef6f009c93264f6708830249130896Chris Lattner 5705cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner if (I->getOpcode() == Instruction::LShr && !I->isExact()) { 5805cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner I->setIsExact(); 59613f1a3994ef6f009c93264f6708830249130896Chris Lattner MadeChange = true; 6005cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner } 6105cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner 6205cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) { 6305cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner I->setHasNoUnsignedWrap(); 64613f1a3994ef6f009c93264f6708830249130896Chris Lattner MadeChange = true; 6505cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner } 6605cd88656135255b545d24adb51c2ba1b5c8b99eChris Lattner } 67613f1a3994ef6f009c93264f6708830249130896Chris Lattner 686c9b8d3d411b0ee65263dc41d2b953fe118cf31eChris Lattner // TODO: Lots more we could do here: 696c9b8d3d411b0ee65263dc41d2b953fe118cf31eChris Lattner // If V is a phi node, we can call this on each of its operands. 706c9b8d3d411b0ee65263dc41d2b953fe118cf31eChris Lattner // "select cond, X, 0" can simplify to "X". 716c9b8d3d411b0ee65263dc41d2b953fe118cf31eChris Lattner 72613f1a3994ef6f009c93264f6708830249130896Chris Lattner return MadeChange ? V : 0; 731add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner} 741add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner 751add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner 76d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// MultiplyOverflows - True if the multiply can not be expressed in an int 77d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// this size. 78d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattnerstatic bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) { 79d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner uint32_t W = C1->getBitWidth(); 80d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner APInt LHSExt = C1->getValue(), RHSExt = C2->getValue(); 81d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (sign) { 8240f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad LHSExt = LHSExt.sext(W * 2); 8340f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad RHSExt = RHSExt.sext(W * 2); 84d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } else { 8540f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad LHSExt = LHSExt.zext(W * 2); 8640f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad RHSExt = RHSExt.zext(W * 2); 87d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 88d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 89d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner APInt MulExt = LHSExt * RHSExt; 90d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 91d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (!sign) 92d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return MulExt.ugt(APInt::getLowBitsSet(W * 2, W)); 93d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 94d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner APInt Min = APInt::getSignedMinValue(W).sext(W * 2); 95d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner APInt Max = APInt::getSignedMaxValue(W).sext(W * 2); 96d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return MulExt.slt(Min) || MulExt.sgt(Max); 97d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 98d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 99d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitMul(BinaryOperator &I) { 100096aa79276b8527a3cbbb3691e40e729dea09523Duncan Sands bool Changed = SimplifyAssociativeOrCommutative(I); 101d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 102d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 10382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = SimplifyMulInst(Op0, Op1, TD)) 10482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return ReplaceInstUsesWith(I, V); 105d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 10637bf92b5238434b00fde79347ba5336e7554e562Duncan Sands if (Value *V = SimplifyUsingDistributiveLaws(I)) 10737bf92b5238434b00fde79347ba5336e7554e562Duncan Sands return ReplaceInstUsesWith(I, V); 10837bf92b5238434b00fde79347ba5336e7554e562Duncan Sands 1097a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (match(Op1, m_AllOnes())) // X * -1 == 0 - X 1107a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::CreateNeg(Op0, I.getName()); 1117a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner 1127a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 1137a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner 1147a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // ((X << C1)*C2) == (X * (C2 << C1)) 1157a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (BinaryOperator *SI = dyn_cast<BinaryOperator>(Op0)) 1167a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (SI->getOpcode() == Instruction::Shl) 1177a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1))) 1187a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::CreateMul(SI->getOperand(0), 1197a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner ConstantExpr::getShl(CI, ShOp)); 1207a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner 1217a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner const APInt &Val = CI->getValue(); 1227a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (Val.isPowerOf2()) { // Replace X*(2^C) with X << C 1237a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Constant *NewCst = ConstantInt::get(Op0->getType(), Val.logBase2()); 1247a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner BinaryOperator *Shl = BinaryOperator::CreateShl(Op0, NewCst); 1257a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (I.hasNoSignedWrap()) Shl->setHasNoSignedWrap(); 1267a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (I.hasNoUnsignedWrap()) Shl->setHasNoUnsignedWrap(); 1277a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return Shl; 128d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 129d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 1307a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // Canonicalize (X+C1)*CI -> X*CI+C1*CI. 1317a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner { Value *X; ConstantInt *C1; 1327a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (Op0->hasOneUse() && 1337a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner match(Op0, m_Add(m_Value(X), m_ConstantInt(C1)))) { 134a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer Value *Add = Builder->CreateMul(X, CI); 1357a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::CreateAdd(Add, Builder->CreateMul(C1, CI)); 136d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 1377a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 138acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings 139f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n 140f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n 141f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings // The "* (2**n)" thus becomes a potential shifting opportunity. 142acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings { 143acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings const APInt & Val = CI->getValue(); 144acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings const APInt &PosVal = Val.abs(); 145acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings if (Val.isNegative() && PosVal.isPowerOf2()) { 146f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings Value *X = 0, *Y = 0; 147f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings if (Op0->hasOneUse()) { 148f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings ConstantInt *C1; 149f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings Value *Sub = 0; 150f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings if (match(Op0, m_Sub(m_Value(Y), m_Value(X)))) 151f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings Sub = Builder->CreateSub(X, Y, "suba"); 152f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1)))) 153f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings Sub = Builder->CreateSub(Builder->CreateNeg(C1), Y, "subc"); 154f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings if (Sub) 155f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings return 156f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings BinaryOperator::CreateMul(Sub, 157f1002828fdaffa4e005a81f269c77fe72951f39fStuart Hastings ConstantInt::get(Y->getType(), PosVal)); 158acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings } 159acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings } 160acbf107d9b9ffeddbcc3d015107c6faff439ee9bStuart Hastings } 1617a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 1627a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner 1637a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // Simplify mul instructions with a constant RHS. 1647a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (isa<Constant>(Op1)) { 165d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Try to fold constant mul into select arguments. 166d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 167d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 168d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return R; 169d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 170d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (isa<PHINode>(Op0)) 171d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 172d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return NV; 173d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 174d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 175d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y 176d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Value *Op1v = dyn_castNegVal(Op1)) 177d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateMul(Op0v, Op1v); 178d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 179d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // (X / Y) * Y = X - (X % Y) 180d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // (X / Y) * -Y = (X % Y) - X 181d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner { 182d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op1C = Op1; 183d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0); 184d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (!BO || 185d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner (BO->getOpcode() != Instruction::UDiv && 186d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BO->getOpcode() != Instruction::SDiv)) { 187d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Op1C = Op0; 188d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BO = dyn_cast<BinaryOperator>(Op1); 189d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 190d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Neg = dyn_castNegVal(Op1C); 191d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (BO && BO->hasOneUse() && 192d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) && 193d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner (BO->getOpcode() == Instruction::UDiv || 194d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BO->getOpcode() == Instruction::SDiv)) { 195d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1); 196d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 19735bda8914c0d1c02a6f90f42e7810c83150737e1Chris Lattner // If the division is exact, X % Y is zero, so we end up with X or -X. 19835bda8914c0d1c02a6f90f42e7810c83150737e1Chris Lattner if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO)) 199d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SDiv->isExact()) { 200d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Op1BO == Op1C) 201d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return ReplaceInstUsesWith(I, Op0BO); 202d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateNeg(Op0BO); 203d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 204d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 205d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Rem; 206d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (BO->getOpcode() == Instruction::UDiv) 207d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Rem = Builder->CreateURem(Op0BO, Op1BO); 208d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner else 209d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Rem = Builder->CreateSRem(Op0BO, Op1BO); 210d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Rem->takeName(BO); 211d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 212d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Op1BO == Op1C) 213d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateSub(Op0BO, Rem); 214d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateSub(Rem, Op0BO); 215d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 216d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 217d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 218d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner /// i1 mul -> i1 and. 219b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy(1)) 220d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateAnd(Op0, Op1); 221d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 222d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X*(1 << Y) --> X << Y 223d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // (1 << Y)*X --> X << Y 224d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner { 225d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Y; 226d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (match(Op0, m_Shl(m_One(), m_Value(Y)))) 227d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateShl(Op1, Y); 228d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (match(Op1, m_Shl(m_One(), m_Value(Y)))) 229d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateShl(Op0, Y); 230d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 231d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 232d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If one of the operands of the multiply is a cast from a boolean value, then 233d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // we know the bool is either zero or one, so this is a 'masking' multiply. 234d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X * Y (where Y is 0 or 1) -> X & (0-Y) 2351df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (!I.getType()->isVectorTy()) { 236d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // -2 is "-1 << 1" so it is all bits set except the low one. 237d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true); 238d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 239d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *BoolCast = 0, *OtherOp = 0; 240d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (MaskedValueIsZero(Op0, Negative2)) 241d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BoolCast = Op0, OtherOp = Op1; 242d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner else if (MaskedValueIsZero(Op1, Negative2)) 243d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BoolCast = Op1, OtherOp = Op0; 244d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 245d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (BoolCast) { 246d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()), 247a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer BoolCast); 248d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateAnd(V, OtherOp); 249d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 250d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 251d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 252d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return Changed ? &I : 0; 253d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 254d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 255d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitFMul(BinaryOperator &I) { 256096aa79276b8527a3cbbb3691e40e729dea09523Duncan Sands bool Changed = SimplifyAssociativeOrCommutative(I); 257d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 258d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 2597302d80490feabfc8a01bee0fa698aab55169544Chris Lattner // Simplify mul instructions with a constant RHS. 260d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 261d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1C)) { 262d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // "In IEEE floating point, x*1 is not equivalent to x for nans. However, 263d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // ANSI says we can drop signals, so we can do this anyway." (from GCC) 264d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Op1F->isExactlyValue(1.0)) 265a9445e11c553855a6caacbbbf77a9b993ecc651eDan Gohman return ReplaceInstUsesWith(I, Op0); // Eliminate 'fmul double %X, 1.0' 2667302d80490feabfc8a01bee0fa698aab55169544Chris Lattner } else if (ConstantDataVector *Op1V = dyn_cast<ConstantDataVector>(Op1C)) { 2677302d80490feabfc8a01bee0fa698aab55169544Chris Lattner // As above, vector X*splat(1.0) -> X in all defined cases. 2687302d80490feabfc8a01bee0fa698aab55169544Chris Lattner if (ConstantFP *F = dyn_cast_or_null<ConstantFP>(Op1V->getSplatValue())) 2697302d80490feabfc8a01bee0fa698aab55169544Chris Lattner if (F->isExactlyValue(1.0)) 2707302d80490feabfc8a01bee0fa698aab55169544Chris Lattner return ReplaceInstUsesWith(I, Op0); 271d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 272d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 273d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Try to fold constant mul into select arguments. 274d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 275d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 276d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return R; 277d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 278d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (isa<PHINode>(Op0)) 279d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 280d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return NV; 281d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 282d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 283d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Value *Op0v = dyn_castFNegVal(Op0)) // -X * -Y = X*Y 284d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Value *Op1v = dyn_castFNegVal(Op1)) 285d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateFMul(Op0v, Op1v); 286d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 287d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return Changed ? &I : 0; 288d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 289d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 290d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select 291d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// instruction. 292d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattnerbool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { 293d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner SelectInst *SI = cast<SelectInst>(I.getOperand(1)); 294d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 295d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 296d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner int NonNullOperand = -1; 297d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) 298d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (ST->isNullValue()) 299d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner NonNullOperand = 2; 300d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 301d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) 302d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (ST->isNullValue()) 303d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner NonNullOperand = 1; 304d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 305d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (NonNullOperand == -1) 306d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return false; 307d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 308d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *SelectCond = SI->getOperand(0); 309d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 310d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Change the div/rem to use 'Y' instead of the select. 311d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner I.setOperand(1, SI->getOperand(NonNullOperand)); 312d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 313d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Okay, we know we replace the operand of the div/rem with 'Y' with no 314d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // problem. However, the select, or the condition of the select may have 315d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // multiple uses. Based on our knowledge that the operand must be non-zero, 316d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // propagate the known value for the select into other uses of it, and 317d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // propagate a known value of the condition into its other users. 318d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 319d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If the select and condition only have a single use, don't bother with this, 320d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // early exit. 321d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SI->use_empty() && SelectCond->hasOneUse()) 322d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return true; 323d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 324d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Scan the current block backward, looking for other uses of SI. 325d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin(); 326d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 327d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner while (BBI != BBFront) { 328d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner --BBI; 329d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If we found a call to a function, we can't assume it will return, so 330d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // information from below it cannot be propagated above it. 331d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) 332d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner break; 333d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 334d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Replace uses of the select or its condition with the known values. 335d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); 336d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner I != E; ++I) { 337d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (*I == SI) { 338d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner *I = SI->getOperand(NonNullOperand); 339d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Worklist.Add(BBI); 340d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } else if (*I == SelectCond) { 341d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner *I = NonNullOperand == 1 ? ConstantInt::getTrue(BBI->getContext()) : 342d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner ConstantInt::getFalse(BBI->getContext()); 343d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Worklist.Add(BBI); 344d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 345d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 346d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 347d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If we past the instruction, quit looking for it. 348d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (&*BBI == SI) 349d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner SI = 0; 350d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (&*BBI == SelectCond) 351d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner SelectCond = 0; 352d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 353d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If we ran out of things to eliminate, break out of the loop. 354d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SelectCond == 0 && SI == 0) 355d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner break; 356d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 357d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 358d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return true; 359d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 360d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 361d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 362d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// This function implements the transforms common to both integer division 363d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// instructions (udiv and sdiv). It is called by the visitors to those integer 364d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// division instructions. 365d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// @brief Common integer divide transforms 366d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { 367d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 368d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 3691add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner // The RHS is known non-zero. 3701add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 3711add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner I.setOperand(1, V); 3721add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner return &I; 3731add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner } 3741add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner 375d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Handle cases involving: [su]div X, (select Cond, Y, Z) 376d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // This does not apply for fdiv. 377d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 378d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return &I; 379d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 380d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 381d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // (X / C1) / C2 -> X / (C1*C2) 382d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *LHS = dyn_cast<Instruction>(Op0)) 383d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode()) 384d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) { 385d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (MultiplyOverflows(RHS, LHSRHS, 386d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner I.getOpcode()==Instruction::SDiv)) 387d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 3887a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::Create(I.getOpcode(), LHS->getOperand(0), 3897a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner ConstantExpr::getMul(RHS, LHSRHS)); 390d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 391d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 392d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (!RHS->isZero()) { // avoid X udiv 0 393d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 394d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 395d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return R; 396d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (isa<PHINode>(Op0)) 397d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 398d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return NV; 399d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 400d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 401d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 40223b02cd0315625d9d586118abcc972053298d50bBenjamin Kramer // See if we can fold away this div instruction. 40323b02cd0315625d9d586118abcc972053298d50bBenjamin Kramer if (SimplifyDemandedInstructionBits(I)) 40423b02cd0315625d9d586118abcc972053298d50bBenjamin Kramer return &I; 40523b02cd0315625d9d586118abcc972053298d50bBenjamin Kramer 406593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y 407593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands Value *X = 0, *Z = 0; 408593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 409593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands bool isSigned = I.getOpcode() == Instruction::SDiv; 410593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || 411593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) 412593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return BinaryOperator::Create(I.getOpcode(), X, Op1); 413d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 414d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 415d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return 0; 416d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 417d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 4187d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer/// dyn_castZExtVal - Checks if V is a zext or constant that can 4197d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer/// be truncated to Ty without losing bits. 420db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnerstatic Value *dyn_castZExtVal(Value *V, Type *Ty) { 4217d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) { 4227d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (Z->getSrcTy() == Ty) 4237d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer return Z->getOperand(0); 4247d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) { 4257d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth()) 4267d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer return ConstantExpr::getTrunc(C, Ty); 4277d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer } 4287d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer return 0; 4297d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer} 4307d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer 431d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitUDiv(BinaryOperator &I) { 432d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 433d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 434593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (Value *V = SimplifyUDivInst(Op0, Op1, TD)) 435593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return ReplaceInstUsesWith(I, V); 436593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 437d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Handle the integer div common cases 438d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *Common = commonIDivTransforms(I)) 439d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return Common; 440a29fc806fe02cea76f7896b7e344bb919dd7ac25Pete Cooper 441a29fc806fe02cea76f7896b7e344bb919dd7ac25Pete Cooper { 4425b39620e2da1451c5db50559085ae4b86a152936Owen Anderson // X udiv 2^C -> X >> C 443d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Check to see if this is an unsigned division with an exact power of 2, 444d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // if so, convert to a right shift. 445a29fc806fe02cea76f7896b7e344bb919dd7ac25Pete Cooper const APInt *C; 446a29fc806fe02cea76f7896b7e344bb919dd7ac25Pete Cooper if (match(Op1, m_Power2(C))) { 4477a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner BinaryOperator *LShr = 448a29fc806fe02cea76f7896b7e344bb919dd7ac25Pete Cooper BinaryOperator::CreateLShr(Op0, 449a29fc806fe02cea76f7896b7e344bb919dd7ac25Pete Cooper ConstantInt::get(Op0->getType(), 450a29fc806fe02cea76f7896b7e344bb919dd7ac25Pete Cooper C->logBase2())); 4517a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (I.isExact()) LShr->setIsExact(); 4527a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return LShr; 4537a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 454a29fc806fe02cea76f7896b7e344bb919dd7ac25Pete Cooper } 455d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 456a29fc806fe02cea76f7896b7e344bb919dd7ac25Pete Cooper if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) { 457d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X udiv C, where C >= signbit 458d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (C->getValue().isNegative()) { 4597a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Value *IC = Builder->CreateICmpULT(Op0, C); 460d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return SelectInst::Create(IC, Constant::getNullValue(I.getType()), 461d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner ConstantInt::get(I.getType(), 1)); 462d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 463d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 464d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 465c81fe9cab545a93a61c059b1c2813f622aef43aeBenjamin Kramer // (x lshr C1) udiv C2 --> x udiv (C2 << C1) 466a694e2a6910a33596ca706e2c6fc713f02b64c50Nadav Rotem if (ConstantInt *C2 = dyn_cast<ConstantInt>(Op1)) { 467aac7c650a6cac09d42c5fda8d3761bc9c871ff03Benjamin Kramer Value *X; 468aac7c650a6cac09d42c5fda8d3761bc9c871ff03Benjamin Kramer ConstantInt *C1; 469aac7c650a6cac09d42c5fda8d3761bc9c871ff03Benjamin Kramer if (match(Op0, m_LShr(m_Value(X), m_ConstantInt(C1)))) { 47037dca6331d6bfadfb80b3c68a1cabd6bdf1a13beBenjamin Kramer APInt NC = C2->getValue().shl(C1->getLimitedValue(C1->getBitWidth()-1)); 471aac7c650a6cac09d42c5fda8d3761bc9c871ff03Benjamin Kramer return BinaryOperator::CreateUDiv(X, Builder->getInt(NC)); 4729753f0b9b4ab33919c5010acb6a7b2dc1e875affNadav Rotem } 4739753f0b9b4ab33919c5010acb6a7b2dc1e875affNadav Rotem } 4749753f0b9b4ab33919c5010acb6a7b2dc1e875affNadav Rotem 475d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 4767a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner { const APInt *CI; Value *N; 4772a5422b1a6955977d05af48222c86c77c7549484Evan Cheng if (match(Op1, m_Shl(m_Power2(CI), m_Value(N))) || 4782a5422b1a6955977d05af48222c86c77c7549484Evan Cheng match(Op1, m_ZExt(m_Shl(m_Power2(CI), m_Value(N))))) { 4797a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (*CI != 1) 480a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer N = Builder->CreateAdd(N, ConstantInt::get(I.getType(),CI->logBase2())); 4812a5422b1a6955977d05af48222c86c77c7549484Evan Cheng if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1)) 4822a5422b1a6955977d05af48222c86c77c7549484Evan Cheng N = Builder->CreateZExt(N, Z->getDestTy()); 4837a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (I.isExact()) 4847a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::CreateExactLShr(Op0, N); 4857a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::CreateLShr(Op0, N); 486d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 487d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 488d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 489d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // udiv X, (Select Cond, C1, C2) --> Select Cond, (shr X, C1), (shr X, C2) 490d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // where C1&C2 are powers of two. 4917a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner { Value *Cond; const APInt *C1, *C2; 4927a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) { 4937a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // Construct the "on true" case of the select 4947a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Value *TSI = Builder->CreateLShr(Op0, C1->logBase2(), Op1->getName()+".t", 4957a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner I.isExact()); 496d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 4977a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // Construct the "on false" case of the select 4987a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Value *FSI = Builder->CreateLShr(Op0, C2->logBase2(), Op1->getName()+".f", 4997a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner I.isExact()); 5007a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner 5017a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // construct the select instruction and return it. 5027a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return SelectInst::Create(Cond, TSI, FSI); 5037a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 5047a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 5057d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer 5067d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer // (zext A) udiv (zext B) --> zext (A udiv B) 5077d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 5087d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 5097d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer return new ZExtInst(Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", 5107d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer I.isExact()), 5117d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer I.getType()); 5127d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer 513d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return 0; 514d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 515d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 516d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitSDiv(BinaryOperator &I) { 517d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 518d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 519593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (Value *V = SimplifySDivInst(Op0, Op1, TD)) 520593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return ReplaceInstUsesWith(I, V); 521593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 522d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Handle the integer div common cases 523d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *Common = commonIDivTransforms(I)) 524d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return Common; 525d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 526d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 527d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // sdiv X, -1 == -X 528d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (RHS->isAllOnesValue()) 529d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateNeg(Op0); 530d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 5317a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // sdiv X, C --> ashr exact X, log2(C) 5327a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (I.isExact() && RHS->getValue().isNonNegative() && 533d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner RHS->getValue().isPowerOf2()) { 534d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *ShAmt = llvm::ConstantInt::get(RHS->getType(), 535d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner RHS->getValue().exactLogBase2()); 5367a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName()); 537d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 538d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 539d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // -X/C --> X/-C provided the negation doesn't overflow. 540d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SubOperator *Sub = dyn_cast<SubOperator>(Op0)) 5417a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (match(Sub->getOperand(0), m_Zero()) && Sub->hasNoSignedWrap()) 542d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateSDiv(Sub->getOperand(1), 543d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner ConstantExpr::getNeg(RHS)); 544d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 545d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 546d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If the sign bits of both operands are zero (i.e. we can prove they are 547d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // unsigned inputs), turn this into a udiv. 548b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy()) { 549d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 550d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (MaskedValueIsZero(Op0, Mask)) { 551d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (MaskedValueIsZero(Op1, Mask)) { 552d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set 553d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 554d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 5557a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner 5567a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (match(Op1, m_Shl(m_Power2(), m_Value()))) { 557d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 558d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Safe because the only negative value (1 << Y) can take on is 559d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 560d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // the sign bit set. 561d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 562d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 563d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 564d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 565d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 566d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return 0; 567d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 568d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 56931726c154dafa9fef08b1bcac9822c2a4618ec19Frits van BommelInstruction *InstCombiner::visitFDiv(BinaryOperator &I) { 57031726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 57131726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel 57231726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel if (Value *V = SimplifyFDivInst(Op0, Op1, TD)) 57331726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel return ReplaceInstUsesWith(I, V); 57431726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel 575546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) { 576546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer const APFloat &Op1F = Op1C->getValueAPF(); 577546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer 578546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer // If the divisor has an exact multiplicative inverse we can turn the fdiv 579546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer // into a cheaper fmul. 580546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer APFloat Reciprocal(Op1F.getSemantics()); 581546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer if (Op1F.getExactInverse(&Reciprocal)) { 582546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer ConstantFP *RFP = ConstantFP::get(Builder->getContext(), Reciprocal); 583546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer return BinaryOperator::CreateFMul(Op0, RFP); 584546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer } 585546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer } 586546739656ec9469499d3866d87dca6fdbcf2eee0Benjamin Kramer 58731726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel return 0; 58831726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel} 58931726c154dafa9fef08b1bcac9822c2a4618ec19Frits van Bommel 590d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// This function implements the transforms common to both integer remainder 591d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// instructions (urem and srem). It is called by the visitors to those integer 592d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// remainder instructions. 593d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner/// @brief Common integer remainder transforms 594d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { 595d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 596d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 5971add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner // The RHS is known non-zero. 5981add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 5991add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner I.setOperand(1, V); 6001add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner return &I; 6011add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner } 6021add46ddfa38f23669cb02de342fdb59a8709245Chris Lattner 603f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands // Handle cases involving: rem X, (select Cond, Y, Z) 604f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 605f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return &I; 606d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 60700676a6df1116f47a015de589f911d2b5b7f4117Duncan Sands if (isa<ConstantInt>(Op1)) { 608d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 609d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 610d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 611d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return R; 612d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } else if (isa<PHINode>(Op0I)) { 613d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 614d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return NV; 615d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 616d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 617d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // See if we can fold away this rem instruction. 618d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (SimplifyDemandedInstructionBits(I)) 619d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return &I; 620d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 621d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 622d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 623d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return 0; 624d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 625d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 626d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitURem(BinaryOperator &I) { 627d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 628d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 629f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands if (Value *V = SimplifyURemInst(Op0, Op1, TD)) 630f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return ReplaceInstUsesWith(I, V); 631f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands 632d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *common = commonIRemTransforms(I)) 633d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return common; 634d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 6357a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // X urem C^2 -> X and C-1 6367a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner { const APInt *C; 6377a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (match(Op1, m_Power2(C))) 6387a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::CreateAnd(Op0, 6397a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner ConstantInt::get(I.getType(), *C-1)); 640d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 641d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 6427a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // Turn A % (C << N), where C is 2^k, into A & ((C << N)-1) 6437a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (match(Op1, m_Shl(m_Power2(), m_Value()))) { 6447a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Constant *N1 = Constant::getAllOnesValue(I.getType()); 645a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer Value *Add = Builder->CreateAdd(Op1, N1); 6467a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return BinaryOperator::CreateAnd(Op0, Add); 647d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 648d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 6497a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // urem X, (select Cond, 2^C1, 2^C2) --> 6507a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // select Cond, (and X, C1-1), (and X, C2-1) 6517a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner // when C1&C2 are powers of two. 6527a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner { Value *Cond; const APInt *C1, *C2; 6537a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) { 6547a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Value *TrueAnd = Builder->CreateAnd(Op0, *C1-1, Op1->getName()+".t"); 6557a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner Value *FalseAnd = Builder->CreateAnd(Op0, *C2-1, Op1->getName()+".f"); 6567a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner return SelectInst::Create(Cond, TrueAnd, FalseAnd); 6577a6aa1a3919af8ece92702c36dc552d81be9151aChris Lattner } 658d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 6597d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer 6607d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer // (zext A) urem (zext B) --> zext (A urem B) 6617d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 6627d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 6637d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), 6647d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer I.getType()); 6657d6eb5a018ef4352730d63dc202cfaf013f489feBenjamin Kramer 666d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return 0; 667d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 668d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 669d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitSRem(BinaryOperator &I) { 670d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 671d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 672f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands if (Value *V = SimplifySRemInst(Op0, Op1, TD)) 673f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return ReplaceInstUsesWith(I, V); 674f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands 675d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // Handle the integer rem common cases 676d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Instruction *Common = commonIRemTransforms(I)) 677d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return Common; 678d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 679d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (Value *RHSNeg = dyn_castNegVal(Op1)) 680d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (!isa<Constant>(RHSNeg) || 681d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner (isa<ConstantInt>(RHSNeg) && 682d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner cast<ConstantInt>(RHSNeg)->getValue().isStrictlyPositive())) { 683d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X % -Y -> X % Y 684d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Worklist.AddValue(I.getOperand(1)); 685d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner I.setOperand(1, RHSNeg); 686d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return &I; 687d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 688d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 689d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If the sign bits of both operands are zero (i.e. we can prove they are 690d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // unsigned inputs), turn this into a urem. 691b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy()) { 692d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 693d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner if (MaskedValueIsZero(Op1, Mask) && MaskedValueIsZero(Op0, Mask)) { 694d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // X srem Y -> X urem Y, iff X and Y don't have sign bit set 695d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 696d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 697d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 698d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 699d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner // If it's a constant vector, flip any negative values positive. 700a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) { 701a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner Constant *C = cast<Constant>(Op1); 702a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner unsigned VWidth = C->getType()->getVectorNumElements(); 703d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 704d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner bool hasNegative = false; 705a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner bool hasMissing = false; 706a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner for (unsigned i = 0; i != VWidth; ++i) { 707a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner Constant *Elt = C->getAggregateElement(i); 708a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (Elt == 0) { 709a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner hasMissing = true; 710a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner break; 711a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner } 712a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner 713a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt)) 714c73b24db5f6226ed44ebc44ce1c25bb357206623Chris Lattner if (RHS->isNegative()) 715d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner hasNegative = true; 716a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner } 717d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 718a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (hasNegative && !hasMissing) { 7194ca829e89567f002fc74eb0e3e532a7c7662e031Chris Lattner SmallVector<Constant *, 16> Elts(VWidth); 720d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner for (unsigned i = 0; i != VWidth; ++i) { 7217302d80490feabfc8a01bee0fa698aab55169544Chris Lattner Elts[i] = C->getAggregateElement(i); // Handle undef, etc. 722a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) { 723c73b24db5f6226ed44ebc44ce1c25bb357206623Chris Lattner if (RHS->isNegative()) 724d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 725d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 726d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 727d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 728d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Constant *NewRHSV = ConstantVector::get(Elts); 729a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (NewRHSV != C) { // Don't loop on -MININT 730d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner Worklist.AddValue(I.getOperand(1)); 731d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner I.setOperand(1, NewRHSV); 732d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return &I; 733d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 734d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 735d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner } 736d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 737d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner return 0; 738d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner} 739d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 740d12c27ce0079ba14e73e0c422a30dac68c631a23Chris LattnerInstruction *InstCombiner::visitFRem(BinaryOperator &I) { 741f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 742d12c27ce0079ba14e73e0c422a30dac68c631a23Chris Lattner 743f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands if (Value *V = SimplifyFRemInst(Op0, Op1, TD)) 744f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return ReplaceInstUsesWith(I, V); 745f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands 746f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands // Handle cases involving: rem X, (select Cond, Y, Z) 747f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 748f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return &I; 749f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands 750f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands return 0; 751f24ed77d2416b66178d8ff1d807858dfab37ca18Duncan Sands} 752