1 //===-- KnownBits.cpp - Stores known zeros/ones ---------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains a class for representing known zeros and ones used by 11 // computeKnownBits. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Support/KnownBits.h" 16 17 using namespace llvm; 18 19 KnownBits KnownBits::computeForAddSub(bool Add, bool NSW, 20 const KnownBits &LHS, KnownBits RHS) { 21 // Carry in a 1 for a subtract, rather than 0. 22 bool CarryIn = false; 23 if (!Add) { 24 // Sum = LHS + ~RHS + 1 25 std::swap(RHS.Zero, RHS.One); 26 CarryIn = true; 27 } 28 29 APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + CarryIn; 30 APInt PossibleSumOne = LHS.One + RHS.One + CarryIn; 31 32 // Compute known bits of the carry. 33 APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero); 34 APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One; 35 36 // Compute set of known bits (where all three relevant bits are known). 37 APInt LHSKnownUnion = LHS.Zero | LHS.One; 38 APInt RHSKnownUnion = RHS.Zero | RHS.One; 39 APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne; 40 APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion; 41 42 assert((PossibleSumZero & Known) == (PossibleSumOne & Known) && 43 "known bits of sum differ"); 44 45 // Compute known bits of the result. 46 KnownBits KnownOut; 47 KnownOut.Zero = ~std::move(PossibleSumZero) & Known; 48 KnownOut.One = std::move(PossibleSumOne) & Known; 49 50 // Are we still trying to solve for the sign bit? 51 if (!Known.isSignBitSet()) { 52 if (NSW) { 53 // Adding two non-negative numbers, or subtracting a negative number from 54 // a non-negative one, can't wrap into negative. 55 if (LHS.isNonNegative() && RHS.isNonNegative()) 56 KnownOut.makeNonNegative(); 57 // Adding two negative numbers, or subtracting a non-negative number from 58 // a negative one, can't wrap into non-negative. 59 else if (LHS.isNegative() && RHS.isNegative()) 60 KnownOut.makeNegative(); 61 } 62 } 63 64 return KnownOut; 65 } 66