Skip to content
  • Andrew Trick's avatar
    A new algorithm for computing LoopInfo. Temporarily disabled. · ff2ed7b6
    Andrew Trick authored
    -stable-loops enables a new algorithm for generating the Loop
    forest. It differs from the original algorithm in a few respects:
    
    - Not determined by use-list order.
    - Initially guarantees RPO order of block and subloops.
    - Linear in the number of CFG edges.
    - Nonrecursive.
    
    I didn't want to change the LoopInfo API yet, so the block lists are
    still inclusive. This seems strange to me, and it means that building
    LoopInfo is not strictly linear, but it may not be a problem in
    practice. At least the block lists start out in RPO order now. In the
    future we may add an attribute or wrapper analysis that allows other
    passes to assume RPO order.
    
    The primary motivation of this work was not to optimize LoopInfo, but
    to allow reproducing performance issues by decomposing the compilation
    stages. I'm often unable to do this with the current LoopInfo, because
    the loop tree order determines Loop pass order. Serializing the IR
    tends to invert the order, which reverses the optimization order. This
    makes it nearly impossible to debug interdependent loop optimizations
    such as LSR.
    
    I also believe this will provide more stable performance results across time.
    
    llvm-svn: 158790
    ff2ed7b6
Loading