| 104 | } |
| 105 | |
| 106 | xla::StatusOr<bool> CreateCycleDetectionGraph(const Graph* graph, |
| 107 | GraphCycles* cycles) { |
| 108 | for (int i = 0; i < graph->num_node_ids(); ++i) { |
| 109 | // We rely on the node IDs in the cycle detection graph being consecutive |
| 110 | // integers starting from 0. |
| 111 | CHECK_EQ(i, cycles->NewNode()); |
| 112 | } |
| 113 | |
| 114 | // Compute the loop structure of the graph. |
| 115 | std::vector<ControlFlowInfo> control_flow_info; |
| 116 | TF_RETURN_IF_ERROR(BuildControlFlowInfo(graph, &control_flow_info)); |
| 117 | |
| 118 | // The clustering code must avoid adding cycles to the graph to prevent |
| 119 | // deadlock. However, the graph may contain loops, which would trigger the |
| 120 | // cycle detection code. To handle loops, we alter the structure of the cycle |
| 121 | // detection graph, disconnecting each loop from the enclosing graph. |
| 122 | // Specifically, we: |
| 123 | // * add a new "frame" node for each loop. |
| 124 | // * replace edges to "Enter" nodes, and edges from "Exit" nodes with edges |
| 125 | // to/from the corresponding frame node. In essence, we collapse the loop |
| 126 | // into a single node for the purpose of cycle detection in the enclosing |
| 127 | // graph. |
| 128 | // * the body of the loop should now be disconnected from the rest of the |
| 129 | // graph; we make it acyclic by breaking loop backedges (edges outgoing from |
| 130 | // "NextIteration" nodes. |
| 131 | |
| 132 | // Map from frame name strings to node IDs in the cycle detection graph. |
| 133 | std::unordered_map<string, int> frame_nodes; |
| 134 | |
| 135 | // Get the cycle graph node ID for frame 'frame_name', or add one if none |
| 136 | // exists. |
| 137 | auto GetOrAddFrameNodeId = [&frame_nodes, cycles](const string& frame_name) { |
| 138 | int& frame_id = frame_nodes.emplace(frame_name, -1).first->second; |
| 139 | if (frame_id < 0) { |
| 140 | // The emplace succeeded; we have not allocated a frame node yet. |
| 141 | frame_id = cycles->NewNode(); |
| 142 | } |
| 143 | return frame_id; |
| 144 | }; |
| 145 | |
| 146 | for (Edge const* edge : graph->edges()) { |
| 147 | if (edge->dst()->IsEnter() || edge->src()->IsExit()) { |
| 148 | const char* src_type = "pre-enter"; |
| 149 | const char* dst_type = "post-exit"; |
| 150 | int src = edge->src()->id(); |
| 151 | int dst = edge->dst()->id(); |
| 152 | |
| 153 | if (edge->dst()->IsEnter()) { |
| 154 | // Lift edges to an "Enter" node to the corresponding frame node. |
| 155 | const string& frame_name = |
| 156 | control_flow_info[edge->dst()->id()].frame_name; |
| 157 | dst = GetOrAddFrameNodeId(frame_name); |
| 158 | dst_type = "frame"; |
| 159 | } |
| 160 | |
| 161 | if (edge->src()->IsExit()) { |
| 162 | // Lift edges from an "Exit" node to the corresponding frame node. |
| 163 | const string& frame_name = |