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
26namespace mlir {
27#define GEN_PASS_DEF_MEM2REG
28#include "mlir/Transforms/Passes.h.inc"
29} // namespace mlir
30
31#define DEBUG_TYPE "mem2reg"
32
33using 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
132namespace {
133
134using BlockingUsesMap =
135 llvm::MapVector<Operation *, SmallPtrSet<OpOperand *, 4>>;
136using RegionBlockingUsesMap =
137 llvm::SmallMapVector<Region *, BlockingUsesMap, 2>;
138
139using RegionSet = SmallPtrSet<Region *, 32>;
140
141/// Information about regions that will be traversed for promotion, computed
142/// during promotion analysis.
143struct 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.
150struct 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.
174class MemorySlotPromotionAnalyzer {
175public:
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
184private:
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> &regionsToPromote,
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.
226using 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.
231class MemorySlotPromoter {
232public:
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
246private:
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
328MemorySlotPromoter::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
349Value 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.
360static Operation *getBlockingUseOwner(Operation *op) {
361 auto memOp = dyn_cast_or_null<PromotableMemOpInterface>(Val: op->getParentOp());
362 return memOp && memOp.ownsWrappedBlockingUses() ? memOp : op;
363}
364
365LogicalResult MemorySlotPromotionAnalyzer::computeBlockingUses(
366 RegionBlockingUsesMap &userToBlockingUses,
367 DenseMap<Region *, RegionPromotionInfo> &regionsToPromote,
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 *> &regionsToPropagateFrom,
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 &regionInfo = 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
523using IDFCalculator = llvm::IDFCalculatorBase<Block, false>;
524void 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
539bool 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
549std::optional<MemorySlotPromotionInfo>
550MemorySlotPromotionAnalyzer::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
604Value 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 &region : op->getRegions()) {
660 auto regionInfoIt = info.regionsToPromote.find(Val: &region);
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 &region : op->getRegions())
685 if (info.regionsToPromote.contains(&region))
686 assert(
687 regionsToProcess.contains(&region) &&
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 &region : op->getRegions())
704 dominance.invalidate(region: &region);
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
717void MemorySlotPromoter::promoteInRegion(Region *region, Value reachingDef) {
718 if (region->hasOneBlock()) {
719 promoteInBlock(block: &region->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: &region->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`.
772static const DenseMap<Block *, size_t> &
773getOrCreateBlockIndices(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.
792static void dominanceSort(SmallVector<Operation *> &ops, Region &region,
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: &region.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
814void 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
877void 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
895void 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
1022std::optional<PromotableAllocationOpInterface>
1023MemorySlotPromoter::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
1061LogicalResult 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
1120namespace {
1121
1122struct 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 &region : scopeOp->getRegions()) {
1137 if (region.getBlocks().empty())
1138 continue;
1139
1140 OpBuilder builder(&region.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