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