> > Ugh. Both to stmt_dominates_stmt_p and to this (both use loops). > For stmt_dominates_stmt_p you'd simply use GIMPLE uids as other > passes do (and compute them, of course), for the above you'd > alongside of the UID store a sequence number that increments > at each stmt with side-effect. UID is 32bits, so you could > even store (stmt-number-in-bb << 8) | side-effect-nr in UID > (with the issue that if there are exactly 256 side-effect stmts > inbetween the two stmts you'd miss that fact ...). > > Well. At least those loops are a real issue IMHO. Adding a > second doesn't make complexity worse I understand - still ... > I expected better from you ;) > > Patch is ok, but think about this for a minute - eventually > you can come up with sth very clever.
As I wrote in the comment above, I think it is best to precompute the bounds in number of iterations in basic blocks by same algorithm as discover_iteration_bound_by_body_walk. We will then have O(nstmts+nbounds) algorithm. The challenge is where to attach the data and how to keep it up to date. The non-wrappingness is tested on random uses of SCEV across the compiler when the loop body can be somewhat modified already (so thus also UIDs will run out of sync). Moreover the non-wrappingness is used by niter logic itself when bounds are being inserted (giving conservatively wrong answers) So I think it is more of 4.9 material. I would expect us to be actually slightly faster than before the patch, because we skip the bound walk when iterations already give the info. With constant time gsi_for_stmt the loop in stmt_dominates_stmt_p can probably be changed to start walk on one statement and look for the second. Honza
