Patchwork Fix switch conversion (PR tree-optimization/48809)

login
register
mail settings
Submitter Jakub Jelinek
Date April 29, 2011, 4:43 p.m.
Message ID <20110429164336.GS17079@tyan-ft48-01.lab.bos.redhat.com>
Download mbox | patch
Permalink /patch/93454/
State New
Headers show

Comments

Jakub Jelinek - April 29, 2011, 4:43 p.m.
Hi!

The following patch fixes a bug in tree-switch-conversion.c with
signed index_expr's.  build_arrays would compute index_expr - range_min
in index_expr's type and use that as index into CSWTCH.N array,
which is wrong, because in this case index_expr 98 - (-62) computed
in signed char type results in signed overflow and we end up
loading from CSWTCH.2[-96].  Apparently for the bounds checking
we perform the same index_expr - range_min computation, but in
corresponding unsigned type.  This patch computes it just once in
unsigned type, so that overflow isn't undefined.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for
trunk/4.6/4.5/4.4?

2011-04-29  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/48809
	* tree-switch-conversion.c (build_arrays): Compute tidx in unsigned
	type.
	(gen_inbound_check): Don't compute index_expr - range_min in utype
	again, instead reuse SSA_NAME initialized in build_arrays.
	Remove two useless gsi_for_stmt calls.

	* gcc.c-torture/execute/pr48809.c: New test.


	Jakub
Jeff Law - April 29, 2011, 6:58 p.m.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 04/29/11 10:43, Jakub Jelinek wrote:
> Hi!
> 
> The following patch fixes a bug in tree-switch-conversion.c with
> signed index_expr's.  build_arrays would compute index_expr - range_min
> in index_expr's type and use that as index into CSWTCH.N array,
> which is wrong, because in this case index_expr 98 - (-62) computed
> in signed char type results in signed overflow and we end up
> loading from CSWTCH.2[-96].  Apparently for the bounds checking
> we perform the same index_expr - range_min computation, but in
> corresponding unsigned type.  This patch computes it just once in
> unsigned type, so that overflow isn't undefined.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for
> trunk/4.6/4.5/4.4?
> 
> 2011-04-29  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/48809
> 	* tree-switch-conversion.c (build_arrays): Compute tidx in unsigned
> 	type.
> 	(gen_inbound_check): Don't compute index_expr - range_min in utype
> 	again, instead reuse SSA_NAME initialized in build_arrays.
> 	Remove two useless gsi_for_stmt calls.
> 
> 	* gcc.c-torture/execute/pr48809.c: New test.
OK.

jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJNuwpHAAoJEBRtltQi2kC71SAH/1VFBhEB7SXDEogMFx59LD1j
G1D+1DBL9qQEDRXMQi+aA6H8Y8WxfUDsUTQUD3rrg9HxZDEaUz55P46nc6dd/DXS
72tFm5OW5bucJbnHocxu+PeAedk8w0cmjxdnXA38ezPhqpeqUKK/ojhPPcGSErHH
7Z9YUdDHGbAcZACjvd1qTObfp4NUG0PTZ7d6+ZOsAt7RwxgECcUJuyJhZaQdxZVV
MTF96cNa205xqOIBYwGCyW5bvFhgL4kDvdUMSln2CURXyl/N+JqeGnuGEElItM+A
8ryLWBIyzuUFHNML6FK6wrROs/QPiUdan2RqDyW46WT8UdE3PgVakT/7c9E42sc=
=395m
-----END PGP SIGNATURE-----
Richard Guenther - May 2, 2011, 9:36 a.m.
On Fri, Apr 29, 2011 at 6:43 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> The following patch fixes a bug in tree-switch-conversion.c with
> signed index_expr's.  build_arrays would compute index_expr - range_min
> in index_expr's type and use that as index into CSWTCH.N array,
> which is wrong, because in this case index_expr 98 - (-62) computed
> in signed char type results in signed overflow and we end up
> loading from CSWTCH.2[-96].  Apparently for the bounds checking
> we perform the same index_expr - range_min computation, but in
> corresponding unsigned type.  This patch computes it just once in
> unsigned type, so that overflow isn't undefined.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for
> trunk/4.6/4.5/4.4?
>
> 2011-04-29  Jakub Jelinek  <jakub@redhat.com>
>
>        PR tree-optimization/48809
>        * tree-switch-conversion.c (build_arrays): Compute tidx in unsigned
>        type.
>        (gen_inbound_check): Don't compute index_expr - range_min in utype
>        again, instead reuse SSA_NAME initialized in build_arrays.
>        Remove two useless gsi_for_stmt calls.
>
>        * gcc.c-torture/execute/pr48809.c: New test.
>
> --- gcc/tree-switch-conversion.c.jj     2010-12-02 11:51:32.000000000 +0100
> +++ gcc/tree-switch-conversion.c        2011-04-29 15:23:57.000000000 +0200
> @@ -1,6 +1,6 @@
>  /* Switch Conversion converts variable initializations based on switch
>    statements to initializations from a static array.
> -   Copyright (C) 2006, 2008, 2009, 2010 Free Software Foundation, Inc.
> +   Copyright (C) 2006, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
>    Contributed by Martin Jambor <jamborm@suse.cz>
>
>  This file is part of GCC.
> @@ -656,7 +656,7 @@ static void
>  build_arrays (gimple swtch)
>  {
>   tree arr_index_type;
> -  tree tidx, sub, tmp;
> +  tree tidx, sub, tmp, utype;
>   gimple stmt;
>   gimple_stmt_iterator gsi;
>   int i;
> @@ -664,14 +664,20 @@ build_arrays (gimple swtch)
>
>   gsi = gsi_for_stmt (swtch);
>
> +  /* Make sure we do not generate arithmetics in a subrange.  */
> +  utype = TREE_TYPE (info.index_expr);
> +  if (TREE_TYPE (utype))
> +    utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
> +  else
> +    utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
> +

type_for_mode?  Ick.  What's TREE_TYPE of that char type anyway?

Why not always

  utype = build_nonstandard_integer_type (TYPE_PRECISION (TREE_TYPE
(info.index_expr)), 1);

?

Richard.

>   arr_index_type = build_index_type (info.range_size);
> -  tmp = create_tmp_var (TREE_TYPE (info.index_expr), "csti");
> +  tmp = create_tmp_var (utype, "csui");
>   add_referenced_var (tmp);
>   tidx = make_ssa_name (tmp, NULL);
> -  sub = fold_build2_loc (loc, MINUS_EXPR,
> -                    TREE_TYPE (info.index_expr), info.index_expr,
> -                    fold_convert_loc (loc, TREE_TYPE (info.index_expr),
> -                                      info.range_min));
> +  sub = fold_build2_loc (loc, MINUS_EXPR, utype,
> +                        fold_convert_loc (loc, utype, info.index_expr),
> +                        fold_convert_loc (loc, utype, info.range_min));
>   sub = force_gimple_operand_gsi (&gsi, sub,
>                                  false, NULL, true, GSI_SAME_STMT);
>   stmt = gimple_build_assign (tidx, sub);
> @@ -780,12 +786,7 @@ gen_inbound_check (gimple swtch)
>   tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
>   tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
>   gimple label1, label2, label3;
> -
> -  tree utype;
> -  tree tmp_u_1, tmp_u_2, tmp_u_var;
> -  tree cast;
> -  gimple cast_assign, minus_assign;
> -  tree ulb, minus;
> +  tree utype, tidx;
>   tree bound;
>
>   gimple cond_stmt;
> @@ -799,49 +800,24 @@ gen_inbound_check (gimple swtch)
>   gcc_assert (info.default_values);
>   bb0 = gimple_bb (swtch);
>
> -  /* Make sure we do not generate arithmetics in a subrange.  */
> -  if (TREE_TYPE (TREE_TYPE (info.index_expr)))
> -    utype = lang_hooks.types.type_for_mode
> -      (TYPE_MODE (TREE_TYPE (TREE_TYPE (info.index_expr))), 1);
> -  else
> -    utype = lang_hooks.types.type_for_mode
> -      (TYPE_MODE (TREE_TYPE (info.index_expr)), 1);
> +  tidx = gimple_assign_lhs (info.arr_ref_first);
> +  utype = TREE_TYPE (tidx);
>
>   /* (end of) block 0 */
>   gsi = gsi_for_stmt (info.arr_ref_first);
> -  tmp_u_var = create_tmp_var (utype, "csui");
> -  add_referenced_var (tmp_u_var);
> -  tmp_u_1 = make_ssa_name (tmp_u_var, NULL);
> -
> -  cast = fold_convert_loc (loc, utype, info.index_expr);
> -  cast_assign = gimple_build_assign (tmp_u_1, cast);
> -  SSA_NAME_DEF_STMT (tmp_u_1) = cast_assign;
> -  gsi_insert_before (&gsi, cast_assign, GSI_SAME_STMT);
> -  update_stmt (cast_assign);
> -
> -  ulb = fold_convert_loc (loc, utype, info.range_min);
> -  minus = fold_build2_loc (loc, MINUS_EXPR, utype, tmp_u_1, ulb);
> -  minus = force_gimple_operand_gsi (&gsi, minus, false, NULL, true,
> -                                   GSI_SAME_STMT);
> -  tmp_u_2 = make_ssa_name (tmp_u_var, NULL);
> -  minus_assign = gimple_build_assign (tmp_u_2, minus);
> -  SSA_NAME_DEF_STMT (tmp_u_2) = minus_assign;
> -  gsi_insert_before (&gsi, minus_assign, GSI_SAME_STMT);
> -  update_stmt (minus_assign);
> +  gsi_next (&gsi);
>
>   bound = fold_convert_loc (loc, utype, info.range_size);
> -  cond_stmt = gimple_build_cond (LE_EXPR, tmp_u_2, bound, NULL_TREE, NULL_TREE);
> +  cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
>   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
>   update_stmt (cond_stmt);
>
>   /* block 2 */
> -  gsi = gsi_for_stmt (info.arr_ref_first);
>   label2 = gimple_build_label (label_decl2);
>   gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
>   last_assign = gen_def_assigns (&gsi);
>
>   /* block 1 */
> -  gsi = gsi_for_stmt (info.arr_ref_first);
>   label1 = gimple_build_label (label_decl1);
>   gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
>
> --- gcc/testsuite/gcc.c-torture/execute/pr48809.c.jj    2011-04-29 15:30:29.000000000 +0200
> +++ gcc/testsuite/gcc.c-torture/execute/pr48809.c       2011-04-29 15:29:49.000000000 +0200
> @@ -0,0 +1,60 @@
> +/* PR tree-optimization/48809 */
> +
> +extern void abort (void);
> +
> +int
> +foo (signed char x)
> +{
> +  int y = 0;
> +  switch (x)
> +    {
> +    case 0: y = 1; break;
> +    case 1: y = 7; break;
> +    case 2: y = 2; break;
> +    case 3: y = 19; break;
> +    case 4: y = 5; break;
> +    case 5: y = 17; break;
> +    case 6: y = 31; break;
> +    case 7: y = 8; break;
> +    case 8: y = 28; break;
> +    case 9: y = 16; break;
> +    case 10: y = 31; break;
> +    case 11: y = 12; break;
> +    case 12: y = 15; break;
> +    case 13: y = 111; break;
> +    case 14: y = 17; break;
> +    case 15: y = 10; break;
> +    case 16: y = 31; break;
> +    case 17: y = 7; break;
> +    case 18: y = 2; break;
> +    case 19: y = 19; break;
> +    case 20: y = 5; break;
> +    case 21: y = 107; break;
> +    case 22: y = 31; break;
> +    case 23: y = 8; break;
> +    case 24: y = 28; break;
> +    case 25: y = 106; break;
> +    case 26: y = 31; break;
> +    case 27: y = 102; break;
> +    case 28: y = 105; break;
> +    case 29: y = 111; break;
> +    case 30: y = 17; break;
> +    case 31: y = 10; break;
> +    case 32: y = 31; break;
> +    case 98: y = 18; break;
> +    case -62: y = 19; break;
> +    }
> +  return y;
> +}
> +
> +int
> +main ()
> +{
> +  if (foo (98) != 18 || foo (97) != 0 || foo (99) != 0)
> +    abort ();
> +  if (foo (-62) != 19 || foo (-63) != 0 || foo (-61) != 0)
> +    abort ();
> +  if (foo (28) != 105 || foo (27) != 102 || foo (29) != 111)
> +    abort ();
> +  return 0;
> +}
>
>        Jakub
>
H.J. Lu - May 3, 2011, 3:09 a.m.
On Fri, Apr 29, 2011 at 9:43 AM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> The following patch fixes a bug in tree-switch-conversion.c with
> signed index_expr's.  build_arrays would compute index_expr - range_min
> in index_expr's type and use that as index into CSWTCH.N array,
> which is wrong, because in this case index_expr 98 - (-62) computed
> in signed char type results in signed overflow and we end up
> loading from CSWTCH.2[-96].  Apparently for the bounds checking
> we perform the same index_expr - range_min computation, but in
> corresponding unsigned type.  This patch computes it just once in
> unsigned type, so that overflow isn't undefined.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for
> trunk/4.6/4.5/4.4?
>
> 2011-04-29  Jakub Jelinek  <jakub@redhat.com>
>
>        PR tree-optimization/48809
>        * tree-switch-conversion.c (build_arrays): Compute tidx in unsigned
>        type.
>        (gen_inbound_check): Don't compute index_expr - range_min in utype
>        again, instead reuse SSA_NAME initialized in build_arrays.
>        Remove two useless gsi_for_stmt calls.
>
>        * gcc.c-torture/execute/pr48809.c: New test.

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48849

Patch

--- gcc/tree-switch-conversion.c.jj	2010-12-02 11:51:32.000000000 +0100
+++ gcc/tree-switch-conversion.c	2011-04-29 15:23:57.000000000 +0200
@@ -1,6 +1,6 @@ 
 /* Switch Conversion converts variable initializations based on switch
    statements to initializations from a static array.
-   Copyright (C) 2006, 2008, 2009, 2010 Free Software Foundation, Inc.
+   Copyright (C) 2006, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
    Contributed by Martin Jambor <jamborm@suse.cz>
 
 This file is part of GCC.
@@ -656,7 +656,7 @@  static void
 build_arrays (gimple swtch)
 {
   tree arr_index_type;
-  tree tidx, sub, tmp;
+  tree tidx, sub, tmp, utype;
   gimple stmt;
   gimple_stmt_iterator gsi;
   int i;
@@ -664,14 +664,20 @@  build_arrays (gimple swtch)
 
   gsi = gsi_for_stmt (swtch);
 
+  /* Make sure we do not generate arithmetics in a subrange.  */
+  utype = TREE_TYPE (info.index_expr);
+  if (TREE_TYPE (utype))
+    utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
+  else
+    utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
+
   arr_index_type = build_index_type (info.range_size);
-  tmp = create_tmp_var (TREE_TYPE (info.index_expr), "csti");
+  tmp = create_tmp_var (utype, "csui");
   add_referenced_var (tmp);
   tidx = make_ssa_name (tmp, NULL);
-  sub = fold_build2_loc (loc, MINUS_EXPR,
-		     TREE_TYPE (info.index_expr), info.index_expr,
-		     fold_convert_loc (loc, TREE_TYPE (info.index_expr),
-				       info.range_min));
+  sub = fold_build2_loc (loc, MINUS_EXPR, utype,
+			 fold_convert_loc (loc, utype, info.index_expr),
+			 fold_convert_loc (loc, utype, info.range_min));
   sub = force_gimple_operand_gsi (&gsi, sub,
 				  false, NULL, true, GSI_SAME_STMT);
   stmt = gimple_build_assign (tidx, sub);
@@ -780,12 +786,7 @@  gen_inbound_check (gimple swtch)
   tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
   tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
   gimple label1, label2, label3;
-
-  tree utype;
-  tree tmp_u_1, tmp_u_2, tmp_u_var;
-  tree cast;
-  gimple cast_assign, minus_assign;
-  tree ulb, minus;
+  tree utype, tidx;
   tree bound;
 
   gimple cond_stmt;
@@ -799,49 +800,24 @@  gen_inbound_check (gimple swtch)
   gcc_assert (info.default_values);
   bb0 = gimple_bb (swtch);
 
-  /* Make sure we do not generate arithmetics in a subrange.  */
-  if (TREE_TYPE (TREE_TYPE (info.index_expr)))
-    utype = lang_hooks.types.type_for_mode
-      (TYPE_MODE (TREE_TYPE (TREE_TYPE (info.index_expr))), 1);
-  else
-    utype = lang_hooks.types.type_for_mode
-      (TYPE_MODE (TREE_TYPE (info.index_expr)), 1);
+  tidx = gimple_assign_lhs (info.arr_ref_first);
+  utype = TREE_TYPE (tidx);
 
   /* (end of) block 0 */
   gsi = gsi_for_stmt (info.arr_ref_first);
-  tmp_u_var = create_tmp_var (utype, "csui");
-  add_referenced_var (tmp_u_var);
-  tmp_u_1 = make_ssa_name (tmp_u_var, NULL);
-
-  cast = fold_convert_loc (loc, utype, info.index_expr);
-  cast_assign = gimple_build_assign (tmp_u_1, cast);
-  SSA_NAME_DEF_STMT (tmp_u_1) = cast_assign;
-  gsi_insert_before (&gsi, cast_assign, GSI_SAME_STMT);
-  update_stmt (cast_assign);
-
-  ulb = fold_convert_loc (loc, utype, info.range_min);
-  minus = fold_build2_loc (loc, MINUS_EXPR, utype, tmp_u_1, ulb);
-  minus = force_gimple_operand_gsi (&gsi, minus, false, NULL, true,
-				    GSI_SAME_STMT);
-  tmp_u_2 = make_ssa_name (tmp_u_var, NULL);
-  minus_assign = gimple_build_assign (tmp_u_2, minus);
-  SSA_NAME_DEF_STMT (tmp_u_2) = minus_assign;
-  gsi_insert_before (&gsi, minus_assign, GSI_SAME_STMT);
-  update_stmt (minus_assign);
+  gsi_next (&gsi);
 
   bound = fold_convert_loc (loc, utype, info.range_size);
-  cond_stmt = gimple_build_cond (LE_EXPR, tmp_u_2, bound, NULL_TREE, NULL_TREE);
+  cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
   update_stmt (cond_stmt);
 
   /* block 2 */
-  gsi = gsi_for_stmt (info.arr_ref_first);
   label2 = gimple_build_label (label_decl2);
   gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
   last_assign = gen_def_assigns (&gsi);
 
   /* block 1 */
-  gsi = gsi_for_stmt (info.arr_ref_first);
   label1 = gimple_build_label (label_decl1);
   gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
 
--- gcc/testsuite/gcc.c-torture/execute/pr48809.c.jj	2011-04-29 15:30:29.000000000 +0200
+++ gcc/testsuite/gcc.c-torture/execute/pr48809.c	2011-04-29 15:29:49.000000000 +0200
@@ -0,0 +1,60 @@ 
+/* PR tree-optimization/48809 */
+
+extern void abort (void);
+
+int
+foo (signed char x)
+{
+  int y = 0;
+  switch (x)
+    {
+    case 0: y = 1; break;
+    case 1: y = 7; break;
+    case 2: y = 2; break;
+    case 3: y = 19; break;
+    case 4: y = 5; break;
+    case 5: y = 17; break;
+    case 6: y = 31; break;
+    case 7: y = 8; break;
+    case 8: y = 28; break;
+    case 9: y = 16; break;
+    case 10: y = 31; break;
+    case 11: y = 12; break;
+    case 12: y = 15; break;
+    case 13: y = 111; break;
+    case 14: y = 17; break;
+    case 15: y = 10; break;
+    case 16: y = 31; break;
+    case 17: y = 7; break;
+    case 18: y = 2; break;
+    case 19: y = 19; break;
+    case 20: y = 5; break;
+    case 21: y = 107; break;
+    case 22: y = 31; break;
+    case 23: y = 8; break;
+    case 24: y = 28; break;
+    case 25: y = 106; break;
+    case 26: y = 31; break;
+    case 27: y = 102; break;
+    case 28: y = 105; break;
+    case 29: y = 111; break;
+    case 30: y = 17; break;
+    case 31: y = 10; break;
+    case 32: y = 31; break;
+    case 98: y = 18; break;
+    case -62: y = 19; break;
+    }
+  return y;
+}
+
+int
+main ()
+{
+  if (foo (98) != 18 || foo (97) != 0 || foo (99) != 0)
+    abort ();
+  if (foo (-62) != 19 || foo (-63) != 0 || foo (-61) != 0)
+    abort ();
+  if (foo (28) != 105 || foo (27) != 102 || foo (29) != 111)
+    abort ();
+  return 0;
+}