Method PartitionSubscripts

source/opt/loop_dependence.cpp:1116–1182

using PartitionedSubscripts =
    std::vector<std::set<std::pair<Instruction*, Instruction*>>>;
PartitionedSubscripts LoopDependenceAnalysis::PartitionSubscripts(
    const std::vector<Instruction*>& source_subscripts,
    const std::vector<Instruction*>& destination_subscripts) {
  PartitionedSubscripts partitions{};

  auto num_subscripts = source_subscripts.size();

  // Create initial partitions with one subscript pair per partition.
  for (size_t i = 0; i < num_subscripts; ++i) {
    partitions.push_back({{source_subscripts[i], destination_subscripts[i]}});
  }

  // Iterate over the loops to create all partitions
  for (auto loop : loops_) {
    int64_t k = -1;

    for (size_t j = 0; j < partitions.size(); ++j) {
      auto& current_partition = partitions[j];

      // Does |loop| appear in |current_partition|
      auto it = std::find_if(
          current_partition.begin(), current_partition.end(),
          [loop,
           this](const std::pair<Instruction*, Instruction*>& elem) -> bool {
            auto source_recurrences =
                scalar_evolution_.AnalyzeInstruction(std::get<0>(elem))
                    ->CollectRecurrentNodes();
            auto destination_recurrences =
                scalar_evolution_.AnalyzeInstruction(std::get<1>(elem))
                    ->CollectRecurrentNodes();

            source_recurrences.insert(source_recurrences.end(),
                                      destination_recurrences.begin(),
                                      destination_recurrences.end());

            auto loops_in_pair = CollectLoops(source_recurrences);
            auto end_it = loops_in_pair.end();

            return std::find(loops_in_pair.begin(), end_it, loop) != end_it;
          });

      auto has_loop = it != current_partition.end();

      if (has_loop) {
        if (k == -1) {
          k = j;
        } else {
          // Add |partitions[j]| to |partitions[k]| and discard |partitions[j]|
          partitions[static_cast<size_t>(k)].insert(current_partition.begin(),
                                                    current_partition.end());
          current_partition.clear();
        }
      }
    }
  }

  // Remove empty (discarded) partitions
  partitions.erase(