lib/Support/KnownBits.cpp

   1 //===-- KnownBits.cpp - Stores known zeros/ones ---------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains a class for representing known zeros and ones used by
  11 // computeKnownBits.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Support/KnownBits.h"
  16
  17 using namespace llvm;
  18
  19 KnownBits KnownBits::computeForAddSub(bool Add, bool NSW,
  20                                       const KnownBits &LHS, KnownBits RHS) {
  21   // Carry in a 1 for a subtract, rather than 0.
  22   bool CarryIn = false;
  23   if (!Add) {
  24     // Sum = LHS + ~RHS + 1
  25     std::swap(RHS.Zero, RHS.One);
  26     CarryIn = true;
  27   }
  28
  29   APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + CarryIn;
  30   APInt PossibleSumOne = LHS.One + RHS.One + CarryIn;
  31
  32   // Compute known bits of the carry.
  33   APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
  34   APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
  35
  36   // Compute set of known bits (where all three relevant bits are known).
  37   APInt LHSKnownUnion = LHS.Zero | LHS.One;
  38   APInt RHSKnownUnion = RHS.Zero | RHS.One;
  39   APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne;
  40   APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;
  41
  42   assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
  43          "known bits of sum differ");
  44
  45   // Compute known bits of the result.
  46   KnownBits KnownOut;
  47   KnownOut.Zero = ~std::move(PossibleSumZero) & Known;
  48   KnownOut.One = std::move(PossibleSumOne) & Known;
  49
  50   // Are we still trying to solve for the sign bit?
  51   if (!Known.isSignBitSet()) {
  52     if (NSW) {
  53       // Adding two non-negative numbers, or subtracting a negative number from
  54       // a non-negative one, can't wrap into negative.
  55       if (LHS.isNonNegative() && RHS.isNonNegative())
  56         KnownOut.makeNonNegative();
  57       // Adding two negative numbers, or subtracting a non-negative number from
  58       // a negative one, can't wrap into non-negative.
  59       else if (LHS.isNegative() && RHS.isNegative())
  60         KnownOut.makeNegative();
  61     }
  62   }
  63
  64   return KnownOut;
  65 }