https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100499
--- Comment #17 from Richard Biener <rguenth at gcc dot gnu.org> --- (In reply to Andrew Macleod from comment #16) > Aldy and I are discussing this. > > Ranger itself can't do anything outside of the gimple IL, its effectively > just a GIMPLE interface to range-ops. ... but I don't think it would be > hard to add a range-ops expression evaluator. I notice the multiple_of_p's > "top" argument is an expression tree ie: > > g_2823_lsm.5_13 * 7854 + 57682 > > We could add an expression evaluator that can walk that expression, invoking > range-ops on each expression, and calling a ranger instance to evaluate a > range for any ssa_name it finds. > > It would bail if there are unknown tree-codes to range-ops. Yeah, it would be similar to the existing determine_value_range () function which does exactly do this (but not using ranger). > I don't think this is a particularly difficult thing to do, but by itself > doesn't really tell you if an overflow is possible Yes, so in itself it wouldn't be enough. > Once we can evaluate an expression outside of the IL like this, it would > also not be difficult to then evaluate the expression in an increased > precision. > We could cast the range at each point of the evaluation to the increased > precision and invoke range-ops on that range. We could tell at any point if > an overflow is possible because the increased precision calculation would be > different than the original. > > so the original expression is in 16 bit math, and if it was evaluated as > [0, 65535] * [7854, 7854] + [57682, 57682] > in 32 bit precision, it would come back with the answer [57682, 514769572]. > Casting the final original value to 32 bit would yield a different result, > and we could conclude than an overflow is possible. > > Would this be useful? and would it solve this problem? I'm sure there are > other details to work out related to the increased precision, but it seems > like it might work? Hmm, so the issue we're facing is asking whether x * 3 is a multiple of 3 but we have to consider that x * 3 might overflow. For '3' being power-of-two overflow doesn't change anything but for some C ((X * C) % S % C) != 0 (where S is the modulo reduction applied on overflow). So it seems that, to be useful, this ranger expression walk would need to be integrated with multiple_of_p itself. Or we need to restrict calls to multiple_of_p to those C where S is a multiple of C. (but in principle multiple_of_p is happy with a symbolic C - not sure if it is ever called with one though) > I think Martin Sebor was also interested in something along these lines so > I'm CC ing him. I think he wanted to do this within the IL for some of his > warnings.. but I think something similar is feasible with an IL walk rather > than expression walk.
