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 961 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
972 static bool HasDominatingDef(Schedule* schedule, Node* node, | 972 static bool HasDominatingDef(Schedule* schedule, Node* node, |
973 BasicBlock* container, BasicBlock* use_block, | 973 BasicBlock* container, BasicBlock* use_block, |
974 int use_pos) { | 974 int use_pos) { |
975 BasicBlock* block = use_block; | 975 BasicBlock* block = use_block; |
976 while (true) { | 976 while (true) { |
977 while (use_pos >= 0) { | 977 while (use_pos >= 0) { |
978 if (block->NodeAt(use_pos) == node) return true; | 978 if (block->NodeAt(use_pos) == node) return true; |
979 use_pos--; | 979 use_pos--; |
980 } | 980 } |
981 block = block->dominator(); | 981 block = block->dominator(); |
982 if (block == NULL) break; | 982 if (block == nullptr) break; |
983 use_pos = static_cast<int>(block->NodeCount()) - 1; | 983 use_pos = static_cast<int>(block->NodeCount()) - 1; |
984 if (node == block->control_input()) return true; | 984 if (node == block->control_input()) return true; |
985 } | 985 } |
986 return false; | 986 return false; |
987 } | 987 } |
988 | 988 |
989 | 989 |
990 static bool Dominates(Schedule* schedule, Node* dominator, Node* dominatee) { | 990 static bool Dominates(Schedule* schedule, Node* dominator, Node* dominatee) { |
991 BasicBlock* dom = schedule->block(dominator); | 991 BasicBlock* dom = schedule->block(dominator); |
992 BasicBlock* sub = schedule->block(dominatee); | 992 BasicBlock* sub = schedule->block(dominatee); |
993 while (sub != NULL) { | 993 while (sub != nullptr) { |
994 if (sub == dom) { | 994 if (sub == dom) { |
995 return true; | 995 return true; |
996 } | 996 } |
997 sub = sub->dominator(); | 997 sub = sub->dominator(); |
998 } | 998 } |
999 return false; | 999 return false; |
1000 } | 1000 } |
1001 | 1001 |
1002 | 1002 |
1003 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block, | 1003 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block, |
(...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1099 } | 1099 } |
1100 } | 1100 } |
1101 // Verify RPO blocks are marked. | 1101 // Verify RPO blocks are marked. |
1102 for (size_t b = 0; b < rpo_order->size(); b++) { | 1102 for (size_t b = 0; b < rpo_order->size(); b++) { |
1103 CHECK(marked[rpo_order->at(b)->id().ToSize()]); | 1103 CHECK(marked[rpo_order->at(b)->id().ToSize()]); |
1104 } | 1104 } |
1105 | 1105 |
1106 { | 1106 { |
1107 // Verify the dominance relation. | 1107 // Verify the dominance relation. |
1108 ZoneVector<BitVector*> dominators(zone); | 1108 ZoneVector<BitVector*> dominators(zone); |
1109 dominators.resize(count, NULL); | 1109 dominators.resize(count, nullptr); |
1110 | 1110 |
1111 // Compute a set of all the nodes that dominate a given node by using | 1111 // Compute a set of all the nodes that dominate a given node by using |
1112 // a forward fixpoint. O(n^2). | 1112 // a forward fixpoint. O(n^2). |
1113 ZoneQueue<BasicBlock*> queue(zone); | 1113 ZoneQueue<BasicBlock*> queue(zone); |
1114 queue.push(start); | 1114 queue.push(start); |
1115 dominators[start->id().ToSize()] = | 1115 dominators[start->id().ToSize()] = |
1116 new (zone) BitVector(static_cast<int>(count), zone); | 1116 new (zone) BitVector(static_cast<int>(count), zone); |
1117 while (!queue.empty()) { | 1117 while (!queue.empty()) { |
1118 BasicBlock* block = queue.front(); | 1118 BasicBlock* block = queue.front(); |
1119 queue.pop(); | 1119 queue.pop(); |
1120 BitVector* block_doms = dominators[block->id().ToSize()]; | 1120 BitVector* block_doms = dominators[block->id().ToSize()]; |
1121 BasicBlock* idom = block->dominator(); | 1121 BasicBlock* idom = block->dominator(); |
1122 if (idom != NULL && !block_doms->Contains(idom->id().ToInt())) { | 1122 if (idom != nullptr && !block_doms->Contains(idom->id().ToInt())) { |
1123 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", | 1123 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", |
1124 block->rpo_number(), idom->rpo_number()); | 1124 block->rpo_number(), idom->rpo_number()); |
1125 } | 1125 } |
1126 for (size_t s = 0; s < block->SuccessorCount(); s++) { | 1126 for (size_t s = 0; s < block->SuccessorCount(); s++) { |
1127 BasicBlock* succ = block->SuccessorAt(s); | 1127 BasicBlock* succ = block->SuccessorAt(s); |
1128 BitVector* succ_doms = dominators[succ->id().ToSize()]; | 1128 BitVector* succ_doms = dominators[succ->id().ToSize()]; |
1129 | 1129 |
1130 if (succ_doms == NULL) { | 1130 if (succ_doms == nullptr) { |
1131 // First time visiting the node. S.doms = B U B.doms | 1131 // First time visiting the node. S.doms = B U B.doms |
1132 succ_doms = new (zone) BitVector(static_cast<int>(count), zone); | 1132 succ_doms = new (zone) BitVector(static_cast<int>(count), zone); |
1133 succ_doms->CopyFrom(*block_doms); | 1133 succ_doms->CopyFrom(*block_doms); |
1134 succ_doms->Add(block->id().ToInt()); | 1134 succ_doms->Add(block->id().ToInt()); |
1135 dominators[succ->id().ToSize()] = succ_doms; | 1135 dominators[succ->id().ToSize()] = succ_doms; |
1136 queue.push(succ); | 1136 queue.push(succ); |
1137 } else { | 1137 } else { |
1138 // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms) | 1138 // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms) |
1139 bool had = succ_doms->Contains(block->id().ToInt()); | 1139 bool had = succ_doms->Contains(block->id().ToInt()); |
1140 if (had) succ_doms->Remove(block->id().ToInt()); | 1140 if (had) succ_doms->Remove(block->id().ToInt()); |
1141 if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ); | 1141 if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ); |
1142 if (had) succ_doms->Add(block->id().ToInt()); | 1142 if (had) succ_doms->Add(block->id().ToInt()); |
1143 } | 1143 } |
1144 } | 1144 } |
1145 } | 1145 } |
1146 | 1146 |
1147 // Verify the immediateness of dominators. | 1147 // Verify the immediateness of dominators. |
1148 for (BasicBlockVector::iterator b = rpo_order->begin(); | 1148 for (BasicBlockVector::iterator b = rpo_order->begin(); |
1149 b != rpo_order->end(); ++b) { | 1149 b != rpo_order->end(); ++b) { |
1150 BasicBlock* block = *b; | 1150 BasicBlock* block = *b; |
1151 BasicBlock* idom = block->dominator(); | 1151 BasicBlock* idom = block->dominator(); |
1152 if (idom == NULL) continue; | 1152 if (idom == nullptr) continue; |
1153 BitVector* block_doms = dominators[block->id().ToSize()]; | 1153 BitVector* block_doms = dominators[block->id().ToSize()]; |
1154 | 1154 |
1155 for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) { | 1155 for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) { |
1156 BasicBlock* dom = | 1156 BasicBlock* dom = |
1157 schedule->GetBlockById(BasicBlock::Id::FromInt(it.Current())); | 1157 schedule->GetBlockById(BasicBlock::Id::FromInt(it.Current())); |
1158 if (dom != idom && | 1158 if (dom != idom && |
1159 !dominators[idom->id().ToSize()]->Contains(dom->id().ToInt())) { | 1159 !dominators[idom->id().ToSize()]->Contains(dom->id().ToInt())) { |
1160 V8_Fatal(__FILE__, __LINE__, | 1160 V8_Fatal(__FILE__, __LINE__, |
1161 "Block B%d is not immediately dominated by B%d", | 1161 "Block B%d is not immediately dominated by B%d", |
1162 block->rpo_number(), idom->rpo_number()); | 1162 block->rpo_number(), idom->rpo_number()); |
(...skipping 19 matching lines...) Expand all Loading... |
1182 } | 1182 } |
1183 } | 1183 } |
1184 | 1184 |
1185 // Verify that all uses are dominated by their definitions. | 1185 // Verify that all uses are dominated by their definitions. |
1186 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); | 1186 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); |
1187 ++b) { | 1187 ++b) { |
1188 BasicBlock* block = *b; | 1188 BasicBlock* block = *b; |
1189 | 1189 |
1190 // Check inputs to control for this block. | 1190 // Check inputs to control for this block. |
1191 Node* control = block->control_input(); | 1191 Node* control = block->control_input(); |
1192 if (control != NULL) { | 1192 if (control != nullptr) { |
1193 CHECK_EQ(block, schedule->block(control)); | 1193 CHECK_EQ(block, schedule->block(control)); |
1194 CheckInputsDominate(schedule, block, control, | 1194 CheckInputsDominate(schedule, block, control, |
1195 static_cast<int>(block->NodeCount()) - 1); | 1195 static_cast<int>(block->NodeCount()) - 1); |
1196 } | 1196 } |
1197 // Check inputs for all nodes in the block. | 1197 // Check inputs for all nodes in the block. |
1198 for (size_t i = 0; i < block->NodeCount(); i++) { | 1198 for (size_t i = 0; i < block->NodeCount(); i++) { |
1199 Node* node = block->NodeAt(i); | 1199 Node* node = block->NodeAt(i); |
1200 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); | 1200 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); |
1201 } | 1201 } |
1202 } | 1202 } |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1259 replacement->op()->EffectOutputCount() > 0); | 1259 replacement->op()->EffectOutputCount() > 0); |
1260 DCHECK(!NodeProperties::IsFrameStateEdge(edge) || | 1260 DCHECK(!NodeProperties::IsFrameStateEdge(edge) || |
1261 replacement->opcode() == IrOpcode::kFrameState); | 1261 replacement->opcode() == IrOpcode::kFrameState); |
1262 } | 1262 } |
1263 | 1263 |
1264 #endif // DEBUG | 1264 #endif // DEBUG |
1265 | 1265 |
1266 } // namespace compiler | 1266 } // namespace compiler |
1267 } // namespace internal | 1267 } // namespace internal |
1268 } // namespace v8 | 1268 } // namespace v8 |
OLD | NEW |