[turbofan] Initial support for escape analysis.

src/compiler/escape-analysis.h

Index: src/compiler/escape-analysis.h
diff --git a/src/compiler/escape-analysis.h b/src/compiler/escape-analysis.h
new file mode 100644
index 0000000000000000000000000000000000000000..44efd6369bad6a9272b4289b488657e38b8a67c1
--- /dev/null
+++ b/src/compiler/escape-analysis.h
@@ -0,0 +1,200 @@
+// Copyright 2015 the V8 project authors. All rights reserved.
+// 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_
+
+#include "src/base/flags.h"
+#include "src/compiler/graph.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+// Forward declarations.
+class CommonOperatorBuilder;
+
+
+class VirtualObject : public ZoneObject {
+ public:
+  enum Status { kUntracked = 0, kTracked = 1 };
+  VirtualObject(NodeId id, Zone* zone)
+      : id_(id), status_(kUntracked), fields_(zone), replacement_(nullptr) {}
+
+  VirtualObject(const VirtualObject& other)
+      : id_(other.id_),
+        status_(other.status_),
+        fields_(other.fields_),
+        replacement_(other.replacement_) {}
+
+  VirtualObject(NodeId id, Zone* zone, size_t field_number)
+      : id_(id), status_(kTracked), fields_(zone), replacement_(nullptr) {
+    fields_.resize(field_number);
+  }
+
+  Node* GetField(size_t offset) {
+    if (offset < fields_.size()) {
+      return fields_[offset];
+    }
+    return nullptr;
+  }
+
+  bool SetField(size_t offset, Node* node) {
+    bool changed = fields_[offset] != node;
+    fields_[offset] = node;
+    return changed;
+  }
+  bool IsVirtual() const { return status_ == kTracked; }
+  bool IsTracked() const { return status_ != kUntracked; }
+  Node* GetReplacement() { return replacement_; }
+  bool SetReplacement(Node* node) {
+    bool changed = replacement_ != node;
+    replacement_ = node;
+    return changed;
+  }
+
+  size_t fields() { return fields_.size(); }
+  bool ResizeFields(size_t field_number) {
+    if (field_number != fields_.size()) {
+      fields_.resize(field_number);
+      return true;
+    }
+    return false;
+  }
+
+  bool UpdateFrom(const VirtualObject& other);
+
+  NodeId id() { return id_; }
+  void id(NodeId id) { id_ = id; }
+
+ private:
+  NodeId id_;
+  Status status_;
+  ZoneVector<Node*> fields_;
+  Node* replacement_;
+};
+
+
+class VirtualState : public ZoneObject {

[Michael Starzinger, 2015/12/01 17:18:38]

Both the VirtualObject as well as the VirtualState classes are only used by the
"escape-analysis.cc" implementation itself. They are never passed around to
different components. I like that very much. I would even go a step further and
move those two classes into the .cc file. Thereby the chance of someone mocking
with internal state of the escape analysis are reduced even further.

[sigurds, 2015/12/02 10:12:20]

Done.

+ public:
+  VirtualState(Zone* zone, size_t size);
+  VirtualState(const VirtualState& states);
+
+  VirtualObject* GetVirtualObject(Node* node);
+  VirtualObject* GetVirtualObject(size_t id);
+  VirtualObject* GetOrCreateTrackedVirtualObject(NodeId id, Zone* zone);
+  void SetVirtualObject(NodeId id, VirtualObject* state);
+  void LastChangedAt(Node* node) { last_changed_ = node; }
+  Node* GetLastChanged() { return last_changed_; }
+  bool UpdateFrom(NodeId id, VirtualObject* state, Zone* zone);
+  Node* ResolveReplacement(Node* node);
+  bool UpdateReplacement(Node* node, Node* rep, Zone* zone);
+  bool UpdateFrom(VirtualState* state, Zone* zone);
+  bool MergeFrom(VirtualState* left, VirtualState* right, Zone* zone,
+                 Graph* graph, CommonOperatorBuilder* common, Node* control);
+
+  size_t size() { return info_.size(); }
+
+ private:
+  ZoneVector<VirtualObject*> info_;
+  Node* last_changed_;
+};
+
+
+class EscapeObjectAnalysis;
+
+
+// EscapeStatusAnalysis determines for each allocation whether it escapes.
+class EscapeStatusAnalysis {
+ public:
+  EscapeStatusAnalysis(EscapeObjectAnalysis* object_analysis, Graph* graph,
+                       Zone* zone);
+  ~EscapeStatusAnalysis();
+
+  enum EscapeStatusFlag {
+    kUnknown = 0u,
+    kVirtual = 1u << 0,
+    kEscaped = 1u << 1,
+  };
+  typedef base::Flags<EscapeStatusFlag> EscapeStatusFlags;
+
+  void Run();
+
+  bool HasEntry(Node* node);
+  bool IsVirtual(Node* node);
+  bool IsEscaped(Node* node);
+
+  void DebugPrint();
+
+ private:
+  void Process(Node* node);
+  void ProcessAllocate(Node* node);
+  void ProcessFinishRegion(Node* node);
+  void ProcessStoreField(Node* node);
+  bool CheckUsesForEscape(Node* node) { return CheckUsesForEscape(node, node); }
+  bool CheckUsesForEscape(Node* node, Node* rep);
+  void RevisitUses(Node* node);
+  void RevisitInputs(Node* node);
+  bool SetEscaped(Node* node);
+
+  Graph* graph() const { return graph_; }
+  Zone* zone() const { return zone_; }
+
+  EscapeObjectAnalysis* object_analysis_;
+  Graph* const graph_;
+  Zone* const zone_;
+  ZoneVector<EscapeStatusFlags> info_;
+  ZoneDeque<Node*> queue_;
+
+  DISALLOW_COPY_AND_ASSIGN(EscapeStatusAnalysis);
+};
+
+
+DEFINE_OPERATORS_FOR_FLAGS(EscapeStatusAnalysis::EscapeStatusFlags)
+
+
+// EscapeObjectAnalysis simulates stores to determine values of loads if
+// an object is virtual and eliminated.
+class EscapeObjectAnalysis {
+ public:
+  EscapeObjectAnalysis(Graph* graph, CommonOperatorBuilder* common, Zone* zone);
+  ~EscapeObjectAnalysis();
+
+  void Run();
+
+  Node* GetReplacement(Node* at, NodeId id);
+
+ private:
+  bool Process(Node* node);
+  void ProcessLoadField(Node* node);
+  void ProcessStoreField(Node* node);
+  void ProcessAllocation(Node* node);
+  void ProcessFinishRegion(Node* node);
+  void ProcessCall(Node* node);
+  void ProcessStart(Node* node);
+  bool ProcessEffectPhi(Node* node);
+  void ForwardVirtualState(Node* node);
+  bool IsEffectBranchPoint(Node* node);
+  bool IsDanglingEffectNode(Node* node);
+  int OffsetFromAccess(Node* node);
+
+  void DebugPrint();
+
+  Graph* graph() const { return graph_; }
+  CommonOperatorBuilder* common() const { return common_; }
+  Zone* zone() const { return zone_; }
+
+  Graph* const graph_;
+  CommonOperatorBuilder* const common_;
+  Zone* const zone_;
+  ZoneVector<VirtualState*> virtual_states_;
+
+  DISALLOW_COPY_AND_ASSIGN(EscapeObjectAnalysis);
+};
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_COMPILER_ESCAPE_ANALYSIS_H_