Repost: RFA [4.1]: improvement to if-conversion and cross-jumping (PR20070)

[Steven Bosscher]

On Tuesday 12 July 2005 14:24, Joern RENNECKE wrote:
> 2005-07-12  J"orn Rennecke <joern.rennecke@st.com>
>
>         PR rtl-optimization/20070
>         * basic-block.h (STRUCT_EQUIV_START, STRUCT_EQUIV_RERUN): Define.
>         (STRUCT_EQUIV_FINAL, STRUCT_EQUIV_MAX_LOCAL): Likewise.
>         (struct struct_equiv_checkpoint, struct equiv_info): Likewise.
>         (struct_equiv_block_eq): Declare.
>         * cfgcleanup.c (reload.h, expr.h): #include.
>         (IMPOSSIBLE_MOVE_FACTOR): Define.
>         (flow_find_cross_jump): Remove.
>         (assign_reg_reg_set, struct_equiv, struct_equiv_set): New functions.
>         (struct_equiv_dst_mem, struct_equiv_make_checkpoint): Likewise. 
>         (struct_equiv_improve_checkpoint): Likewise.
>         (struct_equiv_restore_checkpoint, struct_equiv_death): Likewise.
>         (struct_equiv_block_eq): Likewise.
>         (find_dying_inputs, resolve_input_conflict): Likewise.
>         (try_crossjump_to_edge): Use struct_equiv_block_eq instead of
>         flow_find_cross_jump.
>         * ifcvt.c (noce_try_complex_cmove): New function.
>         (noce_process_if_block): Call it.
>         For flag_expensive_optimizations, update cond_exec_changed_p on
>         success.
>         (rest_of_handle_if_conversion): For flag_expensive_optimizations,
>         provide if_convert with register lifeness info.

Hi Joern,

If I understand your patch correctly, it makes cross-jumping and one
special if-conversion case consider semantically equivalent blocks,
instead of requiring the blocks to be completely equal.  Sounds like
a useful idea.

I have a few comments on / questions about the patch.

First of all, this entire code to match the blocks does IMVHO not
belong in basic-block.h and cfgcleanup.c, but in a separate file. 
The code could be useful in a bunch of places outside cfgcleanupc,
as you show yourself by using it in ifcvt.c.


You have this huge comment before "struct equiv_info".  Maybe you
can move the comments about the individual fields into the struct
definition, like we do elsewhere.  E.g.

+struct equiv_info
+{
+  /* Two block being compared.  */
+  basic_block x_block, y_block;
(..>)
+}

instead of the comment before the struct definition.


Why not write this in a human-readable form with ifs and elses? ;-)
+	return ((rvalue < 0
+		 ? ((dst_code != STRICT_LOW_PART
+		     && dst_code != ZERO_EXTEND
+		     && dst_code != SIGN_EXTEND)
+		    ? struct_equiv_dst_mem (SET_DEST (x), SET_DEST (y), info)
+		    : struct_equiv (&SET_DEST (x), SET_DEST (y), 1, info))
+		 : struct_equiv (&SET_DEST (x), SET_DEST (y), 0, info))
+		&& struct_equiv (&SET_SRC (x), SET_SRC (y), 1, info));


Why pass a pointer to an rtx, instead of just the rth itself, as the
first argument to struct_equiv() ?
+struct_equiv (rtx *xp, rtx y, int rvalue, struct equiv_info *info)

I suppose this is for validate_change.  But that means that struct_equiv
can change the rtx passed to it, right?  The comment before the function
doesn't say that (or explain why this is necessary).


You haven't said anything about how this impacts compile time.  Given
comments like, 
+/* This function must be called up to three times for a successful cross-jump
+   match:
it makes me wonder if this entire idea isn't prohibitively expensive.


Ehm, yikes!
-      if_convert (0);
+      if (flag_expensive_optimizations)
+	{
+	  basic_block bb;
+
+	  life_analysis (dump_file, PROP_REG_INFO);
+	  if_convert (1);
+	  count_or_remove_death_notes (NULL, 1);
+	  FOR_EACH_BB (bb)
+	    {
+	      bb->il.rtl->global_live_at_start = 0;
+	      bb->il.rtl->global_live_at_end = 0;
+	    }
+	  ENTRY_BLOCK_PTR->il.rtl->global_live_at_start = 0;
+	  EXIT_BLOCK_PTR->il.rtl->global_live_at_start = 0;
+	}
+      else
+	if_convert (0);
Is it really crucial to do the complex cmove thing before combine?

Gr.
Steven