Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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, [Stride]) Generate a sequence of defs with
  42. //   printf. For instance, (sequence "R%u", 0, 3) -> [ R0, R1, R2, R3 ] and
  43. //   (sequence "R%u", 20, 30, 5) -> [ R20, R25, R30 ].
  44. //
  45. //===----------------------------------------------------------------------===//
  46.  
  47. #ifndef LLVM_TABLEGEN_SETTHEORY_H
  48. #define LLVM_TABLEGEN_SETTHEORY_H
  49.  
  50. #include "llvm/ADT/ArrayRef.h"
  51. #include "llvm/ADT/SetVector.h"
  52. #include "llvm/ADT/StringMap.h"
  53. #include "llvm/ADT/StringRef.h"
  54. #include "llvm/Support/SMLoc.h"
  55. #include <map>
  56. #include <memory>
  57. #include <vector>
  58.  
  59. namespace llvm {
  60.  
  61. class DagInit;
  62. class Init;
  63. class Record;
  64.  
  65. class SetTheory {
  66. public:
  67.   using RecVec = std::vector<Record *>;
  68.   using RecSet = SmallSetVector<Record *, 16>;
  69.  
  70.   /// Operator - A callback representing a DAG operator.
  71.   class Operator {
  72.     virtual void anchor();
  73.  
  74.   public:
  75.     virtual ~Operator() = default;
  76.  
  77.     /// apply - Apply this operator to Expr's arguments and insert the result
  78.     /// in Elts.
  79.     virtual void apply(SetTheory&, DagInit *Expr, RecSet &Elts,
  80.                        ArrayRef<SMLoc> Loc) = 0;
  81.   };
  82.  
  83.   /// Expander - A callback function that can transform a Record representing a
  84.   /// set into a fully expanded list of elements. Expanders provide a way for
  85.   /// users to define named sets that can be used in DAG expressions.
  86.   class Expander {
  87.     virtual void anchor();
  88.  
  89.   public:
  90.     virtual ~Expander() = default;
  91.  
  92.     virtual void expand(SetTheory&, Record*, RecSet &Elts) = 0;
  93.   };
  94.  
  95. private:
  96.   // Map set defs to their fully expanded contents. This serves as a memoization
  97.   // cache and it makes it possible to return const references on queries.
  98.   using ExpandMap = std::map<Record *, RecVec>;
  99.   ExpandMap Expansions;
  100.  
  101.   // Known DAG operators by name.
  102.   StringMap<std::unique_ptr<Operator>> Operators;
  103.  
  104.   // Typed expanders by class name.
  105.   StringMap<std::unique_ptr<Expander>> Expanders;
  106.  
  107. public:
  108.   /// Create a SetTheory instance with only the standard operators.
  109.   SetTheory();
  110.  
  111.   /// addExpander - Add an expander for Records with the named super class.
  112.   void addExpander(StringRef ClassName, std::unique_ptr<Expander>);
  113.  
  114.   /// addFieldExpander - Add an expander for ClassName that simply evaluates
  115.   /// FieldName in the Record to get the set elements.  That is all that is
  116.   /// needed for a class like:
  117.   ///
  118.   ///   class Set<dag d> {
  119.   ///     dag Elts = d;
  120.   ///   }
  121.   ///
  122.   void addFieldExpander(StringRef ClassName, StringRef FieldName);
  123.  
  124.   /// addOperator - Add a DAG operator.
  125.   void addOperator(StringRef Name, std::unique_ptr<Operator>);
  126.  
  127.   /// evaluate - Evaluate Expr and append the resulting set to Elts.
  128.   void evaluate(Init *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc);
  129.  
  130.   /// evaluate - Evaluate a sequence of Inits and append to Elts.
  131.   template<typename Iter>
  132.   void evaluate(Iter begin, Iter end, RecSet &Elts, ArrayRef<SMLoc> Loc) {
  133.     while (begin != end)
  134.       evaluate(*begin++, Elts, Loc);
  135.   }
  136.  
  137.   /// expand - Expand a record into a set of elements if possible.  Return a
  138.   /// pointer to the expanded elements, or NULL if Set cannot be expanded
  139.   /// further.
  140.   const RecVec *expand(Record *Set);
  141. };
  142.  
  143. } // end namespace llvm
  144.  
  145. #endif // LLVM_TABLEGEN_SETTHEORY_H
  146.