include/llvm/TableGen/SetTheory.h

   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