CIRCT  18.0.0git
HWReductions.cpp
Go to the documentation of this file.
1 //===- HWReductions.cpp - Reduction patterns for the HW dialect -----------===//
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 
11 #include "circt/Dialect/HW/HWOps.h"
13 #include "llvm/ADT/SmallSet.h"
14 #include "llvm/Support/Debug.h"
15 
16 #define DEBUG_TYPE "hw-reductions"
17 
18 using namespace mlir;
19 using namespace circt;
20 using namespace hw;
21 
22 //===----------------------------------------------------------------------===//
23 // Utilities
24 //===----------------------------------------------------------------------===//
25 
26 /// Utility to track the transitive size of modules.
27 struct ModuleSizeCache {
28  void clear() { moduleSizes.clear(); }
29 
30  uint64_t getModuleSize(HWModuleLike module,
31  hw::InstanceGraph &instanceGraph) {
32  if (auto it = moduleSizes.find(module); it != moduleSizes.end())
33  return it->second;
34  uint64_t size = 1;
35  module->walk([&](Operation *op) {
36  size += 1;
37  if (auto instOp = dyn_cast<HWInstanceLike>(op))
38  if (auto instModule =
39  instanceGraph.getReferencedModule<hw::HWModuleLike>(instOp))
40  size += getModuleSize(instModule, instanceGraph);
41  });
42  moduleSizes.insert({module, size});
43  return size;
44  }
45 
46 private:
47  llvm::DenseMap<Operation *, uint64_t> moduleSizes;
48 };
49 
50 //===----------------------------------------------------------------------===//
51 // Reduction patterns
52 //===----------------------------------------------------------------------===//
53 
54 /// A sample reduction pattern that maps `hw.module` to `hw.module.extern`.
55 struct ModuleExternalizer : public OpReduction<HWModuleOp> {
56  void beforeReduction(mlir::ModuleOp op) override {
57  instanceGraph = std::make_unique<InstanceGraph>(op);
58  moduleSizes.clear();
59  }
60 
61  uint64_t match(HWModuleOp op) override {
62  return moduleSizes.getModuleSize(op, *instanceGraph);
63  }
64 
65  LogicalResult rewrite(HWModuleOp op) override {
66  OpBuilder builder(op);
67  builder.create<HWModuleExternOp>(op->getLoc(), op.getModuleNameAttr(),
68  op.getPortList(), StringRef(),
69  op.getParameters());
70  op->erase();
71  return success();
72  }
73 
74  std::string getName() const override { return "hw-module-externalizer"; }
75 
76  std::unique_ptr<InstanceGraph> instanceGraph;
78 };
79 
80 /// A sample reduction pattern that replaces all uses of an operation with one
81 /// of its operands. This can help pruning large parts of the expression tree
82 /// rapidly.
83 template <unsigned OpNum>
84 struct HWOperandForwarder : public Reduction {
85  uint64_t match(Operation *op) override {
86  if (op->getNumResults() != 1 || op->getNumOperands() < 2 ||
87  OpNum >= op->getNumOperands())
88  return 0;
89  auto resultTy = op->getResult(0).getType().dyn_cast<IntegerType>();
90  auto opTy = op->getOperand(OpNum).getType().dyn_cast<IntegerType>();
91  return resultTy && opTy && resultTy == opTy &&
92  op->getResult(0) != op->getOperand(OpNum);
93  }
94  LogicalResult rewrite(Operation *op) override {
95  assert(match(op));
96  ImplicitLocOpBuilder builder(op->getLoc(), op);
97  auto result = op->getResult(0);
98  auto operand = op->getOperand(OpNum);
99  LLVM_DEBUG(llvm::dbgs()
100  << "Forwarding " << operand << " in " << *op << "\n");
101  result.replaceAllUsesWith(operand);
102  reduce::pruneUnusedOps(op, *this);
103  return success();
104  }
105  std::string getName() const override {
106  return ("hw-operand" + Twine(OpNum) + "-forwarder").str();
107  }
108 };
109 
110 /// A sample reduction pattern that replaces integer operations with a constant
111 /// zero of their type.
112 struct HWConstantifier : public Reduction {
113  uint64_t match(Operation *op) override {
114  if (op->getNumResults() == 0 || op->getNumOperands() == 0)
115  return 0;
116  return llvm::all_of(op->getResults(), [](Value result) {
117  return result.getType().isa<IntegerType>();
118  });
119  }
120  LogicalResult rewrite(Operation *op) override {
121  assert(match(op));
122  OpBuilder builder(op);
123  for (auto result : op->getResults()) {
124  auto type = result.getType().cast<IntegerType>();
125  auto newOp = builder.create<hw::ConstantOp>(op->getLoc(), type, 0);
126  result.replaceAllUsesWith(newOp);
127  }
128  reduce::pruneUnusedOps(op, *this);
129  return success();
130  }
131  std::string getName() const override { return "hw-constantifier"; }
132 };
133 
134 //===----------------------------------------------------------------------===//
135 // Reduction Registration
136 //===----------------------------------------------------------------------===//
137 
138 void HWReducePatternDialectInterface::populateReducePatterns(
140  // Gather a list of reduction patterns that we should try. Ideally these are
141  // assigned reasonable benefit indicators (higher benefit patterns are
142  // prioritized). For example, things that can knock out entire modules while
143  // being cheap should be tried first (and thus have higher benefit), before
144  // trying to tweak operands of individual arithmetic ops.
145  patterns.add<ModuleExternalizer, 6>();
146  patterns.add<HWConstantifier, 5>();
150 }
151 
153  mlir::DialectRegistry &registry) {
154  registry.addExtension(+[](MLIRContext *ctx, HWDialect *dialect) {
155  dialect->addInterfaces<HWReducePatternDialectInterface>();
156  });
157 }
assert(baseType &&"element must be base type")
Builder builder
void registerReducePatternDialectInterface(mlir::DialectRegistry &registry)
Register the Arc Reduction pattern dialect interface to the given registry.
std::map< std::string, std::set< std::string > > InstanceGraph
Iterates over the handshake::FuncOp's in the program to build an instance graph.
void pruneUnusedOps(Operation *initialOp, Reduction &reduction)
Starting at the given op, traverse through it and its operands and erase operations that have no more...
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
Definition: hw.py:1
mlir::raw_indented_ostream & dbgs()
Definition: Utility.h:28
A sample reduction pattern that replaces integer operations with a constant zero of their type.
uint64_t match(Operation *op) override
Check if the reduction can apply to a specific operation.
std::string getName() const override
Return a human-readable name for this reduction pattern.
LogicalResult rewrite(Operation *op) override
Apply the reduction to a specific operation.
A sample reduction pattern that replaces all uses of an operation with one of its operands.
LogicalResult rewrite(Operation *op) override
Apply the reduction to a specific operation.
uint64_t match(Operation *op) override
Check if the reduction can apply to a specific operation.
std::string getName() const override
Return a human-readable name for this reduction pattern.
A sample reduction pattern that maps hw.module to hw.module.extern.
std::string getName() const override
Return a human-readable name for this reduction pattern.
LogicalResult rewrite(HWModuleOp op) override
std::unique_ptr< InstanceGraph > instanceGraph
void beforeReduction(mlir::ModuleOp op) override
Called before the reduction is applied to a new subset of operations.
uint64_t match(HWModuleOp op) override
ModuleSizeCache moduleSizes
Utility to track the transitive size of modules.
uint64_t getModuleSize(HWModuleLike module, hw::InstanceGraph &instanceGraph)
An abstract reduction pattern.
Definition: Reduction.h:24
A dialect interface to provide reduction patterns to a reducer tool.
Definition: HWReductions.h:18