message: Improve performance of InstructionFusion::ComputeGloballyUnfusible
  Swap the loop iterating over the producer and consumer pairs because
  all early exit is based on the producer so it makes more sense to
  iterate that in the outher loop.
diff: @@ -250,12 +250,8 @@ InstructionFusion::ComputeGloballyUnfusible(
  HloInstructionSet do_not_duplicate;
  absl::flat_hash_map<std::pair<HloInstruction*, HloInstruction*>, bool>
  can_fuse_on_all_paths_result_cache;
  - for (HloInstruction* consumer : post_order) {
  - for (HloInstruction* producer : consumer->operands()) {
  - if (do_not_duplicate.count(producer) > 0) {
  - continue;
  - }
  -
  + for (auto it = post_order.rbegin(); it != post_order.rend(); ++it) {
  + HloInstruction* producer = *it;
  // If the producer is effectively not more than unary, duplicating it
  // will not increase the number of relevant inputs read, as the fusion
  // node will only need to read at most 1 relevant input (the input of
  @@ -272,8 +268,7 @@ InstructionFusion::ComputeGloballyUnfusible(
  auto total_size = [](const Shape& shape) {
  int64 size = 0;
  ShapeUtil::ForEachSubshape(
  - shape,
  - [&size](const Shape& subshape, const ShapeIndex& shape_index) {
  + shape, [&size](const Shape& subshape, const ShapeIndex& shape_index) {
  if (subshape.IsArray()) {
  size += ShapeUtil::ElementsIn(subshape);
  }
  @@ -305,13 +300,14 @@ InstructionFusion::ComputeGloballyUnfusible(
  // A will be not allowed to be fused into B, as it cannot be fused via
  // all paths.
  if (producer->IsFusible() &&
  - CanFuseOnAllPaths(producer, consumer, do_not_duplicate,
  - &can_fuse_on_all_paths_result_cache)) {
  + absl::c_all_of(producer->users(), [&](HloInstruction* consumer) {
  + return CanFuseOnAllPaths(producer, consumer, do_not_duplicate,
  + &can_fuse_on_all_paths_result_cache);
  + })) {
  continue;
  }
  do_not_duplicate.insert(producer);
  }
  - }
  return do_not_duplicate;
  }
  @@ -409,11 +405,9 @@ class ReversePostOrderFusionQueue : public FusionQueue {
  }
  sorted_operand_numbers.push_back(i);
  }
  - absl::c_sort(
  - sorted_operand_numbers, [&](int64 i, int64 j) {
  + absl::c_sort(sorted_operand_numbers, [&](int64 i, int64 j) {
  // Instructions with higher priority in the queue come first.
  - return (
  - FindOrDie(post_order_index_, instruction->mutable_operand(i)) >
  + return (FindOrDie(post_order_index_, instruction->mutable_operand(i)) >
  FindOrDie(post_order_index_, instruction->mutable_operand(j)));
  });
  return std::make_pair(instruction, sorted_operand_numbers);
  