Skip to content
  1. Oct 21, 2011
    • Chandler Carruth's avatar
      Implement a block placement pass based on the branch probability and · 10281425
      Chandler Carruth authored
      block frequency analyses. This differs substantially from the existing
      block-placement pass in LLVM:
      
      1) It operates on the Machine-IR in the CodeGen layer. This exposes much
         more (and more precise) information and opportunities. Also, the
         results are more stable due to fewer transforms ocurring after the
         pass runs.
      2) It uses the generalized probability and frequency analyses. These can
         model static heuristics, code annotation derived heuristics as well
         as eventual profile loading. By basing the optimization on the
         analysis interface it can work from any (or a combination) of these
         inputs.
      3) It uses a more aggressive algorithm, both building chains from tho
         bottom up to maximize benefit, and using an SCC-based walk to layout
         chains of blocks in a profitable ordering without O(N^2) iterations
         which the old pass involves.
      
      The pass is currently gated behind a flag, and not enabled by default
      because it still needs to grow some important features. Most notably, it
      needs to support loop aligning and careful layout of loop structures
      much as done by hand currently in CodePlacementOpt. Once it supports
      these, and has sufficient testing and quality tuning, it should replace
      both of these passes.
      
      Thanks to Nick Lewycky and Richard Smith for help authoring & debugging
      this, and to Jakob, Andy, Eric, Jim, and probably a few others I'm
      forgetting for reviewing and answering all my questions. Writing
      a backend pass is *sooo* much better now than it used to be. =D
      
      llvm-svn: 142641
      10281425
Loading