Home | History | Annotate | Download | only in compiler 
      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 
     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.
     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.
     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.
     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.
     80   virtual size_t HashCode() const { return base::hash<Opcode>()(opcode()); }
     81 
     82   // Check whether this operator has the given property.
     83   bool HasProperty(Property property) const {
     84     return (properties() & property) == property;
     85   }
     86 
     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.
     93   int ValueInputCount() const { return value_in_; }
     94   int EffectInputCount() const { return effect_in_; }
     95   int ControlInputCount() const { return control_in_; }
     96 
     97   int ValueOutputCount() const { return value_out_; }
     98   int EffectOutputCount() const { return effect_out_; }
     99   int ControlOutputCount() const { return control_out_; }
    100 
    101   static size_t ZeroIfEliminatable(Properties properties) {
    102     return (properties & kEliminatable) == kEliminatable ? 0 : 1;
    103   }
    104 
    105   static size_t ZeroIfNoThrow(Properties properties) {
    106     return (properties & kNoThrow) == kNoThrow ? 0 : 2;
    107   }
    108 
    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())
    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 
    164   T const& parameter() const { return parameter_; }
    165 
    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   }
    172   size_t HashCode() const final {
    173     return base::hash_combine(this->opcode(), this->hash_(this->parameter()));
    174   }
    175   virtual void PrintParameter(std::ostream& os) const {
    176     os << "[" << this->parameter() << "]";
    177   }
    178 
    179  protected:
    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>
    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