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 #include <cassert> 16 17 using namespace llvm; 18 19 static KnownBits computeForAddCarry( 20 const KnownBits &LHS, const KnownBits &RHS, 21 bool CarryZero, bool CarryOne) { 22 assert(!(CarryZero && CarryOne) && 23 "Carry can't be zero and one at the same time"); 24 25 APInt PossibleSumZero = LHS.getMaxValue() + RHS.getMaxValue() + !CarryZero; 26 APInt PossibleSumOne = LHS.getMinValue() + RHS.getMinValue() + CarryOne; 27 28 // Compute known bits of the carry. 29 APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero); 30 APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One; 31 32 // Compute set of known bits (where all three relevant bits are known). 33 APInt LHSKnownUnion = LHS.Zero | LHS.One; 34 APInt RHSKnownUnion = RHS.Zero | RHS.One; 35 APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne; 36 APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion; 37 38 assert((PossibleSumZero & Known) == (PossibleSumOne & Known) && 39 "known bits of sum differ"); 40 41 // Compute known bits of the result. 42 KnownBits KnownOut; 43 KnownOut.Zero = ~std::move(PossibleSumZero) & Known; 44 KnownOut.One = std::move(PossibleSumOne) & Known; 45 return KnownOut; 46 } 47 48 KnownBits KnownBits::computeForAddCarry( 49 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) { 50 assert(Carry.getBitWidth() == 1 && "Carry must be 1-bit"); 51 return ::computeForAddCarry( 52 LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue()); 53 } 54 55 KnownBits KnownBits::computeForAddSub(bool Add, bool NSW, 56 const KnownBits &LHS, KnownBits RHS) { 57 KnownBits KnownOut; 58 if (Add) { 59 // Sum = LHS + RHS + 0 60 KnownOut = ::computeForAddCarry( 61 LHS, RHS, /*CarryZero*/true, /*CarryOne*/false); 62 } else { 63 // Sum = LHS + ~RHS + 1 64 std::swap(RHS.Zero, RHS.One); 65 KnownOut = ::computeForAddCarry( 66 LHS, RHS, /*CarryZero*/false, /*CarryOne*/true); 67 } 68 69 // Are we still trying to solve for the sign bit? 70 if (!KnownOut.isNegative() && !KnownOut.isNonNegative()) { 71 if (NSW) { 72 // Adding two non-negative numbers, or subtracting a negative number from 73 // a non-negative one, can't wrap into negative. 74 if (LHS.isNonNegative() && RHS.isNonNegative()) 75 KnownOut.makeNonNegative(); 76 // Adding two negative numbers, or subtracting a non-negative number from 77 // a negative one, can't wrap into non-negative. 78 else if (LHS.isNegative() && RHS.isNegative()) 79 KnownOut.makeNegative(); 80 } 81 } 82 83 return KnownOut; 84 } 85 86 KnownBits &KnownBits::operator&=(const KnownBits &RHS) { 87 // Result bit is 0 if either operand bit is 0. 88 Zero |= RHS.Zero; 89 // Result bit is 1 if both operand bits are 1. 90 One &= RHS.One; 91 return *this; 92 } 93 94 KnownBits &KnownBits::operator|=(const KnownBits &RHS) { 95 // Result bit is 0 if both operand bits are 0. 96 Zero &= RHS.Zero; 97 // Result bit is 1 if either operand bit is 1. 98 One |= RHS.One; 99 return *this; 100 } 101 102 KnownBits &KnownBits::operator^=(const KnownBits &RHS) { 103 // Result bit is 0 if both operand bits are 0 or both are 1. 104 APInt Z = (Zero & RHS.Zero) | (One & RHS.One); 105 // Result bit is 1 if one operand bit is 0 and the other is 1. 106 One = (Zero & RHS.One) | (One & RHS.Zero); 107 Zero = std::move(Z); 108 return *this; 109 } 110