[PATCH] Loop unswitching: support gswitch statements.

[Andrew MacLeod]

On 1/6/22 11:02, Martin Liška wrote:
> On 1/6/22 16:11, Andrew MacLeod wrote:
>> On 1/5/22 07:34, Richard Biener wrote:
>>> On Thu, Dec 9, 2021 at 2:02 PM Martin Liška <mliska@suse.cz> wrote:
>>>> On 11/30/21 12:17, Richard Biener wrote:
>>>>
>>> +                 unswitch_predicate *predicate
>>> +                   = new unswitch_predicate (expr, idx, edge_index);
>>> +                 ranger->gori ().outgoing_edge_range_p
>>> (predicate->true_range, e,
>>> +                                                        idx,
>>> *get_global_range_query ());
>>> +                 /* Huge switches are not supported by Ranger.  */
>>> +                 if (predicate->true_range.undefined_p ())
>>>
>>> I hope ranger will set the range to varying_p () in that case, not
>>> undefined?  But even
>>> then, is that a reason for punting?  I guess we fail to prune cases in
>>> that case but
>>> the cost modeling should then account for those and thus we are at
>>> least consistent?
>>
>> huge switches not supported?  I don't know what you mean, either that 
>> or I forget :-)  If there are more edges than multi-ranges support, 
>> then things will start getting merged because they cant be 
>> represented.. and the default case may then also contain some values 
>> that also have cases..  but all inconsistencies will move towards 
>> varying.. not undefined.
>>
>> Andrew
>>
>
> Hello.
>
> If you consider the attached test-case, then I get for:
>
> (gdb) p debug_bb(e->src)
> <bb 4> [local count: 955630225]:
> # i_489 = PHI <i_485(99), 0(98)>
> # tmp_490 = PHI <tmp_379(99), tmp_382(D)(98)>
> _1329 = (long unsigned int) i_489;
> _1330 = _1329 * 8;
> switch (order_385(D)) <default: <L94> [1.08%], case 0: <L1> [1.08%], 
> case 1: <L2> [1.08%], case 2: <L3> [1.08%], case 3: <L4> [1.08%], case 
> 4: <L5> [1.08%], case 5: <L6> [1.08%], case 6: <L7> [1.08%], case 7: 
> <L8> [1.08%], case 8: <L9> [1.08%], case 9: <L10> [1.08%], case 10: 
> <L11> [1.08%], case 11: <L12> [1.08%], case 12: <L13> [1.08%], case 
> 13: <L14> [1.08%], case 14: <L15> [1.08%], case 15: <L16> [1.08%], 
> case 16: <L17> [1.08%], case 17: <L18> [1.08%], case 18: <L19> 
> [1.08%], case 19: <L20> [1.08%], case 20: <L21> [1.08%], case 21: 
> <L22> [1.08%], case 22: <L23> [1.08%], case 23: <L24> [1.08%], case 
> 24: <L25> [1.08%], case 25: <L26> [1.08%], case 26: <L27> [1.08%], 
> case 27: <L28> [1.08%], case 28: <L29> [1.08%], case 29: <L30> 
> [1.08%], case 30: <L31> [1.08%], case 31: <L32> [1.08%], case 32: 
> <L33> [1.08%], case 33: <L34> [1.08%], case 34: <L35> [1.08%], case 
> 35: <L36> [1.08%], case 36: <L37> [1.08%], case 37: <L38> [1.08%], 
> case 38: <L39> [1.08%], case 39: <L40> [1.08%], case 40: <L41> 
> [1.08%], case 41: <L42> [1.08%], case 42: <L43> [1.08%], case 43: 
> <L44> [1.08%], case 44: <L45> [1.08%], case 45: <L46> [1.08%], case 
> 46: <L47> [1.08%], case 47: <L48> [1.08%], case 48: <L49> [1.08%], 
> case 49: <L50> [1.08%], case 50: <L51> [1.08%], case 51: <L52> 
> [1.08%], case 52: <L53> [1.08%], case 53: <L54> [1.08%], case 54: 
> <L55> [1.08%], case 55: <L56> [1.08%], case 56: <L57> [1.08%], case 
> 57: <L58> [1.08%], case 58: <L59> [1.08%], case 59: <L60> [1.08%], 
> case 60: <L61> [1.08%], case 61: <L62> [1.08%], case 62: <L63> 
> [1.08%], case 63: <L64> [1.08%], case 64: <L65> [1.08%], case 65: 
> <L66> [1.08%], case 66: <L67> [1.08%], case 67: <L68> [1.08%], case 
> 68: <L69> [1.08%], case 69: <L70> [1.08%], case 70: <L71> [1.08%], 
> case 71: <L72> [1.08%], case 72: <L73> [1.08%], case 73: <L74> 
> [1.08%], case 74: <L75> [1.08%], case 75: <L76> [1.08%], case 76: 
> <L77> [1.08%], case 77: <L78> [1.08%], case 78: <L79> [1.08%], case 
> 79: <L80> [1.08%], case 80: <L81> [1.08%], case 81: <L82> [1.08%], 
> case 82: <L83> [1.08%], case 83: <L84> [1.08%], case 84: <L85> 
> [1.08%], case 85: <L86> [1.08%], case 86: <L87> [1.08%], case 87: 
> <L88> [1.08%], case 88: <L89> [1.08%], case 89: <L90> [1.08%], case 
> 90: <L91> [1.08%], case 91: <L92> [1.08%]>
>
> $7 = void
> (gdb) p debug_bb(e->dest)
> <bb 5> [local count: 10275591]:
> <L1>:
> _3 = a_386(D) + _1330;
> _4 = *_3;
> tmp_478 = _4 * 0.0;
> goto <bb 97>; [100.00%]
>
> │      480                    ranger->gori ().outgoing_edge_range_p 
> (predicate->true_range, e,
> │ 481                                                           idx, 
> *get_global_range_query ());
>
> Note the return value is false. But I think the comment is not precise:


So if you get a FALSE back, you cannot use any results because GORI is 
claiming that it cant figure something out... or there is nothing to 
figure out.   Most of rangers routines are implemented so that if they 
return FALSE, the result is meaningless.


what is IDX you are passing?  order_385?

As a side note, theres a typo in the testcase:  .. Im not sure how that 
affects things, but :

    defaut:
             __builtin_unreachable ();


default is misspelled...  maybe it thinks that some kind of runtime 
value?   I am surprised it even compiles.  maybe that is mucking up what 
GORI thiunks it can calculate?



>
> │     1233  // Calculate a range on edge E and return it in R. Try to 
> evaluate a
> │     1234  // range for NAME on this edge.  Return FALSE if this is 
> either not a
> │     1235  // control edge or NAME is not defined by this edge.
>
> and
>
> (gdb) p predicate->true_range.debug()
> UNDEFINED
>
> So is the behavior correct Andrew?
> Thanks,
> Martin
>