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