Analysis run with extensive restarting causes stack overflow

[stilscher]

For several commits of zstd, the incremental analysis with extensive restarting throws a stack overflow exception:

vars = 0    evals = 0    narrow_reuses = 0    aborts = 0

Timings:
TOTAL                           2.247 s
  parse                           0.774 s
  convert to CIL                  0.971 s
  mergeCIL                        0.372 s
  compareCilFiles                 0.130 s
  analysis                        0.000 s
    createCFG                       1.869 s
      handle                          0.216 s
      iter_connect                    1.593 s
        computeSCCs                     0.430 s
    global_inits                    0.228 s
    solving                        36.415 s
Timing used
Memory statistics: total=86795.74MB, max=5410.87MB, minor=84327.94MB, major=3489.57MB, promoted=1021.78MB
    minor collections=40232  major collections=17 compactions=0

Fatal error: exception Stack overflow

commit: 874a590 (parent commit: 9f327c0)

[sim642]

This is interesting because the destabilize_with_side used for restarting is just based on the old destabilize, of course neither is tail recursive. It's just TD3's solve which is tail recursive.

I wonder if a destabilize stack overflow might then also happen without restarting, given a big enough program. I suppose destabilize_with_side makes the stack bound more easily reachable since it follows additional infl/dep, which is how it can go deeper.

destabilize itself is essentially a DFS in its current form. Since it's quite self-contained (i.e. doesn't need to call solve etc), it should be possible to just replace it with DFS/BFS, which is more imperative rather than so recursive.

Unless there's some other bigger issue (like infinite recursion), this should be avoidable by just increasing stack size.