MLIR 24.0.0git
MemorySlotInterfaces.cpp
Go to the documentation of this file.
1//===-- MemorySlotInterfaces.cpp - MemorySlot interfaces --------*- 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
10
11#include "llvm/ADT/SmallVector.h"
12
13#include "mlir/Interfaces/MemorySlotOpInterfaces.cpp.inc"
14#include "mlir/Interfaces/MemorySlotTypeInterfaces.cpp.inc"
15
16using namespace mlir;
17
18/// Returns the slot describing `aliasPtr`: `rootSlot` if it is the root,
19/// the entry in `aliasMap` if it's a known alias, or `nullopt` otherwise.
20static std::optional<MemorySlot>
21getParentSlot(Value aliasPtr, const MemorySlot &rootSlot,
22 const PromotableAliasMap &aliasMap) {
23 if (aliasPtr == rootSlot.ptr)
24 return rootSlot;
25 auto it = aliasMap.find(aliasPtr);
26 if (it == aliasMap.end())
27 return std::nullopt;
28 return it->second.slot;
29}
30
31void mlir::populatePromotableAliasMap(PromotableAliaserInterface aliaser,
32 const MemorySlot &rootSlot,
33 PromotableAliasMap &aliasMap) {
34 for (OpOperand &operand : aliaser->getOpOperands()) {
35 std::optional<MemorySlot> parentSlot =
36 getParentSlot(operand.get(), rootSlot, aliasMap);
37 if (!parentSlot)
38 continue;
40 aliaser.getPromotableSlotAliases(operand, *parentSlot, newSlots);
41 for (const MemorySlot &alias : newSlots)
42 aliasMap.try_emplace(alias.ptr, PromotableSlotAliasInfo{alias, &operand});
43 }
44}
45
46std::optional<MemorySlot>
48 const PromotableAliasMap &aliasMap) {
49 // An op owning its wrapped blocking uses (e.g., `vector.mask`) reaches the
50 // slot only through the wrapped operation, so inspect that one instead.
51 if (auto memOp = dyn_cast<PromotableMemOpInterface>(op);
52 memOp && memOp.ownsWrappedBlockingUses()) {
53 assert(op->getNumRegions() == 1 && op->getRegion(0).hasOneBlock() &&
54 op->getRegion(0).front().getOperations().size() == 2 &&
55 isa<PromotableMemOpInterface>(op->getRegion(0).front().front()) &&
56 "an op owning wrapped blocking uses must have one single-block "
57 "region holding a wrapped PromotableMemOpInterface op and a "
58 "terminator");
59 op = &op->getRegion(0).front().front();
60 }
61
62 for (Value operand : op->getOperands())
63 if (std::optional<MemorySlot> slot =
64 getParentSlot(operand, rootSlot, aliasMap))
65 return slot;
66 return std::nullopt;
67}
68
70 const MemorySlot &rootSlot,
71 const PromotableAliasMap &aliasMap) {
72 // As in `getOpAliasSlot`, inspect the wrapped operation instead.
73 if (auto memOp = dyn_cast<PromotableMemOpInterface>(op);
74 memOp && memOp.ownsWrappedBlockingUses()) {
75 assert(op->getNumRegions() == 1 && op->getRegion(0).hasOneBlock() &&
76 op->getRegion(0).front().getOperations().size() == 2 &&
77 isa<PromotableMemOpInterface>(op->getRegion(0).front().front()) &&
78 "an op owning wrapped blocking uses must have one single-block "
79 "region holding a wrapped PromotableMemOpInterface op and a "
80 "terminator");
81 op = &op->getRegion(0).front().front();
82 }
83
84 Value uniqueAliasPtr;
85 for (Value operand : op->getOperands()) {
86 std::optional<MemorySlot> slot = getParentSlot(operand, rootSlot, aliasMap);
87 if (!slot)
88 continue;
89 if (uniqueAliasPtr && uniqueAliasPtr != slot->ptr)
90 return false;
91 uniqueAliasPtr = slot->ptr;
92 }
93 return true;
94}
95
96namespace {
97/// A step in an alias chain, from leaf to root. `parentSlot` is one step
98/// closer to the root; `aliasSlot` is the slot exposed at this step.
99struct ChainStep {
100 PromotableAliaserInterface aliaser;
101 OpOperand *aliasedSlotPointerOperand;
102 MemorySlot parentSlot;
103 MemorySlot aliasSlot;
104};
105} // namespace
106
107/// Walks from `aliasSlot` back to `rootSlot` via `aliasMap`. Returns the
108/// leaf-to-root chain, or `nullopt` if `aliasSlot` is not a known alias.
109static std::optional<SmallVector<ChainStep>>
110buildAliasChain(const MemorySlot &aliasSlot, const MemorySlot &rootSlot,
111 const PromotableAliasMap &aliasMap) {
113 Value current = aliasSlot.ptr;
114 while (current != rootSlot.ptr) {
115 auto it = aliasMap.find(current);
116 if (it == aliasMap.end())
117 return std::nullopt;
118 OpOperand *operand = it->second.aliasedSlotPointerOperand;
119 auto aliaser = cast<PromotableAliaserInterface>(operand->getOwner());
120 std::optional<MemorySlot> parent =
121 getParentSlot(operand->get(), rootSlot, aliasMap);
122 if (!parent)
123 return std::nullopt;
124 chain.push_back(ChainStep{aliaser, operand, *parent, it->second.slot});
125 current = operand->get();
126 }
127 return chain;
128}
129
131 const MemorySlot &aliasSlot,
132 const MemorySlot &rootSlot,
133 const PromotableAliasMap &aliasMap,
134 OpBuilder &builder) {
135 std::optional<SmallVector<ChainStep>> chain =
136 buildAliasChain(aliasSlot, rootSlot, aliasMap);
137 if (!chain)
138 return {};
139 Value current = slotValue;
140 // Root-to-leaf walk: reverse the leaf-first chain.
141 for (ChainStep &step : llvm::reverse(*chain)) {
142 current = step.aliaser.projectSlotValueToAliasValue(
143 *step.aliasedSlotPointerOperand, step.parentSlot, step.aliasSlot,
144 current, builder);
145 if (!current)
146 return {};
147 }
148 return current;
149}
150
152 const MemorySlot &aliasSlot,
153 Value rootReachingDef,
154 const MemorySlot &rootSlot,
155 const PromotableAliasMap &aliasMap,
156 OpBuilder &builder) {
157 std::optional<SmallVector<ChainStep>> chainOpt =
158 buildAliasChain(aliasSlot, rootSlot, aliasMap);
159 if (!chainOpt)
160 return {};
161 SmallVector<ChainStep> &chain = *chainOpt;
162
163 // Project `rootReachingDef` down to each step's parent level so the
164 // per-step projector can use it (needed for partial sub-aliases; full
165 // aliases ignore it). The chain is leaf-first, so `chain.back()` is the
166 // root-most step (parent = rootSlot) and `chain.front()` is the leaf.
167 SmallVector<Value> perStepReachingDef(chain.size());
168 Value current = rootReachingDef;
169 for (int i = static_cast<int>(chain.size()) - 1; i >= 0; --i) {
170 perStepReachingDef[i] = current;
171 current = chain[i].aliaser.projectSlotValueToAliasValue(
172 *chain[i].aliasedSlotPointerOperand, chain[i].parentSlot,
173 chain[i].aliasSlot, current, builder);
174 if (!current)
175 return {};
176 }
177
178 // Walk leaf-to-root, combining `aliasValue` with the projected reaching
179 // definition at each step.
180 current = aliasValue;
181 for (size_t i = 0; i < chain.size(); ++i) {
182 current = chain[i].aliaser.projectAliasValueToSlotValue(
183 *chain[i].aliasedSlotPointerOperand, chain[i].parentSlot,
184 chain[i].aliasSlot, current, perStepReachingDef[i], builder);
185 if (!current)
186 return {};
187 }
188 return current;
189}
static std::optional< MemorySlot > getParentSlot(Value aliasPtr, const MemorySlot &rootSlot, const PromotableAliasMap &aliasMap)
Returns the slot describing aliasPtr: rootSlot if it is the root, the entry in aliasMap if it's a kno...
static std::optional< SmallVector< ChainStep > > buildAliasChain(const MemorySlot &aliasSlot, const MemorySlot &rootSlot, const PromotableAliasMap &aliasMap)
Walks from aliasSlot back to rootSlot via aliasMap.
OpListType & getOperations()
Definition Block.h:162
Operation & front()
Definition Block.h:178
IRValueT get() const
Return the current value being used by this operand.
This class helps build Operations.
Definition Builders.h:210
This class represents an operand of an operation.
Definition Value.h:256
Operation is the basic unit of execution within MLIR.
Definition Operation.h:87
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
Definition Operation.h:740
unsigned getNumRegions()
Returns the number of regions held by this operation.
Definition Operation.h:728
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition Operation.h:405
Block & front()
Definition Region.h:65
bool hasOneBlock()
Return true if this region has exactly one block.
Definition Region.h:68
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition Value.h:96
Operation * getOwner() const
Return the owner of this operand.
Definition UseDefLists.h:38
Include the generated interface declarations.
bool referencesAtMostOneAliasOfSlot(Operation *op, const MemorySlot &rootSlot, const PromotableAliasMap &aliasMap)
Returns true if op's operands reach rootSlot through at most one distinct alias pointer (the root its...
Value convertSlotValueToAliasValue(Value slotValue, const MemorySlot &aliasSlot, const MemorySlot &rootSlot, const PromotableAliasMap &aliasMap, OpBuilder &builder)
Walks the alias chain from rootSlot down to aliasSlot.
void populatePromotableAliasMap(PromotableAliaserInterface aliaser, const MemorySlot &rootSlot, PromotableAliasMap &aliasMap)
Populates aliasMap with alias entries produced by aliaser for operands that already alias rootSlot.
Value convertAliasValueToSlotValue(Value aliasValue, const MemorySlot &aliasSlot, Value rootReachingDef, const MemorySlot &rootSlot, const PromotableAliasMap &aliasMap, OpBuilder &builder)
Walks the alias chain from aliasSlot back up to rootSlot.
llvm::SmallDenseMap< Value, PromotableSlotAliasInfo, 4 > PromotableAliasMap
Maps an alias slot pointer (a result of a PromotableAliaserInterface op) reachable from a root slot t...
std::optional< MemorySlot > getOpAliasSlot(Operation *op, const MemorySlot &rootSlot, const PromotableAliasMap &aliasMap)
Returns a MemorySlot for the operand of op that aliases rootSlot.ptr (either the root itself or a kno...
Represents a slot in memory.
Value ptr
Pointer to the memory slot, used by operations to refer to it.
An entry in a PromotableAliasMap: the memory slot defined by an aliaser operation and its source oper...