This is an archive of the discontinued LLVM Phabricator instance.

[BPI] Use saturating multiplication to calculate denominators
ClosedPublic

Authored by vsk on Dec 16 2016, 2:37 PM.

Details

Summary

BPI may trigger signed overflow UB while computing branch probabilities
for cold calls or to unreachables. For example, with our current choice
of weights, we'll crash if there are >= 2^12 branches to an unreachable.

Use an alternate BranchProbability constructor which handles large fractions.

Diff Detail

Repository
rL LLVM

Event Timeline

vsk updated this revision to Diff 81795.Dec 16 2016, 2:37 PM
vsk updated this revision to Diff 81797.
vsk retitled this revision from to [BPI] Use saturating multiplication to calculate denominators (WIP).
vsk updated this object.
vsk added reviewers: congh, davidxl, junbuml.
vsk added a subscriber: llvm-commits.
  • Include the test case, which I accidentally forgot when I first uploaded the diff.
vsk updated this revision to Diff 81806.Dec 16 2016, 3:32 PM
vsk retitled this revision from [BPI] Use saturating multiplication to calculate denominators (WIP) to [BPI] Use saturating multiplication to calculate denominators.
vsk updated this object.
  • Remove the lit test in favor of a more flexible lit test.
  • Still no test for the cold call heuristic, because that would require creating ~2^26 edges. That's too much overhead for a unit test.
davidxl added inline comments.Dec 16 2016, 3:56 PM
lib/Analysis/BranchProbabilityInfo.cpp
167 ↗(On Diff #81806)

BranchProbablity::getBranchProbablity(..) method takes uint64 as the argument. You can probably use that

vsk updated this revision to Diff 81811.Dec 16 2016, 4:04 PM
vsk updated this object.
vsk marked an inline comment as done.
  • Use BranchProbability::getBranchProbability, per David's suggestion.
  • Fix a typo in the unit test.
davidxl accepted this revision.Dec 16 2016, 4:13 PM
davidxl edited edge metadata.

lgtm

This revision is now accepted and ready to land.Dec 16 2016, 4:13 PM
This revision was automatically updated to reflect the committed changes.