[JumpThreading] Simplify FindMostPopularDest (NFC)
authorKazu Hirata <kazu@google.com>
Wed, 3 Jun 2020 01:43:09 +0000 (18:43 -0700)
committerKazu Hirata <kazu@google.com>
Wed, 3 Jun 2020 01:43:31 +0000 (18:43 -0700)
commitf355c7fc2f8fb0db829313b8e43f974ed730cf6d
tree5dde99479e21948d1020924138789547dd85f6f1
parent85fdec988fc55d56988d57fa88e2b870f6e0e8e9
[JumpThreading] Simplify FindMostPopularDest (NFC)

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.

Reviewers: wmi, efriedma

Reviewed By: wmi

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D81030
llvm/lib/Transforms/Scalar/JumpThreading.cpp