1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
| //===- SetTheory.h - Generate ordered sets from DAG expressions -*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the SetTheory class that computes ordered sets of
// Records from DAG expressions. Operators for standard set operations are
// predefined, and it is possible to add special purpose set operators as well.
//
// The user may define named sets as Records of predefined classes. Set
// expanders can be added to a SetTheory instance to teach it how to find the
// elements of such a named set.
//
// These are the predefined operators. The argument lists can be individual
// elements (defs), other sets (defs of expandable classes), lists, or DAG
// expressions that are evaluated recursively.
//
// - (add S1, S2 ...) Union sets. This is also how sets are created from element
// lists.
//
// - (sub S1, S2, ...) Set difference. Every element in S1 except for the
// elements in S2, ...
//
// - (and S1, S2) Set intersection. Every element in S1 that is also in S2.
//
// - (shl S, N) Shift left. Remove the first N elements from S.
//
// - (trunc S, N) Truncate. The first N elements of S.
//
// - (rotl S, N) Rotate left. Same as (add (shl S, N), (trunc S, N)).
//
// - (rotr S, N) Rotate right.
//
// - (decimate S, N) Decimate S by picking every N'th element, starting with
// the first one. For instance, (decimate S, 2) returns the even elements of
// S.
//
// - (sequence "Format", From, To) Generate a sequence of defs with printf.
// For instance, (sequence "R%u", 0, 3) -> [ R0, R1, R2, R3 ]
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TABLEGEN_SETTHEORY_H
#define LLVM_TABLEGEN_SETTHEORY_H
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Support/SMLoc.h"
#include <map>
#include <memory>
#include <vector>
namespace llvm {
class DagInit;
class Init;
class Record;
class SetTheory {
public:
using RecVec = std::vector<Record *>;
using RecSet = SmallSetVector<Record *, 16>;
/// Operator - A callback representing a DAG operator.
class Operator {
virtual void anchor();
public:
virtual ~Operator() = default;
/// apply - Apply this operator to Expr's arguments and insert the result
/// in Elts.
virtual void apply(SetTheory&, DagInit *Expr, RecSet &Elts,
ArrayRef<SMLoc> Loc) = 0;
};
/// Expander - A callback function that can transform a Record representing a
/// set into a fully expanded list of elements. Expanders provide a way for
/// users to define named sets that can be used in DAG expressions.
class Expander {
virtual void anchor();
public:
virtual ~Expander() = default;
virtual void expand(SetTheory&, Record*, RecSet &Elts) = 0;
};
private:
// Map set defs to their fully expanded contents. This serves as a memoization
// cache and it makes it possible to return const references on queries.
using ExpandMap = std::map<Record *, RecVec>;
ExpandMap Expansions;
// Known DAG operators by name.
StringMap<std::unique_ptr<Operator>> Operators;
// Typed expanders by class name.
StringMap<std::unique_ptr<Expander>> Expanders;
public:
/// Create a SetTheory instance with only the standard operators.
SetTheory();
/// addExpander - Add an expander for Records with the named super class.
void addExpander(StringRef ClassName, std::unique_ptr<Expander>);
/// addFieldExpander - Add an expander for ClassName that simply evaluates
/// FieldName in the Record to get the set elements. That is all that is
/// needed for a class like:
///
/// class Set<dag d> {
/// dag Elts = d;
/// }
///
void addFieldExpander(StringRef ClassName, StringRef FieldName);
/// addOperator - Add a DAG operator.
void addOperator(StringRef Name, std::unique_ptr<Operator>);
/// evaluate - Evaluate Expr and append the resulting set to Elts.
void evaluate(Init *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc);
/// evaluate - Evaluate a sequence of Inits and append to Elts.
template<typename Iter>
void evaluate(Iter begin, Iter end, RecSet &Elts, ArrayRef<SMLoc> Loc) {
while (begin != end)
evaluate(*begin++, Elts, Loc);
}
/// expand - Expand a record into a set of elements if possible. Return a
/// pointer to the expanded elements, or NULL if Set cannot be expanded
/// further.
const RecVec *expand(Record *Set);
};
} // end namespace llvm
#endif // LLVM_TABLEGEN_SETTHEORY_H
|