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 : typedef uint16_t Opcode;
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 : typedef base::Flags<Property, uint8_t> Properties;
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 0 : virtual ~Operator() {}
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 10107014 : virtual bool Equals(const Operator* that) const {
83 10107014 : 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 24383682 : 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(bmeurer): Use bit fields below?
99 : static const size_t kMaxControlOutputCount = (1u << 16) - 1;
100 :
101 : // TODO(titzer): convert return values here to size_t.
102 1062072522 : int ValueInputCount() const { return value_in_; }
103 768504902 : int EffectInputCount() const { return effect_in_; }
104 361842775 : int ControlInputCount() const { return control_in_; }
105 :
106 4962650 : int ValueOutputCount() const { return value_out_; }
107 17792688 : int EffectOutputCount() const { return effect_out_; }
108 140586292 : int ControlOutputCount() const { return control_out_; }
109 :
110 : static size_t ZeroIfEliminatable(Properties properties) {
111 3360787 : return (properties & kEliminatable) == kEliminatable ? 0 : 1;
112 : }
113 :
114 : static size_t ZeroIfNoThrow(Properties properties) {
115 3360787 : return (properties & kNoThrow) == kNoThrow ? 0 : 2;
116 : }
117 :
118 : static size_t ZeroIfPure(Properties properties) {
119 6721574 : return (properties & kPure) == kPure ? 0 : 1;
120 : }
121 :
122 : // TODO(titzer): API for input and output types, for typechecking graph.
123 :
124 : // Print the full operator into the given stream, including any
125 : // static parameters. Useful for debugging and visualizing the IR.
126 : void PrintTo(std::ostream& os,
127 : PrintVerbosity verbose = PrintVerbosity::kVerbose) const {
128 : // We cannot make PrintTo virtual, because default arguments to virtual
129 : // methods are banned in the style guide.
130 434 : return PrintToImpl(os, verbose);
131 : }
132 :
133 : void PrintPropsTo(std::ostream& os) const;
134 :
135 : protected:
136 : virtual void PrintToImpl(std::ostream& os, PrintVerbosity verbose) const;
137 :
138 : private:
139 : Opcode opcode_;
140 : Properties properties_;
141 : const char* mnemonic_;
142 : uint32_t value_in_;
143 : uint16_t effect_in_;
144 : uint16_t control_in_;
145 : uint16_t value_out_;
146 : uint8_t effect_out_;
147 : uint32_t control_out_;
148 :
149 : DISALLOW_COPY_AND_ASSIGN(Operator);
150 : };
151 :
152 : DEFINE_OPERATORS_FOR_FLAGS(Operator::Properties)
153 :
154 : std::ostream& operator<<(std::ostream& os, const Operator& op);
155 :
156 :
157 : // Default equality function for below Operator1<*> class.
158 : template <typename T>
159 : struct OpEqualTo : public std::equal_to<T> {};
160 :
161 :
162 : // Default hashing function for below Operator1<*> class.
163 : template <typename T>
164 : struct OpHash : public base::hash<T> {};
165 :
166 :
167 : // A templatized implementation of Operator that has one static parameter of
168 : // type {T} with the proper default equality and hashing functions.
169 : template <typename T, typename Pred = OpEqualTo<T>, typename Hash = OpHash<T>>
170 0 : class Operator1 : public Operator {
171 : public:
172 : Operator1(Opcode opcode, Properties properties, const char* mnemonic,
173 : size_t value_in, size_t effect_in, size_t control_in,
174 : size_t value_out, size_t effect_out, size_t control_out,
175 : T parameter, Pred const& pred = Pred(), Hash const& hash = Hash())
176 : : Operator(opcode, properties, mnemonic, value_in, effect_in, control_in,
177 : value_out, effect_out, control_out),
178 : parameter_(parameter),
179 : pred_(pred),
180 75411738 : hash_(hash) {}
181 :
182 : T const& parameter() const { return parameter_; }
183 :
184 124778206 : bool Equals(const Operator* other) const final {
185 124778206 : if (opcode() != other->opcode()) return false;
186 : const Operator1<T, Pred, Hash>* that =
187 : reinterpret_cast<const Operator1<T, Pred, Hash>*>(other);
188 35283773 : return this->pred_(this->parameter(), that->parameter());
189 : }
190 75146328 : size_t HashCode() const final {
191 213708065 : return base::hash_combine(this->opcode(), this->hash_(this->parameter()));
192 : }
193 : // For most parameter types, we have only a verbose way to print them, namely
194 : // ostream << parameter. But for some types it is particularly useful to have
195 : // a shorter way to print them for the node labels in Turbolizer. The
196 : // following method can be overridden to provide a concise and a verbose
197 : // printing of a parameter.
198 :
199 77 : virtual void PrintParameter(std::ostream& os, PrintVerbosity verbose) const {
200 77 : os << "[" << parameter() << "]";
201 77 : }
202 :
203 77 : virtual void PrintToImpl(std::ostream& os, PrintVerbosity verbose) const {
204 77 : os << mnemonic();
205 77 : PrintParameter(os, verbose);
206 77 : }
207 :
208 : private:
209 : T const parameter_;
210 : Pred const pred_;
211 : Hash const hash_;
212 : };
213 :
214 :
215 : // Helper to extract parameters from Operator1<*> operator.
216 : template <typename T>
217 : inline T const& OpParameter(const Operator* op) {
218 : return reinterpret_cast<const Operator1<T, OpEqualTo<T>, OpHash<T>>*>(op)
219 : ->parameter();
220 : }
221 :
222 :
223 : // NOTE: We have to be careful to use the right equal/hash functions below, for
224 : // float/double we always use the ones operating on the bit level, for Handle<>
225 : // we always use the ones operating on the location level.
226 : template <>
227 : struct OpEqualTo<float> : public base::bit_equal_to<float> {};
228 : template <>
229 : struct OpHash<float> : public base::bit_hash<float> {};
230 :
231 : template <>
232 : struct OpEqualTo<double> : public base::bit_equal_to<double> {};
233 : template <>
234 : struct OpHash<double> : public base::bit_hash<double> {};
235 :
236 : template <>
237 : struct OpEqualTo<Handle<HeapObject>> : public Handle<HeapObject>::equal_to {};
238 : template <>
239 : struct OpHash<Handle<HeapObject>> : public Handle<HeapObject>::hash {};
240 :
241 : template <>
242 : struct OpEqualTo<Handle<String>> : public Handle<String>::equal_to {};
243 : template <>
244 : struct OpHash<Handle<String>> : public Handle<String>::hash {};
245 :
246 : template <>
247 : struct OpEqualTo<Handle<ScopeInfo>> : public Handle<ScopeInfo>::equal_to {};
248 : template <>
249 : struct OpHash<Handle<ScopeInfo>> : public Handle<ScopeInfo>::hash {};
250 :
251 : } // namespace compiler
252 : } // namespace internal
253 : } // namespace v8
254 :
255 : #endif // V8_COMPILER_OPERATOR_H_
|