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 "src/base/flags.h"
9#include "src/ostreams.h"
10#include "src/unique.h"
11
12namespace v8 {
13namespace internal {
14namespace compiler {
15
16// An operator represents description of the "computation" of a node in the
17// compiler IR. A computation takes values (i.e. data) as input and produces
18// zero or more values as output. The side-effects of a computation must be
19// captured by additional control and data dependencies which are part of the
20// IR graph.
21// Operators are immutable and describe the statically-known parts of a
22// computation. Thus they can be safely shared by many different nodes in the
23// IR graph, or even globally between graphs. Operators can have "static
24// parameters" which are compile-time constant parameters to the operator, such
25// as the name for a named field access, the ID of a runtime function, etc.
26// Static parameters are private to the operator and only semantically
27// meaningful to the operator itself.
28class Operator : public ZoneObject {
29 public:
30  typedef uint8_t Opcode;
31
32  // Properties inform the operator-independent optimizer about legal
33  // transformations for nodes that have this operator.
34  enum Property {
35    kNoProperties = 0,
36    kReducible = 1 << 0,    // Participates in strength reduction.
37    kCommutative = 1 << 1,  // OP(a, b) == OP(b, a) for all inputs.
38    kAssociative = 1 << 2,  // OP(a, OP(b,c)) == OP(OP(a,b), c) for all inputs.
39    kIdempotent = 1 << 3,   // OP(a); OP(a) == OP(a).
40    kNoRead = 1 << 4,       // Has no scheduling dependency on Effects
41    kNoWrite = 1 << 5,      // Does not modify any Effects and thereby
42                            // create new scheduling dependencies.
43    kNoThrow = 1 << 6,      // Can never generate an exception.
44    kFoldable = kNoRead | kNoWrite,
45    kEliminatable = kNoWrite | kNoThrow,
46    kPure = kNoRead | kNoWrite | kNoThrow | kIdempotent
47  };
48  typedef base::Flags<Property, uint8_t> Properties;
49
50  Operator(Opcode opcode, Properties properties, const char* mnemonic)
51      : opcode_(opcode), properties_(properties), mnemonic_(mnemonic) {}
52  virtual ~Operator();
53
54  // A small integer unique to all instances of a particular kind of operator,
55  // useful for quick matching for specific kinds of operators. For fast access
56  // the opcode is stored directly in the operator object.
57  Opcode opcode() const { return opcode_; }
58
59  // Returns a constant string representing the mnemonic of the operator,
60  // without the static parameters. Useful for debugging.
61  const char* mnemonic() const { return mnemonic_; }
62
63  // Check if this operator equals another operator. Equivalent operators can
64  // be merged, and nodes with equivalent operators and equivalent inputs
65  // can be merged.
66  virtual bool Equals(const Operator* other) const = 0;
67
68  // Compute a hashcode to speed up equivalence-set checking.
69  // Equal operators should always have equal hashcodes, and unequal operators
70  // should have unequal hashcodes with high probability.
71  virtual int HashCode() const = 0;
72
73  // Check whether this operator has the given property.
74  bool HasProperty(Property property) const {
75    return (properties() & property) == property;
76  }
77
78  // Number of data inputs to the operator, for verifying graph structure.
79  virtual int InputCount() const = 0;
80
81  // Number of data outputs from the operator, for verifying graph structure.
82  virtual int OutputCount() const = 0;
83
84  Properties properties() const { return properties_; }
85
86  // TODO(titzer): API for input and output types, for typechecking graph.
87 protected:
88  // Print the full operator into the given stream, including any
89  // static parameters. Useful for debugging and visualizing the IR.
90  virtual OStream& PrintTo(OStream& os) const = 0;  // NOLINT
91  friend OStream& operator<<(OStream& os, const Operator& op);
92
93 private:
94  Opcode opcode_;
95  Properties properties_;
96  const char* mnemonic_;
97
98  DISALLOW_COPY_AND_ASSIGN(Operator);
99};
100
101DEFINE_OPERATORS_FOR_FLAGS(Operator::Properties)
102
103OStream& operator<<(OStream& os, const Operator& op);
104
105// An implementation of Operator that has no static parameters. Such operators
106// have just a name, an opcode, and a fixed number of inputs and outputs.
107// They can represented by singletons and shared globally.
108class SimpleOperator : public Operator {
109 public:
110  SimpleOperator(Opcode opcode, Properties properties, int input_count,
111                 int output_count, const char* mnemonic);
112  ~SimpleOperator();
113
114  virtual bool Equals(const Operator* that) const FINAL {
115    return opcode() == that->opcode();
116  }
117  virtual int HashCode() const FINAL { return opcode(); }
118  virtual int InputCount() const FINAL { return input_count_; }
119  virtual int OutputCount() const FINAL { return output_count_; }
120
121 private:
122  virtual OStream& PrintTo(OStream& os) const FINAL {  // NOLINT
123    return os << mnemonic();
124  }
125
126  int input_count_;
127  int output_count_;
128
129  DISALLOW_COPY_AND_ASSIGN(SimpleOperator);
130};
131
132// Template specialization implements a kind of type class for dealing with the
133// static parameters of Operator1 automatically.
134template <typename T>
135struct StaticParameterTraits {
136  static OStream& PrintTo(OStream& os, T val) {  // NOLINT
137    return os << "??";
138  }
139  static int HashCode(T a) { return 0; }
140  static bool Equals(T a, T b) {
141    return false;  // Not every T has a ==. By default, be conservative.
142  }
143};
144
145// Specialization for static parameters of type {int}.
146template <>
147struct StaticParameterTraits<int> {
148  static OStream& PrintTo(OStream& os, int val) {  // NOLINT
149    return os << val;
150  }
151  static int HashCode(int a) { return a; }
152  static bool Equals(int a, int b) { return a == b; }
153};
154
155// Specialization for static parameters of type {double}.
156template <>
157struct StaticParameterTraits<double> {
158  static OStream& PrintTo(OStream& os, double val) {  // NOLINT
159    return os << val;
160  }
161  static int HashCode(double a) {
162    return static_cast<int>(bit_cast<int64_t>(a));
163  }
164  static bool Equals(double a, double b) {
165    return bit_cast<int64_t>(a) == bit_cast<int64_t>(b);
166  }
167};
168
169// Specialization for static parameters of type {Unique<Object>}.
170template <>
171struct StaticParameterTraits<Unique<Object> > {
172  static OStream& PrintTo(OStream& os, Unique<Object> val) {  // NOLINT
173    return os << Brief(*val.handle());
174  }
175  static int HashCode(Unique<Object> a) {
176    return static_cast<int>(a.Hashcode());
177  }
178  static bool Equals(Unique<Object> a, Unique<Object> b) { return a == b; }
179};
180
181// Specialization for static parameters of type {Unique<Name>}.
182template <>
183struct StaticParameterTraits<Unique<Name> > {
184  static OStream& PrintTo(OStream& os, Unique<Name> val) {  // NOLINT
185    return os << Brief(*val.handle());
186  }
187  static int HashCode(Unique<Name> a) { return static_cast<int>(a.Hashcode()); }
188  static bool Equals(Unique<Name> a, Unique<Name> b) { return a == b; }
189};
190
191#if DEBUG
192// Specialization for static parameters of type {Handle<Object>} to prevent any
193// direct usage of Handles in constants.
194template <>
195struct StaticParameterTraits<Handle<Object> > {
196  static OStream& PrintTo(OStream& os, Handle<Object> val) {  // NOLINT
197    UNREACHABLE();  // Should use Unique<Object> instead
198    return os;
199  }
200  static int HashCode(Handle<Object> a) {
201    UNREACHABLE();  // Should use Unique<Object> instead
202    return 0;
203  }
204  static bool Equals(Handle<Object> a, Handle<Object> b) {
205    UNREACHABLE();  // Should use Unique<Object> instead
206    return false;
207  }
208};
209#endif
210
211// A templatized implementation of Operator that has one static parameter of
212// type {T}. If a specialization of StaticParameterTraits<{T}> exists, then
213// operators of this kind can automatically be hashed, compared, and printed.
214template <typename T>
215class Operator1 : public Operator {
216 public:
217  Operator1(Opcode opcode, Properties properties, int input_count,
218            int output_count, const char* mnemonic, T parameter)
219      : Operator(opcode, properties, mnemonic),
220        input_count_(input_count),
221        output_count_(output_count),
222        parameter_(parameter) {}
223
224  const T& parameter() const { return parameter_; }
225
226  virtual bool Equals(const Operator* other) const OVERRIDE {
227    if (opcode() != other->opcode()) return false;
228    const Operator1<T>* that = static_cast<const Operator1<T>*>(other);
229    return StaticParameterTraits<T>::Equals(this->parameter_, that->parameter_);
230  }
231  virtual int HashCode() const OVERRIDE {
232    return opcode() + 33 * StaticParameterTraits<T>::HashCode(this->parameter_);
233  }
234  virtual int InputCount() const OVERRIDE { return input_count_; }
235  virtual int OutputCount() const OVERRIDE { return output_count_; }
236  virtual OStream& PrintParameter(OStream& os) const {  // NOLINT
237    return StaticParameterTraits<T>::PrintTo(os << "[", parameter_) << "]";
238  }
239
240 protected:
241  virtual OStream& PrintTo(OStream& os) const FINAL {  // NOLINT
242    return PrintParameter(os << mnemonic());
243  }
244
245 private:
246  int input_count_;
247  int output_count_;
248  T parameter_;
249};
250
251
252// Helper to extract parameters from Operator1<*> operator.
253template <typename T>
254static inline const T& OpParameter(const Operator* op) {
255  return reinterpret_cast<const Operator1<T>*>(op)->parameter();
256}
257
258}  // namespace compiler
259}  // namespace internal
260}  // namespace v8
261
262#endif  // V8_COMPILER_OPERATOR_H_
263