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
computeForAddSub(bool Add,bool NSW,const KnownBits & LHS,KnownBits RHS)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