[JumpThreading] Set edge probabilities when creating basic blocks
authorKazu Hirata <kazu@google.com>
Tue, 27 Oct 2020 23:07:27 +0000 (16:07 -0700)
committerKazu Hirata <kazu@google.com>
Tue, 27 Oct 2020 23:07:27 +0000 (16:07 -0700)
commitc91487769d80487eba1712a7a172a1c8977a9b4f
tree1ad66cb028629a95e656500b4a9b3216eea3740a
parent84129150ce82894e185c084f2eaec05f4c03dd4c
[JumpThreading] Set edge probabilities when creating basic blocks

This patch teaches the jump threading pass to set edge probabilities
whenever the pass creates new basic blocks.

Without this patch, the compiler sometimes produces non-deterministic
results.  The non-determinism comes from the jump threading pass using
stale edge probabilities in BranchProbabilityInfo.  Specifically, when
the jump threading pass creates a new basic block, we don't initialize
its outgoing edge probability.

Edge probabilities are maintained in:

  DenseMap<Edge, BranchProbability> Probs;

in class BranchProbabilityInfo, where Edge is an ordered pair of
BasicBlock * and a successor index declared as:

  using Edge = std::pair<const BasicBlock *, unsigned>;

Probs maps edges to their corresponding probabilities.

Now, we rarely remove entries from this map, so if we happen to
allocate a new basic block at the same address as a previously deleted
basic block with an edge probability assigned, the newly created basic
block appears to have an edge probability, albeit a stale one.

This patch fixes the problem by explicitly setting edge probabilities
whenever the jump threading pass creates new basic blocks.

Differential Revision: https://reviews.llvm.org/D90106
llvm/lib/Transforms/Scalar/JumpThreading.cpp
llvm/test/Transforms/JumpThreading/thread-prob-1.ll [new file with mode: 0644]
llvm/test/Transforms/JumpThreading/thread-prob-2.ll [new file with mode: 0644]
llvm/test/Transforms/JumpThreading/thread-prob-3.ll [new file with mode: 0644]