Value Range Propagation Pass Status

Joern Rennecke amylaar@cygnus.co.uk
Mon Feb 7 11:32:00 GMT 2000


> I'd like the range check for switches on certain enums to be eliminated.
> In C, enums can actually have a value that's not in the enumeration list
> which defeats the optimisation: you can't assume every case is covered.
> However, there are two approaches to eliminating the bounds check:
> 
>    - __builtin_assume (x < 6);
> 
>    - __attribute__ ((bounded)) enum Foo { A, B, C} foo;
> 
> I like the second better for enum types, but the first is a more general
> purpose solution.

I suppose it would be best to have both ;-)

I had a patch some four yearts ago that optimized switches on enums
with the assumption that they were all bounded when you passed a special
option.
It also recognized the case when the jump table needed just a little bit more
padding to get rid of the range check.
Maybe you can spruce up this patch a bit and change to to use a type
attribute instead of the invocation option.

>From amylaar Sat Jul  8 11:15:07 1995
Return-Path: <amylaar>
Message-Id: <m0sUVyb-000D32C@meolyon>
Date: Sat, 8 Jul 95 11:15 MET DST
From: amylaar (Joern Rennecke)
To: bug-gcc@prep.ai.mit.edu
Subject: New gcc optimization option: -fomit-default-branch
Bcc: amylaar
Status: RO

For an example what this option can do to your code, look at what
the patched gcc does to the following funktion with and without
-fomit-default-branch . There is also a patch to gcc.1 in the diff.

enum {a=100,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t} z;

void x() {
  switch(z) {
  case a: case b: case c: case e: case f: case g:
  case h: case i: case j:
    z++;
  case k: case n: case o: case q: case r: case s:
    z++;
  case l: case m: case p:
  case t:
  }
}

One Issue I haven't looked at is why the resulting instruction sequence

        addl $-100,%eax
        jmp *.L45(,%eax,4)

is not combined later into a single instruction. I would have assumend that
the add would go into the memory adressing.

	Joern Rennecke


<original diff deleted because it had some problems>

>From jwminhh!mwhh!cs.tu-berlin.de!amylaar Tue Jul 11 10:55:47 1995
Return-Path: <jwminhh!mwhh!cs.tu-berlin.de!amylaar>
Received: by jwminhh.Hanse.DE with uucp(Smail3.1.28.1 #1)
	id m0sVSvq-000MveC; Tue, 11 Jul 95 02:12 MET DST
Received: from mail.hanse.de by mwhh.Hanse.DE with smtp
	(Smail3.1.28.1 #20) id m0sVPEj-000HyhC; Mon, 10 Jul 95 21:15 GMT+0100
Received: from mail.cs.tu-berlin.de [130.149.17.13] by mail.hanse.de with smtp
	  for <amylaar@meolyon.hanse.de> id <m0sVNwd-0004hNC@mail.hanse.de>; Mon, 10 Jul 95 20:52 MET DST
Received: from haydn.cs.tu-berlin.de (amylaar@haydn.cs.tu-berlin.de [130.149.29.45]) by mail.cs.tu-berlin.de (8.6.12/8.6.12) with ESMTP id UAA01887; Mon, 10 Jul 1995 20:52:17 +0200
From: Joern Rennecke <amylaar@cs.tu-berlin.de>
Received: (amylaar@localhost) by haydn.cs.tu-berlin.de (8.6.12/8.6.9) id UAA11206; Mon, 10 Jul 1995 20:52:12 +0200
Message-Id: <199507101852.UAA11206@haydn.cs.tu-berlin.de>
Subject: New gcc optimization option: -fomit-default-branch - correction
To: bug-gcc@prep.ai.mit.edu
Date: Mon, 10 Jul 1995 20:52:11 +0200 (MET DST)
X-Mailer: ELM [version 2.4 PL24]
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset=US-ASCII
Status: RO

While sleeping over it, it occured to me that I might have clobbered a
program invariant in case of an error. Checking it in the source I found
not only that to be true, but also that I needed to assign orig_minval,
and that my indentation didn't blend in right.

Appended is the corrected diff.

diff -cp --recursive gcc-2.7.0/ChangeLog gcc-2.7.0-x/ChangeLog
*** gcc-2.7.0/ChangeLog	Sat Jul  8 01:54:05 1995
--- gcc-2.7.0-x/ChangeLog	Sat Jul  8 10:47:14 1995
***************
*** 1,3 ****
--- 1,7 ----
+ Sat Jul  8 10:33:59 1995  J"orn Rennecke  (amylaar@meolyon.hanse.de)
+ 	* New optimization option -fomit-default-branch . Most of it
+ 	is in expand_end_case(). Doc in gcc.1
+ 
  Fri Jun 16 06:54:03 1995  Richard Kenner  (kenner@vlsi1.ultra.nyu.edu)
  
  	* alpha.c (alpha_builtin_saveregs): Use ptr_mode and conversions
diff -cp --recursive gcc-2.7.0/expr.c gcc-2.7.0-x/expr.c
*** gcc-2.7.0/expr.c	Sat Jul  8 01:56:19 1995
--- gcc-2.7.0-x/expr.c	Sun Jul  9 04:05:28 1995
*************** do_store_flag (exp, target, mode, only_c
*** 9888,9896 ****
     index value is out of range.  */
  
  void
! do_tablejump (index, mode, range, table_label, default_label)
       rtx index, range, table_label, default_label;
       enum machine_mode mode;
  {
    register rtx temp, vector;
  
--- 9888,9897 ----
     index value is out of range.  */
  
  void
! do_tablejump (index, mode, range, table_label, default_label, default_dropped)
       rtx index, range, table_label, default_label;
       enum machine_mode mode;
+      int default_dropped;
  {
    register rtx temp, vector;
  
*************** do_tablejump (index, mode, range, table_
*** 9902,9909 ****
       or equal to the minimum value of the range and less than or equal to
       the maximum value of the range.  */
  
!   emit_cmp_insn (index, range, GTU, NULL_RTX, mode, 1, 0);
!   emit_jump_insn (gen_bgtu (default_label));
  
    /* If index is in range, it must fit in Pmode.
       Convert to Pmode so we can index with it.  */
--- 9903,9913 ----
       or equal to the minimum value of the range and less than or equal to
       the maximum value of the range.  */
  
!   if (!default_dropped)
!     {
!       emit_cmp_insn (index, range, GTU, NULL_RTX, mode, 1, 0);
!       emit_jump_insn (gen_bgtu (default_label));
!     }
  
    /* If index is in range, it must fit in Pmode.
       Convert to Pmode so we can index with it.  */
diff -cp --recursive gcc-2.7.0/expr.h gcc-2.7.0-x/expr.h
*** gcc-2.7.0/expr.h	Sat Jul  8 01:56:20 1995
--- gcc-2.7.0-x/expr.h	Sat Jul  8 06:09:43 1995
*************** extern rtx compare_from_rtx PROTO((rtx, 
*** 712,718 ****
  				   enum machine_mode, rtx, int));
  
  /* Generate a tablejump instruction (used for switch statements).  */
! extern void do_tablejump PROTO((rtx, enum machine_mode, rtx, rtx, rtx));
  
  #ifdef TREE_CODE
  /* rtl.h and tree.h were included.  */
--- 712,718 ----
  				   enum machine_mode, rtx, int));
  
  /* Generate a tablejump instruction (used for switch statements).  */
! extern void do_tablejump PROTO((rtx, enum machine_mode, rtx, rtx, rtx, int));
  
  #ifdef TREE_CODE
  /* rtl.h and tree.h were included.  */
diff -cp --recursive gcc-2.7.0/flags.h gcc-2.7.0-x/flags.h
*** gcc-2.7.0/flags.h	Sat Jul  8 01:56:23 1995
--- gcc-2.7.0-x/flags.h	Sat Jul  8 06:31:13 1995
*************** extern int flag_delayed_branch;
*** 299,304 ****
--- 299,311 ----
  
  extern int flag_short_temps;
  
+ /* Nonzero means that the type passed to a switch should be used for
+    optimization.  This makes switching on an uninitialized variable or
+    on an out-of-range enum value have undefined effects, but it saves
+    a comparison and a branch when it comes into effect.			  */
+ 
+ extern int flag_drop_default_branch;
+ 
  /* Nonzero means pretend it is OK to examine bits of target floats,
     even if that isn't true.  The resulting code will have incorrect constants,
     but the same series of instructions that the native compiler would make.  */
diff -cp --recursive gcc-2.7.0/gcc.1 gcc-2.7.0-x/gcc.1
*** gcc-2.7.0/gcc.1	Sat Jul  8 01:56:26 1995
--- gcc-2.7.0-x/gcc.1	Sat Jul  8 10:27:26 1995
*************** in the following sections.
*** 245,250 ****
--- 245,251 ----
  \-fno\-function\-cse
  \-fno\-inline
  \-fno\-peephole
+ \-fomit\-default\-branch
  \-fomit\-frame\-pointer
  \-frerun\-cse\-after\-loop
  \-fschedule\-insns
*************** This option should never be turned on by
*** 2529,2534 ****
--- 2530,2555 ----
  it can result in incorrect output for programs which depend on
  an exact implementation of IEEE or ANSI rules/specifications for
  math functions.
+ .TP
+ .B \-fomit-default-branch
+ This option makes gcc assume that the unpromoted type given to a switch()
+ instruction is correct,
+ and it tries to eleminate the branch that is usually used
+ to handle all values that are outside the range of listed values. This
+ will always suceed if you pass an enum which highest and lowest member appear
+ as case labels.
+ .Sp
+ Before this optimization is made, it is checked that
+ all given case labels are inside the range of the passed value, ignoring
+ default promotions, and possibly giving an
+ .B error.
+ This is because you can only expect this option to
+ produce proper code if the passed value is consistent with its type.
+ This option should never be turned on by any `\|\c
+ .B \-O\c
+ \&\|' option since it results in undefined behaviour when enum types
+ or pointers to unions of ints of different sizes are used in a sloppy
+ way as switch() argument.
  .PP
  The following options control specific optimizations.  The `\|\c
  .B \-O2\c
diff -cp --recursive gcc-2.7.0/stmt.c gcc-2.7.0-x/stmt.c
*** gcc-2.7.0/stmt.c	Sat Jul  8 01:57:00 1995
--- gcc-2.7.0-x/stmt.c	Sun Jul  9 04:03:29 1995
*************** expand_end_case (orig_index)
*** 4882,4887 ****
--- 4882,4930 ----
        else
  	{
  	  int win = 0;
+ 	  int default_dropped = 0;
+ 
+ 	  if (flag_drop_default_branch)
+ 	    {
+ 	      /* If the range of case labels is larger than the range of the
+ 		 type, the programmer is in error; with -fdrop_default
+ 		 there is an implicit promise that arguments to switch won't
+ 		 hold invalid values (usually happens with enums, but on some
+ 		 hosts small types are represented as words).
+ 		 When using this flag, a switch on a garbage value has
+ 		 undefined behaviour.
+ 		 If the former range is smaller than the latter, we can't
+ 		 optimize the branch out. Alas, we may grow the range of
+ 		 case labels slightly to make it fit.			    */
+ 
+ 	      tree orig_type, type_min, type_max, missing, nocheck_range;
+ 
+ 	      orig_type = TREE_TYPE(orig_index);
+ 	      type_min = TYPE_MIN_VALUE(orig_type);
+ 	      type_max = TYPE_MAX_VALUE(orig_type);
+ 	      if (INT_CST_LT(minval, type_min) || INT_CST_LT(type_max, maxval))
+ 		{
+ 		  error("case value(s) outside range of used data type");
+ 		}
+ 	      else
+ 		{
+ 		  nocheck_range = fold (build (MINUS_EXPR, index_type,
+ 		      convert (index_type, type_max),
+ 		      convert (index_type, type_min)
+ 		    )
+ 		  );
+ 		  missing =
+ 		    fold (build (MINUS_EXPR, index_type, nocheck_range, range));
+ 		  if ((unsigned)
+ 			(TREE_INT_CST_HIGH(missing) | TREE_INT_CST_LOW(missing))
+ 			  <= 2)
+ 		    {
+ 		      range = nocheck_range;
+ 		      orig_minval = minval = convert (index_type, type_min);
+ 		      default_dropped = 1;
+ 		    }
+ 		}
+ 	    }
  #ifdef HAVE_casesi
  	  if (HAVE_casesi)
  	    {
*************** expand_end_case (orig_index)
*** 4902,4909 ****
  				      index_expr, minval);
  		  minval = integer_zero_node;
  		  index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
! 		  emit_cmp_insn (rangertx, index, LTU, NULL_RTX, omode, 1, 0);
! 		  emit_jump_insn (gen_bltu (default_label));
  		  /* Now we can safely truncate.  */
  		  index = convert_to_mode (index_mode, index, 0);
  		}
--- 4945,4955 ----
  				      index_expr, minval);
  		  minval = integer_zero_node;
  		  index = expand_expr (index_expr, NULL_RTX, VOIDmode, 0);
! 		  /* WARNING: the following test was not reached in testruns */
! 		  if (!default_dropped) {
! 		    emit_cmp_insn (rangertx, index, LTU, NULL_RTX, omode, 1, 0);
! 		    emit_jump_insn (gen_bltu (default_label));
! 		  }
  		  /* Now we can safely truncate.  */
  		  index = convert_to_mode (index_mode, index, 0);
  		}
*************** expand_end_case (orig_index)
*** 4960,4966 ****
  
  	      do_tablejump (index, TYPE_MODE (index_type),
  			    expand_expr (range, NULL_RTX, VOIDmode, 0),
! 			    table_label, default_label);
  	      win = 1;
  	    }
  #endif
--- 5006,5012 ----
  
  	      do_tablejump (index, TYPE_MODE (index_type),
  			    expand_expr (range, NULL_RTX, VOIDmode, 0),
! 			    table_label, default_label, default_dropped);
  	      win = 1;
  	    }
  #endif
diff -cp --recursive gcc-2.7.0/toplev.c gcc-2.7.0-x/toplev.c
*** gcc-2.7.0/toplev.c	Sat Jul  8 01:57:04 1995
--- gcc-2.7.0-x/toplev.c	Sat Jul  8 09:39:16 1995
*************** int flag_delayed_branch;
*** 462,467 ****
--- 462,469 ----
  
  int flag_short_temps;
  
+ int flag_drop_default_branch;
+ 
  /* Nonzero if we are compiling pure (sharable) code.
     Value is 1 if we are doing reasonable (i.e. simple
     offset into offset table) pic.  Value is 2 if we can
*************** struct { char *string; int *variable; in
*** 558,563 ****
--- 560,566 ----
    {"pic", &flag_pic, 1},
    {"PIC", &flag_pic, 2},
    {"fast-math", &flag_fast_math, 1},
+   {"omit-default-branch", &flag_drop_default_branch, 1},
    {"common", &flag_no_common, 0},
    {"inhibit-size-directive", &flag_inhibit_size_directive, 1},
    {"verbose-asm", &flag_verbose_asm, 1},




More information about the Gcc mailing list