24#include "mlir/Analysis/TopologicalSortUtils.h"
25#include "mlir/IR/Builders.h"
26#include "mlir/IR/BuiltinOps.h"
27#include "mlir/IR/DialectRegistry.h"
28#include "mlir/IR/OperationSupport.h"
29#include "mlir/IR/RegionKindInterface.h"
30#include "mlir/IR/Visitors.h"
31#include "mlir/Support/LogicalResult.h"
32#include "mlir/Tools/mlir-translate/Translation.h"
33#include "llvm/ADT/DenseMap.h"
34#include "llvm/ADT/EquivalenceClasses.h"
35#include "llvm/ADT/SmallVector.h"
36#include "llvm/ADT/StringExtras.h"
37#include "llvm/ADT/StringRef.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/LEB128.h"
40#include "llvm/Support/raw_ostream.h"
50#define DEBUG_TYPE "export-aiger"
58 return hw::getBitWidth(value.getType());
74 : module(module), os(os), options(options), handler(handler) {}
77 LogicalResult exportModule();
80 using Object = std::pair<Value, int>;
84 llvm::raw_ostream &os;
89 DenseMap<Object, unsigned> valueLiteralMap;
92 unsigned getNumInputs() {
return inputs.size(); }
93 unsigned getNumLatches() {
return latches.size(); }
94 unsigned getNumOutputs() {
return outputs.size(); }
95 unsigned getNumAnds() {
return andGates.size(); }
97 llvm::EquivalenceClasses<Object> valueEquivalence;
98 SmallVector<std::pair<Object, StringAttr>> inputs;
99 SmallVector<std::tuple<Object, StringAttr, Object>>
101 SmallVector<std::pair<Object, StringAttr>> outputs;
102 SmallVector<std::tuple<Object, Object, Object>> andGates;
104 std::optional<Value> clock;
107 LogicalResult analyzeModule();
110 StringAttr getIndexName(
Object obj, StringAttr name) {
112 obj.first.getType().isInteger(1))
115 return StringAttr::get(name.getContext(),
116 name.getValue() +
"[" + Twine(obj.second) +
"]");
120 void addInput(
Object obj, StringAttr name = {}) {
121 inputs.push_back({obj, getIndexName(obj, name)});
125 void addLatch(
Object current,
Object next, StringAttr name = {}) {
126 latches.push_back({current, getIndexName(current, name), next});
130 void addOutput(
Object obj, StringAttr name = {}) {
131 outputs.push_back({obj, getIndexName(obj, name)});
141 LogicalResult assignLiterals();
144 LogicalResult writeHeader();
145 LogicalResult writeInputs();
146 LogicalResult writeLatches();
147 LogicalResult writeOutputs();
148 LogicalResult writeAndGates();
149 LogicalResult writeSymbolTable();
150 LogicalResult writeComments();
153 LogicalResult visit(Operation *op);
156 LogicalResult visit(aig::AndInverterOp op);
160 LogicalResult visit(comb::ReplicateOp op);
163 unsigned getLiteral(
Object obj,
bool inverted =
false);
172LogicalResult AIGERExporter::exportModule() {
173 LLVM_DEBUG(llvm::dbgs() <<
"Starting AIGER export\n");
174 if (failed(analyzeModule()) || failed(writeHeader()) ||
175 failed(writeInputs()) || failed(writeLatches()) ||
176 failed(writeOutputs()) || failed(writeAndGates()) ||
177 failed(writeSymbolTable()) || failed(writeComments()))
180 LLVM_DEBUG(llvm::dbgs() <<
"AIGER export completed successfully\n");
184LogicalResult AIGERExporter::analyzeModule() {
185 LLVM_DEBUG(llvm::dbgs() <<
"Analyzing module\n");
187 auto topModule =
module;
188 LLVM_DEBUG(llvm::dbgs() <<
"Found top module: " << topModule.getModuleName()
192 if (failed(analyzePorts(topModule)))
196 if (failed(analyzeOperations(topModule)))
200 if (failed(assignLiterals()))
203 LLVM_DEBUG(llvm::dbgs() <<
"Analysis complete: M="
204 << getNumInputs() + getNumLatches() + getNumAnds()
205 <<
" I=" << getNumInputs() <<
" L=" << getNumLatches()
206 <<
" O=" << getNumOutputs() <<
" A=" << getNumAnds()
212LogicalResult AIGERExporter::writeHeader() {
213 LLVM_DEBUG(llvm::dbgs() <<
"Writing AIGER header\n");
222 os <<
" " << getNumInputs() + getNumLatches() + getNumAnds() <<
" "
223 << getNumInputs() <<
" " << getNumLatches() <<
" " << getNumOutputs()
224 <<
" " << getNumAnds() <<
"\n";
229LogicalResult AIGERExporter::writeInputs() {
230 LLVM_DEBUG(llvm::dbgs() <<
"Writing inputs\n");
237 for (
auto [input, name] : inputs)
238 os << getLiteral(input) <<
"\n";
243LogicalResult AIGERExporter::writeLatches() {
244 LLVM_DEBUG(llvm::dbgs() <<
"Writing latches\n");
247 for (
auto [current, currentName, next] : latches) {
251 unsigned nextLiteral = getLiteral(next);
255 os << nextLiteral <<
"\n";
257 os << getLiteral(current) <<
" " << nextLiteral <<
"\n";
264LogicalResult AIGERExporter::writeOutputs() {
265 LLVM_DEBUG(llvm::dbgs() <<
"Writing outputs\n");
268 for (
auto [output, _] : outputs)
269 os << getLiteral(output) <<
"\n";
274LogicalResult AIGERExporter::writeAndGates() {
275 LLVM_DEBUG(llvm::dbgs() <<
"Writing AND gates\n");
279 for (
auto [lhs, rhs0, rhs1] : andGates) {
280 unsigned lhsLiteral = getLiteral(lhs);
283 auto andInvOp = lhs.first.getDefiningOp<aig::AndInverterOp>();
284 assert(andInvOp && andInvOp.getInputs().size() == 2);
287 bool rhs0Inverted = andInvOp.getInverted()[0];
288 bool rhs1Inverted = andInvOp.getInverted()[1];
290 unsigned rhs0Literal = getLiteral(rhs0, rhs0Inverted);
291 unsigned rhs1Literal = getLiteral(rhs1, rhs1Inverted);
294 if (rhs0Literal < rhs1Literal) {
295 std::swap(rhs0Literal, rhs1Literal);
296 std::swap(rhs0, rhs1);
297 std::swap(rhs0Inverted, rhs1Inverted);
303 unsigned delta0 = lhsLiteral - rhs0Literal;
304 unsigned delta1 = rhs0Literal - rhs1Literal;
306 LLVM_DEBUG(llvm::dbgs()
307 <<
"Writing AND gate: " << lhsLiteral <<
" = " << rhs0Literal
308 <<
" & " << rhs1Literal <<
" (deltas: " << delta0 <<
", "
310 assert(lhsLiteral >= rhs0Literal &&
"lhsLiteral >= rhs0Literal");
311 assert(rhs0Literal >= rhs1Literal &&
"rhs0Literal >= rhs1Literal");
314 encodeULEB128(delta0, os);
315 encodeULEB128(delta1, os);
319 for (
auto [lhs, rhs0, rhs1] : andGates) {
320 unsigned lhsLiteral = getLiteral(lhs);
323 auto andInvOp = lhs.first.getDefiningOp<aig::AndInverterOp>();
325 assert(andInvOp && andInvOp.getInputs().size() == 2);
328 bool rhs0Inverted = andInvOp.getInverted()[0];
329 bool rhs1Inverted = andInvOp.getInverted()[1];
331 unsigned rhs0Literal = getLiteral(rhs0, rhs0Inverted);
332 unsigned rhs1Literal = getLiteral(rhs1, rhs1Inverted);
334 os << lhsLiteral <<
" " << rhs0Literal <<
" " << rhs1Literal <<
"\n";
341LogicalResult AIGERExporter::writeSymbolTable() {
342 LLVM_DEBUG(llvm::dbgs() <<
"Writing symbol table\n");
347 for (
auto [index, elem] :
llvm::enumerate(inputs)) {
348 auto [obj, name] = elem;
352 os <<
"i" << index <<
" " << name.getValue() <<
"\n";
355 for (
auto [index, elem] :
llvm::enumerate(latches)) {
356 auto [current, currentName, next] = elem;
360 os <<
"l" << index <<
" " << currentName.getValue() <<
"\n";
363 for (
auto [index, elem] :
llvm::enumerate(outputs)) {
364 auto [obj, name] = elem;
368 os <<
"o" << index <<
" " << name.getValue() <<
"\n";
374LogicalResult AIGERExporter::writeComments() {
375 LLVM_DEBUG(llvm::dbgs() <<
"Writing comments\n");
380 os <<
"module: " <<
module.getModuleName() << "\n";
385unsigned AIGERExporter::getLiteral(
Object obj,
bool inverted) {
387 obj = valueEquivalence.getOrInsertLeaderValue(obj);
390 auto value = obj.first;
391 auto pos = obj.second;
393 auto it = valueLiteralMap.find({value, pos});
394 if (it != valueLiteralMap.end()) {
395 unsigned literal = it->second;
396 return inverted ? literal ^ 1 : literal;
401 APInt constValue = constOp.getValue();
402 if (constValue[obj.second])
404 return inverted ? 0 : 1;
406 return inverted ? 1 : 0;
410 if (
auto andInvOp = value.getDefiningOp<aig::AndInverterOp>()) {
411 if (andInvOp.getInputs().size() == 1) {
413 Value input = andInvOp.getInputs()[0];
414 bool inputInverted = andInvOp.getInverted()[0];
415 unsigned inputLiteral = getLiteral({input, pos}, inputInverted);
417 valueLiteralMap[{value, pos}] = inputLiteral;
418 return inverted ? inputLiteral ^ 1 : inputLiteral;
423 assert((!isa_and_nonnull<comb::ConcatOp, comb::ExtractOp, comb::ReplicateOp>(
424 value.getDefiningOp())) &&
425 "Unhandled operation type");
428 auto it = valueLiteralMap.find({value, pos});
429 if (it != valueLiteralMap.end()) {
430 unsigned literal = it->second;
431 return inverted ? literal ^ 1 : literal;
434 llvm::errs() <<
"Unhandled: Value not found in literal map: " << value <<
"["
438 llvm_unreachable(
"Value not found in literal map");
441LogicalResult AIGERExporter::analyzePorts(
hw::HWModuleOp hwModule) {
442 LLVM_DEBUG(llvm::dbgs() <<
"Analyzing module ports\n");
444 auto inputNames = hwModule.getInputNames();
445 auto outputNames = hwModule.getOutputNames();
448 for (
auto [index, arg] :
451 if (!arg.getType().isInteger())
456 if (!handler || handler->
valueCallback(arg, i, inputs.size()))
458 llvm::dyn_cast_or_null<StringAttr>(inputNames[index]));
461 LLVM_DEBUG(llvm::dbgs() <<
" Input " << index <<
": " << arg <<
"\n");
465 auto *outputOp = hwModule.getBodyBlock()->getTerminator();
466 for (
auto [operand, name] :
467 llvm::zip(outputOp->getOpOperands(), outputNames)) {
468 for (int64_t i = 0; i <
getBitWidth(operand.get()); ++i)
470 addOutput({operand.get(), i}, llvm::dyn_cast_or_null<StringAttr>(name));
471 LLVM_DEBUG(llvm::dbgs() <<
" Output: " << operand.get() <<
"\n");
474 LLVM_DEBUG(llvm::dbgs() <<
"Found " << getNumInputs() <<
" inputs, "
475 << getNumOutputs() <<
" outputs from ports\n");
479LogicalResult AIGERExporter::analyzeOperations(
hw::HWModuleOp hwModule) {
480 LLVM_DEBUG(llvm::dbgs() <<
"Analyzing operations\n");
483 auto result = hwModule.walk([&](Region *region) {
484 auto regionKindOp = dyn_cast<RegionKindInterface>(region->getParentOp());
486 regionKindOp.hasSSADominance(region->getRegionNumber()))
487 return WalkResult::advance();
490 for (
auto &block : *region) {
491 if (!sortTopologically(&block, [&](Value value, Operation *op) {
497 return WalkResult::interrupt();
499 return WalkResult::advance();
502 if (result.wasInterrupted())
503 return mlir::emitError(hwModule.getLoc(),
504 "failed to sort operations topologically");
507 for (Operation &op : hwModule.
getBodyBlock()->getOperations()) {
508 if (failed(visit(&op)))
512 LLVM_DEBUG(llvm::dbgs() <<
"Found " << getNumAnds() <<
" AND gates, "
513 << getNumLatches() <<
" latches\n");
517LogicalResult AIGERExporter::visit(Operation *op) {
518 return TypeSwitch<Operation *, LogicalResult>(op)
519 .Case<aig::AndInverterOp>([&](
auto op) {
return visit(op); })
520 .Case<seq::CompRegOp>([&](
auto op) {
return visit(op); })
521 .Case<comb::ConcatOp>([&](
auto op) {
return visit(op); })
522 .Case<comb::ExtractOp>([&](
auto op) {
return visit(op); })
523 .Case<comb::ReplicateOp>([&](
auto op) {
return visit(op); })
524 .Case<hw::HWModuleOp, hw::ConstantOp, hw::OutputOp>(
525 [](
auto) {
return success(); })
526 .Default([&](Operation *op) -> LogicalResult {
529 return mlir::emitError(op->getLoc(),
"unhandled operation: ") << *op;
532 for (mlir::OpOperand &operand : op->getOpOperands()) {
533 if (operand.get().getType().isInteger())
534 for (int64_t i = 0; i <
getBitWidth(operand.get()); ++i) {
536 addOutput({operand.get(), i});
540 for (mlir::OpResult result : op->getOpResults()) {
541 if (!result.getType().isInteger())
543 for (int64_t i = 0; i <
getBitWidth(result); ++i) {
545 addInput({result, i});
548 valueLiteralMap[{result, i}] = 0;
556LogicalResult AIGERExporter::visit(aig::AndInverterOp op) {
558 if (op.getInputs().size() == 1) {
561 LLVM_DEBUG(llvm::dbgs() <<
" Found inverter: " << op <<
"\n");
562 }
else if (op.getInputs().size() == 2) {
565 andGates.push_back({{op.getResult(), i},
566 {op.getInputs()[0], i},
567 {op.getInputs()[1], i}});
569 LLVM_DEBUG(llvm::dbgs() <<
" Found AND gate: " << op <<
"\n");
572 return mlir::emitError(op->getLoc(),
573 "variadic AND gates not supported, run "
574 "aig-lower-variadic pass first");
584 addLatch({op.getResult(), i}, {op.getInput(), i}, op.getNameAttr());
586 LLVM_DEBUG(llvm::dbgs() <<
" Found latch: " << op <<
"\n");
594 for (
auto operand :
llvm::reverse(op.getInputs()))
595 for (int64_t i = 0, e =
getBitWidth(operand); i < e; ++i)
596 valueEquivalence.unionSets({operand, i}, {op.getResult(), pos++});
601 for (int64_t i = 0, e =
getBitWidth(op); i < e; ++i)
602 valueEquivalence.unionSets({op.getInput(), op.getLowBit() + i},
603 {op.getResult(), i});
607LogicalResult AIGERExporter::visit(comb::ReplicateOp op) {
609 for (int64_t i = 0, e =
getBitWidth(op); i < e; ++i)
610 valueEquivalence.unionSets({op.getInput(), i % operandWidth},
611 {op.getResult(), i});
616 const AIGERExporter::Object &obj) {
617 return os << obj.first <<
"[" << obj.second <<
"]";
622 const std::pair<AIGERExporter::Object, StringAttr> &obj) {
623 return os << obj.first
624 << (obj.second ?
" (" + obj.second.getValue() +
")" :
"");
627LogicalResult AIGERExporter::assignLiterals() {
628 LLVM_DEBUG(llvm::dbgs() <<
"Assigning literals\n");
630 unsigned nextLiteral =
634 for (
auto input : inputs) {
635 valueLiteralMap[input.first] = nextLiteral;
636 LLVM_DEBUG(llvm::dbgs()
637 <<
" Input literal " << nextLiteral <<
": " << input <<
"\n");
642 for (
auto [current, currentName, next] : latches) {
643 valueLiteralMap[current] = nextLiteral;
644 LLVM_DEBUG(llvm::dbgs()
645 <<
" Latch literal " << nextLiteral <<
": " << current <<
"\n");
647 auto clocked = current.first.getDefiningOp<seq::Clocked>();
650 clock = clocked.getClk();
651 else if (clock != clocked.getClk()) {
652 auto diag = mlir::emitError(clocked.getClk().getLoc(),
653 "multiple clocks found in the module");
654 diag.attachNote(clock->getLoc()) <<
"previous clock is here";
659 if (clock && handler)
662 for (
auto [lhs, rhs0, rhs1] : andGates) {
663 valueLiteralMap[lhs] = nextLiteral;
664 LLVM_DEBUG(llvm::dbgs()
665 <<
" AND gate literal " << nextLiteral <<
": " << lhs <<
"\n");
669 LLVM_DEBUG(llvm::dbgs() <<
"Assigned " << valueLiteralMap.size()
679 llvm::raw_ostream &os,
684 options = &defaultOptions;
686 AIGERExporter exporter(module, os, *options, handler);
687 return exporter.exportModule();
692 llvm::cl::desc(
"Export AIGER in text format"),
693 llvm::cl::init(
false));
697 llvm::cl::desc(
"Exclude symbol table from the output"),
698 llvm::cl::init(
false));
701 static mlir::TranslateFromMLIRRegistration toAIGER(
702 "export-aiger",
"Export AIG to AIGER format",
703 [](mlir::ModuleOp module, llvm::raw_ostream &os) -> LogicalResult {
704 auto ops =
module.getOps<hw::HWModuleOp>();
706 return module.emitError(
"no HW module found in the input");
707 if (std::next(ops.begin()) != ops.end())
708 return module.emitError(
709 "multiple HW modules found, expected single top module");
717 [](DialectRegistry ®istry) {
718 registry.insert<synth::SynthDialect, hw::HWDialect, seq::SeqDialect,
719 comb::CombDialect>();
assert(baseType &&"element must be base type")
llvm::cl::opt< bool > includeSymbolTable("exclude-symbol-table", llvm::cl::desc("Exclude symbol table from the output"), llvm::cl::init(false))
llvm::cl::opt< bool > emitTextFormat("emit-text-format", llvm::cl::desc("Export AIGER in text format"), llvm::cl::init(false))
static Block * getBodyBlock(FModuleLike mod)
mlir::LogicalResult exportAIGER(hw::HWModuleOp module, llvm::raw_ostream &os, const ExportAIGEROptions *options=nullptr, ExportAIGERHandler *handler=nullptr)
Export an MLIR module containing AIG dialect operations to AIGER format.
void registerExportAIGERTranslation()
Register the export-aiger MLIR translation.
OS & operator<<(OS &os, const InnerSymTarget &target)
Printing InnerSymTarget's.
int64_t getBitWidth(mlir::Type type)
Return the hardware bit width of a type.
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
const char * getCirctVersion()
Handler for AIGER export.
virtual bool valueCallback(Value result, size_t bitPos, size_t inputIndex)
virtual void notifyClock(Value value)
virtual bool operandCallback(mlir::OpOperand &operand, size_t bitPos, size_t outputIndex)
virtual void notifyEmitted(Operation *op)
Options for AIGER export.
bool includeSymbolTable
Whether to include symbol table in the output.
bool binaryFormat
Whether to export in binary format (aig) or ASCII format (aag).