This is an archive of the discontinued LLVM Phabricator instance.

Fix information loss in branch probability computation.
ClosedPublic

Authored by dnovillo on May 1 2015, 1:21 PM.

Details

Summary

This addresses PR 22718. When branch weights are too large, they were
being clamped to the range [1, MaxWeightForBB]. But this clamping is
only applied to edges that go outside the range, so it distorts the
relative branch probabilities.

This patch changes the weight calculation to scale every branch so the
relative probabilities are preserved.

The patch fixes an existing test that had slightly wrong branch
probabilities due to the previous clamping. It now gets branch weights
scaled accordingly.

Diff Detail

Event Timeline

dnovillo updated this revision to Diff 24827.May 1 2015, 1:21 PM
dnovillo retitled this revision from to Fix information loss in branch probability computation..
dnovillo updated this object.
dnovillo edited the test plan for this revision. (Show Details)
dnovillo added a reviewer: dexonsmith.
dnovillo added a subscriber: Unknown Object (MLST).
dnovillo updated this revision to Diff 25103.May 6 2015, 4:00 PM

This modifies the scaling to do it based on the sum of all branch weights. If
the sum of weights exceeds 32 bits, compute an integer scale to bring all the
weights within the range.

Additionally, remove the use of scaled integers. Use 64 bit integers for
all the calculations.

Adjust tests and an assertion in switch lowering. The assertion was
using the previous branch weight limits.

dnovillo updated this revision to Diff 25192.May 7 2015, 8:26 AM

This version fixes the 32bit overflow check in visitSwitch()

This revision was automatically updated to reflect the committed changes.