On Mon, Nov 9, 2020 at 1:26 PM Martin Liška <mli...@suse.cz> wrote: > > On 11/6/20 1:31 PM, Richard Biener wrote: > > On Fri, Oct 16, 2020 at 4:04 PM Martin Liška <mli...@suse.cz> wrote: > >> > >> Hello. > >> > >> There's another version of the patch that should be based on what > >> I discussed with Richi and Jakub: > >> > >> - the first patch introduces a new option -fbit-tests that analogue to > >> -fjump-tables > >> and will control the new if-to-switch conversion pass > >> > >> - the second patch adds the pass > >> - I share code with tree-ssa-reassoc.c (range_entry and init_range_entry) > >> - a local discovery phase is run first > >> - later than these local BBs are chained into a candidate list for the > >> conversion > >> > >> I'm also sending transformed chains for 'make all-host' (620 > >> transformations). > >> Patch can bootstrap on x86_64-linux-gnu and survives regression tests. > > > > -static bool > > +bool > > no_side_effect_bb (basic_block bb) > > { > > > > exporting this with this name is dangerous I think because the function > > seems to allow side-effects in the last stmt - not sure exactly what > > it tries to allow - there's no comment to that :/ > > All right, will fix that. > > > > > + free (rpo); > > + free_dominance_info (CDI_DOMINATORS); > > + > > + if (!all_candidates.is_empty ()) > > + mark_virtual_operands_for_renaming (fun); > > > > please avoid freeing dominance info when there was no change done > > (move it to the !all_candidates.is_empty () block). > > > > + basic_block bb; > > + FOR_EACH_BB_FN (bb, fun) > > + find_conditions (bb, &conditions_in_bbs); > > + > > > > if we didn't find any conditions (or found just one?) we can elide the > > rest of the function, no? > > Sure. > > > > > + if_chain *chain = new if_chain (); > > + chain->m_entries.safe_push (info); > > + /* Try to find a chain starting in this BB. */ > > + while (true) > > + { > > + if (!single_pred_p (gimple_bb (info->m_cond))) > > + break; > > + edge e = single_pred_edge (gimple_bb (info->m_cond)); > > + condition_info *info2 = conditions_in_bbs.get (e->src); > > + if (!info2 || info->m_ranges[0].exp != info2->m_ranges[0].exp) > > + break; > > + > > + chain->m_entries.safe_push (info2); > > + bitmap_set_bit (seen_bbs, e->src->index); > > + info = info2; > > + } > > > > so while we now record conditions per BB the above doesn't really > > allow matching a binary tree. > > Yes. The pass currently only supports conditions of the following form: > 1) index in {min, max} > 2) index out of {min, max} > > which means one edge in form 1). I don't see how can be useful handling > of a situation where both edges contain a such-chain? Can you please > come up with a test-case that can be interesting?
Sth like if (val < 10) { if (val == 1) ... else if (val == 2) ... else default; } else { if (val == 99) ... else if (val == 42) ... else gcc_unreachable (); } but the most trivial thing would be to feed the pass the balanced-tree generated by switch expansion where I would expect us to be able to detect it as the original switch again. > > What I was thinking of is to record > > if_chain * per BB as well and look at successors, thus (pseudo-code) > > > > if (block ends in cond) > > if (if_chain on true edge && if_chain on false edge) > > try merge > > else if (if_chain on true edge && this-cond tests same var) > > try merge > > else if (if_chan on false edge && ...) > > try merge > > record if_chain for block > > > > where merging would eventually detach the if_chains from the successors. > > For now we'd just handle the true (and maybe false) edge combos to handle > > linear chains. Walking reverse RPO (I'm not 100% sure reverse RPO is what > > we want here, but guess it will work fine for now) will gather chains > > accordingly. > > When merging from a successor to a BB fails we push the successor chain > > to the candidate list. > > > > +/* Algorithm of the pass runs in the following steps: > > + a) We walk basic blocks in DOMINATOR order so that we first reach > > + a first condition of a future switch. > > + b) We follow false edges of a if-else-chain and we record chain > > + of GIMPLE conditions. These blocks are only used for comparison > > + of a common SSA_NAME and we do not allow any side effect. > > + c) We remove all basic blocks (except first) of such chain and > > + GIMPLE switch replaces the condition in the first basic block. > > + d) We move all GIMPLE statements in the removed blocks into the > > + first one. */ > > > > the overall comment is now a bit out-of-date? > > > > Please remove the PHI mapping as I outlined in earlier review. > > > > The 0001-Add-fbit-tests-option.patch is OK for trunk. > > Installed to master. > > Martin > > > > > Thanks, > > Richard. > > > > > >> Thoughts? > >> Thanks, > >> Martin >