1 | //===- SetTheory.h - Generate ordered sets from DAG expressions -*- C++ -*-===// |
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. Operators for standard set operations are |
11 | // predefined, and it is possible to add special purpose set operators as well. |
12 | // |
13 | // The user may define named sets as Records of predefined classes. Set |
14 | // expanders can be added to a SetTheory instance to teach it how to find the |
15 | // elements of such a named set. |
16 | // |
17 | // These are the predefined operators. The argument lists can be individual |
18 | // elements (defs), other sets (defs of expandable classes), lists, or DAG |
19 | // expressions that are evaluated recursively. |
20 | // |
21 | // - (add S1, S2 ...) Union sets. This is also how sets are created from element |
22 | // lists. |
23 | // |
24 | // - (sub S1, S2, ...) Set difference. Every element in S1 except for the |
25 | // elements in S2, ... |
26 | // |
27 | // - (and S1, S2) Set intersection. Every element in S1 that is also in S2. |
28 | // |
29 | // - (shl S, N) Shift left. Remove the first N elements from S. |
30 | // |
31 | // - (trunc S, N) Truncate. The first N elements of S. |
32 | // |
33 | // - (rotl S, N) Rotate left. Same as (add (shl S, N), (trunc S, N)). |
34 | // |
35 | // - (rotr S, N) Rotate right. |
36 | // |
37 | // - (decimate S, N) Decimate S by picking every N'th element, starting with |
38 | // the first one. For instance, (decimate S, 2) returns the even elements of |
39 | // S. |
40 | // |
41 | // - (sequence "Format", From, To, [Stride]) Generate a sequence of defs with |
42 | // printf. For instance, (sequence "R%u", 0, 3) -> [ R0, R1, R2, R3 ] and |
43 | // (sequence "R%u", 20, 30, 5) -> [ R20, R25, R30 ]. |
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 | 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 | 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 | void evaluate(Iter begin, Iter end, RecSet &Elts, ArrayRef<SMLoc> Loc) { |
133 | while (begin != end) |
134 | evaluate(*begin++, Elts, Loc); |
135 | } |
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 |
146 | |