Lines Matching refs:node
15 #include "src/compiler/node.h"
16 #include "src/compiler/node-matchers.h"
17 #include "src/compiler/node-properties.h"
47 // A node is dangling, if it is a load of some kind, and does not have
51 // A node is is an effect branch point, if it has more than 2 non-dangling
61 bool IsVirtual(Node* node);
62 bool IsEscaped(Node* node);
63 bool IsAllocation(Node* node);
72 void EnqueueForStatusAnalysis(Node* node);
73 bool SetEscaped(Node* node);
74 bool IsEffectBranchPoint(Node* node);
75 bool IsDanglingEffectNode(Node* node);
88 bool IsNotReachable(Node* node);
91 void Process(Node* node);
92 void ProcessAllocate(Node* node);
93 void ProcessFinishRegion(Node* node);
94 void ProcessStoreField(Node* node);
95 void ProcessStoreElement(Node* node);
96 bool CheckUsesForEscape(Node* node, bool phi_escaping = false) {
97 return CheckUsesForEscape(node, node, phi_escaping);
99 bool CheckUsesForEscape(Node* node, Node* rep, bool phi_escaping = false);
100 void RevisitUses(Node* node);
101 void RevisitInputs(Node* node);
105 bool HasEntry(Node* node);
107 bool IsAllocationPhi(Node* node);
109 ZoneVector<Node*> stack_;
114 ZoneVector<Node*> status_stack_;
165 Node* GetField(size_t offset) { return fields_[offset]; }
169 void SetField(size_t offset, Node* node, bool created_phi = false) {
170 fields_[offset] = node;
178 Node** fields_array() { return &fields_.front(); }
203 bool MergeFrom(MergeCache* cache, Node* at, Graph* graph,
205 void SetObjectState(Node* node) { object_state_ = node; }
206 Node* GetObjectState() const { return object_state_; }
220 bool MergeFields(size_t i, Node* at, MergeCache* cache, Graph* graph,
225 ZoneVector<Node*> fields_;
227 Node* object_state_;
254 VirtualState(Node* owner, Zone* zone, size_t size)
257 VirtualState(Node* owner, const VirtualState& state)
271 CommonOperatorBuilder* common, Node* at);
273 Node* owner() const { return owner_; }
283 Node* owner_;
298 ZoneVector<Node*>& fields() { return fields_; }
307 Node* GetFields(size_t pos);
312 ZoneVector<Node*> fields_;
334 for (Node* field : fields_) {
343 Node* MergeCache::GetFields(size_t pos) {
345 Node* rep = pos >= objects_.front()->field_count()
350 Node* field = obj->GetField(pos);
405 bool IsEquivalentPhi(Node* node1, Node* node2) {
412 Node* input1 = NodeProperties::GetValueInput(node1, i);
413 Node* input2 = NodeProperties::GetValueInput(node2, i);
421 bool IsEquivalentPhi(Node* phi, ZoneVector<Node*>& inputs) {
427 Node* input = NodeProperties::GetValueInput(phi, static_cast<int>(i));
437 bool VirtualObject::MergeFields(size_t i, Node* at, MergeCache* cache,
441 Node* rep = GetField(i);
443 Node* control = NodeProperties::GetControlInput(at);
445 Node* phi = graph->NewNode(
463 Node* old = NodeProperties::GetValueInput(rep, n);
473 bool VirtualObject::MergeFrom(MergeCache* cache, Node* at, Graph* graph,
479 if (Node* field = cache->GetFields(i)) {
502 CommonOperatorBuilder* common, Node* at) {
567 bool EscapeStatusAnalysis::HasEntry(Node* node) {
568 return status_[node->id()] & (kTracked | kEscaped);
571 bool EscapeStatusAnalysis::IsVirtual(Node* node) {
572 return IsVirtual(node->id());
579 bool EscapeStatusAnalysis::IsEscaped(Node* node) {
580 return status_[node->id()] & kEscaped;
583 bool EscapeStatusAnalysis::IsAllocation(Node* node) {
584 return node->opcode() == IrOpcode::kAllocate ||
585 node->opcode() == IrOpcode::kFinishRegion;
588 bool EscapeStatusAnalysis::SetEscaped(Node* node) {
589 bool changed = !(status_[node->id()] & kEscaped);
590 status_[node->id()] |= kEscaped | kTracked;
617 Node* node = status_stack_.back();
619 status_[node->id()] &= ~kOnStack;
620 Process(node);
621 status_[node->id()] |= kVisited;
625 void EscapeStatusAnalysis::EnqueueForStatusAnalysis(Node* node) {
626 DCHECK_NOT_NULL(node);
627 if (!(status_[node->id()] & kOnStack)) {
628 status_stack_.push_back(node);
629 status_[node->id()] |= kOnStack;
633 void EscapeStatusAnalysis::RevisitInputs(Node* node) {
634 for (Edge edge : node->input_edges()) {
635 Node* input = edge.to();
643 void EscapeStatusAnalysis::RevisitUses(Node* node) {
644 for (Edge edge : node->use_edges()) {
645 Node* use = edge.from();
653 void EscapeStatusAnalysis::Process(Node* node) {
654 switch (node->opcode()) {
656 ProcessAllocate(node);
659 ProcessFinishRegion(node);
662 ProcessStoreField(node);
665 ProcessStoreElement(node);
669 if (Node* rep = object_analysis_->GetReplacement(node)) {
670 if (IsAllocation(rep) && CheckUsesForEscape(node, rep)) {
675 RevisitUses(node);
679 if (!HasEntry(node)) {
680 status_[node->id()] |= kTracked;
681 RevisitUses(node);
683 if (!IsAllocationPhi(node) && SetEscaped(node)) {
684 RevisitInputs(node);
685 RevisitUses(node);
687 CheckUsesForEscape(node);
693 bool EscapeStatusAnalysis::IsAllocationPhi(Node* node) {
694 for (Edge edge : node->input_edges()) {
695 Node* input = edge.to();
703 void EscapeStatusAnalysis::ProcessStoreField(Node* node) {
704 DCHECK_EQ(node->opcode(), IrOpcode::kStoreField);
705 Node* to = NodeProperties::GetValueInput(node, 0);
706 Node* val = NodeProperties::GetValueInput(node, 1);
715 void EscapeStatusAnalysis::ProcessStoreElement(Node* node) {
716 DCHECK_EQ(node->opcode(), IrOpcode::kStoreElement);
717 Node* to = NodeProperties::GetValueInput(node, 0);
718 Node* val = NodeProperties::GetValueInput(node, 2);
727 void EscapeStatusAnalysis::ProcessAllocate(Node* node) {
728 DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
729 if (!HasEntry(node)) {
730 status_[node->id()] |= kTracked;
731 TRACE("Created status entry for node #%d (%s)\n", node->id(),
732 node->op()->mnemonic());
733 NumberMatcher size(node->InputAt(0));
734 DCHECK(node->InputAt(0)->opcode() != IrOpcode::kInt32Constant &&
735 node->InputAt(0)->opcode() != IrOpcode::kInt64Constant &&
736 node->InputAt(0)->opcode() != IrOpcode::kFloat32Constant &&
737 node->InputAt(0)->opcode() != IrOpcode::kFloat64Constant);
738 RevisitUses(node);
739 if (!size.HasValue() && SetEscaped(node)) {
740 TRACE("Setting #%d to escaped because of non-const alloc\n", node->id());
741 // This node is already known to escape, uses do not have to be checked
746 if (CheckUsesForEscape(node, true)) {
747 RevisitUses(node);
751 bool EscapeStatusAnalysis::CheckUsesForEscape(Node* uses, Node* rep,
754 Node* use = edge.from();
763 "Setting #%d (%s) to escaped because of use by phi node "
780 "Setting #%d (%s) to escaped because of use by escaping node "
829 void EscapeStatusAnalysis::ProcessFinishRegion(Node* node) {
830 DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
831 if (!HasEntry(node)) {
832 status_[node->id()] |= kTracked;
833 RevisitUses(node);
835 if (CheckUsesForEscape(node, true)) {
836 RevisitInputs(node);
843 PrintF("Node #%d is %s\n", id,
887 Node* node = stack_.back();
889 switch (node->opcode()) {
891 if (aliases_[node->id()] >= kUntrackable) {
892 aliases_[node->id()] = NextAlias();
893 TRACE(" @%d:%s#%u", aliases_[node->id()], node->op()->mnemonic(),
894 node->id());
895 EnqueueForStatusAnalysis(node);
899 Node* allocate = NodeProperties::GetValueInput(node, 0);
911 aliases_[node->id()] = aliases_[allocate->id()];
912 TRACE(" @%d:%s#%u", aliases_[node->id()], node->op()->mnemonic(),
913 node->id());
918 DCHECK_EQ(aliases_[node->id()], kUntrackable);
921 for (Edge edge : node->input_edges()) {
922 Node* input = edge.to();
932 bool EscapeStatusAnalysis::IsNotReachable(Node* node) {
933 if (node->id() >= aliases_.size()) {
936 return aliases_[node->id()] == kNotReachable;
941 ZoneDeque<Node*> queue(zone());
943 ZoneVector<Node*> danglers(zone());
945 Node* node = queue.back();
947 status_analysis_->SetInQueue(node->id(), false);
948 if (Process(node)) {
949 for (Edge edge : node->use_edges()) {
950 Node* use = edge.from();
988 bool EscapeStatusAnalysis::IsDanglingEffectNode(Node* node) {
989 if (status_[node->id()] & kDanglingComputed) {
990 return status_[node->id()] & kDangling;
992 if (node->op()->EffectInputCount() == 0 ||
993 node->op()->EffectOutputCount() == 0 ||
994 (node->op()->EffectInputCount() == 1 &&
995 NodeProperties::GetEffectInput(node)->opcode() == IrOpcode::kStart)) {
996 // The start node is used as sentinel for nodes that are in general
999 status_[node->id()] |= kDanglingComputed;
1002 for (Edge edge : node->use_edges()) {
1003 Node* use = edge.from();
1006 status_[node->id()] |= kDanglingComputed;
1010 status_[node->id()] |= kDanglingComputed | kDangling;
1014 bool EscapeStatusAnalysis::IsEffectBranchPoint(Node* node) {
1015 if (status_[node->id()] & kBranchPointComputed) {
1016 return status_[node->id()] & kBranchPoint;
1019 for (Edge edge : node->use_edges()) {
1020 Node* use = edge.from();
1029 status_[node->id()] |= kBranchPointComputed | kBranchPoint;
1034 status_[node->id()] |= kBranchPointComputed;
1038 bool EscapeAnalysis::Process(Node* node) {
1039 switch (node->opcode()) {
1041 ProcessAllocation(node);
1044 ForwardVirtualState(node);
1047 ProcessFinishRegion(node);
1050 ProcessStoreField(node);
1053 ProcessLoadField(node);
1056 ProcessStoreElement(node);
1059 ProcessLoadElement(node);
1062 ProcessStart(node);
1065 return ProcessEffectPhi(node);
1068 if (node->op()->EffectInputCount() > 0) {
1069 ForwardVirtualState(node);
1071 ProcessAllocationUsers(node);
1077 void EscapeAnalysis::ProcessAllocationUsers(Node* node) {
1078 for (Edge edge : node->input_edges()) {
1079 Node* input = edge.to();
1080 Node* use = edge.from();
1084 switch (node->opcode()) {
1096 VirtualState* state = virtual_states_[node->id()];
1100 obj = CopyForModificationAt(obj, state, node);
1112 Node* node) {
1113 if (state->owner() != node) {
1114 VirtualState* new_state = new (zone()) VirtualState(node, *state);
1115 virtual_states_[node->id()] = new_state;
1116 TRACE("Copying virtual state %p to new state %p at node %s#%d\n",
1118 node->op()->mnemonic(), node->id());
1126 Node* node) {
1128 state = CopyForModificationAt(state, node);
1134 void EscapeAnalysis::ForwardVirtualState(Node* node) {
1135 DCHECK_EQ(node->op()->EffectInputCount(), 1);
1137 if (node->opcode() != IrOpcode::kLoadField &&
1138 node->opcode() != IrOpcode::kLoadElement &&
1139 node->opcode() != IrOpcode::kLoad &&
1140 status_analysis_->IsDanglingEffectNode(node)) {
1141 PrintF("Dangeling effect node: #%d (%s)\n", node->id(),
1142 node->op()->mnemonic());
1146 Node* effect = NodeProperties::GetEffectInput(node);
1148 if (virtual_states_[node->id()]) {
1149 virtual_states_[node->id()]->UpdateFrom(virtual_states_[effect->id()],
1152 virtual_states_[node->id()] = virtual_states_[effect->id()];
1155 effect->op()->mnemonic(), effect->id(), node->op()->mnemonic(),
1156 node->id());
1158 OperatorProperties::GetFrameStateInputCount(node->op()) > 0) {
1159 virtual_states_[node->id()]->SetCopyRequired();
1167 void EscapeAnalysis::ProcessStart(Node* node) {
1168 DCHECK_EQ(node->opcode(), IrOpcode::kStart);
1169 virtual_states_[node->id()] =
1170 new (zone()) VirtualState(node, zone(), status_analysis_->AliasCount());
1173 bool EscapeAnalysis::ProcessEffectPhi(Node* node) {
1174 DCHECK_EQ(node->opcode(), IrOpcode::kEffectPhi);
1177 VirtualState* mergeState = virtual_states_[node->id()];
1180 new (zone()) VirtualState(node, zone(), status_analysis_->AliasCount());
1181 virtual_states_[node->id()] = mergeState;
1183 TRACE("Effect Phi #%d got new virtual state %p.\n", node->id(),
1189 TRACE("At Effect Phi #%d, merging states into %p:", node->id(),
1192 for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
1193 Node* input = NodeProperties::GetEffectInput(node, i);
1199 VirtualState(node, zone(), status_analysis_->AliasCount());
1200 virtual_states_[node->id()] = mergeState;
1214 mergeState->MergeFrom(cache_, zone(), graph(), common(), node) || changed;
1216 TRACE("Merge %s the node.\n", changed ? "changed" : "did not change");
1224 void EscapeAnalysis::ProcessAllocation(Node* node) {
1225 DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
1226 ForwardVirtualState(node);
1227 VirtualState* state = virtual_states_[node->id()];
1228 Alias alias = status_analysis_->GetAlias(node->id());
1230 // Check if we have already processed this node.
1236 state = CopyForModificationAt(state, node);
1239 NumberMatcher size(node->InputAt(0));
1240 DCHECK(node->InputAt(0)->opcode() != IrOpcode::kInt32Constant &&
1241 node->InputAt(0)->opcode() != IrOpcode::kInt64Constant &&
1242 node->InputAt(0)->opcode() != IrOpcode::kFloat32Constant &&
1243 node->InputAt(0)->opcode() != IrOpcode::kFloat64Constant);
1246 node->id(), state, zone(), size.Value() / kPointerSize, false);
1250 alias, new (zone()) VirtualObject(node->id(), state, zone()));
1254 void EscapeAnalysis::ProcessFinishRegion(Node* node) {
1255 DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
1256 ForwardVirtualState(node);
1257 Node* allocation = NodeProperties::GetValueInput(node, 0);
1259 VirtualState* state = virtual_states_[node->id()];
1261 state->VirtualObjectFromAlias(status_analysis_->GetAlias(node->id()));
1267 Node* EscapeAnalysis::replacement(Node* node) {
1268 if (node->id() >= replacements_.size()) return nullptr;
1269 return replacements_[node->id()];
1272 bool EscapeAnalysis::SetReplacement(Node* node, Node* rep) {
1273 bool changed = replacements_[node->id()] != rep;
1274 replacements_[node->id()] = rep;
1278 bool EscapeAnalysis::UpdateReplacement(VirtualState* state, Node* node,
1279 Node* rep) {
1280 if (SetReplacement(node, rep)) {
1282 TRACE("Replacement of #%d is #%d (%s)\n", node->id(), rep->id(),
1285 TRACE("Replacement of #%d cleared\n", node->id());
1292 Node* EscapeAnalysis::ResolveReplacement(Node* node) {
1293 while (replacement(node)) {
1294 node = replacement(node);
1296 return node;
1299 Node* EscapeAnalysis::GetReplacement(Node* node) {
1300 Node* result = nullptr;
1301 while (replacement(node)) {
1302 node = result = replacement(node);
1307 bool EscapeAnalysis::IsVirtual(Node* node) {
1308 if (node->id() >= status_analysis_->GetStatusVectorSize()) {
1311 return status_analysis_->IsVirtual(node);
1314 bool EscapeAnalysis::IsEscaped(Node* node) {
1315 if (node->id() >= status_analysis_->GetStatusVectorSize()) {
1318 return status_analysis_->IsEscaped(node);
1321 bool EscapeAnalysis::CompareVirtualObjects(Node* left, Node* right) {
1333 int OffsetForFieldAccess(Node* node) {
1334 FieldAccess access = FieldAccessOf(node->op());
1339 int OffsetForElementAccess(Node* node, int index) {
1340 ElementAccess access = ElementAccessOf(node->op());
1349 void EscapeAnalysis::ProcessLoadFromPhi(int offset, Node* from, Node* load,
1355 Node* input = NodeProperties::GetValueInput(load, i);
1364 Node* rep = replacement(load);
1368 Node* phi = graph()->NewNode(
1385 void EscapeAnalysis::ProcessLoadField(Node* node) {
1386 DCHECK_EQ(node->opcode(), IrOpcode::kLoadField);
1387 ForwardVirtualState(node);
1388 Node* from = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
1389 VirtualState* state = virtual_states_[node->id()];
1392 int offset = OffsetForFieldAccess(node);
1394 Node* value = object->GetField(offset);
1399 UpdateReplacement(state, node, value);
1401 FieldAccessOf(node->op()).offset % kPointerSize == 0) {
1402 int offset = OffsetForFieldAccess(node);
1404 ProcessLoadFromPhi(offset, from, node, state);
1406 UpdateReplacement(state, node, nullptr);
1410 void EscapeAnalysis::ProcessLoadElement(Node* node) {
1411 DCHECK_EQ(node->opcode(), IrOpcode::kLoadElement);
1412 ForwardVirtualState(node);
1413 Node* from = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
1414 VirtualState* state = virtual_states_[node->id()];
1415 Node* index_node = node->InputAt(1);
1424 int offset = OffsetForElementAccess(node, index.Value());
1426 Node* value = object->GetField(offset);
1431 UpdateReplacement(state, node, value);
1433 int offset = OffsetForElementAccess(node, index.Value());
1434 ProcessLoadFromPhi(offset, from, node, state);
1436 UpdateReplacement(state, node, nullptr);
1444 from->id(), from->op()->mnemonic(), node->id(), index_node->id(),
1450 void EscapeAnalysis::ProcessStoreField(Node* node) {
1451 DCHECK_EQ(node->opcode(), IrOpcode::kStoreField);
1452 ForwardVirtualState(node);
1453 Node* to = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
1454 VirtualState* state = virtual_states_[node->id()];
1457 int offset = OffsetForFieldAccess(node);
1459 Node* val = ResolveReplacement(NodeProperties::GetValueInput(node, 1));
1466 DCHECK_EQ(JSFunction::kCodeEntryOffset, FieldAccessOf(node->op()).offset);
1470 object = CopyForModificationAt(object, state, node);
1476 void EscapeAnalysis::ProcessStoreElement(Node* node) {
1477 DCHECK_EQ(node->opcode(), IrOpcode::kStoreElement);
1478 ForwardVirtualState(node);
1479 Node* to = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
1480 Node* index_node = node->InputAt(1);
1486 VirtualState* state = virtual_states_[node->id()];
1490 int offset = OffsetForElementAccess(node, index.Value());
1492 Node* val = ResolveReplacement(NodeProperties::GetValueInput(node, 2));
1494 object = CopyForModificationAt(object, state, node);
1504 node->id(), index_node->id(),
1510 object = CopyForModificationAt(object, state, node);
1519 Node* EscapeAnalysis::GetOrCreateObjectState(Node* effect, Node* node) {
1520 if ((node->opcode() == IrOpcode::kFinishRegion ||
1521 node->opcode() == IrOpcode::kAllocate) &&
1522 IsVirtual(node)) {
1524 ResolveReplacement(node))) {
1525 if (Node* object_state = vobj->GetObjectState()) {
1530 if (Node* field = vobj->GetField(i)) {
1535 Node* new_object_state =
1540 "Creating object state #%d for vobj %p (from node #%d) at effect "
1542 new_object_state->id(), static_cast<void*>(vobj), node->id(),
1546 if (Node* field = vobj->GetField(i)) {
1547 if (Node* field_object_state =
1568 if (Node* f = object->GetField(i)) {
1592 Node* node) {
1593 if (node->id() >= status_analysis_->GetAliasMap().size()) return nullptr;
1594 Alias alias = status_analysis_->GetAlias(node->id());
