src/v8/src/compiler/operator.h

   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
  12 namespace v8 {
  13 namespace internal {
  14 namespace 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.
  28 class 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
 101 DEFINE_OPERATORS_FOR_FLAGS(Operator::Properties)
 102
 103 OStream& 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.
 108 class 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.
 134 template <typename T>
 135 struct 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}.
 146 template <>
 147 struct 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}.
 156 template <>
 157 struct 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>}.
 170 template <>
 171 struct 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>}.
 182 template <>
 183 struct 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.
 194 template <>
 195 struct 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.
 214 template <typename T>
 215 class 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.
 253 template <typename T>
 254 static 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_