LLVM  16.0.0git
SetTheory.h
Go to the documentation of this file.
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 *>;
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.
103 
104  // Typed expanders by class name.
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
llvm::SetTheory::Operator
Operator - A callback representing a DAG operator.
Definition: SetTheory.h:71
llvm::SetTheory::Expander::~Expander
virtual ~Expander()=default
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
StringRef.h
llvm::SetTheory::evaluate
void evaluate(Iter begin, Iter end, RecSet &Elts, ArrayRef< SMLoc > Loc)
evaluate - Evaluate a sequence of Inits and append to Elts.
Definition: SetTheory.h:132
llvm::DagInit
(v a, b) - Represent a DAG tree value.
Definition: Record.h:1390
llvm::SetTheory::addExpander
void addExpander(StringRef ClassName, std::unique_ptr< Expander >)
addExpander - Add an expander for Records with the named super class.
Definition: SetTheory.cpp:273
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::SetTheory
Definition: SetTheory.h:65
llvm::SetTheory::addFieldExpander
void addFieldExpander(StringRef ClassName, StringRef FieldName)
addFieldExpander - Add an expander for ClassName that simply evaluates FieldName in the Record to get...
Definition: SetTheory.cpp:277
llvm::SetTheory::Operator::~Operator
virtual ~Operator()=default
SMLoc.h
llvm::SetTheory::Expander::expand
virtual void expand(SetTheory &, Record *, RecSet &Elts)=0
llvm::SetTheory::Expander
Expander - A callback function that can transform a Record representing a set into a fully expanded l...
Definition: SetTheory.h:86
llvm::StringMap
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:110
ArrayRef.h
llvm::Record
Definition: Record.h:1573
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::SetTheory::Operator::apply
virtual void apply(SetTheory &, DagInit *Expr, RecSet &Elts, ArrayRef< SMLoc > Loc)=0
apply - Apply this operator to Expr's arguments and insert the result in Elts.
llvm::SetTheory::RecVec
std::vector< Record * > RecVec
Definition: SetTheory.h:67
llvm::Init
Definition: Record.h:281
llvm::SetTheory::addOperator
void addOperator(StringRef Name, std::unique_ptr< Operator >)
addOperator - Add a DAG operator.
Definition: SetTheory.cpp:269
llvm::SetTheory::expand
const RecVec * expand(Record *Set)
expand - Expand a record into a set of elements if possible.
Definition: SetTheory.cpp:307
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
StringMap.h
llvm::SetTheory::SetTheory
SetTheory()
Create a SetTheory instance with only the standard operators.
Definition: SetTheory.cpp:256
SetVector.h
llvm::SetTheory::evaluate
void evaluate(Init *Expr, RecSet &Elts, ArrayRef< SMLoc > Loc)
evaluate - Evaluate Expr and append the resulting set to Elts.
Definition: SetTheory.cpp:281