InstCombineAddSub.cpp revision db125cfaf57cc83e7dd7453de2d509bc8efd0e5e
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) { 87096aa79276b8527a3cbbb3691e40e729dea09523Duncan Sands bool Changed = SimplifyAssociativeOrCommutative(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 9437bf92b5238434b00fde79347ba5336e7554e562Duncan Sands // (A*B)+(A*C) -> A*(B+C) etc 9537bf92b5238434b00fde79347ba5336e7554e562Duncan Sands if (Value *V = SimplifyUsingDistributiveLaws(I)) 9637bf92b5238434b00fde79347ba5336e7554e562Duncan Sands return ReplaceInstUsesWith(I, V); 9737bf92b5238434b00fde79347ba5336e7554e562Duncan Sands 98b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 99b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X + (signbit) --> X ^ signbit 100b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner const APInt &Val = CI->getValue(); 101b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Val.isSignBit()) 102b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateXor(LHS, RHS); 103b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 104b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // See if SimplifyDemandedBits can simplify this. This handles stuff like 105b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X & 254)+1 -> (X&254)|1 106b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (SimplifyDemandedInstructionBits(I)) 107b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return &I; 108b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 109b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // zext(bool) + C -> bool ? C + 1 : C 110b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS)) 111b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (ZI->getSrcTy()->isIntegerTy(1)) 112b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI); 11353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 114b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *XorLHS = 0; ConstantInt *XorRHS = 0; 115b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) { 11653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner uint32_t TySizeBits = I.getType()->getScalarSizeInBits(); 117b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner const APInt &RHSVal = CI->getValue(); 118be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman unsigned ExtendAmt = 0; 119be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext. 120be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext. 121be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (XorRHS->getValue() == -RHSVal) { 122be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (RHSVal.isPowerOf2()) 123be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = TySizeBits - RHSVal.logBase2() - 1; 124be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman else if (XorRHS->getValue().isPowerOf2()) 125be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = TySizeBits - XorRHS->getValue().logBase2() - 1; 12653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 127b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 128be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (ExtendAmt) { 129be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman APInt Mask = APInt::getHighBitsSet(TySizeBits, ExtendAmt); 130be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (!MaskedValueIsZero(XorLHS, Mask)) 131be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman ExtendAmt = 0; 132be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman } 133b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 134be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman if (ExtendAmt) { 135be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman Constant *ShAmt = ConstantInt::get(I.getType(), ExtendAmt); 136be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman Value *NewShl = Builder->CreateShl(XorLHS, ShAmt, "sext"); 137be7cfa6033d9f432a30f43870705bd57db0cbd5bEli Friedman return BinaryOperator::CreateAShr(NewShl, ShAmt); 13853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 13953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 14053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 14153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 142b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (isa<Constant>(RHS) && isa<PHINode>(LHS)) 143b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 144b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return NV; 145b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 146b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy(1)) 14753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateXor(LHS, RHS); 14853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 149b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X + X --> X << 1 150bd9f6bf5cd5499715e216415989c29f820a7561cChris Lattner if (LHS == RHS) { 15141429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner BinaryOperator *New = 15241429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner BinaryOperator::CreateShl(LHS, ConstantInt::get(I.getType(), 1)); 15341429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner New->setHasNoSignedWrap(I.hasNoSignedWrap()); 15441429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner New->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 15541429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner return New; 15641429e3f1e4d72ee4f7d4df786b5b0c87405f5b0Chris Lattner } 15753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 15853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + B --> B - A 15953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + -B --> -(A + B) 16053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *LHSV = dyn_castNegVal(LHS)) { 161b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Value *RHSV = dyn_castNegVal(RHS)) { 162b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *NewAdd = Builder->CreateAdd(LHSV, RHSV, "sum"); 163b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateNeg(NewAdd); 16453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 16553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 16653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(RHS, LHSV); 16753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 16853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 16953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // A + -B --> A - B 17053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!isa<Constant>(RHS)) 17153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castNegVal(RHS)) 17253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(LHS, V); 17353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 17453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 17553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C2; 17653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *X = dyn_castFoldableMul(LHS, C2)) { 17753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == RHS) // X*C + X --> X * (C+1) 17853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(RHS, AddOne(C2)); 17953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 18053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X*C1 + X*C2 --> X * (C1+C2) 18153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C1; 18253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == dyn_castFoldableMul(RHS, C1)) 18353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(X, ConstantExpr::getAdd(C1, C2)); 18453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 18553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 18653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X + X*C --> X * (C+1) 18753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (dyn_castFoldableMul(RHS, C2) == LHS) 18853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(LHS, AddOne(C2)); 18953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 19053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // A+B --> A|B iff A and B have no bits set in common. 191db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) { 19253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt Mask = APInt::getAllOnesValue(IT->getBitWidth()); 19353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt LHSKnownOne(IT->getBitWidth(), 0); 19453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt LHSKnownZero(IT->getBitWidth(), 0); 19553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ComputeMaskedBits(LHS, Mask, LHSKnownZero, LHSKnownOne); 19653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSKnownZero != 0) { 19753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt RHSKnownOne(IT->getBitWidth(), 0); 19853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner APInt RHSKnownZero(IT->getBitWidth(), 0); 19953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ComputeMaskedBits(RHS, Mask, RHSKnownZero, RHSKnownOne); 20053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 20153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // No bits in common -> bitwise or. 20253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if ((LHSKnownZero|RHSKnownZero).isAllOnesValue()) 20353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateOr(LHS, RHS); 20453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 20553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 20653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 20753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // W*X + Y*Z --> W * (X+Z) iff W == Y 208b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner { 20953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *W, *X, *Y, *Z; 21053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(LHS, m_Mul(m_Value(W), m_Value(X))) && 21153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(RHS, m_Mul(m_Value(Y), m_Value(Z)))) { 21253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (W != Y) { 21353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (W == Z) { 21453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(Y, Z); 21553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (Y == X) { 21653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(W, X); 21753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (X == Z) { 21853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(Y, Z); 21953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner std::swap(W, X); 22053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 22153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 22253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 22353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (W == Y) { 22453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateAdd(X, Z, LHS->getName()); 22553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(W, NewAdd); 22653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 22753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 22853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 22953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 23053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) { 23153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *X = 0; 23253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(LHS, m_Not(m_Value(X)))) // ~X + C --> (C-1) - X 23353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateSub(SubOne(CRHS), X); 23453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 23553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (X & FF00) + xx00 -> (X+xx00) & FF00 23653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHS->hasOneUse() && 237b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(LHS, m_And(m_Value(X), m_ConstantInt(C2))) && 238b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner CRHS->getValue() == (CRHS->getValue() & C2->getValue())) { 239b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // See if all bits from the first bit set in the Add RHS up are included 240b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // in the mask. First, get the rightmost bit. 241b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner const APInt &AddRHSV = CRHS->getValue(); 242b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 243b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Form a mask of all bits from the lowest bit added through the top. 244b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner APInt AddRHSHighBits(~((AddRHSV & -AddRHSV)-1)); 245b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 246b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // See if the and mask includes all of these bits. 247b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner APInt AddRHSHighBitsAnd(AddRHSHighBits & C2->getValue()); 248b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 249b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (AddRHSHighBits == AddRHSHighBitsAnd) { 250b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Okay, the xform is safe. Insert the new add pronto. 251b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *NewAdd = Builder->CreateAdd(X, CRHS, LHS->getName()); 252b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAnd(NewAdd, C2); 25353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 25453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 25553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 25653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Try to fold constant add into select arguments. 25753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(LHS)) 25853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 25953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return R; 26053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 26153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 26253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // add (select X 0 (sub n A)) A --> select X A n 26353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner { 26453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SelectInst *SI = dyn_cast<SelectInst>(LHS); 26553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *A = RHS; 26653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!SI) { 26753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner SI = dyn_cast<SelectInst>(RHS); 26853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner A = LHS; 26953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 27053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SI && SI->hasOneUse()) { 27153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *TV = SI->getTrueValue(); 27253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *FV = SI->getFalseValue(); 27353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *N; 27453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 27553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Can we fold the add into the argument of the select? 27653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // We check both true and false select arguments for a matching subtract. 277b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(FV, m_Zero()) && match(TV, m_Sub(m_Value(N), m_Specific(A)))) 27853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Fold the add into the true select value. 27953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(SI->getCondition(), N, A); 280b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 281b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(TV, m_Zero()) && match(FV, m_Sub(m_Value(N), m_Specific(A)))) 28253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Fold the add into the false select value. 28353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(SI->getCondition(), A, N); 28453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 28553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 28653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 28753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Check for (add (sext x), y), see if we can merge this into an 28853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add followed by a sext. 28953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SExtInst *LHSConv = dyn_cast<SExtInst>(LHS)) { 29053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (add (sext x), cst) --> (sext (add x, cst')) 29153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 29253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *CI = 29353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType()); 29453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->hasOneUse() && 29553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getSExt(CI, I.getType()) == RHSC && 29653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 29753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new, smaller add. 29853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 29953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CI, "addconv"); 30053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SExtInst(NewAdd, I.getType()); 30153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 30253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 30353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 30453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (add (sext x), (sext y)) --> (sext (add int x, y)) 30553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SExtInst *RHSConv = dyn_cast<SExtInst>(RHS)) { 30653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Only do this if x/y have the same type, if at last one of them has a 30753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // single use (so we don't increase the number of sexts), and if the 30853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add will not overflow. 30953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 31053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 31153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), 31253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0))) { 31353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 31453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 3153168c7dd25193039b3dbf9ce6bb57c7da3e56f85Chris Lattner RHSConv->getOperand(0), "addconv"); 31653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SExtInst(NewAdd, I.getType()); 31753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 31853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 31953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 32053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 32153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Changed ? &I : 0; 32253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 32353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 32453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitFAdd(BinaryOperator &I) { 325096aa79276b8527a3cbbb3691e40e729dea09523Duncan Sands bool Changed = SimplifyAssociativeOrCommutative(I); 32653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 32753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 32853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 32953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X + 0 --> X 33053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 33153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CFP->isExactlyValue(ConstantFP::getNegativeZero 33253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (I.getType())->getValueAPF())) 33353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, LHS); 33453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 33553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 33653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (isa<PHINode>(LHS)) 33753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *NV = FoldOpIntoPhi(I)) 33853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return NV; 33953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 34053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 34153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + B --> B - A 34253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -A + -B --> -(A + B) 34353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *LHSV = dyn_castFNegVal(LHS)) 34453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateFSub(RHS, LHSV); 34553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 34653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // A + -B --> A - B 34753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (!isa<Constant>(RHS)) 34853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castFNegVal(RHS)) 34953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateFSub(LHS, V); 35053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 35153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Check for X+0.0. Simplify it to X if we know X is not -0.0. 35253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) 35353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CFP->getValueAPF().isPosZero() && CannotBeNegativeZero(LHS)) 35453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, LHS); 35553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 356a9445e11c553855a6caacbbbf77a9b993ecc651eDan Gohman // Check for (fadd double (sitofp x), y), see if we can merge this into an 35753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // integer add followed by a promotion. 35853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SIToFPInst *LHSConv = dyn_cast<SIToFPInst>(LHS)) { 359a9445e11c553855a6caacbbbf77a9b993ecc651eDan Gohman // (fadd double (sitofp x), fpcst) --> (sitofp (add int x, intcst)) 36053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // ... if the constant fits in the integer value. This is useful for things 36153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // like (double)(x & 1234) + 4.0 -> (double)((X & 1234)+4) which no longer 36253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // requires a constant pool load, and generally allows the add to be better 36353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // instcombined. 36453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHS)) { 36553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *CI = 36653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getFPToSI(CFP, LHSConv->getOperand(0)->getType()); 36753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->hasOneUse() && 36853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getSIToFP(CI, I.getType()) == CFP && 36953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), CI)) { 37053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 37153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 37253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CI, "addconv"); 37353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SIToFPInst(NewAdd, I.getType()); 37453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 37553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 37653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 377a9445e11c553855a6caacbbbf77a9b993ecc651eDan Gohman // (fadd double (sitofp x), (sitofp y)) --> (sitofp (add int x, y)) 37853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SIToFPInst *RHSConv = dyn_cast<SIToFPInst>(RHS)) { 37953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Only do this if x/y have the same type, if at last one of them has a 38053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // single use (so we don't increase the number of int->fp conversions), 38153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // and if the integer add will not overflow. 38253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSConv->getOperand(0)->getType()==RHSConv->getOperand(0)->getType()&& 38353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner (LHSConv->hasOneUse() || RHSConv->hasOneUse()) && 38453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner WillNotOverflowSignedAdd(LHSConv->getOperand(0), 38553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0))) { 38653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Insert the new integer add. 38753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *NewAdd = Builder->CreateNSWAdd(LHSConv->getOperand(0), 38853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSConv->getOperand(0),"addconv"); 38953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return new SIToFPInst(NewAdd, I.getType()); 39053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 39153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 39253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 39353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 39453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Changed ? &I : 0; 39553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 39653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 39753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 39853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the 39953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// code necessary to compute the offset from the base pointer (without adding 40053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// in the base pointer). Return the result as a signed integer of intptr size. 40153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerValue *InstCombiner::EmitGEPOffset(User *GEP) { 40253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner TargetData &TD = *getTargetData(); 40353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner gep_type_iterator GTI = gep_type_begin(GEP); 404db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *IntPtrTy = TD.getIntPtrType(GEP->getContext()); 40553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Result = Constant::getNullValue(IntPtrTy); 40653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 4076cdf2ea98e9952a57768a1fcdce8850089263260Chris Lattner // If the GEP is inbounds, we know that none of the addressing operations will 4086cdf2ea98e9952a57768a1fcdce8850089263260Chris Lattner // overflow in an unsigned sense. 4096cdf2ea98e9952a57768a1fcdce8850089263260Chris Lattner bool isInBounds = cast<GEPOperator>(GEP)->isInBounds(); 4106cdf2ea98e9952a57768a1fcdce8850089263260Chris Lattner 41153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Build a mask for high order bits. 41253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner unsigned IntPtrWidth = TD.getPointerSizeInBits(); 41353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth); 41453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 41553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e; 41653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ++i, ++GTI) { 41753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Op = *i; 41853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask; 41953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *OpC = dyn_cast<ConstantInt>(Op)) { 42053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (OpC->isZero()) continue; 42153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 42253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Handle a struct index, which adds its field offset to the pointer. 423db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (StructType *STy = dyn_cast<StructType>(*GTI)) { 42453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Size = TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue()); 42553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 4266cdf2ea98e9952a57768a1fcdce8850089263260Chris Lattner if (Size) 4276cdf2ea98e9952a57768a1fcdce8850089263260Chris Lattner Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size), 4286aa68a76474525255943bee914e37b68a3ba75c8Chris Lattner GEP->getName()+".offs"); 42953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner continue; 43053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 43153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 43253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *Scale = ConstantInt::get(IntPtrTy, Size); 43353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Constant *OC = 43453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/); 4356cdf2ea98e9952a57768a1fcdce8850089263260Chris Lattner Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/); 43653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Emit an add instruction. 4376aa68a76474525255943bee914e37b68a3ba75c8Chris Lattner Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs"); 43853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner continue; 43953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 44053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Convert to correct type. 44153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Op->getType() != IntPtrTy) 44253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c"); 44353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Size != 1) { 44453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // We'll let instcombine(mul) convert this to a shl if possible. 4456cdf2ea98e9952a57768a1fcdce8850089263260Chris Lattner Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size), 4466cdf2ea98e9952a57768a1fcdce8850089263260Chris Lattner GEP->getName()+".idx", isInBounds /*NUW*/); 44753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 44853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 44953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Emit an add instruction. 4506aa68a76474525255943bee914e37b68a3ba75c8Chris Lattner Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs"); 45153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 45253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Result; 45353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 45453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 45553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 45653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 45753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 45853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// Optimize pointer differences into the same array into a size. Consider: 45953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// &A[10] - &A[0]: we should compile this to "10". LHS/RHS are the pointer 46053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// operands to the ptrtoint instructions for the LHS/RHS of the subtract. 46153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner/// 46253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerValue *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS, 463db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty) { 46453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner assert(TD && "Must have target data info for this"); 46553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 46653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If LHS is a gep based on RHS or RHS is a gep based on LHS, we can optimize 46753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // this. 46853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner bool Swapped = false; 46953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GetElementPtrInst *GEP = 0; 47053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantExpr *CstGEP = 0; 47153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 47253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // TODO: Could also optimize &A[i] - &A[j] -> "i-j", and "&A.foo[i] - &A.foo". 47353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // For now we require one side to be the base pointer "A" or a constant 47453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // expression derived from it. 47553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (GetElementPtrInst *LHSGEP = dyn_cast<GetElementPtrInst>(LHS)) { 47653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (gep X, ...) - X 47753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (LHSGEP->getOperand(0) == RHS) { 47853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GEP = LHSGEP; 47953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = false; 48053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(RHS)) { 48153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (gep X, ...) - (ce_gep X, ...) 48253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CE->getOpcode() == Instruction::GetElementPtr && 48353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner LHSGEP->getOperand(0) == CE->getOperand(0)) { 48453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CstGEP = CE; 48553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GEP = LHSGEP; 48653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = false; 48753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 48853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 48953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 49053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 49153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (GetElementPtrInst *RHSGEP = dyn_cast<GetElementPtrInst>(RHS)) { 49253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // X - (gep X, ...) 49353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (RHSGEP->getOperand(0) == LHS) { 49453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GEP = RHSGEP; 49553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = true; 49653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(LHS)) { 49753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // (ce_gep X, ...) - (gep X, ...) 49853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CE->getOpcode() == Instruction::GetElementPtr && 49953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner RHSGEP->getOperand(0) == CE->getOperand(0)) { 50053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner CstGEP = CE; 50153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner GEP = RHSGEP; 50253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Swapped = true; 50353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 50453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 50553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 50653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 50753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (GEP == 0) 50853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 50953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 51053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Emit the offset of the GEP and an intptr_t. 51153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Result = EmitGEPOffset(GEP); 51253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 51353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If we had a constant expression GEP on the other side offsetting the 51453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // pointer, subtract it from the offset we have. 51553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (CstGEP) { 51653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *CstOffset = EmitGEPOffset(CstGEP); 51753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Result = Builder->CreateSub(Result, CstOffset); 51853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 51953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 52053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 52153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If we have p - gep(p, ...) then we have to negate the result. 52253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Swapped) 52353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Result = Builder->CreateNeg(Result, "diff.neg"); 52453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 52553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Builder->CreateIntCast(Result, Ty, true); 52653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 52753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 52853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 52953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitSub(BinaryOperator &I) { 53053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 53153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 532fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(), 533fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands I.hasNoUnsignedWrap(), TD)) 534fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return ReplaceInstUsesWith(I, V); 53553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 53637bf92b5238434b00fde79347ba5336e7554e562Duncan Sands // (A*B)-(A*C) -> A*(B-C) etc 53737bf92b5238434b00fde79347ba5336e7554e562Duncan Sands if (Value *V = SimplifyUsingDistributiveLaws(I)) 53837bf92b5238434b00fde79347ba5336e7554e562Duncan Sands return ReplaceInstUsesWith(I, V); 53937bf92b5238434b00fde79347ba5336e7554e562Duncan Sands 54053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If this is a 'B = x-(-A)', change to B = x+A. This preserves NSW/NUW. 54153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castNegVal(Op1)) { 54253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner BinaryOperator *Res = BinaryOperator::CreateAdd(Op0, V); 54353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Res->setHasNoSignedWrap(I.hasNoSignedWrap()); 54453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Res->setHasNoUnsignedWrap(I.hasNoUnsignedWrap()); 54553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return Res; 54653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 54753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 548b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (I.getType()->isIntegerTy(1)) 54953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateXor(Op0, Op1); 550b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 551b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Replace (-1 - A) with (~A). 552b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op0, m_AllOnes())) 553b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateNot(Op1); 55453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 55553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) { 55653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // C - ~X == X + (1+C) 55753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *X = 0; 55853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op1, m_Not(m_Value(X)))) 55953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateAdd(X, AddOne(C)); 56053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 56153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -(X >>u 31) -> (X >>s 31) 56253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // -(X >>s 31) -> (X >>u 31) 56353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (C->isZero()) { 564b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *X; ConstantInt *CI; 565b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_LShr(m_Value(X), m_ConstantInt(CI))) && 566b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Verify we are shifting out everything but the sign bit. 567b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 568b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAShr(X, CI); 569b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 570b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_AShr(m_Value(X), m_ConstantInt(CI))) && 571b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // Verify we are shifting out everything but the sign bit. 572b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner CI->getValue() == I.getType()->getPrimitiveSizeInBits()-1) 573b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateLShr(X, CI); 57453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 57553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 57653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Try to fold constant sub into select arguments. 57753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 57853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Instruction *R = FoldOpIntoSelect(I, SI)) 57953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return R; 58053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 58153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // C - zext(bool) -> bool ? C - 1 : C 58253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (ZExtInst *ZI = dyn_cast<ZExtInst>(Op1)) 583b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (ZI->getSrcTy()->isIntegerTy(1)) 58453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return SelectInst::Create(ZI->getOperand(0), SubOne(C), C); 585b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 586b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // C-(X+C2) --> (C-C2)-X 587b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner ConstantInt *C2; 588b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Add(m_Value(X), m_ConstantInt(C2)))) 589b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X); 59053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 59153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 592b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 593b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner { Value *Y; 594b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X-(X+Y) == -Y X-(Y+X) == -Y 595b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Add(m_Specific(Op0), m_Value(Y))) || 596b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_Add(m_Value(Y), m_Specific(Op0)))) 597b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateNeg(Y); 598b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 599b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X-Y)-X == -Y 600b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y)))) 601b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateNeg(Y); 602b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner } 603b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 604b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Op1->hasOneUse()) { 605b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *X = 0, *Y = 0, *Z = 0; 606b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Constant *C = 0; 607b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner ConstantInt *CI = 0; 608b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 609b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X - (Y - Z)) --> (X + (Z - Y)). 610b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Sub(m_Value(Y), m_Value(Z)))) 611b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAdd(Op0, 612b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Builder->CreateSub(Z, Y, Op1->getName())); 613b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 614b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // (X - (X & Y)) --> (X & ~Y) 615b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // 616b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_And(m_Value(Y), m_Specific(Op0))) || 617b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_And(m_Specific(Op0), m_Value(Y)))) 618b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAnd(Op0, 619b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Builder->CreateNot(Y, Y->getName() + ".not")); 620b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 621b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // 0 - (X sdiv C) -> (X sdiv -C) 622b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_SDiv(m_Value(X), m_Constant(C))) && 623b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op0, m_Zero())) 624b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(C)); 625b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 626b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // 0 - (X << Y) -> (-X << Y) when X is freely negatable. 627b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero())) 628b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (Value *XNeg = dyn_castNegVal(X)) 629b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateShl(XNeg, Y); 630b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 631b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - X*C --> X * (1-C) 632b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Mul(m_Specific(Op0), m_ConstantInt(CI)))) { 633b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Constant *CP1 = ConstantExpr::getSub(ConstantInt::get(I.getType(),1), CI); 634b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateMul(Op0, CP1); 63553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 63653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 637b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - X<<C --> X * (1-(1<<C)) 638b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Shl(m_Specific(Op0), m_ConstantInt(CI)))) { 639b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Constant *One = ConstantInt::get(I.getType(), 1); 640b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner C = ConstantExpr::getSub(One, ConstantExpr::getShl(One, CI)); 641b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateMul(Op0, C); 64253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 643b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 644b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - A*-B -> X + A*B 645b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - -A*B -> X + A*B 646b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *A, *B; 647b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Mul(m_Value(A), m_Neg(m_Value(B)))) || 648b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_Mul(m_Neg(m_Value(A)), m_Value(B)))) 649b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAdd(Op0, Builder->CreateMul(A, B)); 650b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner 651b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - A*CI -> X + A*-CI 652b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner // X - CI*A -> X + A*-CI 653b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner if (match(Op1, m_Mul(m_Value(A), m_ConstantInt(CI))) || 654b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner match(Op1, m_Mul(m_ConstantInt(CI), m_Value(A)))) { 655b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner Value *NewMul = Builder->CreateMul(A, ConstantExpr::getNeg(CI)); 656b9b9044600a472d5f8750f43fd884e32e2afe4ccChris Lattner return BinaryOperator::CreateAdd(Op0, NewMul); 65753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 65853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 65953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 66053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C1; 66153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *X = dyn_castFoldableMul(Op0, C1)) { 66253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == Op1) // X*C - X --> X * (C-1) 66353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(Op1, SubOne(C1)); 66453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 66553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner ConstantInt *C2; // X*C1 - X*C2 -> X * (C1-C2) 66653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (X == dyn_castFoldableMul(Op1, C2)) 66753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateMul(X, ConstantExpr::getSub(C1, C2)); 66853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 66953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 67053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // Optimize pointer differences into the same array into a size. Consider: 67153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // &A[10] - &A[0]: we should compile this to "10". 67253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (TD) { 67353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *LHSOp, *RHSOp; 67453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op0, m_PtrToInt(m_Value(LHSOp))) && 67553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(Op1, m_PtrToInt(m_Value(RHSOp)))) 67653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 67753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Res); 67853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 67953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // trunc(p)-trunc(q) -> trunc(p-q) 68053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (match(Op0, m_Trunc(m_PtrToInt(m_Value(LHSOp)))) && 68153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner match(Op1, m_Trunc(m_PtrToInt(m_Value(RHSOp))))) 68253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType())) 68353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return ReplaceInstUsesWith(I, Res); 68453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner } 68553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 68653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 68753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 68853a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 68953a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris LattnerInstruction *InstCombiner::visitFSub(BinaryOperator &I) { 69053a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 69153a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 69253a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner // If this is a 'B = x-(-A)', change to B = x+A... 69353a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner if (Value *V = dyn_castFNegVal(Op1)) 69453a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return BinaryOperator::CreateFAdd(Op0, V); 69553a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner 69653a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner return 0; 69753a19b73b5d18794c314bf93f4f3f03e5a8af1f2Chris Lattner} 698