ifcvt cond_exec support rewrite

Maxim Kuvyrkov maxim@codesourcery.com
Sat Mar 3 01:00:00 GMT 2012


On 30/09/2011, at 1:11 AM, Bernd Schmidt wrote:
...
> 
> The following patch rewrites essentially all the cond_exec support in
> ifcvt; reviewing is probably easier if it's thought of as new code.

Kudos for improving if-conversion!

I reviewed this patch to the extent I know ifcvt.c, which is below your level of understanding.  The new implementation looks good to me, and my review mostly focuses on making the code more understandable to someone without the in-depth knowledge of optimization.

> A
> large overview comment is added to basic-block.h.

I suggest moving this comment to ifcvt.c as it really describes the optimization, not the underlying data structures.

Also, are there any publications describing the new implementation or is this your own masterpiece?  If there are papers relevant to your new implementation, please add references to them.

...
> 
> This patch was bootstrapped on ia64-linux; a slightly earlier version
> was regression tested and had a random guality failure that goes away
> with this one (gcc & g++ tested again). It's also been tested on c6x-elf
> along the way (currently testing again for the latest version and
> looking OK so far), and it's in our 4.5 c6x tree.

For which targets is this optimization enabled for (as in "is not a no-op")?  Is it only IA64, FRV and C6X?  [I think at least ARM should also be affected.]

If it's only ia64, frv and c6x, then you are in the clear with testing.  If the optimization can change code for other targets (arm, x86, ppc, mips), then we need to do more testing to make sure correctness and performance do not regress.  I'm ready to help with the testing and benchmarking.


> Index: gcc/ifcvt.c
> ===================================================================
> *** gcc/ifcvt.c	(revision 178854)
> --- gcc/ifcvt.c	(working copy)
...
> +   cond_exec_discard_added_insns ();
>     cancel_changes (0);
> !   return false;
> ! }
> ! 
> ! /* Given an IF-THEN or IF-THEN-ELSE block with possibly nested
> !    sub-blocks in CE_ROOT, attempt to convert as much of the tree as
> !    possible to conditional execution.  Return TRUE if we were
> !    successful at converting the block.  */
> ! 
> ! static int
> ! cond_exec_process_if_block (ce_if_block_t *ce_root)
> ! {
> !   bool retval = false;
> !   basic_block bb, prev_bb = NULL;
> !   ce_blocks_info_t *blkinfo;
> !   int n_blocks;
> !   unsigned i;
> !   HARD_REG_SET set_anywhere;
> ! 
> !   /* Verify that all blocks are adjacent.  This isn't really a
> !      requirement, but only because rtl_move_block is unimplemented.
> !      Later.  */

What does this 'Later' mean?

> !   FOR_EACH_VEC_ELT (basic_block, ce_root->targets, i, bb)
> !     {
> !       if (prev_bb && prev_bb->next_bb != bb)
> ! 	return false;
> ! 
> !       prev_bb = bb;
> !     }

...

> ! /* After finding an if header CE_INFO with discover_if_header, this function
> !    can be used to recursively examine the then, else, and join blocks to see
> !    if they are themselves if blocks.  OUTER_JOIN should be NULL for the
> !    outermost if-block we're examining; on recursive calls it holds the join_bb
> !    of the parent if-block.
> !    Return true if we found a recognizable blocks structure.  */
>   
> ! static bool
> ! ce_discover_if_structure (ce_if_block_t *ce_info, basic_block outer_join)

This is a HUGE function.  Please try splitting it up into several smaller functions or making (its structure || steps that it makes) more apparent in other ways.

...
> 
> !   /* Try to avoid building up extremely large if trees only to find that
> !      they would be too expensive to convert.  The numbers are arbitrarily
> !      chosen to ensure reasonable compile times for extreme test cases without
> !      preventing useful optimizations.  */
> !   if (n_basic_blocks > 100
> !       /* Avoid the special case from above.  */
> !       && (then_bb == NULL || EDGE_COUNT (then_bb->succs) > 0))
> !     {
> !       VEC (basic_block, heap) *dom_vec;
> !       basic_block bb;
> !       int count = 0;
> !       dom_vec = get_dominated_to_depth (CDI_DOMINATORS, test_bb, 0);
> !       FOR_EACH_VEC_ELT (basic_block, dom_vec, i, bb)
> ! 	if (dominated_by_p (CDI_POST_DOMINATORS, bb, join_bb))
> ! 	  count++;
> !       VEC_free (basic_block, heap, dom_vec);
> !       if (count > 40)
> ! 	return false;
> !     }

Please replace the magic numbers '100' and '40' above with parameters or, at least, constants with descriptive names.  

...
> 
> !   if (sub_info != NULL && sub_info->join_bb == join_bb
> !       /* We cannot do this if we have matching pieces of code, as these must be
> ! 	 predicated with the parent's condition (which, hence, must be in a
> ! 	 different register).  */

"We cannot do this ... " -- what "this" refers to?

...

> Index: gcc/basic-block.h
> ===================================================================
> *** gcc/basic-block.h	(revision 178854)
> --- gcc/basic-block.h	(working copy)

  The placement of data structure definitions to basic-block.h seems historic, and, I think, it would be better to move them to a new stand-alone header ifcvt.h.  I didn't see anything among ifcvt definitions in basic-block.h that has to be intertwined with the rest of the header.

...

> +    === Conversion
> + 
> +    In order to convert such a structure to conditional execution, we work from
> +    the leaves (then or else blocks which are not themselves tests) upwards
> +    through the tree, assigning registers for the conditions, verifying costs,
> +    etc.

References to specific routines where we do the above core steps of algorithm (the upward walk, register assignment, etc.) would be very helpful here for someone trying to understand the implementation.  Similarly, code references in other parts of this and other comment would be greatly appreciated.


>  Ideally we can convert the entire structure, but in complicated cases
> +    it's more likely that We end up with a forest of convertible sub-trees.

s/We/we.

Thank you,

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics






More information about the Gcc-patches mailing list