Skip to content
Snippets Groups Projects
  • Chandler Carruth's avatar
    Take two on rotating the block ordering of loops. My previous attempt · 03adbd46
    Chandler Carruth authored
    was centered around the premise of laying out a loop in a chain, and
    then rotating that chain. This is good for preserving contiguous layout,
    but bad for actually making sane rotations. In order to keep it safe,
    I had to essentially make it impossible to rotate deeply nested loops.
    The information needed to correctly reason about a deeply nested loop is
    actually available -- *before* we layout the loop. We know the inner
    loops are already fused into chains, etc. We lose information the moment
    we actually lay out the loop.
    
    The solution was the other alternative for this algorithm I discussed
    with Benjamin and some others: rather than rotating the loop
    after-the-fact, try to pick a profitable starting block for the loop's
    layout, and then use our existing layout logic. I was worried about the
    complexity of this "pick" step, but it turns out such complexity is
    needed to handle all the important cases I keep teasing out of benchmarks.
    
    This is, I'm afraid, a bit of a work-in-progress. It is still
    misbehaving on some likely important cases I'm investigating in Olden.
    It also isn't really tested. I'm going to try to craft some interesting
    nested-loop test cases, but it's likely to be extremely time consuming
    and I don't want to go there until I'm sure I'm testing the correct
    behavior. Sadly I can't come up with a way of getting simple, fine
    grained test cases for this logic. We need complex loop structures to
    even trigger much of it.
    
    llvm-svn: 145183
    03adbd46