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