Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 21 | // EscapeStatusAnalysis determines for each allocation whether it escapes. |
| 22 | class EscapeStatusAnalysis { |
| 23 | public: |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 24 | typedef NodeId Alias; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 25 | ~EscapeStatusAnalysis(); |
| 26 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 27 | enum Status { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 28 | kUnknown = 0u, |
| 29 | kTracked = 1u << 0, |
| 30 | kEscaped = 1u << 1, |
| 31 | kOnStack = 1u << 2, |
| 32 | kVisited = 1u << 3, |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 33 | // 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 Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 42 | }; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 43 | typedef base::Flags<Status, uint16_t> StatusFlags; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 44 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 45 | void RunStatusAnalysis(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 46 | |
| 47 | bool IsVirtual(Node* node); |
| 48 | bool IsEscaped(Node* node); |
| 49 | bool IsAllocation(Node* node); |
| 50 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 51 | bool IsInQueue(NodeId id); |
| 52 | void SetInQueue(NodeId id, bool on_stack); |
| 53 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 54 | void DebugPrint(); |
| 55 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 56 | EscapeStatusAnalysis(EscapeAnalysis* object_analysis, Graph* graph, |
| 57 | Zone* zone); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 58 | 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 Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 78 | 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 Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 89 | |
| 90 | Alias NextAlias() { return next_free_alias_++; } |
| 91 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 92 | bool HasEntry(Node* node); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 93 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 94 | bool IsAllocationPhi(Node* node); |
| 95 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 96 | ZoneVector<Node*> stack_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 97 | EscapeAnalysis* object_analysis_; |
| 98 | Graph* const graph_; |
| 99 | Zone* const zone_; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 100 | ZoneVector<StatusFlags> status_; |
| 101 | Alias next_free_alias_; |
| 102 | ZoneVector<Node*> status_stack_; |
| 103 | ZoneVector<Alias> aliases_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 104 | |
| 105 | DISALLOW_COPY_AND_ASSIGN(EscapeStatusAnalysis); |
| 106 | }; |
| 107 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 108 | DEFINE_OPERATORS_FOR_FLAGS(EscapeStatusAnalysis::StatusFlags) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 109 | |
| 110 | // Forward Declaration. |
| 111 | class MergeCache; |
| 112 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 113 | // EscapeObjectAnalysis simulates stores to determine values of loads if |
| 114 | // an object is virtual and eliminated. |
| 115 | class EscapeAnalysis { |
| 116 | public: |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 117 | using Alias = EscapeStatusAnalysis::Alias; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 118 | 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 Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 128 | bool ExistsVirtualAllocate(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 129 | |
| 130 | private: |
| 131 | void RunObjectAnalysis(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 132 | 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 Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 147 | int OffsetFromAccess(Node* node); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 148 | VirtualState* CopyForModificationAt(VirtualState* state, Node* node); |
| 149 | VirtualObject* CopyForModificationAt(VirtualObject* obj, VirtualState* state, |
| 150 | Node* node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 151 | VirtualObject* GetVirtualObject(Node* at, NodeId id); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 152 | |
| 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 Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 167 | Graph* graph() const { return status_analysis_.graph(); } |
| 168 | Zone* zone() const { return status_analysis_.zone(); } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 169 | CommonOperatorBuilder* common() const { return common_; } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 170 | 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 Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 181 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 182 | EscapeStatusAnalysis status_analysis_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 183 | CommonOperatorBuilder* const common_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 184 | ZoneVector<VirtualState*> virtual_states_; |
| 185 | ZoneVector<Node*> replacements_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 186 | MergeCache* cache_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 187 | |
| 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_ |