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