LCOV - code coverage report
Current view: top level - src/compiler - escape-analysis.h (source / functions) Hit Total Coverage
Test: app.info Lines: 18 19 94.7 %
Date: 2019-04-17 Functions: 2 2 100.0 %

          Line data    Source code
       1             : // Copyright 2017 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_ESCAPE_ANALYSIS_H_
       6             : #define V8_COMPILER_ESCAPE_ANALYSIS_H_
       7             : 
       8             : #include "src/base/functional.h"
       9             : #include "src/compiler/graph-reducer.h"
      10             : #include "src/compiler/js-graph.h"
      11             : #include "src/compiler/persistent-map.h"
      12             : #include "src/globals.h"
      13             : #include "src/objects/name.h"
      14             : 
      15             : namespace v8 {
      16             : namespace internal {
      17             : namespace compiler {
      18             : 
      19             : class CommonOperatorBuilder;
      20             : class VariableTracker;
      21             : class EscapeAnalysisTracker;
      22             : 
      23             : // {EffectGraphReducer} reduces up to a fixed point. It distinguishes changes to
      24             : // the effect output of a node from changes to the value output to reduce the
      25             : // number of revisitations.
      26      928332 : class EffectGraphReducer {
      27             :  public:
      28             :   class Reduction {
      29             :    public:
      30             :     bool value_changed() const { return value_changed_; }
      31     1761658 :     void set_value_changed() { value_changed_ = true; }
      32             :     bool effect_changed() const { return effect_changed_; }
      33     7654506 :     void set_effect_changed() { effect_changed_ = true; }
      34             : 
      35             :    private:
      36             :     bool value_changed_ = false;
      37             :     bool effect_changed_ = false;
      38             :   };
      39             : 
      40             :   EffectGraphReducer(Graph* graph,
      41             :                      std::function<void(Node*, Reduction*)> reduce, Zone* zone);
      42             : 
      43      464161 :   void ReduceGraph() { ReduceFrom(graph_->end()); }
      44             : 
      45             :   // Mark node for revisitation.
      46             :   void Revisit(Node* node);
      47             : 
      48             :   // Add a new root node to start reduction from. This is useful if the reducer
      49             :   // adds nodes that are not yet reachable, but should already be considered
      50             :   // part of the graph.
      51             :   void AddRoot(Node* node) {
      52             :     DCHECK_EQ(State::kUnvisited, state_.Get(node));
      53             :     state_.Set(node, State::kRevisit);
      54             :     revisit_.push(node);
      55             :   }
      56             : 
      57             :   bool Complete() { return stack_.empty() && revisit_.empty(); }
      58             : 
      59             :  private:
      60             :   struct NodeState {
      61             :     Node* node;
      62             :     int input_index;
      63             :   };
      64             :   void ReduceFrom(Node* node);
      65             :   enum class State : uint8_t { kUnvisited = 0, kRevisit, kOnStack, kVisited };
      66             :   const uint8_t kNumStates = static_cast<uint8_t>(State::kVisited) + 1;
      67             :   Graph* graph_;
      68             :   NodeMarker<State> state_;
      69             :   ZoneStack<Node*> revisit_;
      70             :   ZoneStack<NodeState> stack_;
      71             :   std::function<void(Node*, Reduction*)> reduce_;
      72             : };
      73             : 
      74             : // A variable is an abstract storage location, which is lowered to SSA values
      75             : // and phi nodes by {VariableTracker}.
      76             : class Variable {
      77             :  public:
      78     1439357 :   Variable() : id_(kInvalid) {}
      79    24894011 :   bool operator==(Variable other) const { return id_ == other.id_; }
      80    19284516 :   bool operator!=(Variable other) const { return id_ != other.id_; }
      81           0 :   bool operator<(Variable other) const { return id_ < other.id_; }
      82             :   static Variable Invalid() { return Variable(kInvalid); }
      83             :   friend V8_INLINE size_t hash_value(Variable v) {
      84             :     return base::hash_value(v.id_);
      85             :   }
      86             :   friend std::ostream& operator<<(std::ostream& os, Variable var) {
      87             :     return os << var.id_;
      88             :   }
      89             : 
      90             :  private:
      91             :   using Id = int;
      92             :   explicit Variable(Id id) : id_(id) {}
      93             :   Id id_;
      94             :   static const Id kInvalid = -1;
      95             : 
      96             :   friend class VariableTracker;
      97             : };
      98             : 
      99             : // An object that can track the nodes in the graph whose current reduction
     100             : // depends on the value of the object.
     101             : class Dependable : public ZoneObject {
     102             :  public:
     103             :   explicit Dependable(Zone* zone) : dependants_(zone) {}
     104     2190930 :   void AddDependency(Node* node) { dependants_.push_back(node); }
     105             :   void RevisitDependants(EffectGraphReducer* reducer) {
     106      958938 :     for (Node* node : dependants_) {
     107      874752 :       reducer->Revisit(node);
     108             :     }
     109             :     dependants_.clear();
     110             :   }
     111             : 
     112             :  private:
     113             :   ZoneVector<Node*> dependants_;
     114             : };
     115             : 
     116             : // A virtual object represents an allocation site and tracks the Variables
     117             : // associated with its fields as well as its global escape status.
     118             : class VirtualObject : public Dependable {
     119             :  public:
     120             :   using Id = uint32_t;
     121             :   using const_iterator = ZoneVector<Variable>::const_iterator;
     122             :   VirtualObject(VariableTracker* var_states, Id id, int size);
     123     1700710 :   Maybe<Variable> FieldAt(int offset) const {
     124     1700710 :     CHECK(IsAligned(offset, kTaggedSize));
     125     1700710 :     CHECK(!HasEscaped());
     126     1700710 :     if (offset >= size()) {
     127             :       // TODO(tebbi): Reading out-of-bounds can only happen in unreachable
     128             :       // code. In this case, we have to mark the object as escaping to avoid
     129             :       // dead nodes in the graph. This is a workaround that should be removed
     130             :       // once we can handle dead nodes everywhere.
     131             :       return Nothing<Variable>();
     132             :     }
     133     1700681 :     return Just(fields_.at(offset / kTaggedSize));
     134             :   }
     135             :   Id id() const { return id_; }
     136     2621533 :   int size() const { return static_cast<int>(kTaggedSize * fields_.size()); }
     137             :   // Escaped might mean that the object escaped to untracked memory or that it
     138             :   // is used in an operation that requires materialization.
     139       84186 :   void SetEscaped() { escaped_ = true; }
     140             :   bool HasEscaped() const { return escaped_; }
     141             :   const_iterator begin() const { return fields_.begin(); }
     142             :   const_iterator end() const { return fields_.end(); }
     143             : 
     144             :  private:
     145             :   bool escaped_ = false;
     146             :   Id id_;
     147             :   ZoneVector<Variable> fields_;
     148             : };
     149             : 
     150             : class EscapeAnalysisResult {
     151             :  public:
     152             :   explicit EscapeAnalysisResult(EscapeAnalysisTracker* tracker)
     153             :       : tracker_(tracker) {}
     154             : 
     155             :   const VirtualObject* GetVirtualObject(Node* node);
     156             :   Node* GetVirtualObjectField(const VirtualObject* vobject, int field,
     157             :                               Node* effect);
     158             :   Node* GetReplacementOf(Node* node);
     159             : 
     160             :  private:
     161             :   EscapeAnalysisTracker* tracker_;
     162             : };
     163             : 
     164      464166 : class V8_EXPORT_PRIVATE EscapeAnalysis final
     165             :     : public NON_EXPORTED_BASE(EffectGraphReducer) {
     166             :  public:
     167             :   EscapeAnalysis(JSGraph* jsgraph, Zone* zone);
     168             : 
     169             :   EscapeAnalysisResult analysis_result() {
     170             :     DCHECK(Complete());
     171             :     return EscapeAnalysisResult(tracker_);
     172             :   }
     173             : 
     174             :  private:
     175             :   void Reduce(Node* node, Reduction* reduction);
     176             :   JSGraph* jsgraph() { return jsgraph_; }
     177             :   Isolate* isolate() const { return jsgraph_->isolate(); }
     178             :   EscapeAnalysisTracker* tracker_;
     179             :   JSGraph* jsgraph_;
     180             : };
     181             : 
     182             : }  // namespace compiler
     183             : }  // namespace internal
     184             : }  // namespace v8
     185             : 
     186             : #endif  // V8_COMPILER_ESCAPE_ANALYSIS_H_

Generated by: LCOV version 1.10