CIRCT 21.0.0git
Loading...
Searching...
No Matches
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 = builder.create<llhd::LoadOp>(
155 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 builder.create<llhd::StoreOp>(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 InstancePath empty
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 '...
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.