HomePhabricator

A post-processing for BFI inference

Authored by spupyrev on Jun 11 2021, 9:45 PM.

Description

A post-processing for BFI inference

The current implementation for computing relative block frequencies does
not handle correctly control-flow graphs containing irreducible loops. This
results in suboptimally generated binaries, whose perf can be up to 5%
worse than optimal.

To resolve the problem, we apply a post-processing step, which iteratively
updates block frequencies based on the frequencies of their predesessors.
This corresponds to finding the stationary point of the Markov chain by
an iterative method aka "PageRank computation". The algorithm takes at
most O(|E| * IterativeBFIMaxIterations) steps but typically converges faster.

It is turned on by passing option use-iterative-bfi-inference
and applied only for functions containing profile data and irreducible loops.

Tested on SPEC06/17, where it is helping to get correct profile counts for one of
the binaries (403.gcc). In prod binaries, we've seen a speedup of up to 2%-5%
for binaries containing functions with hot irreducible loops.

Reviewed By: hoy, wenlei, davidxl

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

Details

Committed
wenleiJun 11 2021, 9:46 PM
Reviewer
hoy
Differential Revision
D103289: A post-processing for BFI inference
Parents
rGdbc262968f8e: [Flang][test] Fix Windows buildbot.
Branches
Unknown
Tags
Unknown