CIRCT  20.0.0git
DeviceDB.cpp
Go to the documentation of this file.
1 //===- DeviceDB.cpp - Implement a device database -------------------------===//
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 
12 
13 #include "mlir/IR/Builders.h"
14 #include "llvm/ADT/TypeSwitch.h"
15 
16 using namespace circt;
17 using namespace msft;
18 
19 //===----------------------------------------------------------------------===//
20 // PrimitiveDB.
21 //===----------------------------------------------------------------------===//
22 // NOTE: Nothing in this implementation is in any way the most optimal
23 // implementation. We put off deciding what the correct data structure is until
24 // we have a better handle of the operations it must accelerate. Performance is
25 // not an immediate goal.
26 //===----------------------------------------------------------------------===//
27 
28 PrimitiveDB::PrimitiveDB(MLIRContext *ctxt) : ctxt(ctxt) {}
29 
30 /// Assign an instance to a primitive. Return false if another instance is
31 /// already placed at that location.
32 LogicalResult PrimitiveDB::addPrimitive(PhysLocationAttr loc) {
33  DenseSet<PrimitiveType> &primsAtLoc = getLeaf(loc);
34  PrimitiveType prim = loc.getPrimitiveType().getValue();
35  if (primsAtLoc.contains(prim))
36  return failure();
37  primsAtLoc.insert(prim);
38  return success();
39 }
40 
41 /// Assign an instance to a primitive. Return false if another instance is
42 /// already placed at that location.
43 /// Check to see if a primitive exists.
44 bool PrimitiveDB::isValidLocation(PhysLocationAttr loc) {
45  DenseSet<PrimitiveType> primsAtLoc = getLeaf(loc);
46  return primsAtLoc.contains(loc.getPrimitiveType().getValue());
47 }
48 
49 PrimitiveDB::DimPrimitiveType &PrimitiveDB::getLeaf(PhysLocationAttr loc) {
50  return placements[loc.getX()][loc.getY()][loc.getNum()];
51 }
52 
53 void PrimitiveDB::foreach (
54  function_ref<void(PhysLocationAttr)> callback) const {
55  for (const auto &x : placements)
56  for (const auto &y : x.second)
57  for (const auto &n : y.second)
58  for (auto p : n.second)
60  x.first, y.first, n.first));
61 }
62 
63 //===----------------------------------------------------------------------===//
64 // PlacementDB.
65 //===----------------------------------------------------------------------===//
66 // NOTE: Nothing in this implementation is in any way the most optimal
67 // implementation. We put off deciding what the correct data structure is until
68 // we have a better handle of the operations it must accelerate. Performance is
69 // not an immediate goal.
70 //===----------------------------------------------------------------------===//
71 
72 PlacementDB::PlacementDB(mlir::ModuleOp topMod)
73  : ctxt(topMod->getContext()), topMod(topMod), seeded(false) {
75 }
76 PlacementDB::PlacementDB(mlir::ModuleOp topMod, const PrimitiveDB &seed)
77  : ctxt(topMod->getContext()), topMod(topMod), seeded(false) {
78 
79  seed.foreach ([this](PhysLocationAttr loc) { (void)getLeaf(loc); });
80  seeded = true;
82 }
83 
84 /// Assign an instance to a primitive. Return null if another instance is
85 /// already placed at that location
87  PhysLocationAttr loc, StringRef subPath,
88  Location srcLoc) {
89  StringAttr subPathAttr;
90  if (!subPath.empty())
91  subPathAttr = StringAttr::get(inst->getContext(), subPath);
92  PDPhysLocationOp locOp =
93  OpBuilder(inst.getBody())
94  .create<PDPhysLocationOp>(srcLoc, loc, subPathAttr,
95  FlatSymbolRefAttr());
96  if (succeeded(insertPlacement(locOp, locOp.getLoc())))
97  return locOp;
98  locOp->erase();
99  return {};
100 }
101 PDRegPhysLocationOp PlacementDB::place(DynamicInstanceOp inst,
102  LocationVectorAttr locs,
103  Location srcLoc) {
104  PDRegPhysLocationOp locOp =
105  OpBuilder(inst.getBody())
106  .create<PDRegPhysLocationOp>(srcLoc, locs, FlatSymbolRefAttr());
107  for (PhysLocationAttr loc : locs.getLocs())
108  if (failed(insertPlacement(locOp, loc))) {
109  locOp->erase();
110  return {};
111  }
112  return locOp;
113 }
114 
115 LogicalResult PlacementDB::insertPlacement(DynInstDataOpInterface op,
116  PhysLocationAttr loc) {
117  if (!loc)
118  return success();
119  PlacementCell *leaf = getLeaf(loc);
120  if (!leaf)
121  return op->emitOpError("Could not apply placement. Invalid location: ")
122  << loc;
123  if (leaf->locOp != nullptr)
124  return op->emitOpError("Could not apply placement ")
125  << loc << ". Position already occupied by "
126  << cast<DynamicInstanceOp>(leaf->locOp->getParentOp()).getPath();
127 
128  leaf->locOp = op;
129  return success();
130 }
131 
132 /// Assign an operation to a physical region. Return false on failure.
134  DeclPhysicalRegionOp physregion,
135  StringRef subPath, Location srcLoc) {
136  StringAttr subPathAttr;
137  if (!subPath.empty())
138  subPathAttr = StringAttr::get(inst->getContext(), subPath);
139  PDPhysRegionOp regOp =
140  OpBuilder::atBlockEnd(&inst.getBody().front())
141  .create<PDPhysRegionOp>(srcLoc, FlatSymbolRefAttr::get(physregion),
142  subPathAttr, FlatSymbolRefAttr());
143  regionPlacements.push_back(regOp);
144  return regOp;
145 }
146 
147 /// Using the operation attributes, add the proper placements to the database.
148 /// Return the number of placements which weren't added due to conflicts.
150  size_t numFailed = 0;
151  inst->walk([&](Operation *op) {
152  LogicalResult added = TypeSwitch<Operation *, LogicalResult>(op)
153  .Case([&](PDPhysLocationOp op) {
154  return insertPlacement(op, op.getLoc());
155  })
156  .Case([&](PDRegPhysLocationOp op) {
157  ArrayRef<PhysLocationAttr> locs =
158  op.getLocs().getLocs();
159  for (auto loc : locs)
160  if (failed(insertPlacement(op, loc)))
161  return failure();
162  return success();
163  })
164  .Case([&](PDPhysRegionOp op) {
165  regionPlacements.push_back(op);
166  return success();
167  })
168  .Default([](Operation *op) { return failure(); });
169  if (failed(added))
170  ++numFailed;
171  });
172 
173  return numFailed;
174 }
175 
176 /// Walk the entire design adding placements.
178  size_t failed = 0;
179  for (auto inst : topMod.getOps<DynamicInstanceOp>())
180  failed += addPlacements(inst);
181  return failed;
182 }
183 
184 /// Remove the placement at a given location. Returns failure if nothing was
185 /// placed there.
187  removePlacement(locOp, locOp.getLoc());
188  locOp.erase();
189 }
190 
191 /// Move the placement at a given location to a new location. Returns failure
192 /// if nothing was placed at the previous location or something is already
193 /// placed at the new location.
194 LogicalResult PlacementDB::movePlacement(PDPhysLocationOp locOp,
195  PhysLocationAttr newLoc) {
196  PhysLocationAttr from = locOp.getLoc();
197  if (failed(movePlacementCheck(locOp, from, newLoc)))
198  return failure();
199  locOp.setLocAttr(newLoc);
200  movePlacement(locOp, from, newLoc);
201  return success();
202 }
203 
204 /// Remove the placement at a given location. Returns failure if nothing was
205 /// placed there.
206 void PlacementDB::removePlacement(PDRegPhysLocationOp locOp) {
207  for (PhysLocationAttr loc : locOp.getLocs().getLocs())
208  if (loc)
209  removePlacement(locOp, loc);
210  locOp.erase();
211 }
212 
213 /// Move the placement at a given location to a new location. Returns failure
214 /// if nothing was placed at the previous location or something is already
215 /// placed at the new location.
216 LogicalResult PlacementDB::movePlacement(PDRegPhysLocationOp locOp,
217  LocationVectorAttr newLocs) {
218  ArrayRef<PhysLocationAttr> fromLocs = locOp.getLocs().getLocs();
219 
220  // Check that each move/insert/delete will succeed before doing any of the
221  // mutations.
222  for (auto [from, to] : llvm::zip(fromLocs, newLocs.getLocs())) {
223  // If 'from' and 'to' are both non-null, this location is being moved.
224  if (from && to && failed(movePlacementCheck(locOp, from, to)))
225  return failure();
226  // If only 'to' is valid, this location is the initial placement.
227  if (to && getInstanceAt(to))
228  return failure();
229  // If 'to' isn't valid, it's a placement removal which will always succeed.
230  }
231 
232  // Mutate.
233  for (auto [from, to] : llvm::zip(fromLocs, newLocs.getLocs())) {
234  // If 'from' and 'to' are both non-null, this location is being moved.
235  if (from && to)
236  movePlacement(locOp, from, to);
237  // If 'to' isn't valid, it's a placement removal.
238  else if (from)
239  removePlacement(locOp, from);
240  // If only 'to' is valid, this location is the initial placement. Since we
241  // checked that there isn't anything currently located at 'to' this call
242  // will never fail.
243  else if (to)
244  (void)insertPlacement(locOp, to);
245  }
246 
247  locOp.setLocsAttr(newLocs);
248  return success();
249 }
250 
251 void PlacementDB::removePlacement(DynInstDataOpInterface op,
252  PhysLocationAttr loc) {
253  PlacementCell *leaf = getLeaf(loc);
254  assert(leaf && "Could not find op at location specified by op");
255  assert(leaf->locOp == op);
256  leaf->locOp = {};
257 }
258 
259 LogicalResult PlacementDB::movePlacementCheck(DynInstDataOpInterface op,
260  PhysLocationAttr from,
261  PhysLocationAttr to) {
262  if (from == to)
263  return success();
264 
265  PlacementCell *oldLeaf = getLeaf(from);
266  PlacementCell *newLeaf = getLeaf(to);
267 
268  if (!oldLeaf || !newLeaf)
269  return failure();
270 
271  if (oldLeaf->locOp == nullptr)
272  return op.emitError("cannot move from a location not occupied by "
273  "specified op. Currently unoccupied");
274  if (oldLeaf->locOp != op)
275  return op.emitError("cannot move from a location not occupied by "
276  "specified op. Currently occupied by ")
277  << oldLeaf->locOp;
278  if (newLeaf->locOp)
279  return op.emitError(
280  "cannot move to new location since location is occupied by ")
281  << cast<DynamicInstanceOp>(newLeaf->locOp->getParentOp()).getPath();
282  return success();
283 }
284 
285 void PlacementDB::movePlacement(DynInstDataOpInterface op,
286  PhysLocationAttr from, PhysLocationAttr to) {
287  assert(succeeded(movePlacementCheck(op, from, to)) &&
288  "Call `movePlacementCheck` first to ensure that move is legal.");
289  if (from == to)
290  return;
291  PlacementCell *oldLeaf = getLeaf(from);
292  PlacementCell *newLeaf = getLeaf(to);
293  newLeaf->locOp = op;
294  oldLeaf->locOp = {};
295 }
296 
297 /// Lookup the instance at a particular location.
298 DynInstDataOpInterface PlacementDB::getInstanceAt(PhysLocationAttr loc) {
299  auto innerMap = placements[loc.getX()][loc.getY()][loc.getNum()];
300  auto instF = innerMap.find(loc.getPrimitiveType().getValue());
301  if (instF == innerMap.end())
302  return {};
303  if (!instF->getSecond().locOp)
304  return {};
305  return instF->getSecond().locOp;
306 }
307 
308 PhysLocationAttr PlacementDB::getNearestFreeInColumn(PrimitiveType prim,
309  uint64_t columnNum,
310  uint64_t nearestToY) {
311  // Simplest possible algorithm.
312  PhysLocationAttr nearest = {};
314  [&nearest, nearestToY](PhysLocationAttr loc, Operation *locOp) {
315  if (locOp)
316  return;
317  if (!nearest) {
318  nearest = loc;
319  return;
320  }
321  int64_t curDist =
322  std::abs((int64_t)nearestToY - (int64_t)nearest.getY());
323  int64_t replDist = std::abs((int64_t)nearestToY - (int64_t)loc.getY());
324  if (replDist < curDist)
325  nearest = loc;
326  },
327  std::make_tuple(columnNum, columnNum, -1, -1), prim);
328  return nearest;
329 }
330 
332  PrimitiveType primType = loc.getPrimitiveType().getValue();
333 
334  DimNumMap &nums = placements[loc.getX()][loc.getY()];
335  if (!seeded)
336  return &nums[loc.getNum()][primType];
337  if (!nums.count(loc.getNum()))
338  return {};
339 
340  DimDevType &primitives = nums[loc.getNum()];
341  if (primitives.count(primType) == 0)
342  return {};
343  return &primitives[primType];
344 }
345 
346 /// Walker for placements.
348  function_ref<void(PhysLocationAttr, DynInstDataOpInterface)> callback,
349  std::tuple<int64_t, int64_t, int64_t, int64_t> bounds,
350  std::optional<PrimitiveType> primType, std::optional<WalkOrder> walkOrder) {
351  uint64_t xmin = std::get<0>(bounds) < 0 ? 0 : std::get<0>(bounds);
352  uint64_t xmax = std::get<1>(bounds) < 0 ? std::numeric_limits<uint64_t>::max()
353  : (uint64_t)std::get<1>(bounds);
354  uint64_t ymin = std::get<2>(bounds) < 0 ? 0 : std::get<2>(bounds);
355  uint64_t ymax = std::get<3>(bounds) < 0 ? std::numeric_limits<uint64_t>::max()
356  : (uint64_t)std::get<3>(bounds);
357 
358  // TODO: Since the data structures we're using aren't sorted, the best we can
359  // do is iterate and filter. If a specific order is requested, we sort the
360  // keys by that as we go. Once we get to performance, we'll figure out the
361  // right data structure.
362 
363  auto maybeSort = [](auto &container, auto direction) {
364  if (!direction.has_value())
365  return;
366  if (*direction == Direction::NONE)
367  return;
368 
369  llvm::sort(container, [direction](auto colA, auto colB) {
370  if (*direction == Direction::ASC)
371  return colA.first < colB.first;
372 
373  return colA.first > colB.first;
374  });
375  };
376 
377  // X loop.
378  SmallVector<std::pair<size_t, DimYMap>> cols(placements.begin(),
379  placements.end());
380  maybeSort(cols, llvm::transformOptional(walkOrder,
381  [](auto wo) { return wo.columns; }));
382  for (const auto &colF : cols) {
383  size_t x = colF.first;
384  if (x < xmin || x > xmax)
385  continue;
386  DimYMap yMap = colF.second;
387 
388  // Y loop.
389  SmallVector<std::pair<size_t, DimNumMap>> rows(yMap.begin(), yMap.end());
390  maybeSort(rows, llvm::transformOptional(walkOrder,
391  [](auto wo) { return wo.rows; }));
392  for (const auto &rowF : rows) {
393  size_t y = rowF.first;
394  if (y < ymin || y > ymax)
395  continue;
396  DimNumMap numMap = rowF.second;
397 
398  // Num loop.
399  for (auto &numF : numMap) {
400  size_t num = numF.getFirst();
401  DimDevType devMap = numF.getSecond();
402 
403  // DevType loop.
404  for (auto &devF : devMap) {
405  PrimitiveType devtype = devF.getFirst();
406  if (primType && devtype != *primType)
407  continue;
408  PlacementCell &inst = devF.getSecond();
409 
410  // Marshall and run the callback.
411  PhysLocationAttr loc = PhysLocationAttr::get(
412  ctxt, PrimitiveTypeAttr::get(ctxt, devtype), x, y, num);
413  callback(loc, inst.locOp);
414  }
415  }
416  }
417  }
418 }
419 
420 /// Walk the region placement information.
422  function_ref<void(PDPhysRegionOp)> callback) {
423  for (auto regOp : regionPlacements)
424  callback(regOp);
425 }
assert(baseType &&"element must be base type")
@ ASC
Definition: MSFT.h:87
@ NONE
Definition: MSFT.h:87
PlacementDB(MlirModule top, PrimitiveDB *seed)
Definition: MSFTModule.cpp:51
bool isValidLocation(MlirAttribute loc)
Definition: MSFTModule.cpp:42
bool addPrimitive(MlirAttribute locAndPrim)
Definition: MSFTModule.cpp:38
LogicalResult movePlacementCheck(DynInstDataOpInterface op, PhysLocationAttr from, PhysLocationAttr to)
Check to make sure the move is going to succeed.
Definition: DeviceDB.cpp:259
void removePlacement(PDPhysLocationOp)
Remove the placement from the DB and IR. Erases the op.
DynInstDataOpInterface getInstanceAt(PhysLocationAttr)
Lookup the instance at a particular location.
size_t addPlacements(DynamicInstanceOp inst)
Load the placements from inst.
Definition: DeviceDB.cpp:149
LogicalResult movePlacement(PDPhysLocationOp, PhysLocationAttr)
Move a placement location to a new location.
DenseMap< size_t, DimNumMap > DimYMap
Definition: DeviceDB.h:134
PDPhysLocationOp place(DynamicInstanceOp inst, PhysLocationAttr, StringRef subpath, Location srcLoc)
Assign an instance to a primitive.
size_t addDesignPlacements()
Load the database from the IR.
Definition: DeviceDB.cpp:177
PlacementCell * getLeaf(PhysLocationAttr)
Get the leaf node.
Definition: DeviceDB.cpp:331
DenseMap< PrimitiveType, PlacementCell > DimDevType
Definition: DeviceDB.h:132
PlacementDB(mlir::ModuleOp topMod)
Create a placement db containing all the placements in 'topMod'.
Definition: DeviceDB.cpp:72
void walkRegionPlacements(function_ref< void(PDPhysRegionOp)>)
Walk the region placement information.
Definition: DeviceDB.cpp:421
MLIRContext * ctxt
Definition: DeviceDB.h:129
PhysLocationAttr getNearestFreeInColumn(PrimitiveType prim, uint64_t column, uint64_t nearestToY)
Find the nearest unoccupied primitive location to 'nearestToY' in 'column'.
PDPhysRegionOp placeIn(DynamicInstanceOp inst, DeclPhysicalRegionOp, StringRef subPath, Location srcLoc)
Assign an operation to a physical region. Return false on failure.
Definition: DeviceDB.cpp:133
mlir::ModuleOp topMod
Definition: DeviceDB.h:130
void walkPlacements(function_ref< void(PhysLocationAttr, DynInstDataOpInterface)>, std::tuple< int64_t, int64_t, int64_t, int64_t > bounds=std::make_tuple(-1, -1, -1, -1), std::optional< PrimitiveType > primType={}, std::optional< WalkOrder >={})
Walk the placement information in some sort of reasonable order.
DenseMap< size_t, DimDevType > DimNumMap
Definition: DeviceDB.h:133
LogicalResult insertPlacement(DynInstDataOpInterface op, PhysLocationAttr)
Definition: DeviceDB.cpp:115
RegionPlacements regionPlacements
Definition: DeviceDB.h:143
A data structure to contain locations of the primitives on the device.
Definition: DeviceDB.h:27
void foreach(function_ref< void(PhysLocationAttr)> callback) const
Iterate over all the primitive locations, executing 'callback' on each one.
Definition: DeviceDB.cpp:53
DenseSet< PrimitiveType > DimPrimitiveType
Definition: DeviceDB.h:42
PrimitiveDB(MLIRContext *)
Create a DB treating 'top' as the root module.
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:55
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21
Definition: msft.py:1
DynInstDataOpInterface locOp
Definition: DeviceDB.h:126