src/v8/src/compiler/generic-node.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_GENERIC_NODE_H_
   6 #define V8_COMPILER_GENERIC_NODE_H_
   7
   8 #include "src/v8.h"
   9
  10 #include "src/zone-containers.h"
  11
  12 namespace v8 {
  13 namespace internal {
  14 namespace compiler {
  15
  16 class GenericGraphBase;
  17
  18 typedef int NodeId;
  19
  20 // A GenericNode<> is the basic primitive of graphs. GenericNode's are
  21 // chained together by input/use chains but by default otherwise contain only an
  22 // identifying number which specific applications of graphs and nodes can use
  23 // to index auxiliary out-of-line data, especially transient data.
  24 // Specializations of the templatized GenericNode<> class must provide a base
  25 // class B that contains all of the members to be made available in each
  26 // specialized Node instance. GenericNode uses a mixin template pattern to
  27 // ensure that common accessors and methods expect the derived class S type
  28 // rather than the GenericNode<B, S> type.
  29 template <class B, class S>
  30 class GenericNode : public B {
  31  public:
  32   typedef B BaseClass;
  33   typedef S DerivedClass;
  34
  35   inline NodeId id() const { return id_; }
  36
  37   int InputCount() const { return input_count_; }
  38   S* InputAt(int index) const {
  39     return static_cast<S*>(GetInputRecordPtr(index)->to);
  40   }
  41   inline void ReplaceInput(int index, GenericNode* new_input);
  42   inline void AppendInput(Zone* zone, GenericNode* new_input);
  43   inline void InsertInput(Zone* zone, int index, GenericNode* new_input);
  44   inline void RemoveInput(int index);
  45
  46   int UseCount() { return use_count_; }
  47   S* UseAt(int index) {
  48     DCHECK(index < use_count_);
  49     Use* current = first_use_;
  50     while (index-- != 0) {
  51       current = current->next;
  52     }
  53     return static_cast<S*>(current->from);
  54   }
  55   inline void ReplaceUses(GenericNode* replace_to);
  56   template <class UnaryPredicate>
  57   inline void ReplaceUsesIf(UnaryPredicate pred, GenericNode* replace_to);
  58   inline void RemoveAllInputs();
  59
  60   inline void TrimInputCount(int input_count);
  61
  62   class Inputs {
  63    public:
  64     class iterator;
  65     iterator begin();
  66     iterator end();
  67
  68     explicit Inputs(GenericNode* node) : node_(node) {}
  69
  70    private:
  71     GenericNode* node_;
  72   };
  73
  74   Inputs inputs() { return Inputs(this); }
  75
  76   class Uses {
  77    public:
  78     class iterator;
  79     iterator begin();
  80     iterator end();
  81     bool empty() { return begin() == end(); }
  82
  83     explicit Uses(GenericNode* node) : node_(node) {}
  84
  85    private:
  86     GenericNode* node_;
  87   };
  88
  89   Uses uses() { return Uses(this); }
  90
  91   class Edge;
  92
  93   bool OwnedBy(GenericNode* owner) const;
  94
  95   static S* New(GenericGraphBase* graph, int input_count, S** inputs);
  96
  97  protected:
  98   friend class GenericGraphBase;
  99
 100   class Use : public ZoneObject {
 101    public:
 102     GenericNode* from;
 103     Use* next;
 104     Use* prev;
 105     int input_index;
 106   };
 107
 108   class Input {
 109    public:
 110     GenericNode* to;
 111     Use* use;
 112
 113     void Update(GenericNode* new_to);
 114   };
 115
 116   void EnsureAppendableInputs(Zone* zone);
 117
 118   Input* GetInputRecordPtr(int index) const {
 119     if (has_appendable_inputs_) {
 120       return &((*inputs_.appendable_)[index]);
 121     } else {
 122       return inputs_.static_ + index;
 123     }
 124   }
 125
 126   inline void AppendUse(Use* use);
 127   inline void RemoveUse(Use* use);
 128
 129   void* operator new(size_t, void* location) { return location; }
 130
 131   GenericNode(GenericGraphBase* graph, int input_count);
 132
 133  private:
 134   void AssignUniqueID(GenericGraphBase* graph);
 135
 136   typedef ZoneDeque<Input> InputDeque;
 137
 138   NodeId id_;
 139   int input_count_ : 31;
 140   bool has_appendable_inputs_ : 1;
 141   union {
 142     // When a node is initially allocated, it uses a static buffer to hold its
 143     // inputs under the assumption that the number of outputs will not increase.
 144     // When the first input is appended, the static buffer is converted into a
 145     // deque to allow for space-efficient growing.
 146     Input* static_;
 147     InputDeque* appendable_;
 148   } inputs_;
 149   int use_count_;
 150   Use* first_use_;
 151   Use* last_use_;
 152
 153   DISALLOW_COPY_AND_ASSIGN(GenericNode);
 154 };
 155
 156 // An encapsulation for information associated with a single use of node as a
 157 // input from another node, allowing access to both the defining node and
 158 // the ndoe having the input.
 159 template <class B, class S>
 160 class GenericNode<B, S>::Edge {
 161  public:
 162   S* from() const { return static_cast<S*>(input_->use->from); }
 163   S* to() const { return static_cast<S*>(input_->to); }
 164   int index() const {
 165     int index = input_->use->input_index;
 166     DCHECK(index < input_->use->from->input_count_);
 167     return index;
 168   }
 169
 170  private:
 171   friend class GenericNode<B, S>::Uses::iterator;
 172   friend class GenericNode<B, S>::Inputs::iterator;
 173
 174   explicit Edge(typename GenericNode<B, S>::Input* input) : input_(input) {}
 175
 176   typename GenericNode<B, S>::Input* input_;
 177 };
 178
 179 // A forward iterator to visit the nodes which are depended upon by a node
 180 // in the order of input.
 181 template <class B, class S>
 182 class GenericNode<B, S>::Inputs::iterator {
 183  public:
 184   iterator(const typename GenericNode<B, S>::Inputs::iterator& other)  // NOLINT
 185       : node_(other.node_),
 186         index_(other.index_) {}
 187
 188   S* operator*() { return static_cast<S*>(GetInput()->to); }
 189   typename GenericNode<B, S>::Edge edge() {
 190     return typename GenericNode::Edge(GetInput());
 191   }
 192   bool operator==(const iterator& other) const {
 193     return other.index_ == index_ && other.node_ == node_;
 194   }
 195   bool operator!=(const iterator& other) const { return !(other == *this); }
 196   iterator& operator++() {
 197     DCHECK(node_ != NULL);
 198     DCHECK(index_ < node_->input_count_);
 199     ++index_;
 200     return *this;
 201   }
 202   iterator& UpdateToAndIncrement(GenericNode<B, S>* new_to) {
 203     typename GenericNode<B, S>::Input* input = GetInput();
 204     input->Update(new_to);
 205     index_++;
 206     return *this;
 207   }
 208   int index() { return index_; }
 209
 210  private:
 211   friend class GenericNode;
 212
 213   explicit iterator(GenericNode* node, int index)
 214       : node_(node), index_(index) {}
 215
 216   Input* GetInput() const { return node_->GetInputRecordPtr(index_); }
 217
 218   GenericNode* node_;
 219   int index_;
 220 };
 221
 222 // A forward iterator to visit the uses of a node. The uses are returned in
 223 // the order in which they were added as inputs.
 224 template <class B, class S>
 225 class GenericNode<B, S>::Uses::iterator {
 226  public:
 227   iterator(const typename GenericNode<B, S>::Uses::iterator& other)  // NOLINT
 228       : current_(other.current_),
 229         index_(other.index_) {}
 230
 231   S* operator*() { return static_cast<S*>(current_->from); }
 232   typename GenericNode<B, S>::Edge edge() {
 233     return typename GenericNode::Edge(CurrentInput());
 234   }
 235
 236   bool operator==(const iterator& other) { return other.current_ == current_; }
 237   bool operator!=(const iterator& other) { return other.current_ != current_; }
 238   iterator& operator++() {
 239     DCHECK(current_ != NULL);
 240     index_++;
 241     current_ = current_->next;
 242     return *this;
 243   }
 244   iterator& UpdateToAndIncrement(GenericNode<B, S>* new_to) {
 245     DCHECK(current_ != NULL);
 246     index_++;
 247     typename GenericNode<B, S>::Input* input = CurrentInput();
 248     current_ = current_->next;
 249     input->Update(new_to);
 250     return *this;
 251   }
 252   int index() const { return index_; }
 253
 254  private:
 255   friend class GenericNode<B, S>::Uses;
 256
 257   iterator() : current_(NULL), index_(0) {}
 258   explicit iterator(GenericNode<B, S>* node)
 259       : current_(node->first_use_), index_(0) {}
 260
 261   Input* CurrentInput() const {
 262     return current_->from->GetInputRecordPtr(current_->input_index);
 263   }
 264
 265   typename GenericNode<B, S>::Use* current_;
 266   int index_;
 267 };
 268 }
 269 }
 270 }  // namespace v8::internal::compiler
 271
 272 #endif  // V8_COMPILER_GENERIC_NODE_H_