LLVM  12.0.0git
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 #include <cassert>
16 
17 using namespace llvm;
18 
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 
49  const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) {
50  assert(Carry.getBitWidth() == 1 && "Carry must be 1-bit");
52  LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue());
53 }
54 
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 
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 
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 
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 }
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:19
Definition: BitVector.h:959
static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS)
Compute known bits resulting from adding LHS and RHS.
Definition: KnownBits.cpp:55
zlib style complession
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:482
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:48
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:95
KnownBits & operator^=(const KnownBits &RHS)
Update known bits based on XORing with RHS.
Definition: KnownBits.cpp:102
KnownBits & operator|=(const KnownBits &RHS)
Update known bits based on ORing with RHS.
Definition: KnownBits.cpp:94
APInt getMinValue() const
Return the minimal value possible given these KnownBits.
Definition: KnownBits.h:114
KnownBits & operator &=(const KnownBits &RHS)
Update known bits based on ANDing with RHS.
void makeNonNegative()
Make this value non-negative.
Definition: KnownBits.h:109
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:962
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
APInt getMaxValue() const
Return the maximal value possible given these KnownBits.
Definition: KnownBits.h:120
void makeNegative()
Make this value negative.
Definition: KnownBits.h:104