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