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