1//===- SetTheory.cpp - Generate ordered sets from DAG expressions ---------===//
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// This file implements the SetTheory class that computes ordered sets of
10// Records from DAG expressions.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/TableGen/SetTheory.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/ADT/StringRef.h"
19#include "llvm/Support/Casting.h"
20#include "llvm/Support/Format.h"
21#include "llvm/Support/SMLoc.h"
22#include "llvm/Support/raw_ostream.h"
23#include "llvm/TableGen/Error.h"
24#include "llvm/TableGen/Record.h"
25#include <algorithm>
26#include <cstdint>
27#include <string>
28#include <utility>
29
30using namespace llvm;
31
32// Define the standard operators.
33namespace {
34
35using RecSet = SetTheory::RecSet;
36using RecVec = SetTheory::RecVec;
37
38// (add a, b, ...) Evaluate and union all arguments.
39struct AddOp : public SetTheory::Operator {
40 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,
41 ArrayRef<SMLoc> Loc) override {
42 ST.evaluate(begin: Expr->arg_begin(), end: Expr->arg_end(), Elts, Loc);
43 }
44};
45
46// (sub Add, Sub, ...) Set difference.
47struct SubOp : public SetTheory::Operator {
48 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,
49 ArrayRef<SMLoc> Loc) override {
50 if (Expr->arg_size() < 2)
51 PrintFatalError(ErrorLoc: Loc, Msg: "Set difference needs at least two arguments: " +
52 Expr->getAsString());
53 RecSet Add, Sub;
54 ST.evaluate(Expr: *Expr->arg_begin(), Elts&: Add, Loc);
55 ST.evaluate(begin: Expr->arg_begin() + 1, end: Expr->arg_end(), Elts&: Sub, Loc);
56 for (const auto &I : Add)
57 if (!Sub.count(key: I))
58 Elts.insert(X: I);
59 }
60};
61
62// (and S1, S2) Set intersection.
63struct AndOp : public SetTheory::Operator {
64 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,
65 ArrayRef<SMLoc> Loc) override {
66 if (Expr->arg_size() != 2)
67 PrintFatalError(ErrorLoc: Loc, Msg: "Set intersection requires two arguments: " +
68 Expr->getAsString());
69 RecSet S1, S2;
70 ST.evaluate(Expr: Expr->arg_begin()[0], Elts&: S1, Loc);
71 ST.evaluate(Expr: Expr->arg_begin()[1], Elts&: S2, Loc);
72 for (const auto &I : S1)
73 if (S2.count(key: I))
74 Elts.insert(X: I);
75 }
76};
77
78// SetIntBinOp - Abstract base class for (Op S, N) operators.
79struct SetIntBinOp : public SetTheory::Operator {
80 virtual void apply2(SetTheory &ST, const DagInit *Expr, RecSet &Set,
81 int64_t N, RecSet &Elts, ArrayRef<SMLoc> Loc) = 0;
82
83 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,
84 ArrayRef<SMLoc> Loc) override {
85 if (Expr->arg_size() != 2)
86 PrintFatalError(ErrorLoc: Loc, Msg: "Operator requires (Op Set, Int) arguments: " +
87 Expr->getAsString());
88 RecSet Set;
89 ST.evaluate(Expr: Expr->arg_begin()[0], Elts&: Set, Loc);
90 const auto *II = dyn_cast<IntInit>(Val: Expr->arg_begin()[1]);
91 if (!II)
92 PrintFatalError(ErrorLoc: Loc, Msg: "Second argument must be an integer: " +
93 Expr->getAsString());
94 apply2(ST, Expr, Set, N: II->getValue(), Elts, Loc);
95 }
96};
97
98// (shl S, N) Shift left, remove the first N elements.
99struct ShlOp : public SetIntBinOp {
100 void apply2(SetTheory &ST, const DagInit *Expr, RecSet &Set, int64_t N,
101 RecSet &Elts, ArrayRef<SMLoc> Loc) override {
102 if (N < 0)
103 PrintFatalError(ErrorLoc: Loc, Msg: "Positive shift required: " +
104 Expr->getAsString());
105 if (unsigned(N) < Set.size())
106 Elts.insert(Start: Set.begin() + N, End: Set.end());
107 }
108};
109
110// (trunc S, N) Truncate after the first N elements.
111struct TruncOp : public SetIntBinOp {
112 void apply2(SetTheory &ST, const DagInit *Expr, RecSet &Set, int64_t N,
113 RecSet &Elts, ArrayRef<SMLoc> Loc) override {
114 if (N < 0)
115 PrintFatalError(ErrorLoc: Loc, Msg: "Positive length required: " +
116 Expr->getAsString());
117 if (unsigned(N) > Set.size())
118 N = Set.size();
119 Elts.insert(Start: Set.begin(), End: Set.begin() + N);
120 }
121};
122
123// Left/right rotation.
124struct RotOp : public SetIntBinOp {
125 const bool Reverse;
126
127 RotOp(bool Rev) : Reverse(Rev) {}
128
129 void apply2(SetTheory &ST, const DagInit *Expr, RecSet &Set, int64_t N,
130 RecSet &Elts, ArrayRef<SMLoc> Loc) override {
131 if (Reverse)
132 N = -N;
133 // N > 0 -> rotate left, N < 0 -> rotate right.
134 if (Set.empty())
135 return;
136 if (N < 0)
137 N = Set.size() - (-N % Set.size());
138 else
139 N %= Set.size();
140 Elts.insert(Start: Set.begin() + N, End: Set.end());
141 Elts.insert(Start: Set.begin(), End: Set.begin() + N);
142 }
143};
144
145// (decimate S, N) Pick every N'th element of S.
146struct DecimateOp : public SetIntBinOp {
147 void apply2(SetTheory &ST, const DagInit *Expr, RecSet &Set, int64_t N,
148 RecSet &Elts, ArrayRef<SMLoc> Loc) override {
149 if (N <= 0)
150 PrintFatalError(ErrorLoc: Loc, Msg: "Positive stride required: " +
151 Expr->getAsString());
152 for (unsigned I = 0; I < Set.size(); I += N)
153 Elts.insert(X: Set[I]);
154 }
155};
156
157// (interleave S1, S2, ...) Interleave elements of the arguments.
158struct InterleaveOp : public SetTheory::Operator {
159 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,
160 ArrayRef<SMLoc> Loc) override {
161 // Evaluate the arguments individually.
162 SmallVector<RecSet, 4> Values(Expr->getNumArgs());
163 unsigned MaxSize = 0;
164 for (auto [Arg, Value] : zip(t: Expr->getArgs(), u&: Values)) {
165 ST.evaluate(Expr: Arg, Elts&: Value, Loc);
166 MaxSize = std::max(a: MaxSize, b: unsigned(Value.size()));
167 }
168 // Interleave arguments into Elts.
169 for (unsigned n = 0; n != MaxSize; ++n)
170 for (const RecSet &Value : Values)
171 if (n < Value.size())
172 Elts.insert(X: Value[n]);
173 }
174};
175
176// (sequence "Format", From, To) Generate a sequence of records by name.
177struct SequenceOp : public SetTheory::Operator {
178 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,
179 ArrayRef<SMLoc> Loc) override {
180 int Step = 1;
181 if (Expr->arg_size() > 4)
182 PrintFatalError(ErrorLoc: Loc, Msg: "Bad args to (sequence \"Format\", From, To): " +
183 Expr->getAsString());
184 if (Expr->arg_size() == 4) {
185 if (const auto *II = dyn_cast<IntInit>(Val: Expr->arg_begin()[3]))
186 Step = II->getValue();
187 else
188 PrintFatalError(ErrorLoc: Loc, Msg: "Stride must be an integer: " +
189 Expr->getAsString());
190 }
191
192 std::string Format;
193 if (const auto *SI = dyn_cast<StringInit>(Val: Expr->arg_begin()[0]))
194 Format = SI->getValue().str();
195 else
196 PrintFatalError(ErrorLoc: Loc, Msg: "Format must be a string: " + Expr->getAsString());
197
198 int64_t From, To;
199 if (const auto *II = dyn_cast<IntInit>(Val: Expr->arg_begin()[1]))
200 From = II->getValue();
201 else
202 PrintFatalError(ErrorLoc: Loc, Msg: "From must be an integer: " + Expr->getAsString());
203 if (From < 0 || From >= (1 << 30))
204 PrintFatalError(ErrorLoc: Loc, Msg: "From out of range");
205
206 if (const auto *II = dyn_cast<IntInit>(Val: Expr->arg_begin()[2]))
207 To = II->getValue();
208 else
209 PrintFatalError(ErrorLoc: Loc, Msg: "To must be an integer: " + Expr->getAsString());
210 if (To < 0 || To >= (1 << 30))
211 PrintFatalError(ErrorLoc: Loc, Msg: "To out of range");
212
213 const RecordKeeper &Records =
214 cast<DefInit>(Val: Expr->getOperator())->getDef()->getRecords();
215
216 Step *= From <= To ? 1 : -1;
217 while (true) {
218 if (Step > 0 && From > To)
219 break;
220 else if (Step < 0 && From < To)
221 break;
222 std::string Name;
223 raw_string_ostream OS(Name);
224 OS << format(Fmt: Format.c_str(), Vals: unsigned(From));
225 const Record *Rec = Records.getDef(Name);
226 if (!Rec)
227 PrintFatalError(ErrorLoc: Loc, Msg: "No def named '" + Name + "': " +
228 Expr->getAsString());
229 // Try to reevaluate Rec in case it is a set.
230 if (const RecVec *Result = ST.expand(Set: Rec))
231 Elts.insert_range(R: *Result);
232 else
233 Elts.insert(X: Rec);
234
235 From += Step;
236 }
237 }
238};
239
240// Expand a Def into a set by evaluating one of its fields.
241struct FieldExpander : public SetTheory::Expander {
242 StringRef FieldName;
243
244 FieldExpander(StringRef fn) : FieldName(fn) {}
245
246 void expand(SetTheory &ST, const Record *Def, RecSet &Elts) override {
247 ST.evaluate(Expr: Def->getValueInit(FieldName), Elts, Loc: Def->getLoc());
248 }
249};
250
251} // end anonymous namespace
252
253// Pin the vtables to this file.
254void SetTheory::Operator::anchor() {}
255void SetTheory::Expander::anchor() {}
256
257SetTheory::SetTheory() {
258 addOperator(Name: "add", std::make_unique<AddOp>());
259 addOperator(Name: "sub", std::make_unique<SubOp>());
260 addOperator(Name: "and", std::make_unique<AndOp>());
261 addOperator(Name: "shl", std::make_unique<ShlOp>());
262 addOperator(Name: "trunc", std::make_unique<TruncOp>());
263 addOperator(Name: "rotl", std::make_unique<RotOp>(args: false));
264 addOperator(Name: "rotr", std::make_unique<RotOp>(args: true));
265 addOperator(Name: "decimate", std::make_unique<DecimateOp>());
266 addOperator(Name: "interleave", std::make_unique<InterleaveOp>());
267 addOperator(Name: "sequence", std::make_unique<SequenceOp>());
268}
269
270void SetTheory::addOperator(StringRef Name, std::unique_ptr<Operator> Op) {
271 Operators[Name] = std::move(Op);
272}
273
274void SetTheory::addExpander(StringRef ClassName, std::unique_ptr<Expander> E) {
275 Expanders[ClassName] = std::move(E);
276}
277
278void SetTheory::addFieldExpander(StringRef ClassName, StringRef FieldName) {
279 addExpander(ClassName, E: std::make_unique<FieldExpander>(args&: FieldName));
280}
281
282void SetTheory::evaluate(const Init *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc) {
283 // A def in a list can be a just an element, or it may expand.
284 if (const auto *Def = dyn_cast<DefInit>(Val: Expr)) {
285 if (const RecVec *Result = expand(Set: Def->getDef()))
286 return Elts.insert_range(R: *Result);
287 Elts.insert(X: Def->getDef());
288 return;
289 }
290
291 // Lists simply expand.
292 if (const auto *LI = dyn_cast<ListInit>(Val: Expr))
293 return evaluate(begin: LI->begin(), end: LI->end(), Elts, Loc);
294
295 // Anything else must be a DAG.
296 const auto *DagExpr = dyn_cast<DagInit>(Val: Expr);
297 if (!DagExpr)
298 PrintFatalError(ErrorLoc: Loc, Msg: "Invalid set element: " + Expr->getAsString());
299 const auto *OpInit = dyn_cast<DefInit>(Val: DagExpr->getOperator());
300 if (!OpInit)
301 PrintFatalError(ErrorLoc: Loc, Msg: "Bad set expression: " + Expr->getAsString());
302 auto I = Operators.find(Key: OpInit->getDef()->getName());
303 if (I == Operators.end())
304 PrintFatalError(ErrorLoc: Loc, Msg: "Unknown set operator: " + Expr->getAsString());
305 I->second->apply(*this, Expr: DagExpr, Elts, Loc);
306}
307
308const RecVec *SetTheory::expand(const Record *Set) {
309 // Check existing entries for Set and return early.
310 ExpandMap::iterator I = Expansions.find(x: Set);
311 if (I != Expansions.end())
312 return &I->second;
313
314 // This is the first time we see Set. Find a suitable expander.
315 for (const Record *SuperClass : Set->getSuperClasses()) {
316 // Skip unnamed superclasses.
317 if (!isa<StringInit>(Val: SuperClass->getNameInit()))
318 continue;
319 auto I = Expanders.find(Key: SuperClass->getName());
320 if (I == Expanders.end())
321 continue;
322 // This breaks recursive definitions.
323 RecVec &EltVec = Expansions[Set];
324 RecSet Elts;
325 I->second->expand(*this, Set, Elts);
326 EltVec.assign(first: Elts.begin(), last: Elts.end());
327 return &EltVec;
328 }
329
330 // Set is not expandable.
331 return nullptr;
332}
333