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 
11 namespace v8 {
12 namespace internal {
13 namespace compiler {
14 
15 // Forward declarations.
16 class CommonOperatorBuilder;
17 class EscapeAnalysis;
18 class VirtualState;
19 class VirtualObject;
20 
21 
22 // EscapeStatusAnalysis determines for each allocation whether it escapes.
23 class 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 
graph()66   Graph* graph() const { return graph_; }
zone()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 
79 DEFINE_OPERATORS_FOR_FLAGS(EscapeStatusAnalysis::EscapeStatusFlags)
80 
81 
82 // Forward Declaration.
83 class MergeCache;
84 
85 
86 // EscapeObjectAnalysis simulates stores to determine values of loads if
87 // an object is virtual and eliminated.
88 class 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 
NextAlias()143   Alias NextAlias() { return next_free_alias_++; }
AliasCount()144   Alias AliasCount() const { return next_free_alias_; }
145 
graph()146   Graph* graph() const { return graph_; }
common()147   CommonOperatorBuilder* common() const { return common_; }
zone()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