Skip to content

Draft: Statically estimate execution frequency of CoreAlts (#20378)

Sebastian Graf requested to merge wip/exec-freq into master

This patch implements #20378. See Note [Estimating CoreAlt frequencies] in the new module GHC.Core.Opt.ExecFreq for details.

These were the changes:

  1. Introduce newtype Freq = Freq Float as a type that captures relative execution frequency and use it as an additional field in CoreAlt. The default when we have no estimate available is NoFreq, e.g., NaN. Otherwise, all Freqs of a Case should add up to 1. Then fix up a whole bunch of use sites.
  2. Introduce a new enum Comparison for the different kinds of comparison operators (LessThan, GreaterOrEqual, NotEqual, ...). Then make Compare primops also declare what kind of Comparison they do. Then introduce a function isComparisonApp_maybe in GHC.Core.Utils that we can use for our estimates (see below).
  3. Write a static analysis pass estimateAltFreqs, that annotates CoreAlts with their relative execution Freq. These Freqs are determined by combining the estimates of different branch heuristics, one of which uses the new isComparisonApp_maybe.

The main function estimateAltFreqs is currently dead, but that is bound to change in follow-up MRs.

Fixes #20378.

Edited by Sebastian Graf

Merge request reports