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