We populate the nodes along a special topological order where nodes having the same root frame are placed adjacent to each other. This grouping enables processing the graph per root frame at a time and guarantees that when a root frame is being processed, nodes in the downstream frames have not yet been processed. This property is important because we need to process an entire frame to know whet
| 1357 | // nested while, as there is no clean cut for separating them in the topological |
| 1358 | // order. |
| 1359 | Status DeadnessAnalysisImpl::Populate(bool enable_optimistic) { |
| 1360 | std::vector<string> unreachable_nodes; |
| 1361 | // Compute the loop structure of the graph. |
| 1362 | TF_RETURN_IF_ERROR( |
| 1363 | BuildControlFlowInfo(&graph_, &control_flow_info_, &unreachable_nodes)); |
| 1364 | |
| 1365 | // Do some opportunistic error checking: |
| 1366 | if (!unreachable_nodes.empty()) { |
| 1367 | if (unreachable_nodes.size() > 5) { |
| 1368 | unreachable_nodes.erase(unreachable_nodes.begin() + 5, |
| 1369 | unreachable_nodes.end()); |
| 1370 | } |
| 1371 | |
| 1372 | return errors::InvalidArgument( |
| 1373 | "Found unreachable nodes, most likely source and sink nodes not " |
| 1374 | "connected: ", |
| 1375 | absl::StrJoin(unreachable_nodes, ", ")); |
| 1376 | } |
| 1377 | |
| 1378 | std::vector<Node*> topo; |
| 1379 | TF_RETURN_IF_ERROR(GetFrameBasedTopologicalOrder(&topo)); |
| 1380 | |
| 1381 | size_t frame_start = 0; |
| 1382 | while (frame_start < topo.size()) { |
| 1383 | // Batching nodes who have the same root frame. |
| 1384 | absl::string_view cur_frame_name; |
| 1385 | TF_RETURN_IF_ERROR( |
| 1386 | GetRootFrame(topo[frame_start], control_flow_info_, &cur_frame_name)); |
| 1387 | size_t frame_end = frame_start; |
| 1388 | for (size_t i = frame_start + 1; i < topo.size(); ++i) { |
| 1389 | absl::string_view i_frame_name; |
| 1390 | TF_RETURN_IF_ERROR( |
| 1391 | GetRootFrame(topo[i], control_flow_info_, &i_frame_name)); |
| 1392 | if (i_frame_name == cur_frame_name) { |
| 1393 | frame_end = i; |
| 1394 | } else { |
| 1395 | break; |
| 1396 | } |
| 1397 | } |
| 1398 | absl::Span<Node*> sub_topo(topo.data() + frame_start, |
| 1399 | /*length=*/frame_end - frame_start + 1); |
| 1400 | frame_start = frame_end + 1; |
| 1401 | |
| 1402 | // First, try the optimistic mode. |
| 1403 | bool success = false; |
| 1404 | if (enable_optimistic && !cur_frame_name.empty()) { |
| 1405 | TF_RETURN_IF_ERROR( |
| 1406 | PopulateFrame(sub_topo, /*use_optimistic_mode=*/true, &success)); |
| 1407 | } |
| 1408 | if (!success) { |
| 1409 | // The optimistic mode does not converge. Let's fall back to the |
| 1410 | // pessimistic mode. |
| 1411 | TF_RETURN_IF_ERROR( |
| 1412 | PopulateFrame(sub_topo, /*use_optimistic_mode=*/false, nullptr)); |
| 1413 | } |
| 1414 | VLOG(2) << "Done populating frame " << cur_frame_name << " using the " |
| 1415 | << (success ? "optimistic" : "pessimistic") << " mode."; |
| 1416 | } |
no test coverage detected