123 llvm::DenseMap<mlir::Operation *, unsigned> keys,
124 llvm::SmallVector<llvm::DenseMap<TileID, unsigned>> neighbours) {
129 virtual mlir::LogicalResult
place(DeviceOp device) = 0;
133 std::optional<TileID>
getPlacement(mlir::Operation *logicalTile)
const {
134 auto it =
result.find(logicalTile);
150 llvm::SmallVector<std::pair<TileLike, TileLike>, 4>
edges;
151 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<unsigned, 2>>
154 void addEdge(TileLike first, TileLike second);
176 llvm::DenseMap<mlir::Operation *, unsigned>
rank;
189 static llvm::MapVector<mlir::Operation *, std::pair<int, int>>
191 llvm::ArrayRef<FlowOp> flows, llvm::ArrayRef<PacketFlowOp> pktFlows,
192 llvm::ArrayRef<RouteOp> routes,
193 llvm::ArrayRef<DMAChannelAnalysis::ChannelClaim> claims,
194 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<std::pair<int, int>>>
196 llvm::DenseMap<mlir::Operation *, mlir::Operation *> *keys =
nullptr);
223 llvm::ArrayRef<PacketFlowOp> pktFlows);
227 llvm::SmallVector<mlir::StringAttr>
ends;
228 llvm::SmallVector<std::pair<int, llvm::SmallVector<mlir::StringAttr>>>
235 llvm::MapVector<mlir::Operation *, std::array<ShimSide, 2>>;
239 DeviceOp device, llvm::ArrayRef<ObjectFifoCreateOp> objectFifos,
240 const llvm::DenseMap<mlir::Operation *, unsigned> &rank,
241 const llvm::DenseMap<mlir::Operation *, mlir::Operation *> &routeKeys =
247 llvm::ArrayRef<const ShimSide *> sides,
248 llvm::ArrayRef<mlir::StringAttr> extra,
249 llvm::ArrayRef<int> pinnedHere);
273 : targetModel(&targetModel), packetSwitched(packetSwitched) {}
276 static std::optional<End>
endOf(ObjectFifoCreateOp fifo,
277 std::optional<unsigned> consumer);
280 std::optional<std::string>
whyApart(End a, End b)
const;
285 unsigned share(End end,
286 const llvm::DenseMap<mlir::Operation *, unsigned> &rank);
288 bool failed()
const {
return diagnosed; }
298 bool diagnosed =
false;
299 llvm::DenseMap<std::tuple<mlir::Operation *, int, int>,
300 std::pair<llvm::SmallVector<End, 2>,
unsigned>>
321 std::optional<std::pair<int, int>>
322 heldAt(
TileID at, llvm::ArrayRef<PinnedChannels::End> ends)
const;
324 std::optional<PinnedChannels::End>
327 llvm::DenseMap<int, llvm::SmallVector<PinnedChannels::End, 2>>
334 std::optional<DMAChannelAnalysis::ChannelClaim>
341 std::map<std::tuple<int, int, int, int>,
342 llvm::SmallVector<PinnedChannels::End, 2>>
344 std::map<std::tuple<int, int, int, int>,
345 llvm::SmallVector<DMAChannelAnalysis::ChannelClaim, 1>>
355 static llvm::DenseMap<mlir::StringAttr,
356 llvm::SmallVector<ShimTransferSpans::Gate>>
379 bool uses(mlir::Operation *logicalTile)
const {
380 return peaks.contains(logicalTile);
382 const llvm::DenseMap<mlir::Operation *, Peak> &
users()
const {
388 int shortfall(llvm::ArrayRef<mlir::Operation *> onTile,
TileID tile)
const;
392 mlir::Operation *owner;
394 llvm::SmallVector<std::optional<uint32_t>> bdIds;
395 uint32_t headAlignment;
401 llvm::SmallVector<uint32_t> pinned;
404 llvm::SmallVector<Task> tasks;
406 llvm::SmallVector<llvm::SmallVector<std::pair<unsigned, bool>>> sequences;
407 llvm::DenseMap<mlir::Operation *, StaticBds> statics;
408 llvm::DenseMap<mlir::Operation *, Peak> peaks;
409 llvm::DenseMap<TileID, mlir::Operation *> placed;
415 llvm::SmallVector<unsigned> tasks;
416 llvm::SmallVector<llvm::SmallVector<unsigned>> events;
418 llvm::SmallVector<Shim> shims;
419 llvm::DenseMap<mlir::Operation *, unsigned> indexOf;
422 mutable llvm::DenseMap<llvm::SmallBitVector, int> shortfallOf;
429 llvm::DenseMap<mlir::Operation *,
430 llvm::SmallVector<DMAChannelAnalysis::ChannelClaim>>
444 llvm::SmallVector<mlir::Operation *>
tiles;
450 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<unsigned>>
ddrGroupsOf;
456 ddrSpread(llvm::function_ref<std::optional<int>(mlir::Operation *)> columnOf,
461 llvm::function_ref<std::optional<int>(mlir::Operation *)> columnOf,
467 llvm::ArrayRef<ObjectFifoCreateOp> objectFifos,
468 llvm::ArrayRef<DMAChannelAnalysis::ChannelClaim> claims,
469 const llvm::DenseMap<mlir::Operation *, unsigned> &rank,
470 const llvm::DenseMap<mlir::Operation *, mlir::Operation *>
493 llvm::ArrayRef<PinnedChannels::End> extra,
494 llvm::ArrayRef<mlir::Operation *> tilesHere,
507 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<mlir::Operation *>>
519 llvm::SmallVector<mlir::Operation *, 2>
dsts;
524 mlir::Operation *
link =
nullptr;
528 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<unsigned>>
streamNetsOf;
533 llvm::function_ref<std::optional<TileID>(mlir::Operation *)> at,
534 TileID &src, llvm::SmallVectorImpl<TileID> &dsts)
const;
537 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<std::pair<int, int>>>
542 std::optional<std::pair<mlir::Operation *, std::pair<int, int>>>
544 llvm::ArrayRef<mlir::Operation *> others)
const;
549 std::pair<mlir::Operation *, std::pair<int, int>> clash)
const;
551 llvm::DenseMap<mlir::Operation *, unsigned>
coreKeys;
648 bool mergeLogicalTiles =
true,
649 bool spreadUnanchoredTiles =
false)
650 : coresPerCol(coresPerCol), mergeLogicalTiles(mergeLogicalTiles),
651 spreadUnanchoredTiles(spreadUnanchoredTiles) {}
656 mlir::LogicalResult
place(DeviceOp device)
override;
658 llvm::StringRef
getName()
const override {
return "sequential_placer"; }
661 std::optional<int> coresPerCol;
662 bool mergeLogicalTiles;
665 bool spreadUnanchoredTiles;
669 llvm::DenseSet<TileID> assignedNonCoreTiles;
670 int deviceCoresPerCol = 0;
672 int placeableCores = 0;
674 llvm::DenseMap<TileID, llvm::SmallVector<mlir::Operation *>> shimTilesAt;
676 llvm::DenseMap<TileID, llvm::SmallVector<mlir::Operation *>> overlayTilesAt;
677 bool fitsSharingShim(
TileID tile, mlir::Operation *logicalTile,
678 std::pair<int, int> required);
679 void recordShimEnds(
TileID tile, mlir::Operation *logicalTile);
684 DeviceOp device, llvm::ArrayRef<ObjectFifoCreateOp> objectFifos,
685 llvm::DenseMap<mlir::Operation *, std::pair<int, int>> &requirements);
688 enum class DmaDir { In, Out };
692 enum class PlacementOrigin { Pinned, Selected };
696 void limitCoresPerColumn(
int maxCoresPerCol,
int numColumns,
697 const llvm::DenseSet<TileID> &held);
703 std::optional<TileID>
704 findTileWithCapacity(std::optional<int> targetCol,
705 llvm::ArrayRef<TileID> tiles,
int requiredInputChannels,
706 int requiredOutputChannels, AIETileType requestedType,
707 mlir::Operation *logicalTile,
bool withinBudgets,
708 bool apartByName =
true);
719 struct CapacityDiagnosis {
720 bool capacityExistsSomewhere =
false;
722 int inUsed = 0, inMax = 0, outUsed = 0, outMax = 0;
724 int closestShortIn = 0, closestShortOut = 0;
727 int overlayOut = 0, overlayUnfit = 0;
731 std::optional<std::tuple<TileID, PinnedChannels::End, PinnedChannels::End>>
736 CapacityDiagnosis diagnoseCapacityExhaustion(AIETileType requestedType,
737 int requiredInputChannels,
738 int requiredOutputChannels,
739 mlir::Operation *joining);
741 void updateChannelUsage(
TileID tile, DmaDir direction,
int numChannels);
744 llvm::DenseMap<int, StreamDemand> columnStreamsUsed;
745 llvm::DenseMap<int, llvm::DenseSet<mlir::Operation *>> columnIncomingFifos;
746 void recordColumnStreamUsage(mlir::Operation *tile,
int col);
747 llvm::DenseMap<TileID, int> broadcastFanoutUsed;
750 StreamCuts placedCuts;
751 llvm::BitVector cutNets;
754 bool raisesStreamCuts(mlir::Operation *logicalTile,
TileID tile)
const;
756 void addPlacedStreams(mlir::Operation *logicalTile);
761 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<PinnedChannels::End>>
766 bool fitsStreamAndBdBudgets(mlir::Operation *logicalTile,
TileID tile)
const;
769 void recordStreamAndBdUsage(mlir::Operation *logicalTile,
TileID tile);
773 bool hasAvailableChannels(
TileID tile,
int inputChannels,
int outputChannels,
774 mlir::Operation *joining =
nullptr);
779 void notePinClash(mlir::InFlightDiagnostic &diag, LogicalTileOp logicalTile,
782 mlir::LogicalResult validateAndUpdateChannelUsage(
783 LogicalTileOp logicalTile,
TileID tile,
784 const llvm::DenseMap<mlir::Operation *, std::pair<int, int>>
785 &channelRequirements,
786 PlacementOrigin origin);
788 llvm::DenseMap<mlir::Operation *, std::pair<int, int>>
789 buildChannelRequirements(
790 llvm::SmallVector<ObjectFifoCreateOp> &objectFifos,
791 llvm::SmallVector<ObjectFifoLinkOp> &objectFifoLinks,
792 const llvm::DenseMap<mlir::Operation *, unsigned> &rank);
795 struct PlacementContext {
796 const AIETargetModel &targetModel;
797 const Adjacency &computePeerAdjacency;
798 const llvm::DenseMap<mlir::Operation *, int> &needNeighborIn;
799 const llvm::DenseMap<mlir::Operation *, int> &needNeighborOut;
802 llvm::DenseMap<TileID, llvm::SmallVector<mlir::Operation *, 2>>
805 int neighborDemand(mlir::Operation *op)
const {
806 return needNeighborIn.lookup(op) + needNeighborOut.lookup(op);
811 int placementPriority(mlir::Operation *op)
const;
814 void reserveNeighborSlots(mlir::Operation *placedOp,
TileID at);
817 bool isReservedForOther(mlir::Operation *lto,
TileID candidate)
const;
825 struct AdjacencyKind {
826 const Adjacency &adjacency;
827 llvm::function_ref<bool(
TileID firstPos,
TileID secondPos)> pred;
828 llvm::function_ref<llvm::StringRef(
bool thisIsFirst)> peerLabel;
829 llvm::StringRef name;
830 llvm::StringRef constraintHint;
836 mlir::LogicalResult enforceAdjacency(LogicalTileOp logicalTile,
TileID tile,
837 const AdjacencyKind &kind);
844 void recordPlacement(LogicalTileOp logicalTile,
TileID tile,
845 PlacementContext &ctx, llvm::StringRef debugLabel);
850 struct UnpinnedPlacementInputs {
851 const Adjacency &bufferAdjacency;
853 const Adjacency &cascadeAdjacency;
855 const Adjacency &sharedMemAdjacency;
857 const Adjacency &computePeerAdjacency;
858 const llvm::DenseMap<mlir::Operation *, int> &needNeighborIn;
859 const llvm::DenseMap<mlir::Operation *, int> &needNeighborOut;
860 llvm::function_ref<bool(mlir::Operation *,
TileID)> isReservedForOther;
863 llvm::ArrayRef<int> preferredCols;
870 struct UnpinnedSearchResult {
871 std::optional<TileID> placement;
872 bool sawConstraintMatch =
false;
873 bool allConstraintMatchesFailedAdjacency =
true;
874 bool computePeerWasCause =
false;
877 std::optional<TileID> pinClash;
886 UnpinnedSearchResult findUnconstrainedCoreCandidate(
887 LogicalTileOp logicalTile, std::optional<int> col, std::optional<int> row,
888 const UnpinnedPlacementInputs &inputs, llvm::ArrayRef<TileID> candidates,
889 llvm::ArrayRef<TileID> pastBudget);
895 buildBufferAdjacency(llvm::ArrayRef<LogicalTileOp> logicalTiles,
896 llvm::ArrayRef<ObjectFifoAllocateOp>
allocates);
900 struct FlowMembership {
901 llvm::DenseMap<mlir::Value,
902 llvm::SmallVector<llvm::SmallVector<mlir::Value>>>
910 mlir::LogicalResult placeNonCoreLogicalTiles(
911 llvm::ArrayRef<LogicalTileOp> logicalTiles,
912 const FlowMembership &flowIndex,
913 const llvm::DenseMap<mlir::Operation *, std::pair<int, int>>
914 &channelRequirements);
921 llvm::DenseMap<mlir::Operation *, unsigned> groupOf;
922 llvm::SmallVector<llvm::SmallVector<LogicalTileOp>> members;
925 CoreGroups buildCoreGroups(llvm::ArrayRef<LogicalTileOp> logicalTiles,
926 const FlowMembership &flowIndex)
const;
932 llvm::SmallVector<int> preferredGroupColumns(LogicalTileOp logicalTile,
933 const CoreGroups &groups)
const;
936 buildFlowMembership(llvm::ArrayRef<FlowOp> flows,
937 llvm::ArrayRef<PacketFlowOp> pktFlows,
938 llvm::ArrayRef<RouteOp> routes,
939 llvm::ArrayRef<ObjectFifoCreateOp> objectFifos);
944 std::optional<int> computeCentroidColumn(LogicalTileOp logicalTile,
945 const FlowMembership &flowIndex);
947 mlir::LogicalResult placeNonCoreTileByCentroid(
948 LogicalTileOp logicalTile,
const FlowMembership &flowIndex,
949 const llvm::DenseMap<mlir::Operation *, std::pair<int, int>>
950 &channelRequirements);
954 bool satisfiesAdjacency(
955 LogicalTileOp logicalTile,
TileID candidate,
const Adjacency &adjacency,
956 llvm::function_ref<
bool(
TileID firstPos,
TileID secondPos)> pred)
const;
966 bool satisfiesComputePeer(
967 LogicalTileOp logicalTile,
TileID candidate,
969 const llvm::DenseMap<mlir::Operation *, int> &needNeighborIn,
970 const llvm::DenseMap<mlir::Operation *, int> &needNeighborOut)
const;
975 static std::pair<int, int> totalComputePeers(mlir::Operation *op,
980 void attachPeerNotes(
981 mlir::InFlightDiagnostic &diag, LogicalTileOp logicalTile,
983 llvm::function_ref<llvm::StringRef(
bool thisIsFirst)> labelPeer)
const;
1186 : rngSeed(seed), config(config) {}
1188 mlir::LogicalResult
place(DeviceOp device)
override;
1189 llvm::StringRef
getName()
const override {
return "sa_placer"; }
1199 return type == AIETileType::ShimNOCTile || type == AIETileType::ShimPLTile;
1207 int finalLockGroups = 0, finalLockPenalty = 0;
1208 bool finalLockStopped =
false;
1213 CollectedOps collected;
1214 llvm::DenseMap<mlir::Operation *, AIETileType> tileTypes;
1215 llvm::DenseMap<mlir::Operation *, int64_t> staticBufferSizes;
1216 llvm::DenseMap<mlir::Operation *, int64_t> stackSizes;
1220 llvm::MapVector<mlir::Operation *, int> fixedLocks;
1221 llvm::DenseMap<TileID, int> placedLocks;
1222 llvm::SmallVector<TileID> placedTiles;
1225 llvm::DenseMap<mlir::Operation *, unsigned> firstAcquire;
1230 struct InputLockGroup {
1231 mlir::Operation *home;
1232 llvm::SmallVector<std::pair<mlir::Operation *, bool>, 2> users;
1235 llvm::SmallVector<InputLockGroup> inputLockGroups;
1238 struct FifoBufferInfo {
1239 mlir::Operation *fifoOp =
nullptr;
1241 mlir::Operation *producer =
nullptr;
1242 llvm::SmallVector<mlir::Operation *> consumers;
1244 mlir::Operation *producerTile =
nullptr;
1245 llvm::SmallVector<mlir::Operation *> consumerTiles;
1246 mlir::Operation *delegate =
nullptr;
1247 int64_t producerSizeBytes = 0;
1248 int64_t consumerSizeBytes = 0;
1250 int64_t producerRawBytes = 0;
1251 int64_t consumerRawBytes = 0;
1253 int sharedDepth = 0;
1254 int producerDepth = 0;
1255 llvm::SmallVector<int> consumerDepths;
1258 std::optional<PlannedDmaEnd> producerEnd;
1259 llvm::SmallVector<std::optional<PlannedDmaEnd>> consumerEnds;
1260 std::optional<unsigned> producerMemTileEntry;
1261 llvm::SmallVector<std::optional<unsigned>> consumerMemTileEntries;
1265 enum class LinkPool { None, Holds, Shares };
1266 LinkPool producerLinkPool = LinkPool::None;
1267 llvm::SmallVector<LinkPool> consumerLinkPools;
1268 std::optional<PlannedDmaEnd> producerLinkPlan;
1269 llvm::SmallVector<std::optional<PlannedDmaEnd>> consumerLinkPlans;
1271 std::optional<PinnedChannels::End> producerPin;
1272 llvm::SmallVector<std::optional<PinnedChannels::End>> consumerPins;
1274 bool forcesDMA =
false;
1276 mlir::Operation *linkTile =
nullptr;
1279 bool allocateFallsBackToDMA =
false;
1280 bool fitsLinkPool =
true;
1281 bool linkSharedProd =
false;
1284 bool unsynchronized =
false;
1285 int64_t initObjects = 0;
1286 bool rearmed =
false;
1287 bool producerCore =
false;
1288 llvm::SmallVector<bool> consumerCore;
1291 int producerLinkSegments = 0;
1292 llvm::SmallVector<int> consumerLinkSegments;
1294 llvm::SmallVector<NetInfo> nets;
1295 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<size_t>> tileToNetIndices;
1296 llvm::SmallVector<FifoBufferInfo, 0> fifoBuffers;
1298 struct FifoEndTypes {
1299 std::optional<AIETileType> producer;
1300 llvm::SmallVector<std::optional<AIETileType>, 4> consumers;
1302 std::vector<FifoEndTypes> fifoEndTypes;
1306 struct RouteEndInfo {
1307 mlir::Operation *tile;
1310 llvm::SmallVector<RouteEndInfo> routeEnds;
1311 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<size_t>> tileToRouteEnds;
1318 llvm::MapVector<mlir::Operation *, llvm::SmallVector<MemTileEnd>> memTileEnds;
1327 struct VariableLink {
1329 llvm::SmallVector<llvm::SmallVector<std::optional<PlannedDmaEnd>>>
ends;
1332 ObjectFifoLinkOp link;
1335 llvm::SmallVector<mlir::Operation *> tiles;
1336 llvm::SmallVector<size_t> fifos;
1337 llvm::SmallVector<std::pair<size_t, std::optional<unsigned>>> holds;
1338 std::map<std::vector<int64_t>,
Replan> replans;
1340 llvm::SmallVector<VariableLink, 0> variableLinks;
1343 struct ReplannedLink {
1348 llvm::SmallVector<ReplannedLink> replannedLinks;
1350 llvm::DenseSet<mlir::Operation *> chargedPools;
1353 llvm::DenseMap<mlir::Operation *, TileID> currentPlacement;
1354 llvm::DenseMap<TileID, mlir::Operation *> physToLogical;
1355 llvm::SmallVector<mlir::Operation *> movableTiles;
1356 llvm::DenseSet<mlir::Operation *> constrainedTiles;
1359 llvm::DenseMap<mlir::Operation *, llvm::SmallVector<size_t>>
1368 llvm::DenseMap<TileID, llvm::SmallVector<TileID>> lockReach;
1371 JournaledMap<TileID, int> currentLockDemand;
1372 int positionsOverLocks = 0;
1374 llvm::DenseMap<mlir::Operation *, int> homeLocks;
1375 JournaledMap<TileID, std::pair<int, int>> currentDMAUsage;
1379 PinnedChannels pinnedRule;
1380 PinnedChannelUse pinUse;
1381 llvm::SmallVector<std::tuple<TileID, PinnedChannels::End, int>> pinLog;
1382 llvm::SmallVector<std::tuple<TileID, DMAChannelAnalysis::ChannelClaim, int>>
1384 JournaledMap<size_t, TileID> sharedMemDestination;
1385 int cachedResourcePenalty = 0;
1388 int memSpilloverPenalty = 0, bdCountPenalty = 0, delegatePenalty = 0;
1392 struct CoreTileContents {
1393 llvm::SmallVector<TileLayoutBuffer> buffers;
1394 bool hasCore =
false;
1396 std::optional<int> stackBank;
1397 int64_t stackAlignBytes = 1;
1399 llvm::DenseMap<mlir::Operation *, CoreTileContents> coreContents;
1401 using BufferCounts = llvm::SortedVectorMap<int64_t, int, 4>;
1403 JournaledMap<TileID, BufferCounts> coreFifoBuffers;
1406 llvm::SmallVector<std::tuple<TileID, int64_t, int>> coreFifoLog;
1408 JournaledMap<TileID, int64_t> coreUnplacedAt;
1410 llvm::DenseSet<TileID> coreDirty;
1412 int coreOverflowPenalty = 0;
1413 llvm::SmallVector<TileID> coreOverflowTiles;
1417 size_t operator()(
const std::vector<int64_t> &key)
const {
1418 return llvm::hash_combine_range(key.begin(), key.end());
1421 mutable std::unordered_map<std::vector<int64_t>, int64_t, KeyHash>
1422 coreUnplacedOf, coreUnplacedByTile;
1425 mutable std::unordered_map<std::vector<int64_t>, std::pair<int, bool>,
1428 static constexpr size_t kLockVerdictBytes = 1 << 20;
1429 static constexpr unsigned kLockVerdictMissRun = 4096;
1430 mutable size_t lockVerdictBytes = 0;
1431 mutable unsigned lockVerdictMissRun = 0;
1432 llvm::DenseSet<mlir::Operation *> spillTiles, delegateTermTiles, pairedTiles;
1435 llvm::MapVector<mlir::Operation *, llvm::SmallVector<BufferAllocation>>
1441 JournaledMap<TileID, int64_t> bdShortfallAt;
1443 llvm::SmallVector<llvm::SmallVector<std::pair<mlir::Operation *, int>>>;
1444 struct BDShortfall {
1447 llvm::SmallVector<int64_t> bytes;
1451 BoundedMemo<std::vector<uintptr_t>, BDShortfall> bdShortfallOf{1u << 16};
1454 BoundedMemo<std::vector<uintptr_t>, int64_t> unplacedOf{1u << 16};
1457 BoundedMemo<std::vector<int64_t>,
int> spillPenaltyOf{1u << 14};
1460 llvm::SmallVector<MemTileSpillSearch::Tile> memTiles;
1461 llvm::DenseMap<TileID, unsigned> memTileIndex;
1462 llvm::DenseMap<TileID, llvm::SmallVector<TileID, 2>> spillNeighbours;
1465 llvm::DenseMap<TileID, TileID> bdLayoutOf;
1468 std::optional<DMAChannelAnalysis> channelAnalysis;
1469 DMAChannelAnalysis::TakenBDs takenBDs;
1470 llvm::DenseMap<TileID, llvm::SmallVector<mlir::Operation *>> physicalTiles;
1473 llvm::SmallVector<mlir::Operation *> logicalMemTiles;
1474 int cachedPressure = 0;
1477 JournaledMap<TileID, int> dmaPenaltyAt;
1480 llvm::SmallVector<mlir::Operation *> overlayTiles;
1484 int streamCutPenalty = 0;
1486 JournaledMap<unsigned, std::pair<TileID, llvm::SmallVector<TileID, 2>>>
1491 JournaledMap<TileID, StreamDemand> streamsAt;
1492 JournaledMap<int, int> incomingAt;
1493 JournaledMap<std::pair<int, mlir::Operation *>,
int> incomingCount;
1498 JournaledMap<unsigned, int64_t> ddrScoreOf;
1499 int64_t ddrTotal = 0;
1502 JournaledMap<TileID, unsigned> keyAt;
1503 int coresChanged = 0;
1506 llvm::SmallVector<StreamDemand> portsAt;
1507 llvm::SmallVector<int> columnSouthPorts;
1509 void chargeStreams(mlir::Operation *op,
TileID at,
int sign);
1510 int portExcess(
TileID at)
const;
1511 int columnExcess(
int col)
const;
1513 JournaledMap<TileID, int> runtimeBdAt;
1523 int bestCost = INT_MAX;
1524 int bestOverallCost = INT_MAX;
1527 int deviceSlots = 0;
1528 int zeroDeltaMoves = 0, posDeltaMoves = 0, negDeltaMoves = 0;
1529 int acceptedUphill = 0, rejectedMoves = 0;
1530 std::chrono::steady_clock::time_point startTime;
1533 mlir::LogicalResult collectAndBuildModel(DeviceOp device);
1534 mlir::LogicalResult generateInitialPlacement();
1535 void initializeSAState();
1536 void runSAMainLoop();
1537 mlir::LogicalResult finalizePlacement(DeviceOp device);
1540 void initResourceTracking();
1541 void addFifoContribution(
size_t fifoIdx,
int sign);
1542 void addRouteEndContribution(
size_t endIdx,
int sign);
1543 void addLockDemand(
TileID pos,
int locks);
1544 void drawChannel(
TileID position,
bool output,
1545 const std::optional<PinnedChannels::End> &pin,
int sign);
1546 int updateResourcePenalty(
1547 const llvm::SmallVector<std::pair<mlir::Operation *, TileID>>
1549 int getResourcePenalty()
const {
return cachedResourcePenalty; }
1554 int64_t bdShortfall(
TileID position, llvm::ArrayRef<mlir::Operation *> tiles,
1555 WalkSets *walkSets =
nullptr,
1556 llvm::SmallVector<int64_t> *walkBytes =
nullptr);
1558 llvm::SmallVector<mlir::Operation *> memTilesAt(
TileID position)
const;
1561 int computeMemSpilloverPenalty(
1562 llvm::SmallVectorImpl<TileID> *charged =
nullptr);
1563 int computeCoreOverflowPenalty(
1564 llvm::SmallVectorImpl<TileID> *charged =
nullptr)
const;
1566 void chargeCoreFifo(
TileID pos, int64_t bytes,
int count);
1570 int64_t coreUnplaced(
TileID pos,
const BufferCounts &added = {},
1571 const BufferCounts &removed = {})
const;
1577 planCoreFit(
TileID pos, llvm::DenseMap<TileID, BufferCounts> &lent,
1578 llvm::SmallVectorImpl<std::pair<size_t, TileID>> *moves)
const;
1581 llvm::SmallVector<TileID> refreshCoreUnplaced();
1583 llvm::DenseSet<TileID> coreOverflowReads()
const;
1585 int computeDMAChannelPenalty();
1587 int computeTileDMAPenalty(
TileID tilePos,
int *bdIds =
nullptr)
const;
1590 void chargeRuntimeBds(
TileID pos);
1592 int computeBDCountPenalty();
1593 int computeDelegatePenalty(
1594 llvm::SmallVectorImpl<TileID> *charged =
nullptr)
const;
1599 void replanLinks(llvm::ArrayRef<std::pair<unsigned, int64_t>> depths);
1602 int computeLockPenalty(
1603 bool *stopped =
nullptr,
1604 llvm::SmallVectorImpl<TileID> *charged =
nullptr)
const;
1610 std::pair<int, llvm::SmallVector<std::pair<TileID, bool>, 2>>>
1612 std::optional<TileID> positionOf(mlir::Operation *tile)
const;
1613 int computeMemoryPressure()
const;
1615 int computeSoftTerms()
const;
1618 int coresChangedAt(
TileID pos)
const;
1619 int computeAdjacencyPenalty(
1620 const Adjacency &adj, llvm::ArrayRef<std::pair<int, int>> validOffsets,
1621 int weight, llvm::SmallVectorImpl<TileID> *charged =
nullptr)
const;
1624 int computePairingPenalty(
1625 llvm::SmallVectorImpl<TileID> *charged =
nullptr)
const;
1629 void explainPenalties(mlir::InFlightDiagnostic &diag);
1631 llvm::SmallVector<TileID> overflowingCoreTiles()
const;
1632 void generateAllocates();
1635 void tryMove(llvm::SmallVector<std::pair<mlir::Operation *, TileID>> &moves);
1639 void rollbackMove();
1641 generateMove(llvm::SmallVector<std::pair<mlir::Operation *, TileID>> &moves);
1643 mlir::Operation *tile,
TileID newPos,
1644 llvm::SmallVector<std::pair<size_t, NetBoundingBox>> &backups);
1646 revertMove(llvm::SmallVector<std::pair<size_t, NetBoundingBox>> &backups);
1649 void buildNetModel(llvm::SmallVector<ObjectFifoCreateOp> &objectFifos,
1650 llvm::SmallVector<ObjectFifoLinkOp> &objectFifoLinks);
1651 void buildFifoBufferInfo(DeviceOp device,
1652 llvm::ArrayRef<ObjectFifoCreateOp> objectFifos,
1653 llvm::ArrayRef<ObjectFifoLinkOp> objectFifoLinks);
1654 void buildRouteModel(DeviceOp device, llvm::ArrayRef<FlowOp> flows,
1655 llvm::ArrayRef<PacketFlowOp> pktFlows,
1656 llvm::ArrayRef<RouteOp> routes,
1657 llvm::ArrayRef<DMAChannelAnalysis::ChannelClaim> claims);
1658 int computeNetHPWL(
const NetInfo &net)
const;
1659 int computeTotalHPWL()
const;
1660 void initBoundingBoxes();
1661 double estimateInitialTemperature(
int numSamples);
1662 bool isLegalPosition(mlir::Operation *tile,
TileID pos)
const;
1665 llvm::SmallVector<mlir::Operation *>
1666 namedAt(mlir::Operation *tile,
TileID pos,
1667 mlir::Operation *leaving =
nullptr)
const;
1668 int64_t computeTileMemoryWeight(mlir::Operation *tile)
const;
1669 void printPlacementStats(int64_t elapsedMs)
const;