Re: [PR50878, PATCH] Fix for verify_dominators in -ftree-tail-merge

[Tom de Vries <Tom_deVries at mentor dot com>]

On 11/01/2011 10:43 AM, Richard Guenther wrote:
> On Mon, Oct 31, 2011 at 9:19 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> On 10/30/2011 10:54 AM, Richard Guenther wrote:
>>> On Sun, Oct 30, 2011 at 9:27 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>>> On 10/30/2011 09:20 AM, Tom de Vries wrote:
>>>>> Richard,
>>>>>
>>>>> I have a fix for PR50878.
>>>>
>>>> Sorry, with patch this time.
>>>
>>> Ok for now, but see Davids mail and the complexity issue with iteratively
>>> updating dominators.
>>
>> I'm not sure which mail you mean.
> 
> The one I CCed you on, which complained about iterative dominator fixing
> taking 70% of the compile-time in some GCC testsuite test.
> 
>>> It seems to me that we know exactly what to update
>>> and how, and we should do that (well, if we need up-to-date dominators,
>>> re-computing them once in the pass would be ok).
>>>
>>
>> Indeed, in this example we know exactly what to update and how. However, PR50908
>> popped up, and there that's not the case anymore.
>>
>> Consider the following cfg, where A is the direct dominator of I:
>>
>>                A
>>               / \
>>              B   \
>>             / \   \
>>                C   D
>>               /|   |\
>>                E   F
>>                |\ /|
>>                | x |
>>                |/ \|
>>                G   H
>>                 \ /
>>                  I
>>
>> Say E and F are duplicates, and F is removed.  The cfg then looks like
>> this:
>>
>>                A
>>               / \
>>              B   \
>>             / \   \
>>                C   D
>>               / \ / \
>>                  E
>>                 / \
>>                G   H
>>                 \ /
>>                  I
>>
>> E is now the new direct dominator of I.
>>
>> The patch for PR50878 did not address this example, since it uses the set of bbs
>> directly dominated by the (single) predecessor of bb1 and bb2.
>>
>> The new patch calculates the updated dominator info by taking the nearest common
>> dominator (A) of bb1 (F) and bb2 (E), and getting the set of bbs immediately
>> dominated by it.  Part of this set is now directly dominated by bb2.
>>
>> Ideally we would have a means to determine which bbs in the set are now
>> directly dominated by bb2, and call set_immediate_dominator for those bbs, but
>> we don't, so instead we let iterate_fix_dominators figure it out.
>>
>> Additionally, the patch makes sure it updates dominator info before updating the
>> vuses, this fixes a latent bug.
>>
>> The patch fixes both PR50908 and PR50878.
>>
>> Bootstrapped and reg-tested on x86_64 and i686, and build and reg-tested on ARM
>> and MIPS.
>>
>> Ok for trunk?
> 
> Ok, but please add testcases for all the bugs you fixed.  This helps adding test
> coverage for these cases.
> 

Committed attached test-cases.

Thanks,
- Tom

2011-11-01  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/50908
	* gcc.dg/pr50908.c: New test.
	* gcc.dg/pr50908-2.c: Same.
	* gcc.dg/pr50908-3.c: Same.

Index: gcc/testsuite/gcc.dg/pr50908-2.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/pr50908-2.c (revision 0)
@@ -0,0 +1,80 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-tail-merge" } */
+
+typedef struct rtx_def *rtx;
+enum debug_info_levels
+{
+  ARM_FLOAT_ABI_SOFT, ARM_FLOAT_ABI_SOFTFP, ARM_FLOAT_ABI_HARD
+};
+struct gcc_options
+{
+  int x_target_flags;
+};
+extern struct gcc_options global_options;
+extern int arm_arch_thumb2;
+enum rtx_code
+{
+  UNSPEC, UNSPEC_VOLATILE, ADDR_VEC, SET, CLOBBER, CALL, RETURN,
+    SIMPLE_RETURN, EH_RETURN, TRAP_IF, CONST_INT, CONST_FIXED, CONST_DOUBLE,
+    CONST_VECTOR, CONST_STRING, CONST, PC, REG, SCRATCH, SUBREG,
+    STRICT_LOW_PART, CONCAT, CONCATN, MEM, LABEL_REF, SYMBOL_REF, CC0,
+    IF_THEN_ELSE, COMPARE, PLUS, MINUS, NEG, MULT, SS_MULT, US_MULT, DIV,
+    SS_DIV, US_DIV, MOD, UDIV, UMOD, AND, IOR, XOR, NOT, ASHIFT, ROTATE,
+    ASHIFTRT, LSHIFTRT, ROTATERT, PRE_DEC, PRE_INC, POST_DEC, POST_INC,
+    PRE_MODIFY, POST_MODIFY, NE, EQ, GE, GT, LE, LT, GEU, GTU, LEU, LTU,
+    UNORDERED, ORDERED, UNEQ, UNGE, UNGT, UNLE, UNLT, LTGT, SIGN_EXTEND,
+    ZERO_EXTEND, TRUNCATE, FLOAT_EXTEND, FLOAT_TRUNCATE, FLOAT, FIX,
+    UNSIGNED_FLOAT, UNSIGNED_FIX, SIGN_EXTRACT, ZERO_EXTRACT, HIGH, LO_SUM,
+    VEC_MERGE, VEC_SELECT, VEC_CONCAT, VEC_DUPLICATE, SS_PLUS, US_PLUS,
+    SS_MINUS, SS_NEG, US_NEG, SS_ABS, SS_ASHIFT, US_ASHIFT, US_MINUS,
+    SS_TRUNCATE, US_TRUNCATE, FMA, VAR_LOCATION, DEBUG_IMPLICIT_PTR,
+    ENTRY_VALUE, DEBUG_PARAMETER_REF, LAST_AND_UNUSED_RTX_CODE
+};
+union rtunion_def
+{
+};
+struct rtx_def
+{
+  enum rtx_code code:16;
+}
+builtin_info_type;
+enum constraint_num
+{
+  CONSTRAINT__UNKNOWN =
+    0, CONSTRAINT_f, CONSTRAINT_t, CONSTRAINT_v, CONSTRAINT_w, CONSTRAINT_x,
+    CONSTRAINT_y, CONSTRAINT_z, CONSTRAINT_l, CONSTRAINT_h, CONSTRAINT_j,
+    CONSTRAINT_Pj, CONSTRAINT_PJ, CONSTRAINT_k, CONSTRAINT_b, CONSTRAINT_c,
+    CONSTRAINT_I, CONSTRAINT_J, CONSTRAINT_K, CONSTRAINT_L, CONSTRAINT_M,
+    CONSTRAINT_N, CONSTRAINT_O, CONSTRAINT_Pa, CONSTRAINT_Pb, CONSTRAINT_Pc,
+    CONSTRAINT_Pd, CONSTRAINT_Ps, CONSTRAINT_Pt, CONSTRAINT_Pu, CONSTRAINT_Pv,
+    CONSTRAINT_Pw, CONSTRAINT_Px, CONSTRAINT_Py, CONSTRAINT_G, CONSTRAINT_H,
+    CONSTRAINT_Dz, CONSTRAINT_Da, CONSTRAINT_Db, CONSTRAINT_Dc, CONSTRAINT_Di,
+    CONSTRAINT_Dn, CONSTRAINT_Dl, CONSTRAINT_DL, CONSTRAINT_Dv, CONSTRAINT_Dy,
+    CONSTRAINT_Ut, CONSTRAINT_Uv, CONSTRAINT_Uy, CONSTRAINT_Un, CONSTRAINT_Um,
+    CONSTRAINT_Us, CONSTRAINT_Uq, CONSTRAINT_Q, CONSTRAINT_Uu, CONSTRAINT_Uw,
+    CONSTRAINT__LIMIT
+};
+typedef struct VEC_char_base
+{
+}
+VEC_int_heap;
+static inline int
+satisfies_constraint_j (rtx op)
+{
+  long long ival = 0;
+  return ((((!((global_options.x_target_flags & (1 << 14)) != 0))
+	    || arm_arch_thumb2) && arm_arch_thumb2))
+    && ((((enum rtx_code) (op)->code) == HIGH)
+	|| ((((enum rtx_code) (op)->code) == CONST_INT)
+	    && (((ival & 0xffff0000) == 0))));
+}
+
+int
+constraint_satisfied_p (rtx op, enum constraint_num c)
+{
+  switch (c)
+    {
+    case CONSTRAINT_j:
+      return satisfies_constraint_j (op);
+    }
+}
Index: gcc/testsuite/gcc.dg/pr50908-3.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/pr50908-3.c (revision 0)
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-tail-merge" } */
+
+extern int v1;
+extern int v2;
+
+void
+f ()
+{
+  if (v2 || v1)
+    (!(v1)) ? (void) 0 : (void) g ();
+}
Index: gcc/testsuite/gcc.dg/pr50908.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/pr50908.c (revision 0)
@@ -0,0 +1,175 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target lp64 } */
+/* { dg-options "-O2 -ftree-tail-merge" } */
+
+enum Lisp_Type
+{
+  Lisp_Int0 = 0, Lisp_Int1 = 4, Lisp_Symbol = 2, Lisp_Misc = 3, Lisp_String =
+    1, Lisp_Vectorlike = 5, Lisp_Cons = 6, Lisp_Float = 7,
+};
+typedef long Lisp_Object;
+enum pvec_type
+{
+  PVEC_NORMAL_VECTOR = 0, PVEC_PROCESS = 0x200, PVEC_FRAME =
+    0x400, PVEC_COMPILED = 0x800, PVEC_WINDOW =
+    0x1000, PVEC_WINDOW_CONFIGURATION = 0x2000, PVEC_SUBR =
+    0x4000, PVEC_CHAR_TABLE = 0x8000, PVEC_BOOL_VECTOR =
+    0x10000, PVEC_BUFFER = 0x20000, PVEC_HASH_TABLE = 0x40000, PVEC_TERMINAL =
+    0x80000, PVEC_SUB_CHAR_TABLE = 0x100000, PVEC_FONT =
+    0x200000, PVEC_OTHER = 0x400000, PVEC_TYPE_MASK = 0x7ffe00
+};
+struct Lisp_Vector
+{
+  unsigned long size;
+};
+struct Lisp_Char_Table
+{
+  Lisp_Object defalt;
+  Lisp_Object ascii;
+};
+struct Lisp_Sub_Char_Table
+{
+  Lisp_Object contents[1];
+};
+extern Lisp_Object Qnil, Qt, Qquote, Qlambda, Qsubr, Qunbound;
+struct buffer_text
+{
+  unsigned char *beg;
+  long gpt_byte;
+  long gap_size;
+};
+struct buffer
+{
+  struct buffer_text *text;
+  struct region_cache *width_run_cache;
+  Lisp_Object tab_width;
+  Lisp_Object ctl_arrow;
+};
+extern struct buffer *current_buffer;
+extern Lisp_Object Vchar_width_table;
+struct frame
+{
+  long text_lines, text_cols;
+};
+struct window
+{
+  Lisp_Object frame;
+};
+extern Lisp_Object Vtruncate_partial_width_windows;
+extern struct Lisp_Char_Table *window_display_table (struct window *);
+struct position *
+compute_motion (from, fromvpos, fromhpos, did_motion, to, tovpos, tohpos,
+		width, hscroll, tab_offset, win)
+     long from, fromvpos, fromhpos, to, tovpos, tohpos;
+     struct window *win;
+{
+  register long hpos = fromhpos;
+  register long pos;
+  long pos_byte;
+  register int c = 0;
+  register struct Lisp_Char_Table *dp = window_display_table (win);
+  long wide_column_end_hpos = 0;
+  long continuation_glyph_width;
+  while (1)
+    {
+      if (hpos > width)
+	{
+	  int total_width = width + continuation_glyph_width;
+	  if (!((Vtruncate_partial_width_windows) == (Qnil))
+	      && (total_width <
+		  (((void) 0,
+		    (struct frame
+		     *) ((long) (((win)->frame) & ~((((long) 1) << 3) -
+						    1)))))->text_cols))
+	    {
+	      if (pos <= to)
+		{
+		  pos = find_before_next_newline (pos, to, 1);
+		}
+	      if (wide_column_end_hpos > width)
+		{
+		  hpos -= width;
+		}
+	    }
+	}
+      else
+	{
+	  Lisp_Object charvec;
+	  c =
+	    *(((((pos_byte)) >=
+		(current_buffer->text->gpt_byte) ? (current_buffer->text->
+						    gap_size) : 0) +
+	       ((pos_byte)) + (current_buffer->text->beg) - ((1))));
+	  if (current_buffer->width_run_cache)
+	    {
+	      if (((((enum Lisp_Type) (((unsigned long) ((charvec))) &
+				       ((((long) 1) << 3) - 1))) ==
+		    Lisp_Vectorlike)
+		   &&
+		   !(((void) 0,
+		      (struct Lisp_Vector
+		       *) ((long) ((charvec) & ~((((long) 1) << 3) - 1))))->
+		     size & ((((unsigned long) 1 << (64 - 1)) >> 1)))))
+		{
+		  unsigned char *ptr;
+		  int bytes, width, wide_column;
+		  do
+		    {
+		      if ((!((*ptr) & 0x80) ? 1 : !((*ptr) & 0x20) ? 2 :
+			   !((*ptr) & 0x10) ? 3 : !((*ptr) & 0x08) ? 4 : 5) !=
+			  bytes)
+			width = bytes * 4;
+		      else
+			{
+			  if (dp != 0
+			      &&
+			      ((((enum
+				  Lisp_Type) (((unsigned
+						long) (((((unsigned) (c) <
+							  0x80)
+							 ? ((((dp)->ascii) ==
+							     (Qnil)) ? (dp)->
+							    defalt
+							    : (((((enum
+								   Lisp_Type)
+								  (((unsigned
+								     long) (((dp)->ascii))) & ((((long) 1) << 3) - 1))) == Lisp_Vectorlike) && (((((void) 0, (struct Lisp_Vector *) ((long) (((dp)->ascii) & ~((((long) 1) << 3) - 1))))->size & (((((unsigned long) 1 << (64 - 1)) >> 1)) | (PVEC_SUB_CHAR_TABLE)))) == (((((unsigned long) 1 << (64 - 1)) >> 1)) | (PVEC_SUB_CHAR_TABLE)))) ? ((void) 0, (struct Lisp_Sub_Char_Table *) ((long) (((dp)->ascii) & ~((((long) 1) << 3) - 1))))->contents[c] : (dp)->ascii)) : disp_char_vector ((dp), (c)))))) & ((((long) 1) << 3) - 1))) == Lisp_Vectorlike) && !(((void) 0, (struct Lisp_Vector *) ((long) (((((unsigned) (c) < 0x80) ? ((((dp)->ascii) == (Qnil)) ? (dp)->defalt : (((((enum Lisp_Type) (((unsigned long) (((dp)->ascii))) & ((((long) 1) << 3) - 1))) == Lisp_Vectorlike) && (((((void) 0, (struct Lisp_Vector *) ((long) (((dp)->ascii) & ~((((long) 1) << 3) - 1))))->size & (((((unsigned long) 1 << (64 - 1)) >> 1)) | (PVEC_SUB_CHAR_TABLE)))) == (((((unsigned long) 1 << (64 - 1)) >> 1)) | (PVEC_SUB_CHAR_TABLE)))) ? ((void) 0, (struct Lisp_Sub_Char_Table *) ((long) (((dp)->ascii) & ~((((long) 1) << 3) - 1))))->contents[c] : (dp)->ascii)) : disp_char_vector ((dp), (c)))) & ~((((long) 1) << 3) - 1))))->size & ((((unsigned long) 1 << (64 - 1)) >> 1)))))
+			    width =
+			      ((void) 0,
+			       (struct Lisp_Vector
+				*) ((long) (((((unsigned) (c) <
+					       0x80) ? ((((dp)->ascii) ==
+							 (Qnil)) ? (dp)->
+							defalt
+							: (((((enum
+							       Lisp_Type) (((unsigned long) (((dp)->ascii))) & ((((long) 1) << 3) - 1))) == Lisp_Vectorlike) && (((((void) 0, (struct Lisp_Vector *) ((long) (((dp)->ascii) & ~((((long) 1) << 3) - 1))))->size & (((((unsigned long) 1 << (64 - 1)) >> 1)) | (PVEC_SUB_CHAR_TABLE)))) == (((((unsigned long) 1 << (64 - 1)) >> 1)) | (PVEC_SUB_CHAR_TABLE)))) ? ((void) 0, (struct Lisp_Sub_Char_Table *) ((long) (((dp)->ascii) & ~((((long) 1) << 3) - 1))))->contents[c] : (dp)->ascii)) : disp_char_vector ((dp), (c)))) & ~((((long) 1) << 3) - 1))))->size;
+			  else
+			    width =
+			      (((unsigned) (c) < 0x80) ? (c <
+							  0x20 ? (c ==
+								  '\t'
+								  ? ((((long)
+								       (current_buffer->
+									tab_width))
+								      >> (3 -
+									  1)))
+								  : (c ==
+								     '\n' ? 0
+								     : (((current_buffer->ctl_arrow) == (Qnil)) ? 4 : 2))) : (c < 0x7f ? 1 : ((((current_buffer->ctl_arrow) == (Qnil)) ? 4 : 2)))) : (((long) ((((unsigned) (c) < 0x80) ? (
+																														       {
+																														       Lisp_Object
+																														       _val;
+																														       _val;}
+			):																							char_table_ref ((Vchar_width_table), (c))))) >> (3 - 1)));
+			  if (width > 1)
+			    wide_column = width;
+			}
+		    }
+		  while (0);
+		  if (wide_column)
+		    wide_column_end_hpos = hpos + wide_column;
+		}
+	    }
+	}
+    }
+}