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

[Richard Biener]

On Fri, Oct 2, 2020 at 3:23 PM Martin Liška <mliska@suse.cz> wrote:
>
> On 9/24/20 2:41 PM, Richard Biener wrote:
> > On Wed, Sep 2, 2020 at 1:53 PM Martin Liška <mliska@suse.cz> wrote:
> >>
> >> On 9/1/20 4:50 PM, David Malcolm wrote:
> >>> Hope this is constructive
> >>> Dave
> >>
> >> Thank you David. All of them very very useful!
> >>
> >> There's updated version of the patch.
> >
> > I noticed several functions without a function-level comment.
> >
> > -  cluster (tree case_label_expr, basic_block case_bb, profile_probability prob,
> > -          profile_probability subtree_prob);
> > +  inline cluster (tree case_label_expr, basic_block case_bb,
> > +                 profile_probability prob, profile_probability subtree_prob);
> >
> > I thought we generally leave this to the compiler ...
>
> Hey.
>
> This one is needed, otherwise we'll have a compilation error (multiple definitions).
>
> >
> > +@item -fconvert-if-to-switch
> > +@opindex fconvert-if-to-switch
> > +Perform conversion of an if cascade into a switch statement.
> > +Do so if the switch can be later transformed using a jump table
> > +or a bit test.  The transformation can help to produce faster code for
> > +the switch statement.  This flag is enabled by default
> > +at @option{-O2} and higher.
> >
> > this mentions we do this only when we later can convert the
> > switch again but both passes (we still have two :/) have
> > independent guards.
>
> All right, I'm planning to come up with -fbit-tests options and this transformation
> will happen only if BT or JT are enabled.
>
> >
> > +  /* For now, just wipe the dominator information.  */
> > +  free_dominance_info (CDI_DOMINATORS);
> >
> > could at least be conditional on the vop renaming condition...
>
> How do you mean this?

don't free dominators if you didn't change anything.

> >
> > +  if (!all_candidates.is_empty ())
> > +    mark_virtual_operands_for_renaming (fun);
> >
> > +      if (bitmap_bit_p (*visited_bbs, bb->index))
> > +       break;
> > +      bitmap_set_bit (*visited_bbs, bb->index);
> >
> > since you are using a bitmap and not a sbitmap (why?)
> > you can combine those into
>
> Yes, sbitmap would be better.
>
> >
> >     if (!bitmap_set_bit (*visited_bbs, bb->index))
> >      break;
>
> Unfortunately, bitmap_set_bit for sbitmap is a void return function.
> Should I change it?

No, with sbitmaps you have to keep your current code.

> >
> > +      /* Current we support following patterns (situations):
> > +
> > +        1) if condition with equal operation:
> > +
> > ...
> >
> > did you see whether using
> >
> >     register_edge_assert_for (lhs, true_edge, code, lhs, rhs, asserts);
> >
> > works equally well?  It fills the 'asserts' vector with relations
> > derived from 'lhs'.  There's also
> > vr_values::extract_range_for_var_from_comparison_expr
> > to compute the case_range
> >
> > +      /* If it's not the first condition, then we need a BB without
> > +        any statements.  */
> > +      if (!first)
> > +       {
> > +         unsigned stmt_count = 0;
> > +         for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
> > +              !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
> > +           ++stmt_count;
> > +
> > +         if (stmt_count - visited_stmt_count != 0)
> > +           break;
> >
> > hmm, OK, this might be a bit iffy to get correct then, still it's a lot
> > of pattern maching code that is there elsewhere already.
> > ifcombine simply hoists any stmts without side-effects up the
> > dominator tree and thus only requires BBs without side-effects
> > (IIRC there's a predicate fn for that).
> >
> > +      /* Prevent loosing information for a PHI node where 2 edges will
> > +        be folded into one.  Note that we must do the same also for false_edge
> > +        (for last BB in a if-elseif chain).  */
> > +      if (!chain->record_phi_arguments (true_edge)
> > +         || !chain->record_phi_arguments (false_edge))
> >
> > I don't really get this - looking at record_phi_arguments it seems
> > we're requiring that all edges into the same PHI from inside the case
> > (irrespective of from which case label) have the same value for the
> > PHI arg?
> >
> > +             if (arg != *v)
> > +               return false;
>
> This one is really needed for situations like:
>
> cat wchar.i
> int i;
>
> int
> pg_utf_mblen() {
>    int len;
>    if (i == 4)
>      len = 3;
>    else if (i == 2)
>      len = 4;
>    else if (i == 6)
>      len = 1;
>    return len;
> }
>
> where we end up just with one edge from switch BB to a destination BB where
> we have the PHI:
>    # len_4 = PHI <3(2), 4(3), len_6(D)(4), 1(5)>

Yeah, see my comment on how to deal with this in code generation
(introduce a forwarder block).

> >
> > should use operand_equal_p at least, REAL_CSTs are for example
> > not shared tree nodes.  I'll also notice that if record_phi_arguments
> > fails we still may have altered its hash-map even though the particular
> > edge will not participate in the current chain, so it will affect other
> > chains ending in the same BB.  Overall this looks a bit too conservative
> > (and random, based on visiting order).
>
> No, the m_phi_map is destroyed when we call 'delete chain'.
>
> >
> > +    expanded_location loc
> > +    = expand_location (gimple_location (chain->m_first_condition));
> > +      if (dump_file)
> > +       {
> > +         fprintf (dump_file, "Condition chain (at %s:%d) with %d conditions "
> > +                  "(%d BBs) transformed into a switch statement.\n",
> > +                  loc.file, loc.line, total_case_values,
> > +                  chain->m_entries.length ());
> >
> > Use dump_printf_loc and you can pass a gimple * stmt as location.
>
> Good idea.
>
> >
> > +      /* Follow if-elseif-elseif chain.  */
> > +      bb = false_edge->dest;
> >
> > so that means the code doesn't handle a tree, right?  But what
> > makes us sure the chain doesn't continue on the true_edge instead,
> > guess this degenerate tree isn't handled either.
>
> Well, I was thinking about this one more time. I would like to see
> a first version that will handle the simple chains that are trivial
> switch statements:
>
> if (x == 1)
> else if (x ..)
> ...
>
> that was my original motivation and it has quite nice coverage.
> Later we can support code hoisting and negative expressions
> like x != 123. Hopefully the upcoming Ranger infrastructure can help
> us here. Is it acceptable approach for upcoming GCC 11?

But is it really extensible with the current implementation?  I doubt so.

Richard.

> Martin
>
> >
> > I was thinking on whether doing the switch discovery in a reverse
> > CFG walk, recording for each BB what case_range(s) it represents
> > for a particular variable(s) so when visiting a dominator you
> > can quickly figure what's the relevant children (true, false or both).
> > It would also make the matching a BB-local operation where you'd
> > do the case_label discovery based on the single-pred BBs gimple-cond.
> >
> > +  output = bit_test_cluster::find_bit_tests (filtered_clusters);
> > +  r = output.length () < filtered_clusters.length ();
> > +  if (r)
> > +    dump_clusters (&output, "BT can be built");
> >
> > so as of the very above comment - this might be guarded with
> > flag_tree_switch_conversion?
> >
> > As mentioned previously I would have liked to see if-to-switch
> > integrated with switch-conversion, having separate passes is
> > somewhat awkward (for example the redundant and possibly
> > expensive find_bit_tests).
> >
> > +         /* Move all statements from the BB to the BB with gswitch.  */
> > +         auto_vec<gimple *> stmts;
> > +         for (gimple_stmt_iterator gsi = gsi_start_bb (entry.m_bb);
> > +              !gsi_end_p (gsi); gsi_next (&gsi))
> > +           {
> > +             gimple *stmt = gsi_stmt (gsi);
> > +             if (gimple_code (stmt) != GIMPLE_COND)
> > +               stmts.safe_push (stmt);
> > +           }
> > +
> > +         for (unsigned i = 0; i < stmts.length (); i++)
> > +           {
> > +             gimple_stmt_iterator gsi_from = gsi_for_stmt (stmts[i]);
> > +             gsi_move_before (&gsi_from, &gsi);
> > +           }
> >
> > so you are already hoisting all stmts ...
> >
> > +      make_edge (first_cond.m_bb, case_bb, 0);
> >
> > and if this doesn't create a new edge you need equivalent PHI
> > args in the case_bb.  To remove this restriction you "only"
> > have to add a forwarder.  Sth like
> >
> >     edge e = make_edge (...);
> >     if (!e)
> >       {
> >          bb = create_basic_block ();
> >          make_edge (first_cond.m_bb, bb, 0);
> >          e = make_edge (bb, case_bb, 0);
> >       }
> >    fill PHI arg of 'e' from original value (no need to create the hash-map then)
> >
> > Richard.
> >
> >
> >> Martin
>