<html>
<head>
<base href="http://llvm.org/bugs/" />
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW --- - Expose a block "bias" metric from BlockFrequencyInfo"
href="http://llvm.org/bugs/show_bug.cgi?id=20316">20316</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Expose a block "bias" metric from BlockFrequencyInfo
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>All
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Global Analyses
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>dexonsmith@apple.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvmbugs@cs.uiuc.edu
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>Chandler and Diego highlighted a few places that "block frequency" is hard to
use (see <a href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-February/069963.html">http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-February/069963.html</a>
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</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>