1 //===- SetTheory.h - Generate ordered sets from DAG expressions -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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.
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.
22 // - (add S1, S2 ...) Union sets. This is also how sets are created from element
25 // - (sub S1, S2, ...) Set difference. Every element in S1 except for the
26 // elements in S2, ...
28 // - (and S1, S2) Set intersection. Every element in S1 that is also in S2.
30 // - (shl S, N) Shift left. Remove the first N elements from S.
32 // - (trunc S, N) Truncate. The first N elements of S.
34 // - (rotl S, N) Rotate left. Same as (add (shl S, N), (trunc S, N)).
36 // - (rotr S, N) Rotate right.
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
42 // - (sequence "Format", From, To) Generate a sequence of defs with printf.
43 // For instance, (sequence "R%u", 0, 3) -> [ R0, R1, R2, R3 ]
45 //===----------------------------------------------------------------------===//
50 #include "llvm/ADT/StringMap.h"
51 #include "llvm/ADT/SetVector.h"
64 typedef std::vector<Record*> RecVec;
65 typedef SmallSetVector<Record*, 16> RecSet;
67 /// Operator - A callback representing a DAG operator.
69 /// apply - Apply this operator to Expr's arguments and insert the result
71 virtual void apply(SetTheory&, DagInit *Expr, RecSet &Elts) =0;
74 /// Expander - A callback function that can transform a Record representing a
75 /// set into a fully expanded list of elements. Expanders provide a way for
76 /// users to define named sets that can be used in DAG expressions.
78 virtual void expand(SetTheory&, Record*, RecSet &Elts) =0;
82 // Map set defs to their fully expanded contents. This serves as a memoization
83 // cache and it makes it possible to return const references on queries.
84 typedef std::map<Record*, RecVec> ExpandMap;
87 // Known DAG operators by name.
88 StringMap<Operator*> Operators;
90 // Typed expanders by class name.
91 StringMap<Expander*> Expanders;
94 /// Create a SetTheory instance with only the standard operators.
95 /// A 'sequence' operator will only be added if a RecordKeeper is given.
96 SetTheory(RecordKeeper *Records = 0);
98 /// addExpander - Add an expander for Records with the named super class.
99 void addExpander(StringRef ClassName, Expander*);
101 /// addFieldExpander - Add an expander for ClassName that simply evaluates
102 /// FieldName in the Record to get the set elements. That is all that is
103 /// needed for a class like:
105 /// class Set<dag d> {
109 void addFieldExpander(StringRef ClassName, StringRef FieldName);
111 /// addOperator - Add a DAG operator.
112 void addOperator(StringRef Name, Operator*);
114 /// evaluate - Evaluate Expr and append the resulting set to Elts.
115 void evaluate(Init *Expr, RecSet &Elts);
117 /// evaluate - Evaluate a sequence of Inits and append to Elts.
118 template<typename Iter>
119 void evaluate(Iter begin, Iter end, RecSet &Elts) {
121 evaluate(*begin++, Elts);
124 /// expand - Expand a record into a set of elements if possible. Return a
125 /// pointer to the expanded elements, or NULL if Set cannot be expanded
127 const RecVec *expand(Record *Set);
130 } // end namespace llvm