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
9#include "mlir/Interfaces/MemorySlotInterfaces.h"
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(Val: 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(aliasPtr: operand.get(), rootSlot, aliasMap);
37 if (!parentSlot)
38 continue;
39 SmallVector<MemorySlot, 2> newSlots;
40 aliaser.getPromotableSlotAliases(aliasedSlotPointerOperand&: operand, parentSlot: *parentSlot, newMemorySlots&: newSlots);
41 for (const MemorySlot &alias : newSlots)
42 aliasMap.try_emplace(Key: alias.ptr, Args: PromotableSlotAliasInfo{.slot: alias, .aliasedSlotPointerOperand: &operand});
43 }
44}
45
46std::optional<MemorySlot>
47mlir::getOpAliasSlot(Operation *op, const MemorySlot &rootSlot,
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>(Val: 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(index: 0).front().front();
60 }
61
62 for (Value operand : op->getOperands())
63 if (std::optional<MemorySlot> slot =
64 getParentSlot(aliasPtr: operand, rootSlot, aliasMap))
65 return slot;
66 return std::nullopt;
67}
68
69bool mlir::referencesAtMostOneAliasOfSlot(Operation *op,
70 const MemorySlot &rootSlot,
71 const PromotableAliasMap &aliasMap) {
72 // As in `getOpAliasSlot`, inspect the wrapped operation instead.
73 if (auto memOp = dyn_cast<PromotableMemOpInterface>(Val: 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(index: 0).front().front();
82 }
83
84 Value uniqueAliasPtr;
85 for (Value operand : op->getOperands()) {
86 std::optional<MemorySlot> slot = getParentSlot(aliasPtr: 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) {
112 SmallVector<ChainStep> chain;
113 Value current = aliasSlot.ptr;
114 while (current != rootSlot.ptr) {
115 auto it = aliasMap.find(Val: current);
116 if (it == aliasMap.end())
117 return std::nullopt;
118 OpOperand *operand = it->second.aliasedSlotPointerOperand;
119 auto aliaser = cast<PromotableAliaserInterface>(Val: operand->getOwner());
120 std::optional<MemorySlot> parent =
121 getParentSlot(aliasPtr: operand->get(), rootSlot, aliasMap);
122 if (!parent)
123 return std::nullopt;
124 chain.push_back(Elt: ChainStep{.aliaser: aliaser, .aliasedSlotPointerOperand: operand, .parentSlot: *parent, .aliasSlot: it->second.slot});
125 current = operand->get();
126 }
127 return chain;
128}
129
130Value mlir::convertSlotValueToAliasValue(Value slotValue,
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(C&: *chain)) {
142 current = step.aliaser.projectSlotValueToAliasValue(
143 aliasedSlotPointerOperand&: *step.aliasedSlotPointerOperand, parentSlot: step.parentSlot, aliasSlot: step.aliasSlot,
144 slotValue: current, builder);
145 if (!current)
146 return {};
147 }
148 return current;
149}
150
151Value mlir::convertAliasValueToSlotValue(Value aliasValue,
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 aliasedSlotPointerOperand&: *chain[i].aliasedSlotPointerOperand, parentSlot: chain[i].parentSlot,
173 aliasSlot: chain[i].aliasSlot, slotValue: 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 aliasedSlotPointerOperand&: *chain[i].aliasedSlotPointerOperand, parentSlot: chain[i].parentSlot,
184 aliasSlot: chain[i].aliasSlot, aliasValue: current, reachingDef: perStepReachingDef[i], builder);
185 if (!current)
186 return {};
187 }
188 return current;
189}
190