1 //===-- KnownBits.cpp - Stores known zeros/ones ---------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains a class for representing known zeros and ones used by 10 // computeKnownBits. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Support/KnownBits.h" 15 16 using namespace llvm; 17 18 static KnownBits computeForAddCarry( 19 const KnownBits &LHS, const KnownBits &RHS, 20 bool CarryZero, bool CarryOne) { 21 assert(!(CarryZero && CarryOne) && 22 "Carry can't be zero and one at the same time"); 23 24 APInt PossibleSumZero = LHS.getMaxValue() + RHS.getMaxValue() + !CarryZero; 25 APInt PossibleSumOne = LHS.getMinValue() + RHS.getMinValue() + CarryOne; 26 27 // Compute known bits of the carry. 28 APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero); 29 APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One; 30 31 // Compute set of known bits (where all three relevant bits are known). 32 APInt LHSKnownUnion = LHS.Zero | LHS.One; 33 APInt RHSKnownUnion = RHS.Zero | RHS.One; 34 APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne; 35 APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion; 36 37 assert((PossibleSumZero & Known) == (PossibleSumOne & Known) && 38 "known bits of sum differ"); 39 40 // Compute known bits of the result. 41 KnownBits KnownOut; 42 KnownOut.Zero = ~std::move(PossibleSumZero) & Known; 43 KnownOut.One = std::move(PossibleSumOne) & Known; 44 return KnownOut; 45 } 46 47 KnownBits KnownBits::computeForAddCarry( 48 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) { 49 assert(Carry.getBitWidth() == 1 && "Carry must be 1-bit"); 50 return ::computeForAddCarry( 51 LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue()); 52 } 53 54 KnownBits KnownBits::computeForAddSub(bool Add, bool NSW, 55 const KnownBits &LHS, KnownBits RHS) { 56 KnownBits KnownOut; 57 if (Add) { 58 // Sum = LHS + RHS + 0 59 KnownOut = ::computeForAddCarry( 60 LHS, RHS, /*CarryZero*/true, /*CarryOne*/false); 61 } else { 62 // Sum = LHS + ~RHS + 1 63 std::swap(RHS.Zero, RHS.One); 64 KnownOut = ::computeForAddCarry( 65 LHS, RHS, /*CarryZero*/false, /*CarryOne*/true); 66 } 67 68 // Are we still trying to solve for the sign bit? 69 if (!KnownOut.isNegative() && !KnownOut.isNonNegative()) { 70 if (NSW) { 71 // Adding two non-negative numbers, or subtracting a negative number from 72 // a non-negative one, can't wrap into negative. 73 if (LHS.isNonNegative() && RHS.isNonNegative()) 74 KnownOut.makeNonNegative(); 75 // Adding two negative numbers, or subtracting a non-negative number from 76 // a negative one, can't wrap into non-negative. 77 else if (LHS.isNegative() && RHS.isNegative()) 78 KnownOut.makeNegative(); 79 } 80 } 81 82 return KnownOut; 83 } 84