Under the hood, MBPI is doing a linear scan of every successor every
authorChandler Carruth <chandlerc@gmail.com>
Mon, 14 Nov 2011 09:12:57 +0000 (09:12 +0000)
committerChandler Carruth <chandlerc@gmail.com>
Mon, 14 Nov 2011 09:12:57 +0000 (09:12 +0000)
commit340d596509129de8c3fa9dbe4184a2b148b78757
tree5511416c0f2745ec7e3e67bc5af47dfcd3c70dfd
parentae5a6fd31575add771264020c8365c6e89d7f912
Under the hood, MBPI is doing a linear scan of every successor every
time it is queried to compute the probability of a single successor.
This makes computing the probability of every successor of a block in
sequence... really really slow. ;] This switches to a linear walk of the
successors rather than a quadratic one. One of several quadratic
behaviors slowing this pass down.

I'm not really thrilled with moving the sum code into the public
interface of MBPI, but I don't (at the moment) have ideas for a better
interface. My direction I'm thinking in for a better interface is to
have MBPI actually retain much more state and make *all* of these
queries cheap. That's a lot of work, and would require invasive changes.
Until then, this seems like the least bad (ie, least quadratic)
solution. Suggestions welcome.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144530 91177308-0d34-0410-b5e6-96231b3b80d8
include/llvm/CodeGen/MachineBranchProbabilityInfo.h
lib/CodeGen/MachineBlockPlacement.cpp