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