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
16using namespace llvm;
17
18static 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
47KnownBits 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
54KnownBits 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