On 9/24/20 2:41 PM, Richard Biener wrote:
On Wed, Sep 2, 2020 at 1:53 PM Martin Liška <mli...@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?
+ 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?
+ /* 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)>
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?
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
