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 | #include "src/compiler/escape-analysis.h" |
| 6 | |
| 7 | #include <limits> |
| 8 | |
| 9 | #include "src/base/flags.h" |
| 10 | #include "src/bootstrapper.h" |
| 11 | #include "src/compilation-dependencies.h" |
| 12 | #include "src/compiler/common-operator.h" |
| 13 | #include "src/compiler/graph-reducer.h" |
| 14 | #include "src/compiler/js-operator.h" |
| 15 | #include "src/compiler/node.h" |
| 16 | #include "src/compiler/node-matchers.h" |
| 17 | #include "src/compiler/node-properties.h" |
| 18 | #include "src/compiler/operator-properties.h" |
| 19 | #include "src/compiler/simplified-operator.h" |
| 20 | #include "src/objects-inl.h" |
| 21 | #include "src/type-cache.h" |
| 22 | |
| 23 | namespace v8 { |
| 24 | namespace internal { |
| 25 | namespace compiler { |
| 26 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 27 | using Alias = EscapeStatusAnalysis::Alias; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 28 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 29 | #ifdef DEBUG |
| 30 | #define TRACE(...) \ |
| 31 | do { \ |
| 32 | if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \ |
| 33 | } while (false) |
| 34 | #else |
| 35 | #define TRACE(...) |
| 36 | #endif |
| 37 | |
| 38 | const Alias EscapeStatusAnalysis::kNotReachable = |
| 39 | std::numeric_limits<Alias>::max(); |
| 40 | const Alias EscapeStatusAnalysis::kUntrackable = |
| 41 | std::numeric_limits<Alias>::max() - 1; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 42 | |
| 43 | class VirtualObject : public ZoneObject { |
| 44 | public: |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 45 | enum Status { |
| 46 | kInitial = 0, |
| 47 | kTracked = 1u << 0, |
| 48 | kInitialized = 1u << 1, |
| 49 | kCopyRequired = 1u << 2, |
| 50 | }; |
| 51 | typedef base::Flags<Status, unsigned char> StatusFlags; |
| 52 | |
| 53 | VirtualObject(NodeId id, VirtualState* owner, Zone* zone) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 54 | : id_(id), |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 55 | status_(kInitial), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 56 | fields_(zone), |
| 57 | phi_(zone), |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 58 | object_state_(nullptr), |
| 59 | owner_(owner) {} |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 60 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 61 | VirtualObject(VirtualState* owner, const VirtualObject& other) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 62 | : id_(other.id_), |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 63 | status_(other.status_ & ~kCopyRequired), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 64 | fields_(other.fields_), |
| 65 | phi_(other.phi_), |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 66 | object_state_(other.object_state_), |
| 67 | owner_(owner) {} |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 68 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 69 | VirtualObject(NodeId id, VirtualState* owner, Zone* zone, size_t field_number, |
| 70 | bool initialized) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 71 | : id_(id), |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 72 | status_(kTracked | (initialized ? kInitialized : kInitial)), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 73 | fields_(zone), |
| 74 | phi_(zone), |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 75 | object_state_(nullptr), |
| 76 | owner_(owner) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 77 | fields_.resize(field_number); |
| 78 | phi_.resize(field_number, false); |
| 79 | } |
| 80 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 81 | Node* GetField(size_t offset) { return fields_[offset]; } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 82 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 83 | bool IsCreatedPhi(size_t offset) { return phi_[offset]; } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 84 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 85 | void SetField(size_t offset, Node* node, bool created_phi = false) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 86 | fields_[offset] = node; |
| 87 | phi_[offset] = created_phi; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 88 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 89 | bool IsTracked() const { return status_ & kTracked; } |
| 90 | bool IsInitialized() const { return status_ & kInitialized; } |
| 91 | bool SetInitialized() { return status_ |= kInitialized; } |
| 92 | VirtualState* owner() const { return owner_; } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 93 | |
| 94 | Node** fields_array() { return &fields_.front(); } |
| 95 | size_t field_count() { return fields_.size(); } |
| 96 | bool ResizeFields(size_t field_count) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 97 | if (field_count > fields_.size()) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 98 | fields_.resize(field_count); |
| 99 | phi_.resize(field_count); |
| 100 | return true; |
| 101 | } |
| 102 | return false; |
| 103 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 104 | void ClearAllFields() { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 105 | for (size_t i = 0; i < fields_.size(); ++i) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 106 | fields_[i] = nullptr; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 107 | phi_[i] = false; |
| 108 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 109 | } |
| 110 | bool AllFieldsClear() { |
| 111 | for (size_t i = 0; i < fields_.size(); ++i) { |
| 112 | if (fields_[i] != nullptr) { |
| 113 | return false; |
| 114 | } |
| 115 | } |
| 116 | return true; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 117 | } |
| 118 | bool UpdateFrom(const VirtualObject& other); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 119 | bool MergeFrom(MergeCache* cache, Node* at, Graph* graph, |
| 120 | CommonOperatorBuilder* common); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 121 | void SetObjectState(Node* node) { object_state_ = node; } |
| 122 | Node* GetObjectState() const { return object_state_; } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 123 | bool IsCopyRequired() const { return status_ & kCopyRequired; } |
| 124 | void SetCopyRequired() { status_ |= kCopyRequired; } |
| 125 | bool NeedCopyForModification() { |
| 126 | if (!IsCopyRequired() || !IsInitialized()) { |
| 127 | return false; |
| 128 | } |
| 129 | return true; |
| 130 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 131 | |
| 132 | NodeId id() const { return id_; } |
| 133 | void id(NodeId id) { id_ = id; } |
| 134 | |
| 135 | private: |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 136 | bool MergeFields(size_t i, Node* at, MergeCache* cache, Graph* graph, |
| 137 | CommonOperatorBuilder* common); |
| 138 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 139 | NodeId id_; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 140 | StatusFlags status_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 141 | ZoneVector<Node*> fields_; |
| 142 | ZoneVector<bool> phi_; |
| 143 | Node* object_state_; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 144 | VirtualState* owner_; |
| 145 | |
| 146 | DISALLOW_COPY_AND_ASSIGN(VirtualObject); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 147 | }; |
| 148 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 149 | DEFINE_OPERATORS_FOR_FLAGS(VirtualObject::StatusFlags) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 150 | |
| 151 | bool VirtualObject::UpdateFrom(const VirtualObject& other) { |
| 152 | bool changed = status_ != other.status_; |
| 153 | status_ = other.status_; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 154 | phi_ = other.phi_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 155 | if (fields_.size() != other.fields_.size()) { |
| 156 | fields_ = other.fields_; |
| 157 | return true; |
| 158 | } |
| 159 | for (size_t i = 0; i < fields_.size(); ++i) { |
| 160 | if (fields_[i] != other.fields_[i]) { |
| 161 | changed = true; |
| 162 | fields_[i] = other.fields_[i]; |
| 163 | } |
| 164 | } |
| 165 | return changed; |
| 166 | } |
| 167 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 168 | class VirtualState : public ZoneObject { |
| 169 | public: |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 170 | VirtualState(Node* owner, Zone* zone, size_t size) |
| 171 | : info_(size, nullptr, zone), owner_(owner) {} |
| 172 | |
| 173 | VirtualState(Node* owner, const VirtualState& state) |
| 174 | : info_(state.info_.size(), nullptr, state.info_.get_allocator().zone()), |
| 175 | owner_(owner) { |
| 176 | for (size_t i = 0; i < info_.size(); ++i) { |
| 177 | if (state.info_[i]) { |
| 178 | info_[i] = state.info_[i]; |
| 179 | } |
| 180 | } |
| 181 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 182 | |
| 183 | VirtualObject* VirtualObjectFromAlias(size_t alias); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 184 | void SetVirtualObject(Alias alias, VirtualObject* state); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 185 | bool UpdateFrom(VirtualState* state, Zone* zone); |
| 186 | bool MergeFrom(MergeCache* cache, Zone* zone, Graph* graph, |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 187 | CommonOperatorBuilder* common, Node* at); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 188 | size_t size() const { return info_.size(); } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 189 | Node* owner() const { return owner_; } |
| 190 | VirtualObject* Copy(VirtualObject* obj, Alias alias); |
| 191 | void SetCopyRequired() { |
| 192 | for (VirtualObject* obj : info_) { |
| 193 | if (obj) obj->SetCopyRequired(); |
| 194 | } |
| 195 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 196 | |
| 197 | private: |
| 198 | ZoneVector<VirtualObject*> info_; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 199 | Node* owner_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 200 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 201 | DISALLOW_COPY_AND_ASSIGN(VirtualState); |
| 202 | }; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 203 | |
| 204 | class MergeCache : public ZoneObject { |
| 205 | public: |
| 206 | explicit MergeCache(Zone* zone) |
| 207 | : states_(zone), objects_(zone), fields_(zone) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 208 | states_.reserve(5); |
| 209 | objects_.reserve(5); |
| 210 | fields_.reserve(5); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 211 | } |
| 212 | ZoneVector<VirtualState*>& states() { return states_; } |
| 213 | ZoneVector<VirtualObject*>& objects() { return objects_; } |
| 214 | ZoneVector<Node*>& fields() { return fields_; } |
| 215 | void Clear() { |
| 216 | states_.clear(); |
| 217 | objects_.clear(); |
| 218 | fields_.clear(); |
| 219 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 220 | size_t LoadVirtualObjectsFromStatesFor(Alias alias); |
| 221 | void LoadVirtualObjectsForFieldsFrom(VirtualState* state, |
| 222 | const ZoneVector<Alias>& aliases); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 223 | Node* GetFields(size_t pos); |
| 224 | |
| 225 | private: |
| 226 | ZoneVector<VirtualState*> states_; |
| 227 | ZoneVector<VirtualObject*> objects_; |
| 228 | ZoneVector<Node*> fields_; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 229 | |
| 230 | DISALLOW_COPY_AND_ASSIGN(MergeCache); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 231 | }; |
| 232 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 233 | size_t MergeCache::LoadVirtualObjectsFromStatesFor(Alias alias) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 234 | objects_.clear(); |
| 235 | DCHECK_GT(states_.size(), 0u); |
| 236 | size_t min = std::numeric_limits<size_t>::max(); |
| 237 | for (VirtualState* state : states_) { |
| 238 | if (VirtualObject* obj = state->VirtualObjectFromAlias(alias)) { |
| 239 | objects_.push_back(obj); |
| 240 | min = std::min(obj->field_count(), min); |
| 241 | } |
| 242 | } |
| 243 | return min; |
| 244 | } |
| 245 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 246 | void MergeCache::LoadVirtualObjectsForFieldsFrom( |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 247 | VirtualState* state, const ZoneVector<Alias>& aliases) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 248 | objects_.clear(); |
| 249 | size_t max_alias = state->size(); |
| 250 | for (Node* field : fields_) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 251 | Alias alias = aliases[field->id()]; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 252 | if (alias >= max_alias) continue; |
| 253 | if (VirtualObject* obj = state->VirtualObjectFromAlias(alias)) { |
| 254 | objects_.push_back(obj); |
| 255 | } |
| 256 | } |
| 257 | } |
| 258 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 259 | Node* MergeCache::GetFields(size_t pos) { |
| 260 | fields_.clear(); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 261 | Node* rep = pos >= objects_.front()->field_count() |
| 262 | ? nullptr |
| 263 | : objects_.front()->GetField(pos); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 264 | for (VirtualObject* obj : objects_) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 265 | if (pos >= obj->field_count()) continue; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 266 | Node* field = obj->GetField(pos); |
| 267 | if (field) { |
| 268 | fields_.push_back(field); |
| 269 | } |
| 270 | if (field != rep) { |
| 271 | rep = nullptr; |
| 272 | } |
| 273 | } |
| 274 | return rep; |
| 275 | } |
| 276 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 277 | VirtualObject* VirtualState::Copy(VirtualObject* obj, Alias alias) { |
| 278 | if (obj->owner() == this) return obj; |
| 279 | VirtualObject* new_obj = |
| 280 | new (info_.get_allocator().zone()) VirtualObject(this, *obj); |
| 281 | TRACE("At state %p, alias @%d (#%d), copying virtual object from %p to %p\n", |
| 282 | static_cast<void*>(this), alias, obj->id(), static_cast<void*>(obj), |
| 283 | static_cast<void*>(new_obj)); |
| 284 | info_[alias] = new_obj; |
| 285 | return new_obj; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 286 | } |
| 287 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 288 | VirtualObject* VirtualState::VirtualObjectFromAlias(size_t alias) { |
| 289 | return info_[alias]; |
| 290 | } |
| 291 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 292 | void VirtualState::SetVirtualObject(Alias alias, VirtualObject* obj) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 293 | info_[alias] = obj; |
| 294 | } |
| 295 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 296 | bool VirtualState::UpdateFrom(VirtualState* from, Zone* zone) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 297 | if (from == this) return false; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 298 | bool changed = false; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 299 | for (Alias alias = 0; alias < size(); ++alias) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 300 | VirtualObject* ls = VirtualObjectFromAlias(alias); |
| 301 | VirtualObject* rs = from->VirtualObjectFromAlias(alias); |
| 302 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 303 | if (ls == rs || rs == nullptr) continue; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 304 | |
| 305 | if (ls == nullptr) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 306 | ls = new (zone) VirtualObject(this, *rs); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 307 | SetVirtualObject(alias, ls); |
| 308 | changed = true; |
| 309 | continue; |
| 310 | } |
| 311 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 312 | TRACE(" Updating fields of @%d\n", alias); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 313 | |
| 314 | changed = ls->UpdateFrom(*rs) || changed; |
| 315 | } |
| 316 | return false; |
| 317 | } |
| 318 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 319 | namespace { |
| 320 | |
| 321 | bool IsEquivalentPhi(Node* node1, Node* node2) { |
| 322 | if (node1 == node2) return true; |
| 323 | if (node1->opcode() != IrOpcode::kPhi || node2->opcode() != IrOpcode::kPhi || |
| 324 | node1->op()->ValueInputCount() != node2->op()->ValueInputCount()) { |
| 325 | return false; |
| 326 | } |
| 327 | for (int i = 0; i < node1->op()->ValueInputCount(); ++i) { |
| 328 | Node* input1 = NodeProperties::GetValueInput(node1, i); |
| 329 | Node* input2 = NodeProperties::GetValueInput(node2, i); |
| 330 | if (!IsEquivalentPhi(input1, input2)) { |
| 331 | return false; |
| 332 | } |
| 333 | } |
| 334 | return true; |
| 335 | } |
| 336 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 337 | bool IsEquivalentPhi(Node* phi, ZoneVector<Node*>& inputs) { |
| 338 | if (phi->opcode() != IrOpcode::kPhi) return false; |
| 339 | if (phi->op()->ValueInputCount() != inputs.size()) { |
| 340 | return false; |
| 341 | } |
| 342 | for (size_t i = 0; i < inputs.size(); ++i) { |
| 343 | Node* input = NodeProperties::GetValueInput(phi, static_cast<int>(i)); |
| 344 | if (!IsEquivalentPhi(input, inputs[i])) { |
| 345 | return false; |
| 346 | } |
| 347 | } |
| 348 | return true; |
| 349 | } |
| 350 | |
| 351 | } // namespace |
| 352 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 353 | bool VirtualObject::MergeFields(size_t i, Node* at, MergeCache* cache, |
| 354 | Graph* graph, CommonOperatorBuilder* common) { |
| 355 | bool changed = false; |
| 356 | int value_input_count = static_cast<int>(cache->fields().size()); |
| 357 | Node* rep = GetField(i); |
| 358 | if (!rep || !IsCreatedPhi(i)) { |
| 359 | Node* control = NodeProperties::GetControlInput(at); |
| 360 | cache->fields().push_back(control); |
| 361 | Node* phi = graph->NewNode( |
| 362 | common->Phi(MachineRepresentation::kTagged, value_input_count), |
| 363 | value_input_count + 1, &cache->fields().front()); |
| 364 | SetField(i, phi, true); |
| 365 | #ifdef DEBUG |
| 366 | if (FLAG_trace_turbo_escape) { |
| 367 | PrintF(" Creating Phi #%d as merge of", phi->id()); |
| 368 | for (int i = 0; i < value_input_count; i++) { |
| 369 | PrintF(" #%d (%s)", cache->fields()[i]->id(), |
| 370 | cache->fields()[i]->op()->mnemonic()); |
| 371 | } |
| 372 | PrintF("\n"); |
| 373 | } |
| 374 | #endif |
| 375 | changed = true; |
| 376 | } else { |
| 377 | DCHECK(rep->opcode() == IrOpcode::kPhi); |
| 378 | for (int n = 0; n < value_input_count; ++n) { |
| 379 | Node* old = NodeProperties::GetValueInput(rep, n); |
| 380 | if (old != cache->fields()[n]) { |
| 381 | changed = true; |
| 382 | NodeProperties::ReplaceValueInput(rep, cache->fields()[n], n); |
| 383 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 384 | } |
| 385 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 386 | return changed; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 387 | } |
| 388 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 389 | bool VirtualObject::MergeFrom(MergeCache* cache, Node* at, Graph* graph, |
| 390 | CommonOperatorBuilder* common) { |
| 391 | DCHECK(at->opcode() == IrOpcode::kEffectPhi || |
| 392 | at->opcode() == IrOpcode::kPhi); |
| 393 | bool changed = false; |
| 394 | for (size_t i = 0; i < field_count(); ++i) { |
| 395 | if (Node* field = cache->GetFields(i)) { |
| 396 | changed = changed || GetField(i) != field; |
| 397 | SetField(i, field); |
| 398 | TRACE(" Field %zu agree on rep #%d\n", i, field->id()); |
| 399 | } else { |
| 400 | int arity = at->opcode() == IrOpcode::kEffectPhi |
| 401 | ? at->op()->EffectInputCount() |
| 402 | : at->op()->ValueInputCount(); |
| 403 | if (cache->fields().size() == arity) { |
| 404 | changed = MergeFields(i, at, cache, graph, common) || changed; |
| 405 | } else { |
| 406 | if (GetField(i) != nullptr) { |
| 407 | TRACE(" Field %zu cleared\n", i); |
| 408 | changed = true; |
| 409 | } |
| 410 | SetField(i, nullptr); |
| 411 | } |
| 412 | } |
| 413 | } |
| 414 | return changed; |
| 415 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 416 | |
| 417 | bool VirtualState::MergeFrom(MergeCache* cache, Zone* zone, Graph* graph, |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 418 | CommonOperatorBuilder* common, Node* at) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 419 | DCHECK_GT(cache->states().size(), 0u); |
| 420 | bool changed = false; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 421 | for (Alias alias = 0; alias < size(); ++alias) { |
| 422 | cache->objects().clear(); |
| 423 | VirtualObject* mergeObject = VirtualObjectFromAlias(alias); |
| 424 | bool copy_merge_object = false; |
| 425 | size_t fields = std::numeric_limits<size_t>::max(); |
| 426 | for (VirtualState* state : cache->states()) { |
| 427 | if (VirtualObject* obj = state->VirtualObjectFromAlias(alias)) { |
| 428 | cache->objects().push_back(obj); |
| 429 | if (mergeObject == obj) { |
| 430 | copy_merge_object = true; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 431 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 432 | fields = std::min(obj->field_count(), fields); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 433 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 434 | } |
| 435 | if (cache->objects().size() == cache->states().size()) { |
| 436 | if (!mergeObject) { |
| 437 | VirtualObject* obj = new (zone) |
| 438 | VirtualObject(cache->objects().front()->id(), this, zone, fields, |
| 439 | cache->objects().front()->IsInitialized()); |
| 440 | SetVirtualObject(alias, obj); |
| 441 | mergeObject = obj; |
| 442 | changed = true; |
| 443 | } else if (copy_merge_object) { |
| 444 | VirtualObject* obj = new (zone) VirtualObject(this, *mergeObject); |
| 445 | SetVirtualObject(alias, obj); |
| 446 | mergeObject = obj; |
| 447 | changed = true; |
| 448 | } else { |
| 449 | changed = mergeObject->ResizeFields(fields) || changed; |
| 450 | } |
| 451 | #ifdef DEBUG |
| 452 | if (FLAG_trace_turbo_escape) { |
| 453 | PrintF(" Alias @%d, merging into %p virtual objects", alias, |
| 454 | static_cast<void*>(mergeObject)); |
| 455 | for (size_t i = 0; i < cache->objects().size(); i++) { |
| 456 | PrintF(" %p", static_cast<void*>(cache->objects()[i])); |
| 457 | } |
| 458 | PrintF("\n"); |
| 459 | } |
| 460 | #endif // DEBUG |
| 461 | changed = mergeObject->MergeFrom(cache, at, graph, common) || changed; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 462 | } else { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 463 | if (mergeObject) { |
| 464 | TRACE(" Alias %d, virtual object removed\n", alias); |
| 465 | changed = true; |
| 466 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 467 | SetVirtualObject(alias, nullptr); |
| 468 | } |
| 469 | } |
| 470 | return changed; |
| 471 | } |
| 472 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 473 | EscapeStatusAnalysis::EscapeStatusAnalysis(EscapeAnalysis* object_analysis, |
| 474 | Graph* graph, Zone* zone) |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 475 | : stack_(zone), |
| 476 | object_analysis_(object_analysis), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 477 | graph_(graph), |
| 478 | zone_(zone), |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 479 | status_(zone), |
| 480 | next_free_alias_(0), |
| 481 | status_stack_(zone), |
| 482 | aliases_(zone) {} |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 483 | |
| 484 | EscapeStatusAnalysis::~EscapeStatusAnalysis() {} |
| 485 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 486 | bool EscapeStatusAnalysis::HasEntry(Node* node) { |
| 487 | return status_[node->id()] & (kTracked | kEscaped); |
| 488 | } |
| 489 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 490 | bool EscapeStatusAnalysis::IsVirtual(Node* node) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 491 | return IsVirtual(node->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 492 | } |
| 493 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 494 | bool EscapeStatusAnalysis::IsVirtual(NodeId id) { |
| 495 | return (status_[id] & kTracked) && !(status_[id] & kEscaped); |
| 496 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 497 | |
| 498 | bool EscapeStatusAnalysis::IsEscaped(Node* node) { |
| 499 | return status_[node->id()] & kEscaped; |
| 500 | } |
| 501 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 502 | bool EscapeStatusAnalysis::IsAllocation(Node* node) { |
| 503 | return node->opcode() == IrOpcode::kAllocate || |
| 504 | node->opcode() == IrOpcode::kFinishRegion; |
| 505 | } |
| 506 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 507 | bool EscapeStatusAnalysis::SetEscaped(Node* node) { |
| 508 | bool changed = !(status_[node->id()] & kEscaped); |
| 509 | status_[node->id()] |= kEscaped | kTracked; |
| 510 | return changed; |
| 511 | } |
| 512 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 513 | bool EscapeStatusAnalysis::IsInQueue(NodeId id) { |
| 514 | return status_[id] & kInQueue; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 515 | } |
| 516 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 517 | void EscapeStatusAnalysis::SetInQueue(NodeId id, bool on_stack) { |
| 518 | if (on_stack) { |
| 519 | status_[id] |= kInQueue; |
| 520 | } else { |
| 521 | status_[id] &= ~kInQueue; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 522 | } |
| 523 | } |
| 524 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 525 | void EscapeStatusAnalysis::ResizeStatusVector() { |
| 526 | if (status_.size() <= graph()->NodeCount()) { |
| 527 | status_.resize(graph()->NodeCount() * 1.1, kUnknown); |
| 528 | } |
| 529 | } |
| 530 | |
| 531 | size_t EscapeStatusAnalysis::GetStatusVectorSize() { return status_.size(); } |
| 532 | |
| 533 | void EscapeStatusAnalysis::RunStatusAnalysis() { |
| 534 | ResizeStatusVector(); |
| 535 | while (!status_stack_.empty()) { |
| 536 | Node* node = status_stack_.back(); |
| 537 | status_stack_.pop_back(); |
| 538 | status_[node->id()] &= ~kOnStack; |
| 539 | Process(node); |
| 540 | status_[node->id()] |= kVisited; |
| 541 | } |
| 542 | } |
| 543 | |
| 544 | void EscapeStatusAnalysis::EnqueueForStatusAnalysis(Node* node) { |
| 545 | DCHECK_NOT_NULL(node); |
| 546 | if (!(status_[node->id()] & kOnStack)) { |
| 547 | status_stack_.push_back(node); |
| 548 | status_[node->id()] |= kOnStack; |
| 549 | } |
| 550 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 551 | |
| 552 | void EscapeStatusAnalysis::RevisitInputs(Node* node) { |
| 553 | for (Edge edge : node->input_edges()) { |
| 554 | Node* input = edge.to(); |
| 555 | if (!(status_[input->id()] & kOnStack)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 556 | status_stack_.push_back(input); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 557 | status_[input->id()] |= kOnStack; |
| 558 | } |
| 559 | } |
| 560 | } |
| 561 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 562 | void EscapeStatusAnalysis::RevisitUses(Node* node) { |
| 563 | for (Edge edge : node->use_edges()) { |
| 564 | Node* use = edge.from(); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 565 | if (!(status_[use->id()] & kOnStack) && !IsNotReachable(use)) { |
| 566 | status_stack_.push_back(use); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 567 | status_[use->id()] |= kOnStack; |
| 568 | } |
| 569 | } |
| 570 | } |
| 571 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 572 | void EscapeStatusAnalysis::Process(Node* node) { |
| 573 | switch (node->opcode()) { |
| 574 | case IrOpcode::kAllocate: |
| 575 | ProcessAllocate(node); |
| 576 | break; |
| 577 | case IrOpcode::kFinishRegion: |
| 578 | ProcessFinishRegion(node); |
| 579 | break; |
| 580 | case IrOpcode::kStoreField: |
| 581 | ProcessStoreField(node); |
| 582 | break; |
| 583 | case IrOpcode::kStoreElement: |
| 584 | ProcessStoreElement(node); |
| 585 | break; |
| 586 | case IrOpcode::kLoadField: |
| 587 | case IrOpcode::kLoadElement: { |
| 588 | if (Node* rep = object_analysis_->GetReplacement(node)) { |
| 589 | if (IsAllocation(rep) && CheckUsesForEscape(node, rep)) { |
| 590 | RevisitInputs(rep); |
| 591 | RevisitUses(rep); |
| 592 | } |
| 593 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 594 | RevisitUses(node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 595 | break; |
| 596 | } |
| 597 | case IrOpcode::kPhi: |
| 598 | if (!HasEntry(node)) { |
| 599 | status_[node->id()] |= kTracked; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 600 | RevisitUses(node); |
| 601 | } |
| 602 | if (!IsAllocationPhi(node) && SetEscaped(node)) { |
| 603 | RevisitInputs(node); |
| 604 | RevisitUses(node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 605 | } |
| 606 | CheckUsesForEscape(node); |
| 607 | default: |
| 608 | break; |
| 609 | } |
| 610 | } |
| 611 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 612 | bool EscapeStatusAnalysis::IsAllocationPhi(Node* node) { |
| 613 | for (Edge edge : node->input_edges()) { |
| 614 | Node* input = edge.to(); |
| 615 | if (input->opcode() == IrOpcode::kPhi && !IsEscaped(input)) continue; |
| 616 | if (IsAllocation(input)) continue; |
| 617 | return false; |
| 618 | } |
| 619 | return true; |
| 620 | } |
| 621 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 622 | void EscapeStatusAnalysis::ProcessStoreField(Node* node) { |
| 623 | DCHECK_EQ(node->opcode(), IrOpcode::kStoreField); |
| 624 | Node* to = NodeProperties::GetValueInput(node, 0); |
| 625 | Node* val = NodeProperties::GetValueInput(node, 1); |
| 626 | if ((IsEscaped(to) || !IsAllocation(to)) && SetEscaped(val)) { |
| 627 | RevisitUses(val); |
| 628 | RevisitInputs(val); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 629 | TRACE("Setting #%d (%s) to escaped because of store to field of #%d\n", |
| 630 | val->id(), val->op()->mnemonic(), to->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 631 | } |
| 632 | } |
| 633 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 634 | void EscapeStatusAnalysis::ProcessStoreElement(Node* node) { |
| 635 | DCHECK_EQ(node->opcode(), IrOpcode::kStoreElement); |
| 636 | Node* to = NodeProperties::GetValueInput(node, 0); |
| 637 | Node* val = NodeProperties::GetValueInput(node, 2); |
| 638 | if ((IsEscaped(to) || !IsAllocation(to)) && SetEscaped(val)) { |
| 639 | RevisitUses(val); |
| 640 | RevisitInputs(val); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 641 | TRACE("Setting #%d (%s) to escaped because of store to field of #%d\n", |
| 642 | val->id(), val->op()->mnemonic(), to->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 643 | } |
| 644 | } |
| 645 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 646 | void EscapeStatusAnalysis::ProcessAllocate(Node* node) { |
| 647 | DCHECK_EQ(node->opcode(), IrOpcode::kAllocate); |
| 648 | if (!HasEntry(node)) { |
| 649 | status_[node->id()] |= kTracked; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 650 | TRACE("Created status entry for node #%d (%s)\n", node->id(), |
| 651 | node->op()->mnemonic()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 652 | NumberMatcher size(node->InputAt(0)); |
| 653 | DCHECK(node->InputAt(0)->opcode() != IrOpcode::kInt32Constant && |
| 654 | node->InputAt(0)->opcode() != IrOpcode::kInt64Constant && |
| 655 | node->InputAt(0)->opcode() != IrOpcode::kFloat32Constant && |
| 656 | node->InputAt(0)->opcode() != IrOpcode::kFloat64Constant); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 657 | RevisitUses(node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 658 | if (!size.HasValue() && SetEscaped(node)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 659 | TRACE("Setting #%d to escaped because of non-const alloc\n", node->id()); |
| 660 | // This node is already known to escape, uses do not have to be checked |
| 661 | // for escape. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 662 | return; |
| 663 | } |
| 664 | } |
| 665 | if (CheckUsesForEscape(node, true)) { |
| 666 | RevisitUses(node); |
| 667 | } |
| 668 | } |
| 669 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 670 | bool EscapeStatusAnalysis::CheckUsesForEscape(Node* uses, Node* rep, |
| 671 | bool phi_escaping) { |
| 672 | for (Edge edge : uses->use_edges()) { |
| 673 | Node* use = edge.from(); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 674 | if (IsNotReachable(use)) continue; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 675 | if (edge.index() >= use->op()->ValueInputCount() + |
| 676 | OperatorProperties::GetContextInputCount(use->op())) |
| 677 | continue; |
| 678 | switch (use->opcode()) { |
| 679 | case IrOpcode::kPhi: |
| 680 | if (phi_escaping && SetEscaped(rep)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 681 | TRACE( |
| 682 | "Setting #%d (%s) to escaped because of use by phi node " |
| 683 | "#%d (%s)\n", |
| 684 | rep->id(), rep->op()->mnemonic(), use->id(), |
| 685 | use->op()->mnemonic()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 686 | return true; |
| 687 | } |
| 688 | // Fallthrough. |
| 689 | case IrOpcode::kStoreField: |
| 690 | case IrOpcode::kLoadField: |
| 691 | case IrOpcode::kStoreElement: |
| 692 | case IrOpcode::kLoadElement: |
| 693 | case IrOpcode::kFrameState: |
| 694 | case IrOpcode::kStateValues: |
| 695 | case IrOpcode::kReferenceEqual: |
| 696 | case IrOpcode::kFinishRegion: |
| 697 | if (IsEscaped(use) && SetEscaped(rep)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 698 | TRACE( |
| 699 | "Setting #%d (%s) to escaped because of use by escaping node " |
| 700 | "#%d (%s)\n", |
| 701 | rep->id(), rep->op()->mnemonic(), use->id(), |
| 702 | use->op()->mnemonic()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 703 | return true; |
| 704 | } |
| 705 | break; |
| 706 | case IrOpcode::kObjectIsSmi: |
| 707 | if (!IsAllocation(rep) && SetEscaped(rep)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 708 | TRACE("Setting #%d (%s) to escaped because of use by #%d (%s)\n", |
| 709 | rep->id(), rep->op()->mnemonic(), use->id(), |
| 710 | use->op()->mnemonic()); |
| 711 | return true; |
| 712 | } |
| 713 | break; |
| 714 | case IrOpcode::kSelect: |
| 715 | if (SetEscaped(rep)) { |
| 716 | TRACE("Setting #%d (%s) to escaped because of use by #%d (%s)\n", |
| 717 | rep->id(), rep->op()->mnemonic(), use->id(), |
| 718 | use->op()->mnemonic()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 719 | return true; |
| 720 | } |
| 721 | break; |
| 722 | default: |
| 723 | if (use->op()->EffectInputCount() == 0 && |
| 724 | uses->op()->EffectInputCount() > 0) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 725 | TRACE("Encountered unaccounted use by #%d (%s)\n", use->id(), |
| 726 | use->op()->mnemonic()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 727 | UNREACHABLE(); |
| 728 | } |
| 729 | if (SetEscaped(rep)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 730 | TRACE("Setting #%d (%s) to escaped because of use by #%d (%s)\n", |
| 731 | rep->id(), rep->op()->mnemonic(), use->id(), |
| 732 | use->op()->mnemonic()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 733 | return true; |
| 734 | } |
| 735 | } |
| 736 | } |
| 737 | return false; |
| 738 | } |
| 739 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 740 | void EscapeStatusAnalysis::ProcessFinishRegion(Node* node) { |
| 741 | DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion); |
| 742 | if (!HasEntry(node)) { |
| 743 | status_[node->id()] |= kTracked; |
| 744 | RevisitUses(node); |
| 745 | } |
| 746 | if (CheckUsesForEscape(node, true)) { |
| 747 | RevisitInputs(node); |
| 748 | } |
| 749 | } |
| 750 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 751 | void EscapeStatusAnalysis::DebugPrint() { |
| 752 | for (NodeId id = 0; id < status_.size(); id++) { |
| 753 | if (status_[id] & kTracked) { |
| 754 | PrintF("Node #%d is %s\n", id, |
| 755 | (status_[id] & kEscaped) ? "escaping" : "virtual"); |
| 756 | } |
| 757 | } |
| 758 | } |
| 759 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 760 | EscapeAnalysis::EscapeAnalysis(Graph* graph, CommonOperatorBuilder* common, |
| 761 | Zone* zone) |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 762 | : status_analysis_(this, graph, zone), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 763 | common_(common), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 764 | virtual_states_(zone), |
| 765 | replacements_(zone), |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 766 | cache_(nullptr) {} |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 767 | |
| 768 | EscapeAnalysis::~EscapeAnalysis() {} |
| 769 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 770 | void EscapeAnalysis::Run() { |
| 771 | replacements_.resize(graph()->NodeCount()); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 772 | status_analysis_.AssignAliases(); |
| 773 | if (status_analysis_.AliasCount() > 0) { |
| 774 | cache_ = new (zone()) MergeCache(zone()); |
| 775 | replacements_.resize(graph()->NodeCount()); |
| 776 | status_analysis_.ResizeStatusVector(); |
| 777 | RunObjectAnalysis(); |
| 778 | status_analysis_.RunStatusAnalysis(); |
| 779 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 780 | } |
| 781 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 782 | void EscapeStatusAnalysis::AssignAliases() { |
| 783 | size_t max_size = 1024; |
| 784 | size_t min_size = 32; |
| 785 | size_t stack_size = |
| 786 | std::min(std::max(graph()->NodeCount() / 5, min_size), max_size); |
| 787 | stack_.reserve(stack_size); |
| 788 | ResizeStatusVector(); |
| 789 | stack_.push_back(graph()->end()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 790 | CHECK_LT(graph()->NodeCount(), kUntrackable); |
| 791 | aliases_.resize(graph()->NodeCount(), kNotReachable); |
| 792 | aliases_[graph()->end()->id()] = kUntrackable; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 793 | status_stack_.reserve(8); |
| 794 | TRACE("Discovering trackable nodes"); |
| 795 | while (!stack_.empty()) { |
| 796 | Node* node = stack_.back(); |
| 797 | stack_.pop_back(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 798 | switch (node->opcode()) { |
| 799 | case IrOpcode::kAllocate: |
| 800 | if (aliases_[node->id()] >= kUntrackable) { |
| 801 | aliases_[node->id()] = NextAlias(); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 802 | TRACE(" @%d:%s#%u", aliases_[node->id()], node->op()->mnemonic(), |
| 803 | node->id()); |
| 804 | EnqueueForStatusAnalysis(node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 805 | } |
| 806 | break; |
| 807 | case IrOpcode::kFinishRegion: { |
| 808 | Node* allocate = NodeProperties::GetValueInput(node, 0); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 809 | DCHECK_NOT_NULL(allocate); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 810 | if (allocate->opcode() == IrOpcode::kAllocate) { |
| 811 | if (aliases_[allocate->id()] >= kUntrackable) { |
| 812 | if (aliases_[allocate->id()] == kNotReachable) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 813 | stack_.push_back(allocate); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 814 | } |
| 815 | aliases_[allocate->id()] = NextAlias(); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 816 | TRACE(" @%d:%s#%u", aliases_[allocate->id()], |
| 817 | allocate->op()->mnemonic(), allocate->id()); |
| 818 | EnqueueForStatusAnalysis(allocate); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 819 | } |
| 820 | aliases_[node->id()] = aliases_[allocate->id()]; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 821 | TRACE(" @%d:%s#%u", aliases_[node->id()], node->op()->mnemonic(), |
| 822 | node->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 823 | } |
| 824 | break; |
| 825 | } |
| 826 | default: |
| 827 | DCHECK_EQ(aliases_[node->id()], kUntrackable); |
| 828 | break; |
| 829 | } |
| 830 | for (Edge edge : node->input_edges()) { |
| 831 | Node* input = edge.to(); |
| 832 | if (aliases_[input->id()] == kNotReachable) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 833 | stack_.push_back(input); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 834 | aliases_[input->id()] = kUntrackable; |
| 835 | } |
| 836 | } |
| 837 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 838 | TRACE("\n"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 839 | } |
| 840 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 841 | bool EscapeStatusAnalysis::IsNotReachable(Node* node) { |
| 842 | if (node->id() >= aliases_.size()) { |
| 843 | return false; |
| 844 | } |
| 845 | return aliases_[node->id()] == kNotReachable; |
| 846 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 847 | |
| 848 | void EscapeAnalysis::RunObjectAnalysis() { |
| 849 | virtual_states_.resize(graph()->NodeCount()); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 850 | ZoneDeque<Node*> queue(zone()); |
| 851 | queue.push_back(graph()->start()); |
| 852 | ZoneVector<Node*> danglers(zone()); |
| 853 | while (!queue.empty()) { |
| 854 | Node* node = queue.back(); |
| 855 | queue.pop_back(); |
| 856 | status_analysis_.SetInQueue(node->id(), false); |
| 857 | if (Process(node)) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 858 | for (Edge edge : node->use_edges()) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 859 | Node* use = edge.from(); |
| 860 | if (IsNotReachable(use)) { |
| 861 | continue; |
| 862 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 863 | if (NodeProperties::IsEffectEdge(edge)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 864 | // Iteration order: depth first, but delay phis. |
| 865 | // We need DFS do avoid some duplication of VirtualStates and |
| 866 | // VirtualObjects, and we want to delay phis to improve performance. |
| 867 | if (use->opcode() == IrOpcode::kEffectPhi) { |
| 868 | if (!status_analysis_.IsInQueue(use->id())) { |
| 869 | queue.push_front(use); |
| 870 | } |
| 871 | } else if ((use->opcode() != IrOpcode::kLoadField && |
| 872 | use->opcode() != IrOpcode::kLoadElement) || |
| 873 | !IsDanglingEffectNode(use)) { |
| 874 | if (!status_analysis_.IsInQueue(use->id())) { |
| 875 | status_analysis_.SetInQueue(use->id(), true); |
| 876 | queue.push_back(use); |
| 877 | } |
| 878 | } else { |
| 879 | danglers.push_back(use); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 880 | } |
| 881 | } |
| 882 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 883 | // Danglers need to be processed immediately, even if they are |
| 884 | // on the stack. Since they do not have effect outputs, |
| 885 | // we don't have to track whether they are on the stack. |
| 886 | queue.insert(queue.end(), danglers.begin(), danglers.end()); |
| 887 | danglers.clear(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 888 | } |
| 889 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 890 | #ifdef DEBUG |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 891 | if (FLAG_trace_turbo_escape) { |
| 892 | DebugPrint(); |
| 893 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 894 | #endif |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 895 | } |
| 896 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 897 | bool EscapeStatusAnalysis::IsDanglingEffectNode(Node* node) { |
| 898 | if (status_[node->id()] & kDanglingComputed) { |
| 899 | return status_[node->id()] & kDangling; |
| 900 | } |
| 901 | if (node->op()->EffectInputCount() == 0 || |
| 902 | node->op()->EffectOutputCount() == 0 || |
| 903 | (node->op()->EffectInputCount() == 1 && |
| 904 | NodeProperties::GetEffectInput(node)->opcode() == IrOpcode::kStart)) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 905 | // The start node is used as sentinel for nodes that are in general |
| 906 | // effectful, but of which an analysis has determined that they do not |
| 907 | // produce effects in this instance. We don't consider these nodes dangling. |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 908 | status_[node->id()] |= kDanglingComputed; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 909 | return false; |
| 910 | } |
| 911 | for (Edge edge : node->use_edges()) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 912 | Node* use = edge.from(); |
| 913 | if (aliases_[use->id()] == kNotReachable) continue; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 914 | if (NodeProperties::IsEffectEdge(edge)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 915 | status_[node->id()] |= kDanglingComputed; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 916 | return false; |
| 917 | } |
| 918 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 919 | status_[node->id()] |= kDanglingComputed | kDangling; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 920 | return true; |
| 921 | } |
| 922 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 923 | bool EscapeStatusAnalysis::IsEffectBranchPoint(Node* node) { |
| 924 | if (status_[node->id()] & kBranchPointComputed) { |
| 925 | return status_[node->id()] & kBranchPoint; |
| 926 | } |
| 927 | int count = 0; |
| 928 | for (Edge edge : node->use_edges()) { |
| 929 | Node* use = edge.from(); |
| 930 | if (aliases_[use->id()] == kNotReachable) continue; |
| 931 | if (NodeProperties::IsEffectEdge(edge)) { |
| 932 | if ((use->opcode() == IrOpcode::kLoadField || |
| 933 | use->opcode() == IrOpcode::kLoadElement || |
| 934 | use->opcode() == IrOpcode::kLoad) && |
| 935 | IsDanglingEffectNode(use)) |
| 936 | continue; |
| 937 | if (++count > 1) { |
| 938 | status_[node->id()] |= kBranchPointComputed | kBranchPoint; |
| 939 | return true; |
| 940 | } |
| 941 | } |
| 942 | } |
| 943 | status_[node->id()] |= kBranchPointComputed; |
| 944 | return false; |
| 945 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 946 | |
| 947 | bool EscapeAnalysis::Process(Node* node) { |
| 948 | switch (node->opcode()) { |
| 949 | case IrOpcode::kAllocate: |
| 950 | ProcessAllocation(node); |
| 951 | break; |
| 952 | case IrOpcode::kBeginRegion: |
| 953 | ForwardVirtualState(node); |
| 954 | break; |
| 955 | case IrOpcode::kFinishRegion: |
| 956 | ProcessFinishRegion(node); |
| 957 | break; |
| 958 | case IrOpcode::kStoreField: |
| 959 | ProcessStoreField(node); |
| 960 | break; |
| 961 | case IrOpcode::kLoadField: |
| 962 | ProcessLoadField(node); |
| 963 | break; |
| 964 | case IrOpcode::kStoreElement: |
| 965 | ProcessStoreElement(node); |
| 966 | break; |
| 967 | case IrOpcode::kLoadElement: |
| 968 | ProcessLoadElement(node); |
| 969 | break; |
| 970 | case IrOpcode::kStart: |
| 971 | ProcessStart(node); |
| 972 | break; |
| 973 | case IrOpcode::kEffectPhi: |
| 974 | return ProcessEffectPhi(node); |
| 975 | break; |
| 976 | default: |
| 977 | if (node->op()->EffectInputCount() > 0) { |
| 978 | ForwardVirtualState(node); |
| 979 | } |
| 980 | ProcessAllocationUsers(node); |
| 981 | break; |
| 982 | } |
| 983 | return true; |
| 984 | } |
| 985 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 986 | void EscapeAnalysis::ProcessAllocationUsers(Node* node) { |
| 987 | for (Edge edge : node->input_edges()) { |
| 988 | Node* input = edge.to(); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 989 | Node* use = edge.from(); |
| 990 | if (edge.index() >= use->op()->ValueInputCount() + |
| 991 | OperatorProperties::GetContextInputCount(use->op())) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 992 | continue; |
| 993 | switch (node->opcode()) { |
| 994 | case IrOpcode::kStoreField: |
| 995 | case IrOpcode::kLoadField: |
| 996 | case IrOpcode::kStoreElement: |
| 997 | case IrOpcode::kLoadElement: |
| 998 | case IrOpcode::kFrameState: |
| 999 | case IrOpcode::kStateValues: |
| 1000 | case IrOpcode::kReferenceEqual: |
| 1001 | case IrOpcode::kFinishRegion: |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1002 | case IrOpcode::kObjectIsSmi: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1003 | break; |
| 1004 | default: |
| 1005 | VirtualState* state = virtual_states_[node->id()]; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1006 | if (VirtualObject* obj = |
| 1007 | GetVirtualObject(state, ResolveReplacement(input))) { |
| 1008 | if (!obj->AllFieldsClear()) { |
| 1009 | obj = CopyForModificationAt(obj, state, node); |
| 1010 | obj->ClearAllFields(); |
| 1011 | TRACE("Cleared all fields of @%d:#%d\n", GetAlias(obj->id()), |
| 1012 | obj->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1013 | } |
| 1014 | } |
| 1015 | break; |
| 1016 | } |
| 1017 | } |
| 1018 | } |
| 1019 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1020 | VirtualState* EscapeAnalysis::CopyForModificationAt(VirtualState* state, |
| 1021 | Node* node) { |
| 1022 | if (state->owner() != node) { |
| 1023 | VirtualState* new_state = new (zone()) VirtualState(node, *state); |
| 1024 | virtual_states_[node->id()] = new_state; |
| 1025 | TRACE("Copying virtual state %p to new state %p at node %s#%d\n", |
| 1026 | static_cast<void*>(state), static_cast<void*>(new_state), |
| 1027 | node->op()->mnemonic(), node->id()); |
| 1028 | return new_state; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1029 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1030 | return state; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1031 | } |
| 1032 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1033 | VirtualObject* EscapeAnalysis::CopyForModificationAt(VirtualObject* obj, |
| 1034 | VirtualState* state, |
| 1035 | Node* node) { |
| 1036 | if (obj->NeedCopyForModification()) { |
| 1037 | state = CopyForModificationAt(state, node); |
| 1038 | return state->Copy(obj, GetAlias(obj->id())); |
| 1039 | } |
| 1040 | return obj; |
| 1041 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1042 | |
| 1043 | void EscapeAnalysis::ForwardVirtualState(Node* node) { |
| 1044 | DCHECK_EQ(node->op()->EffectInputCount(), 1); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1045 | #ifdef DEBUG |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1046 | if (node->opcode() != IrOpcode::kLoadField && |
| 1047 | node->opcode() != IrOpcode::kLoadElement && |
| 1048 | node->opcode() != IrOpcode::kLoad && IsDanglingEffectNode(node)) { |
| 1049 | PrintF("Dangeling effect node: #%d (%s)\n", node->id(), |
| 1050 | node->op()->mnemonic()); |
| 1051 | UNREACHABLE(); |
| 1052 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1053 | #endif // DEBUG |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1054 | Node* effect = NodeProperties::GetEffectInput(node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1055 | DCHECK_NOT_NULL(virtual_states_[effect->id()]); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1056 | if (virtual_states_[node->id()]) { |
| 1057 | virtual_states_[node->id()]->UpdateFrom(virtual_states_[effect->id()], |
| 1058 | zone()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1059 | } else { |
| 1060 | virtual_states_[node->id()] = virtual_states_[effect->id()]; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1061 | TRACE("Forwarding object state %p from %s#%d to %s#%d", |
| 1062 | static_cast<void*>(virtual_states_[effect->id()]), |
| 1063 | effect->op()->mnemonic(), effect->id(), node->op()->mnemonic(), |
| 1064 | node->id()); |
| 1065 | if (IsEffectBranchPoint(effect) || |
| 1066 | OperatorProperties::GetFrameStateInputCount(node->op()) > 0) { |
| 1067 | virtual_states_[node->id()]->SetCopyRequired(); |
| 1068 | TRACE(", effect input %s#%d is branch point", effect->op()->mnemonic(), |
| 1069 | effect->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1070 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1071 | TRACE("\n"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1072 | } |
| 1073 | } |
| 1074 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1075 | void EscapeAnalysis::ProcessStart(Node* node) { |
| 1076 | DCHECK_EQ(node->opcode(), IrOpcode::kStart); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1077 | virtual_states_[node->id()] = |
| 1078 | new (zone()) VirtualState(node, zone(), AliasCount()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1079 | } |
| 1080 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1081 | bool EscapeAnalysis::ProcessEffectPhi(Node* node) { |
| 1082 | DCHECK_EQ(node->opcode(), IrOpcode::kEffectPhi); |
| 1083 | bool changed = false; |
| 1084 | |
| 1085 | VirtualState* mergeState = virtual_states_[node->id()]; |
| 1086 | if (!mergeState) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1087 | mergeState = new (zone()) VirtualState(node, zone(), AliasCount()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1088 | virtual_states_[node->id()] = mergeState; |
| 1089 | changed = true; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1090 | TRACE("Effect Phi #%d got new virtual state %p.\n", node->id(), |
| 1091 | static_cast<void*>(mergeState)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1092 | } |
| 1093 | |
| 1094 | cache_->Clear(); |
| 1095 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1096 | TRACE("At Effect Phi #%d, merging states into %p:", node->id(), |
| 1097 | static_cast<void*>(mergeState)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1098 | |
| 1099 | for (int i = 0; i < node->op()->EffectInputCount(); ++i) { |
| 1100 | Node* input = NodeProperties::GetEffectInput(node, i); |
| 1101 | VirtualState* state = virtual_states_[input->id()]; |
| 1102 | if (state) { |
| 1103 | cache_->states().push_back(state); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1104 | if (state == mergeState) { |
| 1105 | mergeState = new (zone()) VirtualState(node, zone(), AliasCount()); |
| 1106 | virtual_states_[node->id()] = mergeState; |
| 1107 | changed = true; |
| 1108 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1109 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1110 | TRACE(" %p (from %d %s)", static_cast<void*>(state), input->id(), |
| 1111 | input->op()->mnemonic()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1112 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1113 | TRACE("\n"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1114 | |
| 1115 | if (cache_->states().size() == 0) { |
| 1116 | return changed; |
| 1117 | } |
| 1118 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1119 | changed = |
| 1120 | mergeState->MergeFrom(cache_, zone(), graph(), common(), node) || changed; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1121 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1122 | TRACE("Merge %s the node.\n", changed ? "changed" : "did not change"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1123 | |
| 1124 | if (changed) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1125 | status_analysis_.ResizeStatusVector(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1126 | } |
| 1127 | return changed; |
| 1128 | } |
| 1129 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1130 | void EscapeAnalysis::ProcessAllocation(Node* node) { |
| 1131 | DCHECK_EQ(node->opcode(), IrOpcode::kAllocate); |
| 1132 | ForwardVirtualState(node); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1133 | VirtualState* state = virtual_states_[node->id()]; |
| 1134 | Alias alias = GetAlias(node->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1135 | |
| 1136 | // Check if we have already processed this node. |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1137 | if (state->VirtualObjectFromAlias(alias)) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1138 | return; |
| 1139 | } |
| 1140 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1141 | if (state->owner()->opcode() == IrOpcode::kEffectPhi) { |
| 1142 | state = CopyForModificationAt(state, node); |
| 1143 | } |
| 1144 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1145 | NumberMatcher size(node->InputAt(0)); |
| 1146 | DCHECK(node->InputAt(0)->opcode() != IrOpcode::kInt32Constant && |
| 1147 | node->InputAt(0)->opcode() != IrOpcode::kInt64Constant && |
| 1148 | node->InputAt(0)->opcode() != IrOpcode::kFloat32Constant && |
| 1149 | node->InputAt(0)->opcode() != IrOpcode::kFloat64Constant); |
| 1150 | if (size.HasValue()) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1151 | VirtualObject* obj = new (zone()) VirtualObject( |
| 1152 | node->id(), state, zone(), size.Value() / kPointerSize, false); |
| 1153 | state->SetVirtualObject(alias, obj); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1154 | } else { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1155 | state->SetVirtualObject( |
| 1156 | alias, new (zone()) VirtualObject(node->id(), state, zone())); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1157 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1158 | } |
| 1159 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1160 | void EscapeAnalysis::ProcessFinishRegion(Node* node) { |
| 1161 | DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion); |
| 1162 | ForwardVirtualState(node); |
| 1163 | Node* allocation = NodeProperties::GetValueInput(node, 0); |
| 1164 | if (allocation->opcode() == IrOpcode::kAllocate) { |
| 1165 | VirtualState* state = virtual_states_[node->id()]; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1166 | VirtualObject* obj = state->VirtualObjectFromAlias(GetAlias(node->id())); |
| 1167 | DCHECK_NOT_NULL(obj); |
| 1168 | obj->SetInitialized(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1169 | } |
| 1170 | } |
| 1171 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1172 | Node* EscapeAnalysis::replacement(NodeId id) { |
| 1173 | if (id >= replacements_.size()) return nullptr; |
| 1174 | return replacements_[id]; |
| 1175 | } |
| 1176 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1177 | Node* EscapeAnalysis::replacement(Node* node) { |
| 1178 | return replacement(node->id()); |
| 1179 | } |
| 1180 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1181 | bool EscapeAnalysis::SetReplacement(Node* node, Node* rep) { |
| 1182 | bool changed = replacements_[node->id()] != rep; |
| 1183 | replacements_[node->id()] = rep; |
| 1184 | return changed; |
| 1185 | } |
| 1186 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1187 | bool EscapeAnalysis::UpdateReplacement(VirtualState* state, Node* node, |
| 1188 | Node* rep) { |
| 1189 | if (SetReplacement(node, rep)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1190 | if (rep) { |
| 1191 | TRACE("Replacement of #%d is #%d (%s)\n", node->id(), rep->id(), |
| 1192 | rep->op()->mnemonic()); |
| 1193 | } else { |
| 1194 | TRACE("Replacement of #%d cleared\n", node->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1195 | } |
| 1196 | return true; |
| 1197 | } |
| 1198 | return false; |
| 1199 | } |
| 1200 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1201 | Node* EscapeAnalysis::ResolveReplacement(Node* node) { |
| 1202 | while (replacement(node)) { |
| 1203 | node = replacement(node); |
| 1204 | } |
| 1205 | return node; |
| 1206 | } |
| 1207 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1208 | Node* EscapeAnalysis::GetReplacement(Node* node) { |
| 1209 | return GetReplacement(node->id()); |
| 1210 | } |
| 1211 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1212 | Node* EscapeAnalysis::GetReplacement(NodeId id) { |
| 1213 | Node* node = nullptr; |
| 1214 | while (replacement(id)) { |
| 1215 | node = replacement(id); |
| 1216 | id = node->id(); |
| 1217 | } |
| 1218 | return node; |
| 1219 | } |
| 1220 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1221 | bool EscapeAnalysis::IsVirtual(Node* node) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1222 | if (node->id() >= status_analysis_.GetStatusVectorSize()) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1223 | return false; |
| 1224 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1225 | return status_analysis_.IsVirtual(node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1226 | } |
| 1227 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1228 | bool EscapeAnalysis::IsEscaped(Node* node) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1229 | if (node->id() >= status_analysis_.GetStatusVectorSize()) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1230 | return false; |
| 1231 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1232 | return status_analysis_.IsEscaped(node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1233 | } |
| 1234 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1235 | bool EscapeAnalysis::SetEscaped(Node* node) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1236 | return status_analysis_.SetEscaped(node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1237 | } |
| 1238 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1239 | VirtualObject* EscapeAnalysis::GetVirtualObject(Node* at, NodeId id) { |
| 1240 | if (VirtualState* states = virtual_states_[at->id()]) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1241 | return states->VirtualObjectFromAlias(GetAlias(id)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1242 | } |
| 1243 | return nullptr; |
| 1244 | } |
| 1245 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1246 | bool EscapeAnalysis::CompareVirtualObjects(Node* left, Node* right) { |
| 1247 | DCHECK(IsVirtual(left) && IsVirtual(right)); |
| 1248 | left = ResolveReplacement(left); |
| 1249 | right = ResolveReplacement(right); |
| 1250 | if (IsEquivalentPhi(left, right)) { |
| 1251 | return true; |
| 1252 | } |
| 1253 | return false; |
| 1254 | } |
| 1255 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1256 | int EscapeAnalysis::OffsetFromAccess(Node* node) { |
| 1257 | DCHECK(OpParameter<FieldAccess>(node).offset % kPointerSize == 0); |
| 1258 | return OpParameter<FieldAccess>(node).offset / kPointerSize; |
| 1259 | } |
| 1260 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1261 | void EscapeAnalysis::ProcessLoadFromPhi(int offset, Node* from, Node* load, |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1262 | VirtualState* state) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1263 | TRACE("Load #%d from phi #%d", load->id(), from->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1264 | |
| 1265 | cache_->fields().clear(); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1266 | for (int i = 0; i < load->op()->ValueInputCount(); ++i) { |
| 1267 | Node* input = NodeProperties::GetValueInput(load, i); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1268 | cache_->fields().push_back(input); |
| 1269 | } |
| 1270 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1271 | cache_->LoadVirtualObjectsForFieldsFrom(state, |
| 1272 | status_analysis_.GetAliasMap()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1273 | if (cache_->objects().size() == cache_->fields().size()) { |
| 1274 | cache_->GetFields(offset); |
| 1275 | if (cache_->fields().size() == cache_->objects().size()) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1276 | Node* rep = replacement(load); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1277 | if (!rep || !IsEquivalentPhi(rep, cache_->fields())) { |
| 1278 | int value_input_count = static_cast<int>(cache_->fields().size()); |
| 1279 | cache_->fields().push_back(NodeProperties::GetControlInput(from)); |
| 1280 | Node* phi = graph()->NewNode( |
| 1281 | common()->Phi(MachineRepresentation::kTagged, value_input_count), |
| 1282 | value_input_count + 1, &cache_->fields().front()); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1283 | status_analysis_.ResizeStatusVector(); |
| 1284 | SetReplacement(load, phi); |
| 1285 | TRACE(" got phi created.\n"); |
| 1286 | } else { |
| 1287 | TRACE(" has already phi #%d.\n", rep->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1288 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1289 | } else { |
| 1290 | TRACE(" has incomplete field info.\n"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1291 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1292 | } else { |
| 1293 | TRACE(" has incomplete virtual object info.\n"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1294 | } |
| 1295 | } |
| 1296 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1297 | void EscapeAnalysis::ProcessLoadField(Node* node) { |
| 1298 | DCHECK_EQ(node->opcode(), IrOpcode::kLoadField); |
| 1299 | ForwardVirtualState(node); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1300 | Node* from = ResolveReplacement(NodeProperties::GetValueInput(node, 0)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1301 | VirtualState* state = virtual_states_[node->id()]; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1302 | if (VirtualObject* object = GetVirtualObject(state, from)) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1303 | int offset = OffsetFromAccess(node); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1304 | if (!object->IsTracked() || |
| 1305 | static_cast<size_t>(offset) >= object->field_count()) { |
| 1306 | return; |
| 1307 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1308 | Node* value = object->GetField(offset); |
| 1309 | if (value) { |
| 1310 | value = ResolveReplacement(value); |
| 1311 | } |
| 1312 | // Record that the load has this alias. |
| 1313 | UpdateReplacement(state, node, value); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1314 | } else if (from->opcode() == IrOpcode::kPhi && |
| 1315 | OpParameter<FieldAccess>(node).offset % kPointerSize == 0) { |
| 1316 | int offset = OffsetFromAccess(node); |
| 1317 | // Only binary phis are supported for now. |
| 1318 | ProcessLoadFromPhi(offset, from, node, state); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1319 | } else { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1320 | UpdateReplacement(state, node, nullptr); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1321 | } |
| 1322 | } |
| 1323 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1324 | void EscapeAnalysis::ProcessLoadElement(Node* node) { |
| 1325 | DCHECK_EQ(node->opcode(), IrOpcode::kLoadElement); |
| 1326 | ForwardVirtualState(node); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1327 | Node* from = ResolveReplacement(NodeProperties::GetValueInput(node, 0)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1328 | VirtualState* state = virtual_states_[node->id()]; |
| 1329 | Node* index_node = node->InputAt(1); |
| 1330 | NumberMatcher index(index_node); |
| 1331 | DCHECK(index_node->opcode() != IrOpcode::kInt32Constant && |
| 1332 | index_node->opcode() != IrOpcode::kInt64Constant && |
| 1333 | index_node->opcode() != IrOpcode::kFloat32Constant && |
| 1334 | index_node->opcode() != IrOpcode::kFloat64Constant); |
| 1335 | ElementAccess access = OpParameter<ElementAccess>(node); |
| 1336 | if (index.HasValue()) { |
| 1337 | int offset = index.Value() + access.header_size / kPointerSize; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1338 | if (VirtualObject* object = GetVirtualObject(state, from)) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1339 | CHECK_GE(ElementSizeLog2Of(access.machine_type.representation()), |
| 1340 | kPointerSizeLog2); |
| 1341 | CHECK_EQ(access.header_size % kPointerSize, 0); |
| 1342 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1343 | if (!object->IsTracked() || |
| 1344 | static_cast<size_t>(offset) >= object->field_count()) { |
| 1345 | return; |
| 1346 | } |
| 1347 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1348 | Node* value = object->GetField(offset); |
| 1349 | if (value) { |
| 1350 | value = ResolveReplacement(value); |
| 1351 | } |
| 1352 | // Record that the load has this alias. |
| 1353 | UpdateReplacement(state, node, value); |
| 1354 | } else if (from->opcode() == IrOpcode::kPhi) { |
| 1355 | ElementAccess access = OpParameter<ElementAccess>(node); |
| 1356 | int offset = index.Value() + access.header_size / kPointerSize; |
| 1357 | ProcessLoadFromPhi(offset, from, node, state); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1358 | } else { |
| 1359 | UpdateReplacement(state, node, nullptr); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1360 | } |
| 1361 | } else { |
| 1362 | // We have a load from a non-const index, cannot eliminate object. |
| 1363 | if (SetEscaped(from)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1364 | TRACE( |
| 1365 | "Setting #%d (%s) to escaped because load element #%d from non-const " |
| 1366 | "index #%d (%s)\n", |
| 1367 | from->id(), from->op()->mnemonic(), node->id(), index_node->id(), |
| 1368 | index_node->op()->mnemonic()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1369 | } |
| 1370 | } |
| 1371 | } |
| 1372 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1373 | void EscapeAnalysis::ProcessStoreField(Node* node) { |
| 1374 | DCHECK_EQ(node->opcode(), IrOpcode::kStoreField); |
| 1375 | ForwardVirtualState(node); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1376 | Node* to = ResolveReplacement(NodeProperties::GetValueInput(node, 0)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1377 | VirtualState* state = virtual_states_[node->id()]; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1378 | VirtualObject* obj = GetVirtualObject(state, to); |
| 1379 | int offset = OffsetFromAccess(node); |
| 1380 | if (obj && obj->IsTracked() && |
| 1381 | static_cast<size_t>(offset) < obj->field_count()) { |
| 1382 | Node* val = ResolveReplacement(NodeProperties::GetValueInput(node, 1)); |
| 1383 | if (obj->GetField(offset) != val) { |
| 1384 | obj = CopyForModificationAt(obj, state, node); |
| 1385 | obj->SetField(offset, val); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1386 | } |
| 1387 | } |
| 1388 | } |
| 1389 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1390 | void EscapeAnalysis::ProcessStoreElement(Node* node) { |
| 1391 | DCHECK_EQ(node->opcode(), IrOpcode::kStoreElement); |
| 1392 | ForwardVirtualState(node); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1393 | Node* to = ResolveReplacement(NodeProperties::GetValueInput(node, 0)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1394 | Node* index_node = node->InputAt(1); |
| 1395 | NumberMatcher index(index_node); |
| 1396 | DCHECK(index_node->opcode() != IrOpcode::kInt32Constant && |
| 1397 | index_node->opcode() != IrOpcode::kInt64Constant && |
| 1398 | index_node->opcode() != IrOpcode::kFloat32Constant && |
| 1399 | index_node->opcode() != IrOpcode::kFloat64Constant); |
| 1400 | ElementAccess access = OpParameter<ElementAccess>(node); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1401 | VirtualState* state = virtual_states_[node->id()]; |
| 1402 | VirtualObject* obj = GetVirtualObject(state, to); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1403 | if (index.HasValue()) { |
| 1404 | int offset = index.Value() + access.header_size / kPointerSize; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1405 | if (obj && obj->IsTracked() && |
| 1406 | static_cast<size_t>(offset) < obj->field_count()) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1407 | CHECK_GE(ElementSizeLog2Of(access.machine_type.representation()), |
| 1408 | kPointerSizeLog2); |
| 1409 | CHECK_EQ(access.header_size % kPointerSize, 0); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1410 | Node* val = ResolveReplacement(NodeProperties::GetValueInput(node, 2)); |
| 1411 | if (obj->GetField(offset) != val) { |
| 1412 | obj = CopyForModificationAt(obj, state, node); |
| 1413 | obj->SetField(offset, val); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1414 | } |
| 1415 | } |
| 1416 | } else { |
| 1417 | // We have a store to a non-const index, cannot eliminate object. |
| 1418 | if (SetEscaped(to)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1419 | TRACE( |
| 1420 | "Setting #%d (%s) to escaped because store element #%d to non-const " |
| 1421 | "index #%d (%s)\n", |
| 1422 | to->id(), to->op()->mnemonic(), node->id(), index_node->id(), |
| 1423 | index_node->op()->mnemonic()); |
| 1424 | } |
| 1425 | if (obj && obj->IsTracked()) { |
| 1426 | if (!obj->AllFieldsClear()) { |
| 1427 | obj = CopyForModificationAt(obj, state, node); |
| 1428 | obj->ClearAllFields(); |
| 1429 | TRACE("Cleared all fields of @%d:#%d\n", GetAlias(obj->id()), |
| 1430 | obj->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1431 | } |
| 1432 | } |
| 1433 | } |
| 1434 | } |
| 1435 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1436 | Node* EscapeAnalysis::GetOrCreateObjectState(Node* effect, Node* node) { |
| 1437 | if ((node->opcode() == IrOpcode::kFinishRegion || |
| 1438 | node->opcode() == IrOpcode::kAllocate) && |
| 1439 | IsVirtual(node)) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1440 | if (VirtualObject* vobj = GetVirtualObject(virtual_states_[effect->id()], |
| 1441 | ResolveReplacement(node))) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1442 | if (Node* object_state = vobj->GetObjectState()) { |
| 1443 | return object_state; |
| 1444 | } else { |
| 1445 | cache_->fields().clear(); |
| 1446 | for (size_t i = 0; i < vobj->field_count(); ++i) { |
| 1447 | if (Node* field = vobj->GetField(i)) { |
| 1448 | cache_->fields().push_back(field); |
| 1449 | } |
| 1450 | } |
| 1451 | int input_count = static_cast<int>(cache_->fields().size()); |
| 1452 | Node* new_object_state = |
| 1453 | graph()->NewNode(common()->ObjectState(input_count, vobj->id()), |
| 1454 | input_count, &cache_->fields().front()); |
| 1455 | vobj->SetObjectState(new_object_state); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1456 | TRACE( |
| 1457 | "Creating object state #%d for vobj %p (from node #%d) at effect " |
| 1458 | "#%d\n", |
| 1459 | new_object_state->id(), static_cast<void*>(vobj), node->id(), |
| 1460 | effect->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1461 | // Now fix uses of other objects. |
| 1462 | for (size_t i = 0; i < vobj->field_count(); ++i) { |
| 1463 | if (Node* field = vobj->GetField(i)) { |
| 1464 | if (Node* field_object_state = |
| 1465 | GetOrCreateObjectState(effect, field)) { |
| 1466 | NodeProperties::ReplaceValueInput( |
| 1467 | new_object_state, field_object_state, static_cast<int>(i)); |
| 1468 | } |
| 1469 | } |
| 1470 | } |
| 1471 | return new_object_state; |
| 1472 | } |
| 1473 | } |
| 1474 | } |
| 1475 | return nullptr; |
| 1476 | } |
| 1477 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1478 | void EscapeAnalysis::DebugPrintObject(VirtualObject* object, Alias alias) { |
| 1479 | PrintF(" Alias @%d: Object #%d with %zu fields\n", alias, object->id(), |
| 1480 | object->field_count()); |
| 1481 | for (size_t i = 0; i < object->field_count(); ++i) { |
| 1482 | if (Node* f = object->GetField(i)) { |
| 1483 | PrintF(" Field %zu = #%d (%s)\n", i, f->id(), f->op()->mnemonic()); |
| 1484 | } |
| 1485 | } |
| 1486 | } |
| 1487 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1488 | void EscapeAnalysis::DebugPrintState(VirtualState* state) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1489 | PrintF("Dumping virtual state %p\n", static_cast<void*>(state)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1490 | for (Alias alias = 0; alias < AliasCount(); ++alias) { |
| 1491 | if (VirtualObject* object = state->VirtualObjectFromAlias(alias)) { |
| 1492 | DebugPrintObject(object, alias); |
| 1493 | } |
| 1494 | } |
| 1495 | } |
| 1496 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1497 | void EscapeAnalysis::DebugPrint() { |
| 1498 | ZoneVector<VirtualState*> object_states(zone()); |
| 1499 | for (NodeId id = 0; id < virtual_states_.size(); id++) { |
| 1500 | if (VirtualState* states = virtual_states_[id]) { |
| 1501 | if (std::find(object_states.begin(), object_states.end(), states) == |
| 1502 | object_states.end()) { |
| 1503 | object_states.push_back(states); |
| 1504 | } |
| 1505 | } |
| 1506 | } |
| 1507 | for (size_t n = 0; n < object_states.size(); n++) { |
| 1508 | DebugPrintState(object_states[n]); |
| 1509 | } |
| 1510 | } |
| 1511 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1512 | VirtualObject* EscapeAnalysis::GetVirtualObject(VirtualState* state, |
| 1513 | Node* node) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1514 | if (node->id() >= status_analysis_.GetAliasMap().size()) return nullptr; |
| 1515 | Alias alias = GetAlias(node->id()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1516 | if (alias >= state->size()) return nullptr; |
| 1517 | return state->VirtualObjectFromAlias(alias); |
| 1518 | } |
| 1519 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 1520 | bool EscapeAnalysis::ExistsVirtualAllocate() { |
| 1521 | for (size_t id = 0; id < status_analysis_.GetAliasMap().size(); ++id) { |
| 1522 | Alias alias = GetAlias(static_cast<NodeId>(id)); |
| 1523 | if (alias < EscapeStatusAnalysis::kUntrackable) { |
| 1524 | if (status_analysis_.IsVirtual(static_cast<int>(id))) { |
| 1525 | return true; |
| 1526 | } |
| 1527 | } |
| 1528 | } |
| 1529 | return false; |
| 1530 | } |
| 1531 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1532 | } // namespace compiler |
| 1533 | } // namespace internal |
| 1534 | } // namespace v8 |