escape-analysis.h revision 014dc512cdd3e367bee49a713fdc5ed92584a3e5 
1// Copyright 2015 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/flags.h"
9#include "src/compiler/graph.h"
10
11namespace v8 {
12namespace internal {
13namespace compiler {
14
15// Forward declarations.
16class CommonOperatorBuilder;
17class EscapeAnalysis;
18class VirtualState;
19class VirtualObject;
20
21
22// EscapeStatusAnalysis determines for each allocation whether it escapes.
23class EscapeStatusAnalysis {
24 public:
25  ~EscapeStatusAnalysis();
26
27  enum EscapeStatusFlag {
28    kUnknown = 0u,
29    kTracked = 1u << 0,
30    kEscaped = 1u << 1,
31    kOnStack = 1u << 2,
32    kVisited = 1u << 3,
33  };
34  typedef base::Flags<EscapeStatusFlag, unsigned char> EscapeStatusFlags;
35
36  void Run();
37
38  bool IsVirtual(Node* node);
39  bool IsEscaped(Node* node);
40  bool IsAllocation(Node* node);
41
42  void DebugPrint();
43
44  friend class EscapeAnalysis;
45
46 private:
47  EscapeStatusAnalysis(EscapeAnalysis* object_analysis, Graph* graph,
48                       Zone* zone);
49  void Process(Node* node);
50  void ProcessAllocate(Node* node);
51  void ProcessFinishRegion(Node* node);
52  void ProcessStoreField(Node* node);
53  void ProcessStoreElement(Node* node);
54  bool CheckUsesForEscape(Node* node, bool phi_escaping = false) {
55    return CheckUsesForEscape(node, node, phi_escaping);
56  }
57  bool CheckUsesForEscape(Node* node, Node* rep, bool phi_escaping = false);
58  void RevisitUses(Node* node);
59  void RevisitInputs(Node* node);
60  bool SetEscaped(Node* node);
61  bool HasEntry(Node* node);
62  void Resize();
63  size_t size();
64  bool IsAllocationPhi(Node* node);
65
66  Graph* graph() const { return graph_; }
67  Zone* zone() const { return zone_; }
68
69  EscapeAnalysis* object_analysis_;
70  Graph* const graph_;
71  Zone* const zone_;
72  ZoneVector<EscapeStatusFlags> status_;
73  ZoneDeque<Node*> queue_;
74
75  DISALLOW_COPY_AND_ASSIGN(EscapeStatusAnalysis);
76};
77
78
79DEFINE_OPERATORS_FOR_FLAGS(EscapeStatusAnalysis::EscapeStatusFlags)
80
81
82// Forward Declaration.
83class MergeCache;
84
85
86// EscapeObjectAnalysis simulates stores to determine values of loads if
87// an object is virtual and eliminated.
88class EscapeAnalysis {
89 public:
90  typedef NodeId Alias;
91
92  EscapeAnalysis(Graph* graph, CommonOperatorBuilder* common, Zone* zone);
93  ~EscapeAnalysis();
94
95  void Run();
96
97  Node* GetReplacement(Node* node);
98  bool IsVirtual(Node* node);
99  bool IsEscaped(Node* node);
100  bool CompareVirtualObjects(Node* left, Node* right);
101  Node* GetOrCreateObjectState(Node* effect, Node* node);
102
103 private:
104  void RunObjectAnalysis();
105  void AssignAliases();
106  bool Process(Node* node);
107  void ProcessLoadField(Node* node);
108  void ProcessStoreField(Node* node);
109  void ProcessLoadElement(Node* node);
110  void ProcessStoreElement(Node* node);
111  void ProcessAllocationUsers(Node* node);
112  void ProcessAllocation(Node* node);
113  void ProcessFinishRegion(Node* node);
114  void ProcessCall(Node* node);
115  void ProcessStart(Node* node);
116  bool ProcessEffectPhi(Node* node);
117  void ProcessLoadFromPhi(int offset, Node* from, Node* node,
118                          VirtualState* states);
119
120  void ForwardVirtualState(Node* node);
121  bool IsEffectBranchPoint(Node* node);
122  bool IsDanglingEffectNode(Node* node);
123  int OffsetFromAccess(Node* node);
124
125  VirtualObject* GetVirtualObject(Node* at, NodeId id);
126  VirtualObject* ResolveVirtualObject(VirtualState* state, Node* node);
127  Node* GetReplacementIfSame(ZoneVector<VirtualObject*>& objs);
128
129  bool SetEscaped(Node* node);
130  Node* replacement(NodeId id);
131  Node* replacement(Node* node);
132  Node* ResolveReplacement(Node* node);
133  Node* GetReplacement(NodeId id);
134  bool SetReplacement(Node* node, Node* rep);
135  bool UpdateReplacement(VirtualState* state, Node* node, Node* rep);
136
137  VirtualObject* GetVirtualObject(VirtualState* state, Node* node);
138
139  void DebugPrint();
140  void DebugPrintState(VirtualState* state);
141  void DebugPrintObject(VirtualObject* state, Alias id);
142
143  Alias NextAlias() { return next_free_alias_++; }
144  Alias AliasCount() const { return next_free_alias_; }
145
146  Graph* graph() const { return graph_; }
147  CommonOperatorBuilder* common() const { return common_; }
148  Zone* zone() const { return zone_; }
149
150  static const Alias kNotReachable;
151  static const Alias kUntrackable;
152  Graph* const graph_;
153  CommonOperatorBuilder* const common_;
154  Zone* const zone_;
155  ZoneVector<VirtualState*> virtual_states_;
156  ZoneVector<Node*> replacements_;
157  EscapeStatusAnalysis escape_status_;
158  MergeCache* cache_;
159  ZoneVector<Alias> aliases_;
160  Alias next_free_alias_;
161
162  DISALLOW_COPY_AND_ASSIGN(EscapeAnalysis);
163};
164
165}  // namespace compiler
166}  // namespace internal
167}  // namespace v8
168
169#endif  // V8_COMPILER_ESCAPE_ANALYSIS_H_
170