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