[LLVMbugs] [Bug 22718] New: Information loss and performance issues in branch probability representation

[bugzilla-daemon at llvm.org]

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

            Bug ID: 22718
           Summary: Information loss and performance issues in branch
                    probability representation
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Global Analyses
          Assignee: dnovillo at google.com
          Reporter: dnovillo at google.com
                CC: davidxl at google.com, llvmbugs at cs.uiuc.edu
    Classification: Unclassified

BranchProbabilityInfo, MachineBranchProbabilityInfo mimic the raw profile data
representation and represents branch probability using non-normalized weights.
We have found some issues where this representation loses information.

Scaling and capping of branch weights may lead to distorted probability for
very hot branches:

 - The weight for each branch is capped at UINT32_MAX/number_successors. The
max weight limit imposed is too small for long-running applications -- hot
branches can easily hit the cap.

 - When any branch weight hits the limit, the implementation does not actually
do any scaling on weights of other branches. For hot branches, this can cause a
highly biased branch to become non-biased. Cascading bad effects will also
occur in the frequency propagation stage due to the capping.

This happens in BranchProbabilityInfo::calcMetadataWeights, as well as
MachineBranchProbabilityInfo::getSumForBlock(const MachineBasicBlock *MBB,
uint32_t &Scale) const

Additionally, the API for getting branch probabilities has some performance
issues:

For many clients where getting relative branch hotness is enough, the client
can simply use getEdgeWeight interface. However if the client needs to know the
actual branch probability, getEdgeProbability is needed. To compute edge
probability, the implementation needs to compute getSumForBlock which needs to
walk through all successors. This has O(N^2) behavior when we need to compute
branch prob for each out going cfg edge.

Instead of representing branch probabilities using non-normalized weights, we
could represent probabilities directly using a fixed point representation with
scaling (between 0 and 1). The benefits would be:

1) conceptually simple. This would allow us to not rely on weight.
2) clients using getEdgeWeight are not affected. The weight can be derived from
getEdgeProb
3) The implementation for getEdgeProb becomes faster.


Finally, we could change the DenseMap hash key for edge probabilities.
Currently, edge probabilities are stored in a map using Pair<BasicBlock*,
SuccessIndex> as the key. Retrieving branch probability information is slow, as
it needs to walk through successors, find the match, and then use the successor
index to do the lookup. A solution that used pair<BasicBlock*, BasicBlock*> as
the key would avoid that.

-- 
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/20150226/35a35182/attachment.html>