LLVM  9.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, KnownBits RHS) {
20  // Carry in a 1 for a subtract, rather than 0.
21  bool CarryIn = false;
22  if (!Add) {
23  // Sum = LHS + ~RHS + 1
24  std::swap(RHS.Zero, RHS.One);
25  CarryIn = true;
26  }
27 
28  APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + CarryIn;
29  APInt PossibleSumOne = LHS.One + RHS.One + CarryIn;
30 
31  // Compute known bits of the carry.
32  APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
33  APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
34 
35  // Compute set of known bits (where all three relevant bits are known).
36  APInt LHSKnownUnion = LHS.Zero | LHS.One;
37  APInt RHSKnownUnion = RHS.Zero | RHS.One;
38  APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne;
39  APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;
40 
41  assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
42  "known bits of sum differ");
43 
44  // Compute known bits of the result.
45  KnownBits KnownOut;
46  KnownOut.Zero = ~std::move(PossibleSumZero) & Known;
47  KnownOut.One = std::move(PossibleSumOne) & Known;
48 
49  // Are we still trying to solve for the sign bit?
50  if (!Known.isSignBitSet()) {
51  if (NSW) {
52  // Adding two non-negative numbers, or subtracting a negative number from
53  // a non-negative one, can't wrap into negative.
54  if (LHS.isNonNegative() && RHS.isNonNegative())
55  KnownOut.makeNonNegative();
56  // Adding two negative numbers, or subtracting a non-negative number from
57  // a negative one, can't wrap into non-negative.
58  else if (LHS.isNegative() && RHS.isNegative())
59  KnownOut.makeNegative();
60  }
61  }
62 
63  return KnownOut;
64 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:18
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