operator.h 9.23 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_OPERATOR_H_
#define V8_COMPILER_OPERATOR_H_

8 9
#include <ostream>  // NOLINT(readability/streams)

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/zone/zone.h"
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

namespace v8 {
namespace internal {
namespace compiler {

// An operator represents description of the "computation" of a node in the
// compiler IR. A computation takes values (i.e. data) as input and produces
// zero or more values as output. The side-effects of a computation must be
// captured by additional control and data dependencies which are part of the
// IR graph.
// Operators are immutable and describe the statically-known parts of a
// computation. Thus they can be safely shared by many different nodes in the
// IR graph, or even globally between graphs. Operators can have "static
// parameters" which are compile-time constant parameters to the operator, such
// as the name for a named field access, the ID of a runtime function, etc.
// Static parameters are private to the operator and only semantically
// meaningful to the operator itself.
33
class V8_EXPORT_PRIVATE Operator : public NON_EXPORTED_BASE(ZoneObject) {
34
 public:
35
  using Opcode = uint16_t;
36 37 38 39 40

  // Properties inform the operator-independent optimizer about legal
  // transformations for nodes that have this operator.
  enum Property {
    kNoProperties = 0,
41 42 43 44 45
    kCommutative = 1 << 0,  // OP(a, b) == OP(b, a) for all inputs.
    kAssociative = 1 << 1,  // OP(a, OP(b,c)) == OP(OP(a,b), c) for all inputs.
    kIdempotent = 1 << 2,   // OP(a); OP(a) == OP(a).
    kNoRead = 1 << 3,       // Has no scheduling dependency on Effects
    kNoWrite = 1 << 4,      // Does not modify any Effects and thereby
46
                            // create new scheduling dependencies.
47 48
    kNoThrow = 1 << 5,      // Can never generate an exception.
    kNoDeopt = 1 << 6,      // Can never generate an eager deoptimization exit.
49
    kFoldable = kNoRead | kNoWrite,
50 51 52
    kKontrol = kNoDeopt | kFoldable | kNoThrow,
    kEliminatable = kNoDeopt | kNoWrite | kNoThrow,
    kPure = kNoDeopt | kNoRead | kNoWrite | kNoThrow | kIdempotent
53
  };
54 55 56 57 58 59

// List of all bits, for the visualizer.
#define OPERATOR_PROPERTY_LIST(V) \
  V(Commutative)                  \
  V(Associative) V(Idempotent) V(NoRead) V(NoWrite) V(NoThrow) V(NoDeopt)

60
  using Properties = base::Flags<Property, uint8_t>;
61
  enum class PrintVerbosity { kVerbose, kSilent };
62

63 64 65 66 67
  // Constructor.
  Operator(Opcode opcode, Properties properties, const char* mnemonic,
           size_t value_in, size_t effect_in, size_t control_in,
           size_t value_out, size_t effect_out, size_t control_out);

68
  virtual ~Operator() = default;
69 70 71 72

  // A small integer unique to all instances of a particular kind of operator,
  // useful for quick matching for specific kinds of operators. For fast access
  // the opcode is stored directly in the operator object.
73
  Opcode opcode() const { return opcode_; }
74 75 76

  // Returns a constant string representing the mnemonic of the operator,
  // without the static parameters. Useful for debugging.
77
  const char* mnemonic() const { return mnemonic_; }
78 79 80 81

  // Check if this operator equals another operator. Equivalent operators can
  // be merged, and nodes with equivalent operators and equivalent inputs
  // can be merged.
82 83 84
  virtual bool Equals(const Operator* that) const {
    return this->opcode() == that->opcode();
  }
85 86 87 88

  // Compute a hashcode to speed up equivalence-set checking.
  // Equal operators should always have equal hashcodes, and unequal operators
  // should have unequal hashcodes with high probability.
89
  virtual size_t HashCode() const { return base::hash<Opcode>()(opcode()); }
90 91

  // Check whether this operator has the given property.
92 93
  bool HasProperty(Property property) const {
    return (properties() & property) == property;
94 95
  }

96
  Properties properties() const { return properties_; }
97

98 99 100 101 102 103 104 105 106
  // TODO(titzer): convert return values here to size_t.
  int ValueInputCount() const { return value_in_; }
  int EffectInputCount() const { return effect_in_; }
  int ControlInputCount() const { return control_in_; }

  int ValueOutputCount() const { return value_out_; }
  int EffectOutputCount() const { return effect_out_; }
  int ControlOutputCount() const { return control_out_; }

107 108 109 110
  static size_t ZeroIfEliminatable(Properties properties) {
    return (properties & kEliminatable) == kEliminatable ? 0 : 1;
  }

111 112 113 114
  static size_t ZeroIfNoThrow(Properties properties) {
    return (properties & kNoThrow) == kNoThrow ? 0 : 2;
  }

115
  static size_t ZeroIfPure(Properties properties) {
116 117 118
    return (properties & kPure) == kPure ? 0 : 1;
  }

119
  // TODO(titzer): API for input and output types, for typechecking graph.
120

121 122
  // Print the full operator into the given stream, including any
  // static parameters. Useful for debugging and visualizing the IR.
123 124 125 126 127 128 129
  void PrintTo(std::ostream& os,
               PrintVerbosity verbose = PrintVerbosity::kVerbose) const {
    // We cannot make PrintTo virtual, because default arguments to virtual
    // methods are banned in the style guide.
    return PrintToImpl(os, verbose);
  }

130 131
  void PrintPropsTo(std::ostream& os) const;

132 133
 protected:
  virtual void PrintToImpl(std::ostream& os, PrintVerbosity verbose) const;
134

135
 private:
136
  const char* mnemonic_;
137 138
  Opcode opcode_;
  Properties properties_;
139
  uint32_t value_in_;
140 141
  uint32_t effect_in_;
  uint32_t control_in_;
142
  uint32_t value_out_;
143
  uint8_t effect_out_;
144
  uint32_t control_out_;
145 146

  DISALLOW_COPY_AND_ASSIGN(Operator);
147 148
};

149 150
DEFINE_OPERATORS_FOR_FLAGS(Operator::Properties)

151 152
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os,
                                           const Operator& op);
153

154 155 156 157 158 159 160 161 162 163
// Default equality function for below Operator1<*> class.
template <typename T>
struct OpEqualTo : public std::equal_to<T> {};


// Default hashing function for below Operator1<*> class.
template <typename T>
struct OpHash : public base::hash<T> {};


164
// A templatized implementation of Operator that has one static parameter of
165 166
// type {T} with the proper default equality and hashing functions.
template <typename T, typename Pred = OpEqualTo<T>, typename Hash = OpHash<T>>
167 168
class Operator1 : public Operator {
 public:
169 170 171 172 173 174
  Operator1(Opcode opcode, Properties properties, const char* mnemonic,
            size_t value_in, size_t effect_in, size_t control_in,
            size_t value_out, size_t effect_out, size_t control_out,
            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),
175 176 177
        parameter_(parameter),
        pred_(pred),
        hash_(hash) {}
178

179
  T const& parameter() const { return parameter_; }
180

181
  bool Equals(const Operator* other) const final {
182
    if (opcode() != other->opcode()) return false;
183 184
    const Operator1<T, Pred, Hash>* that =
        reinterpret_cast<const Operator1<T, Pred, Hash>*>(other);
185
    return this->pred_(this->parameter(), that->parameter());
186
  }
187
  size_t HashCode() const final {
188
    return base::hash_combine(this->opcode(), this->hash_(this->parameter()));
189
  }
190 191 192 193 194 195 196 197
  // For most parameter types, we have only a verbose way to print them, namely
  // ostream << parameter. But for some types it is particularly useful to have
  // a shorter way to print them for the node labels in Turbolizer. The
  // following method can be overridden to provide a concise and a verbose
  // printing of a parameter.

  virtual void PrintParameter(std::ostream& os, PrintVerbosity verbose) const {
    os << "[" << parameter() << "]";
198 199
  }

200
  void PrintToImpl(std::ostream& os, PrintVerbosity verbose) const override {
201
    os << mnemonic();
202
    PrintParameter(os, verbose);
203 204
  }

205
 private:
206 207 208
  T const parameter_;
  Pred const pred_;
  Hash const hash_;
209 210
};

211 212 213

// Helper to extract parameters from Operator1<*> operator.
template <typename T>
214
inline T const& OpParameter(const Operator* op) {
215 216
  return reinterpret_cast<const Operator1<T, OpEqualTo<T>, OpHash<T>>*>(op)
      ->parameter();
217 218
}

219

svenpanne's avatar
svenpanne committed
220
// NOTE: We have to be careful to use the right equal/hash functions below, for
221 222
// float/double we always use the ones operating on the bit level, for Handle<>
// we always use the ones operating on the location level.
svenpanne's avatar
svenpanne committed
223
template <>
224 225 226
struct OpEqualTo<float> : public base::bit_equal_to<float> {};
template <>
struct OpHash<float> : public base::bit_hash<float> {};
svenpanne's avatar
svenpanne committed
227 228

template <>
229 230 231
struct OpEqualTo<double> : public base::bit_equal_to<double> {};
template <>
struct OpHash<double> : public base::bit_hash<double> {};
svenpanne's avatar
svenpanne committed
232

233
template <>
234 235 236
struct OpEqualTo<Handle<HeapObject>> : public Handle<HeapObject>::equal_to {};
template <>
struct OpHash<Handle<HeapObject>> : public Handle<HeapObject>::hash {};
237 238

template <>
239 240 241
struct OpEqualTo<Handle<String>> : public Handle<String>::equal_to {};
template <>
struct OpHash<Handle<String>> : public Handle<String>::hash {};
242

243
template <>
244 245 246
struct OpEqualTo<Handle<ScopeInfo>> : public Handle<ScopeInfo>::equal_to {};
template <>
struct OpHash<Handle<ScopeInfo>> : public Handle<ScopeInfo>::hash {};
247

248 249 250
}  // namespace compiler
}  // namespace internal
}  // namespace v8
251 252

#endif  // V8_COMPILER_OPERATOR_H_