LLVM  10.0.0svn
KnownBits.cpp
Go to the documentation of this file.
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 
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.Zero + ~RHS.Zero + !CarryZero;
25  APInt PossibleSumOne = LHS.One + RHS.One + 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 
48  const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) {
49  assert(Carry.getBitWidth() == 1 && "Carry must be 1-bit");
51  LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue());
52 }
53 
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 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:39
static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
Definition: KnownBits.cpp:18
Definition: BitVector.h:937
static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS)
Compute known bits resulting from adding LHS and RHS.
Definition: KnownBits.cpp:54
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:477
static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry)
Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
Definition: KnownBits.cpp:47
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:95
void makeNonNegative()
Make this value non-negative.
Definition: KnownBits.h:106
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
Class for arbitrary precision integers.
Definition: APInt.h:69
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:98
void makeNegative()
Make this value negative.
Definition: KnownBits.h:101