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: [email protected]
Reporter: [email protected]
CC: [email protected], [email protected]
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.
_______________________________________________
LLVMbugs mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/llvmbugs
