On Fri, Oct 2, 2020 at 3:23 PM Martin Liška <mli...@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 <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?
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 >