Question about tree-switch-conversion.c

Question about tree-switch-conversion.c

[Ian Bolton]

[-- Attachment #1: Type: text/plain, Size: 1697 bytes --]

I am in the process of fixing PR44328
(http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44328)

The problem is that gen_inbound_check in tree-switch-conversion.c subtracts
info.range_min from info.index_expr, which can cause the MIN and MAX values
for info.index_expr to become invalid.

For example:


typedef enum {
  FIRST = 0,
  SECOND,
  THIRD,
  FOURTH
} ExampleEnum;

int dummy (const ExampleEnum e)
{
  int mode = 0;
  switch (e)
  {
    case SECOND: mode = 20; break;
    case THIRD: mode = 30; break;
    case FOURTH: mode = 40; break;
  }
  return mode;
}


tree-switch-conversion would like to create a lookup table for this, so
that SECOND maps to entry 0, THIRD maps to entry 1 and FOURTH maps to
entry 2.  It achieves this by subtracting SECOND from index_expr.  The
problem is that after the subtraction, the type of the result can have a
value outside the range 0-3.

Later, when tree-vrp.c sees the inbound check as being <= 2 with a possible
range for the type as 0-3, it converts the <=2 into a != 3, which is
totally wrong.  If e==FIRST, then we can end up looking for entry 255 in
the lookup table!

I think the solution is to update the type of the result of the subtraction
to show that it is no longer in the range 0-3, but I have had trouble
implementing this.  The attached patch (based off 4.5 branch) shows my
current approach, but I ran into LTO issues:

lto1: internal compiler error: in lto_get_pickled_tree, at lto-streamer-in.c

I am guessing this is because the debug info for the type does not match
the new range I have set for it.

Is there a *right* way to update the range such that LTO doesn't get
unhappy?  (Maybe a cast with fold_convert_loc would be right?)

[-- Attachment #2: pr44328.gcc4.5.fix.patch --]
[-- Type: application/octet-stream, Size: 1184 bytes --]

Index: gcc/tree-switch-conversion.c
===================================================================
--- gcc/tree-switch-conversion.c	(revision 162573)
+++ gcc/tree-switch-conversion.c	(working copy)
@@ -721,6 +721,21 @@
 
   bound = fold_convert_loc (loc, utype, info.range_size);
   cond_stmt = gimple_build_cond (LE_EXPR, tmp_u_2, bound, NULL_TREE, NULL_TREE);
+
+  /* Check that the subtraction does not cause underflow - if it does then we
+     must fix up the max value for the tmp_u expression used in the cond_stmt,
+     so that simplify_cond_using_ranges() in tree-vrp.c has the correct value
+     ranges to play with.  */
+  if ((TREE_INT_CST_LOW(TYPE_MIN_VALUE (TREE_TYPE(tmp_u_2)))
+       - TREE_INT_CST_LOW(ulb))
+     > TREE_INT_CST_LOW(TYPE_MIN_VALUE (TREE_TYPE(tmp_u_2))))
+    {
+      TYPE_MAX_VALUE (TREE_TYPE (gimple_cond_lhs(cond_stmt)))
+        = build_int_cst (TREE_TYPE(gimple_cond_lhs(cond_stmt)),
+                         TREE_INT_CST_LOW(TYPE_MIN_VALUE (TREE_TYPE(tmp_u_2)))
+                         - TREE_INT_CST_LOW(ulb)); 
+    }
+
   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
   update_stmt (cond_stmt);
 

Re: Question about tree-switch-conversion.c

[Richard Guenther]

On Tue, Aug 10, 2010 at 6:48 PM, Ian Bolton <Ian.Bolton@arm.com> wrote:
> I am in the process of fixing PR44328
> (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44328)
>
> The problem is that gen_inbound_check in tree-switch-conversion.c subtracts
> info.range_min from info.index_expr, which can cause the MIN and MAX values
> for info.index_expr to become invalid.
>
> For example:
>
>
> typedef enum {
>  FIRST = 0,
>  SECOND,
>  THIRD,
>  FOURTH
> } ExampleEnum;
>
> int dummy (const ExampleEnum e)
> {
>  int mode = 0;
>  switch (e)
>  {
>    case SECOND: mode = 20; break;
>    case THIRD: mode = 30; break;
>    case FOURTH: mode = 40; break;
>  }
>  return mode;
> }
>
>
> tree-switch-conversion would like to create a lookup table for this, so
> that SECOND maps to entry 0, THIRD maps to entry 1 and FOURTH maps to
> entry 2.  It achieves this by subtracting SECOND from index_expr.  The
> problem is that after the subtraction, the type of the result can have a
> value outside the range 0-3.
>
> Later, when tree-vrp.c sees the inbound check as being <= 2 with a possible
> range for the type as 0-3, it converts the <=2 into a != 3, which is
> totally wrong.  If e==FIRST, then we can end up looking for entry 255 in
> the lookup table!
>
> I think the solution is to update the type of the result of the subtraction
> to show that it is no longer in the range 0-3, but I have had trouble
> implementing this.  The attached patch (based off 4.5 branch) shows my
> current approach, but I ran into LTO issues:
>
> lto1: internal compiler error: in lto_get_pickled_tree, at lto-streamer-in.c
>
> I am guessing this is because the debug info for the type does not match
> the new range I have set for it.
>
> Is there a *right* way to update the range such that LTO doesn't get
> unhappy?  (Maybe a cast with fold_convert_loc would be right?)

The fix is to always use a standard unsigned integer type for the new index
value.  lang_hooks.types.type_for_mode (TYPE_MODE (old-idx-type), 1)
would give you one.

Richard.