[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..50fd022f6181c03cc53317de43d2cbb82c204c67
--- /dev/null
+++ b/src/compiler/escape-analysis.h
@@ -0,0 +1,177 @@
+// 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 {
+
+// Forward declarations.
+class CompilationDependencies;
+class TypeCache;

[Michael Starzinger, 2015/11/30 10:05:39]

nit: Some of the forward declarations seem not to be used in this file anymore,
let's drop those.

[sigurds, 2015/11/30 13:50:24]

Done.

+
+
+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), representation_(nullptr) {}
+
+  VirtualObject(const VirtualObject& other)
+      : id_(other.id_),
+        status_(other.status_),
+        fields_(other.fields_),
+        representation_(other.representation_) {}
+
+  VirtualObject(NodeId id, Zone* zone, size_t field_number)
+      : id_(id), status_(kTracked), fields_(zone), representation_(nullptr) {
+    fields_.resize(field_number);
+  }
+
+  Node* GetField(size_t offset) { return fields_[offset]; }
+  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* GetRepresentation() { return representation_; }
+  bool SetRepresentation(Node* node) {
+    bool changed = representation_ != node;
+    representation_ = node;
+    return changed;
+  }
+  size_t fields() { return fields_.size(); }
+
+  bool UpdateFrom(const VirtualObject& other);
+
+  NodeId id() { return id_; }
+  void id(NodeId id) { id_ = id; }
+
+ private:
+  NodeId id_;
+  Status status_;
+  ZoneVector<Node*> fields_;
+  Node* representation_;
+};
+
+
+class VirtualState : public ZoneObject {
+ public:
+  VirtualState(Zone* zone, size_t size);
+  VirtualState(const VirtualState& states);
+
+  VirtualObject* GetState(Node* node);
+  VirtualObject* GetState(size_t id);
+  void SetState(NodeId id, VirtualObject* state);
+  void SetLastChanged(Node* node) { last_changed_ = node; }
+  Node* GetLastChanged() { return last_changed_; }
+  bool UpdateFrom(NodeId id, VirtualObject* state, Zone* zone);
+
+  size_t size() { return info_.size(); }
+
+ private:
+  ZoneVector<VirtualObject*> info_;
+  Node* last_changed_;
+};
+
+
+// EscapeStatusAnalysis determines for each allocation whether it escapes.
+class EscapeStatusAnalysis {
+ public:
+  EscapeStatusAnalysis(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);
+  void RevisitUses(Node* node);
+  void RevisitInputs(Node* node);
+  bool SetEscaped(Node* node);
+
+  Graph* graph() const { return graph_; }
+  Zone* zone() const { return zone_; }
+
+  Graph* const graph_;
+  Zone* const zone_;
+  ZoneVector<EscapeStatusFlags> info_;
+  ZoneDeque<Node*> queue_;
+};
+
+
+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* representation(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 ForwardObjectState(Node* node);
+  bool IsEffectBranchPoint(Node* node);
+  bool IsDanglingEffectNode(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*> states_;
+
+  DISALLOW_COPY_AND_ASSIGN(EscapeObjectAnalysis);
+};
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_COMPILER_TYPER_H_