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?

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

Reply via email to