lib/Support/KnownBits.cpp

   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
  18 static 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.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
  47 KnownBits 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
  54 KnownBits 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 }