Fix compilation slowdown due to controlflow analysis

[sklam]

• makes CFG computation lazier.
• replace backedge algorithm with a DFS based algorithm instead of dominator-based.

[sklam]

My current reproducer for issue #6133

from pprint import pprint
import numpy as np
import numba

body = """
    for fi in range(0, 10):
        data[fi] += 1
        for index in range(0, 7):
            idx = index
            if idx % 2 == 0:
                data[idx] += fi
            else:
                data[idx] += 1 if data[idx] < 3 else 2
                data[idx] += 1
            data[idx] += 1
"""

wrapper = """
def kernel(data):
    {}
"""

source = wrapper.format(body * 100) # 75
glbs = {}
exec(source, glbs)

arg = np.zeros(100)
argtypes = (numba.typeof(arg),)

kernel = numba.njit(argtypes)(glbs['kernel'])

# 0.48.0 takes 24sec
# 0.51.0 takes 1min13sec

metadata = kernel.get_metadata(kernel.signatures[0])
timings = metadata['pipeline_times']['nopython']
sorttimings = sorted(timings.items(), key=lambda x: sum(x[1]))
for k, v in reversed(sorttimings):
    print(f"{k:40} {sum(v):.3}")

This prints the compiler passes in descending runtime.

With the patch:

13_reconstruct_ssa                       25.3
20_nopython_backend                      13.2
18_nopython_rewrites                     2.36

Without the patch:

13_reconstruct_ssa                       40.1
20_nopython_backend                      13.5
18_nopython_rewrites                     3.23

So the patch trims 20 seconds from SSA

[sklam]

264665e replaces the backedge algorithm with a simple but faster DFS version. This further speed up the SSA reconstruction:

20_nopython_backend                      15.8
13_reconstruct_ssa                       8.74
18_nopython_rewrites                     2.37

(updated to use output from non-profiled run)

[stuartarchibald]

Thanks for the patch. I tested this manually, locally, 10.4->4.73s change in SSA rebuild.

[stuartarchibald]

Code changes look good, couple of minor comments.

[stuartarchibald]

Can probably remove this comment now, process() has little effect as everything is delayed.

[sklam]

good catch.

[sklam]

Resolved all comments.
Merged master and resolved a conflict of missing import

[stuartarchibald]

Thanks for the fixes.