OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/verifier.h" | 5 #include "src/compiler/verifier.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <deque> | 8 #include <deque> |
9 #include <queue> | 9 #include <queue> |
10 #include <sstream> | 10 #include <sstream> |
(...skipping 847 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
858 BasicBlock* use_block = block; | 858 BasicBlock* use_block = block; |
859 if (node->opcode() == IrOpcode::kPhi) { | 859 if (node->opcode() == IrOpcode::kPhi) { |
860 use_block = use_block->PredecessorAt(j); | 860 use_block = use_block->PredecessorAt(j); |
861 use_pos = static_cast<int>(use_block->NodeCount()) - 1; | 861 use_pos = static_cast<int>(use_block->NodeCount()) - 1; |
862 } | 862 } |
863 Node* input = node->InputAt(j); | 863 Node* input = node->InputAt(j); |
864 if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block, | 864 if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block, |
865 use_pos)) { | 865 use_pos)) { |
866 V8_Fatal(__FILE__, __LINE__, | 866 V8_Fatal(__FILE__, __LINE__, |
867 "Node #%d:%s in B%d is not dominated by input@%d #%d:%s", | 867 "Node #%d:%s in B%d is not dominated by input@%d #%d:%s", |
868 node->id(), node->op()->mnemonic(), block->id().ToInt(), j, | 868 node->id(), node->op()->mnemonic(), block->rpo_number(), j, |
869 input->id(), input->op()->mnemonic()); | 869 input->id(), input->op()->mnemonic()); |
870 } | 870 } |
871 } | 871 } |
872 // Ensure that nodes are dominated by their control inputs; | 872 // Ensure that nodes are dominated by their control inputs; |
873 // kEnd is an exception, as unreachable blocks resulting from kMerge | 873 // kEnd is an exception, as unreachable blocks resulting from kMerge |
874 // are not in the RPO. | 874 // are not in the RPO. |
875 if (node->op()->ControlInputCount() == 1 && | 875 if (node->op()->ControlInputCount() == 1 && |
876 node->opcode() != IrOpcode::kEnd) { | 876 node->opcode() != IrOpcode::kEnd) { |
877 Node* ctl = NodeProperties::GetControlInput(node); | 877 Node* ctl = NodeProperties::GetControlInput(node); |
878 if (!Dominates(schedule, ctl, node)) { | 878 if (!Dominates(schedule, ctl, node)) { |
879 V8_Fatal(__FILE__, __LINE__, | 879 V8_Fatal(__FILE__, __LINE__, |
880 "Node #%d:%s in B%d is not dominated by control input #%d:%s", | 880 "Node #%d:%s in B%d is not dominated by control input #%d:%s", |
881 node->id(), node->op()->mnemonic(), block->id(), ctl->id(), | 881 node->id(), node->op()->mnemonic(), block->rpo_number(), |
882 ctl->op()->mnemonic()); | 882 ctl->id(), ctl->op()->mnemonic()); |
883 } | 883 } |
884 } | 884 } |
885 } | 885 } |
886 | 886 |
887 | 887 |
888 void ScheduleVerifier::Run(Schedule* schedule) { | 888 void ScheduleVerifier::Run(Schedule* schedule) { |
889 const size_t count = schedule->BasicBlockCount(); | 889 const size_t count = schedule->BasicBlockCount(); |
890 Zone tmp_zone; | 890 Zone tmp_zone; |
891 Zone* zone = &tmp_zone; | 891 Zone* zone = &tmp_zone; |
892 BasicBlock* start = schedule->start(); | 892 BasicBlock* start = schedule->start(); |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
966 queue.push(start); | 966 queue.push(start); |
967 dominators[start->id().ToSize()] = | 967 dominators[start->id().ToSize()] = |
968 new (zone) BitVector(static_cast<int>(count), zone); | 968 new (zone) BitVector(static_cast<int>(count), zone); |
969 while (!queue.empty()) { | 969 while (!queue.empty()) { |
970 BasicBlock* block = queue.front(); | 970 BasicBlock* block = queue.front(); |
971 queue.pop(); | 971 queue.pop(); |
972 BitVector* block_doms = dominators[block->id().ToSize()]; | 972 BitVector* block_doms = dominators[block->id().ToSize()]; |
973 BasicBlock* idom = block->dominator(); | 973 BasicBlock* idom = block->dominator(); |
974 if (idom != NULL && !block_doms->Contains(idom->id().ToInt())) { | 974 if (idom != NULL && !block_doms->Contains(idom->id().ToInt())) { |
975 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", | 975 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", |
976 block->id().ToInt(), idom->id().ToInt()); | 976 block->rpo_number(), idom->rpo_number()); |
977 } | 977 } |
978 for (size_t s = 0; s < block->SuccessorCount(); s++) { | 978 for (size_t s = 0; s < block->SuccessorCount(); s++) { |
979 BasicBlock* succ = block->SuccessorAt(s); | 979 BasicBlock* succ = block->SuccessorAt(s); |
980 BitVector* succ_doms = dominators[succ->id().ToSize()]; | 980 BitVector* succ_doms = dominators[succ->id().ToSize()]; |
981 | 981 |
982 if (succ_doms == NULL) { | 982 if (succ_doms == NULL) { |
983 // First time visiting the node. S.doms = B U B.doms | 983 // First time visiting the node. S.doms = B U B.doms |
984 succ_doms = new (zone) BitVector(static_cast<int>(count), zone); | 984 succ_doms = new (zone) BitVector(static_cast<int>(count), zone); |
985 succ_doms->CopyFrom(*block_doms); | 985 succ_doms->CopyFrom(*block_doms); |
986 succ_doms->Add(block->id().ToInt()); | 986 succ_doms->Add(block->id().ToInt()); |
(...skipping 17 matching lines...) Expand all Loading... |
1004 if (idom == NULL) continue; | 1004 if (idom == NULL) continue; |
1005 BitVector* block_doms = dominators[block->id().ToSize()]; | 1005 BitVector* block_doms = dominators[block->id().ToSize()]; |
1006 | 1006 |
1007 for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) { | 1007 for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) { |
1008 BasicBlock* dom = | 1008 BasicBlock* dom = |
1009 schedule->GetBlockById(BasicBlock::Id::FromInt(it.Current())); | 1009 schedule->GetBlockById(BasicBlock::Id::FromInt(it.Current())); |
1010 if (dom != idom && | 1010 if (dom != idom && |
1011 !dominators[idom->id().ToSize()]->Contains(dom->id().ToInt())) { | 1011 !dominators[idom->id().ToSize()]->Contains(dom->id().ToInt())) { |
1012 V8_Fatal(__FILE__, __LINE__, | 1012 V8_Fatal(__FILE__, __LINE__, |
1013 "Block B%d is not immediately dominated by B%d", | 1013 "Block B%d is not immediately dominated by B%d", |
1014 block->id().ToInt(), idom->id().ToInt()); | 1014 block->rpo_number(), idom->rpo_number()); |
1015 } | 1015 } |
1016 } | 1016 } |
1017 } | 1017 } |
1018 } | 1018 } |
1019 | 1019 |
1020 // Verify phis are placed in the block of their control input. | 1020 // Verify phis are placed in the block of their control input. |
1021 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); | 1021 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); |
1022 ++b) { | 1022 ++b) { |
1023 for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) { | 1023 for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) { |
1024 Node* phi = *i; | 1024 Node* phi = *i; |
(...skipping 24 matching lines...) Expand all Loading... |
1049 // Check inputs for all nodes in the block. | 1049 // Check inputs for all nodes in the block. |
1050 for (size_t i = 0; i < block->NodeCount(); i++) { | 1050 for (size_t i = 0; i < block->NodeCount(); i++) { |
1051 Node* node = block->NodeAt(i); | 1051 Node* node = block->NodeAt(i); |
1052 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); | 1052 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); |
1053 } | 1053 } |
1054 } | 1054 } |
1055 } | 1055 } |
1056 } | 1056 } |
1057 } | 1057 } |
1058 } // namespace v8::internal::compiler | 1058 } // namespace v8::internal::compiler |
OLD | NEW |