Function SortChains

tensorflow/lite/delegates/gpu/metal/compiled_model.cc:197–242

Accepts unsorted list of chains and returns sorted list with the order of GPU task execution.

// Accepts unsorted list of chains and returns sorted list with the order of GPU
// task execution.
std::list<FusionSequence> SortChains(
    const std::vector<ValueId>& graph_input_ids,
    std::list<FusionSequence>* chains) {
  std::list<FusionSequence> sorted_chains;
  while (!chains->empty()) {
    // Collect ready buffers.
    std::vector<ValueId> ready_buffer_ids;
    ready_buffer_ids.reserve(graph_input_ids.size() + sorted_chains.size());
    ready_buffer_ids.insert(ready_buffer_ids.begin(), graph_input_ids.begin(),
                            graph_input_ids.end());
    for (auto& chain : sorted_chains) {
      ready_buffer_ids.push_back(chain.back()->output_buffer.id);
    }

    for (auto it = chains->begin(); it != chains->end();) {
      const FusionSequence& chain = *it;

      // If the input is also is the output in the same chain - eliminate
      // because it used internally inside this chain only.
      std::vector<ValueId> elements_output_buffer_ids;
      elements_output_buffer_ids.reserve(chain.size());
      for (const ComputeTaskDescriptorPtr& element : chain) {
        elements_output_buffer_ids.push_back(element->output_buffer.id);
      }

      // Collect all inputs also for linked operations.
      std::vector<ValueId> elements_input_buffer_ids;
      for (auto element : chain) {
        for (const auto& buffer : element->input_buffers) {
          if (!Contains(elements_output_buffer_ids, buffer.id)) {
            elements_input_buffer_ids.push_back(buffer.id);
          }
        }
      }

      if (Contains(ready_buffer_ids, elements_input_buffer_ids)) {
        // All input buffers for all elements of this chain are ready.
        sorted_chains.push_back(chain);
        it = chains->erase(it);
      } else {
        ++it;
      }
    }
  }
  return sorted_chains;
}

// If a graph structure contains unused outputs then it can lead to unused
// operations and unused input buffers. It's not an error but some sort of