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
19using namespace llvm;
20
21#define DEBUG_TYPE "codegen-hwmodes"
22
23StringRef CodeGenHwModes::DefaultModeName = "DefaultMode";
24
25HwMode::HwMode(const Record *R) {
26 Name = R->getName();
27 Predicates = R->getValueAsListOfDefs(FieldName: "Predicates");
28}
29
30LLVM_DUMP_METHOD
31void 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
39HwModeSelect::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
48LLVM_DUMP_METHOD
49void 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.
56HwModePredicates::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.
70HwModePredicates
71HwModePredicates::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
114void 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.
126static 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.
141bool 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.
178bool HwModePredicates::conflictsWith(const HwModePredicates &Other) const {
179 HwModePredicates Combined(*this);
180 Combined.add(Other);
181 return Combined.isSelfContradictory();
182}
183
184CodeGenHwModes::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
203const HwModePredicates &
204CodeGenHwModes::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
215unsigned 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
223const 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
229LLVM_DUMP_METHOD
230void 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.
253const Record *
254CodeGenHwModes::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