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
|
//===- SetTheory.h - Generate ordered sets from DAG expressions -*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// 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 SETTHEORY_H
#define SETTHEORY_H
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/SetVector.h"
#include <map>
#include <vector>
namespace llvm {
class DagInit;
class Init;
class Record;
class RecordKeeper;
class SetTheory {
public:
typedef std::vector<Record*> RecVec;
typedef SmallSetVector<Record*, 16> RecSet;
/// Operator - A callback representing a DAG operator.
struct Operator {
virtual ~Operator() {}
/// apply - Apply this operator to Expr's arguments and insert the result
/// in Elts.
virtual void apply(SetTheory&, DagInit *Expr, RecSet &Elts) =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.
struct Expander {
virtual ~Expander() {}
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.
typedef std::map<Record*, RecVec> ExpandMap;
ExpandMap Expansions;
// Known DAG operators by name.
StringMap<Operator*> Operators;
// Typed expanders by class name.
StringMap<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, 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, Operator*);
/// evaluate - Evaluate Expr and append the resulting set to Elts.
void evaluate(Init *Expr, RecSet &Elts);
/// evaluate - Evaluate a sequence of Inits and append to Elts.
template<typename Iter>
void evaluate(Iter begin, Iter end, RecSet &Elts) {
while (begin != end)
evaluate(*begin++, Elts);
}
/// 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
|
