[PATCH] Add if-chain to switch conversion pass.

[Andrew MacLeod]

On 10/12/20 8:39 AM, Martin Liška wrote:
> On 10/6/20 4:12 PM, Jakub Jelinek wrote:
>> On Tue, Oct 06, 2020 at 03:48:38PM +0200, Martin Liška wrote:
>>> On 10/6/20 9:47 AM, Richard Biener wrote:
>>>> But is it really extensible with the current implementation?  I 
>>>> doubt so.
>>>
>>> I must agree with the statement. So let's make the pass properly.
>>> I would need a help with the algorithm where I'm planning to do the 
>>> following
>>> steps:
>>>
>>> 1) for each BB ending with a gcond, parse index variable and it's VR;
>>>     I'll support:
>>>     a) index == 123 ([123, 123])
>>>     b) 1 <= index && index <= 9 ([1, 9])
>>>     c) index == 123 || index == 12345 ([123, 123] [12345, 12345])
>>>     d) index != 1 ([1, 1])
>>>     e) index != 1 && index != 5 ([1, 1] [5, 5])
>>
>> The fold_range_test created cases are essential to support, so
>> f) index - 123U < 456U ([123, 456+123])
>> g) (unsigned) index - 123U < 456U (ditto)
>> but the discovery should actually recurse on all of those forms, so 
>> it will
>> handle
>> (unsigned) index - 123U < 456U || (unsigned) index - 16384U <= 32711U
>> etc.
>> You can see what reassoc init_range_entry does and do something similar?
>
> All right, I started to use init_range_entry in combination with 
> linearize_expr_tree.
> One thing I have problem with is that linearize_expr_tree doesn't 
> properly mark
> all statements as visited for cases like:
>
>   <bb 4> :
>   index2.1_1 = (unsigned int) index2_16(D);
>   _2 = index2.1_1 + 4294967196;
>   _3 = _2 <= 100;
>   _5 = index2.1_1 + 4294966996;
>   _6 = _5 <= 33;
>   _7 = _3 | _6;
>   if (_7 != 0)
>     goto <bb 5>; [INV]
>   else
>     goto <bb 6>; [INV]
>
> As seen, all statements in this BB are used by the final _7 != 0 and 
> it would
> be handy for me to identify all statements that should be hoisted.

The ranger infrastructure includes definition chains for what can 
potentially have a range calculated on an outgoing edge.  It contains 
all the ssa-names defined in the block for which we have range-ops 
entries that allow us to potentially wind back thru a calculation.   ie, 
any name which is defined in the block whose value can be changed based 
on which edge is taken...


I created:

foo (int index)
{
  if (index - 123U < 456U || index - 16384U <= 32711U )
     foo (42);
}

the exports range list contains
  =========== BB 2 ============
index_9(D)      int VARYING
     <bb 2> :
     index.0_1 = (unsigned int) index_9(D);
     _2 = index.0_1 + 4294967173;
     _3 = _2 <= 455;
     _5 = index.0_1 + 4294950912;
     _6 = _5 <= 32711;
     _7 = _3 | _6;
     if (_7 != 0)
       goto <bb 3>; [INV]
     else
       goto <bb 4>; [INV]

2->3  (T) index.0_1 :   unsigned int [123, 578][16384, 49095]
2->3  (T) _7 :  _Bool [1, 1]
2->3  (T) index_9(D) :  int [123, 578][16384, 49095]
2->4  (F) index.0_1 :   unsigned int [0, 122][579, 16383][49096, +INF]
2->4  (F) _2 :  unsigned int [456, +INF]
2->4  (F) _3 :  _Bool [0, 0]
2->4  (F) _5 :  unsigned int [32712, +INF]
2->4  (F) _6 :  _Bool [0, 0]
2->4  (F) _7 :  _Bool [0, 0]
2->4  (F) index_9(D) :  int [-INF, 122][579, 16383][49096, +INF]

and importantly, the defchain structure which lists names which are used 
to define this name  looks like:

DUMPING GORI MAP
bb2    index.0_1 : index_9(D)
        _2 : index.0_1  index_9(D)
        _3 : index.0_1  _2  index_9(D)
        _5 : index.0_1  index_9(D)
        _6 : index.0_1  _5  index_9(D)
        _7 : index.0_1  _2  _3  _5  _6  index_9(D)
        exports: index.0_1  _2  _3  _5  _6  _7  index_9(D)


This indicates that if you are using _7 as the control name of the branch,

_7 : index.0_1  _2  _3  _5  _6  index_9(D)

is the list of names that _7 uses in its definition chain...and we can 
calculate ranges for.      index_9 is not defined in this BB, so it is 
considered an import.  you'd probably be looking for all the names in 
this list whose SSA_NAME_DEF_STMT is in this block.. That looks a lot 
like the list of statements you want to hoist.

Caveats are that
   1)  this is currently only used internally by the ranger, so there 
are some  minor warts that may currently limit its usefulness elsewhere
   2) its is limited to only processing statements for which we have 
range-ops understanding.    which means we know how to calculate ranges 
for the statement.  Perhaps this is also not an issue since if there are 
statements we cant generate a range for, perhaps you dont care.

This might be more ionfo than  you need, but also

   3) before the enxt stage 1 I plan to rework the GORI component, and I 
plan to split this into additional "parts"  in particualr, this entire 
export list will still exist, but there will be 3 subcomponents which 
form it:
        a)  control names :   These are booleans which contribute to the 
TRUE/FALSEness of the edge
        b) direct exports  : These are ssanames which are directly 
affected by relations on the edge.. Ie, the edge gives them a range
        c) calculable exports  : These are other ssa_names which can be 
calculated based on the direct exports. Ie, the direct export is used in 
calculating this value
for the above block,
   control names :  _7, _6 and _3
   direct exports : _5 and _2
   calculable exports : index.0_1 index_9(D)


I bring it up because as IM reworking those bits, we can take into 
account other requirements that might be needed that can make it useful 
other places. And by anaylzing the names that are common between any 
direct exports, you may find useful information.

Currently, the exports list is not exported from the ranger, nor is the 
gori map,  but that would be trivial to do.   You basically get a bitmap 
back..

The classes are not dependant on the ranger either, so you can roll your 
own if you wanted to experiment.  Since they are internal  they are 
currently located in  gimple-range-gori.cc.. its basically the gori_map 
class which tracks all this and uses the range_def_chain class to manage 
the definition chains.  I threw a number fo comments in there already.   
Its lazily evaluated as queries are made.

If you think there is something useful, we can move those classes into 
the gimple-range-gori.h header file and adjust the APIs as needed.




>
> Thoughts how can I achieve that?
> Thanks,
> Martin
>