LLVM 20.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
59namespace llvm {
60
61class DagInit;
62class Init;
63class Record;
64
65class SetTheory {
66public:
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
95private:
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
107public:
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
This file defines the StringMap class.
std::string Name
This file implements a set that has insertion order iteration characteristics.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
(v a, b) - Represent a DAG tree value.
Definition: Record.h:1445
Expander - A callback function that can transform a Record representing a set into a fully expanded l...
Definition: SetTheory.h:86
virtual void expand(SetTheory &, Record *, RecSet &Elts)=0
virtual ~Expander()=default
Operator - A callback representing a DAG operator.
Definition: SetTheory.h:71
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.
virtual ~Operator()=default
const RecVec * expand(Record *Set)
expand - Expand a record into a set of elements if possible.
Definition: SetTheory.cpp:307
void addOperator(StringRef Name, std::unique_ptr< Operator >)
addOperator - Add a DAG operator.
Definition: SetTheory.cpp:269
SetTheory()
Create a SetTheory instance with only the standard operators.
Definition: SetTheory.cpp:256
void evaluate(Init *Expr, RecSet &Elts, ArrayRef< SMLoc > Loc)
evaluate - Evaluate Expr and append the resulting set to Elts.
Definition: SetTheory.cpp:281
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
std::vector< Record * > RecVec
Definition: SetTheory.h:67
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
void addExpander(StringRef ClassName, std::unique_ptr< Expander >)
addExpander - Add an expander for Records with the named super class.
Definition: SetTheory.cpp:273
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:128
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18