include/llvm/TableGen/SetTheory.h

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