Skip to content
  • Erik Verbruggen's avatar
    V4 IR: (natural) loop detection. · 48dcabdb
    Erik Verbruggen authored
    
    
    We perform loop detection to be able to assign to each block its loop,
    an chain them up from inner loop to outer loop. The new algorithm works
    on each basic block just once, and looks at a basic block just the
    number of connections it has. As it relies on the dominator tree it is
    more robust on actually finding al looping constructs and only those
    rather than relying on the statements used. It assumes that a basic
    block is analyzed before the one that dominate it (to guarantee finding
    outer loop headers before inner loop headers), so blocks are ordered to
    work on them in a way that guarantees that, using dominator tree depth,
    that is trivially available.
    
    Loop detection allows us to then schedule the loop body before the part
    after the loop (the header dominates both so just domination cannot
    choose between both), and can be used to optimize loops (either
    unrolling the first iteration or hoisting constant parts out of it).
    
    It also helps with generated JavaScript code: in order to simulate gotos
    or other unconditional branches, nested labeled do-while(false) loops
    are often used in combination with break/continue to "jump" between
    "loops".
    
    Change-Id: Idfcc74589e057b191f74880ffd309d0a9c301811
    Reviewed-by: default avatarFawzi Mohamed <fawzi.mohamed@digia.com>
    48dcabdb