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/compiler-specific.h"
     11 #include "src/base/flags.h"
     12 #include "src/base/functional.h"
     13 #include "src/globals.h"
     14 #include "src/handles.h"
     15 #include "src/zone/zone.h"
     16 
     17 namespace v8 {
     18 namespace internal {
     19 namespace compiler {
     20 
     21 // An operator represents description of the "computation" of a node in the
     22 // compiler IR. A computation takes values (i.e. data) as input and produces
     23 // zero or more values as output. The side-effects of a computation must be
     24 // captured by additional control and data dependencies which are part of the
     25 // IR graph.
     26 // Operators are immutable and describe the statically-known parts of a
     27 // computation. Thus they can be safely shared by many different nodes in the
     28 // IR graph, or even globally between graphs. Operators can have "static
     29 // parameters" which are compile-time constant parameters to the operator, such
     30 // as the name for a named field access, the ID of a runtime function, etc.
     31 // Static parameters are private to the operator and only semantically
     32 // meaningful to the operator itself.
     33 class V8_EXPORT_PRIVATE Operator : public NON_EXPORTED_BASE(ZoneObject) {
     34  public:
     35   typedef uint16_t Opcode;
     36 
     37   // Properties inform the operator-independent optimizer about legal
     38   // transformations for nodes that have this operator.
     39   enum Property {
     40     kNoProperties = 0,
     41     kCommutative = 1 << 0,  // OP(a, b) == OP(b, a) for all inputs.
     42     kAssociative = 1 << 1,  // OP(a, OP(b,c)) == OP(OP(a,b), c) for all inputs.
     43     kIdempotent = 1 << 2,   // OP(a); OP(a) == OP(a).
     44     kNoRead = 1 << 3,       // Has no scheduling dependency on Effects
     45     kNoWrite = 1 << 4,      // Does not modify any Effects and thereby
     46                             // create new scheduling dependencies.
     47     kNoThrow = 1 << 5,      // Can never generate an exception.
     48     kNoDeopt = 1 << 6,      // Can never generate an eager deoptimization exit.
     49     kFoldable = kNoRead | kNoWrite,
     50     kKontrol = kNoDeopt | kFoldable | kNoThrow,
     51     kEliminatable = kNoDeopt | kNoWrite | kNoThrow,
     52     kPure = kNoDeopt | kNoRead | kNoWrite | kNoThrow | kIdempotent
     53   };
     54 
     55 // List of all bits, for the visualizer.
     56 #define OPERATOR_PROPERTY_LIST(V) \
     57   V(Commutative)                  \
     58   V(Associative) V(Idempotent) V(NoRead) V(NoWrite) V(NoThrow) V(NoDeopt)
     59 
     60   typedef base::Flags<Property, uint8_t> Properties;
     61   enum class PrintVerbosity { kVerbose, kSilent };
     62 
     63   // Constructor.
     64   Operator(Opcode opcode, Properties properties, const char* mnemonic,
     65            size_t value_in, size_t effect_in, size_t control_in,
     66            size_t value_out, size_t effect_out, size_t control_out);
     67 
     68   virtual ~Operator() {}
     69 
     70   // A small integer unique to all instances of a particular kind of operator,
     71   // useful for quick matching for specific kinds of operators. For fast access
     72   // the opcode is stored directly in the operator object.
     73   Opcode opcode() const { return opcode_; }
     74 
     75   // Returns a constant string representing the mnemonic of the operator,
     76   // without the static parameters. Useful for debugging.
     77   const char* mnemonic() const { return mnemonic_; }
     78 
     79   // Check if this operator equals another operator. Equivalent operators can
     80   // be merged, and nodes with equivalent operators and equivalent inputs
     81   // can be merged.
     82   virtual bool Equals(const Operator* that) const {
     83     return this->opcode() == that->opcode();
     84   }
     85 
     86   // Compute a hashcode to speed up equivalence-set checking.
     87   // Equal operators should always have equal hashcodes, and unequal operators
     88   // 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   bool HasProperty(Property property) const {
     93     return (properties() & property) == property;
     94   }
     95 
     96   Properties properties() const { return properties_; }
     97 
     98   // TODO(bmeurer): Use bit fields below?
     99   static const size_t kMaxControlOutputCount = (1u << 16) - 1;
    100 
    101   // TODO(titzer): convert return values here to size_t.
    102   int ValueInputCount() const { return value_in_; }
    103   int EffectInputCount() const { return effect_in_; }
    104   int ControlInputCount() const { return control_in_; }
    105 
    106   int ValueOutputCount() const { return value_out_; }
    107   int EffectOutputCount() const { return effect_out_; }
    108   int ControlOutputCount() const { return control_out_; }
    109 
    110   static size_t ZeroIfEliminatable(Properties properties) {
    111     return (properties & kEliminatable) == kEliminatable ? 0 : 1;
    112   }
    113 
    114   static size_t ZeroIfNoThrow(Properties properties) {
    115     return (properties & kNoThrow) == kNoThrow ? 0 : 2;
    116   }
    117 
    118   static size_t ZeroIfPure(Properties properties) {
    119     return (properties & kPure) == kPure ? 0 : 1;
    120   }
    121 
    122   // TODO(titzer): API for input and output types, for typechecking graph.
    123 
    124   // Print the full operator into the given stream, including any
    125   // static parameters. Useful for debugging and visualizing the IR.
    126   void PrintTo(std::ostream& os,
    127                PrintVerbosity verbose = PrintVerbosity::kVerbose) const {
    128     // We cannot make PrintTo virtual, because default arguments to virtual
    129     // methods are banned in the style guide.
    130     return PrintToImpl(os, verbose);
    131   }
    132 
    133   void PrintPropsTo(std::ostream& os) const;
    134 
    135  protected:
    136   virtual void PrintToImpl(std::ostream& os, PrintVerbosity verbose) const;
    137 
    138  private:
    139   Opcode opcode_;
    140   Properties properties_;
    141   const char* mnemonic_;
    142   uint32_t value_in_;
    143   uint16_t effect_in_;
    144   uint16_t control_in_;
    145   uint16_t value_out_;
    146   uint8_t effect_out_;
    147   uint32_t control_out_;
    148 
    149   DISALLOW_COPY_AND_ASSIGN(Operator);
    150 };
    151 
    152 DEFINE_OPERATORS_FOR_FLAGS(Operator::Properties)
    153 
    154 std::ostream& operator<<(std::ostream& os, const Operator& op);
    155 
    156 
    157 // Default equality function for below Operator1<*> class.
    158 template <typename T>
    159 struct OpEqualTo : public std::equal_to<T> {};
    160 
    161 
    162 // Default hashing function for below Operator1<*> class.
    163 template <typename T>
    164 struct OpHash : public base::hash<T> {};
    165 
    166 
    167 // A templatized implementation of Operator that has one static parameter of
    168 // type {T} with the proper default equality and hashing functions.
    169 template <typename T, typename Pred = OpEqualTo<T>, typename Hash = OpHash<T>>
    170 class Operator1 : public Operator {
    171  public:
    172   Operator1(Opcode opcode, Properties properties, const char* mnemonic,
    173             size_t value_in, size_t effect_in, size_t control_in,
    174             size_t value_out, size_t effect_out, size_t control_out,
    175             T parameter, Pred const& pred = Pred(), Hash const& hash = Hash())
    176       : Operator(opcode, properties, mnemonic, value_in, effect_in, control_in,
    177                  value_out, effect_out, control_out),
    178         parameter_(parameter),
    179         pred_(pred),
    180         hash_(hash) {}
    181 
    182   T const& parameter() const { return parameter_; }
    183 
    184   bool Equals(const Operator* other) const final {
    185     if (opcode() != other->opcode()) return false;
    186     const Operator1<T, Pred, Hash>* that =
    187         reinterpret_cast<const Operator1<T, Pred, Hash>*>(other);
    188     return this->pred_(this->parameter(), that->parameter());
    189   }
    190   size_t HashCode() const final {
    191     return base::hash_combine(this->opcode(), this->hash_(this->parameter()));
    192   }
    193   // For most parameter types, we have only a verbose way to print them, namely
    194   // ostream << parameter. But for some types it is particularly useful to have
    195   // a shorter way to print them for the node labels in Turbolizer. The
    196   // following method can be overridden to provide a concise and a verbose
    197   // printing of a parameter.
    198 
    199   virtual void PrintParameter(std::ostream& os, PrintVerbosity verbose) const {
    200     os << "[" << parameter() << "]";
    201   }
    202 
    203   virtual void PrintToImpl(std::ostream& os, PrintVerbosity verbose) const {
    204     os << mnemonic();
    205     PrintParameter(os, verbose);
    206   }
    207 
    208  private:
    209   T const parameter_;
    210   Pred const pred_;
    211   Hash const hash_;
    212 };
    213 
    214 
    215 // Helper to extract parameters from Operator1<*> operator.
    216 template <typename T>
    217 inline T const& OpParameter(const Operator* op) {
    218   return reinterpret_cast<const Operator1<T, OpEqualTo<T>, OpHash<T>>*>(op)
    219       ->parameter();
    220 }
    221 
    222 
    223 // NOTE: We have to be careful to use the right equal/hash functions below, for
    224 // float/double we always use the ones operating on the bit level, for Handle<>
    225 // we always use the ones operating on the location level.
    226 template <>
    227 struct OpEqualTo<float> : public base::bit_equal_to<float> {};
    228 template <>
    229 struct OpHash<float> : public base::bit_hash<float> {};
    230 
    231 template <>
    232 struct OpEqualTo<double> : public base::bit_equal_to<double> {};
    233 template <>
    234 struct OpHash<double> : public base::bit_hash<double> {};
    235 
    236 template <>
    237 struct OpEqualTo<Handle<HeapObject>> : public Handle<HeapObject>::equal_to {};
    238 template <>
    239 struct OpHash<Handle<HeapObject>> : public Handle<HeapObject>::hash {};
    240 
    241 template <>
    242 struct OpEqualTo<Handle<String>> : public Handle<String>::equal_to {};
    243 template <>
    244 struct OpHash<Handle<String>> : public Handle<String>::hash {};
    245 
    246 template <>
    247 struct OpEqualTo<Handle<ScopeInfo>> : public Handle<ScopeInfo>::equal_to {};
    248 template <>
    249 struct OpHash<Handle<ScopeInfo>> : public Handle<ScopeInfo>::hash {};
    250 
    251 }  // namespace compiler
    252 }  // namespace internal
    253 }  // namespace v8
    254 
    255 #endif  // V8_COMPILER_OPERATOR_H_
    256