Re: [PATCH 1/2]middle-end: Fix wrong overmatching of div-bitmask by using new optabs [PR108583]

[Andrew MacLeod <amacleod@redhat.com>]

On 2/15/23 07:51, Tamar Christina wrote:
>>>>>> In any case, if you disagree I don’t' really see a way forward
>>>>>> aside from making this its own pattern running it before the
>>>>>> overwidening
>>> pattern.
>>>>> I think we should look to see if ranger can be persuaded to provide
>>>>> the range of the 16-bit addition, even though the statement that
>>>>> produces it isn't part of a BB.  It shouldn't matter that the
>>>>> addition originally came from a 32-bit one: the range follows
>>>>> directly from the ranges of the operands (i.e. the fact that the
>>>>> operands are the results of widening conversions).
>>>> I think you can ask ranger on operations on names defined in the IL,
>>>> so you can work yourself through the sequence of operations in the
>>>> pattern sequence to compute ranges on their defs (and possibly even
>>>> store them in the SSA info).  You just need to pick the correct
>>>> ranger API for this…. Andrew CCed
>>>>
>>>>
>>> Its not clear to me whats being asked...
>>>
>>> Expressions don't need to be in the IL to do range calculations.. I
>>> believe we support arbitrary tree expressions via range_of_expr.
>>>
>>> if you have 32 bit ranges that you want to do 16 bit addition on, you
>>> can also cast those ranges to a 16bit type,
>>>
>>> my32bitrange.cast (my16bittype);
>>>
>>> then invoke range-ops directly via getting the handler:
>>>
>>> handler = range_op_handler (PLUS_EXPR, 16bittype_tree); if (handler)
>>>      handler->fold (result, my16bittype, mycasted32bitrange,
>>> myothercasted32bitrange)
>>>
>>> There are higher level APIs if what you have on hand is closer to IL
>>> than random ranges
>>>
>>> Describe exactly what it is you want to do... and I'll try to direct
>>> you to the best way to do it.
>> The vectorizer has  a pattern matcher that runs at startup on the scalar code.
>> This pattern matcher can replace one or more statements with alternative
>> ones, these can be either existing tree_code or new internal functions.
>>
>> One of the patterns here is a overwidening detection pattern which reduces
>> the precision that an operation is to be done in during vectorization.
>>
>> Another one is widening multiplication, which replaced PLUS_EXPR with
>> WIDEN_PLUS_EXPR.
>>
>> These can be chained, so e.g. a widening addition done on ints can be
>> reduced to a widen addition done on shorts.
>>
>> The question is whether given the new expression that the vectorizer has
>> created whether ranger can tell what the precision is.  get_range_query fails
>> because presumably it has no idea about the new operations created  and
>> also doesn't know about any new IFNs.
> Hi,
>
> I have been trying to use ranger as requested. I've tried:
>
> 	  gimple_ranger ranger;
> 	  int_range_max r;
> 	  /* Check that no overflow will occur.  If we don't have range
> 	     information we can't perform the optimization.  */
> 	  if (ranger.range_of_expr (r, oprnd0, stmt))
> 	    {
> 	      wide_int max = r.upper_bound ();
>                      ....
>
> Which works for non-patterns, but still doesn't work for patterns.
> On a stmt:
> patt_27 = (_3) w+ (level_15(D));
>
> it gives me a range:
>
> $2 = {
>    <wide_int_storage> = {
>      val = {[0x0] = 0xffffffffffffffff, [0x1] = 0x7fff95bd8b00, [0x2] = 0x7fff95bd78b0, [0x3] = 0x3fa1dd0, [0x4] = 0x3fa1dd0, [0x5] = 0x344a706f832d4f00, [0x6] = 0x7fff95bd7950, [0x7] = 0x1ae7f11, [0x8] = 0x7fff95bd79f8},
>      len = 0x1,
>      precision = 0x10
>    },
>    members of generic_wide_int<wide_int_storage>:
>    static is_sign_extended = 0x1
> }
>
> The precision is fine, but range seems to be -1?
>
> Should I use range_op_handler (WIDEN_PLUS_EXPR, ...) in this case?

Its easier to see the range if you dump it.. ie:

p r.dump(stderr)

Im way behind the curve on exactly whats going on.  Im not sure how the 
above 2 things relate..  I presume $2 is is 'max'?  I have no context, 
what did you expect the range of _3 to be?

We have no entry in range-ops.cc for a WIDEN_PLUS_EXPR,  so ranger would 
only give back a VARYING for that no doubt.. however I doubt it would be 
too difficult to write the fold_range() method for it.

Its unclear to me what you mean by it doesnt work on patterns. so lets 
do some basics.

You have a stmt  "patt_27 = (_3) w+ (level_15(D));"

I gather thats a WIDEN_PLUS_EXPR, and if I read it right, patt_27 is a 
type that is twice as wide as _3, and will contain the value "_3 + 
level_15"?

You query above is asking for the range of _3 at this stmt in the IL.

And you are trying to determine whether the expression "_3 + level_15" 
would still fit in the type of _3, and thus you could avoid the WIDEN_* 
paradigm and revert to a simply plus?

And you also want to be able to do this for expressions which are not 
currently in the IL?

----  IF that is all true, then I would suggest one of 2 possible routes.
1) we add WIDEN_PLUS_EXPR to range-ops.  THIs involves writing 
fold_range() for it whereby it would create a range of a type double the 
precision of _3, then take the 2 ranges for op1 and op2, cast them to 
this new type and add them.

2) manually doing the same thing.   BUt if you are goignto manually do 
it, we might as well put that same code into fold_range then the entire 
ecosystem will benefit.

Once the operation can be performed in range ops, you can cast the new 
range back to the type of _3 and see if its fully represented. ie

int_range_max r1, r2
if (ranger.range_of_stmt (r1, stmt))
   {
     r2 = r1;
     r2.cast (TREE_TYPE (_3));
     r2.cast (TREE_TYPE (patt_27));
     if (r1 == r2)
       // No info was lost casting back and forth, so r1 must fit into 
type of _3

That should work for within the IL.  And if you want to do the same 
thing outside of the IL, you have to come up with the values you want to 
use for op1 and op2, replace the ranger query with a direct range-opfold:

range_op_handler handler (WIDEN_PLUS_EXPR, TREE_TYPE (patt_27));
if (handler && handler->fold_range (r1, range_of__3, range_of_level_15))
   {
     // same casting song and dance


If you dont want to go thru this process, in theory, you could try 
simply adding _3 and level_15 in their own precision, and if max/min 
aren't +INF/-INF then you can probably assume there is no overflow?
in which case, all you do is the path you are on above for within a stmt 
should work:

	  gimple_ranger ranger;
	  int_range_max r0, r1, def;
	  /* Check that no overflow will occur.  If we don't have range
	     information we can't perform the optimization.  */
	  if (ranger.range_of_expr (r0, oprnd0, stmt) && ranger.range_of_expr (r1,oprnd1, stmt)
	    {
	      range_op_handler handler (PLUS_EXPR, TREE_TYPE (_3));
	      if (handler && handler->fold_range (def, r0, r1))
		// examine def.upper_bound() and def.lower_bound()

Am I grasping some of the issue here?

Andrew