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 SETTHEORY_H
48#define SETTHEORY_H
49
50#include "llvm/ADT/SetVector.h"
51#include "llvm/ADT/StringMap.h"
52#include "llvm/Support/SourceMgr.h"
53#include <map>
54#include <vector>
55
56namespace llvm {
57
58class DagInit;
59class Init;
60class Record;
61class RecordKeeper;
62
63class SetTheory {
64public:
65  typedef std::vector<Record*> RecVec;
66  typedef SmallSetVector<Record*, 16> RecSet;
67
68  /// Operator - A callback representing a DAG operator.
69  class Operator {
70    virtual void anchor();
71  public:
72    virtual ~Operator() {}
73
74    /// apply - Apply this operator to Expr's arguments and insert the result
75    /// in Elts.
76    virtual void apply(SetTheory&, DagInit *Expr, RecSet &Elts,
77                       ArrayRef<SMLoc> Loc) =0;
78  };
79
80  /// Expander - A callback function that can transform a Record representing a
81  /// set into a fully expanded list of elements. Expanders provide a way for
82  /// users to define named sets that can be used in DAG expressions.
83  class Expander {
84    virtual void anchor();
85  public:
86    virtual ~Expander() {}
87
88    virtual void expand(SetTheory&, Record*, RecSet &Elts) =0;
89  };
90
91private:
92  // Map set defs to their fully expanded contents. This serves as a memoization
93  // cache and it makes it possible to return const references on queries.
94  typedef std::map<Record*, RecVec> ExpandMap;
95  ExpandMap Expansions;
96
97  // Known DAG operators by name.
98  StringMap<Operator*> Operators;
99
100  // Typed expanders by class name.
101  StringMap<Expander*> Expanders;
102
103public:
104  /// Create a SetTheory instance with only the standard operators.
105  SetTheory();
106
107  /// addExpander - Add an expander for Records with the named super class.
108  void addExpander(StringRef ClassName, Expander*);
109
110  /// addFieldExpander - Add an expander for ClassName that simply evaluates
111  /// FieldName in the Record to get the set elements.  That is all that is
112  /// needed for a class like:
113  ///
114  ///   class Set<dag d> {
115  ///     dag Elts = d;
116  ///   }
117  ///
118  void addFieldExpander(StringRef ClassName, StringRef FieldName);
119
120  /// addOperator - Add a DAG operator.
121  void addOperator(StringRef Name, Operator*);
122
123  /// evaluate - Evaluate Expr and append the resulting set to Elts.
124  void evaluate(Init *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc);
125
126  /// evaluate - Evaluate a sequence of Inits and append to Elts.
127  template<typename Iter>
128  void evaluate(Iter begin, Iter end, RecSet &Elts, ArrayRef<SMLoc> Loc) {
129    while (begin != end)
130      evaluate(*begin++, Elts, Loc);
131  }
132
133  /// expand - Expand a record into a set of elements if possible.  Return a
134  /// pointer to the expanded elements, or NULL if Set cannot be expanded
135  /// further.
136  const RecVec *expand(Record *Set);
137};
138
139} // end namespace llvm
140
141#endif
142
143