[LLVMbugs] [Bug 23447] New: Compile time performance issues in branch probability API

[bugzilla-daemon at llvm.org]

https://llvm.org/bugs/show_bug.cgi?id=23447

            Bug ID: 23447
           Summary: Compile time performance issues in branch probability
                    API
           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

[ Split from original report in https://llvm.org/bugs/show_bug.cgi?id=22718 ]

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/20150507/fbd70931/attachment.html>