Line data Source code
1 : // Copyright 2013 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_COMPILER_OPERATOR_H_
6 : #define V8_COMPILER_OPERATOR_H_
7 :
8 : #include <ostream> // NOLINT(readability/streams)
9 :
10 : #include "src/base/compiler-specific.h"
11 : #include "src/base/flags.h"
12 : #include "src/base/functional.h"
13 : #include "src/globals.h"
14 : #include "src/handles.h"
15 : #include "src/zone/zone.h"
16 :
17 : namespace v8 {
18 : namespace internal {
19 : namespace compiler {
20 :
21 : // An operator represents description of the "computation" of a node in the
22 : // compiler IR. A computation takes values (i.e. data) as input and produces
23 : // zero or more values as output. The side-effects of a computation must be
24 : // captured by additional control and data dependencies which are part of the
25 : // IR graph.
26 : // Operators are immutable and describe the statically-known parts of a
27 : // computation. Thus they can be safely shared by many different nodes in the
28 : // IR graph, or even globally between graphs. Operators can have "static
29 : // parameters" which are compile-time constant parameters to the operator, such
30 : // as the name for a named field access, the ID of a runtime function, etc.
31 : // Static parameters are private to the operator and only semantically
32 : // meaningful to the operator itself.
33 : class V8_EXPORT_PRIVATE Operator : public NON_EXPORTED_BASE(ZoneObject) {
34 : public:
35 : using Opcode = uint16_t;
36 :
37 : // Properties inform the operator-independent optimizer about legal
38 : // transformations for nodes that have this operator.
39 : enum Property {
40 : kNoProperties = 0,
41 : kCommutative = 1 << 0, // OP(a, b) == OP(b, a) for all inputs.
42 : kAssociative = 1 << 1, // OP(a, OP(b,c)) == OP(OP(a,b), c) for all inputs.
43 : kIdempotent = 1 << 2, // OP(a); OP(a) == OP(a).
44 : kNoRead = 1 << 3, // Has no scheduling dependency on Effects
45 : kNoWrite = 1 << 4, // Does not modify any Effects and thereby
46 : // create new scheduling dependencies.
47 : kNoThrow = 1 << 5, // Can never generate an exception.
48 : kNoDeopt = 1 << 6, // Can never generate an eager deoptimization exit.
49 : kFoldable = kNoRead | kNoWrite,
50 : kKontrol = kNoDeopt | kFoldable | kNoThrow,
51 : kEliminatable = kNoDeopt | kNoWrite | kNoThrow,
52 : kPure = kNoDeopt | kNoRead | kNoWrite | kNoThrow | kIdempotent
53 : };
54 :
55 : // List of all bits, for the visualizer.
56 : #define OPERATOR_PROPERTY_LIST(V) \
57 : V(Commutative) \
58 : V(Associative) V(Idempotent) V(NoRead) V(NoWrite) V(NoThrow) V(NoDeopt)
59 :
60 : using Properties = base::Flags<Property, uint8_t>;
61 : enum class PrintVerbosity { kVerbose, kSilent };
62 :
63 : // Constructor.
64 : Operator(Opcode opcode, Properties properties, const char* mnemonic,
65 : size_t value_in, size_t effect_in, size_t control_in,
66 : size_t value_out, size_t effect_out, size_t control_out);
67 :
68 365493 : virtual ~Operator() = default;
69 :
70 : // A small integer unique to all instances of a particular kind of operator,
71 : // useful for quick matching for specific kinds of operators. For fast access
72 : // the opcode is stored directly in the operator object.
73 : Opcode opcode() const { return opcode_; }
74 :
75 : // Returns a constant string representing the mnemonic of the operator,
76 : // without the static parameters. Useful for debugging.
77 : const char* mnemonic() const { return mnemonic_; }
78 :
79 : // Check if this operator equals another operator. Equivalent operators can
80 : // be merged, and nodes with equivalent operators and equivalent inputs
81 : // can be merged.
82 12489031 : virtual bool Equals(const Operator* that) const {
83 12489101 : return this->opcode() == that->opcode();
84 : }
85 :
86 : // Compute a hashcode to speed up equivalence-set checking.
87 : // Equal operators should always have equal hashcodes, and unequal operators
88 : // should have unequal hashcodes with high probability.
89 36418612 : virtual size_t HashCode() const { return base::hash<Opcode>()(opcode()); }
90 :
91 : // Check whether this operator has the given property.
92 : bool HasProperty(Property property) const {
93 : return (properties() & property) == property;
94 : }
95 :
96 : Properties properties() const { return properties_; }
97 :
98 : // TODO(titzer): convert return values here to size_t.
99 1532953868 : int ValueInputCount() const { return value_in_; }
100 1505084917 : int EffectInputCount() const { return effect_in_; }
101 708622008 : int ControlInputCount() const { return control_in_; }
102 :
103 151030763 : int ValueOutputCount() const { return value_out_; }
104 122618372 : int EffectOutputCount() const { return effect_out_; }
105 227234699 : int ControlOutputCount() const { return control_out_; }
106 :
107 : static size_t ZeroIfEliminatable(Properties properties) {
108 5645932 : return (properties & kEliminatable) == kEliminatable ? 0 : 1;
109 : }
110 :
111 : static size_t ZeroIfNoThrow(Properties properties) {
112 5645932 : return (properties & kNoThrow) == kNoThrow ? 0 : 2;
113 : }
114 :
115 : static size_t ZeroIfPure(Properties properties) {
116 11291864 : return (properties & kPure) == kPure ? 0 : 1;
117 : }
118 :
119 : // TODO(titzer): API for input and output types, for typechecking graph.
120 :
121 : // Print the full operator into the given stream, including any
122 : // static parameters. Useful for debugging and visualizing the IR.
123 : void PrintTo(std::ostream& os,
124 : PrintVerbosity verbose = PrintVerbosity::kVerbose) const {
125 : // We cannot make PrintTo virtual, because default arguments to virtual
126 : // methods are banned in the style guide.
127 2364 : return PrintToImpl(os, verbose);
128 : }
129 :
130 : void PrintPropsTo(std::ostream& os) const;
131 :
132 : protected:
133 : virtual void PrintToImpl(std::ostream& os, PrintVerbosity verbose) const;
134 :
135 : private:
136 : const char* mnemonic_;
137 : Opcode opcode_;
138 : Properties properties_;
139 : uint32_t value_in_;
140 : uint32_t effect_in_;
141 : uint32_t control_in_;
142 : uint32_t value_out_;
143 : uint8_t effect_out_;
144 : uint32_t control_out_;
145 :
146 : DISALLOW_COPY_AND_ASSIGN(Operator);
147 : };
148 :
149 : DEFINE_OPERATORS_FOR_FLAGS(Operator::Properties)
150 :
151 : V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os,
152 : const Operator& op);
153 :
154 : // Default equality function for below Operator1<*> class.
155 : template <typename T>
156 : struct OpEqualTo : public std::equal_to<T> {};
157 :
158 :
159 : // Default hashing function for below Operator1<*> class.
160 : template <typename T>
161 : struct OpHash : public base::hash<T> {};
162 :
163 :
164 : // A templatized implementation of Operator that has one static parameter of
165 : // type {T} with the proper default equality and hashing functions.
166 : template <typename T, typename Pred = OpEqualTo<T>, typename Hash = OpHash<T>>
167 210 : class Operator1 : public Operator {
168 : public:
169 : Operator1(Opcode opcode, Properties properties, const char* mnemonic,
170 : size_t value_in, size_t effect_in, size_t control_in,
171 : size_t value_out, size_t effect_out, size_t control_out,
172 : T parameter, Pred const& pred = Pred(), Hash const& hash = Hash())
173 : : Operator(opcode, properties, mnemonic, value_in, effect_in, control_in,
174 : value_out, effect_out, control_out),
175 : parameter_(parameter),
176 : pred_(pred),
177 113571802 : hash_(hash) {}
178 :
179 128447106 : T const& parameter() const { return parameter_; }
180 :
181 75346626 : bool Equals(const Operator* other) const final {
182 75346796 : if (opcode() != other->opcode()) return false;
183 : const Operator1<T, Pred, Hash>* that =
184 : reinterpret_cast<const Operator1<T, Pred, Hash>*>(other);
185 30485965 : return this->pred_(this->parameter(), that->parameter());
186 : }
187 125204623 : size_t HashCode() const final {
188 146209974 : return base::hash_combine(this->opcode(), this->hash_(this->parameter()));
189 : }
190 : // For most parameter types, we have only a verbose way to print them, namely
191 : // ostream << parameter. But for some types it is particularly useful to have
192 : // a shorter way to print them for the node labels in Turbolizer. The
193 : // following method can be overridden to provide a concise and a verbose
194 : // printing of a parameter.
195 :
196 1951 : virtual void PrintParameter(std::ostream& os, PrintVerbosity verbose) const {
197 2540 : os << "[" << parameter() << "]";
198 1951 : }
199 :
200 1983 : void PrintToImpl(std::ostream& os, PrintVerbosity verbose) const override {
201 1983 : os << mnemonic();
202 1983 : PrintParameter(os, verbose);
203 1983 : }
204 :
205 : private:
206 : T const parameter_;
207 : Pred const pred_;
208 : Hash const hash_;
209 : };
210 :
211 :
212 : // Helper to extract parameters from Operator1<*> operator.
213 : template <typename T>
214 : inline T const& OpParameter(const Operator* op) {
215 : return reinterpret_cast<const Operator1<T, OpEqualTo<T>, OpHash<T>>*>(op)
216 : ->parameter();
217 : }
218 :
219 :
220 : // NOTE: We have to be careful to use the right equal/hash functions below, for
221 : // float/double we always use the ones operating on the bit level, for Handle<>
222 : // we always use the ones operating on the location level.
223 : template <>
224 : struct OpEqualTo<float> : public base::bit_equal_to<float> {};
225 : template <>
226 : struct OpHash<float> : public base::bit_hash<float> {};
227 :
228 : template <>
229 : struct OpEqualTo<double> : public base::bit_equal_to<double> {};
230 : template <>
231 : struct OpHash<double> : public base::bit_hash<double> {};
232 :
233 : template <>
234 : struct OpEqualTo<Handle<HeapObject>> : public Handle<HeapObject>::equal_to {};
235 : template <>
236 : struct OpHash<Handle<HeapObject>> : public Handle<HeapObject>::hash {};
237 :
238 : template <>
239 : struct OpEqualTo<Handle<String>> : public Handle<String>::equal_to {};
240 : template <>
241 : struct OpHash<Handle<String>> : public Handle<String>::hash {};
242 :
243 : template <>
244 : struct OpEqualTo<Handle<ScopeInfo>> : public Handle<ScopeInfo>::equal_to {};
245 : template <>
246 : struct OpHash<Handle<ScopeInfo>> : public Handle<ScopeInfo>::hash {};
247 :
248 : } // namespace compiler
249 : } // namespace internal
250 : } // namespace v8
251 :
252 : #endif // V8_COMPILER_OPERATOR_H_
|