[BranchProbabilityInfo] Use SmallVector (NFC)
authorKazu Hirata <kazu@google.com>
Tue, 10 Nov 2020 01:29:40 +0000 (17:29 -0800)
committerKazu Hirata <kazu@google.com>
Tue, 10 Nov 2020 01:29:40 +0000 (17:29 -0800)
commit2f1038c7b699e959e0521638e2e2818a849fe19c
tree6c125e5e5848932d6f59a608e3f7072756a3323e
parentc2cb093d9b968f50ded99680a841d46120a114ef
[BranchProbabilityInfo] Use SmallVector (NFC)

This patch simplifies BranchProbabilityInfo by changing the type of
Probs.

Without this patch:

  DenseMap<Edge, BranchProbability> Probs

maps an ordered pair of a BasicBlock* and a successor index to an edge
probability.

With this patch:

  DenseMap<const BasicBlock *, SmallVector<BranchProbability, 2>> Probs

maps a BasicBlock* to a vector of edge probabilities.

BranchProbabilityInfo has a property that for a given basic block, we
either have edge probabilities for all successors or do not have any
edge probability at all.  This property combined with the current map
type leads to a somewhat complicated algorithm in eraseBlock to erase
map entries one by one while increasing the successor index.

The new map type allows us to remove the all edge probabilities for a
given basic block in a more intuitive manner, namely:

  Probs.erase(BB);

Differential Revision: https://reviews.llvm.org/D91017
llvm/include/llvm/Analysis/BranchProbabilityInfo.h
llvm/lib/Analysis/BranchProbabilityInfo.cpp