[C PATCH] Various c_do_switch_warnings improvements

[Roger Sayle <roger at eyesopen dot com>]

The following patch addresses both the potential quadratic behaviour
of c-common.c's c_do_switch_warnings and resolves a diagnostic
regression from gcc-3.4.

My recent patch to avoid compilation warnings in c-parser.c, led me
to investigate why we were no longer issuing warnings from mainline,
and the possibility of simultaneously fixing PR c/25995.  Ultimately,
I've discovered 25995 isn't really bug and the c-parser.c regression
is elsewhere in the compiler, but along the way I managed to clean-up
the code to remove potentially quadratic behaviour, avoid undocumented
use of tree_common flags and fix a missed diagnostic regression from
the gcc-3.4.

The task is that given the set of literals of an enumerated type,
and a set of case values/ranges over that type, we need to test (i)
whether every literal is handled in the switch, and (ii) whether
every case value, or upper/lower bound of case range is a valid
enumeration literal.  The existing algorithm works by inserting all
of the case values/ranges into a splay-tree and then for each
enumeration literal probing the splay tree.

If the literal lookup fails, we issue a warning, and this implements
test (i).  The far more interesting case is test (ii), where we check
whether every case value/bound is an enumeration literal.  This is
done as a traversal of the splay tree as a second pass.

To prevent quadratic behaviour in the common case (of just values,
not ranges), the current code cleverly abuses the TREE_ADDRESSABLE flag
on the CASE_LABEL_EXPR during the lookup pass, to record that the value
was seen during the probing into the splay tree.  The problems are that
the logic for setting TREE_ADDRESSABLE for the lower-bound of ranges
is incorrect, and secondly because we're not recording whether the
upper bound of a range is seen, every upper bound requires a linear
scan of a TREE_LIST of enumeration literals to see whether it's valid.
As described in the comments in the code, this has O(N^2) worst case.


The logic error in recording the lower bound can be seen in the
testcase below, which issued an error for the use of "1" in gcc-3.4,
but no longer does on mainline:

typedef enum { a = 2 } T;

void foo()
{
    T x = a;
    switch(x) {
    case a ... 3: break;  /* Works fine, but quadratic worst case.  */
    }
    switch(x) {
    case 1 ... a: break;  /* Regression, no longer warns on mainline.  */
    }
}


The reorganization below uses the same temporary visit/seen flag trick
for the upper bound as we currently use of the lower bound and discrete
values.  However, instead of covertly abusing TREE_ADDRESSABLE, we
legitimize and document this use by introducing new CASE_HIGH_SEEN and
CASE_LOW_SEEN accessor macros in tree.h.

Next, we improve the splay-tree lookup logic, where because we've already
warned about overlapping ranges and organized case values in increasing
order via the splay tree, the look-up of each literal either matches
exactly the case/value or lower-bound, or is in the range covered by
the predecessor case.  The current implement is overly generic (a.k.a.
inefficient) as it appears to be derived/cut'n'paste from the code to
spot overlapping ranges.  There's no never a need to look up a literal's
sucessor.

The previous logic error was that we'd set TREE_ADDRESSABLE on the
predecessor's lower bound if the label was in the range.  This of
course is incorrect if the literal isn't the lower bound, i.e. when
the first value probe should have found something.  The extension
to upper bounds is simply to reuse the result of the existing
"literal <= upper_bound" comparison, such that if "literal ==
upper_bound", we record the fact with CASE_HIGH_SEEN.

One further improvement to this subroutine, was the feature that we
didn't bother testing anything previously if the controlling expression
of the switch was a constant.  Of course, it makes no sense to warn
about "foo" being unhandled, if the switch expression is the constant
"bar".  However, this completely ignoring the switch is too heavy a
hammer, that means we'd never warn that one of the elements of the switch
wasn't a literal, and we'd even fail to warn when the switch constant
wasn't handled.  This is refined below, by performing the usual checks but
only issuing the not-handled error when the unhandled literal is the
dispatched constant.



The following patch has been tested on x86_64-unknown-linux-gnu with a
full "make bootstrap", all default languages, and regression tested with
a top-level "make -k check" with no new failures.

Ok for mainline?  [I'll self-approve the tree.h change if the rest of
the patch is acceptable to the C front-end maintainers.]

Thanks in advance,



2006-07-08  Roger Sayle  <roger@eyesopen.com>

	* tree.h (CASE_LOW_SEEN, CASE_HIGH_SEEN): New macros for manipulating
	temporary visit flags on CASE_LABEL_EXPRs.
	* c-common.c (match_case_to_enum): Add function comment.  Avoid
	O(N) loop, by looking up both CASE_LOW_SEEN and CASE_HIGH_SEEN.
	(c_do_switch_warnings):  Reorganize to record CASE_LOW_SEEN and
	CASE_HIGH_SEEN for enumerated types.  If the switch expression is
	a constant, only warn if that constant value isn't handled.

	* gcc.dg/Wswitch-enum-2.c: New test case.
	* gcc.dg/Wswitch-enum-3.c: Likewise.


Index: tree.h
===================================================================
*** tree.h	(revision 115243)
--- tree.h	(working copy)
*************** struct tree_common GTY(())
*** 395,400 ****
--- 395,401 ----
  	   In a STMT_EXPR, it means we want the result of the enclosed
  	   expression.
         CALL_EXPR_TAILCALL in CALL_EXPR
+        CASE_LOW_SEEN in CASE_LABEL_EXPR

     static_flag:

*************** struct tree_common GTY(())
*** 413,418 ****
--- 414,420 ----
         EH_FILTER_MUST_NOT_THROW in EH_FILTER_EXPR
         TYPE_REF_CAN_ALIAS_ALL in
             POINTER_TYPE, REFERENCE_TYPE
+        CASE_HIGH_SEEN in CASE_LABEL_EXPR

     public_flag:

*************** extern void omp_clause_range_check_faile
*** 1024,1029 ****
--- 1026,1036 ----
     call optimizations.  */
  #define CALL_EXPR_TAILCALL(NODE) (CALL_EXPR_CHECK(NODE)->common.addressable_flag)

+ /* Used as a temporary field on a CASE_LABEL_EXPR to indicate that the
+    CASE_LOW operand has been processed.  */
+ #define CASE_LOW_SEEN(NODE) \
+   (CASE_LABEL_EXPR_CHECK (NODE)->common.addressable_flag)
+
  /* In a VAR_DECL, nonzero means allocate static storage.
     In a FUNCTION_DECL, nonzero if function has been defined.
     In a CONSTRUCTOR, nonzero means allocate static storage.
*************** extern void omp_clause_range_check_faile
*** 1037,1042 ****
--- 1044,1054 ----
     of its scope.  */
  #define CLEANUP_EH_ONLY(NODE) ((NODE)->common.static_flag)

+ /* Used as a temporary field on a CASE_LABEL_EXPR to indicate that the
+    CASE_HIGH operand has been processed.  */
+ #define CASE_HIGH_SEEN(NODE) \
+   (CASE_LABEL_EXPR_CHECK (NODE)->common.static_flag)
+
  /* In an expr node (usually a conversion) this means the node was made
     implicitly and should not lead to any sort of warning.  In a decl node,
     warnings concerning the decl should be suppressed.  This is used at
Index: c-common.c
===================================================================
*** c-common.c	(revision 115243)
--- c-common.c	(working copy)
*************** match_case_to_enum_1 (tree key, tree typ
*** 3797,3802 ****
--- 3797,3805 ----
  	     CASE_LABEL (label), buf, type);
  }

+ /* Subroutine of c_do_switch_warnings, called via splay_tree_foreach.
+    Used to verify that case values match up with enumerator values.  */
+
  static int
  match_case_to_enum (splay_tree_node node, void *data)
  {
*************** match_case_to_enum (splay_tree_node node
*** 3807,3832 ****
    if (!CASE_LOW (label))
      return 0;

!   /* If TREE_ADDRESSABLE is not set, that means CASE_LOW did not appear
       when we did our enum->case scan.  Reset our scratch bit after.  */
!   if (!TREE_ADDRESSABLE (label))
      match_case_to_enum_1 (CASE_LOW (label), type, label);
    else
!     TREE_ADDRESSABLE (label) = 0;

!   /* If CASE_HIGH is non-null, we have a range.  Here we must search.
!      Note that the old code in stmt.c did not check for the values in
!      the range either, just the endpoints.  */
    if (CASE_HIGH (label))
      {
!       tree chain, key = CASE_HIGH (label);
!
!       for (chain = TYPE_VALUES (type);
! 	   chain && !tree_int_cst_equal (key, TREE_VALUE (chain));
! 	   chain = TREE_CHAIN (chain))
! 	continue;
!       if (!chain)
! 	match_case_to_enum_1 (key, type, label);
      }

    return 0;
--- 3810,3831 ----
    if (!CASE_LOW (label))
      return 0;

!   /* If CASE_LOW_SEEN is not set, that means CASE_LOW did not appear
       when we did our enum->case scan.  Reset our scratch bit after.  */
!   if (!CASE_LOW_SEEN (label))
      match_case_to_enum_1 (CASE_LOW (label), type, label);
    else
!     CASE_LOW_SEEN (label) = 0;

!   /* If CASE_HIGH is non-null, we have a range.  If CASE_HIGH_SEEN is
!      not set, that means that CASE_HIGH did not appear when we did our
!      enum->case scan.  Reset our scratch bit after.  */
    if (CASE_HIGH (label))
      {
!       if (!CASE_HIGH_SEEN (label))
! 	match_case_to_enum_1 (CASE_HIGH (label), type, label);
!       else
! 	CASE_HIGH_SEEN (label) = 0;
      }

    return 0;
*************** c_do_switch_warnings (splay_tree cases,
*** 3844,3849 ****
--- 3843,3850 ----
  		      tree type, tree cond)
  {
    splay_tree_node default_node;
+   splay_tree_node node;
+   tree chain;

    if (!warn_switch && !warn_switch_enum && !warn_switch_default)
      return;
*************** c_do_switch_warnings (splay_tree cases,
*** 3853,3931 ****
      warning (OPT_Wswitch_default, "%Hswitch missing default case",
  	     &switch_location);

    /* If the switch expression was an enumerated type, check that
       exactly all enumeration literals are covered by the cases.
       The check is made when -Wswitch was specified and there is no
       default case, or when -Wswitch-enum was specified.  */
!   if (((warn_switch && !default_node) || warn_switch_enum)
!       && type && TREE_CODE (type) == ENUMERAL_TYPE
!       && TREE_CODE (cond) != INTEGER_CST)
!     {
!       tree chain;
!
!       /* The time complexity here is O(N*lg(N)) worst case, but for the
! 	 common case of monotonically increasing enumerators, it is
! 	 O(N), since the nature of the splay tree will keep the next
! 	 element adjacent to the root at all times.  */
!
!       for (chain = TYPE_VALUES (type); chain; chain = TREE_CHAIN (chain))
! 	{
! 	  splay_tree_node node
! 	    = splay_tree_lookup (cases, (splay_tree_key) TREE_VALUE (chain));
! 	  if (!node)
! 	    {
! 	      tree low_value = TREE_VALUE (chain);
! 	      splay_tree_node low_bound;
! 	      splay_tree_node high_bound;
! 	      /* Even though there wasn't an exact match, there might be a
! 		 case range which includes the enumator's value.  */
! 	      low_bound = splay_tree_predecessor (cases,
! 						  (splay_tree_key) low_value);
! 	      high_bound = splay_tree_successor (cases,
! 						 (splay_tree_key) low_value);
!
! 	      /* It is smaller than the LOW_VALUE, so there is no need to check
! 		 unless the LOW_BOUND is in fact itself a case range.  */
! 	      if (low_bound
! 		  && CASE_HIGH ((tree) low_bound->value)
! 		  && tree_int_cst_compare (CASE_HIGH ((tree) low_bound->value),
! 					    low_value) >= 0)
! 		node = low_bound;
! 	      /* The low end of that range is bigger than the current value. */
! 	      else if (high_bound
! 		       && (tree_int_cst_compare ((tree) high_bound->key,
! 						 low_value)
! 			   <= 0))
! 		node = high_bound;
! 	    }
! 	  if (node)
! 	    {
! 	      /* Mark the CASE_LOW part of the case entry as seen, so
! 		 that we save time later.  Choose TREE_ADDRESSABLE
! 		 randomly as a bit that won't have been set to-date.  */
! 	      tree label = (tree) node->value;
! 	      TREE_ADDRESSABLE (label) = 1;
! 	    }
! 	  else
  	    {
! 	      /* Warn if there are enumerators that don't correspond to
! 		 case expressions.  */
! 	      warning (0, "%Henumeration value %qE not handled in switch",
! 		       &switch_location, TREE_PURPOSE (chain));
  	    }
  	}

!       /* Warn if there are case expressions that don't correspond to
! 	 enumerators.  This can occur since C and C++ don't enforce
! 	 type-checking of assignments to enumeration variables.
!
! 	 The time complexity here is O(N**2) worst case, since we've
! 	 not sorted the enumeration values.  However, in the absence
! 	 of case ranges this is O(N), since all single cases that
! 	 corresponded to enumerations have been marked above.  */

!       splay_tree_foreach (cases, match_case_to_enum, type);
      }
  }

  /* Finish an expression taking the address of LABEL (an
--- 3854,3932 ----
      warning (OPT_Wswitch_default, "%Hswitch missing default case",
  	     &switch_location);

+   /* From here on, we only care about about enumerated types.  */
+   if (!type || TREE_CODE (type) != ENUMERAL_TYPE)
+     return;
+
    /* If the switch expression was an enumerated type, check that
       exactly all enumeration literals are covered by the cases.
       The check is made when -Wswitch was specified and there is no
       default case, or when -Wswitch-enum was specified.  */
!
!   if (!warn_switch_enum
!       && !(warn_switch && !default_node))
!     return;
!
!   /* Clearing COND if it is not an integer constant simplifies
!      the tests inside the loop below.  */
!   if (TREE_CODE (cond) != INTEGER_CST)
!     cond = NULL_TREE;
!
!   /* The time complexity here is O(N*lg(N)) worst case, but for the
!       common case of monotonically increasing enumerators, it is
!       O(N), since the nature of the splay tree will keep the next
!       element adjacent to the root at all times.  */
!
!   for (chain = TYPE_VALUES (type); chain; chain = TREE_CHAIN (chain))
!     {
!       tree value = TREE_VALUE (chain);
!       node = splay_tree_lookup (cases, (splay_tree_key) value);
!       if (node)
! 	{
! 	  /* Mark the CASE_LOW part of the case entry as seen.  */
! 	  tree label = (tree) node->value;
! 	  CASE_LOW_SEEN (label) = 1;
! 	  continue;
! 	}
!
!       /* Even though there wasn't an exact match, there might be a
! 	 case range which includes the enumator's value.  */
!       node = splay_tree_predecessor (cases, (splay_tree_key) value);
!       if (node && CASE_HIGH ((tree) node->value))
! 	{
! 	  tree label = (tree) node->value;
! 	  int cmp = tree_int_cst_compare (CASE_HIGH (label), value);
! 	  if (cmp >= 0)
  	    {
! 	      /* If we match the upper bound exactly, mark the CASE_HIGH
! 		 part of the case entry as seen.  */
! 	      if (cmp == 0)
! 		CASE_HIGH_SEEN (label) = 1;
! 	      continue;
  	    }
  	}

!       /* We've now determined that this enumerated literal isn't
! 	 handled by the case labels of the switch statement.  */

!       /* If the switch expression is a constant, we only really care
! 	 about whether that constant is handled by the switch.  */
!       if (cond && tree_int_cst_compare (cond, value))
! 	continue;
!
!       warning (0, "%Henumeration value %qE not handled in switch",
! 	       &switch_location, TREE_PURPOSE (chain));
      }
+
+   /* Warn if there are case expressions that don't correspond to
+      enumerators.  This can occur since C and C++ don't enforce
+      type-checking of assignments to enumeration variables.
+
+      The time complexity here is now always O(N) worst case, since
+      we should have marked both the lower bound and upper bound of
+      every disjoint case label, with CASE_LOW_SEEN and CASE_HIGH_SEEN
+      above.  This scan also resets those fields.  */
+   splay_tree_foreach (cases, match_case_to_enum, type);
  }

  /* Finish an expression taking the address of LABEL (an


/* { dg-do compile } */
/* { dg-options "-O2 -Wswitch-enum" } */

typedef enum { a = 2 } T;

int main()
{
    T x = a;
    switch(x)
    {
    case a ... 3: /* { dg-warning "case value '3' not in enumerated" "3" } */
        break;
    }
    switch(x)
    {
    case 1 ... a: /* { dg-warning "case value '1' not in enumerated" "1" } */
        break;
    }
    return 0;
}


/* { dg-do compile } */
/* { dg-options "-O2 -Wswitch-enum" } */

typedef enum { a = 2 } T;

int main()
{
    switch((T)a) /* { dg-warning "enumeration value 'a' not handled" "a" } */
    {
    case 1: /* { dg-warning "case value '1' not in enumerated" "1" } */
        break;
    }
    return 0;
}



Roger
--