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