https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100081
--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> --- (In reply to Andrew Macleod from comment #8) > OMG. Don't bother reducing. I can see the problem. > > EVRP is fine, but when wrestrict runs, its quite late, and the CFG has > > <bb 560> [local count: 28382607]: > <...> > _571 = _61 >= _593; > _3583 = &arr_724 + _3992; > _2220 = _831 <= _3583; > _47 = _571 | _2220; > _2935 = _376 * 2; > _3966 = &arr_725 + _2935; > _3024 = _61 >= _3966; > _4219 = _3992 * 2; > _4218 = &arr_725 + _4219; > _1836 = _831 <= _4218; > _3080 = _1836 | _3024; > <...> > _5348 = _5347 & _32080; > _5349 = _5348 & _32151; > _5350 = _5349 & _32176; > _5351 = _5350 & _32488; > _5352 = _5351 & _33691; > _5353 = _5352 & _33762; > _5354 = _5353 & _34753; > _35662 = _5354 & _34824; > if (_35662 != 0) > goto <bb 561>; [90.00%] > else > goto <bb 1510>; [10.00%] > > Its a 7200 stmt basic block, made up of calculations and 2614 ORs and 1480 > ANDs. > > A request is made for a range which can be exported from this block, and > ranger is dutifully trying everything it can to process those blocks. > > Each AND/OR is a logical expression which evaluates a TRUE and FALSE range > for each operands, so it calculates up to 4 ranges for each pair of > operands. I knew this could get out of hand in pathological cases, so we > introduced a logical cache to help resolve this and avoid extra work. Its > actually making this one worse I think. Hmm, still the overall work should be linear to produce ranges for all of the SSA defs in this BB, no? As heuristic you might want to avoid producing ranges for single-use defs, like those that are just used in another & or | combination? Wrestrict should only be interested in ranges for the "tails" of this &| tree (for example _61 in _61 >= _3966). But yes, if you have any worse than O(n log n) algorithm then artificially limiting it's cost by capping 'n' at some (--param controlled) value is the way to go.
