SimplifyTruthTable.cpp

Go to the documentation of this file.

//===----------------------------------------------------------------------===//
//
// 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 the SimplifyTruthTable pass, which simplifies truth
// tables that depend on one or fewer inputs.
//
//===----------------------------------------------------------------------===//
 
#include "circt/Dialect/Comb/CombOps.h"
#include "circt/Dialect/Comb/CombPasses.h"
#include "circt/Dialect/HW/HWOps.h"
#include "circt/Support/Naming.h"
#include "circt/Support/TruthTable.h"
#include "mlir/IR/PatternMatch.h"
#include "mlir/Transforms/WalkPatternRewriteDriver.h"
#include "llvm/Support/LogicalResult.h"
 
using namespace circt;
using namespace comb;
 
namespace circt {
namespace comb {
#define GEN_PASS_DEF_SIMPLIFYTRUTHTABLE
#include "circt/Dialect/Comb/Passes.h.inc"
} // namespace comb
} // namespace circt
 
namespace {
 
// Helper to check if operation is trivially recursive
static bool isOpTriviallyRecursive(Operation *op) {
  return llvm::any_of(op->getOperands(), [op](auto operand) {
    return operand.getDefiningOp() == op;
  });
}
 
// Pattern to simplify truth tables
struct SimplifyTruthTable : public OpRewritePattern<TruthTableOp> {
  using OpRewritePattern::OpRewritePattern;
 
  LogicalResult matchAndRewrite(TruthTableOp op,
                                PatternRewriter &rewriter) const override {
    if (isOpTriviallyRecursive(op))
      return failure();
 
    const auto inputs = op.getInputs();
    const auto table = op.getLookupTable();
    size_t numInputs = inputs.size();
 
    // Check if all table entries are the same (constant output)
    bool allSame = llvm::all_equal(table);
    if (allSame) {
      bool firstValue = table[0];
      auto constOp =
          hw::ConstantOp::create(rewriter, op.getLoc(), APInt(1, firstValue));
      replaceOpAndCopyNamehint(rewriter, op, constOp);
      return success();
    }
 
    // Convert truth table to APInt for cofactor computation
    APInt truthTable(table.size(), 0);
    for (size_t i = 0; i < table.size(); ++i)
      truthTable.setBitVal(i, table[i]);
 
    // Use cofactors to detect which inputs the function depends on
    // A function depends on variable i if its cofactors differ
    // The cofactor function uses bit position indexing (LSB=0),
    // but inputs are indexed with input 0 being the MSB in the truth table
    int dependentInput = -1;
    unsigned numDependencies = 0;
    APInt negativeCofactor, positiveCofactor;
 
    for (size_t bitPos = 0; bitPos < numInputs; ++bitPos) {
      std::tie(negativeCofactor, positiveCofactor) =
          computeCofactors(truthTable, numInputs, bitPos);
 
      // If cofactors differ, the function depends on this variable
      if (negativeCofactor != positiveCofactor) {
        // Convert bit position to input index: bitPos 0 (LSB) = last input
        dependentInput = numInputs - 1 - bitPos;
        numDependencies++;
 
        // Exit early if we found more than one dependency
        if (numDependencies > 1)
          break;
      }
    }
 
    // Only simplify if exactly one input dependency found
    if (numDependencies != 1)
      return failure();
 
    // Determine if the truth table is identity or inverted
    // Check the output when the dependent input is 1 (all other inputs at 0)
    size_t bitPositionInTable = numInputs - 1 - dependentInput;
    size_t idxWhen1 = 1ull << bitPositionInTable;
    bool isIdentity = table[idxWhen1];
 
    // A single-input negation is already in its simplest form
    if (!isIdentity && numInputs == 1)
      return failure();
 
    // Replace with the input or a simpler truth table for negation
    Value input = inputs[dependentInput];
    if (isIdentity) {
      // Identity case: just replace with the input directly
      replaceOpAndCopyNamehint(rewriter, op, input);
    } else {
      // Inverted case: replace with a single-input truth table for negation
      // This avoids introducing comb.xor, which is useful for LUT mapping
      replaceOpWithNewOpAndCopyNamehint<TruthTableOp>(
          rewriter, op, ValueRange{input}, ArrayRef<bool>{true, false});
    }
    return success();
  }
};
 
class SimplifyTruthTablePass
    : public impl::SimplifyTruthTableBase<SimplifyTruthTablePass> {
public:
  using SimplifyTruthTableBase::SimplifyTruthTableBase;
  void runOnOperation() override;
};
 
} // namespace
 
void SimplifyTruthTablePass::runOnOperation() {
  Operation *op = getOperation();
  MLIRContext *context = op->getContext();
  RewritePatternSet patterns(context);
  patterns.add<SimplifyTruthTable>(context);
  walkAndApplyPatterns(op, std::move(patterns));
}