escape-analysis.h 5.92 KB
Newer Older
1
// Copyright 2017 the V8 project authors. All rights reserved.
2 3 4 5 6 7
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_ESCAPE_ANALYSIS_H_
#define V8_COMPILER_ESCAPE_ANALYSIS_H_

8
#include "src/base/functional.h"
9
#include "src/common/globals.h"
10 11 12
#include "src/compiler/graph-reducer.h"
#include "src/compiler/js-graph.h"
#include "src/compiler/persistent-map.h"
13
#include "src/objects/name.h"
14 15 16

namespace v8 {
namespace internal {
17 18 19

class TickCounter;

20 21 22
namespace compiler {

class CommonOperatorBuilder;
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
class VariableTracker;
class EscapeAnalysisTracker;

// {EffectGraphReducer} reduces up to a fixed point. It distinguishes changes to
// the effect output of a node from changes to the value output to reduce the
// number of revisitations.
class EffectGraphReducer {
 public:
  class Reduction {
   public:
    bool value_changed() const { return value_changed_; }
    void set_value_changed() { value_changed_ = true; }
    bool effect_changed() const { return effect_changed_; }
    void set_effect_changed() { effect_changed_ = true; }

   private:
    bool value_changed_ = false;
    bool effect_changed_ = false;
  };

  EffectGraphReducer(Graph* graph,
44 45
                     std::function<void(Node*, Reduction*)> reduce,
                     TickCounter* tick_counter, Zone* zone);
46 47 48 49 50 51 52 53 54 55

  void ReduceGraph() { ReduceFrom(graph_->end()); }

  // Mark node for revisitation.
  void Revisit(Node* node);

  // Add a new root node to start reduction from. This is useful if the reducer
  // adds nodes that are not yet reachable, but should already be considered
  // part of the graph.
  void AddRoot(Node* node) {
56
    DCHECK_EQ(State::kUnvisited, state_.Get(node));
57 58 59 60 61 62
    state_.Set(node, State::kRevisit);
    revisit_.push(node);
  }

  bool Complete() { return stack_.empty() && revisit_.empty(); }

63 64
  TickCounter* tick_counter() const { return tick_counter_; }

65 66 67 68 69 70 71 72 73 74 75 76 77
 private:
  struct NodeState {
    Node* node;
    int input_index;
  };
  void ReduceFrom(Node* node);
  enum class State : uint8_t { kUnvisited = 0, kRevisit, kOnStack, kVisited };
  const uint8_t kNumStates = static_cast<uint8_t>(State::kVisited) + 1;
  Graph* graph_;
  NodeMarker<State> state_;
  ZoneStack<Node*> revisit_;
  ZoneStack<NodeState> stack_;
  std::function<void(Node*, Reduction*)> reduce_;
78
  TickCounter* const tick_counter_;
79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
};

// A variable is an abstract storage location, which is lowered to SSA values
// and phi nodes by {VariableTracker}.
class Variable {
 public:
  Variable() : id_(kInvalid) {}
  bool operator==(Variable other) const { return id_ == other.id_; }
  bool operator!=(Variable other) const { return id_ != other.id_; }
  bool operator<(Variable other) const { return id_ < other.id_; }
  static Variable Invalid() { return Variable(kInvalid); }
  friend V8_INLINE size_t hash_value(Variable v) {
    return base::hash_value(v.id_);
  }
  friend std::ostream& operator<<(std::ostream& os, Variable var) {
    return os << var.id_;
  }

 private:
98
  using Id = int;
99 100 101 102 103 104 105 106 107 108
  explicit Variable(Id id) : id_(id) {}
  Id id_;
  static const Id kInvalid = -1;

  friend class VariableTracker;
};

// An object that can track the nodes in the graph whose current reduction
// depends on the value of the object.
class Dependable : public ZoneObject {
109
 public:
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
  explicit Dependable(Zone* zone) : dependants_(zone) {}
  void AddDependency(Node* node) { dependants_.push_back(node); }
  void RevisitDependants(EffectGraphReducer* reducer) {
    for (Node* node : dependants_) {
      reducer->Revisit(node);
    }
    dependants_.clear();
  }

 private:
  ZoneVector<Node*> dependants_;
};

// A virtual object represents an allocation site and tracks the Variables
// associated with its fields as well as its global escape status.
class VirtualObject : public Dependable {
 public:
127 128
  using Id = uint32_t;
  using const_iterator = ZoneVector<Variable>::const_iterator;
129 130
  VirtualObject(VariableTracker* var_states, Id id, int size);
  Maybe<Variable> FieldAt(int offset) const {
131
    CHECK(IsAligned(offset, kTaggedSize));
132 133
    CHECK(!HasEscaped());
    if (offset >= size()) {
134 135 136 137
      // TODO(tebbi): Reading out-of-bounds can only happen in unreachable
      // code. In this case, we have to mark the object as escaping to avoid
      // dead nodes in the graph. This is a workaround that should be removed
      // once we can handle dead nodes everywhere.
138 139
      return Nothing<Variable>();
    }
140
    return Just(fields_.at(offset / kTaggedSize));
141 142
  }
  Id id() const { return id_; }
143
  int size() const { return static_cast<int>(kTaggedSize * fields_.size()); }
144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
  // Escaped might mean that the object escaped to untracked memory or that it
  // is used in an operation that requires materialization.
  void SetEscaped() { escaped_ = true; }
  bool HasEscaped() const { return escaped_; }
  const_iterator begin() const { return fields_.begin(); }
  const_iterator end() const { return fields_.end(); }

 private:
  bool escaped_ = false;
  Id id_;
  ZoneVector<Variable> fields_;
};

class EscapeAnalysisResult {
 public:
  explicit EscapeAnalysisResult(EscapeAnalysisTracker* tracker)
      : tracker_(tracker) {}

  const VirtualObject* GetVirtualObject(Node* node);
  Node* GetVirtualObjectField(const VirtualObject* vobject, int field,
                              Node* effect);
  Node* GetReplacementOf(Node* node);

 private:
  EscapeAnalysisTracker* tracker_;
};

class V8_EXPORT_PRIVATE EscapeAnalysis final
    : public NON_EXPORTED_BASE(EffectGraphReducer) {
 public:
174
  EscapeAnalysis(JSGraph* jsgraph, TickCounter* tick_counter, Zone* zone);
175 176 177 178 179

  EscapeAnalysisResult analysis_result() {
    DCHECK(Complete());
    return EscapeAnalysisResult(tracker_);
  }
180 181

 private:
182 183
  void Reduce(Node* node, Reduction* reduction);
  JSGraph* jsgraph() { return jsgraph_; }
184
  Isolate* isolate() const { return jsgraph_->isolate(); }
185 186
  EscapeAnalysisTracker* tracker_;
  JSGraph* jsgraph_;
187 188 189 190 191 192 193
};

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_ESCAPE_ANALYSIS_H_