Revert a change in propagateMassToSuccessors that summed redundant edges n^2 times

[AndrewScheidecker]

Summary

This reverts part of r300656, which caused a regression in propagateMassToSuccessors by counting edges n^2 times, where n is the number of edges from the source basic block to the same successor basic block. The result was both incorrect and very slow to compute for large values of n (e.g. switches with multiple cases that go to the same basic block).

[AndrewScheidecker]

Include full context in diff, as suggested on IRC

[dexonsmith]

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1326

If you run clang-format-diff on this I think the loop logic will be clearer. For reference, see the Script for patch reformatting section of:
https://clang.llvm.org/docs/ClangFormat.html#script-for-patch-reformatting

(It will indent SuccE, clarifying that it's a continuation of the statement on the previous line. I suspect it'll line it up with SuccI.)

1330

A comment explaining why we're passing in an iterator here might help to prevent a regression.

But I wonder if you even need this change: can't getEdgeProbability() call BlockT::getIterator on the reference? I believe both BasicBlock and MachineBasicBlock have that function. In that case, you should leave this function as is and clean up getEdgeProbability().

[AndrewScheidecker]

Ran the patch through clang-format

[AndrewScheidecker]

I ran the patch through clang-format. But looking at the code again, I see that calling the getEdgeProbability overload with a successor index or iterator instead of the destination basic block actually does something different from the original code: passing a successor index/iterator gets the probability for a single edge, while passing a basic block sums the probability for all edges between the two blocks.

However, and I have to admit that I'm in over my head here, what the original code was doing doesn't seem correct. For each edge from A to B, it was summing the probability of all edges from A to B, then adding the sum to the mass for B. If there are N edges from A to B, and they have probabilities that sum to M, then this will distribute N*M mass to B instead of M. In my contrived case, N=196928.

I still think this change is good, but I didn't mean for it to change the results. What are your thoughts?

[dexonsmith]

In D40891#947361, @AndrewScheidecker wrote:

I ran the patch through clang-format. But looking at the code again, I see that calling the getEdgeProbability overload with a successor index or iterator instead of the destination basic block actually does something different from the original code: passing a successor index/iterator gets the probability for a single edge, while passing a basic block sums the probability for all edges between the two blocks.

However, and I have to admit that I'm in over my head here, what the original code was doing doesn't seem correct. For each edge from A to B, it was summing the probability of all edges from A to B, then adding the sum to the mass for B. If there are N edges from A to B, and they have probabilities that sum to M, then this will distribute N*M mass to B instead of M. In my contrived case, N=196928.

I still think this change is good, but I didn't mean for it to change the results. What are your thoughts?

You're right, the current logic is wrong. Looking at the history, it looks like it was broken by r300656, which was reviewed in https://reviews.llvm.org/D32118. You're effectively doing a partial-revert of that commit -- please be clear about that in the commit message.

Also, please add a test for this. See the current tests in test/Analysis/BlockFrequencyInfo/ for examples.

As a side note, it's somewhat subtle for the edge-iterator and block-reference versions of getEdgeProbability to give different answers. I think the latter should change names, perhaps to getEdgeProbabilitySum. But that should be in a follow-up patch.

[AndrewScheidecker]

Added a test that produces different results with and without this fix

[dexonsmith]

LGTM, after you try to shrink the testcase. Thanks for tracking this down!

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1318–1324

The old code had SI and SE, which are the typical initialisms. But if you prefer spelling out SuccI that's fine with me.

test/Analysis/BlockFrequencyInfo/redundant_edges.ll

16–25

Do you really need a 8-way switch to see a difference here, or would a 4-way suffice? a 3-way?

[AndrewScheidecker]

Simplified test, and changed iterator variable names to SI/SE.

[AndrewScheidecker]

I don't have commit access; can somebody please commit this?

[dexonsmith]

Committed in r320208.

include/llvm/Analysis/BlockFrequencyInfoImpl.h

BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
   Distribution Dist;
   if (auto *Loop = Working[Node.Index].getPackagedLoop()) {
     assert(Loop != OuterLoop && "Cannot propagate mass in a packaged loop");
     if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist))
       // Irreducible backedge.
       return false;
   } else {
     const BlockT *BB = getBlock(Node);
-    for (const auto Succ : children<const BlockT *>(BB))
-      if (!addToDist(Dist, OuterLoop, Node, getNode(Succ),
-                     getWeightFromBranchProb(BPI->getEdgeProbability(BB, Succ))))
+    for (auto SI = GraphTraits<const BlockT *>::child_begin(BB),
+              SE = GraphTraits<const BlockT *>::child_end(BB);
+         SI != SE; ++SI)
+      if (!addToDist(
+              Dist, OuterLoop, Node, getNode(*SI),
+              getWeightFromBranchProb(BPI->getEdgeProbability(BB, SI))))
         // Irreducible backedge.
         return false;
   }
 
   // Distribute mass to successors, saving exit and backedge data in the
   // loop header.
   distributeMass(Node, OuterLoop, Dist);
   return true;
 }
 
 template <class BT>
 raw_ostream &BlockFrequencyInfoImpl<BT>::print(raw_ostream &OS) const {
   if (!F)
     return OS;
   OS << "block-frequency-info: " << F->getName() << "\n";

test/Analysis/BlockFrequencyInfo/redundant_edges.ll

+; RUN: opt < %s -analyze -block-freq | FileCheck %s
+; RUN: opt < %s -analyze -lazy-block-freq | FileCheck %s
+; RUN: opt < %s -passes='print<block-freq>' -disable-output 2>&1 | FileCheck %s
+
+define void @test1() {
+; CHECK-LABEL: Printing analysis {{.*}} for function 'test1':
+; CHECK-NEXT: block-frequency-info: test1
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  br label %loop
+
+; CHECK-NEXT: loop: float = 32.0
+loop:
+  switch i32 undef, label %loop [
+    i32 0, label %return
+    i32 1, label %return
+  ]
+
+; CHECK-NEXT: return: float = 1.0
+return:
+  ret void
+}