| 1 | //===--- CodeGenHwModes.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 | // Classes to parse and store HW mode information for instruction selection |
| 9 | //===----------------------------------------------------------------------===// |
| 10 | |
| 11 | #include "CodeGenHwModes.h" |
| 12 | #include "SubtargetFeatureInfo.h" |
| 13 | #include "llvm/Support/Debug.h" |
| 14 | #include "llvm/Support/raw_ostream.h" |
| 15 | #include "llvm/TableGen/Error.h" |
| 16 | #include "llvm/TableGen/Record.h" |
| 17 | #include <set> |
| 18 | |
| 19 | using namespace llvm; |
| 20 | |
| 21 | #define DEBUG_TYPE "codegen-hwmodes" |
| 22 | |
| 23 | StringRef CodeGenHwModes::DefaultModeName = "DefaultMode" ; |
| 24 | |
| 25 | HwMode::HwMode(const Record *R) { |
| 26 | Name = R->getName(); |
| 27 | Predicates = R->getValueAsListOfDefs(FieldName: "Predicates" ); |
| 28 | } |
| 29 | |
| 30 | LLVM_DUMP_METHOD |
| 31 | void HwMode::dump() const { |
| 32 | dbgs() << Name << ": " ; |
| 33 | ListSeparator LS; |
| 34 | for (const Record *R : Predicates) |
| 35 | dbgs() << LS << R->getName(); |
| 36 | dbgs() << '\n'; |
| 37 | } |
| 38 | |
| 39 | HwModeSelect::HwModeSelect(const Record *R, CodeGenHwModes &CGH) { |
| 40 | std::vector<const Record *> Modes = R->getValueAsListOfDefs(FieldName: "Modes" ); |
| 41 | std::vector<const Record *> Objects = R->getValueAsListOfDefs(FieldName: "Objects" ); |
| 42 | for (auto [Mode, Object] : zip_equal(t&: Modes, u&: Objects)) { |
| 43 | unsigned ModeId = CGH.getHwModeId(R: Mode); |
| 44 | Items.emplace_back(args&: ModeId, args&: Object); |
| 45 | } |
| 46 | } |
| 47 | |
| 48 | LLVM_DUMP_METHOD |
| 49 | void HwModeSelect::dump() const { |
| 50 | dbgs() << '{'; |
| 51 | for (const PairType &P : Items) |
| 52 | dbgs() << " (" << P.first << ',' << P.second->getName() << ')'; |
| 53 | dbgs() << " }\n" ; |
| 54 | } |
| 55 | // Helper to represent predicates semantically. |
| 56 | HwModePredicates::HwModePredicates(ArrayRef<const Record *> Preds) { |
| 57 | HasNonAsmPredicates = |
| 58 | !getRequiredFeatures(FeaturesSet, AnyOfFeatureSets, ReqPredicates: Preds); |
| 59 | } |
| 60 | |
| 61 | // DefaultMode is implicitly active only when *none* of the other target |
| 62 | // HwModes are active. |
| 63 | // |
| 64 | // Mathematically: DefaultMode = !(Mode_1 || Mode_2 || ... || Mode_N) |
| 65 | // = !Mode_1 && !Mode_2 && ... && !Mode_N |
| 66 | // |
| 67 | // If Mode_1 requires (FeatureA && FeatureB), then !Mode_1 requires |
| 68 | // (!FeatureA || !FeatureB). We construct these implicit OR-sets for all |
| 69 | // other modes and add them to DefaultMode's requirements. |
| 70 | HwModePredicates |
| 71 | HwModePredicates::createForDefaultMode(const CodeGenHwModes &CGH) { |
| 72 | HwModePredicates SP; |
| 73 | for (unsigned M = 1; M < CGH.getNumModeIds(); ++M) { |
| 74 | const HwMode &Mode = CGH.getMode(Id: M); |
| 75 | HwModePredicates ModePreds(Mode.Predicates); |
| 76 | if (ModePreds.HasNonAsmPredicates) { |
| 77 | LLVM_DEBUG(dbgs().indent(2) |
| 78 | << "Warning: HwMode '" << Mode.Name |
| 79 | << "' has non-assembler predicates. Ignoring for " |
| 80 | "DefaultMode negation.\n" ); |
| 81 | SP.HasNonAsmPredicates = true; |
| 82 | continue; |
| 83 | } |
| 84 | |
| 85 | // Negate the features in FeaturesSet: !(F1 && F2) = !F1 || !F2 |
| 86 | std::set<SubtargetFeatureLiteral> NegatedFeatures; |
| 87 | for (const auto &Op : ModePreds.FeaturesSet) { |
| 88 | NegatedFeatures.insert(x: {.Feature: Op.Feature, .IsNot: !Op.IsNot}); |
| 89 | } |
| 90 | |
| 91 | if (ModePreds.AnyOfFeatureSets.empty()) { |
| 92 | if (!NegatedFeatures.empty()) |
| 93 | SP.AnyOfFeatureSets.insert(x: std::move(NegatedFeatures)); |
| 94 | } else if (ModePreds.AnyOfFeatureSets.size() == 1) { |
| 95 | // Negate a mode with a single OR-set: |
| 96 | // !(F1 && F2 && (L1 || L2)) = !F1 || !F2 || (!L1 && !L2) |
| 97 | // In CNF: (!F1 || !F2 || !L1) && (!F1 || !F2 || !L2) |
| 98 | const auto &OrSet = *ModePreds.AnyOfFeatureSets.begin(); |
| 99 | for (const auto &Op : OrSet) { |
| 100 | std::set<SubtargetFeatureLiteral> NewOrSet = NegatedFeatures; |
| 101 | NewOrSet.insert(x: {.Feature: Op.Feature, .IsNot: !Op.IsNot}); |
| 102 | SP.AnyOfFeatureSets.insert(x: std::move(NewOrSet)); |
| 103 | } |
| 104 | } else { |
| 105 | LLVM_DEBUG(dbgs().indent(2) |
| 106 | << "Warning: HwMode '" << Mode.Name |
| 107 | << "' has multiple complex predicates. Ignoring for " |
| 108 | "DefaultMode negation.\n" ); |
| 109 | } |
| 110 | } |
| 111 | return SP; |
| 112 | } |
| 113 | |
| 114 | void HwModePredicates::add(const HwModePredicates &Other) { |
| 115 | FeaturesSet.insert(first: Other.FeaturesSet.begin(), last: Other.FeaturesSet.end()); |
| 116 | AnyOfFeatureSets.insert(first: Other.AnyOfFeatureSets.begin(), |
| 117 | last: Other.AnyOfFeatureSets.end()); |
| 118 | HasNonAsmPredicates |= Other.HasNonAsmPredicates; |
| 119 | } |
| 120 | |
| 121 | // Evaluates if the current set of predicates contains a contradiction. |
| 122 | // Performs unit propagation: if we have a known feature F, we can simplify |
| 123 | // OR-sets (A || B) containing F or !F. |
| 124 | // Returns true if the OrSet is satisfied, false otherwise. |
| 125 | // If not satisfied, fills SimplifiedSet with remaining active literals. |
| 126 | static bool simplifyOrSet(const std::set<SubtargetFeatureLiteral> &OrSet, |
| 127 | const std::set<SubtargetFeatureLiteral> &FeaturesSet, |
| 128 | std::set<SubtargetFeatureLiteral> &SimplifiedSet) { |
| 129 | for (const auto &Lit : OrSet) { |
| 130 | if (FeaturesSet.count(x: Lit)) |
| 131 | return true; // Satisfied |
| 132 | if (!FeaturesSet.count(x: {.Feature: Lit.Feature, .IsNot: !Lit.IsNot})) |
| 133 | SimplifiedSet.insert(x: Lit); |
| 134 | } |
| 135 | return false; |
| 136 | } |
| 137 | |
| 138 | // Evaluates if the current set of predicates contains a contradiction. |
| 139 | // Performs unit propagation: if we have a known feature F, we can simplify |
| 140 | // OR-sets (A || B) containing F or !F. |
| 141 | bool HwModePredicates::isSelfContradictory() { |
| 142 | // Check for immediate contradictions (e.g. requiring both F and !F). |
| 143 | for (const auto &Lit : FeaturesSet) { |
| 144 | if (FeaturesSet.count(x: {.Feature: Lit.Feature, .IsNot: !Lit.IsNot})) |
| 145 | return true; |
| 146 | } |
| 147 | |
| 148 | std::set<std::set<SubtargetFeatureLiteral>> NewAnyOfs; |
| 149 | bool FeaturesChanged = false; |
| 150 | |
| 151 | for (const auto &OrSet : AnyOfFeatureSets) { |
| 152 | std::set<SubtargetFeatureLiteral> SimplifiedSet; |
| 153 | if (simplifyOrSet(OrSet, FeaturesSet, SimplifiedSet)) |
| 154 | continue; // Discard satisfied set |
| 155 | |
| 156 | // All literals in this OR-set are false, causing a contradiction. |
| 157 | if (SimplifiedSet.empty()) |
| 158 | return true; |
| 159 | |
| 160 | if (SimplifiedSet.size() == 1) { |
| 161 | // Unit clause: only one choice remains, so it must be true. |
| 162 | FeaturesSet.insert(x: *SimplifiedSet.begin()); |
| 163 | FeaturesChanged = true; |
| 164 | } else { |
| 165 | NewAnyOfs.insert(x: std::move(SimplifiedSet)); |
| 166 | } |
| 167 | } |
| 168 | |
| 169 | if (FeaturesChanged) { |
| 170 | AnyOfFeatureSets = std::move(NewAnyOfs); |
| 171 | return isSelfContradictory(); |
| 172 | } |
| 173 | |
| 174 | return false; |
| 175 | } |
| 176 | |
| 177 | // Two predicate sets conflict if their union is self-contradictory. |
| 178 | bool HwModePredicates::conflictsWith(const HwModePredicates &Other) const { |
| 179 | HwModePredicates Combined(*this); |
| 180 | Combined.add(Other); |
| 181 | return Combined.isSelfContradictory(); |
| 182 | } |
| 183 | |
| 184 | CodeGenHwModes::CodeGenHwModes(const RecordKeeper &RK) : Records(RK) { |
| 185 | for (const Record *R : Records.getAllDerivedDefinitions(ClassName: "HwMode" )) { |
| 186 | // The default mode needs a definition in the .td sources for TableGen |
| 187 | // to accept references to it. We need to ignore the definition here. |
| 188 | if (R->getName() == DefaultModeName) |
| 189 | continue; |
| 190 | Modes.emplace_back(args&: R); |
| 191 | ModeIds.try_emplace(Key: R, Args: Modes.size()); |
| 192 | } |
| 193 | |
| 194 | assert(Modes.size() <= 32 && "number of HwModes exceeds maximum of 32" ); |
| 195 | |
| 196 | for (const Record *R : Records.getAllDerivedDefinitions(ClassName: "HwModeSelect" )) { |
| 197 | auto P = ModeSelects.emplace(args&: R, args: HwModeSelect(R, *this)); |
| 198 | assert(P.second); |
| 199 | (void)P; |
| 200 | } |
| 201 | } |
| 202 | |
| 203 | const HwModePredicates & |
| 204 | CodeGenHwModes::getModePredicates(unsigned ModeId) const { |
| 205 | if (PredicatesByMode.empty()) { |
| 206 | PredicatesByMode.resize(new_size: getNumModeIds()); |
| 207 | PredicatesByMode[DefaultMode] = |
| 208 | HwModePredicates::createForDefaultMode(CGH: *this); |
| 209 | for (unsigned M = 1; M < getNumModeIds(); ++M) |
| 210 | PredicatesByMode[M] = HwModePredicates(getMode(Id: M).Predicates); |
| 211 | } |
| 212 | return PredicatesByMode[ModeId]; |
| 213 | } |
| 214 | |
| 215 | unsigned CodeGenHwModes::getHwModeId(const Record *R) const { |
| 216 | if (R->getName() == DefaultModeName) |
| 217 | return DefaultMode; |
| 218 | auto F = ModeIds.find(Val: R); |
| 219 | assert(F != ModeIds.end() && "Unknown mode name" ); |
| 220 | return F->second; |
| 221 | } |
| 222 | |
| 223 | const HwModeSelect &CodeGenHwModes::getHwModeSelect(const Record *R) const { |
| 224 | auto F = ModeSelects.find(x: R); |
| 225 | assert(F != ModeSelects.end() && "Record is not a \"mode select\"" ); |
| 226 | return F->second; |
| 227 | } |
| 228 | |
| 229 | LLVM_DUMP_METHOD |
| 230 | void CodeGenHwModes::dump() const { |
| 231 | dbgs() << "Modes: {\n" ; |
| 232 | for (const HwMode &M : Modes) { |
| 233 | dbgs() << " " ; |
| 234 | M.dump(); |
| 235 | } |
| 236 | dbgs() << "}\n" ; |
| 237 | |
| 238 | dbgs() << "ModeIds: {\n" ; |
| 239 | for (const auto &P : ModeIds) |
| 240 | dbgs() << " " << P.first->getName() << " -> " << P.second << '\n'; |
| 241 | dbgs() << "}\n" ; |
| 242 | |
| 243 | dbgs() << "ModeSelects: {\n" ; |
| 244 | for (const auto &P : ModeSelects) { |
| 245 | dbgs() << " " << P.first->getName() << " -> " ; |
| 246 | P.second.dump(); |
| 247 | } |
| 248 | dbgs() << "}\n" ; |
| 249 | } |
| 250 | |
| 251 | // Resolves a HwModeSelect record based on pattern predicates. |
| 252 | // Returns a unique resolved record if compatible, or nullptr if ambiguous. |
| 253 | const Record * |
| 254 | CodeGenHwModes::resolveModeSelect(const Record *SelectRec, |
| 255 | ArrayRef<const Record *> PatPreds) const { |
| 256 | if (!SelectRec->isSubClassOf(Name: "HwModeSelect" )) |
| 257 | return SelectRec; |
| 258 | |
| 259 | LLVM_DEBUG(dbgs() << "Trying to resolve HwModeSelect '" |
| 260 | << SelectRec->getName() << "'\n" ); |
| 261 | |
| 262 | const HwModeSelect &MS = getHwModeSelect(R: SelectRec); |
| 263 | |
| 264 | std::set<const Record *> ResolvedObjects; |
| 265 | |
| 266 | // Construct and parse the pattern predicates ONCE here |
| 267 | HwModePredicates PatPredsSet(PatPreds); |
| 268 | |
| 269 | for (const auto &[ModeId, Obj] : MS.Items) { |
| 270 | const HwModePredicates &ModePreds = getModePredicates(ModeId); |
| 271 | |
| 272 | if (!ModePreds.conflictsWith(Other: PatPredsSet)) { |
| 273 | LLVM_DEBUG(dbgs() << " HwMode '" << getModeName(ModeId, true) |
| 274 | << "' is compatible -> " << Obj->getName() << "\n" ); |
| 275 | ResolvedObjects.insert(x: Obj); |
| 276 | } else { |
| 277 | LLVM_DEBUG(dbgs() << " HwMode '" << getModeName(ModeId, true) |
| 278 | << "' is incompatible due to semantic conflict\n" ); |
| 279 | } |
| 280 | } |
| 281 | |
| 282 | if (ResolvedObjects.size() == 1) { |
| 283 | const Record *Resolved = *ResolvedObjects.begin(); |
| 284 | LLVM_DEBUG(dbgs() << " Resolved to unique object: " << Resolved->getName() |
| 285 | << "\n" ); |
| 286 | return Resolved; |
| 287 | } |
| 288 | |
| 289 | if (ResolvedObjects.empty()) { |
| 290 | LLVM_DEBUG(dbgs() << " No active modes resolved for '" |
| 291 | << SelectRec->getName() << "'\n" ); |
| 292 | } else { |
| 293 | LLVM_DEBUG( |
| 294 | dbgs() << " Multiple active modes resolved to different objects for '" |
| 295 | << SelectRec->getName() << "'\n" ); |
| 296 | } |
| 297 | return nullptr; |
| 298 | } |
| 299 | |