| 320 | } |
| 321 | |
| 322 | void AssignSplitId(LayerSelectionInfo::LayerInfoContainer& layerInfos, LayerSelectionInfo& layerInfo) |
| 323 | { |
| 324 | // Check each input to see if we can attach ourselves to any of the subgraphs that have already been assigned. |
| 325 | ForEachLayerInput(layerInfos, layerInfo, [&](LayerSelectionInfo& parentInfo) |
| 326 | { |
| 327 | // We can only attach ourselves to the subgraph from this input if there isn't a cut here. |
| 328 | if (layerInfo.m_IsSelected == parentInfo.m_IsSelected) |
| 329 | { |
| 330 | // We also need to check that merging into this subgraph won't cause a dependency cycle between subgraphs. |
| 331 | // This will be the case if the subgraph that we will become part of is already a dependency |
| 332 | // of one of the subgraphs that are input to this layer, e.g: |
| 333 | // |
| 334 | // 0 | The numbers (0, 1) are the subgraph IDs of each layer and we are looking at layer X. |
| 335 | // / \ | |
| 336 | // 1 0 | We can't merge X into subgraph 0, because the left-hand input already depends on subgraph 0. |
| 337 | // \ / | We can however merge X into subgraph 1. |
| 338 | // X | |
| 339 | // |
| 340 | bool dependenciesOk = true; |
| 341 | ForEachLayerInput(layerInfos, layerInfo, [&](LayerSelectionInfo& otherParentInfo) |
| 342 | { |
| 343 | // We call HasAntecedent() ~ n^2 times, where n is the number of inputs to this layer. |
| 344 | // Hence it is important that this is efficient - see PartialSubgraph class description. |
| 345 | if (otherParentInfo.m_Subgraph->HasAntecedent(parentInfo.m_Subgraph.get())) |
| 346 | { |
| 347 | dependenciesOk = false; |
| 348 | } |
| 349 | }); |
| 350 | |
| 351 | if (dependenciesOk) |
| 352 | { |
| 353 | // Merge into the subgraph of this input. If we have already been merged into another subgraph |
| 354 | // (from another input of this layer), then merge both of them together. |
| 355 | if (layerInfo.m_Subgraph == nullptr) |
| 356 | { |
| 357 | layerInfo.m_Subgraph = parentInfo.m_Subgraph; |
| 358 | } |
| 359 | else |
| 360 | { |
| 361 | // We call MergeWith() ~ n times, where n is the number of inputs to this layer. |
| 362 | // Therefore it does not need to be as performant as HasAntecedent(). |
| 363 | layerInfo.m_Subgraph->MergeWith(parentInfo.m_Subgraph.get()); |
| 364 | } |
| 365 | } |
| 366 | } |
| 367 | }); |
| 368 | |
| 369 | // If we weren't able to merge into an existing subgraph then we need to make a new one |
| 370 | if (layerInfo.m_Subgraph == nullptr) |
| 371 | { |
| 372 | layerInfo.m_Subgraph = std::make_shared<PartialSubgraph>(); |
| 373 | } |
| 374 | |
| 375 | // Record dependencies of the chosen subgraph based on the inputs of this layer. |
| 376 | ForEachLayerInput(layerInfos, layerInfo, [&](LayerSelectionInfo& parentInfo) |
| 377 | { |
| 378 | // These functions are called ~n times, where n is the number of inputs to this layer. |
| 379 | // Therefore it does not need to be as performant as HasAntecedent(). |
no test coverage detected