[LLVMbugs] [Bug 20316] New: Expose a block "bias" metric from BlockFrequencyInfo

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=20316

            Bug ID: 20316
           Summary: Expose a block "bias" metric from BlockFrequencyInfo
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Global Analyses
          Assignee: unassignedbugs at nondot.org
          Reporter: dexonsmith at apple.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Chandler and Diego highlighted a few places that "block frequency" is hard to
use (see http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-February/069963.html
and follow-ups).

As part of rewriting BFI, I mapped out a plan for a exposing a "bias" metric as
a second output.

While block frequency measures how often a block is likely to be executed
compared to an arbitrary reference point -- used by comparing against the block
frequency of a "section" entry block (like the function entry or loop header)
-- block bias measures how much more (or less) likely a block is to be executed
than its "competing" branches.

Here's the idea of bias:

 1. Calculate block frequency normally.

 2. In parallel, calculate a "reference" block frequency for every block, which
represents an unbiased block frequency.

 3. Take the ratio of the two, and call it the block bias.

The reference block frequency calculations assume that all branch weights are
even.  E.g., if a block has three successor edges, then each edge has a
probability of 1/3.  If a block has five successor edges and two of them go to
the same block, the effective probability for that successor is 2/5.

Furthermore, the reference block frequency is not scaled up by the expected
number of loop iterations.

The result is that for code like this:

define void @loop_with_branch(i32 %a) {
entry:
  %skip_loop = call i1 @foo0(i32 %a)
  br i1 %skip_loop, label %skip, label %header, !prof !0

skip:
  br label %exit

header:
  %i = phi i32 [ 0, %entry ], [ %i.next, %back ]
  %i.next = add i32 %i, 1
  %choose = call i2 @foo1(i32 %i)
  switch i2 %choose, label %exit [ i2 0, label %left
                                   i2 1, label %right ], !prof !1

left:
  br label %back

right:
  br label %back

back:
  br label %header

exit:
  ret void
}
!0 = metadata !{metadata !"branch_weights", i32 1, i32 3}
!1 = metadata !{metadata !"branch_weights", i32 1, i32 2, i32 3}

We get freq[uency], ref[erence frequency], and bias like this:

 - entry:  freq = 1.0,  ref = 1.0,          bias = 1.0
 - header: freq = 4.5,  ref = 0.5,          bias = 9.0
 - right:  freq = 2.25, ref = 0.1666666667, bias = 13.5
 - left:   freq = 1.5,  ref = 0.1666666667, bias = 9.0
 - back:   freq = 3.75, ref = 0.3333333333, bias = 11.25
 - skip:   freq = 0.25, ref = 0.5,          bias = 0.5
 - exit:   freq = 1.0,  ref = 1.0,          bias = 1.0

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20140716/f957ef80/attachment.html>