| 1 | //===- Mem2Reg.cpp - Promotes memory slots into values ----------*- C++ -*-===// |
| 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 | #include "mlir/Transforms/Mem2Reg.h" |
| 10 | #include "mlir/Analysis/DataLayoutAnalysis.h" |
| 11 | #include "mlir/Analysis/SliceAnalysis.h" |
| 12 | #include "mlir/Analysis/TopologicalSortUtils.h" |
| 13 | #include "mlir/IR/Builders.h" |
| 14 | #include "mlir/IR/Dominance.h" |
| 15 | #include "mlir/IR/PatternMatch.h" |
| 16 | #include "mlir/IR/RegionKindInterface.h" |
| 17 | #include "mlir/IR/Value.h" |
| 18 | #include "mlir/Interfaces/ControlFlowInterfaces.h" |
| 19 | #include "mlir/Interfaces/MemorySlotInterfaces.h" |
| 20 | #include "mlir/Transforms/Passes.h" |
| 21 | #include "llvm/ADT/STLExtras.h" |
| 22 | #include "llvm/ADT/SetVector.h" |
| 23 | #include "llvm/Support/DebugLog.h" |
| 24 | #include "llvm/Support/GenericIteratedDominanceFrontier.h" |
| 25 | |
| 26 | namespace mlir { |
| 27 | #define GEN_PASS_DEF_MEM2REG |
| 28 | #include "mlir/Transforms/Passes.h.inc" |
| 29 | } // namespace mlir |
| 30 | |
| 31 | #define DEBUG_TYPE "mem2reg" |
| 32 | |
| 33 | using namespace mlir; |
| 34 | |
| 35 | /// mem2reg |
| 36 | /// |
| 37 | /// This pass turns unnecessary uses of automatically allocated memory slots |
| 38 | /// into direct Value-based operations. For example, it will simplify storing a |
| 39 | /// constant in a memory slot to immediately load it to a direct use of that |
| 40 | /// constant. In other words, given a memory slot addressed by a "pointer" Value |
| 41 | /// (which may be exposed through aliases), mem2reg removes all the uses of |
| 42 | /// that pointer and its aliases. |
| 43 | /// |
| 44 | /// Within a block, this is done by following the chain of stores and loads of |
| 45 | /// the slot (or its aliases) and replacing the results of loads with the values |
| 46 | /// previously stored. If a load happens before any other store, a poison value |
| 47 | /// is used instead. |
| 48 | /// |
| 49 | /// Control flow can create situations where a load could be replaced by |
| 50 | /// multiple possible stores depending on the control flow path taken. As a |
| 51 | /// result, this pass must introduce new block arguments in some blocks to |
| 52 | /// accommodate for the multiple possible definitions. Each predecessor will |
| 53 | /// populate the block argument with the definition reached at its end. With |
| 54 | /// this, the value stored can be well defined at block boundaries, allowing |
| 55 | /// the propagation of replacement through blocks. |
| 56 | /// |
| 57 | /// The way regions are handled in the transformation is by offering an |
| 58 | /// interface to express the behavior of the allocation value at the edges of |
| 59 | /// the regions: from a particular definition reaching the region operation, the |
| 60 | /// operation will specify what the reaching definition at the entry of its |
| 61 | /// regions are (potentially mutating itself, for example to add region |
| 62 | /// arguments). Likewise, provided a reaching definition at the end of the |
| 63 | /// blocks in the regions, the region operation will provide the reaching |
| 64 | /// definition right after itself. |
| 65 | /// |
| 66 | /// This pass computes this transformation in two main phases: an analysis |
| 67 | /// phase that does not mutate IR, and a transformation phase where mutation |
| 68 | /// happens. Each phase is handled by the `MemorySlotPromotionAnalyzer` and |
| 69 | /// `MemorySlotPromoter` classes respectively. |
| 70 | /// |
| 71 | /// The two steps of the analysis phase are the following: |
| 72 | /// - A first step computes the list of operations that transitively use the |
| 73 | /// memory slot we would like to promote. The purpose of this phase is to |
| 74 | /// identify which uses must be removed to promote the slot, either by rewiring |
| 75 | /// the user or deleting it. Naturally, direct uses of the slot and its aliases |
| 76 | /// must be removed. Sometimes additional uses must also be removed: this is |
| 77 | /// notably the case when a direct user of the slot cannot rewire its use and |
| 78 | /// must delete itself, and thus must make its users no longer use it. If the |
| 79 | /// allocation is used in nested regions, it is also ensured the region |
| 80 | /// operations provide the right interface to analyze the values of the |
| 81 | /// allocation at the edges of its regions. If any of those constraints cannot |
| 82 | /// be satisfied, promotion cannot continue: this is decided at this step. |
| 83 | /// - A second step computes the list of blocks where a block argument will be |
| 84 | /// needed ("merge points") without mutating the IR. These blocks are the blocks |
| 85 | /// leading to a definition clash between two predecessors. Such blocks happen |
| 86 | /// to be the Iterated Dominance Frontier (IDF) of the set of blocks containing |
| 87 | /// a store, as they represent the points where a clear defining dominator stops |
| 88 | /// existing. Computing this information in advance allows making sure the |
| 89 | /// terminators that will forward values are capable of doing so (inability to |
| 90 | /// do so aborts promotion at this step). |
| 91 | /// |
| 92 | /// At this point, promotion is guaranteed to happen, and the transformation |
| 93 | /// phase can begin. The transformation is a three-step process. |
| 94 | /// - The first step computes the reaching definition of the memory slot at |
| 95 | /// each blocking user. This is the core of the mem2reg algorithm, also known |
| 96 | /// as load-store forwarding. This analyses loads and stores and propagates |
| 97 | /// which value must be stored in the slot at each blocking user. This is |
| 98 | /// achieved by doing a depth-first walk of the dominator tree of the function. |
| 99 | /// This is sufficient because the reaching definition at the beginning of a |
| 100 | /// block is either its new block argument if it is a merge block, or the |
| 101 | /// definition reaching the end of its immediate dominator (parent in the |
| 102 | /// dominator tree). We can therefore propagate this information down the |
| 103 | /// dominator tree to proceed with renaming within blocks. If at any point a |
| 104 | /// region operation that contains a use of the allocation is encountered, the |
| 105 | /// reaching definition computation is recursively triggered on the child |
| 106 | /// regions of the encountered operation, to obtain the reaching definition at |
| 107 | /// its end and carry on with the value forwarding. |
| 108 | /// - The second step visits the values that will replace the memory slot for |
| 109 | /// operations that requested it. This must happen before the removal of |
| 110 | /// blocking uses, so that operations can safely inspect reaching definitions |
| 111 | /// before they may be removed or modified. |
| 112 | /// - The third step uses the reaching definition to remove blocking uses. Some |
| 113 | /// reaching definitions may be values that will be removed or modified during |
| 114 | /// the blocking use removal step (typically, in the case of a store that stores |
| 115 | /// the result of a load). To properly handle such values, this step traverses |
| 116 | /// the regions in post-order, and the operations to modify in reverse |
| 117 | /// topological order. This way, if a value that will disappear is used in place |
| 118 | /// of a reaching definition, the logic to make it disappear will be executed |
| 119 | /// after the value has been used to replace an operation. For regions within a |
| 120 | /// PromotableRegionOpInterface, this ensures that the finalization logic (run |
| 121 | /// during the first step) and visitReplacedValues (run during the second step) |
| 122 | /// happen before the blocking use removal step, so that any use of a value that |
| 123 | /// will be removed gets properly replaced. |
| 124 | /// |
| 125 | /// For further reading, chapter three of SSA-based Compiler Design [1] |
| 126 | /// showcases SSA construction for control-flow graphs, where mem2reg is an |
| 127 | /// adaptation of the same process. |
| 128 | /// |
| 129 | /// [1]: Rastello F. & Bouchez Tichadou F., SSA-based Compiler Design (2022), |
| 130 | /// Springer. |
| 131 | |
| 132 | namespace { |
| 133 | |
| 134 | using BlockingUsesMap = |
| 135 | llvm::MapVector<Operation *, SmallPtrSet<OpOperand *, 4>>; |
| 136 | using RegionBlockingUsesMap = |
| 137 | llvm::SmallMapVector<Region *, BlockingUsesMap, 2>; |
| 138 | |
| 139 | using RegionSet = SmallPtrSet<Region *, 32>; |
| 140 | |
| 141 | /// Information about regions that will be traversed for promotion, computed |
| 142 | /// during promotion analysis. |
| 143 | struct RegionPromotionInfo { |
| 144 | /// True if an operation storing to the slot is present in the region. |
| 145 | bool hasValueStores; |
| 146 | }; |
| 147 | |
| 148 | /// Information computed during promotion analysis used to perform actual |
| 149 | /// promotion. |
| 150 | struct MemorySlotPromotionInfo { |
| 151 | /// Blocks for which at least two definitions of the slot values clash. |
| 152 | SmallPtrSet<Block *, 8> mergePoints; |
| 153 | /// Contains, for each each region, the blocking uses for its operations. The |
| 154 | /// blocking uses are the uses that must be eliminated by promotion. For each |
| 155 | /// region, this is a DAG structure because if an operation must eliminate |
| 156 | /// some of its uses, it is because the defining ops of the blocking uses |
| 157 | /// requested it. The defining ops therefore must also have blocking uses or |
| 158 | /// be the starting point of the blocking uses. |
| 159 | RegionBlockingUsesMap userToBlockingUses; |
| 160 | /// Regions of which the edges must be analyzed for promotion. All regions |
| 161 | /// are guaranteed to be held by a PromotableRegionOpInterface, and to be |
| 162 | /// nested within the parent region of the slot pointer. |
| 163 | DenseMap<Region *, RegionPromotionInfo> regionsToPromote; |
| 164 | /// Transitive aliases of `slot.ptr` via `PromotableAliaserInterface`, |
| 165 | /// mapping alias values to their exposed slot and aliased operand. |
| 166 | PromotableAliasMap aliasMap; |
| 167 | /// True if at least one blocking use requires visiting the replaced values. |
| 168 | bool needsAnyReplacedValuesVisit = false; |
| 169 | }; |
| 170 | |
| 171 | /// Computes information for basic slot promotion. This will check that direct |
| 172 | /// slot promotion can be performed, and provide the information to execute the |
| 173 | /// promotion. This does not mutate IR. |
| 174 | class MemorySlotPromotionAnalyzer { |
| 175 | public: |
| 176 | MemorySlotPromotionAnalyzer(MemorySlot slot, DominanceInfo &dominance, |
| 177 | const DataLayout &dataLayout) |
| 178 | : slot(slot), dominance(dominance), dataLayout(dataLayout) {} |
| 179 | |
| 180 | /// Computes the information for slot promotion if promotion is possible, |
| 181 | /// returns nothing otherwise. |
| 182 | std::optional<MemorySlotPromotionInfo> computeInfo(); |
| 183 | |
| 184 | private: |
| 185 | /// Computes the transitive uses of the slot that block promotion. This finds |
| 186 | /// uses that would block the promotion, checks that the operation has a |
| 187 | /// solution to remove the blocking use, and potentially forwards the analysis |
| 188 | /// if the operation needs further blocking uses resolved to resolve its own |
| 189 | /// uses (typically, removing its users because it will delete itself to |
| 190 | /// resolve its own blocking uses). This will fail if one of the transitive |
| 191 | /// users cannot remove a requested use, and should prevent promotion. |
| 192 | /// Resulting blocking uses are grouped by region. |
| 193 | /// This also ensures all the uses are within promotable regions, adding |
| 194 | /// information about regions to be promoted to the `regionsToPromote` map. |
| 195 | LogicalResult |
| 196 | computeBlockingUses(RegionBlockingUsesMap &userToBlockingUses, |
| 197 | DenseMap<Region *, RegionPromotionInfo> ®ionsToPromote, |
| 198 | PromotableAliasMap &aliasMap, |
| 199 | bool &needsAnyReplacedValuesVisit); |
| 200 | |
| 201 | /// Computes the points in the provided region where multiple re-definitions |
| 202 | /// of the slot's value (stores) may conflict. |
| 203 | /// `definingBlocks` is the set of blocks containing a store to the slot, |
| 204 | /// either directly or inherited from a nested region. |
| 205 | void computeMergePoints(Region *region, |
| 206 | SmallPtrSetImpl<Block *> &definingBlocks, |
| 207 | SmallPtrSetImpl<Block *> &mergePoints); |
| 208 | |
| 209 | /// Ensures predecessors of merge points can properly provide their current |
| 210 | /// definition of the value stored in the slot to the merge point. This can |
| 211 | /// notably be an issue if the terminator used does not have the ability to |
| 212 | /// forward values through block operands. |
| 213 | bool areMergePointsUsable(SmallPtrSetImpl<Block *> &mergePoints); |
| 214 | |
| 215 | MemorySlot slot; |
| 216 | |
| 217 | DominanceInfo &dominance; |
| 218 | const DataLayout &dataLayout; |
| 219 | }; |
| 220 | |
| 221 | /// Maps a region to a map of blocks to their index in the region. |
| 222 | /// The region is identified by its entry block pointer instead of its region |
| 223 | /// pointer to not need to invalidate the cache when region content is moved to |
| 224 | /// a new region. This only supports moves of all the blocks of a region to |
| 225 | /// an empty region. |
| 226 | using BlockIndexCache = DenseMap<Block *, DenseMap<Block *, size_t>>; |
| 227 | |
| 228 | /// The MemorySlotPromoter handles the state of promoting a memory slot. It |
| 229 | /// wraps a slot and its associated allocator. This will perform the mutation of |
| 230 | /// IR. |
| 231 | class MemorySlotPromoter { |
| 232 | public: |
| 233 | MemorySlotPromoter(MemorySlot slot, PromotableAllocationOpInterface allocator, |
| 234 | OpBuilder &builder, DominanceInfo &dominance, |
| 235 | const DataLayout &dataLayout, MemorySlotPromotionInfo info, |
| 236 | const Mem2RegStatistics &statistics, |
| 237 | BlockIndexCache &blockIndexCache); |
| 238 | |
| 239 | /// Actually promotes the slot by mutating IR. Promoting a slot DOES |
| 240 | /// invalidate the MemorySlotPromotionInfo of other slots. Preparation of |
| 241 | /// promotion info should NOT be performed in batches. |
| 242 | /// Returns a promotable allocation op if a new allocator was created, nullopt |
| 243 | /// otherwise. |
| 244 | std::optional<PromotableAllocationOpInterface> promoteSlot(); |
| 245 | |
| 246 | private: |
| 247 | /// Computes the reaching definition for all the operations that require |
| 248 | /// promotion, including within nested regions needing promotion. |
| 249 | /// `reachingDef` is the value the slot contains at the beginning of the |
| 250 | /// block. This member function returns the reached definition at the end of |
| 251 | /// the block. Blocking uses are not removed and `visitReplacedValues` is |
| 252 | /// not called here; both are deferred to `promoteSlot`. |
| 253 | /// |
| 254 | /// The `reachingDef` may be a null value. In that case, a lazily-created |
| 255 | /// default value will be used. |
| 256 | /// |
| 257 | /// This member function must only be called at most once per block. |
| 258 | Value promoteInBlock(Block *block, Value reachingDef); |
| 259 | |
| 260 | /// Computes the reaching definition for all the operations that require |
| 261 | /// promotion, including within nested regions needing promotion. Records |
| 262 | /// `region` in `regionsInPostOrder` after the DFS completes. |
| 263 | /// `reachingDef` is the value the slot contains at the beginning of the |
| 264 | /// region. Blocking uses are not removed here; that is deferred to |
| 265 | /// `promoteSlot`. |
| 266 | /// |
| 267 | /// The `reachingDef` may be a null value. In that case, a lazily-created |
| 268 | /// default value will be used. |
| 269 | /// |
| 270 | /// This member function must only be called at most once per region. |
| 271 | void promoteInRegion(Region *region, Value reachingDef); |
| 272 | |
| 273 | /// Calls `visitReplacedValues` on ops in `region` that requested it. |
| 274 | /// Must run before `removeBlockingUses` so that replacedValues are still |
| 275 | /// valid (`removeBlockingUses` can later replace them). |
| 276 | void visitReplacedValuesForRegion( |
| 277 | Region *region, ArrayRef<std::pair<Operation *, Value>> replacedValues); |
| 278 | |
| 279 | /// Removes the blocking uses of the slot within the given region, in |
| 280 | /// reverse topological order. If the content of the region was moved out |
| 281 | /// to a different region, the new region will be processed instead. |
| 282 | void removeBlockingUses(Region *region); |
| 283 | |
| 284 | /// Removes operations and merge point block arguments that ended up not being |
| 285 | /// necessary. |
| 286 | void removeUnusedItems(); |
| 287 | |
| 288 | /// Lazily-constructed default value representing the content of the slot when |
| 289 | /// no store has been executed. This function may mutate IR. |
| 290 | Value getOrCreateDefaultValue(); |
| 291 | |
| 292 | MemorySlot slot; |
| 293 | PromotableAllocationOpInterface allocator; |
| 294 | OpBuilder &builder; |
| 295 | /// Potentially non-initialized default value. Use `getOrCreateDefaultValue` |
| 296 | /// to initialize it on demand. |
| 297 | Value defaultValue; |
| 298 | /// Contains the reaching definition at this operation. Reaching definitions |
| 299 | /// are only computed for promotable memory operations with blocking uses. |
| 300 | DenseMap<PromotableMemOpInterface, Value> reachingDefs; |
| 301 | DenseMap<PromotableMemOpInterface, Value> replacedValuesMap; |
| 302 | |
| 303 | /// Contains the reaching definition at the end of the blocks visited so far. |
| 304 | DenseMap<Block *, Value> reachingAtBlockEnd; |
| 305 | |
| 306 | /// Regions visited by `promoteInRegion`, recorded in DFS post-order. |
| 307 | /// Inner regions appear before their enclosing regions. |
| 308 | llvm::SmallVector<Region *> regionsInPostOrder; |
| 309 | |
| 310 | /// Operations to be erased at the end of the promotion. |
| 311 | llvm::SmallSetVector<Operation *, 8> toErase; |
| 312 | |
| 313 | DominanceInfo &dominance; |
| 314 | const DataLayout &dataLayout; |
| 315 | MemorySlotPromotionInfo info; |
| 316 | const Mem2RegStatistics &statistics; |
| 317 | |
| 318 | /// Shared cache of block indices of specific regions. |
| 319 | /// Cache entries must be invalidated before any addition, removal or |
| 320 | /// reordering of blocks in the corresponding region. |
| 321 | /// Cache entries are *NOT* invalidated if all the blocks of the corresponding |
| 322 | /// region are moved to an empty region. |
| 323 | BlockIndexCache &blockIndexCache; |
| 324 | }; |
| 325 | |
| 326 | } // namespace |
| 327 | |
| 328 | MemorySlotPromoter::MemorySlotPromoter( |
| 329 | MemorySlot slot, PromotableAllocationOpInterface allocator, |
| 330 | OpBuilder &builder, DominanceInfo &dominance, const DataLayout &dataLayout, |
| 331 | MemorySlotPromotionInfo info, const Mem2RegStatistics &statistics, |
| 332 | BlockIndexCache &blockIndexCache) |
| 333 | : slot(slot), allocator(allocator), builder(builder), dominance(dominance), |
| 334 | dataLayout(dataLayout), info(std::move(info)), statistics(statistics), |
| 335 | blockIndexCache(blockIndexCache) { |
| 336 | #ifndef NDEBUG |
| 337 | auto isResultOrNewBlockArgument = [&]() { |
| 338 | if (BlockArgument arg = dyn_cast<BlockArgument>(slot.ptr)) |
| 339 | return arg.getOwner()->getParentOp() == allocator; |
| 340 | return slot.ptr.getDefiningOp() == allocator; |
| 341 | }; |
| 342 | |
| 343 | assert(isResultOrNewBlockArgument() && |
| 344 | "a slot must be a result of the allocator or an argument of the child " |
| 345 | "regions of the allocator" ); |
| 346 | #endif // NDEBUG |
| 347 | } |
| 348 | |
| 349 | Value MemorySlotPromoter::getOrCreateDefaultValue() { |
| 350 | if (defaultValue) |
| 351 | return defaultValue; |
| 352 | |
| 353 | OpBuilder::InsertionGuard guard(builder); |
| 354 | builder.setInsertionPointToStart(&slot.ptr.getParentRegion()->front()); |
| 355 | return defaultValue = allocator.getDefaultValue(slot, builder); |
| 356 | } |
| 357 | |
| 358 | /// Returns `op`'s parent if it owns the blocking uses of `op` as a wrapped |
| 359 | /// access, or `op` otherwise. |
| 360 | static Operation *getBlockingUseOwner(Operation *op) { |
| 361 | auto memOp = dyn_cast_or_null<PromotableMemOpInterface>(Val: op->getParentOp()); |
| 362 | return memOp && memOp.ownsWrappedBlockingUses() ? memOp : op; |
| 363 | } |
| 364 | |
| 365 | LogicalResult MemorySlotPromotionAnalyzer::computeBlockingUses( |
| 366 | RegionBlockingUsesMap &userToBlockingUses, |
| 367 | DenseMap<Region *, RegionPromotionInfo> ®ionsToPromote, |
| 368 | PromotableAliasMap &aliasMap, bool &needsAnyReplacedValuesVisit) { |
| 369 | // The promotion of an operation may require the promotion of further |
| 370 | // operations (typically, removing operations that use an operation that must |
| 371 | // delete itself). We thus need to start from the use of the slot pointer and |
| 372 | // propagate further requests through the forward slice. |
| 373 | |
| 374 | // Graph regions are not supported. |
| 375 | Region *slotPtrRegion = slot.ptr.getParentRegion(); |
| 376 | auto slotPtrRegionOp = |
| 377 | dyn_cast<RegionKindInterface>(Val: slotPtrRegion->getParentOp()); |
| 378 | if (slotPtrRegionOp && |
| 379 | slotPtrRegionOp.getRegionKind(index: slotPtrRegion->getRegionNumber()) == |
| 380 | RegionKind::Graph) |
| 381 | return failure(); |
| 382 | |
| 383 | // First insert that all immediate users of the slot pointer must no longer |
| 384 | // use it. |
| 385 | for (OpOperand &use : slot.ptr.getUses()) { |
| 386 | Operation *useOwner = getBlockingUseOwner(op: use.getOwner()); |
| 387 | SmallPtrSet<OpOperand *, 4> &blockingUses = |
| 388 | userToBlockingUses[useOwner->getParentRegion()][useOwner]; |
| 389 | blockingUses.insert(Ptr: &use); |
| 390 | } |
| 391 | |
| 392 | // Regions that immediately contain a slot memory use that is not a store. |
| 393 | RegionSet regionsWithDirectUse; |
| 394 | // Regions that immediately contain a slot memory use that is a store. |
| 395 | RegionSet regionsWithDirectStore; |
| 396 | |
| 397 | // Then, propagate the requirements for the removal of uses. The |
| 398 | // topologically-sorted forward slice allows for all blocking uses of an |
| 399 | // operation to have been computed before it is reached. Operations are |
| 400 | // traversed in topological order of their uses, starting from the slot |
| 401 | // pointer. |
| 402 | SetVector<Operation *> forwardSlice; |
| 403 | mlir::getForwardSlice(root: slot.ptr, forwardSlice: &forwardSlice); |
| 404 | SmallPtrSet<Operation *, 4> visitedWrappers; |
| 405 | for (Operation *op : forwardSlice) { |
| 406 | Operation *user = getBlockingUseOwner(op); |
| 407 | // Both a wrapped access and the terminator yielding its results map to |
| 408 | // the wrapper. Only process the wrapper once. |
| 409 | if (user != op && !visitedWrappers.insert(Ptr: user).second) |
| 410 | continue; |
| 411 | // If the next operation has no blocking uses, everything is fine. |
| 412 | auto *blockingUsesMapIt = userToBlockingUses.find(Key: user->getParentRegion()); |
| 413 | if (blockingUsesMapIt == userToBlockingUses.end()) |
| 414 | continue; |
| 415 | BlockingUsesMap &blockingUsesMap = blockingUsesMapIt->second; |
| 416 | auto *it = blockingUsesMap.find(Key: user); |
| 417 | if (it == blockingUsesMap.end()) |
| 418 | continue; |
| 419 | |
| 420 | // Populate the alias map for alias-exposing ops. |
| 421 | if (auto aliaser = dyn_cast<PromotableAliaserInterface>(Val: user)) |
| 422 | populatePromotableAliasMap(aliaser, rootSlot: slot, aliasMap); |
| 423 | |
| 424 | SmallPtrSet<OpOperand *, 4> &blockingUses = it->second; |
| 425 | |
| 426 | SmallVector<OpOperand *> newBlockingUses; |
| 427 | // If the operation decides it cannot deal with removing the blocking uses, |
| 428 | // promotion must fail. |
| 429 | if (auto promotable = dyn_cast<PromotableOpInterface>(Val: user)) { |
| 430 | if (!promotable.canUsesBeRemoved(blockingUses, newBlockingUses, |
| 431 | datalayout: dataLayout)) |
| 432 | return failure(); |
| 433 | regionsWithDirectUse.insert(Ptr: user->getParentRegion()); |
| 434 | if (promotable.requiresReplacedValues()) |
| 435 | needsAnyReplacedValuesVisit = true; |
| 436 | } else if (auto promotable = dyn_cast<PromotableMemOpInterface>(Val: user)) { |
| 437 | // If the memop reaches the root slot through multiple distinct alias |
| 438 | // operands, promotion fails. `PromotableMemOpInterface` expects a |
| 439 | // single slot per call. Supporting multiple aliases would require |
| 440 | // extending the interface. |
| 441 | if (!referencesAtMostOneAliasOfSlot(op: user, rootSlot: slot, aliasMap)) |
| 442 | return failure(); |
| 443 | MemorySlot aliasSlot = |
| 444 | getOpAliasSlot(op: user, rootSlot: slot, aliasMap).value_or(u&: slot); |
| 445 | if (!promotable.canUsesBeRemoved(slot: aliasSlot, blockingUses, newBlockingUses, |
| 446 | datalayout: dataLayout)) |
| 447 | return failure(); |
| 448 | |
| 449 | // Operations that interact with the slot's memory will be promoted using |
| 450 | // a reaching definition. Therefore, the operation must be within a region |
| 451 | // where the reaching definition can be computed. |
| 452 | if (promotable.storesTo(slot: aliasSlot)) |
| 453 | regionsWithDirectStore.insert(Ptr: user->getParentRegion()); |
| 454 | else |
| 455 | regionsWithDirectUse.insert(Ptr: user->getParentRegion()); |
| 456 | } else { |
| 457 | // An operation that has blocking uses must be promoted. If it is not |
| 458 | // promotable, promotion must fail. |
| 459 | return failure(); |
| 460 | } |
| 461 | |
| 462 | // A wrapper wraps a memory access, not an alias op, so it creates no new |
| 463 | // blocking uses. |
| 464 | assert((user == op || newBlockingUses.empty()) && |
| 465 | "an op owning wrapped blocking uses must not add new blocking uses" ); |
| 466 | |
| 467 | // Then, register any new blocking uses for coming operations. |
| 468 | for (OpOperand *blockingUse : newBlockingUses) { |
| 469 | assert(llvm::is_contained(user->getResults(), blockingUse->get())); |
| 470 | |
| 471 | Operation *useOwner = getBlockingUseOwner(op: blockingUse->getOwner()); |
| 472 | SmallPtrSetImpl<OpOperand *> &newUserBlockingUseSet = |
| 473 | userToBlockingUses[useOwner->getParentRegion()][useOwner]; |
| 474 | newUserBlockingUseSet.insert(Ptr: blockingUse); |
| 475 | } |
| 476 | } |
| 477 | |
| 478 | // Finally, check that all the regions needed are promotable, and propagate |
| 479 | // the constraint to their parent regions. |
| 480 | auto visitRegions = [&](SmallVector<Region *> ®ionsToPropagateFrom, |
| 481 | bool hasValueStores) { |
| 482 | while (!regionsToPropagateFrom.empty()) { |
| 483 | Region *region = regionsToPropagateFrom.pop_back_val(); |
| 484 | |
| 485 | if (region == slot.ptr.getParentRegion() || |
| 486 | regionsToPromote.contains(Val: region)) |
| 487 | continue; |
| 488 | |
| 489 | RegionPromotionInfo ®ionInfo = regionsToPromote[region]; |
| 490 | regionInfo.hasValueStores = hasValueStores; |
| 491 | |
| 492 | auto promotableParentOp = |
| 493 | dyn_cast<PromotableRegionOpInterface>(Val: region->getParentOp()); |
| 494 | if (!promotableParentOp) |
| 495 | return failure(); |
| 496 | |
| 497 | if (!promotableParentOp.isRegionPromotable(slot, region, hasValueStores)) |
| 498 | return failure(); |
| 499 | |
| 500 | regionsToPropagateFrom.push_back(Elt: region->getParentRegion()); |
| 501 | } |
| 502 | |
| 503 | return success(); |
| 504 | }; |
| 505 | |
| 506 | // Start with the regions that directly contain a store to give priority |
| 507 | // to stores in the propagation of `hasValueStores` information. |
| 508 | SmallVector<Region *> regionsToPropagateFrom(regionsWithDirectStore.begin(), |
| 509 | regionsWithDirectStore.end()); |
| 510 | if (failed(Result: visitRegions(regionsToPropagateFrom, true))) |
| 511 | return failure(); |
| 512 | |
| 513 | // Then, propagate from the regions that directly contain non-store uses. |
| 514 | regionsToPropagateFrom.clear(); |
| 515 | regionsToPropagateFrom.append(in_start: regionsWithDirectUse.begin(), |
| 516 | in_end: regionsWithDirectUse.end()); |
| 517 | if (failed(Result: visitRegions(regionsToPropagateFrom, false))) |
| 518 | return failure(); |
| 519 | |
| 520 | return success(); |
| 521 | } |
| 522 | |
| 523 | using IDFCalculator = llvm::IDFCalculatorBase<Block, false>; |
| 524 | void MemorySlotPromotionAnalyzer::computeMergePoints( |
| 525 | Region *region, SmallPtrSetImpl<Block *> &definingBlocks, |
| 526 | SmallPtrSetImpl<Block *> &mergePoints) { |
| 527 | if (region->hasOneBlock()) |
| 528 | return; |
| 529 | |
| 530 | IDFCalculator idfCalculator(dominance.getDomTree(region)); |
| 531 | idfCalculator.setDefiningBlocks(definingBlocks); |
| 532 | |
| 533 | SmallVector<Block *> mergePointsVec; |
| 534 | idfCalculator.calculate(IDFBlocks&: mergePointsVec); |
| 535 | |
| 536 | mergePoints.insert_range(R&: mergePointsVec); |
| 537 | } |
| 538 | |
| 539 | bool MemorySlotPromotionAnalyzer::areMergePointsUsable( |
| 540 | SmallPtrSetImpl<Block *> &mergePoints) { |
| 541 | for (Block *mergePoint : mergePoints) |
| 542 | for (Block *pred : mergePoint->getPredecessors()) |
| 543 | if (!isa<BranchOpInterface>(Val: pred->getTerminator())) |
| 544 | return false; |
| 545 | |
| 546 | return true; |
| 547 | } |
| 548 | |
| 549 | std::optional<MemorySlotPromotionInfo> |
| 550 | MemorySlotPromotionAnalyzer::computeInfo() { |
| 551 | MemorySlotPromotionInfo info; |
| 552 | |
| 553 | // First, find the set of operations that will need to be changed for the |
| 554 | // promotion to happen. These operations need to resolve some of their uses, |
| 555 | // either by rewiring them or simply deleting themselves. If any of them |
| 556 | // cannot find a way to resolve their blocking uses, we abort the promotion. |
| 557 | // We also compute at this stage the regions that will be analyzed for |
| 558 | // reaching definition information. |
| 559 | if (failed(Result: computeBlockingUses(userToBlockingUses&: info.userToBlockingUses, regionsToPromote&: info.regionsToPromote, |
| 560 | aliasMap&: info.aliasMap, |
| 561 | needsAnyReplacedValuesVisit&: info.needsAnyReplacedValuesVisit))) |
| 562 | return {}; |
| 563 | |
| 564 | // Compute the blocks containing a store for each region, either directly or |
| 565 | // inherited from a nested region. As a side effect, `definingBlocks` contains |
| 566 | // all regions with at least one store. |
| 567 | // |
| 568 | // Iterate over direct users of the slot pointer and all alias pointers in |
| 569 | // `info.aliasMap`. This assumes `PromotableMemOpInterface` operations storing |
| 570 | // to the slot use the slot pointer or its aliases directly. Dialects must |
| 571 | // implement `PromotableAliaserInterface` for views/aliasing. |
| 572 | DenseMap<Region *, SmallPtrSet<Block *, 16>> definingBlocks; |
| 573 | auto collectStoringBlocks = [&](Value ptr, const MemorySlot &ptrSlot) { |
| 574 | for (OpOperand &use : ptr.getUses()) { |
| 575 | Operation *user = getBlockingUseOwner(op: use.getOwner()); |
| 576 | if (auto storeOp = dyn_cast<PromotableMemOpInterface>(Val: user)) |
| 577 | if (storeOp.storesTo(slot: ptrSlot)) |
| 578 | definingBlocks[user->getParentRegion()].insert(Ptr: user->getBlock()); |
| 579 | } |
| 580 | }; |
| 581 | collectStoringBlocks(slot.ptr, slot); |
| 582 | for (auto &[aliasPtr, aliasInfo] : info.aliasMap) |
| 583 | collectStoringBlocks(aliasPtr, aliasInfo.slot); |
| 584 | for (auto &[region, regionInfo] : info.regionsToPromote) |
| 585 | if (regionInfo.hasValueStores) |
| 586 | definingBlocks[region->getParentRegion()].insert( |
| 587 | Ptr: region->getParentOp()->getBlock()); |
| 588 | |
| 589 | // Then, compute blocks in which two or more definitions of the allocated |
| 590 | // variable may conflict. These blocks will need a new block argument to |
| 591 | // accommodate this. |
| 592 | for (auto &[region, defBlocks] : definingBlocks) |
| 593 | computeMergePoints(region, definingBlocks&: defBlocks, mergePoints&: info.mergePoints); |
| 594 | |
| 595 | // The slot can be promoted if the block arguments to be created can |
| 596 | // actually be populated with values, which may not be possible depending |
| 597 | // on their predecessors. |
| 598 | if (!areMergePointsUsable(mergePoints&: info.mergePoints)) |
| 599 | return {}; |
| 600 | |
| 601 | return info; |
| 602 | } |
| 603 | |
| 604 | Value MemorySlotPromoter::promoteInBlock(Block *block, Value reachingDef) { |
| 605 | SmallVector<Operation *> blockOps; |
| 606 | for (Operation &op : block->getOperations()) |
| 607 | blockOps.push_back(Elt: &op); |
| 608 | for (Operation *op : blockOps) { |
| 609 | // Promote operations that interact with the slot's memory. |
| 610 | if (auto memOp = dyn_cast<PromotableMemOpInterface>(Val: op)) { |
| 611 | if (info.userToBlockingUses[memOp->getParentRegion()].contains(Key: memOp)) |
| 612 | reachingDefs.insert(KV: {memOp, reachingDef}); |
| 613 | |
| 614 | MemorySlot aliasSlot = |
| 615 | getOpAliasSlot(op: memOp, rootSlot: slot, aliasMap: info.aliasMap).value_or(u&: slot); |
| 616 | if (memOp.storesTo(slot: aliasSlot)) { |
| 617 | // Ensures helper IR introduced by `getStored` is created before the |
| 618 | // storing op. This ensures the provided stored value dominates the |
| 619 | // store, allowing `visitReplacedValues` to safely create new uses |
| 620 | // after the store. |
| 621 | builder.setInsertionPoint(memOp); |
| 622 | // To not expose default value creation to the interfaces, if we have |
| 623 | // no reaching definition by now, we set it to the default value. |
| 624 | // This is slightly too eager as `getStored` may not need it. |
| 625 | if (!reachingDef) |
| 626 | reachingDef = getOrCreateDefaultValue(); |
| 627 | Value reachingDefAtStore = reachingDef; |
| 628 | if (slot.ptr != aliasSlot.ptr) { |
| 629 | // The store sees the slot at `aliasSlot.elemType`; project the |
| 630 | // reaching definition (at root elem type) before handing it to |
| 631 | // `getStored`. |
| 632 | reachingDefAtStore = convertSlotValueToAliasValue( |
| 633 | slotValue: reachingDef, aliasSlot, rootSlot: slot, aliasMap: info.aliasMap, builder); |
| 634 | assert(reachingDefAtStore && |
| 635 | "projectSlotValueToAliasValue contract violation" ); |
| 636 | } |
| 637 | Value stored = |
| 638 | memOp.getStored(slot: aliasSlot, builder, reachingDef: reachingDefAtStore, dataLayout); |
| 639 | assert(stored && "a memory operation storing to a slot must provide a " |
| 640 | "new definition of the slot" ); |
| 641 | // `replacedValuesMap` keeps `stored` at `aliasSlot.elemType` for |
| 642 | // `visitReplacedValues`; the new reaching definition is tracked at |
| 643 | // the root slot's elem type, so project `stored` back. |
| 644 | replacedValuesMap[memOp] = stored; |
| 645 | if (aliasSlot.ptr != slot.ptr) { |
| 646 | stored = convertAliasValueToSlotValue(aliasValue: stored, aliasSlot, rootReachingDef: reachingDef, |
| 647 | rootSlot: slot, aliasMap: info.aliasMap, builder); |
| 648 | assert(stored && "projectAliasValueToSlotValue contract violation" ); |
| 649 | } |
| 650 | reachingDef = stored; |
| 651 | } |
| 652 | } |
| 653 | |
| 654 | // Promote regions that contain operations that interact with the slot's |
| 655 | // memory. |
| 656 | if (auto promotableRegionOp = dyn_cast<PromotableRegionOpInterface>(Val: op)) { |
| 657 | bool needsPromotion = false; |
| 658 | bool hasValueStores = false; |
| 659 | for (Region ®ion : op->getRegions()) { |
| 660 | auto regionInfoIt = info.regionsToPromote.find(Val: ®ion); |
| 661 | if (regionInfoIt == info.regionsToPromote.end()) |
| 662 | continue; |
| 663 | needsPromotion = true; |
| 664 | if (!regionInfoIt->second.hasValueStores) |
| 665 | continue; |
| 666 | |
| 667 | hasValueStores = true; |
| 668 | break; |
| 669 | } |
| 670 | |
| 671 | if (needsPromotion) { |
| 672 | llvm::SmallMapVector<Region *, Value, 2> regionsToProcess; |
| 673 | |
| 674 | // To not expose default value creation to the interfaces, if we have |
| 675 | // no reaching definition by now, we set it to the default value. |
| 676 | // This is slightly too eager as `setupPromotion` may not need it. |
| 677 | if (!reachingDef) |
| 678 | reachingDef = getOrCreateDefaultValue(); |
| 679 | |
| 680 | promotableRegionOp.setupPromotion(slot, reachingDef, hasValueStores, |
| 681 | regionsToProcess); |
| 682 | |
| 683 | #ifndef NDEBUG |
| 684 | for (Region ®ion : op->getRegions()) |
| 685 | if (info.regionsToPromote.contains(®ion)) |
| 686 | assert( |
| 687 | regionsToProcess.contains(®ion) && |
| 688 | "reaching definition must be provided for a required region" ); |
| 689 | #endif // NDEBUG |
| 690 | |
| 691 | for (auto &[region, reachingDef] : regionsToProcess) { |
| 692 | assert(region->getParentOp() == op && |
| 693 | "region must be part of the operation" ); |
| 694 | if (!info.regionsToPromote.contains(Val: region)) |
| 695 | continue; |
| 696 | promoteInRegion(region, reachingDef); |
| 697 | } |
| 698 | |
| 699 | // TODO: Currently we have to invalidate the dominance information of |
| 700 | // the regions of the operation because finalizePromotion may move their |
| 701 | // content. We might want to support moving dominance information |
| 702 | // accross regions as this can be detected. |
| 703 | for (Region ®ion : op->getRegions()) |
| 704 | dominance.invalidate(region: ®ion); |
| 705 | |
| 706 | builder.setInsertionPointAfter(op); |
| 707 | reachingDef = promotableRegionOp.finalizePromotion( |
| 708 | slot, entryReachingDef: reachingDef, hasValueStores, reachingAtBlockEnd, builder); |
| 709 | } |
| 710 | } |
| 711 | } |
| 712 | |
| 713 | reachingAtBlockEnd[block] = reachingDef; |
| 714 | return reachingDef; |
| 715 | } |
| 716 | |
| 717 | void MemorySlotPromoter::promoteInRegion(Region *region, Value reachingDef) { |
| 718 | if (region->hasOneBlock()) { |
| 719 | promoteInBlock(block: ®ion->front(), reachingDef); |
| 720 | regionsInPostOrder.push_back(Elt: region); |
| 721 | return; |
| 722 | } |
| 723 | |
| 724 | struct DfsJob { |
| 725 | llvm::DomTreeNodeBase<Block> *block; |
| 726 | Value reachingDef; |
| 727 | }; |
| 728 | |
| 729 | SmallVector<DfsJob> dfsStack; |
| 730 | |
| 731 | auto &domTree = dominance.getDomTree(region); |
| 732 | |
| 733 | dfsStack.emplace_back<DfsJob>( |
| 734 | Args: {.block: domTree.getNode(BB: ®ion->front()), .reachingDef: reachingDef}); |
| 735 | |
| 736 | while (!dfsStack.empty()) { |
| 737 | DfsJob job = dfsStack.pop_back_val(); |
| 738 | Block *block = job.block->getBlock(); |
| 739 | |
| 740 | if (info.mergePoints.contains(Ptr: block)) { |
| 741 | BlockArgument blockArgument = |
| 742 | block->addArgument(type: slot.valueType, loc: slot.ptr.getLoc()); |
| 743 | job.reachingDef = blockArgument; |
| 744 | } |
| 745 | |
| 746 | job.reachingDef = promoteInBlock(block, reachingDef: job.reachingDef); |
| 747 | |
| 748 | if (auto terminator = dyn_cast<BranchOpInterface>(Val: block->getTerminator())) { |
| 749 | for (BlockOperand &blockOperand : terminator->getBlockOperands()) { |
| 750 | if (info.mergePoints.contains(Ptr: blockOperand.get())) { |
| 751 | if (!job.reachingDef) |
| 752 | job.reachingDef = getOrCreateDefaultValue(); |
| 753 | |
| 754 | terminator.getSuccessorOperands(index: blockOperand.getOperandNumber()) |
| 755 | .append(valueRange: job.reachingDef); |
| 756 | } |
| 757 | } |
| 758 | } |
| 759 | |
| 760 | for (auto *child : job.block->children()) |
| 761 | dfsStack.emplace_back<DfsJob>(Args: {.block: child, .reachingDef: job.reachingDef}); |
| 762 | } |
| 763 | |
| 764 | // Record this region after its (and any nested) promotion has completed, |
| 765 | // so that `regionsInPostOrder` lists inner regions before their enclosing |
| 766 | // regions. |
| 767 | regionsInPostOrder.push_back(Elt: region); |
| 768 | } |
| 769 | |
| 770 | /// Gets or creates a block index mapping for the region of which the entry |
| 771 | /// block is `regionEntryBlock`. |
| 772 | static const DenseMap<Block *, size_t> & |
| 773 | getOrCreateBlockIndices(BlockIndexCache &blockIndexCache, |
| 774 | Block *regionEntryBlock) { |
| 775 | auto [it, inserted] = blockIndexCache.try_emplace(Key: regionEntryBlock); |
| 776 | if (!inserted) |
| 777 | return it->second; |
| 778 | |
| 779 | DenseMap<Block *, size_t> &blockIndices = it->second; |
| 780 | SetVector<Block *> topologicalOrder = |
| 781 | getBlocksSortedByDominance(region&: *regionEntryBlock->getParent()); |
| 782 | for (auto [index, block] : llvm::enumerate(First&: topologicalOrder)) |
| 783 | blockIndices[block] = index; |
| 784 | return blockIndices; |
| 785 | } |
| 786 | |
| 787 | /// Sorts `ops` according to dominance. Relies on the topological order of basic |
| 788 | /// blocks to get a deterministic ordering. Uses `blockIndexCache` to avoid the |
| 789 | /// potentially expensive recomputation of a block index map. |
| 790 | /// This function assumes no blocks are ever deleted or entry block changed |
| 791 | /// during the lifetime of the block index cache. |
| 792 | static void dominanceSort(SmallVector<Operation *> &ops, Region ®ion, |
| 793 | BlockIndexCache &blockIndexCache) { |
| 794 | if (region.empty()) |
| 795 | return; |
| 796 | |
| 797 | // Produce a topological block order and construct a map to lookup the indices |
| 798 | // of blocks. |
| 799 | const DenseMap<Block *, size_t> &topoBlockIndices = |
| 800 | getOrCreateBlockIndices(blockIndexCache, regionEntryBlock: ®ion.front()); |
| 801 | |
| 802 | // Combining the topological order of the basic blocks together with block |
| 803 | // internal operation order guarantees a deterministic, dominance respecting |
| 804 | // order. |
| 805 | llvm::sort(C&: ops, Comp: [&](Operation *lhs, Operation *rhs) { |
| 806 | size_t lhsBlockIndex = topoBlockIndices.at(Val: lhs->getBlock()); |
| 807 | size_t rhsBlockIndex = topoBlockIndices.at(Val: rhs->getBlock()); |
| 808 | if (lhsBlockIndex == rhsBlockIndex) |
| 809 | return lhs->isBeforeInBlock(other: rhs); |
| 810 | return lhsBlockIndex < rhsBlockIndex; |
| 811 | }); |
| 812 | } |
| 813 | |
| 814 | void MemorySlotPromoter::removeBlockingUses(Region *region) { |
| 815 | auto *blockingUsesMapIt = info.userToBlockingUses.find(Key: region); |
| 816 | if (blockingUsesMapIt == info.userToBlockingUses.end()) |
| 817 | return; |
| 818 | BlockingUsesMap &blockingUsesMap = blockingUsesMapIt->second; |
| 819 | if (blockingUsesMap.empty()) |
| 820 | return; |
| 821 | |
| 822 | // Operations may have been moved to a different region at this point. |
| 823 | // To cover this, we process the current region of an operation to remove |
| 824 | // instead of the provided region. |
| 825 | region = blockingUsesMap.front().first->getParentRegion(); |
| 826 | #ifndef NDEBUG |
| 827 | for (auto &[op, blockingUses] : blockingUsesMap) |
| 828 | assert(op->getParentRegion() == region && |
| 829 | "all operations must still be in the same region" ); |
| 830 | #endif // NDEBUG |
| 831 | |
| 832 | llvm::SmallVector<Operation *> usersToRemoveUses( |
| 833 | llvm::make_first_range(c&: blockingUsesMap)); |
| 834 | |
| 835 | // Sort according to dominance. |
| 836 | dominanceSort(ops&: usersToRemoveUses, region&: *region, blockIndexCache); |
| 837 | |
| 838 | // Iterate over the operations to rewrite in reverse dominance order. |
| 839 | for (Operation *toPromote : llvm::reverse(C&: usersToRemoveUses)) { |
| 840 | if (auto toPromoteMemOp = dyn_cast<PromotableMemOpInterface>(Val: toPromote)) { |
| 841 | Value reachingDef = reachingDefs.lookup(Val: toPromoteMemOp); |
| 842 | // If no reaching definition is known, this use is outside the reach of |
| 843 | // the slot. The default value should thus be used. |
| 844 | // FIXME: This is too eager, and will generate default values even for |
| 845 | // pure stores. This cannot be removed easily as partial stores may |
| 846 | // still require a default value to complete. |
| 847 | if (!reachingDef) |
| 848 | reachingDef = getOrCreateDefaultValue(); |
| 849 | |
| 850 | builder.setInsertionPointAfter(toPromote); |
| 851 | MemorySlot aliasSlot = |
| 852 | getOpAliasSlot(op: toPromote, rootSlot: slot, aliasMap: info.aliasMap).value_or(u&: slot); |
| 853 | Value reachingDefAtBlockingUse = reachingDef; |
| 854 | if (aliasSlot.ptr != slot.ptr) { |
| 855 | // Project the reaching definition to `aliasSlot.elemType` to match |
| 856 | // what `toPromoteMemOp` sees. |
| 857 | reachingDefAtBlockingUse = convertSlotValueToAliasValue( |
| 858 | slotValue: reachingDef, aliasSlot, rootSlot: slot, aliasMap: info.aliasMap, builder); |
| 859 | assert(reachingDefAtBlockingUse && |
| 860 | "projectSlotValueToAliasValue contract violation" ); |
| 861 | } |
| 862 | if (toPromoteMemOp.removeBlockingUses( |
| 863 | slot: aliasSlot, blockingUses: blockingUsesMap[toPromote], builder, |
| 864 | reachingDefinition: reachingDefAtBlockingUse, dataLayout) == DeletionKind::Delete) |
| 865 | toErase.insert(X: toPromote); |
| 866 | continue; |
| 867 | } |
| 868 | |
| 869 | auto toPromoteBasic = cast<PromotableOpInterface>(Val: toPromote); |
| 870 | builder.setInsertionPointAfter(toPromote); |
| 871 | if (toPromoteBasic.removeBlockingUses(blockingUses: blockingUsesMap[toPromote], |
| 872 | builder) == DeletionKind::Delete) |
| 873 | toErase.insert(X: toPromote); |
| 874 | } |
| 875 | } |
| 876 | |
| 877 | void MemorySlotPromoter::visitReplacedValuesForRegion( |
| 878 | Region *region, ArrayRef<std::pair<Operation *, Value>> replacedValues) { |
| 879 | auto *blockingUsesMapIt = info.userToBlockingUses.find(Key: region); |
| 880 | if (blockingUsesMapIt == info.userToBlockingUses.end()) |
| 881 | return; |
| 882 | BlockingUsesMap &blockingUsesMap = blockingUsesMapIt->second; |
| 883 | if (blockingUsesMap.empty()) |
| 884 | return; |
| 885 | |
| 886 | for (auto &[op, _] : blockingUsesMap) { |
| 887 | auto toVisit = dyn_cast<PromotableOpInterface>(Val: op); |
| 888 | if (!toVisit || !toVisit.requiresReplacedValues()) |
| 889 | continue; |
| 890 | builder.setInsertionPointAfter(op); |
| 891 | toVisit.visitReplacedValues(mutatedDefs: replacedValues, builder); |
| 892 | } |
| 893 | } |
| 894 | |
| 895 | void MemorySlotPromoter::removeUnusedItems() { |
| 896 | // We want to eliminate unused block arguments. Because block arguments can be |
| 897 | // used to populate other block arguments, there might be cycles of arguments |
| 898 | // that are only used to populate each-other. We therefore need a small |
| 899 | // dataflow analysis to identify which block arguments are truly used. |
| 900 | |
| 901 | SmallPtrSet<BlockArgument, 8> mergePointArgsUnused; |
| 902 | SmallVector<BlockArgument> usedMergePointArgsToProcess; |
| 903 | |
| 904 | // First, separate the block arguments that are not used or only used for the |
| 905 | // purpose of populating a merge point block argument from the others. These |
| 906 | // block arguments are potentially unused. Meanwhile, arguments that are |
| 907 | // definitely used will be the starting point of the propagation of the |
| 908 | // analysis. |
| 909 | auto isDefinitelyUsed = [&](BlockArgument arg) { |
| 910 | for (auto &use : arg.getUses()) { |
| 911 | if (llvm::is_contained(Range&: toErase, Element: use.getOwner())) |
| 912 | continue; |
| 913 | |
| 914 | // We now want to detect whether the use is to populate a merge point |
| 915 | // block argument. If it is not, the argument is definitely used. |
| 916 | |
| 917 | auto branchOp = dyn_cast<BranchOpInterface>(Val: use.getOwner()); |
| 918 | if (!branchOp) |
| 919 | return true; |
| 920 | |
| 921 | std::optional<BlockArgument> successorArgument = |
| 922 | branchOp.getSuccessorBlockArgument(operandIndex: use.getOperandNumber()); |
| 923 | if (!successorArgument) |
| 924 | return true; |
| 925 | |
| 926 | if (!info.mergePoints.contains(Ptr: successorArgument->getOwner())) |
| 927 | return true; |
| 928 | |
| 929 | // The last block argument of a merge point is its reaching definition |
| 930 | // argument. If the argument being populated is not the last one, it is a |
| 931 | // genuine use of the value. |
| 932 | bool isLastBlockArgument = |
| 933 | successorArgument->getArgNumber() == |
| 934 | successorArgument->getOwner()->getNumArguments() - 1; |
| 935 | if (!isLastBlockArgument) |
| 936 | return true; |
| 937 | } |
| 938 | return false; |
| 939 | }; |
| 940 | |
| 941 | for (Block *mergePoint : info.mergePoints) { |
| 942 | BlockArgument arg = mergePoint->getArguments().back(); |
| 943 | if (isDefinitelyUsed(arg)) |
| 944 | usedMergePointArgsToProcess.push_back(Elt: arg); |
| 945 | else |
| 946 | mergePointArgsUnused.insert(Ptr: arg); |
| 947 | } |
| 948 | |
| 949 | // We now refine mergePointArgsUnused from the information of which block |
| 950 | // arguments are definitely used. |
| 951 | while (!usedMergePointArgsToProcess.empty()) { |
| 952 | BlockArgument arg = usedMergePointArgsToProcess.pop_back_val(); |
| 953 | Block *mergePoint = arg.getOwner(); |
| 954 | |
| 955 | assert(arg.getArgNumber() == mergePoint->getNumArguments() - 1 && |
| 956 | "merge point argument must be the last argument of the merge point" ); |
| 957 | |
| 958 | for (BlockOperand &use : mergePoint->getUses()) { |
| 959 | // If a value used to populate this used merge point argument is another |
| 960 | // merge point block argument that is currently considered unused, it must |
| 961 | // now be considered used and processed as such later. |
| 962 | |
| 963 | auto branch = cast<BranchOpInterface>(Val: use.getOwner()); |
| 964 | SuccessorOperands succOperands = |
| 965 | branch.getSuccessorOperands(index: use.getOperandNumber()); |
| 966 | |
| 967 | // The successor operand is either the last one or is not present if the |
| 968 | // user block is dead. |
| 969 | assert(succOperands.size() == mergePoint->getNumArguments() || |
| 970 | succOperands.size() + 1 == mergePoint->getNumArguments()); |
| 971 | |
| 972 | // If the user block is dead, the default value acts as a placeholder |
| 973 | // dummy value. |
| 974 | if (succOperands.size() + 1 == mergePoint->getNumArguments()) |
| 975 | succOperands.append(valueRange: getOrCreateDefaultValue()); |
| 976 | |
| 977 | Value populatedValue = succOperands[arg.getArgNumber()]; |
| 978 | auto populatedValueAsArg = dyn_cast<BlockArgument>(Val&: populatedValue); |
| 979 | if (populatedValueAsArg && |
| 980 | mergePointArgsUnused.erase(Ptr: populatedValueAsArg)) |
| 981 | usedMergePointArgsToProcess.push_back(Elt: populatedValueAsArg); |
| 982 | } |
| 983 | |
| 984 | builder.setInsertionPointToStart(mergePoint); |
| 985 | allocator.handleBlockArgument(slot, argument: arg, builder); |
| 986 | if (statistics.newBlockArgumentAmount) |
| 987 | (*statistics.newBlockArgumentAmount)++; |
| 988 | } |
| 989 | |
| 990 | for (Operation *toEraseOp : toErase) |
| 991 | toEraseOp->erase(); |
| 992 | |
| 993 | // First, erase all successor operands that feed into unused merge point |
| 994 | // block arguments. This must be done before erasing the block arguments |
| 995 | // themselves because an unused merge point argument may be used to |
| 996 | // populate another unused merge point argument via a branch operation. |
| 997 | for (BlockArgument arg : mergePointArgsUnused) { |
| 998 | Block *mergePoint = arg.getOwner(); |
| 999 | for (BlockOperand &use : mergePoint->getUses()) { |
| 1000 | auto branch = cast<BranchOpInterface>(Val: use.getOwner()); |
| 1001 | SuccessorOperands succOperands = |
| 1002 | branch.getSuccessorOperands(index: use.getOperandNumber()); |
| 1003 | // A dead predecessor's branch carries no operand for this merge point: |
| 1004 | // operands are appended during the dominator-tree walk, which dead |
| 1005 | // blocks are not part of, and only the used-argument path above appends |
| 1006 | // a placeholder to such branches, so there is nothing to erase. |
| 1007 | assert(succOperands.size() == mergePoint->getNumArguments() || |
| 1008 | succOperands.size() + 1 == mergePoint->getNumArguments()); |
| 1009 | if (succOperands.size() == mergePoint->getNumArguments()) |
| 1010 | succOperands.erase(subStart: arg.getArgNumber()); |
| 1011 | } |
| 1012 | } |
| 1013 | |
| 1014 | // Now that all successor operands feeding unused args have been removed, |
| 1015 | // erase the block arguments themselves. |
| 1016 | for (BlockArgument arg : mergePointArgsUnused) { |
| 1017 | Block *mergePoint = arg.getOwner(); |
| 1018 | mergePoint->eraseArgument(index: mergePoint->getNumArguments() - 1); |
| 1019 | } |
| 1020 | } |
| 1021 | |
| 1022 | std::optional<PromotableAllocationOpInterface> |
| 1023 | MemorySlotPromoter::promoteSlot() { |
| 1024 | // Step 1: perform the promotion recursively through nested regions. The |
| 1025 | // reaching definition starts with a null value that will be replaced by a |
| 1026 | // lazily-created default value if the value must be passed to a promotion |
| 1027 | // interface while no store has been encountered yet. |
| 1028 | // Blocking uses are not removed yet. |
| 1029 | promoteInRegion(region: slot.ptr.getParentRegion(), reachingDef: nullptr); |
| 1030 | |
| 1031 | // Step 2: call `visitReplacedValues` on operations that requested it. |
| 1032 | if (info.needsAnyReplacedValuesVisit) { |
| 1033 | SmallVector<std::pair<Operation *, Value>> replacedValues; |
| 1034 | replacedValues.reserve(N: replacedValuesMap.size()); |
| 1035 | for (const auto &[memOp, value] : replacedValuesMap) |
| 1036 | if (value) |
| 1037 | replacedValues.push_back(Elt: {memOp, value}); |
| 1038 | for (Region *region : regionsInPostOrder) |
| 1039 | visitReplacedValuesForRegion(region, replacedValues); |
| 1040 | } |
| 1041 | |
| 1042 | // Step 3: remove the slot's blocking uses across all regions. Iterating |
| 1043 | // in through the regions in same order as promoteInRegion. |
| 1044 | for (Region *region : regionsInPostOrder) |
| 1045 | removeBlockingUses(region); |
| 1046 | |
| 1047 | // Finally, remove unused operations and merge point block arguments. |
| 1048 | removeUnusedItems(); |
| 1049 | |
| 1050 | assert(slot.ptr.use_empty() && |
| 1051 | "after promotion, the slot pointer should not be used anymore" ); |
| 1052 | |
| 1053 | LDBG() << "Promoted memory slot: " << slot.ptr; |
| 1054 | |
| 1055 | if (statistics.promotedAmount) |
| 1056 | (*statistics.promotedAmount)++; |
| 1057 | |
| 1058 | return allocator.handlePromotionComplete(slot, defaultValue, builder); |
| 1059 | } |
| 1060 | |
| 1061 | LogicalResult mlir::tryToPromoteMemorySlots( |
| 1062 | ArrayRef<PromotableAllocationOpInterface> allocators, OpBuilder &builder, |
| 1063 | const DataLayout &dataLayout, DominanceInfo &dominance, |
| 1064 | Mem2RegStatistics statistics) { |
| 1065 | bool promotedAny = false; |
| 1066 | |
| 1067 | // A cache that stores deterministic block indices which are used to determine |
| 1068 | // a valid operation modification order. The block index maps are computed |
| 1069 | // lazily and cached to avoid expensive recomputation. |
| 1070 | BlockIndexCache blockIndexCache; |
| 1071 | |
| 1072 | SmallVector<PromotableAllocationOpInterface> workList(allocators); |
| 1073 | |
| 1074 | SmallVector<PromotableAllocationOpInterface> newWorkList; |
| 1075 | newWorkList.reserve(N: workList.size()); |
| 1076 | while (true) { |
| 1077 | bool changesInThisRound = false; |
| 1078 | for (PromotableAllocationOpInterface allocator : workList) { |
| 1079 | bool changedAllocator = false; |
| 1080 | for (MemorySlot slot : allocator.getPromotableSlots()) { |
| 1081 | if (slot.ptr.use_empty()) |
| 1082 | continue; |
| 1083 | |
| 1084 | MemorySlotPromotionAnalyzer analyzer(slot, dominance, dataLayout); |
| 1085 | std::optional<MemorySlotPromotionInfo> info = analyzer.computeInfo(); |
| 1086 | if (info) { |
| 1087 | std::optional<PromotableAllocationOpInterface> newAllocator = |
| 1088 | MemorySlotPromoter(slot, allocator, builder, dominance, |
| 1089 | dataLayout, std::move(*info), statistics, |
| 1090 | blockIndexCache) |
| 1091 | .promoteSlot(); |
| 1092 | changedAllocator = true; |
| 1093 | // Add newly created allocators to the worklist for further |
| 1094 | // processing. |
| 1095 | if (newAllocator) |
| 1096 | newWorkList.push_back(Elt: *newAllocator); |
| 1097 | |
| 1098 | // A break is required, since promoting a slot may invalidate the |
| 1099 | // remaining slots of an allocator. |
| 1100 | break; |
| 1101 | } |
| 1102 | } |
| 1103 | if (!changedAllocator) |
| 1104 | newWorkList.push_back(Elt: allocator); |
| 1105 | changesInThisRound |= changedAllocator; |
| 1106 | } |
| 1107 | if (!changesInThisRound) |
| 1108 | break; |
| 1109 | promotedAny = true; |
| 1110 | |
| 1111 | // Swap the vector's backing memory and clear the entries in newWorkList |
| 1112 | // afterwards. This ensures that additional heap allocations can be avoided. |
| 1113 | workList.swap(RHS&: newWorkList); |
| 1114 | newWorkList.clear(); |
| 1115 | } |
| 1116 | |
| 1117 | return success(IsSuccess: promotedAny); |
| 1118 | } |
| 1119 | |
| 1120 | namespace { |
| 1121 | |
| 1122 | struct Mem2Reg : impl::Mem2RegBase<Mem2Reg> { |
| 1123 | using impl::Mem2RegBase<Mem2Reg>::Mem2RegBase; |
| 1124 | |
| 1125 | void runOnOperation() override { |
| 1126 | Operation *scopeOp = getOperation(); |
| 1127 | |
| 1128 | Mem2RegStatistics statistics{.promotedAmount: &promotedAmount, .newBlockArgumentAmount: &newBlockArgumentAmount}; |
| 1129 | |
| 1130 | bool changed = false; |
| 1131 | |
| 1132 | auto &dataLayoutAnalysis = getAnalysis<DataLayoutAnalysis>(); |
| 1133 | const DataLayout &dataLayout = dataLayoutAnalysis.getAtOrAbove(operation: scopeOp); |
| 1134 | auto &dominance = getAnalysis<DominanceInfo>(); |
| 1135 | |
| 1136 | for (Region ®ion : scopeOp->getRegions()) { |
| 1137 | if (region.getBlocks().empty()) |
| 1138 | continue; |
| 1139 | |
| 1140 | OpBuilder builder(®ion.front(), region.front().begin()); |
| 1141 | |
| 1142 | SmallVector<PromotableAllocationOpInterface> allocators; |
| 1143 | // Build a list of allocators to attempt to promote the slots of. |
| 1144 | region.walk(callback: [&](PromotableAllocationOpInterface allocator) { |
| 1145 | allocators.emplace_back(Args&: allocator); |
| 1146 | }); |
| 1147 | |
| 1148 | // Attempt promoting as many of the slots as possible. |
| 1149 | if (succeeded(Result: tryToPromoteMemorySlots(allocators, builder, dataLayout, |
| 1150 | dominance, statistics))) |
| 1151 | changed = true; |
| 1152 | } |
| 1153 | if (!changed) |
| 1154 | markAllAnalysesPreserved(); |
| 1155 | } |
| 1156 | }; |
| 1157 | |
| 1158 | } // namespace |
| 1159 | |