escape-analysis.h 5.95 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 9 10 11
#include "src/base/functional.h"
#include "src/compiler/graph-reducer.h"
#include "src/compiler/js-graph.h"
#include "src/compiler/persistent-map.h"
12
#include "src/globals.h"
13
#include "src/objects/name.h"
14 15 16 17 18 19

namespace v8 {
namespace internal {
namespace compiler {

class CommonOperatorBuilder;
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
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,
                     std::function<void(Node*, Reduction*)> reduce, Zone* zone);

  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) {
52
    DCHECK_EQ(State::kUnvisited, state_.Get(node));
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
    state_.Set(node, State::kRevisit);
    revisit_.push(node);
  }

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

 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_;
};

// 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:
  typedef int Id;
  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 {
102
 public:
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
  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:
  typedef uint32_t Id;
  typedef ZoneVector<Variable>::const_iterator const_iterator;
  VirtualObject(VariableTracker* var_states, Id id, int size);
  Maybe<Variable> FieldAt(int offset) const {
124 125 126 127 128 129 130
    if (offset % kPointerSize != 0) {
      // We do not support fields that are not word-aligned. Bail out by
      // treating the object as escaping. This can only happen for
      // {Name::kHashFieldOffset} on 64bit big endian architectures.
      DCHECK_EQ(Name::kHashFieldOffset, offset);
      return Nothing<Variable>();
    }
131 132
    CHECK(!HasEscaped());
    if (offset >= size()) {
133 134 135 136
      // 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.
137 138 139 140 141 142 143 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 174 175 176 177 178
      return Nothing<Variable>();
    }
    return Just(fields_.at(offset / kPointerSize));
  }
  Id id() const { return id_; }
  int size() const { return static_cast<int>(kPointerSize * fields_.size()); }
  // 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:
  EscapeAnalysis(JSGraph* jsgraph, Zone* zone);

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

 private:
181 182 183 184
  void Reduce(Node* node, Reduction* reduction);
  JSGraph* jsgraph() { return jsgraph_; }
  EscapeAnalysisTracker* tracker_;
  JSGraph* jsgraph_;
185 186 187 188 189 190 191
};

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

#endif  // V8_COMPILER_ESCAPE_ANALYSIS_H_