//===- SetTheory.h - Generate ordered sets from DAG expressions -*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file implements the SetTheory class that computes ordered sets of // Records from DAG expressions. Operators for standard set operations are // predefined, and it is possible to add special purpose set operators as well. // // The user may define named sets as Records of predefined classes. Set // expanders can be added to a SetTheory instance to teach it how to find the // elements of such a named set. // // These are the predefined operators. The argument lists can be individual // elements (defs), other sets (defs of expandable classes), lists, or DAG // expressions that are evaluated recursively. // // - (add S1, S2 ...) Union sets. This is also how sets are created from element // lists. // // - (sub S1, S2, ...) Set difference. Every element in S1 except for the // elements in S2, ... // // - (and S1, S2) Set intersection. Every element in S1 that is also in S2. // // - (shl S, N) Shift left. Remove the first N elements from S. // // - (trunc S, N) Truncate. The first N elements of S. // // - (rotl S, N) Rotate left. Same as (add (shl S, N), (trunc S, N)). // // - (rotr S, N) Rotate right. // // - (decimate S, N) Decimate S by picking every N'th element, starting with // the first one. For instance, (decimate S, 2) returns the even elements of // S. // // - (sequence "Format", From, To, [Stride]) Generate a sequence of defs with // printf. For instance, (sequence "R%u", 0, 3) -> [ R0, R1, R2, R3 ] and // (sequence "R%u", 20, 30, 5) -> [ R20, R25, R30 ]. // //===----------------------------------------------------------------------===// #ifndef LLVM_TABLEGEN_SETTHEORY_H #define LLVM_TABLEGEN_SETTHEORY_H #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringRef.h" #include "llvm/Support/SMLoc.h" #include #include #include namespace llvm { class DagInit; class Init; class Record; class SetTheory { public: using RecVec = std::vector; using RecSet = SmallSetVector; /// Operator - A callback representing a DAG operator. class Operator { virtual void anchor(); public: virtual ~Operator() = default; /// apply - Apply this operator to Expr's arguments and insert the result /// in Elts. virtual void apply(SetTheory&, DagInit *Expr, RecSet &Elts, ArrayRef Loc) = 0; }; /// Expander - A callback function that can transform a Record representing a /// set into a fully expanded list of elements. Expanders provide a way for /// users to define named sets that can be used in DAG expressions. class Expander { virtual void anchor(); public: virtual ~Expander() = default; virtual void expand(SetTheory&, Record*, RecSet &Elts) = 0; }; private: // Map set defs to their fully expanded contents. This serves as a memoization // cache and it makes it possible to return const references on queries. using ExpandMap = std::map; ExpandMap Expansions; // Known DAG operators by name. StringMap> Operators; // Typed expanders by class name. StringMap> Expanders; public: /// Create a SetTheory instance with only the standard operators. SetTheory(); /// addExpander - Add an expander for Records with the named super class. void addExpander(StringRef ClassName, std::unique_ptr); /// addFieldExpander - Add an expander for ClassName that simply evaluates /// FieldName in the Record to get the set elements. That is all that is /// needed for a class like: /// /// class Set { /// dag Elts = d; /// } /// void addFieldExpander(StringRef ClassName, StringRef FieldName); /// addOperator - Add a DAG operator. void addOperator(StringRef Name, std::unique_ptr); /// evaluate - Evaluate Expr and append the resulting set to Elts. void evaluate(Init *Expr, RecSet &Elts, ArrayRef Loc); /// evaluate - Evaluate a sequence of Inits and append to Elts. template void evaluate(Iter begin, Iter end, RecSet &Elts, ArrayRef Loc) { while (begin != end) evaluate(*begin++, Elts, Loc); } /// expand - Expand a record into a set of elements if possible. Return a /// pointer to the expanded elements, or NULL if Set cannot be expanded /// further. const RecVec *expand(Record *Set); }; } // end namespace llvm #endif // LLVM_TABLEGEN_SETTHEORY_H