Home | History | Annotate | Line # | Download | only in TableGen 
      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