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.
Hey.
What a juicy patch review!
I noticed several functions without a function-level comment.
Yep, but several of them are documented in a class declaration. Anyway, I will
improve for the next time.
- 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 ...
+@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.
Yes, we have the option for jump tables (-jump-tables), but we miss one for a
bit-test.
Moreover, as mentioned in the cover email, one can see it beneficial to convert
a if-chain
to switch as the expansion (without any BT and JT) can benefit from balanced
tree.
+ /* For now, just wipe the dominator information. */
+ free_dominance_info (CDI_DOMINATORS);
could at least be conditional on the vop renaming condition...
+ if (!all_candidates.is_empty ())
+ mark_virtual_operands_for_renaming (fun);
Yep.
+ 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
New to me, thanks.
if (!bitmap_set_bit (*visited_bbs, bb->index))
break;
+ /* 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
Good point! I must admit that my patch doesn't properly handle negative
conditions:
if (argc != 11111)
{
if (argc == 1)
global = 222;
...
}
which can VRP correctly identify as anti-range:
int ~[11111, 11111] EQUIVALENCES: { argc_8(D) } (1 elements)$1 = void
I have question about OR and AND conditions:
<bb 2> :
_1 = aChar_8(D) == 1;
_2 = aChar_8(D) == 10;
_3 = _1 | _2;
if (_3 != 0)
goto <bb 6>; [INV]
else
goto <bb 3>; [INV]
<bb 2> :
_1 = aChar_8(D) != 1;
_2 = aChar_8(D) != 10;
_3 = _1 & _2;
if (_3 != 0)
goto <bb 6>; [INV]
else
goto <bb 3>; [INV]
Can I somehow get that from VRP (as I ask register_edge_assert_for only for LHS
of a condition)?
+ /* 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).
Yes, I completely miss support for code hoisting (expect first BB where we put
gswitch).
If I'm correct hoisting should be possible where case destination should be a
new BB
that will contain original statements and then it will jump to a case
destination block.
+ /* 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?
I guess so, I'll refresh the functionality.
+ if (arg != *v)
+ return false;
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).
Oh, yes, it's not properly cleared once we bail out for a particular 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.
+ /* 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.
As mentioned earlier, I didn't consider VAR != CST type of conditions that
makes it more complicated.
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).
Sounds promising. Note that right now we do not support overlapping cases like:
if (5 <= argc && argc <= 10)
foo ();
else if (6 <= argc && argc <= 100)
foo ();
So I'm wondering if we can support 2 children?
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.
Can you please describe more how will the walk work?
+ 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?
flag_tree_switch_conversion isn't connected to the if-chain pass (yet).
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).
Well, the CFG transformation for BT and JT is not trivial and I would like
to go in the first iteration through gswitch statements.
I have a massive speed up for the find_bit_tests/find_jump_tables.
+ /* 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 ...
As mentioned, it's not supported right now. This moves all these kind of "temp"
statements:
_1 = aChar_8(D) == 1;
_2 = aChar_8(D) == 10;
_3 = _1 | _2;
Martin
+ 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
