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