unittests/Support/KnownBitsTest.cpp

   1 //===- llvm/unittest/Support/KnownBitsTest.cpp - KnownBits tests ----------===//
   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 implements unit tests for KnownBits functions.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Support/KnownBits.h"
  14 #include "gtest/gtest.h"
  15
  16 using namespace llvm;
  17
  18 namespace {
  19
  20 template<typename FnTy>
  21 void ForeachKnownBits(unsigned Bits, FnTy Fn) {
  22   unsigned Max = 1 << Bits;
  23   KnownBits Known(Bits);
  24   for (unsigned Zero = 0; Zero < Max; ++Zero) {
  25     for (unsigned One = 0; One < Max; ++One) {
  26       Known.Zero = Zero;
  27       Known.One = One;
  28       if (Known.hasConflict())
  29         continue;
  30
  31       Fn(Known);
  32     }
  33   }
  34 }
  35
  36 template<typename FnTy>
  37 void ForeachNumInKnownBits(const KnownBits &Known, FnTy Fn) {
  38   unsigned Bits = Known.getBitWidth();
  39   unsigned Max = 1 << Bits;
  40   for (unsigned N = 0; N < Max; ++N) {
  41     APInt Num(Bits, N);
  42     if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
  43       continue;
  44
  45     Fn(Num);
  46   }
  47 }
  48
  49 TEST(KnownBitsTest, AddCarryExhaustive) {
  50   unsigned Bits = 4;
  51   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
  52     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
  53       ForeachKnownBits(1, [&](const KnownBits &KnownCarry) {
  54         // Explicitly compute known bits of the addition by trying all
  55         // possibilities.
  56         KnownBits Known(Bits);
  57         Known.Zero.setAllBits();
  58         Known.One.setAllBits();
  59         ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
  60           ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
  61             ForeachNumInKnownBits(KnownCarry, [&](const APInt &Carry) {
  62               APInt Add = N1 + N2;
  63               if (Carry.getBoolValue())
  64                 ++Add;
  65
  66               Known.One &= Add;
  67               Known.Zero &= ~Add;
  68             });
  69           });
  70         });
  71
  72         KnownBits KnownComputed = KnownBits::computeForAddCarry(
  73             Known1, Known2, KnownCarry);
  74         EXPECT_EQ(Known.Zero, KnownComputed.Zero);
  75         EXPECT_EQ(Known.One, KnownComputed.One);
  76       });
  77     });
  78   });
  79 }
  80
  81 static void TestAddSubExhaustive(bool IsAdd) {
  82   unsigned Bits = 4;
  83   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
  84     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
  85       KnownBits Known(Bits), KnownNSW(Bits);
  86       Known.Zero.setAllBits();
  87       Known.One.setAllBits();
  88       KnownNSW.Zero.setAllBits();
  89       KnownNSW.One.setAllBits();
  90
  91       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
  92         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
  93           bool Overflow;
  94           APInt Res;
  95           if (IsAdd)
  96             Res = N1.sadd_ov(N2, Overflow);
  97           else
  98             Res = N1.ssub_ov(N2, Overflow);
  99
 100           Known.One &= Res;
 101           Known.Zero &= ~Res;
 102
 103           if (!Overflow) {
 104             KnownNSW.One &= Res;
 105             KnownNSW.Zero &= ~Res;
 106           }
 107         });
 108       });
 109
 110       KnownBits KnownComputed = KnownBits::computeForAddSub(
 111           IsAdd, /*NSW*/false, Known1, Known2);
 112       EXPECT_EQ(Known.Zero, KnownComputed.Zero);
 113       EXPECT_EQ(Known.One, KnownComputed.One);
 114
 115       // The NSW calculation is not precise, only check that it's
 116       // conservatively correct.
 117       KnownBits KnownNSWComputed = KnownBits::computeForAddSub(
 118           IsAdd, /*NSW*/true, Known1, Known2);
 119       EXPECT_TRUE(KnownNSWComputed.Zero.isSubsetOf(KnownNSW.Zero));
 120       EXPECT_TRUE(KnownNSWComputed.One.isSubsetOf(KnownNSW.One));
 121     });
 122   });
 123 }
 124
 125 TEST(KnownBitsTest, AddSubExhaustive) {
 126   TestAddSubExhaustive(true);
 127   TestAddSubExhaustive(false);
 128 }
 129
 130 } // end anonymous namespace