Re: [PATCH] Loop unswitching: support gswitch statements.

[Andrew MacLeod <amacleod@redhat.com>]

On 9/28/21 7:50 AM, Richard Biener wrote:
> On Wed, Sep 15, 2021 at 10:46 AM Martin Liška <mliska@suse.cz> wrote:
>>    /* Unswitch single LOOP.  NUM is number of unswitchings done; we do not allow
>> @@ -269,6 +311,7 @@ tree_unswitch_single_loop (class loop *loop, int num)
>>      class loop *nloop;
>>      unsigned i, found;
>>      tree cond = NULL_TREE;
>> +  edge cond_edge = NULL;
>>      gimple *stmt;
>>      bool changed = false;
>>      HOST_WIDE_INT iterations;
>> @@ -311,11 +354,12 @@ tree_unswitch_single_loop (class loop *loop, int num)
>>      bbs = get_loop_body (loop);
>>      found = loop->num_nodes;
>>
>> +  gimple_ranger ranger;
> ISTR constructing/destructing ranger has a non-negligible overhead -
> is it possible
> to keep it live for a longer time (note we're heavily modifying the CFG)?


There is some overhead.. right now we determine all the imports and 
exports for each block ahead of time, but thats about it. We can make 
adjustments for true on demand clients like this so that even that 
doesnt happen. we only do that so we know ahead of time which ssa-names 
are never used in outgoing edges, and never even have to check those.  
Thats mostly an optimization for heavy users like EVRP.  If you want, I 
can make that an option  so there virtually no overhead

More importantly, the longer it remains alive, the more "reuse" of 
ranges you will get..   If there is not a pattern of using variables 
from earlier in the program it wouldnt really matter much.

In Theory, modifying the IL should be fine, it happens already in 
places, but its not extensively tested under those conditions yet.

>>      while (1)
>>        {
>>          /* Find a bb to unswitch on.  */
>>          for (; i < loop->num_nodes; i++)
>> -       if ((cond = tree_may_unswitch_on (bbs[i], loop)))
>> +       if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge)))
>>            break;
>>
>>          if (i == loop->num_nodes)
>> @@ -333,24 +377,70 @@ tree_unswitch_single_loop (class loop *loop, int num)
>>            break;
>>          }
>>
>> -      cond = simplify_using_entry_checks (loop, cond);
> I also fear we're losing simplification of unswitching on float compares or even
> run into endlessly unswitching on the same condition?
Ranger will only do integra/pointer stuff right now.  floats are on the 
list for GCC13, fwiw.
>
> In the testcases I failed to see some verifying we're _not_ repeatedly
> processing
> ifs, like scan for a definitive number of unswitchings for, say,
>
>    for (..)
>      {
>           if (a)
>            ...;
>           xyz;
>           if (a)
>             ...;
>      }
>
> where we want to unswitch on if (a) only once (but of course simplify the second
> if (a) ideally from within unswitching so CFG cleanup removes the dead paths).
> The old code guaranteed this even for float compares IIRC.
>
> At least also add scan-tree-dump-times overall expected unswitch count scans
> to the new testcases.
>
> Btw, I was hoping to use the relation stuff here, not so much use range
> queries, but see below ...
I seem to recall a discussion about using predication and how thats 
really what we want here?  . I had some thoughts on a predication engine 
we could add utilizing the relations oracle, but haven't had a time to 
look into it yet
>
>>          stmt = last_stmt (bbs[i]);
>> -      if (integer_nonzerop (cond))
>> +      gcond *condition = dyn_cast<gcond *> (stmt);
>> +      gswitch *swtch = dyn_cast<gswitch *> (stmt);
>> +
>> +      if (condition != NULL)
>>          {
>> -         /* Remove false path.  */
>> -         gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
>> -                                              boolean_true_node);
>> -         changed = true;
>> +         int_range_max r;
>> +         edge edge_true, edge_false;
>> +         extract_true_false_edges_from_block (bbs[i], &edge_true, &edge_false);
>> +         tree cond = gimple_cond_lhs (stmt);
>> +
>> +         if (r.supports_type_p (TREE_TYPE (cond)))
>> +           {
>> +             if (ranger.range_on_edge (r, edge_true, cond)
>> +                 && r.undefined_p ())
> Can you really use ranger this way to tell whether the edge is not executed?
> I think you instead want to somehow evaluate the gcond or gswitch, looking
> for a known taken edge?

Yes and no  :-)  I use to do that, but now that we allow uninitialized 
values to be treated as UNDEFINED,  it may also mean that its 
uninitialized on that edge.

Evaluating
if (c_3 == 0)       when we know c_3 = [1,1]

What you suggest is fundamentally what ranger does... It evaluates what 
the full set of possible ranges are on the edge you ask about, then 
intersects it with the known range of c_3.  .   If the condition cannot 
ever be true,and is thus unexecutable,  the result will be UNDEFINED .  
ie above,  c_3 would have to have a range of [0,0] on the true edge, and 
its real range is [1,1].. intersecting the 2 values results in UNDEFINED...

So it can mean the edge is unexecutable.   It can also mean the value is 
actually undefined.. if this was a use-before-def case, the range of c_3 
in the block would be UNDEFINED.  and c_3 will be UNDEFINED on BOTH 
edges due ot the intersection.  the UNDEFINED state is viral.

I guess you can argue you can arbitrarily choose an edge to process in 
this case, but if you want to avoid that situation completely, I think 
you could also check that cond is not UNDEFINED  in the stmt first.. 
then if you get UNDEFINED on and edge you are 100% sure its 
unexectuable.. ie

+
+         if (ranger.range_of_expr (r, cond, stmt) && !r.undefined_p ())
+           {
+             if (ranger.range_on_edge (r, edge_true, cond) && r.undefined_p ())

Note the call to range_of_expr () will do the supported_type check 
anyway and return false if it isnt supported.


>> +               {
>> +/* Remove all dead cases from switches that are unswitched.  */
>> +
>> +static void
>> +clean_up_switches (void)
>> +{
>> +  basic_block bb;
>> +
>> +  FOR_EACH_BB_FN (bb, cfun)
>> +    {
>> +      gimple *last = last_stmt (bb);
>> +      if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
>> +       {
>> +         unsigned nlabels = gimple_switch_num_labels (stmt);
>> +         unsigned index = 1;
>> +         for (unsigned i = 1; i < nlabels; ++i)
>> +           {
>> +             tree lab = gimple_switch_label (stmt, i);
>> +             basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
>> +             edge e = find_edge (gimple_bb (stmt), dest);
>> +             if (e == NULL)
>> +               ; /* The edge is already removed.  */
>> +             else if (e->flags & EDGE_IGNORE)
> btw, a bit better would be to use a pass-local edge flag via
>
>    auto_edge_flag edge_unswitched (cfun);
>
> and use that.  EDGE_IGNORED seems to be unused and should
> probably be removed.
side note.. I love that auto_edge_flag thing :-)  Thanks again for 
pointing it out.

Andrew