Update the branch weight metadata in JumpThreading pass.

Currently in JumpThreading pass, the branch weight metadata is not updated after CFG modification. Consider the jump threading on PredBB, BB, and SuccBB. After jump threading, the weight on BB->SuccBB should be adjusted as some of it is contributed by the edge PredBB->BB, which doesn't exist anymore. This patch tries to update the edge weight in metadata on BB->SuccBB by scaling it by 1 - Freq(PredBB->BB) / Freq(BB->SuccBB).

This is the third attempt to submit this patch, while the first two led to failures in some FDO tests. After investigation, it is the edge weight normalization that caused those failures. In this patch the edge weight normalization is fixed so that there is no zero weight in the output and the sum of all weights can fit in 32-bit integer. Several unit tests are added.

Differential revision: http://reviews.llvm.org/D10979

llvm-svn: 250345

1 files changed, 41 insertions, 0 deletions

diff --git a/llvm/unittests/Support/BranchProbabilityTest.cpp b/llvm/unittests/Support/BranchProbabilityTest.cpp
index 87a25091947..37a5c3f0dc8 100644
--- a/llvm/unittests/Support/BranchProbabilityTest.cpp
+++ b/llvm/unittests/Support/BranchProbabilityTest.cpp
@@ -287,4 +287,45 @@ TEST(BranchProbabilityTest, scaleBruteForce) {
   }
 }
 
+TEST(BranchProbabilityTest, NormalizeEdgeWeights) {
+  {
+    SmallVector<uint32_t, 2> Weights{0, 0};
+    BranchProbability::normalizeEdgeWeights(Weights.begin(), Weights.end());
+    EXPECT_EQ(1u, Weights[0]);
+    EXPECT_EQ(1u, Weights[1]);
+  }
+  {
+    SmallVector<uint32_t, 2> Weights{0, UINT32_MAX};
+    BranchProbability::normalizeEdgeWeights(Weights.begin(), Weights.end());
+    EXPECT_EQ(1u, Weights[0]);
+    EXPECT_EQ(UINT32_MAX - 1u, Weights[1]);
+  }
+  {
+    SmallVector<uint32_t, 2> Weights{1, UINT32_MAX};
+    BranchProbability::normalizeEdgeWeights(Weights.begin(), Weights.end());
+    EXPECT_EQ(1u, Weights[0]);
+    EXPECT_EQ(UINT32_MAX - 1u, Weights[1]);
+  }
+  {
+    SmallVector<uint32_t, 3> Weights{0, 0, UINT32_MAX};
+    BranchProbability::normalizeEdgeWeights(Weights.begin(), Weights.end());
+    EXPECT_EQ(1u, Weights[0]);
+    EXPECT_EQ(1u, Weights[1]);
+    EXPECT_EQ(UINT32_MAX / 2u, Weights[2]);
+  }
+  {
+    SmallVector<uint32_t, 2> Weights{UINT32_MAX, UINT32_MAX};
+    BranchProbability::normalizeEdgeWeights(Weights.begin(), Weights.end());
+    EXPECT_EQ(UINT32_MAX / 3u, Weights[0]);
+    EXPECT_EQ(UINT32_MAX / 3u, Weights[1]);
+  }
+  {
+    SmallVector<uint32_t, 3> Weights{UINT32_MAX, UINT32_MAX, UINT32_MAX};
+    BranchProbability::normalizeEdgeWeights(Weights.begin(), Weights.end());
+    EXPECT_EQ(UINT32_MAX / 4u, Weights[0]);
+    EXPECT_EQ(UINT32_MAX / 4u, Weights[1]);
+    EXPECT_EQ(UINT32_MAX / 4u, Weights[2]);
+  }
+}
+
 }