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