blob: c3f236d556b73942f6c4a0c7227d5af599766263 [file] [log] [blame]
Ben Murdoch4a90d5f2016-03-22 12:00:34 +00001// 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
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000021// EscapeStatusAnalysis determines for each allocation whether it escapes.
22class EscapeStatusAnalysis {
23 public:
Ben Murdoch097c5b22016-05-18 11:27:45 +010024 typedef NodeId Alias;
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000025 ~EscapeStatusAnalysis();
26
Ben Murdoch097c5b22016-05-18 11:27:45 +010027 enum Status {
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000028 kUnknown = 0u,
29 kTracked = 1u << 0,
30 kEscaped = 1u << 1,
31 kOnStack = 1u << 2,
32 kVisited = 1u << 3,
Ben Murdoch097c5b22016-05-18 11:27:45 +010033 // A node is dangling, if it is a load of some kind, and does not have
34 // an effect successor.
35 kDanglingComputed = 1u << 4,
36 kDangling = 1u << 5,
37 // A node is is an effect branch point, if it has more than 2 non-dangling
38 // effect successors.
39 kBranchPointComputed = 1u << 6,
40 kBranchPoint = 1u << 7,
41 kInQueue = 1u << 8
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000042 };
Ben Murdoch097c5b22016-05-18 11:27:45 +010043 typedef base::Flags<Status, uint16_t> StatusFlags;
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000044
Ben Murdoch097c5b22016-05-18 11:27:45 +010045 void RunStatusAnalysis();
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000046
47 bool IsVirtual(Node* node);
48 bool IsEscaped(Node* node);
49 bool IsAllocation(Node* node);
50
Ben Murdoch097c5b22016-05-18 11:27:45 +010051 bool IsInQueue(NodeId id);
52 void SetInQueue(NodeId id, bool on_stack);
53
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000054 void DebugPrint();
55
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000056 EscapeStatusAnalysis(EscapeAnalysis* object_analysis, Graph* graph,
57 Zone* zone);
Ben Murdoch097c5b22016-05-18 11:27:45 +010058 void EnqueueForStatusAnalysis(Node* node);
59 bool SetEscaped(Node* node);
60 bool IsEffectBranchPoint(Node* node);
61 bool IsDanglingEffectNode(Node* node);
62 void ResizeStatusVector();
63 size_t GetStatusVectorSize();
64 bool IsVirtual(NodeId id);
65
66 Graph* graph() const { return graph_; }
67 Zone* zone() const { return zone_; }
68 void AssignAliases();
69 Alias GetAlias(NodeId id) const { return aliases_[id]; }
70 const ZoneVector<Alias>& GetAliasMap() const { return aliases_; }
71 Alias AliasCount() const { return next_free_alias_; }
72 static const Alias kNotReachable;
73 static const Alias kUntrackable;
74
75 bool IsNotReachable(Node* node);
76
77 private:
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000078 void Process(Node* node);
79 void ProcessAllocate(Node* node);
80 void ProcessFinishRegion(Node* node);
81 void ProcessStoreField(Node* node);
82 void ProcessStoreElement(Node* node);
83 bool CheckUsesForEscape(Node* node, bool phi_escaping = false) {
84 return CheckUsesForEscape(node, node, phi_escaping);
85 }
86 bool CheckUsesForEscape(Node* node, Node* rep, bool phi_escaping = false);
87 void RevisitUses(Node* node);
88 void RevisitInputs(Node* node);
Ben Murdoch097c5b22016-05-18 11:27:45 +010089
90 Alias NextAlias() { return next_free_alias_++; }
91
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000092 bool HasEntry(Node* node);
Ben Murdoch097c5b22016-05-18 11:27:45 +010093
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000094 bool IsAllocationPhi(Node* node);
95
Ben Murdoch097c5b22016-05-18 11:27:45 +010096 ZoneVector<Node*> stack_;
Ben Murdoch4a90d5f2016-03-22 12:00:34 +000097 EscapeAnalysis* object_analysis_;
98 Graph* const graph_;
99 Zone* const zone_;
Ben Murdoch097c5b22016-05-18 11:27:45 +0100100 ZoneVector<StatusFlags> status_;
101 Alias next_free_alias_;
102 ZoneVector<Node*> status_stack_;
103 ZoneVector<Alias> aliases_;
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000104
105 DISALLOW_COPY_AND_ASSIGN(EscapeStatusAnalysis);
106};
107
Ben Murdoch097c5b22016-05-18 11:27:45 +0100108DEFINE_OPERATORS_FOR_FLAGS(EscapeStatusAnalysis::StatusFlags)
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000109
110// Forward Declaration.
111class MergeCache;
112
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000113// EscapeObjectAnalysis simulates stores to determine values of loads if
114// an object is virtual and eliminated.
115class EscapeAnalysis {
116 public:
Ben Murdoch097c5b22016-05-18 11:27:45 +0100117 using Alias = EscapeStatusAnalysis::Alias;
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000118 EscapeAnalysis(Graph* graph, CommonOperatorBuilder* common, Zone* zone);
119 ~EscapeAnalysis();
120
121 void Run();
122
123 Node* GetReplacement(Node* node);
124 bool IsVirtual(Node* node);
125 bool IsEscaped(Node* node);
126 bool CompareVirtualObjects(Node* left, Node* right);
127 Node* GetOrCreateObjectState(Node* effect, Node* node);
Ben Murdoch097c5b22016-05-18 11:27:45 +0100128 bool ExistsVirtualAllocate();
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000129
130 private:
131 void RunObjectAnalysis();
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000132 bool Process(Node* node);
133 void ProcessLoadField(Node* node);
134 void ProcessStoreField(Node* node);
135 void ProcessLoadElement(Node* node);
136 void ProcessStoreElement(Node* node);
137 void ProcessAllocationUsers(Node* node);
138 void ProcessAllocation(Node* node);
139 void ProcessFinishRegion(Node* node);
140 void ProcessCall(Node* node);
141 void ProcessStart(Node* node);
142 bool ProcessEffectPhi(Node* node);
143 void ProcessLoadFromPhi(int offset, Node* from, Node* node,
144 VirtualState* states);
145
146 void ForwardVirtualState(Node* node);
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000147 int OffsetFromAccess(Node* node);
Ben Murdoch097c5b22016-05-18 11:27:45 +0100148 VirtualState* CopyForModificationAt(VirtualState* state, Node* node);
149 VirtualObject* CopyForModificationAt(VirtualObject* obj, VirtualState* state,
150 Node* node);
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000151 VirtualObject* GetVirtualObject(Node* at, NodeId id);
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000152
153 bool SetEscaped(Node* node);
154 Node* replacement(NodeId id);
155 Node* replacement(Node* node);
156 Node* ResolveReplacement(Node* node);
157 Node* GetReplacement(NodeId id);
158 bool SetReplacement(Node* node, Node* rep);
159 bool UpdateReplacement(VirtualState* state, Node* node, Node* rep);
160
161 VirtualObject* GetVirtualObject(VirtualState* state, Node* node);
162
163 void DebugPrint();
164 void DebugPrintState(VirtualState* state);
165 void DebugPrintObject(VirtualObject* state, Alias id);
166
Ben Murdoch097c5b22016-05-18 11:27:45 +0100167 Graph* graph() const { return status_analysis_.graph(); }
168 Zone* zone() const { return status_analysis_.zone(); }
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000169 CommonOperatorBuilder* common() const { return common_; }
Ben Murdoch097c5b22016-05-18 11:27:45 +0100170 bool IsEffectBranchPoint(Node* node) {
171 return status_analysis_.IsEffectBranchPoint(node);
172 }
173 bool IsDanglingEffectNode(Node* node) {
174 return status_analysis_.IsDanglingEffectNode(node);
175 }
176 bool IsNotReachable(Node* node) {
177 return status_analysis_.IsNotReachable(node);
178 }
179 Alias GetAlias(NodeId id) const { return status_analysis_.GetAlias(id); }
180 Alias AliasCount() const { return status_analysis_.AliasCount(); }
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000181
Ben Murdoch097c5b22016-05-18 11:27:45 +0100182 EscapeStatusAnalysis status_analysis_;
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000183 CommonOperatorBuilder* const common_;
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000184 ZoneVector<VirtualState*> virtual_states_;
185 ZoneVector<Node*> replacements_;
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000186 MergeCache* cache_;
Ben Murdoch4a90d5f2016-03-22 12:00:34 +0000187
188 DISALLOW_COPY_AND_ASSIGN(EscapeAnalysis);
189};
190
191} // namespace compiler
192} // namespace internal
193} // namespace v8
194
195#endif // V8_COMPILER_ESCAPE_ANALYSIS_H_