[DemandedBits] Improve accuracy of Add propagator

[rrika]

Summary

The current demand propagator for addition will mark all input bits at and right of the alive output bit as alive. But carry won't propagate beyond a bit for which both operands are zero (or one/zero in the case of subtraction) so a more accurate answer is possible given known bits.

I derived a propagator by working through truth tables and using a bit-reversed addition to make demand ripple to the right, but I'm not sure how to make a convincing argument for its correctness in the comments yet. Nevertheless, here's a minimal implementation and test to get feedback.

This would help in a situation where, for example, four bytes (<128) packed into an int are added with four others SIMD-style but only one of the four results is actually read.

Known A:     0_______0_______0_______0_______
Known B:     0_______0_______0_______0_______
AOut:        00000000001000000000000000000000
AB, current: 00000000001111111111111111111111
AB, patch:   00000000001111111000000000000000

[lebedev.ri]

Can an exhaustive test be added for this?

[rrika]

By exhaustive test you mean an .ll file, or a program looping over all values? In the process of writing this I found a mistake (the final '+1' only applies to additions, not subtractions) so I'll edit the patch in a bit.

UPDATE: The original propagator was fine. It was the source below that had a mistake. I marked the changes below with '// EDIT'

// exhaustive test for add demand propagator on 4 bit integers

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
typedef uint8_t u8;
typedef uint8_t u16;
typedef uint32_t u32;

u8 flip_nybble[256] = {
	0x0, 0x8, 0x4, 0xC, 0x2, 0xA, 0x6, 0xE, 0x1, 0x9, 0x5, 0xD, 0x3, 0xB, 0x7, 0xF
};

static int mode; // 0=add 1=sub
static u8 a, b, ka, kb, aout;
static u8 aa, ab;

void fail (int x, int y) {
	u8 ab = 0xf & (mode ? a-b : a+b);
	u8 xy = 0xf & (mode ? x-y : x+y);
	char c = mode ? '-' : '+';
	printf(
		"propagator failed:\n"
		"  a=%01x ka=%01x aa=%01x   x=%01x\n"
		"  b=%01x kb=%01x ab=%01x   y=%01x\n"
		"a%cb=%01x    aout=%01x x%cy=%01x\n",
		a, ka, aa, x,
		b, kb, ab, y,
		c, ab, aout, c, xy
	);
	exit(1);
}

void confirm_add (u8 x, u8 y) {
	x = (x & ~aa) | a; // a and x match in alive bits
	y = (y & ~ab) | b; // b and y match in alive bits
	int ok = (((a+b) ^ (x+y)) & aout) == 0; // then a+b and x+y must match in alive bits
	if (!ok)
		fail(x, y);
}

void confirm_sub (u8 x, u8 y) {
	x = (x & ~aa) | a; // a and x match in alive bits
	y = (y & ~ab) | b; // b and y match in alive bits
	int ok = (((a-b) ^ (x-y)) & aout) == 0; // then a-b and x-y must match in alive bits
	if (!ok)
		fail(x, y);
}

void confirm_adds () {
	for (u32 xy=0; xy < 256; xy++) {
		u8 x = (xy >> 0) & 0xf;
		u8 y = (xy >> 4) & 0xf;
		confirm_add(x, y);
	}
}

void confirm_subs () {
	for (u32 xy=0; xy < 256; xy++) {
		u8 x = (xy >> 0) & 0xf;
		u8 y = (xy >> 4) & 0xf;
		confirm_sub(x, y);
	}
}


int main (int argc, char **argv) {
	(void) argc;
	(void) argv;
	for (mode=0; mode<2; mode++) // 0 = add, 1 = sub
	for (u32 t=0; t < 0x100000; t++) {
		a    = (t >>  0) & 0xf;
		b    = (t >>  4) & 0xf;
		ka   = (t >>  8) & 0xf;
		kb   = (t >> 12) & 0xf;
		aout = (t >> 16) & 0xf;

		u8 a0 = ~a & ka;
		u8 a1 =  a & ka;
		u8 b0 = ~b & kb;
		u8 b1 =  b & kb;

		// now the propagator
		// EDIT:
		u8 bound1 = mode ? a1 : a0;
		u8 bound2 = b0;
		// u8 bound1 = a0;
		// u8 bound2 = mode ? b1 : b0;
		u8 bound = bound1 & bound2;
		u8 rbound = flip_nybble[bound];
		u8 raout = flip_nybble[aout];
		u8 rprop = raout + (raout | ~rbound);
		u8 rq = (rprop ^ ~(raout | rbound));
		rq &= 0xf;

		u8 q = flip_nybble[rq];
		u8 ua = bound1 | ~bound2;
		u8 ub = bound2 | ~bound1;
		// EDIT:
		aa = aout | (q & (ua | (bound1 + bound2 + 1)));
		ab = aout | (q & (ub | (bound1 + bound2 + 1)));
		// aa = aout | (q & (ua | (bound1 + bound2 + (mode?0:1))));
		// ab = aout | (q & (ub | (bound1 + bound2 + (mode?0:1))));

		aa &= 0xf;
		ab &= 0xf;

		if (mode == 0)
			confirm_adds(a, b, aa, ab, aout);
		else
			confirm_subs(a, b, aa, ab, aout);
	}
	return 0;
}

[lebedev.ri]

In D72423#1811604, @rrika wrote:

By exhaustive test you mean an .ll file, or a program looping over all values?

No, a unit test.
See llvm/unittests/IR/ConstantRangeTest.cpp for inspiration.

In the process of writing this I found a mistake (the final '+1' only applies to additions, not subtractions) so I'll edit the patch in a bit.

(That's why such a test should exist)

[rrika]

Here's an update to confirm that the unit test is going in the right direction. DemandedBits::determineLiveOperandBits is private, so right now it seems to be necessary to build up all this IR before each query. I have yet to read up on what allocation responsibilities are, because creating new llvm contexts in a hot loop doesn't feel like the way it's meant to be done.

[nikic]

@rrika Performing these kinds of tests on IR is both quite inefficient and unnecessary complex. It would be better to extract the code logic (which just operates on APInts) into a separate file, which will allow you to easily test it, and also share the logic with other places doing demanded bits analysis, such as InstCombine and SelectionDAG.

[lebedev.ri]

In D72423#1815871, @nikic wrote:

@rrika Performing these kinds of tests on IR is both quite inefficient and unnecessary complex. It would be better to extract the code logic (which just operates on APInts) into a separate file, which will allow you to easily test it, and also share the logic with other places doing demanded bits analysis, such as InstCombine and SelectionDAG.

[rrika]

In D72423#1815871, @nikic wrote:

@rrika Performing these kinds of tests on IR is both quite inefficient and unnecessary complex. It would be better to extract the code logic (which just operates on APInts) into a separate file, which will allow you to easily test it, and also share the logic with other places doing demanded bits analysis, such as InstCombine and SelectionDAG.

Are you suggesting factoring out the logic for addition/subtraction only or all opcodes? Where should this new function live?

[nikic]

In D72423#1816715, @rrika wrote:

In D72423#1815871, @nikic wrote:

@rrika Performing these kinds of tests on IR is both quite inefficient and unnecessary complex. It would be better to extract the code logic (which just operates on APInts) into a separate file, which will allow you to easily test it, and also share the logic with other places doing demanded bits analysis, such as InstCombine and SelectionDAG.

Are you suggesting factoring out the logic for addition/subtraction only or all opcodes? Where should this new function live?

At least to start with, only addition/subtraction is fine. I'm not totally sure where it would live, but as we have KnownBits in Support, possibly there?

[rrika]

Changes:

• The test no longer builds a temporary IR. The propagator is instead exposed as a static member function on llvm::DemandedBits.
• The propagator now also recognizes a pair of one bits as blocking carry.

[rrika]

Ping

[RKSimon]

Adding @regehr and @nikic as they might have some thoughts on this

If possible I'd like to see some tests in InstCombine/InstSimplify that demonstrates the benefit of this.

Does anyone have comments about the exhaustive tests? 4 bits shouldn't take very long to complete but I'm not sure about general policy on this approach.

llvm/include/llvm/Analysis/DemandedBits.h

76

Would it make sense to move this into KnownBits so DAG/GlobalIsel can reuse it more easily?

[lebedev.ri]

This seems okay to me in general, assuming i'm not misreading the tests and they are actually exhaustive.

In D72423#1959341, @RKSimon wrote:

Adding @regehr and @nikic as they might have some thoughts on this

If possible I'd like to see some tests in InstCombine/InstSimplify that demonstrates the benefit of this.

I too would like to see some such test.

Does anyone have comments about the exhaustive tests? 4 bits shouldn't take very long to complete but I'm not sure about general policy on this approach.

That is fine by me. This is what is being done for all the good ConstantRange tests already anyway.

llvm/include/llvm/Analysis/DemandedBits.h

64–66

I find the naming scheme confusing. Why [a]live?
What we are deducing here, is what bits of operand OperandNo
are actually *demanded* given the demanded bits of result of operation, no?

llvm/lib/Analysis/DemandedBits.cpp

490–491

Assert only one carry is selected?

llvm/unittests/IR/DemandedBitsTest.cpp

18–39

I think there's some intersection with helpers defined in KnownBitsTest.cpp
It would be best to move them into one common header (KnownBitsTest.h?) and use them consistently.

19

I think this is just ForeachKnownBits() from KnownBitsTest.cpp?

32

This looks like to be ForeachNumInKnownBits()?

[lebedev.ri]

as per my last comment

[rrika]

Sorry for the delay. Changes:

• ForeachKnownBits / ForeachNumInKnownBits in their own header
• Added a fast path for the case that AOut is shaped like 00001111 (if (AOut.isMask()) { AB = AOut; }), importantly known bits of the arguments are not computed in this case
• Added an assertion for the carry

In D72423#1959341, @RKSimon wrote:

[...] If possible I'd like to see some tests in InstCombine/InstSimplify that demonstrates the benefit of this. [...]

What would that look like exactly? I guess you mean something other than the new test/Analysis/DemandedBits/add.ll.

[rrika]

llvm/include/llvm/Analysis/DemandedBits.h

64–66

determineLiveOperandBitsAdd and determineLiveOperandBitsSub are factored out of determineLiveOperandBits so that's where the name is from. I believe the names demanded bits/alive bits are interchangeable in this context?

76

Is that a question to me, or the other reviewers?

[lebedev.ri]

LGTM
@RKSimon ?

[RKSimon]

llvm/test/Analysis/DemandedBits/add.ll

18

@rrika I'm going to pre-commit this to show trunk's current output, then you'll need to rebase so this patch shows the delta

[lebedev.ri]

llvm/test/Analysis/DemandedBits/add.ll

4

Is the order not deterministic?
It would be best to test everything there is in the output.

18

Isn't there some transform pass based on demandedbits analysis?
Can that test be added to that pass, too?

[rrika]

Rebased to modify add.ll instead of creating it.

[rrika]

llvm/test/Analysis/DemandedBits/add.ll

4

It seems not to be. The other tests in that directory also used CHECK-DAG for this.

llvm/include/llvm/Analysis/DemandedBits.h

public:
   /// Return true if, during analysis, I could not be reached.
   bool isInstructionDead(Instruction *I);
 
   /// Return whether this use is dead by means of not having any demanded bits.
   bool isUseDead(Use *U);
 
   void print(raw_ostream &OS);
 
+  /// Compute alive bits of one addition operand from alive output and known
+  /// operand bits
+  static APInt determineLiveOperandBitsAdd(unsigned OperandNo,
+                                           const APInt &AOut,
+                                           const KnownBits &LHS,
+                                           const KnownBits &RHS);
+
+  /// Compute alive bits of one subtraction operand from alive output and known
+  /// operand bits
+  static APInt determineLiveOperandBitsSub(unsigned OperandNo,
+                                           const APInt &AOut,
+                                           const KnownBits &LHS,
+                                           const KnownBits &RHS);
+
 private:
   void performAnalysis();
   void determineLiveOperandBits(const Instruction *UserI,
     const Value *Val, unsigned OperandNo,
     const APInt &AOut, APInt &AB,
     KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed);
 
   Function &F;

llvm/lib/Analysis/DemandedBits.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI))
           else if (OperandNo == 1)
             AB = AOut.shl(BitWidth - ShiftAmt);
         }
         break;
       }
       }
     break;
   case Instruction::Add:
+    if (AOut.isMask()) {
+      AB = AOut;
+    } else {
+      ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
+      AB = determineLiveOperandBitsAdd(OperandNo, AOut, Known, Known2);
+    }
+    break;
   case Instruction::Sub:
+    if (AOut.isMask()) {
+      AB = AOut;
+    } else {
+      ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
+      AB = determineLiveOperandBitsSub(OperandNo, AOut, Known, Known2);
+    }
+    break;
   case Instruction::Mul:
     // Find the highest live output bit. We don't need any more input
     // bits than that (adds, and thus subtracts, ripple only to the
     // left).
     AB = APInt::getLowBitsSet(BitWidth, AOut.getActiveBits());
     break;
   case Instruction::Shl:
     if (OperandNo == 0) {

 void DemandedBits::print(raw_ostream &OS) {
   performAnalysis();
   for (auto &KV : AliveBits) {
     OS << "DemandedBits: 0x" << Twine::utohexstr(KV.second.getLimitedValue())
        << " for " << *KV.first << '\n';
   }
 }
 
+static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo,
+                                              const APInt &AOut,
+                                              const KnownBits &LHS,
+                                              const KnownBits &RHS,
+                                              bool CarryZero, bool CarryOne) {
+  assert(!(CarryZero && CarryOne) &&
+         "Carry can't be zero and one at the same time");
+
+  // The following check should be done by the caller, as it also indicates
+  // that LHS and RHS don't need to be computed.
+  //
+  // if (AOut.isMask())
+  //   return AOut;
+
+  // Boundary bits' carry out is unaffected by their carry in.
+  APInt Bound = (LHS.Zero & RHS.Zero) | (LHS.One & RHS.One);
+
+  // First, the alive carry bits are determined from the alive output bits:
+  // Let demand ripple to the right but only up to any set bit in Bound.
+  //   AOut         = -1----
+  //   Bound        = ----1-
+  //   ACarry&~AOut = --111-
+  APInt RBound = Bound.reverseBits();
+  APInt RAOut = AOut.reverseBits();
+  APInt RProp = RAOut + (RAOut | ~RBound);
+  APInt RACarry = RProp ^ ~RBound;
+  APInt ACarry = RACarry.reverseBits();
+
+  // Then, the alive input bits are determined from the alive carry bits:
+  APInt NeededToMaintainCarryZero;
+  APInt NeededToMaintainCarryOne;
+  if (OperandNo == 0) {
+    NeededToMaintainCarryZero = LHS.Zero | ~RHS.Zero;
+    NeededToMaintainCarryOne = LHS.One | ~RHS.One;
+  } else {
+    NeededToMaintainCarryZero = RHS.Zero | ~LHS.Zero;
+    NeededToMaintainCarryOne = RHS.One | ~LHS.One;
+  }
+
+  // As in computeForAddCarry
+  APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + !CarryZero;
+  APInt PossibleSumOne = LHS.One + RHS.One + CarryOne;
+
+  // The below is simplified from
+  //
+  // APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
+  // APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
+  // APInt CarryUnknown = ~(CarryKnownZero | CarryKnownOne);
+  //
+  // APInt NeededToMaintainCarry =
+  //   (CarryKnownZero & NeededToMaintainCarryZero) |
+  //   (CarryKnownOne  & NeededToMaintainCarryOne) |
+  //   CarryUnknown;
+
+  APInt NeededToMaintainCarry = (~PossibleSumZero | NeededToMaintainCarryZero) &
+                                (PossibleSumOne | NeededToMaintainCarryOne);
+
+  APInt AB = AOut | (ACarry & NeededToMaintainCarry);
+  return AB;
+}
+
+APInt DemandedBits::determineLiveOperandBitsAdd(unsigned OperandNo,
+                                                const APInt &AOut,
+                                                const KnownBits &LHS,
+                                                const KnownBits &RHS) {
+  return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, RHS, true,
+                                          false);
+}
+
+APInt DemandedBits::determineLiveOperandBitsSub(unsigned OperandNo,
+                                                const APInt &AOut,
+                                                const KnownBits &LHS,
+                                                const KnownBits &RHS) {
+  KnownBits NRHS;
+  NRHS.Zero = RHS.One;
+  NRHS.One = RHS.Zero;
+  return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, NRHS, false,
+                                          true);
+}
+
 FunctionPass *llvm::createDemandedBitsWrapperPass() {
   return new DemandedBitsWrapperPass();
 }
 
 AnalysisKey DemandedBitsAnalysis::Key;
 
 DemandedBits DemandedBitsAnalysis::run(Function &F,
                                              FunctionAnalysisManager &AM) {

llvm/test/Analysis/DemandedBits/add.ll

+; RUN: opt -S -demanded-bits -analyze < %s | FileCheck %s
+; RUN: opt -S -disable-output -passes="print<demanded-bits>" < %s 2>&1 | FileCheck %s
+
+; CHECK-DAG: DemandedBits: 0x1e for   %1 = and i32 %a, 9
+; CHECK-DAG: DemandedBits: 0x1a for   %2 = and i32 %b, 9
+; CHECK-DAG: DemandedBits: 0x1a for   %3 = and i32 %c, 13
+; CHECK-DAG: DemandedBits: 0x1a for   %4 = and i32 %d, 4
+define i32 @test_add(i32 %a, i32 %b, i32 %c, i32 %d) {
+  %1 = and i32 %a, 9
+  %2 = and i32 %b, 9
+  %3 = and i32 %c, 13
+  %4 = and i32 %d, 4 ; no bit of %d alive, %4 simplifies to zero
+  %5 = or i32 %2, %3
+  %6 = or i32 %4, %5
+  %7 = add i32 %1, %6
+  %8 = and i32 %7, 16
+  ret i32 %8
+}

llvm/unittests/IR/CMakeLists.txt

add_llvm_unittest(IRTests
   AttributesTest.cpp
   BasicBlockTest.cpp
   CFGBuilder.cpp
   ConstantRangeTest.cpp
   ConstantsTest.cpp
   DataLayoutTest.cpp
   DebugInfoTest.cpp
   DebugTypeODRUniquingTest.cpp
+  DemandedBitsTest.cpp
   DominatorTreeTest.cpp
   DominatorTreeBatchUpdatesTest.cpp
   FunctionTest.cpp
   PassBuilderCallbacksTest.cpp
   IRBuilderTest.cpp
   InstructionsTest.cpp
   IntrinsicsTest.cpp
   LegacyPassManagerTest.cpp

llvm/unittests/IR/DemandedBitsTest.cpp

+//===- DemandedBitsTest.cpp - DemandedBits tests --------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/DemandedBits.h"
+#include "../Support/KnownBitsTest.h"
+#include "llvm/Support/KnownBits.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+template <typename Fn1, typename Fn2>
+static void TestBinOpExhaustive(Fn1 PropagateFn, Fn2 EvalFn) {
+  unsigned Bits = 4;
+  unsigned Max = 1 << Bits;
+  ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
+    ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
+      for (unsigned AOut_ = 0; AOut_ < Max; AOut_++) {
+        APInt AOut(Bits, AOut_);
+        APInt AB1 = PropagateFn(0, AOut, Known1, Known2);
+        APInt AB2 = PropagateFn(1, AOut, Known1, Known2);
+        {
+          // If the propagator claims that certain known bits
+          // didn't matter, check it doesn't change its mind
+          // when they become unknown.
+          KnownBits Known1Redacted;
+          KnownBits Known2Redacted;
+          Known1Redacted.Zero = Known1.Zero & AB1;
+          Known1Redacted.One = Known1.One & AB1;
+          Known2Redacted.Zero = Known2.Zero & AB2;
+          Known2Redacted.One = Known2.One & AB2;
+
+          APInt AB1R = PropagateFn(0, AOut, Known1Redacted, Known2Redacted);
+          APInt AB2R = PropagateFn(1, AOut, Known1Redacted, Known2Redacted);
+          EXPECT_EQ(AB1, AB1R);
+          EXPECT_EQ(AB2, AB2R);
+        }
+        ForeachNumInKnownBits(Known1, [&](APInt Value1) {
+          ForeachNumInKnownBits(Known2, [&](APInt Value2) {
+            APInt ReferenceResult = EvalFn((Value1 & AB1), (Value2 & AB2));
+            APInt Result = EvalFn(Value1, Value2);
+            EXPECT_EQ(Result & AOut, ReferenceResult & AOut);
+          });
+        });
+      }
+    });
+  });
+}
+
+TEST(DemandedBitsTest, Add) {
+  TestBinOpExhaustive(DemandedBits::determineLiveOperandBitsAdd,
+                      [](APInt N1, APInt N2) -> APInt { return N1 + N2; });
+}
+
+TEST(DemandedBitsTest, Sub) {
+  TestBinOpExhaustive(DemandedBits::determineLiveOperandBitsSub,
+                      [](APInt N1, APInt N2) -> APInt { return N1 - N2; });
+}
+
+} // anonymous namespace

llvm/unittests/Support/KnownBitsTest.h

+//===- llvm/unittest/Support/KnownBitsTest.h - KnownBits tests ------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements helpers for KnownBits and DemandedBits unit tests.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UNITTESTS_SUPPORT_KNOWNBITSTEST_H
+#define LLVM_UNITTESTS_SUPPORT_KNOWNBITSTEST_H
+
+#include "llvm/Support/KnownBits.h"
+
+namespace {
+
+using namespace llvm;
+
+template <typename FnTy> void ForeachKnownBits(unsigned Bits, FnTy Fn) {
+  unsigned Max = 1 << Bits;
+  KnownBits Known(Bits);
+  for (unsigned Zero = 0; Zero < Max; ++Zero) {
+    for (unsigned One = 0; One < Max; ++One) {
+      Known.Zero = Zero;
+      Known.One = One;
+      if (Known.hasConflict())
+        continue;
+
+      Fn(Known);
+    }
+  }
+}
+
+template <typename FnTy>
+void ForeachNumInKnownBits(const KnownBits &Known, FnTy Fn) {
+  unsigned Bits = Known.getBitWidth();
+  unsigned Max = 1 << Bits;
+  for (unsigned N = 0; N < Max; ++N) {
+    APInt Num(Bits, N);
+    if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
+      continue;
+
+    Fn(Num);
+  }
+}
+
+} // end anonymous namespace
+
+#endif

llvm/unittests/Support/KnownBitsTest.cpp

 //===- llvm/unittest/Support/KnownBitsTest.cpp - KnownBits tests ----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements unit tests for KnownBits functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/KnownBits.h"
+#include "KnownBitsTest.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
-template<typename FnTy>
-void ForeachKnownBits(unsigned Bits, FnTy Fn) {
-  unsigned Max = 1 << Bits;
-  KnownBits Known(Bits);
-  for (unsigned Zero = 0; Zero < Max; ++Zero) {
-    for (unsigned One = 0; One < Max; ++One) {
-      Known.Zero = Zero;
-      Known.One = One;
-      if (Known.hasConflict())
-        continue;
-
-      Fn(Known);
-    }
-  }
-}
-
-template<typename FnTy>
-void ForeachNumInKnownBits(const KnownBits &Known, FnTy Fn) {
-  unsigned Bits = Known.getBitWidth();
-  unsigned Max = 1 << Bits;
-  for (unsigned N = 0; N < Max; ++N) {
-    APInt Num(Bits, N);
-    if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
-      continue;
-
-    Fn(Num);
-  }
-}
-
 TEST(KnownBitsTest, AddCarryExhaustive) {
   unsigned Bits = 4;
   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
       ForeachKnownBits(1, [&](const KnownBits &KnownCarry) {
         // Explicitly compute known bits of the addition by trying all
         // possibilities.
         KnownBits Known(Bits);