1// Copyright 2015 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_STATE_VALUES_UTILS_H_
6#define V8_COMPILER_STATE_VALUES_UTILS_H_
7
8#include <array>
9
10#include "src/common/globals.h"
11#include "src/compiler/common-operator.h"
12#include "src/compiler/js-graph.h"
13#include "src/zone/zone-hashmap.h"
14
15namespace v8 {
16namespace internal {
17
18class BitVector;
19
20namespace compiler {
21
22class Graph;
23class BytecodeLivenessState;
24
25class V8_EXPORT_PRIVATE StateValuesCache {
26 public:
27  explicit StateValuesCache(JSGraph* js_graph);
28
29  Node* GetNodeForValues(Node** values, size_t count,
30                         const BytecodeLivenessState* liveness = nullptr);
31
32 private:
33  static const size_t kMaxInputCount = 8;
34  using WorkingBuffer = std::array<Node*, kMaxInputCount>;
35
36  struct NodeKey {
37    Node* node;
38
39    explicit NodeKey(Node* node) : node(node) {}
40  };
41
42  struct StateValuesKey : public NodeKey {
43    // ValueArray - array of nodes ({node} has to be nullptr).
44    size_t count;
45    SparseInputMask mask;
46    Node** values;
47
48    StateValuesKey(size_t count, SparseInputMask mask, Node** values)
49        : NodeKey(nullptr), count(count), mask(mask), values(values) {}
50  };
51
52  static bool AreKeysEqual(void* key1, void* key2);
53  static bool IsKeysEqualToNode(StateValuesKey* key, Node* node);
54  static bool AreValueKeysEqual(StateValuesKey* key1, StateValuesKey* key2);
55
56  // Fills {node_buffer}, starting from {node_count}, with {values}, starting
57  // at {values_idx}, sparsely encoding according to {liveness}. {node_count} is
58  // updated with the new number of inputs in {node_buffer}, and a bitmask of
59  // the sparse encoding is returned.
60  SparseInputMask::BitMaskType FillBufferWithValues(
61      WorkingBuffer* node_buffer, size_t* node_count, size_t* values_idx,
62      Node** values, size_t count, const BytecodeLivenessState* liveness);
63
64  Node* BuildTree(size_t* values_idx, Node** values, size_t count,
65                  const BytecodeLivenessState* liveness, size_t level);
66
67  WorkingBuffer* GetWorkingSpace(size_t level);
68  Node* GetEmptyStateValues();
69  Node* GetValuesNodeFromCache(Node** nodes, size_t count,
70                               SparseInputMask mask);
71
72  Graph* graph() { return js_graph_->graph(); }
73  CommonOperatorBuilder* common() { return js_graph_->common(); }
74
75  Zone* zone() { return graph()->zone(); }
76
77  JSGraph* js_graph_;
78  CustomMatcherZoneHashMap hash_map_;
79  ZoneVector<WorkingBuffer> working_space_;  // One working space per level.
80  Node* empty_state_values_;
81};
82
83class V8_EXPORT_PRIVATE StateValuesAccess {
84 public:
85  struct TypedNode {
86    Node* node;
87    MachineType type;
88    TypedNode(Node* node, MachineType type) : node(node), type(type) {}
89  };
90
91  class V8_EXPORT_PRIVATE iterator {
92   public:
93    bool operator!=(iterator const& other) const;
94    iterator& operator++();
95    TypedNode operator*();
96
97    Node* node();
98    bool done() const { return current_depth_ < 0; }
99
100    // Returns the number of empty nodes that were skipped over.
101    size_t AdvanceTillNotEmpty();
102
103   private:
104    friend class StateValuesAccess;
105
106    iterator() : current_depth_(-1) {}
107    explicit iterator(Node* node);
108
109    MachineType type();
110    void Advance();
111    void EnsureValid();
112
113    SparseInputMask::InputIterator* Top();
114    void Push(Node* node);
115    void Pop();
116
117    static const int kMaxInlineDepth = 8;
118    SparseInputMask::InputIterator stack_[kMaxInlineDepth];
119    int current_depth_;
120  };
121
122  explicit StateValuesAccess(Node* node) : node_(node) {}
123
124  size_t size() const;
125  iterator begin() const { return iterator(node_); }
126  iterator begin_without_receiver() const {
127    return ++begin();  // Skip the receiver.
128  }
129  iterator begin_without_receiver_and_skip(int n_skips) {
130    iterator it = begin_without_receiver();
131    while (n_skips > 0 && !it.done()) {
132      ++it;
133      --n_skips;
134    }
135    return it;
136  }
137  iterator end() const { return iterator(); }
138
139 private:
140  Node* node_;
141};
142
143}  // namespace compiler
144}  // namespace internal
145}  // namespace v8
146
147#endif  // V8_COMPILER_STATE_VALUES_UTILS_H_
148