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