1//===- Var.cpp ------------------------------------------------------------===//
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 "Var.h"
10#include "DimLvlMap.h"
11
12using namespace mlir;
13using namespace mlir::sparse_tensor;
14using namespace mlir::sparse_tensor::ir_detail;
15
16//===----------------------------------------------------------------------===//
17// `VarKind` helpers.
18//===----------------------------------------------------------------------===//
19
20/// For use in foreach loops.
21static constexpr const VarKind everyVarKind[] = {
22 VarKind::Dimension, VarKind::Symbol, VarKind::Level};
23
24//===----------------------------------------------------------------------===//
25// `Var` implementation.
26//===----------------------------------------------------------------------===//
27
28std::string Var::str() const {
29 std::string str;
30 llvm::raw_string_ostream os(str);
31 print(os);
32 return str;
33}
34
35void Var::print(AsmPrinter &printer) const { print(os&: printer.getStream()); }
36
37void Var::print(llvm::raw_ostream &os) const {
38 os << toChar(vk: getKind()) << getNum();
39}
40
41#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
42void Var::dump() const {
43 print(llvm::errs());
44 llvm::errs() << "\n";
45}
46#endif
47
48//===----------------------------------------------------------------------===//
49// `Ranks` implementation.
50//===----------------------------------------------------------------------===//
51
52bool Ranks::operator==(Ranks const &other) const {
53 for (const auto vk : everyVarKind)
54 if (getRank(vk) != other.getRank(vk))
55 return false;
56 return true;
57}
58
59bool Ranks::isValid(DimLvlExpr expr) const {
60 assert(expr);
61 // Compute the maximum identifiers for symbol-vars and dim/lvl-vars
62 // (each `DimLvlExpr` only allows one kind of non-symbol variable).
63 int64_t maxSym = -1, maxVar = -1;
64 mlir::getMaxDimAndSymbol<ArrayRef<AffineExpr>>(exprsList: {{expr.getAffineExpr()}},
65 maxDim&: maxVar, maxSym);
66 return maxSym < getSymRank() && maxVar < getRank(vk: expr.getAllowedVarKind());
67}
68
69//===----------------------------------------------------------------------===//
70// `VarSet` implementation.
71//===----------------------------------------------------------------------===//
72
73VarSet::VarSet(Ranks const &ranks) {
74 for (const auto vk : everyVarKind)
75 impl[vk] = llvm::SmallBitVector(ranks.getRank(vk));
76 assert(getRanks() == ranks);
77}
78
79bool VarSet::contains(Var var) const {
80 // NOTE: We make sure to return false on OOB, for consistency with
81 // the `anyCommon` implementation of `VarSet::occursIn(VarSet)`.
82 // However beware that, as always with silencing OOB, this can hide
83 // bugs in client code.
84 const llvm::SmallBitVector &bits = impl[var.getKind()];
85 const auto num = var.getNum();
86 return num < bits.size() && bits[num];
87}
88
89void VarSet::add(Var var) {
90 // NOTE: `SmallBitVector::operator[]` will raise assertion errors for OOB.
91 impl[var.getKind()][var.getNum()] = true;
92}
93
94void VarSet::add(VarSet const &other) {
95 // NOTE: `SmallBitVector::operator&=` will implicitly resize
96 // the bitvector (unlike `BitVector::operator&=`), so we add an
97 // assertion against OOB for consistency with the implementation
98 // of `VarSet::add(Var)`.
99 for (const auto vk : everyVarKind) {
100 assert(impl[vk].size() >= other.impl[vk].size());
101 impl[vk] &= other.impl[vk];
102 }
103}
104
105void VarSet::add(DimLvlExpr expr) {
106 if (!expr)
107 return;
108 switch (expr.getAffineKind()) {
109 case AffineExprKind::Constant:
110 return;
111 case AffineExprKind::SymbolId:
112 add(var: expr.castSymVar());
113 return;
114 case AffineExprKind::DimId:
115 add(var: expr.castDimLvlVar());
116 return;
117 case AffineExprKind::Add:
118 case AffineExprKind::Mul:
119 case AffineExprKind::Mod:
120 case AffineExprKind::FloorDiv:
121 case AffineExprKind::CeilDiv: {
122 const auto [lhs, op, rhs] = expr.unpackBinop();
123 (void)op;
124 add(expr: lhs);
125 add(expr: rhs);
126 return;
127 }
128 }
129 llvm_unreachable("unknown AffineExprKind");
130}
131
132//===----------------------------------------------------------------------===//
133// `VarInfo` implementation.
134//===----------------------------------------------------------------------===//
135
136void VarInfo::setNum(Var::Num n) {
137 assert(!hasNum() && "Var::Num is already set");
138 assert(Var::isWF_Num(n) && "Var::Num is too large");
139 num = n;
140}
141
142//===----------------------------------------------------------------------===//
143// `VarEnv` implementation.
144//===----------------------------------------------------------------------===//
145
146/// Helper function for `assertUsageConsistency` to better handle SMLoc
147/// mismatches.
148[[maybe_unused]] static llvm::SMLoc minSMLoc(AsmParser &parser, llvm::SMLoc sm1,
149 llvm::SMLoc sm2) {
150 const auto loc1 = dyn_cast<FileLineColLoc>(Val: parser.getEncodedSourceLoc(loc: sm1));
151 assert(loc1 && "Could not get `FileLineColLoc` for first `SMLoc`");
152 const auto loc2 = dyn_cast<FileLineColLoc>(Val: parser.getEncodedSourceLoc(loc: sm2));
153 assert(loc2 && "Could not get `FileLineColLoc` for second `SMLoc`");
154 if (loc1.getFilename() != loc2.getFilename())
155 return SMLoc();
156 const auto pair1 = std::make_pair(x: loc1.getLine(), y: loc1.getColumn());
157 const auto pair2 = std::make_pair(x: loc2.getLine(), y: loc2.getColumn());
158 return pair1 <= pair2 ? sm1 : sm2;
159}
160
161static bool isInternalConsistent(VarEnv const &env, VarInfo::ID id,
162 StringRef name) {
163 const auto &var = env.access(id);
164 return (var.getName() == name && var.getID() == id);
165}
166
167static bool isUsageConsistent(VarEnv const &env, VarInfo::ID id,
168 llvm::SMLoc loc, VarKind vk) {
169 const auto &var = env.access(id);
170 return var.getKind() == vk;
171}
172
173std::optional<VarInfo::ID> VarEnv::lookup(StringRef name) const {
174 const auto iter = ids.find(Key: name);
175 if (iter == ids.end())
176 return std::nullopt;
177 const auto id = iter->second;
178 if (!isInternalConsistent(env: *this, id, name))
179 return std::nullopt;
180 return id;
181}
182
183std::optional<std::pair<VarInfo::ID, bool>>
184VarEnv::create(StringRef name, llvm::SMLoc loc, VarKind vk, bool verifyUsage) {
185 const auto &[iter, didInsert] = ids.try_emplace(Key: name, Args: nextID());
186 const auto id = iter->second;
187 if (didInsert) {
188 vars.emplace_back(Args: id, Args&: name, Args&: loc, Args&: vk);
189 } else {
190 if (!isInternalConsistent(env: *this, id, name))
191 return std::nullopt;
192 if (verifyUsage)
193 if (!isUsageConsistent(env: *this, id, loc, vk))
194 return std::nullopt;
195 }
196 return std::make_pair(x: id, y: didInsert);
197}
198
199std::optional<std::pair<VarInfo::ID, bool>>
200VarEnv::lookupOrCreate(Policy creationPolicy, StringRef name, llvm::SMLoc loc,
201 VarKind vk) {
202 switch (creationPolicy) {
203 case Policy::MustNot: {
204 const auto oid = lookup(name);
205 if (!oid)
206 return std::nullopt; // Doesn't exist, but must not create.
207 if (!isUsageConsistent(env: *this, id: *oid, loc, vk))
208 return std::nullopt;
209 return std::make_pair(x: *oid, y: false);
210 }
211 case Policy::May:
212 return create(name, loc, vk, /*verifyUsage=*/true);
213 case Policy::Must: {
214 const auto res = create(name, loc, vk, /*verifyUsage=*/false);
215 const auto didCreate = res->second;
216 if (!didCreate)
217 return std::nullopt; // Already exists, but must create.
218 return res;
219 }
220 }
221 llvm_unreachable("unknown Policy");
222}
223
224Var VarEnv::bindUnusedVar(VarKind vk) { return Var(vk, nextNum[vk]++); }
225Var VarEnv::bindVar(VarInfo::ID id) {
226 auto &info = access(id);
227 const auto var = bindUnusedVar(vk: info.getKind());
228 info.setNum(var.getNum());
229 return var;
230}
231
232InFlightDiagnostic VarEnv::emitErrorIfAnyUnbound(AsmParser &parser) const {
233 for (const auto &var : vars)
234 if (!var.hasNum())
235 return parser.emitError(loc: var.getLoc(),
236 message: "Unbound variable: " + var.getName());
237 return {};
238}
239
240//===----------------------------------------------------------------------===//
241