[JumpThreading] Simplify FindMostPopularDest (NFC)

[kazu]

Summary

This patch simplifies FindMostPopularDest without changing the
functionality.

Given a list of jump threading destinations, the function finds the
most popular destination. To ensure determinism when there are
multiple destinations with the highest popularity, the function picks
the first one in the successor list with the highest popularity.

Without this patch:

• The function populates DestPopularity -- a histogram mapping destinations to their respective occurrence counts.

• Then we iterate over DestPopularity, looking for the highest popularity while building a vector of destinations with the highest popularity.

• Finally, we iterate the successor list, looking for the destination with the highest popularity.

With this patch:

• We implement DestPopularity with MapVector instead of DenseMap. We populate the map with popularity 0 for all successors in the order they appear in the successor list.

• We build the histogram in the same way as before.

• We simply use std::max_element on DestPopularity to find the most popular destination. The use of MapVector ensures determinism.

[wmi]

LGTM.

[efriedma]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1490

Initializing DestPopularity like this should be unnecessary, I think; as long as the ordering of PredToDestList is deterministic, the ordering of the resulting MapVector should also be deterministic.

Can we just assert !DestPopularity.empty(), instead of messing with nullptr? If PredToDestList is non-empty, DestPopularity should also be non-empty.over inserting nullptr; inserting nullptr simplifies the control flow, but it's not intuitive.

[kazu]

Thank you two for reviews!

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1490

I am afraid that assuming a certain order in PredToDestList might make the interface a bit fragile because FindMostPopularDest doesn't have control over how PredToDestList is populated.

I agree that the nullptr trick is not very intuitive. However, we cannot assert !DestPopularity.empty() because DestPopularity could be empty when the sole entry in PredToDestList maps undef branch condition to nullptr destination basic block. This situation actually occurs during ninja check-llvm.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 //===- JumpThreading.cpp - Thread control through conditional blocks ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Jump Threading pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/JumpThreading.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
FindMostPopularDest(BasicBlock *BB,
                     const SmallVectorImpl<std::pair<BasicBlock *,
                                           BasicBlock *>> &PredToDestList) {
   assert(!PredToDestList.empty());
 
   // Determine popularity.  If there are multiple possible destinations, we
   // explicitly choose to ignore 'undef' destinations.  We prefer to thread
   // blocks with known and real destinations to threading undef.  We'll handle
   // them later if interesting.
-  DenseMap<BasicBlock*, unsigned> DestPopularity;
+  MapVector<BasicBlock *, unsigned> DestPopularity;
+
+  // Populate DestPopularity with the successors in the order they appear in the
+  // successor list.  This way, we ensure determinism by iterating it in the
+  // same order in std::max_element below.  We map nullptr to 0 so that we can
+  // return nullptr when PredToDestList contains nullptr only.
+  DestPopularity[nullptr] = 0;
+  for (auto *SuccBB : successors(BB))
+    DestPopularity[SuccBB] = 0;
+
   for (const auto &PredToDest : PredToDestList)
     if (PredToDest.second)
       DestPopularity[PredToDest.second]++;
 
-  if (DestPopularity.empty())
-    return nullptr;
-
   // Find the most popular dest.
-  DenseMap<BasicBlock*, unsigned>::iterator DPI = DestPopularity.begin();
-  BasicBlock *MostPopularDest = DPI->first;
-  unsigned Popularity = DPI->second;
-  SmallVector<BasicBlock*, 4> SamePopularity;
-
-  for (++DPI; DPI != DestPopularity.end(); ++DPI) {
-    // If the popularity of this entry isn't higher than the popularity we've
-    // seen so far, ignore it.
-    if (DPI->second < Popularity)
-      ; // ignore.
-    else if (DPI->second == Popularity) {
-      // If it is the same as what we've seen so far, keep track of it.
-      SamePopularity.push_back(DPI->first);
-    } else {
-      // If it is more popular, remember it.
-      SamePopularity.clear();
-      MostPopularDest = DPI->first;
-      Popularity = DPI->second;
-    }
-  }
-
-  // Okay, now we know the most popular destination.  If there is more than one
-  // destination, we need to determine one.  This is arbitrary, but we need
-  // to make a deterministic decision.  Pick the first one that appears in the
-  // successor list.
-  if (!SamePopularity.empty()) {
-    SamePopularity.push_back(MostPopularDest);
-    Instruction *TI = BB->getTerminator();
-    for (unsigned i = 0; ; ++i) {
-      assert(i != TI->getNumSuccessors() && "Didn't find any successor!");
-
-      if (!is_contained(SamePopularity, TI->getSuccessor(i)))
-        continue;
-
-      MostPopularDest = TI->getSuccessor(i);
-      break;
-    }
-  }
+  using VT = decltype(DestPopularity)::value_type;
+  auto MostPopular = std::max_element(
+      DestPopularity.begin(), DestPopularity.end(),
+      [](const VT &L, const VT &R) { return L.second < R.second; });
 
   // Okay, we have finally picked the most popular destination.
-  return MostPopularDest;
+  return MostPopular->first;
 }
 
 // Try to evaluate the value of V when the control flows from PredPredBB to
 // BB->getSinglePredecessor() and then on to BB.
 Constant *JumpThreadingPass::EvaluateOnPredecessorEdge(BasicBlock *BB,
                                                        BasicBlock *PredPredBB,
                                                        Value *V) {
   BasicBlock *PredBB = BB->getSinglePredecessor();