• Andreas Klebinger's avatar
    Add loop level analysis to the NCG backend. · 535a88e1
    Andreas Klebinger authored
    For backends maintaining the CFG during codegen
    we can now find loops and their nesting level.
    This is based on the Cmm CFG and dominator analysis.
    As a result we can estimate edge frequencies a lot better
    for methods, resulting in far better code layout.
    Speedup on nofib: ~1.5%
    Increase in compile times: ~1.9%
    To make this feasible this commit adds:
    * Dominator analysis based on the Lengauer-Tarjan Algorithm.
    * An algorithm estimating global edge frequences from branch
    probabilities - In CFG.hs
    A few static branch prediction heuristics:
    * Expect to take the backedge in loops.
    * Expect to take the branch NOT exiting a loop.
    * Expect integer vs constant comparisons to be false.
    We also treat heap/stack checks special for branch prediction
    to avoid them being treated as loops.
Code owners : Ben Gamari
Dominators.hs 15.6 KB