1223013Sdim//===- SetTheory.h - Generate ordered sets from DAG expressions -*- C++ -*-===// 2223013Sdim// 3223013Sdim// The LLVM Compiler Infrastructure 4223013Sdim// 5223013Sdim// This file is distributed under the University of Illinois Open Source 6223013Sdim// License. See LICENSE.TXT for details. 7223013Sdim// 8223013Sdim//===----------------------------------------------------------------------===// 9223013Sdim// 10223013Sdim// This file implements the SetTheory class that computes ordered sets of 11223013Sdim// Records from DAG expressions. Operators for standard set operations are 12223013Sdim// predefined, and it is possible to add special purpose set operators as well. 13223013Sdim// 14223013Sdim// The user may define named sets as Records of predefined classes. Set 15223013Sdim// expanders can be added to a SetTheory instance to teach it how to find the 16223013Sdim// elements of such a named set. 17223013Sdim// 18223013Sdim// These are the predefined operators. The argument lists can be individual 19223013Sdim// elements (defs), other sets (defs of expandable classes), lists, or DAG 20223013Sdim// expressions that are evaluated recursively. 21223013Sdim// 22223013Sdim// - (add S1, S2 ...) Union sets. This is also how sets are created from element 23223013Sdim// lists. 24223013Sdim// 25223013Sdim// - (sub S1, S2, ...) Set difference. Every element in S1 except for the 26223013Sdim// elements in S2, ... 27223013Sdim// 28223013Sdim// - (and S1, S2) Set intersection. Every element in S1 that is also in S2. 29223013Sdim// 30223013Sdim// - (shl S, N) Shift left. Remove the first N elements from S. 31223013Sdim// 32223013Sdim// - (trunc S, N) Truncate. The first N elements of S. 33223013Sdim// 34223013Sdim// - (rotl S, N) Rotate left. Same as (add (shl S, N), (trunc S, N)). 35223013Sdim// 36223013Sdim// - (rotr S, N) Rotate right. 37223013Sdim// 38223013Sdim// - (decimate S, N) Decimate S by picking every N'th element, starting with 39223013Sdim// the first one. For instance, (decimate S, 2) returns the even elements of 40223013Sdim// S. 41223013Sdim// 42223013Sdim// - (sequence "Format", From, To) Generate a sequence of defs with printf. 43223013Sdim// For instance, (sequence "R%u", 0, 3) -> [ R0, R1, R2, R3 ] 44223013Sdim// 45223013Sdim//===----------------------------------------------------------------------===// 46223013Sdim 47223013Sdim#ifndef SETTHEORY_H 48223013Sdim#define SETTHEORY_H 49223013Sdim 50252723Sdim#include "llvm/ADT/SetVector.h" 51223013Sdim#include "llvm/ADT/StringMap.h" 52245431Sdim#include "llvm/Support/SourceMgr.h" 53223013Sdim#include <map> 54223013Sdim#include <vector> 55223013Sdim 56223013Sdimnamespace llvm { 57223013Sdim 58223013Sdimclass DagInit; 59224145Sdimclass Init; 60223013Sdimclass Record; 61223013Sdimclass RecordKeeper; 62223013Sdim 63223013Sdimclass SetTheory { 64223013Sdimpublic: 65223013Sdim typedef std::vector<Record*> RecVec; 66223013Sdim typedef SmallSetVector<Record*, 16> RecSet; 67223013Sdim 68223013Sdim /// Operator - A callback representing a DAG operator. 69235633Sdim class Operator { 70235633Sdim virtual void anchor(); 71235633Sdim public: 72223013Sdim virtual ~Operator() {} 73223013Sdim 74223013Sdim /// apply - Apply this operator to Expr's arguments and insert the result 75223013Sdim /// in Elts. 76245431Sdim virtual void apply(SetTheory&, DagInit *Expr, RecSet &Elts, 77245431Sdim ArrayRef<SMLoc> Loc) =0; 78223013Sdim }; 79223013Sdim 80223013Sdim /// Expander - A callback function that can transform a Record representing a 81223013Sdim /// set into a fully expanded list of elements. Expanders provide a way for 82223013Sdim /// users to define named sets that can be used in DAG expressions. 83235633Sdim class Expander { 84235633Sdim virtual void anchor(); 85235633Sdim public: 86223013Sdim virtual ~Expander() {} 87223013Sdim 88223013Sdim virtual void expand(SetTheory&, Record*, RecSet &Elts) =0; 89223013Sdim }; 90223013Sdim 91223013Sdimprivate: 92223013Sdim // Map set defs to their fully expanded contents. This serves as a memoization 93223013Sdim // cache and it makes it possible to return const references on queries. 94223013Sdim typedef std::map<Record*, RecVec> ExpandMap; 95223013Sdim ExpandMap Expansions; 96223013Sdim 97223013Sdim // Known DAG operators by name. 98223013Sdim StringMap<Operator*> Operators; 99223013Sdim 100223013Sdim // Typed expanders by class name. 101223013Sdim StringMap<Expander*> Expanders; 102223013Sdim 103223013Sdimpublic: 104223013Sdim /// Create a SetTheory instance with only the standard operators. 105223013Sdim SetTheory(); 106223013Sdim 107223013Sdim /// addExpander - Add an expander for Records with the named super class. 108223013Sdim void addExpander(StringRef ClassName, Expander*); 109223013Sdim 110223013Sdim /// addFieldExpander - Add an expander for ClassName that simply evaluates 111223013Sdim /// FieldName in the Record to get the set elements. That is all that is 112223013Sdim /// needed for a class like: 113223013Sdim /// 114223013Sdim /// class Set<dag d> { 115223013Sdim /// dag Elts = d; 116223013Sdim /// } 117223013Sdim /// 118223013Sdim void addFieldExpander(StringRef ClassName, StringRef FieldName); 119223013Sdim 120223013Sdim /// addOperator - Add a DAG operator. 121223013Sdim void addOperator(StringRef Name, Operator*); 122223013Sdim 123223013Sdim /// evaluate - Evaluate Expr and append the resulting set to Elts. 124245431Sdim void evaluate(Init *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc); 125223013Sdim 126223013Sdim /// evaluate - Evaluate a sequence of Inits and append to Elts. 127223013Sdim template<typename Iter> 128245431Sdim void evaluate(Iter begin, Iter end, RecSet &Elts, ArrayRef<SMLoc> Loc) { 129223013Sdim while (begin != end) 130245431Sdim evaluate(*begin++, Elts, Loc); 131223013Sdim } 132223013Sdim 133223013Sdim /// expand - Expand a record into a set of elements if possible. Return a 134223013Sdim /// pointer to the expanded elements, or NULL if Set cannot be expanded 135223013Sdim /// further. 136223013Sdim const RecVec *expand(Record *Set); 137223013Sdim}; 138223013Sdim 139223013Sdim} // end namespace llvm 140223013Sdim 141223013Sdim#endif 142223013Sdim 143