| 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 | |
| 12 | using namespace mlir; |
| 13 | using namespace mlir::sparse_tensor; |
| 14 | using namespace mlir::sparse_tensor::ir_detail; |
| 15 | |
| 16 | //===----------------------------------------------------------------------===// |
| 17 | // `VarKind` helpers. |
| 18 | //===----------------------------------------------------------------------===// |
| 19 | |
| 20 | /// For use in foreach loops. |
| 21 | static constexpr const VarKind everyVarKind[] = { |
| 22 | VarKind::Dimension, VarKind::Symbol, VarKind::Level}; |
| 23 | |
| 24 | //===----------------------------------------------------------------------===// |
| 25 | // `Var` implementation. |
| 26 | //===----------------------------------------------------------------------===// |
| 27 | |
| 28 | std::string Var::str() const { |
| 29 | std::string str; |
| 30 | llvm::raw_string_ostream os(str); |
| 31 | print(os); |
| 32 | return str; |
| 33 | } |
| 34 | |
| 35 | void Var::print(AsmPrinter &printer) const { print(os&: printer.getStream()); } |
| 36 | |
| 37 | void Var::print(llvm::raw_ostream &os) const { |
| 38 | os << toChar(vk: getKind()) << getNum(); |
| 39 | } |
| 40 | |
| 41 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| 42 | void Var::dump() const { |
| 43 | print(llvm::errs()); |
| 44 | llvm::errs() << "\n" ; |
| 45 | } |
| 46 | #endif |
| 47 | |
| 48 | //===----------------------------------------------------------------------===// |
| 49 | // `Ranks` implementation. |
| 50 | //===----------------------------------------------------------------------===// |
| 51 | |
| 52 | bool 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 | |
| 59 | bool 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 | |
| 73 | VarSet::VarSet(Ranks const &ranks) { |
| 74 | for (const auto vk : everyVarKind) |
| 75 | impl[vk] = llvm::SmallBitVector(ranks.getRank(vk)); |
| 76 | assert(getRanks() == ranks); |
| 77 | } |
| 78 | |
| 79 | bool 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 | |
| 89 | void VarSet::add(Var var) { |
| 90 | // NOTE: `SmallBitVector::operator[]` will raise assertion errors for OOB. |
| 91 | impl[var.getKind()][var.getNum()] = true; |
| 92 | } |
| 93 | |
| 94 | void 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 | |
| 105 | void 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 | |
| 136 | void 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 | |
| 161 | static 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 | |
| 167 | static 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 | |
| 173 | std::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 | |
| 183 | std::optional<std::pair<VarInfo::ID, bool>> |
| 184 | VarEnv::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 | |
| 199 | std::optional<std::pair<VarInfo::ID, bool>> |
| 200 | VarEnv::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 | |
| 224 | Var VarEnv::bindUnusedVar(VarKind vk) { return Var(vk, nextNum[vk]++); } |
| 225 | Var 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 | |
| 232 | InFlightDiagnostic 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 | |