Loading [MathJax]/extensions/tex2jax.js
CIRCT 22.0.0git
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
MemoryToBlockArgumentPass.cpp
Go to the documentation of this file.
1//===- VarToBlockArgumentPass.cpp - Implement Var to Block Argument Pass --===//
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// Implement pass to promote memory to block arguments.
10//
11//===----------------------------------------------------------------------===//
12
15#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
16#include "mlir/Dialect/Func/IR/FuncOps.h"
17#include "mlir/IR/Dominance.h"
18#include "mlir/Pass/Pass.h"
19#include <set>
20
21namespace circt {
22namespace llhd {
23#define GEN_PASS_DEF_MEMORYTOBLOCKARGUMENT
24#include "circt/Dialect/LLHD/Transforms/LLHDPasses.h.inc"
25} // namespace llhd
26} // namespace circt
27
28using namespace circt;
29namespace {
30
31struct MemoryToBlockArgumentPass
32 : public circt::llhd::impl::MemoryToBlockArgumentBase<
33 MemoryToBlockArgumentPass> {
34 void runOnOperation() override;
35 void runOnProcess(llhd::ProcessOp operation);
36};
37
38} // anonymous namespace
39
40/// Add the dominance fontier blocks of 'frontierOf' to the 'df' set
41static void getDominanceFrontier(Block *frontierOf, Operation *op,
42 std::set<Block *> &df) {
43 mlir::DominanceInfo dom(op);
44 for (Block &block : op->getRegion(0).getBlocks()) {
45 for (Block *pred : block.getPredecessors()) {
46 if (dom.dominates(frontierOf, pred) &&
47 !dom.properlyDominates(frontierOf, &block) &&
48 block.getOps<llhd::VarOp>().empty()) {
49 df.insert(&block);
50 }
51 }
52 }
53}
54
55/// Add the blocks in the closure of the dominance fontier relation of all the
56/// block in 'initialSet' to 'closure'
57static void getDFClosure(SmallVectorImpl<Block *> &initialSet, Operation *op,
58 std::set<Block *> &closure) {
59 unsigned numElements;
60 for (Block *block : initialSet) {
61 getDominanceFrontier(block, op, closure);
62 }
63 do {
64 numElements = closure.size();
65 for (Block *block : closure) {
66 getDominanceFrontier(block, op, closure);
67 }
68 } while (numElements < closure.size());
69}
70
71/// Add a block argument to a given terminator. Only 'std.br', 'std.cond_br' and
72/// 'llhd.wait' are supported. The successor block has to be provided for the
73/// 'std.cond_br' terminator which has two possible successors.
74static void addBlockOperandToTerminator(Operation *terminator,
75 Block *successsor, Value toAppend) {
76 if (auto wait = dyn_cast<llhd::WaitOp>(terminator)) {
77 wait.getDestOperandsMutable().append(toAppend);
78 } else if (auto br = dyn_cast<mlir::cf::BranchOp>(terminator)) {
79 br.getDestOperandsMutable().append(toAppend);
80 } else if (auto condBr = dyn_cast<mlir::cf::CondBranchOp>(terminator)) {
81 if (condBr.getFalseDest() == successsor) {
82 condBr.getFalseDestOperandsMutable().append(toAppend);
83 } else {
84 condBr.getTrueDestOperandsMutable().append(toAppend);
85 }
86 } else {
87 llvm_unreachable("unsupported terminator op");
88 }
89}
90
91void MemoryToBlockArgumentPass::runOnOperation() {
92 for (auto proc : getOperation().getOps<llhd::ProcessOp>())
93 runOnProcess(proc);
94}
95
96void MemoryToBlockArgumentPass::runOnProcess(llhd::ProcessOp operation) {
97 OpBuilder builder(operation);
98
99 // No operations that have their own region and are not isolated from above
100 // are allowed for now.
101 WalkResult result = operation.getBody().walk([](Operation *op) -> WalkResult {
102 if (op->getNumRegions() > 0 &&
103 !op->hasTrait<OpTrait::IsIsolatedFromAbove>())
104 return WalkResult::interrupt();
105 return WalkResult::advance();
106 });
107 if (result.wasInterrupted())
108 return;
109
110 // Get all variables defined in the body of this operation
111 // Note that variables that are passed as a function argument are not
112 // considered.
113 SmallVector<Value, 16> vars(operation->getRegion(0).getOps<llhd::VarOp>());
114
115 // Don't consider variables that are used in other operations than load and
116 // store (e.g. as an argument to a call)
117 for (auto *var = vars.begin(); var != vars.end(); ++var) {
118 for (Operation *user : var->getUsers()) {
119 if (!isa<llhd::LoadOp>(user) && !isa<llhd::StoreOp>(user)) {
120 vars.erase(var--);
121 break;
122 }
123 }
124 }
125
126 // For each variable find the blocks where a value is stored to it
127 for (Value var : vars) {
128 SmallVector<Block *, 16> defBlocks;
129 defBlocks.push_back(
130 var.getDefiningOp<llhd::VarOp>().getOperation()->getBlock());
131 operation->walk([&](llhd::StoreOp op) {
132 if (op.getPointer() == var)
133 defBlocks.push_back(op.getOperation()->getBlock());
134 });
135 // Remove duplicates from the list
136 std::sort(defBlocks.begin(), defBlocks.end());
137 defBlocks.erase(std::unique(defBlocks.begin(), defBlocks.end()),
138 defBlocks.end());
139
140 // Calculate initial set of join points
141 std::set<Block *> joinPoints;
142 getDFClosure(defBlocks, operation, joinPoints);
143
144 for (Block *jp : joinPoints) {
145 // Add a block argument for the variable at each join point
146 BlockArgument phi = jp->addArgument(
147 cast<llhd::PtrType>(var.getType()).getElementType(), var.getLoc());
148
149 // Add a load at the end of every predecessor and pass the loaded value as
150 // the block argument
151 for (Block *pred : jp->getPredecessors()) {
152 // Set insertion point before terminator to insert the load operation
153 builder.setInsertionPoint(pred->getTerminator());
154 Value load = llhd::LoadOp::create(
155 builder, pred->getTerminator()->getLoc(),
156 cast<llhd::PtrType>(var.getType()).getElementType(), var);
157 // Add the loaded value as additional block argument
158 addBlockOperandToTerminator(pred->getTerminator(), jp, load);
159 }
160 // Insert a store at the beginning of the join point to make removal of
161 // all the memory operations easier later on
162 builder.setInsertionPointToStart(jp);
163 llhd::StoreOp::create(builder, jp->front().getLoc(), var, phi);
164 }
165
166 // Basically reaching definitions analysis and replacing the loaded values
167 // by the values stored
168 DenseMap<Block *, Value> outputMap;
169 SmallPtrSet<Block *, 32> workQueue;
170 SmallPtrSet<Block *, 32> workDone;
171
172 workQueue.insert(&operation->getRegion(0).front());
173
174 while (!workQueue.empty()) {
175 // Pop block to process at the front
176 Block *block = *workQueue.begin();
177 workQueue.erase(block);
178
179 // Remember the currently stored value
180 Value currStoredValue;
181
182 // Update the value stored for the current variable at the start of this
183 // block
184 for (Block *pred : block->getPredecessors()) {
185 // Get the value at the end of a predecessor block and set it to the
186 // currently stored value at the start of this block
187 // NOTE: because we added block arguments and a store at the beginning
188 // of each join point we can assume that all predecessors have the same
189 // value stored at their end here because if that is not the case the
190 // first instruction in this block is a store instruction and will
191 // update the currently stored value to a correct one
192 if (!currStoredValue && outputMap.count(pred)) {
193 currStoredValue = outputMap[pred];
194 break;
195 }
196 }
197
198 // Iterate through all operations of the current block
199 for (auto op = block->begin(); op != block->end(); ++op) {
200 // Update currStoredValue at every store operation that stores to the
201 // variable we are currently considering
202 if (auto store = dyn_cast<llhd::StoreOp>(op)) {
203 if (store.getPointer() == var) {
204 currStoredValue = store.getValue();
205 op = std::prev(op);
206 store.getOperation()->dropAllReferences();
207 store.erase();
208 }
209 // Set currStoredValue to the initializer value of the variable
210 // operation that created the variable we are currently considering,
211 // note that before that currStoredValue is uninitialized
212 } else if (auto varOp = dyn_cast<llhd::VarOp>(op)) {
213 if (varOp.getResult() == var)
214 currStoredValue = varOp.getInit();
215 // Replace the value returned by a load from the variable we are
216 // currently considering with the currStoredValue and delete the load
217 // operation
218 } else if (auto load = dyn_cast<llhd::LoadOp>(op)) {
219 if (load.getPointer() == var && currStoredValue) {
220 op = std::prev(op);
221 load.getResult().replaceAllUsesWith(currStoredValue);
222 load.getOperation()->dropAllReferences();
223 load.erase();
224 }
225 }
226 }
227
228 if (currStoredValue)
229 outputMap.insert(std::make_pair(block, currStoredValue));
230
231 workDone.insert(block);
232
233 // Add all successors of this block to the work queue if they are not
234 // already processed
235 for (Block *succ : block->getSuccessors()) {
236 if (!workDone.count(succ))
237 workQueue.insert(succ);
238 }
239 }
240 }
241
242 // Remove all variable declarations for which we already removed all loads and
243 // stores
244 for (Value var : vars) {
245 Operation *op = var.getDefiningOp();
246 op->dropAllDefinedValueUses();
247 op->dropAllReferences();
248 op->erase();
249 }
250}
MlirType uint64_t numElements
Definition CHIRRTL.cpp:30
static void addBlockOperandToTerminator(Operation *terminator, Block *successsor, Value toAppend)
Add a block argument to a given terminator.
static void getDominanceFrontier(Block *frontierOf, Operation *op, std::set< Block * > &df)
Add the dominance fontier blocks of 'frontierOf' to the 'df' set.
static void getDFClosure(SmallVectorImpl< Block * > &initialSet, Operation *op, std::set< Block * > &closure)
Add the blocks in the closure of the dominance fontier relation of all the block in 'initialSet' to '...
static InstancePath empty
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.