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 KnownBits KnownBits::computeForAddSub(bool Add, bool NSW, 19 const KnownBits &LHS, KnownBits RHS) { 20 // Carry in a 1 for a subtract, rather than 0. 21 bool CarryIn = false; 22 if (!Add) { 23 // Sum = LHS + ~RHS + 1 24 std::swap(RHS.Zero, RHS.One); 25 CarryIn = true; 26 } 27 28 APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + CarryIn; 29 APInt PossibleSumOne = LHS.One + RHS.One + CarryIn; 30 31 // Compute known bits of the carry. 32 APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero); 33 APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One; 34 35 // Compute set of known bits (where all three relevant bits are known). 36 APInt LHSKnownUnion = LHS.Zero | LHS.One; 37 APInt RHSKnownUnion = RHS.Zero | RHS.One; 38 APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne; 39 APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion; 40 41 assert((PossibleSumZero & Known) == (PossibleSumOne & Known) && 42 "known bits of sum differ"); 43 44 // Compute known bits of the result. 45 KnownBits KnownOut; 46 KnownOut.Zero = ~std::move(PossibleSumZero) & Known; 47 KnownOut.One = std::move(PossibleSumOne) & Known; 48 49 // Are we still trying to solve for the sign bit? 50 if (!Known.isSignBitSet()) { 51 if (NSW) { 52 // Adding two non-negative numbers, or subtracting a negative number from 53 // a non-negative one, can't wrap into negative. 54 if (LHS.isNonNegative() && RHS.isNonNegative()) 55 KnownOut.makeNonNegative(); 56 // Adding two negative numbers, or subtracting a non-negative number from 57 // a negative one, can't wrap into non-negative. 58 else if (LHS.isNegative() && RHS.isNegative()) 59 KnownOut.makeNegative(); 60 } 61 } 62 63 return KnownOut; 64 } 65