blockfreq: Rewrite BlockFrequencyInfoImpl

Rewrite the shared implementation of BlockFrequencyInfo and

MachineBlockFrequencyInfo entirely.

The old implementation had a fundamental flaw: precision losses from

nested loops (or very wide branches) compounded past loop exits (and

convergence points).

The @nested_loops testcase at the end of

test/Analysis/BlockFrequencyAnalysis/basic.ll is motivating. This

function has three nested loops, with branch weights in the loop headers

of 1:4000 (exit:continue). The old analysis gives non-sensical results:

Printing analysis 'Block Frequency Analysis' for function 'nested_loops': ---- Block Freqs ---- entry = 1.0 for.cond1.preheader = 1.00103 for.cond4.preheader = 5.5222 for.body6 = 18095.19995 for.inc8 = 4.52264 for.inc11 = 0.00109 for.end13 = 0.0

The new analysis gives correct results:

Printing analysis 'Block Frequency Analysis' for function 'nested_loops': block-frequency-info: nested_loops - entry: float = 1.0, int = 8 - for.cond1.preheader: float = 4001.0, int = 32007 - for.cond4.preheader: float = 16008001.0, int = 128064007 - for.body6: float = 64048012001.0, int = 512384096007 - for.inc8: float = 16008001.0, int = 128064007 - for.inc11: float = 4001.0, int = 32007 - for.end13: float = 1.0, int = 8

Most importantly, the frequency leaving each loop matches the frequency

entering it.

The new algorithm leverages BlockMass and PositiveFloat to maintain

precision, separates "probability mass distribution" from "loop

scaling", and uses dithering to eliminate probability mass loss. I have

unit tests for these types out of tree, but it was decided in the review

to make the classes private to BlockFrequencyInfoImpl, and try to shrink

them (or remove them entirely) in follow-up commits.

The new algorithm should generally have a complexity advantage over the

old. The previous algorithm was quadratic in the worst case. The new

algorithm is still worst-case quadratic in the presence of irreducible

control flow, but it's linear without it.

The key difference between the old algorithm and the new is that control

flow within a loop is evaluated separately from control flow outside,

limiting propagation of precision problems and allowing loop scale to be

calculated independently of mass distribution. Loops are visited

bottom-up, their loop scales are calculated, and they are replaced by

pseudo-nodes. Mass is then distributed through the function, which is

now a DAG. Finally, loops are revisited top-down to multiply through

the loop scales and the masses distributed to pseudo nodes.

There are some remaining flaws.

- Irreducible control flow isn't modelled correctly. LoopInfo and MachineLoopInfo ignore irreducible edges, so this algorithm will fail to scale accordingly. There's a note in the class documentation about how to get closer. See also the comments in test/Analysis/BlockFrequencyInfo/irreducible.ll.

- Loop scale is limited to 4096 per loop (2^12) to avoid exhausting the 64-bit integer precision used downstream.

- The "bias" calculation proposed on llvmdev is *not* incorporated here. This will be added in a follow-up commit, once comments from this review have been handled.