CIRCT 22.0.0git
Loading...
Searching...
No Matches
GenericLUTMapper.cpp
Go to the documentation of this file.
1//===----------------------------------------------------------------------===//
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 a generic LUT mapper pass using the cut-based rewriting
10// framework. It performs technology mapping by converting combinational logic
11// networks into implementations using K-input lookup tables (LUTs).
12//
13//===----------------------------------------------------------------------===//
14
19#include "circt/Support/LLVM.h"
21#include "mlir/IR/Builders.h"
22#include "mlir/Pass/Pass.h"
23#include "llvm/Support/Debug.h"
24
25#define DEBUG_TYPE "synth-generic-lut-mapper"
26
27using namespace circt;
28using namespace circt::synth;
29
30namespace circt {
31namespace synth {
32#define GEN_PASS_DEF_GENERICLUTMAPPER
33#include "circt/Dialect/Synth/Transforms/SynthPasses.h.inc"
34} // namespace synth
35} // namespace circt
36
37//===----------------------------------------------------------------------===//
38// Generic LUT Pattern
39//===----------------------------------------------------------------------===//
40
41/// A generic K-input LUT pattern that can implement any boolean function
42/// with up to K inputs using a lookup table.
44 unsigned k; // Maximum number of inputs for this LUT
45
46 GenericLUT(mlir::MLIRContext *context, unsigned k)
48
49 bool match(const Cut &cut) const override {
50 // This pattern can implement any cut with at most k inputs
51 return cut.getInputSize() <= k && cut.getOutputSize() == 1;
52 }
53
54 llvm::FailureOr<Operation *> rewrite(mlir::OpBuilder &rewriter,
55 Cut &cut) const override {
56 // NOTE: Don't use NPN since it's unnecessary.
57 auto truthTable = cut.getTruthTable();
58 LLVM_DEBUG({
59 llvm::dbgs() << "Rewriting cut with " << cut.getInputSize()
60 << " inputs and " << cut.getInputSize()
61 << " operations to a generic LUT with " << k << " inputs.\n";
62 cut.dump(llvm::dbgs());
63 llvm::dbgs() << "Truth table details:\n";
64 truthTable.dump(llvm::dbgs());
65 });
66
67 SmallVector<bool> lutTable;
68 // Convert the truth table to a LUT table
69 for (uint32_t i = 0; i < truthTable.table.getBitWidth(); ++i)
70 lutTable.push_back(truthTable.table[i]);
71
72 auto arrayAttr = rewriter.getBoolArrayAttr(
73 lutTable); // Create a boolean array attribute.
74
75 // Reverse the inputs to match the LUT input order
76 SmallVector<Value> lutInputs(cut.inputs.rbegin(), cut.inputs.rend());
77
78 // Generate comb.truth table operation.
79 auto truthTableOp = rewriter.create<comb::TruthTableOp>(
80 cut.getRoot()->getLoc(), lutInputs, arrayAttr);
81
82 // Replace the root operation with the truth table operation
83 return truthTableOp.getOperation();
84 }
85
86 double getArea(const Cut &cut) const override {
87 // Each LUT has unit area regardless of the function it implements
88 return 1.0;
89 }
90
91 DelayType getDelay(unsigned inputIndex, unsigned outputIndex) const override {
92 // All LUTs have unit delay from any input to any output
93 return 1;
94 }
95
96 unsigned getNumInputs() const override { return k; }
97
98 unsigned getNumOutputs() const override { return 1; }
99
100 StringRef getPatternName() const override { return "GenericLUT"; }
101};
102
103//===----------------------------------------------------------------------===//
104// Generic LUT Mapper Pass
105//===----------------------------------------------------------------------===//
106
108 : public impl::GenericLutMapperBase<GenericLUTMapperPass> {
109 using GenericLutMapperBase<GenericLUTMapperPass>::GenericLutMapperBase;
110
111 void runOnOperation() override {
112 auto module = getOperation();
113 // Create the cut rewriter options
114 CutRewriterOptions options;
115 options.strategy = strategy;
116 options.maxCutInputSize = maxLutSize;
117 options.maxCutSizePerRoot = maxCutsPerRoot;
118 options.allowNoMatch = false;
119 options.attachDebugTiming = test;
120
121 // Create the pattern for generic K-LUT
122 SmallVector<std::unique_ptr<CutRewritePattern>, 4> patterns;
123 patterns.push_back(
124 std::make_unique<GenericLUT>(module->getContext(), maxLutSize));
125
126 // Create the pattern set
127 CutRewritePatternSet patternSet(std::move(patterns));
128
129 // Create the cut rewriter
130 CutRewriter rewriter(options, patternSet);
131
132 // Apply the rewriting
133 if (failed(rewriter.run(module)))
134 return signalPassFailure();
135 }
136};
Strategy strategy
Manages a collection of rewriting patterns for combinational logic optimization.
Main cut-based rewriting algorithm for combinational logic optimization.
LogicalResult run(Operation *topOp)
Execute the complete cut-based rewriting algorithm.
Represents a cut in the combinational logic network.
Definition CutRewriter.h:74
unsigned getOutputSize() const
Get the number of outputs from root operation.
mlir::Operation * getRoot() const
Get the root operation of this cut.
llvm::SmallSetVector< mlir::Value, 4 > inputs
External inputs to this cut (cut boundary).
Definition CutRewriter.h:88
void dump(llvm::raw_ostream &os) const
const BinaryTruthTable & getTruthTable() const
Get the truth table for this cut.
unsigned getInputSize() const
Get the number of inputs to this cut.
int64_t DelayType
Definition CutRewriter.h:35
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
void runOnOperation() override
A generic K-input LUT pattern that can implement any boolean function with up to K inputs using a loo...
unsigned getNumInputs() const override
Get the number of inputs this pattern expects.
bool match(const Cut &cut) const override
Check if a cut matches this pattern.
DelayType getDelay(unsigned inputIndex, unsigned outputIndex) const override
Get the delay between specific input and output.
unsigned getNumOutputs() const override
Get the number of outputs this pattern produces.
llvm::FailureOr< Operation * > rewrite(mlir::OpBuilder &rewriter, Cut &cut) const override
Return a new operation that replaces the matched cut.
double getArea(const Cut &cut) const override
Get the area cost of this pattern.
StringRef getPatternName() const override
Get the name of this pattern. Used for debugging.
GenericLUT(mlir::MLIRContext *context, unsigned k)
Base class for cut rewriting patterns used in combinational logic optimization.
mlir::MLIRContext * context
Configuration options for the cut-based rewriting algorithm.
unsigned maxCutInputSize
Maximum number of inputs allowed for any cut.
unsigned maxCutSizePerRoot
Maximum number of cuts to maintain per logic node.
bool allowNoMatch
Fail if there is a root operation that has no matching pattern.
bool attachDebugTiming
Put arrival times to rewritten operations.
OptimizationStrategy strategy
Optimization strategy (area vs. timing).