[Analysis] Qualify auto variables in for loops (NFC)

[llvm] Use value instead of getValue (NFC)

[BPI] Avoid ConstantExpr::get()

Use ConstantFoldBinaryOpOperands() instead, to prepare for the case
where not all binary operators have a constant expression form.

I believe this code actually inte

[BPI] Avoid ConstantExpr::get()

Use ConstantFoldBinaryOpOperands() instead, to prepare for the case
where not all binary operators have a constant expression form.

I believe this code actually intended to set OnlyIfReduced=true,
however ConstantExpr::get() actually accepts a Flags argument at
that position (and OnlyIfReducedTy as the next argument), so this
ended up creating a constant expression with some random flag
(probably exact or nuw depending on which).

show more ...

Revert "Don't use Optional::hasValue (NFC)"

This reverts commit aa8feeefd3ac6c78ee8f67bf033976fc7d68bc6d.

Don't use Optional::hasValue (NFC)

[llvm] Don't use Optional::getValue (NFC)

[llvm] Use value_or instead of getValueOr (NFC)

[NFC] Add missing <map> includes

These were relying on a transitive include.

[BPI] Look-up tables for non-loop branches. NFC.

This adds and uses look-up tables for non-loop branch probabilities, which have
have probabilities directly encoded into the tables for the different

[BPI] Look-up tables for non-loop branches. NFC.

This adds and uses look-up tables for non-loop branch probabilities, which have
have probabilities directly encoded into the tables for the different condition
codes. Compared to having this logic inlined in different functions, as it used
to be the case, I think this is compacter and thus also easier to check/cross
reference. This also adds a test for pointer heuristics that was missing.

Differential Revision: https://reviews.llvm.org/D114009

show more ...

[BPI] Push exit block rather than exiting ones in getSccExitBlocks

The function BranchProbabilityInfo::SccInfo::getSccExitBlocks is
supposed to collect all exit blocks for SCC rather than all exitin

[BPI] Push exit block rather than exiting ones in getSccExitBlocks

The function BranchProbabilityInfo::SccInfo::getSccExitBlocks is
supposed to collect all exit blocks for SCC rather than all exiting
blocks. This patch fixes the typo.

Reviewed By: ebrevnov

Differential Revision: https://reviews.llvm.org/D113344

show more ...

[Analaysis, CodeGen] Remove getHotSucc (NFC)

These functions seem to be unused for at least 5 years.

Fix some -Wunused-but-set-variable in -DLLVM_ENABLE_ASSERTIONS=off build

[Analysis] Use range-based for loops (NFC)

[llvm] Use pop_back_val (NFC)

[BPI] Improve static heuristics for "cold" paths.

Current approach doesn't work well in cases when multiple paths are predicted to be "cold". By "cold" paths I mean those containing "unreachable" in

[BPI] Improve static heuristics for "cold" paths.

Current approach doesn't work well in cases when multiple paths are predicted to be "cold". By "cold" paths I mean those containing "unreachable" instruction, call marked with 'cold' attribute and 'unwind' handler of 'invoke' instruction. The issue is that heuristics are applied one by one until the first match and essentially ignores relative hotness/coldness
of other paths.

New approach unifies processing of "cold" paths by assigning predefined absolute weight to each block estimated to be "cold". Then we propagate these weights up/down IR similarly to existing approach. And finally set up edge probabilities based on estimated block weights.

One important difference is how we propagate weight up. Existing approach propagates the same weight to all blocks that are post-dominated by a block with some "known" weight. This is useless at least because it always gives 50\50 distribution which is assumed by default anyway. Worse, it causes the algorithm to skip further heuristics and can miss setting more accurate probability. New algorithm propagates the weight up only to the blocks that dominates and post-dominated by a block with some "known" weight. In other words, those blocks that are either always executed or not executed together.

In addition new approach processes loops in an uniform way as well. Essentially loop exit edges are estimated as "cold" paths relative to back edges and should be considered uniformly with other coldness/hotness markers.

Reviewed By: yrouban

Differential Revision: https://reviews.llvm.org/D79485

show more ...

[Analysis, CodeGen, IR] Use contains (NFC)

[BPI] Look through bitcasts in calcZeroHeuristic

Constant hoisting may hide the constant value behind bitcast for And's
operand. Track down the constant to make the BFI result consistent
regardless

[BPI] Look through bitcasts in calcZeroHeuristic

Constant hoisting may hide the constant value behind bitcast for And's
operand. Track down the constant to make the BFI result consistent
regardless of hoisting.

Differential Revision: https://reviews.llvm.org/D91450

show more ...

[JumpThreading] Call eraseBlock when folding a conditional branch

This patch teaches the jump threading pass to call BPI->eraseBlock
when it folds a conditional branch.

Without this patch, BranchPr

[JumpThreading] Call eraseBlock when folding a conditional branch

This patch teaches the jump threading pass to call BPI->eraseBlock
when it folds a conditional branch.

Without this patch, BranchProbabilityInfo could end up with stale edge
probabilities for the basic block containing the conditional branch --
one edge probability with less than 1.0 and the other for a removed
edge.

This patch is one of the steps before we can safely re-apply D91017.

Differential Revision: https://reviews.llvm.org/D91511

show more ...

[BranchProbabilityInfo] Use predecessors(BB) and successors(BB) (NFC)

Revert "[BranchProbabilityInfo] Use SmallVector (NFC)"

This reverts commit 2f1038c7b699e959e0521638e2e2818a849fe19c.

[BranchProbabilityInfo] Use a range-based for loop (NFC)

[BranchProbabilityInfo] Use SmallVector (NFC)

This patch simplifies BranchProbabilityInfo by changing the type of
Probs.

Without this patch:

DenseMap<Edge, BranchProbability> Probs

maps an orde

[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

show more ...

[BranchProbabilityInfo] Simplify getEdgeProbability (NFC)

The patch simplifies BranchProbabilityInfo::getEdgeProbability by
handling two cases separately, depending on whether we have edge
probabili

[BranchProbabilityInfo] Simplify getEdgeProbability (NFC)

The patch simplifies BranchProbabilityInfo::getEdgeProbability by
handling two cases separately, depending on whether we have edge
probabilities.

- If we have edge probabilities, then add up probabilities for
successors being equal to Dst.

- Otherwise, return the number of ocurrences divided by the total
number of successors.

Differential Revision: https://reviews.llvm.org/D90980

show more ...

[BranchProbabilityInfo] Use succ_size (NFC)

[BranchProbabilityInfo] Introduce method copyEdgeProbabilities(). NFC

A new method is introduced to allow bulk copy of outgoing edge
probabilities from one block to another. This can be useful when

[BranchProbabilityInfo] Introduce method copyEdgeProbabilities(). NFC

A new method is introduced to allow bulk copy of outgoing edge
probabilities from one block to another. This can be useful when
a block is cloned from another one and we do not know if there
are edge probabilities set for the original block or not.
Copying outside of the BranchProbabilityInfo class makes the user
unconditionally set the cloned block's edge probabilities even if
they are unset for the original block.

Reviewed By: MaskRay

Differential Revision: https://reviews.llvm.org/D90839

show more ...