LLVM 20.0.0git
SetTheory.cpp
Go to the documentation of this file.
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
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/StringRef.h"
20#include "llvm/Support/Format.h"
21#include "llvm/Support/SMLoc.h"
23#include "llvm/TableGen/Error.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(Expr->arg_begin(), 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(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 (const auto &I : Add)
57 if (!Sub.count(I))
58 Elts.insert(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(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 (const auto &I : S1)
73 if (S2.count(I))
74 Elts.insert(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(Loc, "Operator requires (Op Set, Int) arguments: " +
87 Expr->getAsString());
88 RecSet Set;
89 ST.evaluate(Expr->arg_begin()[0], Set, Loc);
90 const auto *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.
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(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.
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(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.
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(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.
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(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.
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(Expr->getArgs(), Values)) {
165 ST.evaluate(Arg, Value, Loc);
166 MaxSize = std::max(MaxSize, 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(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(Loc, "Bad args to (sequence \"Format\", From, To): " +
183 Expr->getAsString());
184 if (Expr->arg_size() == 4) {
185 if (const auto *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 (const auto *SI = dyn_cast<StringInit>(Expr->arg_begin()[0]))
194 Format = std::string(SI->getValue());
195 else
196 PrintFatalError(Loc, "Format must be a string: " + Expr->getAsString());
197
198 int64_t From, To;
199 if (const auto *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 (const auto *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 const 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;
224 OS << format(Format.c_str(), unsigned(From));
225 const Record *Rec = Records.getDef(Name);
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.
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(Def->getValueInit(FieldName), Elts, 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
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
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
279 addExpander(ClassName, std::make_unique<FieldExpander>(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>(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 (const auto *LI = dyn_cast<ListInit>(Expr))
293 return evaluate(LI->begin(), LI->end(), Elts, Loc);
294
295 // Anything else must be a DAG.
296 const auto *DagExpr = dyn_cast<DagInit>(Expr);
297 if (!DagExpr)
298 PrintFatalError(Loc, "Invalid set element: " + Expr->getAsString());
299 const auto *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
308const RecVec *SetTheory::expand(const 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 for (const auto &[SuperClass, Loc] : Set->getSuperClasses()) {
316 // Skip unnamed superclasses.
317 if (!isa<StringInit>(SuperClass->getNameInit()))
318 continue;
319 auto I = Expanders.find(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(Elts.begin(), Elts.end());
327 return &EltVec;
328 }
329
330 // Set is not expandable.
331 return nullptr;
332}
static const LLT S1
BlockVerifier::State From
std::string Name
#define I(x, y, z)
Definition: MD5.cpp:58
uint64_t IntrinsicInst * II
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
This class represents an Operation in the Expression.
(v a, b) - Represent a DAG tree value.
Definition: Record.h:1458
unsigned getNumArgs() const
Definition: Record.h:1501
const_arg_iterator arg_begin() const
Definition: Record.h:1539
const_arg_iterator arg_end() const
Definition: Record.h:1540
const Init * getOperator() const
Definition: Record.h:1492
size_t arg_size() const
Definition: Record.h:1542
ArrayRef< const Init * > getArgs() const
Definition: Record.h:1522
std::string getAsString() const override
Convert this value to a literal form.
Definition: Record.cpp:2745
virtual std::string getAsString() const =0
Convert this value to a literal form.
Base class for operators.
Definition: Record.h:823
Expander - A callback function that can transform a Record representing a set into a fully expanded l...
Definition: SetTheory.h:86
virtual void expand(SetTheory &, const Record *, RecSet &Elts)=0
Operator - A callback representing a DAG operator.
Definition: SetTheory.h:71
virtual void apply(SetTheory &, const DagInit *Expr, RecSet &Elts, ArrayRef< SMLoc > Loc)=0
apply - Apply this operator to Expr's arguments and insert the result in Elts.
void addOperator(StringRef Name, std::unique_ptr< Operator >)
addOperator - Add a DAG operator.
Definition: SetTheory.cpp:270
SetTheory()
Create a SetTheory instance with only the standard operators.
Definition: SetTheory.cpp:257
const RecVec * expand(const Record *Set)
expand - Expand a record into a set of elements if possible.
Definition: SetTheory.cpp:308
SmallSetVector< const Record *, 16 > RecSet
Definition: SetTheory.h:68
void evaluate(const Init *Expr, RecSet &Elts, ArrayRef< SMLoc > Loc)
evaluate - Evaluate Expr and append the resulting set to Elts.
Definition: SetTheory.cpp:282
std::vector< const Record * > RecVec
Definition: SetTheory.h:67
void addFieldExpander(StringRef ClassName, StringRef FieldName)
addFieldExpander - Add an expander for ClassName that simply evaluates FieldName in the Record to get...
Definition: SetTheory.cpp:278
void addExpander(StringRef ClassName, std::unique_ptr< Expander >)
addExpander - Add an expander for Records with the named super class.
Definition: SetTheory.cpp:274
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:113
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:103
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:51
LLVM Value Representation.
Definition: Value.h:74
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:661
llvm::SmallVector< std::shared_ptr< RecordsSlice >, 4 > Records
Definition: RecordsSlice.h:197
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
Format
The format used for serializing/deserializing remarks.
Definition: RemarkFormat.h:25
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:854
void PrintFatalError(const Twine &Msg)
Definition: Error.cpp:132
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:125
@ Add
Sum of integers.
#define N