InstCombineAddSub.cpp revision b0bc6c361da9009e8414efde317d9bbff755f6c0
153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner//===- InstCombineAddSub.cpp ----------------------------------------------===// 253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// The LLVM Compiler Infrastructure 453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// This file is distributed under the University of Illinois Open Source 653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// License. See LICENSE.TXT for details. 753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner//===----------------------------------------------------------------------===// 953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 1053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// This file implements the visit functions for add, fadd, sub, and fsub. 1153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 1253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner//===----------------------------------------------------------------------===// 1353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 1453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner#include "InstCombine.h" 1553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner#include "llvm/Analysis/InstructionSimplify.h" 1653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner#include "llvm/Target/TargetData.h" 1753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 1853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner#include "llvm/Support/PatternMatch.h" 1953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerusing namespace llvm; 2053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerusing namespace PatternMatch; 2153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 2253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// AddOne - Add one to a ConstantInt. 2353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerstatic Constant *AddOne(Constant *C) { 2453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1)); 2553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 2653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// SubOne - Subtract one from a ConstantInt. 2753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerstatic Constant *SubOne(ConstantInt *C) { 2853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ConstantInt::get(C->getContext(), C->getValue()-1); 2953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 3053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 3153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 3253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// dyn_castFoldableMul - If this value is a multiply that can be folded into 3353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// other computations (because it has a constant operand), return the 3453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// non-constant operand of the multiply, and set CST to point to the multiplier. 3553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// Otherwise, return null. 3653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner// 3753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerstatic inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) { 38b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (!V->hasOneUse() || !V->getType()->isIntegerTy()) 393168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner return 0; 403168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner 413168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 423168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner if (I == 0) return 0; 433168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner 443168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner if (I->getOpcode() == Instruction::Mul) 453168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) 463168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner return I->getOperand(0); 473168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner if (I->getOpcode() == Instruction::Shl) 483168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) { 493168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner // The multiplier is really 1 << CST. 503168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 513168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner uint32_t CSTVal = CST->getLimitedValue(BitWidth); 523168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner CST = ConstantInt::get(V->getType()->getContext(), 533168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner APInt(BitWidth, 1).shl(CSTVal)); 543168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner return I->getOperand(0); 5553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 5653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 5753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 5853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 5953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 6053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// WillNotOverflowSignedAdd - Return true if we can prove that: 6153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// (sext (add LHS, RHS)) === (add (sext LHS), (sext RHS)) 6253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// This basically requires proving that the add in the original type would not 6353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// overflow to change the sign bit or have a carry out. 6453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattnerbool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) { 6553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // There are different heuristics we can use for this. Here are some simple 6653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // ones. 6753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 6853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Add has the property that adding any two 2's complement numbers can only 6953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // have one carry bit which can change a sign. As such, if LHS and RHS each 7053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // have at least two sign bits, we know that the addition of the two values 7153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // will sign extend fine. 7253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ComputeNumSignBits(LHS) > 1 && ComputeNumSignBits(RHS) > 1) 7353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return true; 7453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 7553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 7653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If one of the operands only has one non-zero bit, and if the other operand 7753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // has a known-zero bit in a more significant place than it (not including the 7853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // sign bit) the ripple may go up to and fill the zero, but won't change the 7953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // sign. For example, (X & ~4) + 1. 8053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 8153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // TODO: Implement. 8253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 8353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return false; 8453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 8553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 8653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitAdd(BinaryOperator &I) { 8753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner bool Changed = SimplifyCommutative(I); 8853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 8953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 9053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(), 9153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner I.hasNoUnsignedWrap(), TD)) 9253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, V); 9353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 9453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 9553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 9653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHSC)) { 9753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X + (signbit) --> X ^ signbit 9853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner const APInt& Val = CI->getValue(); 9953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner uint32_t BitWidth = Val.getBitWidth(); 10053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Val == APInt::getSignBit(BitWidth)) 10153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateXor(LHS, RHS); 10253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 10353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // See if SimplifyDemandedBits can simplify this. This handles stuff like 10453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (X & 254)+1 -> (X&254)|1 10553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SimplifyDemandedInstructionBits(I)) 10653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return &I; 10753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 10853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // zext(bool) + C -> bool ? C + 1 : C 10953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS)) 11053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ZI->getSrcTy() == Type::getInt1Ty(I.getContext())) 11153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI); 11253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 11353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 11453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (isa<PHINode>(LHS)) 11553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 11653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return NV; 11753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 11853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *XorRHS = 0; 11953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *XorLHS = 0; 12053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (isa<ConstantInt>(RHSC) && 12153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) { 12253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner uint32_t TySizeBits = I.getType()->getScalarSizeInBits(); 12353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner const APInt& RHSVal = cast<ConstantInt>(RHSC)->getValue(); 124be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman unsigned ExtendAmt = 0; 125be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext. 126be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext. 127be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (XorRHS->getValue() == -RHSVal) { 128be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (RHSVal.isPowerOf2()) 129be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = TySizeBits - RHSVal.logBase2() - 1; 130be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman else if (XorRHS->getValue().isPowerOf2()) 131be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1; 13253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 133be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman 134be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (ExtendAmt) { 135be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt); 136be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (!MaskedValueIsZero(XorLHS, Mask)) 137be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = 0; 138be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman } 139be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman 140be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (ExtendAmt) { 141be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt); 142be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext"); 143be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman return BinaryOperator::CreateAShr(NewShl, ShAmt); 14453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 14553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 14653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 14753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 148b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy(1)) 14953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateXor(LHS, RHS); 15053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 151b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy()) { 15253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X + X --> X << 1 15353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHS == RHS) 15453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1)); 15553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 15653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *RHSI = dyn_cast<Instruction>(RHS)) { 15753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (RHSI->getOpcode() == Instruction::Sub) 15853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHS == RHSI->getOperand(1)) // A + (B - A) --> B 15953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, RHSI->getOperand(0)); 16053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 16153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *LHSI = dyn_cast<Instruction>(LHS)) { 16253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSI->getOpcode() == Instruction::Sub) 16353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (RHS == LHSI->getOperand(1)) // (B - A) + A --> B 16453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, LHSI->getOperand(0)); 16553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 16653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 16753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 16853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + B --> B - A 16953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + -B --> -(A + B) 17053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *LHSV = dyn_castNegVal(LHS)) { 171b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (LHS->getType()->isIntOrIntVectorTy()) { 17253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *RHSV = dyn_castNegVal(RHS)) { 17353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum"); 17453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateNeg(NewAdd); 17553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 17653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 17753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 17853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(RHS, LHSV); 17953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 18053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 18153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // A + -B --> A - B 18253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!isa<Constant>(RHS)) 18353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castNegVal(RHS)) 18453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(LHS, V); 18553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 18653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 18753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C2; 18853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *X = dyn_castFoldableMul(LHS, C2)) { 18953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == RHS) // X*C + X --> X * (C+1) 19053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(RHS, AddOne(C2)); 19153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 19253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X*C1 + X*C2 --> X * (C1+C2) 19353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C1; 19453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == dyn_castFoldableMul(RHS, C1)) 19553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2)); 19653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 19753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 19853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X + X*C --> X * (C+1) 19953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (dyn_castFoldableMul(RHS, C2) == LHS) 20053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(LHS, AddOne(C2)); 20153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 20253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X + ~X --> -1 since ~X = -X-1 20353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(LHS, m_Not(m_Specific(RHS))) || 20453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(RHS, m_Not(m_Specific(LHS)))) 20553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType())); 20653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 20753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // A+B --> A|B iff A and B have no bits set in common. 20853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (const IntegerType *IT = dyn_cast<IntegerType>(I.getType())) { 20953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt Mask = APInt::getAllOnesValue(IT->getBitWidth()); 21053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt LHSKnownOne(IT->getBitWidth(), 0); 21153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt LHSKnownZero(IT->getBitWidth(), 0); 21253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ComputeMaskedBits(LHS, Mask, LHSKnownZero, LHSKnownOne); 21353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSKnownZero != 0) { 21453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt RHSKnownOne(IT->getBitWidth(), 0); 21553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt RHSKnownZero(IT->getBitWidth(), 0); 21653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ComputeMaskedBits(RHS, Mask, RHSKnownZero, RHSKnownOne); 21753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 21853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // No bits in common -> bitwise or. 21953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if ((LHSKnownZero|RHSKnownZero).isAllOnesValue()) 22053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateOr(LHS, RHS); 22153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 22253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 22353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 22453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // W*X + Y*Z --> W * (X+Z) iff W == Y 225b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntOrIntVectorTy()) { 22653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *W, *X, *Y, *Z; 22753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(LHS, m_Mul(m_Value(W), m_Value(X))) && 22853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) { 22953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (W != Y) { 23053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (W == Z) { 23153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(Y, Z); 23253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (Y == X) { 23353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(W, X); 23453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (X == Z) { 23553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(Y, Z); 23653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(W, X); 23753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 23853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 23953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 24053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (W == Y) { 24153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName()); 24253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(W, NewAdd); 24353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 24453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 24553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 24653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 24753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) { 24853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *X = 0; 24953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X 25053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(SubOne(CRHS), X); 25153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 25253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (X & FF00) + xx00 -> (X+xx00) & FF00 25353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHS->hasOneUse() && 25453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(LHS, m_And(m_Value(X), m_ConstantInt(C2)))) { 25553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *Anded = ConstantExpr::getAnd(CRHS, C2); 25653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Anded == CRHS) { 25753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // See if all bits from the first bit set in the Add RHS up are included 25853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // in the mask. First, get the rightmost bit. 25953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner const APInt &AddRHSV = CRHS->getValue(); 26053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 26153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Form a mask of all bits from the lowest bit added through the top. 26253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1)); 26353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 26453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // See if the and mask includes all of these bits. 26553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue()); 26653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 26753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (AddRHSHighBits == AddRHSHighBitsAnd) { 26853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Okay, the xform is safe. Insert the new add pronto. 26953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName()); 27053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateAnd(NewAdd, C2); 27153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 27253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 27353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 27453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 27553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Try to fold constant add into select arguments. 27653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 27753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 27853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return R; 27953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 28053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 28153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // add (select X 0 (sub n A)) A --> select X A n 28253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner { 28353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SelectInst *SI = dyn_cast<SelectInst>(LHS); 28453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *A = RHS; 28553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!SI) { 28653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SI = dyn_cast<SelectInst>(RHS); 28753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner A = LHS; 28853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 28953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SI && SI->hasOneUse()) { 29053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *TV = SI->getTrueValue(); 29153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *FV = SI->getFalseValue(); 29253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *N; 29353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 29453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Can we fold the add into the argument of the select? 29553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // We check both true and false select arguments for a matching subtract. 29653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(FV, m_Zero()) && 29753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(TV, m_Sub(m_Value(N), m_Specific(A)))) 29853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Fold the add into the true select value. 29953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(SI->getCondition(), N, A); 30053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(TV, m_Zero()) && 30153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(FV, m_Sub(m_Value(N), m_Specific(A)))) 30253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Fold the add into the false select value. 30353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(SI->getCondition(), A, N); 30453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 30553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 30653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 30753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Check for (add (sext x), y), see if we can merge this into an 30853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add followed by a sext. 30953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) { 31053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (add (sext x), cst) --> (sext (add x, cst')) 31153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 31253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *CI = 31353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); 31453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->hasOneUse() && 31553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getSExt(CI, I.getType()) == RHSC && 31653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 31753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new, smaller add. 31853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 31953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CI, "addconv"); 32053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SExtInst(NewAdd, I.getType()); 32153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 32253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 32353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 32453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (add (sext x), (sext y)) --> (sext (add int x, y)) 32553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) { 32653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Only do this if x/y have the same type, if at last one of them has a 32753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // single use (so we don't increase the number of sexts), and if the 32853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add will not overflow. 32953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 33053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 33153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), 33253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0))) { 33353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 33453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 3353168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner RHSConv->getOperand(0), "addconv"); 33653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SExtInst(NewAdd, I.getType()); 33753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 33853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 33953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 34053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 34153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Changed ? &I : 0; 34253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 34353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 34453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitFAdd(BinaryOperator &I) { 34553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner bool Changed = SimplifyCommutative(I); 34653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 34753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 34853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 34953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X + 0 --> X 35053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 35153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CFP->isExactlyValue(ConstantFP::getNegativeZero 35253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (I.getType())->getValueAPF())) 35353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, LHS); 35453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 35553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 35653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (isa<PHINode>(LHS)) 35753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 35853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return NV; 35953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 36053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 36153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + B --> B - A 36253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + -B --> -(A + B) 36353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *LHSV = dyn_castFNegVal(LHS)) 36453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateFSub(RHS, LHSV); 36553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 36653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // A + -B --> A - B 36753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!isa<Constant>(RHS)) 36853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castFNegVal(RHS)) 36953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateFSub(LHS, V); 37053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 37153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Check for X+0.0. Simplify it to X if we know X is not -0.0. 37253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) 37353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CFP->getValueAPF().isPosZero() && CannotBeNegativeZero(LHS)) 37453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, LHS); 37553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 37653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Check for (add double (sitofp x), y), see if we can merge this into an 37753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add followed by a promotion. 37853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) { 37953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (add double (sitofp x), fpcst) --> (sitofp (add int x, intcst)) 38053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // ... if the constant fits in the integer value. This is useful for things 38153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer 38253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // requires a constant pool load, and generally allows the add to be better 38353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // instcombined. 38453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) { 38553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *CI = 38653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType()); 38753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->hasOneUse() && 38853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getSIToFP(CI, I.getType()) == CFP && 38953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 39053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 39153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 39253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CI, "addconv"); 39353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SIToFPInst(NewAdd, I.getType()); 39453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 39553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 39653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 39753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (add double (sitofp x), (sitofp y)) --> (sitofp (add int x, y)) 39853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) { 39953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Only do this if x/y have the same type, if at last one of them has a 40053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // single use (so we don't increase the number of int->fp conversions), 40153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // and if the integer add will not overflow. 40253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 40353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 40453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), 40553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0))) { 40653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 40753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 40853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0),"addconv"); 40953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SIToFPInst(NewAdd, I.getType()); 41053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 41153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 41253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 41353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 41453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Changed ? &I : 0; 41553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 41653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 41753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 41853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the 41953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// code necessary to compute the offset from the base pointer (without adding 42053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// in the base pointer). Return the result as a signed integer of intptr size. 42153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerValue *InstCombiner::EmitGEPOffset(User *GEP) { 42253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner TargetData &TD = *getTargetData(); 42353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner gep_type_iterator GTI = gep_type_begin(GEP); 42453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner const Type *IntPtrTy = TD.getIntPtrType(GEP->getContext()); 42553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Result = Constant::getNullValue(IntPtrTy); 42653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 42753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Build a mask for high order bits. 42853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner unsigned IntPtrWidth = TD.getPointerSizeInBits(); 42953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth); 43053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 43153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e; 43253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ++i, ++GTI) { 43353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Op = *i; 43453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask; 43553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *OpC = dyn_cast<ConstantInt>(Op)) { 43653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (OpC->isZero()) continue; 43753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 43853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Handle a struct index, which adds its field offset to the pointer. 43953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (const StructType *STy = dyn_cast<StructType>(*GTI)) { 44053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Size = TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue()); 44153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 44253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Result = Builder->CreateAdd(Result, 44353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt::get(IntPtrTy, Size), 44453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GEP->getName()+".offs"); 44553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner continue; 44653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 44753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 44853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *Scale = ConstantInt::get(IntPtrTy, Size); 44953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *OC = 45053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/); 45153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Scale = ConstantExpr::getMul(OC, Scale); 45253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Emit an add instruction. 45353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs"); 45453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner continue; 45553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 45653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Convert to correct type. 45753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op->getType() != IntPtrTy) 45853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c"); 45953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Size != 1) { 46053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *Scale = ConstantInt::get(IntPtrTy, Size); 46153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // We'll let instcombine(mul) convert this to a shl if possible. 46253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Op = Builder->CreateMul(Op, Scale, GEP->getName()+".idx"); 46353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 46453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 46553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Emit an add instruction. 46653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs"); 46753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 46853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Result; 46953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 47053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 47153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 47253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 47353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 47453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// Optimize pointer differences into the same array into a size. Consider: 47553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer 47653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// operands to the ptrtoint instructions for the LHS/RHS of the subtract. 47753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// 47853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerValue *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS, 47953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner const Type *Ty) { 48053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner assert(TD && "Must have target data info for this"); 48153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 48253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize 48353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // this. 48453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner bool Swapped = false; 48553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GetElementPtrInst *GEP = 0; 48653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr *CstGEP = 0; 48753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 48853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // TODO: Could also optimize &A[i] - &A[j] -> "i-j", and "&A.foo[i] - &A.foo". 48953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // For now we require one side to be the base pointer "A" or a constant 49053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // expression derived from it. 49153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (GetElementPtrInst *LHSGEP = dyn_cast<GetElementPtrInst>(LHS)) { 49253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (gep X, ...) - X 49353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSGEP->getOperand(0) == RHS) { 49453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GEP = LHSGEP; 49553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = false; 49653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(RHS)) { 49753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (gep X, ...) - (ce_gep X, ...) 49853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CE->getOpcode() == Instruction::GetElementPtr && 49953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner LHSGEP->getOperand(0) == CE->getOperand(0)) { 50053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CstGEP = CE; 50153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GEP = LHSGEP; 50253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = false; 50353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 50453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 50553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 50653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 50753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (GetElementPtrInst *RHSGEP = dyn_cast<GetElementPtrInst>(RHS)) { 50853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X - (gep X, ...) 50953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (RHSGEP->getOperand(0) == LHS) { 51053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GEP = RHSGEP; 51153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = true; 51253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(LHS)) { 51353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (ce_gep X, ...) - (gep X, ...) 51453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CE->getOpcode() == Instruction::GetElementPtr && 51553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSGEP->getOperand(0) == CE->getOperand(0)) { 51653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CstGEP = CE; 51753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GEP = RHSGEP; 51853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = true; 51953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 52053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 52153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 52253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 52353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (GEP == 0) 52453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 52553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 52653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Emit the offset of the GEP and an intptr_t. 52753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Result = EmitGEPOffset(GEP); 52853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 52953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If we had a constant expression GEP on the other side offsetting the 53053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // pointer, subtract it from the offset we have. 53153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CstGEP) { 53253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *CstOffset = EmitGEPOffset(CstGEP); 53353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Result = Builder->CreateSub(Result, CstOffset); 53453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 53553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 53653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 53753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If we have p - gep(p, ...) then we have to negate the result. 53853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Swapped) 53953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Result = Builder->CreateNeg(Result, "diff.neg"); 54053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 54153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Builder->CreateIntCast(Result, Ty, true); 54253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 54353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 54453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 54553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitSub(BinaryOperator &I) { 54653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 54753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 54853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op0 == Op1) // sub X, X -> 0 54953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 55053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 55153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If this is a 'B = x-(-A)', change to B = x+A. This preserves NSW/NUW. 55253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castNegVal(Op1)) { 55353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V); 55453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Res->setHasNoSignedWrap(I.hasNoSignedWrap()); 55553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 55653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Res; 55753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 55853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 55953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (isa<UndefValue>(Op0)) 56053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Op0); // undef - X -> undef 56153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (isa<UndefValue>(Op1)) 56253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Op1); // X - undef -> undef 563b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy(1)) 56453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateXor(Op0, Op1); 56553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 56653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) { 56753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Replace (-1 - A) with (~A). 56853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (C->isAllOnesValue()) 56953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateNot(Op1); 57053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 57153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // C - ~X == X + (1+C) 57253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *X = 0; 57353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op1, m_Not(m_Value(X)))) 57453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateAdd(X, AddOne(C)); 57553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 57653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -(X >>u 31) -> (X >>s 31) 57753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -(X >>s 31) -> (X >>u 31) 57853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (C->isZero()) { 57953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (BinaryOperator *SI = dyn_cast<BinaryOperator>(Op1)) { 58053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SI->getOpcode() == Instruction::LShr) { 58153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *CU = dyn_cast<ConstantInt>(SI->getOperand(1))) { 58253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Check to see if we are shifting out everything but the sign bit. 58353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CU->getLimitedValue(SI->getType()->getPrimitiveSizeInBits()) == 58453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SI->getType()->getPrimitiveSizeInBits()-1) { 58553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Ok, the transformation is safe. Insert AShr. 58653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::Create(Instruction::AShr, 58753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SI->getOperand(0), CU, SI->getName()); 58853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 58953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 59053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (SI->getOpcode() == Instruction::AShr) { 59153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *CU = dyn_cast<ConstantInt>(SI->getOperand(1))) { 59253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Check to see if we are shifting out everything but the sign bit. 59353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CU->getLimitedValue(SI->getType()->getPrimitiveSizeInBits()) == 59453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SI->getType()->getPrimitiveSizeInBits()-1) { 59553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Ok, the transformation is safe. Insert LShr. 59653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateLShr( 59753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SI->getOperand(0), CU, SI->getName()); 59853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 59953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 60053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 60153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 60253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 60353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 60453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Try to fold constant sub into select arguments. 60553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 60653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 60753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return R; 60853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 60953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // C - zext(bool) -> bool ? C - 1 : C 61053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ZExtInst *ZI = dyn_cast<ZExtInst>(Op1)) 61153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ZI->getSrcTy() == Type::getInt1Ty(I.getContext())) 61253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(ZI->getOperand(0), SubOne(C), C); 61353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 61453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 61553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1)) { 61653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op1I->getOpcode() == Instruction::Add) { 61753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op1I->getOperand(0) == Op0) // X-(X+Y) == -Y 61853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateNeg(Op1I->getOperand(1), 61953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner I.getName()); 62053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner else if (Op1I->getOperand(1) == Op0) // X-(Y+X) == -Y 62153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateNeg(Op1I->getOperand(0), 62253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner I.getName()); 62353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner else if (ConstantInt *CI1 = dyn_cast<ConstantInt>(I.getOperand(0))) { 62453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *CI2 = dyn_cast<ConstantInt>(Op1I->getOperand(1))) 62553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // C1-(X+C2) --> (C1-C2)-X 62653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub( 62753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getSub(CI1, CI2), Op1I->getOperand(0)); 62853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 62953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 63053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 63153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op1I->hasOneUse()) { 63253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression 63353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // is not used by anyone else... 63453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // 63553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op1I->getOpcode() == Instruction::Sub) { 63653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Swap the two operands of the subexpr... 63753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1); 63853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Op1I->setOperand(0, IIOp1); 63953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Op1I->setOperand(1, IIOp0); 64053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 64153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Create the new top level add instruction... 64253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateAdd(Op0, Op1); 64353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 64453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 64553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Replace (A - (A & B)) with (A & ~B) if this is the only use of (A&B)... 64653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // 64753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op1I->getOpcode() == Instruction::And && 64853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (Op1I->getOperand(0) == Op0 || Op1I->getOperand(1) == Op0)) { 64953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *OtherOp = Op1I->getOperand(Op1I->getOperand(0) == Op0); 65053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 65153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewNot = Builder->CreateNot(OtherOp, "B.not"); 65253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateAnd(Op0, NewNot); 65353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 65453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 65553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // 0 - (X sdiv C) -> (X sdiv -C) 65653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op1I->getOpcode() == Instruction::SDiv) 65753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *CSI = dyn_cast<ConstantInt>(Op0)) 65853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CSI->isZero()) 65953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Constant *DivRHS = dyn_cast<Constant>(Op1I->getOperand(1))) 66053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSDiv(Op1I->getOperand(0), 66153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getNeg(DivRHS)); 66253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 663694488f4770468f03b974180631c0fbfa21b28ccEli Friedman // 0 - (C << X) -> (-C << X) 664694488f4770468f03b974180631c0fbfa21b28ccEli Friedman if (Op1I->getOpcode() == Instruction::Shl) 665694488f4770468f03b974180631c0fbfa21b28ccEli Friedman if (ConstantInt *CSI = dyn_cast<ConstantInt>(Op0)) 666694488f4770468f03b974180631c0fbfa21b28ccEli Friedman if (CSI->isZero()) 667694488f4770468f03b974180631c0fbfa21b28ccEli Friedman if (Value *ShlLHSNeg = dyn_castNegVal(Op1I->getOperand(0))) 668694488f4770468f03b974180631c0fbfa21b28ccEli Friedman return BinaryOperator::CreateShl(ShlLHSNeg, Op1I->getOperand(1)); 669694488f4770468f03b974180631c0fbfa21b28ccEli Friedman 67053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X - X*C --> X * (1-C) 67153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C2 = 0; 67253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (dyn_castFoldableMul(Op1I, C2) == Op0) { 67353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *CP1 = 67453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getSub(ConstantInt::get(I.getType(), 1), 67553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner C2); 67653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(Op0, CP1); 67753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 67853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 67953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 68053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 68153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) { 68253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op0I->getOpcode() == Instruction::Add) { 68353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op0I->getOperand(0) == Op1) // (Y+X)-Y == X 68453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Op0I->getOperand(1)); 68553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner else if (Op0I->getOperand(1) == Op1) // (X+Y)-Y == X 68653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Op0I->getOperand(0)); 68753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (Op0I->getOpcode() == Instruction::Sub) { 68853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op0I->getOperand(0) == Op1) // (X-Y)-X == -Y 68953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateNeg(Op0I->getOperand(1), 69053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner I.getName()); 69153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 69253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 69353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 69453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C1; 69553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *X = dyn_castFoldableMul(Op0, C1)) { 69653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == Op1) // X*C - X --> X * (C-1) 69753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(Op1, SubOne(C1)); 69853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 69953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C2; // X*C1 - X*C2 -> X * (C1-C2) 70053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == dyn_castFoldableMul(Op1, C2)) 70153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2)); 70253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 70353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 70453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Optimize pointer differences into the same array into a size. Consider: 70553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // &A[10] - &A[0]: we should compile this to "10". 70653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (TD) { 70753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHSOp, *RHSOp; 70853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op0, m_PtrToInt(m_Value(LHSOp))) && 70953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(Op1, m_PtrToInt(m_Value(RHSOp)))) 71053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 71153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Res); 71253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 71353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // trunc(p)-trunc(q) -> trunc(p-q) 71453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) && 71553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp))))) 71653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 71753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Res); 71853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 71953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 72053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 72153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 72253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 72353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitFSub(BinaryOperator &I) { 72453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 72553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 72653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If this is a 'B = x-(-A)', change to B = x+A... 72753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castFNegVal(Op1)) 72853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateFAdd(Op0, V); 72953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 73053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 73153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 732