* Huge compile time regressions
@ 2005-12-15 2:12 Steven Bosscher
2005-12-15 7:58 ` Daniel Berlin
0 siblings, 1 reply; 16+ messages in thread
From: Steven Bosscher @ 2005-12-15 2:12 UTC (permalink / raw)
To: gcc
Hi,
Someone caused a >10% compile time regression yesterday for CSiBE, see
http://www.csibe.org/draw-diag.php?branchid=mainline&flags=-Os&rel_flag=--none--&dataview=Timeline&finish_button=Finish&draw=sbs&view=1&basephp=l-sbs
Gr.
Steven
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: Huge compile time regressions
2005-12-15 2:12 Huge compile time regressions Steven Bosscher
@ 2005-12-15 7:58 ` Daniel Berlin
2005-12-16 13:46 ` Bernd Schmidt
2005-12-19 13:58 ` Huge compile time regressions Joern RENNECKE
0 siblings, 2 replies; 16+ messages in thread
From: Daniel Berlin @ 2005-12-15 7:58 UTC (permalink / raw)
To: Steven Bosscher; +Cc: gcc, Joern RENNECKE
On Thu, 2005-12-15 at 00:48 +0100, Steven Bosscher wrote:
> Hi,
>
> Someone caused a >10% compile time regression yesterday for CSiBE, see
> http://www.csibe.org/draw-diag.php?branchid=mainline&flags=-Os&rel_flag=--none--&dataview=Timeline&finish_button=Finish&draw=sbs&view=1&basephp=l-sbs
>
>
> Gr.
> Steven
>
This is very very bad.
Joern, i'd imagine this was your patch.
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: Huge compile time regressions
2005-12-15 7:58 ` Daniel Berlin
@ 2005-12-16 13:46 ` Bernd Schmidt
2006-01-05 22:06 ` Joern RENNECKE
2005-12-19 13:58 ` Huge compile time regressions Joern RENNECKE
1 sibling, 1 reply; 16+ messages in thread
From: Bernd Schmidt @ 2005-12-16 13:46 UTC (permalink / raw)
To: Daniel Berlin; +Cc: Steven Bosscher, gcc, Joern RENNECKE
Daniel Berlin wrote:
> On Thu, 2005-12-15 at 00:48 +0100, Steven Bosscher wrote:
>
>>Hi,
>>
>>Someone caused a >10% compile time regression yesterday for CSiBE, see
>>http://www.csibe.org/draw-diag.php?branchid=mainline&flags=-Os&rel_flag=--none--&dataview=Timeline&finish_button=Finish&draw=sbs&view=1&basephp=l-sbs
>>
>>
>>Gr.
>>Steven
>>
>
>
> This is very very bad.
>
> Joern, i'd imagine this was your patch.
Seems to be. I can reproduce a massive compile-time difference (up to a
50% increase) between 108479 and 108480, but I'm having trouble figure
out where exactly that time goes.
Joern, please revert the patch for now. I'll be away for three weeks;
if no one else works with you on this in the meantime I'll help once I'm
back.
Bernd
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: Huge compile time regressions
2005-12-15 7:58 ` Daniel Berlin
2005-12-16 13:46 ` Bernd Schmidt
@ 2005-12-19 13:58 ` Joern RENNECKE
1 sibling, 0 replies; 16+ messages in thread
From: Joern RENNECKE @ 2005-12-19 13:58 UTC (permalink / raw)
To: Daniel Berlin; +Cc: Steven Bosscher, gcc, rth
Daniel Berlin wrote:
>On Thu, 2005-12-15 at 00:48 +0100, Steven Bosscher wrote:
>
>
>>Hi,
>>
>>Someone caused a >10% compile time regression yesterday for CSiBE, see
>>http://www.csibe.org/draw-diag.php?branchid=mainline&flags=-Os&rel_flag=--none--&dataview=Timeline&finish_button=Finish&draw=sbs&view=1&basephp=l-sbs
>>
>>
>>Gr.
>>Steven
>>
>>
>>
>
>This is very very bad.
>
>Joern, i'd imagine this was your patch.
>
>
I think this is related to using register liveness information from
flow. My original if-conversion patch
http://gcc.gnu.org/ml/gcc-patches/2004-01/msg03281.html used a simple
linear-time
algorithm to identify registers that are local to each basic block.
I can think of two things that could cause a noticable slowdown:
- comparison of global_live_at_end in struct_equiv_init. Most call
sites call gcc_unreachable when struct_equiv_init fails. If an
additional parameter is passed into struct_equiv_init to tell if the
the comparison may fail, we can optimize the sanity check out for
!ENABLE_CHECKING.
- The call to update_life_info_in_dirty_blocks when one of the compared
blocks is dirty. I'm not sure if we could get away with doing a local
update, and/or starting the update only for the blocks under
consideration. If we don't have to do the global_live_at_end
comparison, we can probably also skip the update if only one of the
blocks is dirty, and use the global_live_at_end from the block that is
not dirty.
A further improvement might be to remove the regset comparison from
struct_equiv_init altogether, and only make sure we use a
global_live_at_end that is right for at least one of the
blocks. The regsets can be compared later when we have matched all the
edges, maybe even the entire block.
We could also go back to makling sure we have consistent data flow
information at the start of the pass, and keep the bits that we need
up-to-date as we go along.
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: Huge compile time regressions
2005-12-16 13:46 ` Bernd Schmidt
@ 2006-01-05 22:06 ` Joern RENNECKE
2006-01-05 22:10 ` Joern RENNECKE
0 siblings, 1 reply; 16+ messages in thread
From: Joern RENNECKE @ 2006-01-05 22:06 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: Daniel Berlin, Steven Bosscher, gcc
[-- Attachment #1: Type: text/plain, Size: 211 bytes --]
I've found that the most striking compilation time increase was for
flex / parse.c, which is a bison parser.
-Os compilation for i686-pc-linux-gnu X sh-elf --disable-checking went
from 0.95 to 4.5 seconds.
[-- Attachment #2: parse.i --]
[-- Type: text/plain, Size: 78176 bytes --]
# 1 "/mnt/scratch/CSiBE/src/./flex-2.5.31/parse.c"
# 1 "<built-in>"
# 1 "<command line>"
# 1 "/mnt/scratch/CSiBE/src/./flex-2.5.31/parse.c"
# 29 "parse.y"
# 72 "parse.y"
# 1 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 1
# 39 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
# 1 "/mnt/scratch/CSiBE/src/./flex-2.5.31/config.h" 1
# 40 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 1 3
# 29 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/_ansi.h" 1 3
# 15 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/_ansi.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/newlib.h" 1 3
# 16 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/_ansi.h" 2 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/config.h" 1 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/ieeefp.h" 1 3
# 5 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/config.h" 2 3
# 17 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/_ansi.h" 2 3
# 30 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 2 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stddef.h" 1 3 4
# 214 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stddef.h" 3 4
typedef unsigned int size_t;
# 35 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 2 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stdarg.h" 1 3 4
# 43 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stdarg.h" 3 4
typedef __builtin_va_list __gnuc_va_list;
# 38 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 2 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 1 3
# 13 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/_ansi.h" 1 3
# 14 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 2 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/_types.h" 1 3
# 12 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/_types.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/lock.h" 1 3
typedef int _LOCK_T;
typedef int _LOCK_RECURSIVE_T;
# 13 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/_types.h" 2 3
typedef long _off_t;
__extension__ typedef long long _off64_t;
typedef int _ssize_t;
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stddef.h" 1 3 4
# 355 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stddef.h" 3 4
typedef unsigned int wint_t;
# 25 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/_types.h" 2 3
typedef struct
{
int __count;
union
{
wint_t __wch;
unsigned char __wchb[4];
} __value;
} _mbstate_t;
typedef _LOCK_RECURSIVE_T _flock_t;
typedef void *_iconv_t;
# 15 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 2 3
typedef unsigned long __ULong;
# 40 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 3
struct _Bigint
{
struct _Bigint *_next;
int _k, _maxwds, _sign, _wds;
__ULong _x[1];
};
struct __tm
{
int __tm_sec;
int __tm_min;
int __tm_hour;
int __tm_mday;
int __tm_mon;
int __tm_year;
int __tm_wday;
int __tm_yday;
int __tm_isdst;
};
struct _on_exit_args {
void * _fnargs[32];
void * _dso_handle[32];
__ULong _fntypes;
__ULong _is_cxa;
};
# 85 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 3
struct _atexit {
struct _atexit *_next;
int _ind;
void (*_fns[32])(void);
struct _on_exit_args _on_exit_args;
};
# 101 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 3
struct __sbuf {
unsigned char *_base;
int _size;
};
typedef long _fpos_t;
# 166 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 3
struct __sFILE {
unsigned char *_p;
int _r;
int _w;
short _flags;
short _file;
struct __sbuf _bf;
int _lbfsize;
void * _cookie;
int (*_read) (void * _cookie, char *_buf, int _n);
int (*_write) (void * _cookie, const char *_buf, int _n);
_fpos_t (*_seek) (void * _cookie, _fpos_t _offset, int _whence);
int (*_close) (void * _cookie);
struct __sbuf _ub;
unsigned char *_up;
int _ur;
unsigned char _ubuf[3];
unsigned char _nbuf[1];
struct __sbuf _lb;
int _blksize;
int _offset;
struct _reent *_data;
_flock_t _lock;
};
# 259 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 3
typedef struct __sFILE __FILE;
struct _glue
{
struct _glue *_next;
int _niobs;
__FILE *_iobs;
};
# 290 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 3
struct _rand48 {
unsigned short _seed[3];
unsigned short _mult[3];
unsigned short _add;
};
# 565 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 3
struct _reent
{
int _errno;
__FILE *_stdin, *_stdout, *_stderr;
int _inc;
char _emergency[25];
int _current_category;
const char *_current_locale;
int __sdidinit;
void (*__cleanup) (struct _reent *);
struct _Bigint *_result;
int _result_k;
struct _Bigint *_p5s;
struct _Bigint **_freelist;
int _cvtlen;
char *_cvtbuf;
union
{
struct
{
unsigned int _unused_rand;
char * _strtok_last;
char _asctime_buf[26];
struct __tm _localtime_buf;
int _gamma_signgam;
__extension__ unsigned long long _rand_next;
struct _rand48 _r48;
_mbstate_t _mblen_state;
_mbstate_t _mbtowc_state;
_mbstate_t _wctomb_state;
char _l64a_buf[8];
char _signal_buf[24];
int _getdate_err;
_mbstate_t _mbrlen_state;
_mbstate_t _mbrtowc_state;
_mbstate_t _mbsrtowcs_state;
_mbstate_t _wcrtomb_state;
_mbstate_t _wcsrtombs_state;
} _reent;
struct
{
unsigned char * _nextf[30];
unsigned int _nmalloc[30];
} _unused;
} _new;
struct _atexit *_atexit;
struct _atexit _atexit0;
void (**(_sig_func))(int);
struct _glue __sglue;
__FILE __sf[3];
};
# 799 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/reent.h" 3
extern struct _reent *_impure_ptr ;
extern struct _reent *const _global_impure_ptr ;
void _reclaim_reent (struct _reent *);
# 46 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 2 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 1 3
# 25 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/_types.h" 1 3
# 22 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/_types.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/limits.h" 1 3 4
# 23 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/_types.h" 2 3
typedef signed char __int8_t ;
typedef unsigned char __uint8_t ;
# 36 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/_types.h" 3
typedef signed short __int16_t;
typedef unsigned short __uint16_t;
# 46 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/_types.h" 3
typedef __int16_t __int_least16_t;
typedef __uint16_t __uint_least16_t;
# 58 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/_types.h" 3
typedef signed int __int32_t;
typedef unsigned int __uint32_t;
# 76 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/_types.h" 3
typedef __int32_t __int_least32_t;
typedef __uint32_t __uint_least32_t;
# 99 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/_types.h" 3
typedef signed long long __int64_t;
typedef unsigned long long __uint64_t;
# 26 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 2 3
# 69 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stddef.h" 1 3 4
# 152 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stddef.h" 3 4
typedef int ptrdiff_t;
# 326 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stddef.h" 3 4
typedef long int wchar_t;
# 70 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 2 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/types.h" 1 3
# 19 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/types.h" 3
typedef long int __off_t;
typedef int __pid_t;
__extension__ typedef long long int __loff_t;
# 71 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 2 3
# 92 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 3
typedef unsigned char u_char;
typedef unsigned short u_short;
typedef unsigned int u_int;
typedef unsigned long u_long;
typedef unsigned short ushort;
typedef unsigned int uint;
typedef unsigned long clock_t;
typedef long time_t;
struct timespec {
time_t tv_sec;
long tv_nsec;
};
struct itimerspec {
struct timespec it_interval;
struct timespec it_value;
};
typedef long daddr_t;
typedef char * caddr_t;
# 135 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 3
typedef unsigned short ino_t;
# 169 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 3
typedef short dev_t;
typedef long off_t;
typedef unsigned short uid_t;
typedef unsigned short gid_t;
typedef int pid_t;
typedef long key_t;
typedef _ssize_t ssize_t;
# 198 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 3
typedef unsigned int mode_t __attribute__ ((__mode__ (__SI__)));
typedef unsigned short nlink_t;
# 225 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 3
typedef long fd_mask;
typedef struct _types_fd_set {
fd_mask fds_bits[(((64)+(((sizeof (fd_mask) * 8))-1))/((sizeof (fd_mask) * 8)))];
} _types_fd_set;
# 256 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 3
typedef unsigned long clockid_t;
typedef unsigned long timer_t;
typedef long useconds_t;
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/features.h" 1 3
# 268 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/types.h" 2 3
# 47 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 2 3
typedef __FILE FILE;
# 59 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 3
typedef _fpos_t fpos_t;
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/stdio.h" 1 3
# 66 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 2 3
# 170 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 3
FILE * tmpfile (void);
char * tmpnam (char *);
int fclose (FILE *);
int fflush (FILE *);
FILE * freopen (const char *, const char *, FILE *);
void setbuf (FILE *, char *);
int setvbuf (FILE *, char *, int, size_t);
int fprintf (FILE *, const char *, ...);
int fscanf (FILE *, const char *, ...);
int printf (const char *, ...);
int scanf (const char *, ...);
int sscanf (const char *, const char *, ...);
int vfprintf (FILE *, const char *, __gnuc_va_list);
int vprintf (const char *, __gnuc_va_list);
int vsprintf (char *, const char *, __gnuc_va_list);
int fgetc (FILE *);
char * fgets (char *, int, FILE *);
int fputc (int, FILE *);
int fputs (const char *, FILE *);
int getc (FILE *);
int getchar (void);
char * gets (char *);
int putc (int, FILE *);
int putchar (int);
int puts (const char *);
int ungetc (int, FILE *);
size_t fread (void *, size_t _size, size_t _n, FILE *);
size_t fwrite (const void * , size_t _size, size_t _n, FILE *);
int fgetpos (FILE *, fpos_t *);
int fseek (FILE *, long, int);
int fsetpos (FILE *, const fpos_t *);
long ftell ( FILE *);
void rewind (FILE *);
void clearerr (FILE *);
int feof (FILE *);
int ferror (FILE *);
void perror (const char *);
FILE * fopen (const char *_name, const char *_type);
int sprintf (char *, const char *, ...);
int remove (const char *);
int rename (const char *, const char *);
int fseeko (FILE *, off_t, int);
off_t ftello ( FILE *);
int asiprintf (char **, const char *, ...);
int asprintf (char **, const char *, ...);
int dprintf (int, const char *, ...);
int fcloseall (void);
int fiprintf (FILE *, const char *, ...);
int iprintf (const char *, ...);
int siprintf (char *, const char *, ...);
int snprintf (char *, size_t, const char *, ...);
int sniprintf (char *, size_t, const char *, ...);
char * tempnam (const char *, const char *);
int vasiprintf (char **, const char *, __gnuc_va_list);
int vasprintf (char **, const char *, __gnuc_va_list);
int vdprintf (int, const char *, __gnuc_va_list);
int vsniprintf (char *, size_t, const char *, __gnuc_va_list);
int vsnprintf (char *, size_t, const char *, __gnuc_va_list);
int vfiprintf (FILE *, const char *, __gnuc_va_list);
int vfiscanf (FILE *, const char *, __gnuc_va_list);
int vfscanf (FILE *, const char *, __gnuc_va_list);
int viprintf (const char *, __gnuc_va_list);
int viscanf (const char *, __gnuc_va_list);
int vscanf (const char *, __gnuc_va_list);
int vsiscanf (const char *, const char *, __gnuc_va_list);
int vsscanf (const char *, const char *, __gnuc_va_list);
# 262 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 3
FILE * fdopen (int, const char *);
int fileno (FILE *);
int getw (FILE *);
int pclose (FILE *);
FILE * popen (const char *, const char *);
int putw (int, FILE *);
void setbuffer (FILE *, char *, int);
int setlinebuf (FILE *);
int getc_unlocked (FILE *);
int getchar_unlocked (void);
void flockfile (FILE *);
int ftrylockfile (FILE *);
void funlockfile (FILE *);
int putc_unlocked (int, FILE *);
int putchar_unlocked (int);
int _asiprintf_r (struct _reent *, char **, const char *, ...);
int _asprintf_r (struct _reent *, char **, const char *, ...);
int _dprintf_r (struct _reent *, int, const char *, ...);
int _fcloseall_r (struct _reent *);
FILE * _fdopen_r (struct _reent *, int, const char *);
FILE * _fopen_r (struct _reent *, const char *, const char *);
int _fclose_r (struct _reent *, FILE *);
int _fiscanf_r (struct _reent *, FILE *, const char *, ...);
int _fscanf_r (struct _reent *, FILE *, const char *, ...);
int _fseek_r (struct _reent *, FILE *, long, int);
long _ftell_r (struct _reent *, FILE *);
int _getchar_r (struct _reent *);
char * _gets_r (struct _reent *, char *);
int _iprintf_r (struct _reent *, const char *, ...);
int _iscanf_r (struct _reent *, const char *, ...);
int _mkstemp_r (struct _reent *, char *);
char * _mktemp_r (struct _reent *, char *);
void _perror_r (struct _reent *, const char *);
int _printf_r (struct _reent *, const char *, ...);
int _putchar_r (struct _reent *, int);
int _puts_r (struct _reent *, const char *);
int _remove_r (struct _reent *, const char *);
int _rename_r (struct _reent *, const char *_old, const char *_new);
int _scanf_r (struct _reent *, const char *, ...);
int _siprintf_r (struct _reent *, char *, const char *, ...);
int _siscanf_r (struct _reent *, const char *, const char *, ...);
int _sniprintf_r (struct _reent *, char *, size_t, const char *, ...);
int _snprintf_r (struct _reent *, char *, size_t, const char *, ...);
int _sprintf_r (struct _reent *, char *, const char *, ...);
int _sscanf_r (struct _reent *, const char *, const char *, ...);
char * _tempnam_r (struct _reent *, const char *, const char *);
FILE * _tmpfile_r (struct _reent *);
char * _tmpnam_r (struct _reent *, char *);
int _ungetc_r (struct _reent *, int, FILE *);
int _vasiprintf_r (struct _reent *, char **, const char *, __gnuc_va_list);
int _vasprintf_r (struct _reent *, char **, const char *, __gnuc_va_list);
int _vdprintf_r (struct _reent *, int, const char *, __gnuc_va_list);
int _vfiprintf_r (struct _reent *, FILE *, const char *, __gnuc_va_list);
int _vfprintf_r (struct _reent *, FILE *, const char *, __gnuc_va_list);
int _viprintf_r (struct _reent *, const char *, __gnuc_va_list);
int _vprintf_r (struct _reent *, const char *, __gnuc_va_list);
int _vsiprintf_r (struct _reent *, char *, const char *, __gnuc_va_list);
int _vsprintf_r (struct _reent *, char *, const char *, __gnuc_va_list);
int _vsniprintf_r (struct _reent *, char *, size_t, const char *, __gnuc_va_list);
int _vsnprintf_r (struct _reent *, char *, size_t, const char *, __gnuc_va_list);
int _vfiscanf_r (struct _reent *, FILE *, const char *, __gnuc_va_list);
int _vfscanf_r (struct _reent *, FILE *, const char *, __gnuc_va_list);
int _viscanf_r (struct _reent *, const char *, __gnuc_va_list);
int _vscanf_r (struct _reent *, const char *, __gnuc_va_list);
int _vsscanf_r (struct _reent *, const char *, const char *, __gnuc_va_list);
int _vsiscanf_r (struct _reent *, const char *, const char *, __gnuc_va_list);
ssize_t __getdelim (char **, size_t *, int, FILE *);
ssize_t __getline (char **, size_t *, FILE *);
# 364 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 3
int __srget (FILE *);
int __swbuf (int, FILE *);
FILE *funopen (const void * _cookie, int (*readfn)(void * _cookie, char *_buf, int _n), int (*writefn)(void * _cookie, const char *_buf, int _n), fpos_t (*seekfn)(void * _cookie, fpos_t _off, int _whence), int (*closefn)(void * _cookie));
# 471 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdio.h" 3
# 44 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdlib.h" 1 3
# 14 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdlib.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stddef.h" 1 3 4
# 15 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdlib.h" 2 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/stdlib.h" 1 3
# 18 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdlib.h" 2 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/alloca.h" 1 3
# 20 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdlib.h" 2 3
typedef struct
{
int quot;
int rem;
} div_t;
typedef struct
{
long quot;
long rem;
} ldiv_t;
typedef struct
{
long long int quot;
long long int rem;
} lldiv_t;
# 57 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/stdlib.h" 3
extern int __mb_cur_max;
void abort (void) __attribute__ ((noreturn));
int abs (int);
int atexit (void (*__func)(void));
double atof (const char *__nptr);
float atoff (const char *__nptr);
int atoi (const char *__nptr);
int _atoi_r (struct _reent *, const char *__nptr);
long atol (const char *__nptr);
long _atol_r (struct _reent *, const char *__nptr);
void * bsearch (const void * __key, const void * __base, size_t __nmemb, size_t __size, int (* _compar) (const void *, const void *));
void * calloc (size_t __nmemb, size_t __size);
div_t div (int __numer, int __denom);
void exit (int __status) __attribute__ ((noreturn));
void free (void *);
char * getenv (const char *__string);
char * _getenv_r (struct _reent *, const char *__string);
char * _findenv (const char *, int *);
char * _findenv_r (struct _reent *, const char *, int *);
long labs (long);
ldiv_t ldiv (long __numer, long __denom);
void * malloc (size_t __size);
int mblen (const char *, size_t);
int _mblen_r (struct _reent *, const char *, size_t, _mbstate_t *);
int mbtowc (wchar_t *, const char *, size_t);
int _mbtowc_r (struct _reent *, wchar_t *, const char *, size_t, _mbstate_t *);
int wctomb (char *, wchar_t);
int _wctomb_r (struct _reent *, char *, wchar_t, _mbstate_t *);
size_t mbstowcs (wchar_t *, const char *, size_t);
size_t _mbstowcs_r (struct _reent *, wchar_t *, const char *, size_t, _mbstate_t *);
size_t wcstombs (char *, const wchar_t *, size_t);
size_t _wcstombs_r (struct _reent *, char *, const wchar_t *, size_t, _mbstate_t *);
int mkstemp (char *);
char * mktemp (char *);
void qsort (void * __base, size_t __nmemb, size_t __size, int(*_compar)(const void *, const void *));
int rand (void);
void * realloc (void * __r, size_t __size);
void srand (unsigned __seed);
double strtod (const char *__n, char **__end_PTR);
double _strtod_r (struct _reent *,const char *__n, char **__end_PTR);
float strtof (const char *__n, char **__end_PTR);
long strtol (const char *__n, char **__end_PTR, int __base);
long _strtol_r (struct _reent *,const char *__n, char **__end_PTR, int __base);
unsigned long strtoul (const char *__n, char **__end_PTR, int __base);
unsigned long _strtoul_r (struct _reent *,const char *__n, char **__end_PTR, int __base);
int system (const char *__string);
long a64l (const char *__input);
char * l64a (long __input);
char * _l64a_r (struct _reent *,long __input);
int on_exit (void (*__func)(int, void *),void * __arg);
void _Exit (int __status) __attribute__ ((noreturn));
int putenv (char *__string);
int _putenv_r (struct _reent *, char *__string);
int setenv (const char *__string, const char *__value, int __overwrite);
int _setenv_r (struct _reent *, const char *__string, const char *__value, int __overwrite);
char * gcvt (double,int,char *);
char * gcvtf (float,int,char *);
char * fcvt (double,int,int *,int *);
char * fcvtf (float,int,int *,int *);
char * ecvt (double,int,int *,int *);
char * ecvtbuf (double, int, int*, int*, char *);
char * fcvtbuf (double, int, int*, int*, char *);
char * ecvtf (float,int,int *,int *);
char * dtoa (double, int, int, int *, int*, char**);
int rand_r (unsigned *__seed);
double drand48 (void);
double _drand48_r (struct _reent *);
double erand48 (unsigned short [3]);
double _erand48_r (struct _reent *, unsigned short [3]);
long jrand48 (unsigned short [3]);
long _jrand48_r (struct _reent *, unsigned short [3]);
void lcong48 (unsigned short [7]);
void _lcong48_r (struct _reent *, unsigned short [7]);
long lrand48 (void);
long _lrand48_r (struct _reent *);
long mrand48 (void);
long _mrand48_r (struct _reent *);
long nrand48 (unsigned short [3]);
long _nrand48_r (struct _reent *, unsigned short [3]);
unsigned short *
seed48 (unsigned short [3]);
unsigned short *
_seed48_r (struct _reent *, unsigned short [3]);
void srand48 (long);
void _srand48_r (struct _reent *, long);
long long atoll (const char *__nptr);
long long _atoll_r (struct _reent *, const char *__nptr);
long long llabs (long long);
lldiv_t lldiv (long long __numer, long long __denom);
long long strtoll (const char *__n, char **__end_PTR, int __base);
long long _strtoll_r (struct _reent *, const char *__n, char **__end_PTR, int __base);
unsigned long long strtoull (const char *__n, char **__end_PTR, int __base);
unsigned long long _strtoull_r (struct _reent *, const char *__n, char **__end_PTR, int __base);
void cfree (void *);
void unsetenv (const char *__string);
void _unsetenv_r (struct _reent *, const char *__string);
char * _dtoa_r (struct _reent *, double, int, int, int *, int*, char**);
void * _malloc_r (struct _reent *, size_t);
void * _calloc_r (struct _reent *, size_t, size_t);
void _free_r (struct _reent *, void *);
void * _realloc_r (struct _reent *, void *, size_t);
void _mstats_r (struct _reent *, char *);
int _system_r (struct _reent *, const char *);
void __eprintf (const char *, const char *, unsigned int, const char *);
# 45 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stdarg.h" 1 3 4
# 105 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stdarg.h" 3 4
typedef __gnuc_va_list va_list;
# 46 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/setjmp.h" 1 3
# 10 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/setjmp.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/setjmp.h" 1 3
# 229 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/machine/setjmp.h" 3
typedef int jmp_buf[20];
# 11 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/setjmp.h" 2 3
void longjmp (jmp_buf __jmpb, int __retval);
int setjmp (jmp_buf __jmpb);
# 47 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/ctype.h" 1 3
int isalnum (int __c);
int isalpha (int __c);
int iscntrl (int __c);
int isdigit (int __c);
int isgraph (int __c);
int islower (int __c);
int isprint (int __c);
int ispunct (int __c);
int isspace (int __c);
int isupper (int __c);
int isxdigit (int __c);
int tolower (int __c);
int toupper (int __c);
int isblank (int __c);
int isascii (int __c);
int toascii (int __c);
int _tolower (int __c);
int _toupper (int __c);
# 39 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/ctype.h" 3
extern const char *__ctype_ptr;
extern const char _ctype_[];
# 71 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/ctype.h" 3
# 48 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/string.h" 1 3
# 14 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/string.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/include/stddef.h" 1 3 4
# 15 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/string.h" 2 3
void * memchr (const void *, int, size_t);
int memcmp (const void *, const void *, size_t);
void * memcpy (void *, const void *, size_t);
void * memmove (void *, const void *, size_t);
void * memset (void *, int, size_t);
char *strcat (char *, const char *);
char *strchr (const char *, int);
int strcmp (const char *, const char *);
int strcoll (const char *, const char *);
char *strcpy (char *, const char *);
size_t strcspn (const char *, const char *);
char *strerror (int);
size_t strlen (const char *);
char *strncat (char *, const char *, size_t);
int strncmp (const char *, const char *, size_t);
char *strncpy (char *, const char *, size_t);
char *strpbrk (const char *, const char *);
char *strrchr (const char *, int);
size_t strspn (const char *, const char *);
char *strstr (const char *, const char *);
char *strtok (char *, const char *);
size_t strxfrm (char *, const char *, size_t);
char *strtok_r (char *, const char *, char **);
int bcmp (const void *, const void *, size_t);
void bcopy (const void *, void *, size_t);
void bzero (void *, size_t);
int ffs (int);
char *index (const char *, int);
void * memccpy (void *, const void *, int, size_t);
void * mempcpy (void *, const void *, size_t);
char *rindex (const char *, int);
int strcasecmp (const char *, const char *);
char *strdup (const char *);
char *_strdup_r (struct _reent *, const char *);
char *strndup (const char *, size_t);
char *_strndup_r (struct _reent *, const char *, size_t);
char *strerror_r (int, char *, size_t);
size_t strlcat (char *, const char *, size_t);
size_t strlcpy (char *, const char *, size_t);
int strncasecmp (const char *, const char *, size_t);
size_t strnlen (const char *, size_t);
char *strsep (char **, const char *);
char *strlwr (char *);
char *strupr (char *);
# 99 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/string.h" 3
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/string.h" 1 3
# 100 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/string.h" 2 3
# 49 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 1 3
# 10 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 3
union __dmath
{
__ULong i[2];
double d;
};
union __fmath
{
__ULong i[1];
float f;
};
union __ldmath
{
__ULong i[4];
long double ld;
};
# 75 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 3
extern double atan (double);
extern double cos (double);
extern double sin (double);
extern double tan (double);
extern double tanh (double);
extern double frexp (double, int *);
extern double modf (double, double *);
extern double ceil (double);
extern double fabs (double);
extern double floor (double);
extern double acos (double);
extern double asin (double);
extern double atan2 (double, double);
extern double cosh (double);
extern double sinh (double);
extern double exp (double);
extern double ldexp (double, int);
extern double log (double);
extern double log10 (double);
extern double pow (double, double);
extern double sqrt (double);
extern double fmod (double, double);
# 112 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 3
typedef float float_t;
typedef double double_t;
# 122 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 3
extern int __fpclassifyf (float x);
extern int __fpclassifyd (double x);
extern int __signbitf (float x);
extern int __signbitd (double x);
# 163 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 3
extern double infinity (void);
extern double nan (const char *);
extern int isnan (double);
extern int isinf (double);
extern int finite (double);
extern double copysign (double, double);
extern int ilogb (double);
extern double asinh (double);
extern double cbrt (double);
extern double nextafter (double, double);
extern double rint (double);
extern double scalbn (double, int);
extern double exp2 (double);
extern double scalbln (double, long int);
extern double tgamma (double);
extern double nearbyint (double);
extern long int lrint (double);
extern double round (double);
extern long int lround (double);
extern double trunc (double);
extern double remquo (double, double, int *);
extern double copysign (double, double);
extern double fdim (double, double);
extern double fmax (double, double);
extern double fmin (double, double);
extern double fma (double, double, double);
extern void sincos (double, double *, double *);
extern double log1p (double);
extern double expm1 (double);
extern double acosh (double);
extern double atanh (double);
extern double remainder (double, double);
extern double gamma (double);
extern double gamma_r (double, int *);
extern double lgamma (double);
extern double lgamma_r (double, int *);
extern double erf (double);
extern double erfc (double);
extern double y0 (double);
extern double y1 (double);
extern double yn (int, double);
extern double j0 (double);
extern double j1 (double);
extern double jn (int, double);
extern double hypot (double, double);
extern double cabs();
extern double drem (double, double);
# 231 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 3
extern float atanf (float);
extern float cosf (float);
extern float sinf (float);
extern float tanf (float);
extern float tanhf (float);
extern float frexpf (float, int *);
extern float modff (float, float *);
extern float ceilf (float);
extern float fabsf (float);
extern float floorf (float);
extern float acosf (float);
extern float asinf (float);
extern float atan2f (float, float);
extern float coshf (float);
extern float sinhf (float);
extern float expf (float);
extern float ldexpf (float, int);
extern float logf (float);
extern float log10f (float);
extern float powf (float, float);
extern float sqrtf (float);
extern float fmodf (float, float);
# 263 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 3
extern float exp2f (float);
extern float scalblnf (float, long int);
extern float tgammaf (float);
extern float nearbyintf (float);
extern long int lrintf (float);
extern float roundf (float);
extern long int lroundf (float);
extern float truncf (float);
extern float remquof (float, float, int *);
extern float copysignf (float, float);
extern float fdimf (float, float);
extern float fmaxf (float, float);
extern float fminf (float, float);
extern float fmaf (float, float, float);
extern float infinityf (void);
extern float nanf (const char *);
extern int isnanf (float);
extern int isinff (float);
extern int finitef (float);
extern float copysignf (float, float);
extern int ilogbf (float);
extern float asinhf (float);
extern float cbrtf (float);
extern float nextafterf (float, float);
extern float rintf (float);
extern float scalbnf (float, int);
extern float log1pf (float);
extern float expm1f (float);
extern void sincosf (float, float *, float *);
extern float acoshf (float);
extern float atanhf (float);
extern float remainderf (float, float);
extern float gammaf (float);
extern float gammaf_r (float, int *);
extern float lgammaf (float);
extern float lgammaf_r (float, int *);
extern float erff (float);
extern float erfcf (float);
extern float y0f (float);
extern float y1f (float);
extern float ynf (int, float);
extern float j0f (float);
extern float j1f (float);
extern float jnf (int, float);
extern float hypotf (float, float);
extern float cabsf();
extern float dremf (float, float);
extern int *__signgam (void);
# 332 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 3
struct exception
{
int type;
char *name;
double arg1;
double arg2;
double retval;
int err;
};
extern int matherr (struct exception *e);
# 387 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 3
enum __fdlibm_version
{
__fdlibm_ieee = -1,
__fdlibm_svid,
__fdlibm_xopen,
__fdlibm_posix
};
extern const enum __fdlibm_version __fdlib_version;
# 407 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/math.h" 3
# 50 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 64 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
# 1 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/wait.h" 1 3
# 29 "/mnt/scratch/ccm-20060104/bin/../lib/gcc/sh-elf/4.2.0/../../../../sh-elf/include/sys/wait.h" 3
pid_t wait (int *);
pid_t waitpid (pid_t, int *, int);
pid_t _wait (int *);
# 65 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 73 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
# 1 "/mnt/scratch/CSiBE/src/./flex-2.5.31/../include/regex.h" 1
# 39 "/mnt/scratch/CSiBE/src/./flex-2.5.31/../include/regex.h"
#pragma export on
# 57 "/mnt/scratch/CSiBE/src/./flex-2.5.31/../include/regex.h"
typedef unsigned reg_syntax_t;
# 156 "/mnt/scratch/CSiBE/src/./flex-2.5.31/../include/regex.h"
extern reg_syntax_t re_syntax_options;
# 265 "/mnt/scratch/CSiBE/src/./flex-2.5.31/../include/regex.h"
typedef enum
{
REG_NOERROR = 0,
REG_NOMATCH,
REG_BADPAT,
REG_ECOLLATE,
REG_ECTYPE,
REG_EESCAPE,
REG_ESUBREG,
REG_EBRACK,
REG_EPAREN,
REG_EBRACE,
REG_BADBR,
REG_ERANGE,
REG_ESPACE,
REG_BADRPT,
REG_EEND,
REG_ESIZE,
REG_ERPAREN
} reg_errcode_t;
struct re_pattern_buffer
{
unsigned char *buffer;
unsigned long allocated;
unsigned long used;
reg_syntax_t syntax;
char *fastmap;
char *translate;
size_t re_nsub;
unsigned can_be_null : 1;
# 342 "/mnt/scratch/CSiBE/src/./flex-2.5.31/../include/regex.h"
unsigned regs_allocated : 2;
unsigned fastmap_accurate : 1;
unsigned no_sub : 1;
unsigned not_bol : 1;
unsigned not_eol : 1;
unsigned newline_anchor : 1;
};
typedef struct re_pattern_buffer regex_t;
typedef int regoff_t;
struct re_registers
{
unsigned num_regs;
regoff_t *start;
regoff_t *end;
};
# 397 "/mnt/scratch/CSiBE/src/./flex-2.5.31/../include/regex.h"
typedef struct
{
regoff_t rm_so;
regoff_t rm_eo;
} regmatch_t;
# 423 "/mnt/scratch/CSiBE/src/./flex-2.5.31/../include/regex.h"
extern reg_syntax_t re_set_syntax (reg_syntax_t syntax);
extern const char *re_compile_pattern
(const char *pattern, int length, struct re_pattern_buffer *buffer);
extern int re_compile_fastmap (struct re_pattern_buffer *buffer);
extern int re_search
(struct re_pattern_buffer *buffer, const char *string, int length, int start, int range, struct re_registers *regs);
extern int re_search_2
(struct re_pattern_buffer *buffer, const char *string1, int length1, const char *string2, int length2, int start, int range, struct re_registers *regs, int stop);
extern int re_match
(struct re_pattern_buffer *buffer, const char *string, int length, int start, struct re_registers *regs);
extern int re_match_2
(struct re_pattern_buffer *buffer, const char *string1, int length1, const char *string2, int length2, int start, struct re_registers *regs, int stop);
# 483 "/mnt/scratch/CSiBE/src/./flex-2.5.31/../include/regex.h"
extern void re_set_registers
(struct re_pattern_buffer *buffer, struct re_registers *regs, unsigned num_regs, regoff_t *starts, regoff_t *ends);
extern char *re_comp (const char *);
extern int re_exec (const char *);
extern int regcomp (regex_t *preg, const char *pattern, int cflags);
extern int regexec
(const regex_t *preg, const char *string, size_t nmatch, regmatch_t pmatch[], int eflags);
extern size_t regerror
(int errcode, const regex_t *preg, char *errbuf, size_t errbuf_size);
extern void regfree (regex_t *preg);
#pragma export reset
# 74 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 1 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexint.h" 1
# 17 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexint.h"
typedef signed char flex_int8_t;
typedef short int flex_int16_t;
typedef int flex_int32_t;
typedef unsigned char flex_uint8_t;
typedef unsigned short int flex_uint16_t;
typedef unsigned int flex_uint32_t;
# 75 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h" 2
# 378 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int printstats, syntaxerror, eofseen, ddebug, trace, nowarn,
spprdflt;
extern int interactive, caseins, lex_compat, posix_compat, do_yylineno;
extern int useecs, fulltbl, usemecs, fullspd;
extern int gen_line_dirs, performance_report, backing_up_report;
extern int reentrant, bison_bridge_lval, bison_bridge_lloc;
extern int ansi_func_defs, ansi_func_protos;
extern int C_plus_plus, long_align, use_read, yytext_is_array, do_yywrap;
extern int csize;
extern int yymore_used, reject, real_reject, continued_action, in_rule;
extern int yymore_really_used, reject_really_used;
# 425 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int datapos, dataline, linenum, out_linenum;
extern FILE *skelfile, *yyin, *backing_up_file;
extern const char *skel[];
extern int skel_ind;
extern char *infilename, *outfilename, *headerfilename;
extern int did_outfilename;
extern char *prefix, *yyclass;
extern int do_stdinit, use_stdout;
extern char **input_files;
extern int num_input_files;
extern char *program_name;
extern char *action_array;
extern int action_size;
extern int defs1_offset, prolog_offset, action_offset, action_index;
# 450 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int onestate[500], onesym[500];
extern int onenext[500], onedef[500], onesp;
# 487 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int maximum_mns, current_mns, current_max_rules;
extern int num_rules, num_eof_rules, default_rule, lastnfa;
extern int *firstst, *lastst, *finalst, *transchar, *trans1, *trans2;
extern int *accptnum, *assoc_rule, *state_type;
extern int *rule_type, *rule_linenum, *rule_useful;
extern int *rule_has_nl, *ccl_has_nl;
extern int nlch;
# 503 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int current_state_type;
# 512 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int variable_trailing_context_rules;
# 527 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int numtemps, numprots, protprev[50], protnext[50], prottbl[50];
extern int protcomst[50], firstprot, lastprot, protsave[2000];
# 546 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int numecs, nextecm[256 + 1], ecgroup[256 + 1], nummecs;
extern int tecfwd[256 + 1], tecbck[256 + 1];
# 566 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int lastsc, *scset, *scbol, *scxclu, *sceof;
extern int current_max_scs;
extern char **scname;
# 601 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int current_max_dfa_size, current_max_xpairs;
extern int current_max_template_xpairs, current_max_dfas;
extern int lastdfa, *nxt, *chk, *tnxt;
extern int *base, *def, *nultrans, NUL_ec, tblend, firstfree, **dss,
*dfasiz;
extern union dfaacc_union {
int *dfaacc_set;
int dfaacc_state;
} *dfaacc;
extern int *accsiz, *dhash, numas;
extern int numsnpairs, jambase, jamstate;
extern int end_of_buffer_state;
# 626 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int lastccl, *cclmap, *ccllen, *cclng, cclreuse;
extern int current_maxccls, current_max_ccl_tbl_size;
extern unsigned char *ccltbl;
# 651 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern char nmstr[2048];
extern int sectnum, nummt, hshcol, dfaeql, numeps, eps2, num_reallocs;
extern int tmpuses, totnst, peakpairs, numuniq, numdup, hshsave;
extern int num_backing_up, bol_needed;
void *allocate_array (int, size_t);
void *reallocate_array (void *, int, size_t);
void *flex_alloc (size_t);
void *flex_realloc (void *, size_t);
void flex_free (void *);
# 711 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int yylval;
extern void ccladd (int, int);
extern int cclinit (void);
extern void cclnegate (int);
extern void list_character_set (FILE *, int[]);
extern void check_for_backing_up (int, int[]);
extern void check_trailing_context (int *, int, int *, int);
extern int *epsclosure (int *, int *, int[], int *, int *);
extern void increase_max_dfas (void);
extern void ntod (void);
extern int snstods (int[], int, int[], int, int, int *);
extern void ccl2ecl (void);
extern int cre8ecs (int[], int[], int);
extern void mkeccl (unsigned char[], int, int[], int[], int, int);
extern void mkechar (int, int[], int[]);
extern void do_indent (void);
extern void gen_backing_up (void);
extern void gen_bu_action (void);
extern void genctbl (void);
extern void gen_find_action (void);
extern void genftbl (void);
extern void gen_next_compressed_state (char *);
extern void gen_next_match (void);
extern void gen_next_state (int);
extern void gen_NUL_trans (void);
extern void gen_start_state (void);
extern void gentabs (void);
extern void indent_put2s (const char *, const char *);
extern void indent_puts (const char *);
extern void make_tables (void);
extern void check_options (void);
extern void flexend (int);
extern void usage (void);
extern void action_define (const char *defname, int value);
extern void add_action (char *new_text);
extern int all_lower (register char *);
extern int all_upper (register char *);
extern void bubble (int[], int);
extern void check_char (int c);
extern unsigned char clower (int);
extern char *copy_string (register const char *);
extern unsigned char *copy_unsigned_string (register unsigned char *);
extern void cshell (unsigned char[], int, int);
extern void dataend (void);
extern void dataflush (void);
extern void flexerror (const char *);
extern void flexfatal (const char *);
# 880 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
extern int htoi (unsigned char[]);
extern void lerrif (const char *, int);
extern void lerrsf (const char *, const char *);
extern void line_directive_out (FILE *, int);
extern void mark_defs1 (void);
extern void mark_prolog (void);
extern void mk2data (int);
extern void mkdata (int);
extern int myctoi (const char *);
extern unsigned char myesc (unsigned char[]);
extern int otoi (unsigned char[]);
extern void out (const char *);
extern void out_dec (const char *, int);
extern void out_dec2 (const char *, int, int);
extern void out_hex (const char *, unsigned int);
extern void out_line_count (const char *);
extern void out_str (const char *, const char *);
extern void out_str3
(const char *, const char *, const char *, const char *);
extern void out_str_dec (const char *, const char *, int);
extern void outc (int);
extern void outn (const char *);
extern void out_m4_define (const char* def, const char* val);
extern char *readable_form (int);
extern void skelout (void);
extern void transition_struct_out (int, int);
extern void *yy_flex_xmalloc (int);
extern void zero_out (char *, size_t);
extern void add_accept (int, int);
extern int copysingl (int, int);
extern void dumpnfa (int);
extern void finish_rule (int, int, int, int, int);
extern int link_machines (int, int);
extern void mark_beginning_as_normal (register int);
extern int mkbranch (int, int);
extern int mkclos (int);
extern int mkopt (int);
extern int mkor (int, int);
extern int mkposcl (int);
extern int mkrep (int, int, int);
extern int mkstate (int);
extern void new_rule (void);
extern void build_eof_action (void);
extern void format_pinpoint_message (const char *, const char *);
extern void pinpoint_message (const char *);
extern void line_warning (const char *, int);
extern void line_pinpoint (const char *, int);
extern void format_synerr (const char *, const char *);
extern void synerr (const char *);
extern void format_warn (const char *, const char *);
extern void warn (const char *);
extern void yyerror (const char *);
extern int yyparse (void);
extern int flexscan (void);
extern void set_input_file (char *);
extern int yywrap (void);
extern void cclinstal (unsigned char[], int);
extern int ccllookup (unsigned char[]);
extern void ndinstal (const char *, unsigned char[]);
extern unsigned char *ndlookup (const char *);
extern void scextend (void);
extern void scinstal (const char *, int);
extern int sclookup (const char *);
extern void bldtbl (int[], int, int, int, int);
extern void cmptmps (void);
extern void expand_nxt_chk (void);
extern int find_table_space (int *, int);
extern void inittbl (void);
extern void mkdeftbl (void);
extern void mk1tbl (int, int, int, int);
extern void place_state (int *, int, int);
extern void stack1 (int, int, int, int);
extern int yylex (void);
struct Buf {
void *elts;
int nelts;
size_t elt_size;
int nmax;
};
extern void buf_init (struct Buf * buf, size_t elem_size);
extern void buf_destroy (struct Buf * buf);
extern struct Buf *buf_append
(struct Buf * buf, const void *ptr, int n_elem);
extern struct Buf *buf_concat (struct Buf* dest, const struct Buf* src);
extern struct Buf *buf_strappend (struct Buf *, const char *str);
extern struct Buf *buf_strnappend
(struct Buf *, const char *str, int nchars);
extern struct Buf *buf_strdefine
(struct Buf * buf, const char *str, const char *def);
extern struct Buf *buf_prints (struct Buf *buf, const char *fmt, const char* s);
extern struct Buf *buf_m4_define (struct Buf *buf, const char* def, const char* val);
extern struct Buf *buf_m4_undefine (struct Buf *buf, const char* def);
extern struct Buf *buf_print_strings (struct Buf * buf, FILE* out);
extern struct Buf *buf_linedir (struct Buf *buf, const char* filename, int lineno);
extern struct Buf userdef_buf;
extern struct Buf defs_buf;
extern struct Buf yydmap_buf;
extern struct Buf m4defs_buf;
extern struct Buf top_buf;
extern jmp_buf flex_main_jmp_buf;
extern char *chomp (char *str);
# 1133 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
int has_case(int c);
int reverse_case(int c);
int range_covers_case (int c1, int c2);
# 1149 "/mnt/scratch/CSiBE/src/./flex-2.5.31/flexdef.h"
struct filter {
int (*filter_func)(struct filter*);
void * extra;
int argc;
const char ** argv;
struct filter * next;
};
extern struct filter * output_chain;
extern struct filter *filter_create_ext (struct filter * chain, const char *cmd, ...);
struct filter *filter_create_int (struct filter *chain, int (*filter_func) (struct filter *), void *extra);
extern int filter_apply_chain (struct filter * chain);
extern int filter_truncate (struct filter * chain, int max_len);
extern int filter_tee_header (struct filter *chain);
extern int filter_fix_linedirs (struct filter *chain);
extern regex_t regex_linedir, regex_blank_line;
int flex_init_regex(void);
void flex_regcomp(regex_t *preg, const char *regex, int cflags);
char *regmatch_dup (regmatch_t * m, const char *src);
char *regmatch_cpy (regmatch_t * m, char *dest, const char *src);
int regmatch_len (regmatch_t * m);
int regmatch_strtol (regmatch_t * m, const char *src, char **endptr, int base);
int regmatch_empty (regmatch_t * m);
# 73 "parse.y" 2
# 1 "/mnt/scratch/CSiBE/src/./flex-2.5.31/tables.h" 1
# 45 "/mnt/scratch/CSiBE/src/./flex-2.5.31/tables.h"
# 1 "/mnt/scratch/CSiBE/src/./flex-2.5.31/tables_shared.h" 1
# 77 "/mnt/scratch/CSiBE/src/./flex-2.5.31/tables_shared.h"
enum yytbl_id {
YYTD_ID_ACCEPT = 0x01,
YYTD_ID_BASE = 0x02,
YYTD_ID_CHK = 0x03,
YYTD_ID_DEF = 0x04,
YYTD_ID_EC = 0x05,
YYTD_ID_META = 0x06,
YYTD_ID_NUL_TRANS = 0x07,
YYTD_ID_NXT = 0x08,
YYTD_ID_RULE_CAN_MATCH_EOL = 0x09,
YYTD_ID_START_STATE_LIST = 0x0A,
YYTD_ID_TRANSITION = 0x0B,
YYTD_ID_ACCLIST = 0x0C
};
enum yytbl_flags {
YYTD_DATA8 = 0x01,
YYTD_DATA16 = 0x02,
YYTD_DATA32 = 0x04,
YYTD_PTRANS = 0x08,
YYTD_STRUCT = 0x10
};
struct yytbl_hdr {
flex_uint32_t th_magic;
flex_uint32_t th_hsize;
flex_uint32_t th_ssize;
flex_uint16_t th_flags;
char *th_version;
char *th_name;
};
struct yytbl_data {
flex_uint16_t td_id;
flex_uint16_t td_flags;
flex_uint32_t td_hilen;
flex_uint32_t td_lolen;
void *td_data;
};
# 139 "/mnt/scratch/CSiBE/src/./flex-2.5.31/tables_shared.h"
flex_int32_t yytbl_calc_total_len (const struct yytbl_data *tbl);
# 46 "/mnt/scratch/CSiBE/src/./flex-2.5.31/tables.h" 2
struct yytbl_writer {
FILE *out;
flex_uint32_t total_written;
fpos_t th_ssize_pos;
};
# 62 "/mnt/scratch/CSiBE/src/./flex-2.5.31/tables.h"
extern int tablesext, tablesverify,gentables;
extern char *tablesfilename, *tablesname;
extern struct yytbl_writer tableswr;
int yytbl_writer_init (struct yytbl_writer *, FILE *);
int yytbl_hdr_init (struct yytbl_hdr *th, const char *version_str,
const char *name);
int yytbl_data_init (struct yytbl_data *tbl, enum yytbl_id id);
int yytbl_data_destroy (struct yytbl_data *td);
int yytbl_hdr_fwrite (struct yytbl_writer *wr,
const struct yytbl_hdr *th);
int yytbl_data_fwrite (struct yytbl_writer *wr, struct yytbl_data *td);
void yytbl_data_compress (struct yytbl_data *tbl);
struct yytbl_data *mkftbl (void);
# 74 "parse.y" 2
# 103 "parse.y"
int pat, scnum, eps, headcnt, trailcnt, anyccl, lastchar, i, rulelen;
int trlcontxt, xcluflg, currccl, cclsorted, varlength, variable_trail_rule;
int *scon_stk;
int scon_stk_ptr;
static int madeany = 0;
int previous_continued_action;
# 158 "parse.y"
static const char yytranslate[] = { 0,
2, 2, 2, 2, 2, 2, 2, 2, 2, 34,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 48, 2, 42, 2, 2, 2, 49,
50, 40, 45, 41, 53, 47, 44, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 38,
33, 39, 46, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
51, 2, 52, 37, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 35, 43, 36, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 1, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
27, 28, 29, 30, 31, 32
};
# 261 "parse.y"
static const short yyr1[] = { 0,
54, 55, 56, 56, 56, 56, 57, 58, 58, 59,
59, 59, 60, 61, 61, 62, 62, 62, 62, 62,
63, 63, 63, 64, 65, 65, 65, 65, 66, 67,
67, 67, 68, 68, 68, 69, 70, 70, 70, 70,
71, 71, 72, 73, 73, 73, 73, 73, 74, 74,
74, 74, 74, 74, 74, 74, 74, 74, 74, 74,
75, 75, 76, 76, 76, 76, 77, 77, 77, 77,
77, 77, 77, 77, 77, 77, 77, 77, 78, 78
};
static const short yyr2[] = { 0,
5, 0, 3, 2, 0, 1, 1, 1, 1, 2,
1, 1, 2, 2, 0, 3, 3, 3, 3, 3,
5, 5, 0, 0, 2, 1, 1, 1, 0, 4,
3, 0, 3, 1, 1, 1, 2, 3, 2, 1,
3, 1, 2, 2, 1, 6, 5, 4, 2, 2,
2, 6, 5, 4, 1, 1, 1, 3, 3, 1,
3, 4, 4, 2, 2, 0, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 2, 0
};
static const short yydefact[] = { 2,
0, 6, 0, 7, 8, 9, 15, 23, 0, 4,
13, 32, 12, 11, 3, 0, 0, 0, 0, 0,
14, 29, 1, 24, 10, 0, 0, 0, 0, 0,
0, 0, 23, 0, 16, 17, 18, 19, 20, 31,
35, 36, 0, 34, 32, 28, 60, 57, 27, 0,
55, 80, 0, 66, 0, 26, 40, 0, 42, 45,
56, 30, 0, 22, 25, 0, 0, 66, 0, 21,
39, 0, 43, 37, 0, 44, 0, 49, 50, 51,
33, 79, 58, 59, 0, 64, 67, 68, 69, 70,
71, 72, 73, 74, 75, 76, 77, 78, 61, 65,
41, 38, 0, 0, 62, 0, 48, 0, 54, 0,
63, 0, 47, 0, 53, 46, 52, 0, 0, 0
};
static const short yydefgoto[] = { 118,
1, 3, 8, 9, 15, 10, 11, 21, 12, 23,
55, 32, 24, 43, 44, 56, 57, 58, 59, 60,
61, 69, 100, 66
};
static const short yypact[] = {-32768,
75,-32768, 61,-32768,-32768,-32768,-32768,-32768, 29,-32768,
83, 6,-32768,-32768, 24, -19, 9, 32, 37, 46,
-32768, 47,-32768, 57,-32768, 96, 100, 101, 102, 103,
73, 30,-32768, -1,-32768,-32768,-32768,-32768,-32768,-32768,
-32768,-32768, -28,-32768, 67,-32768,-32768,-32768,-32768, 26,
-32768,-32768, 26, 76, 80,-32768, 58, 26, 42, 38,
-32768,-32768, 107,-32768,-32768, 1, -9,-32768, 0,-32768,
-32768, 26,-32768, 64, 112, 38, 113,-32768,-32768,-32768,
-32768,-32768,-32768,-32768, 36, 65,-32768,-32768,-32768,-32768,
-32768,-32768,-32768,-32768,-32768,-32768,-32768,-32768,-32768,-32768,
42,-32768, -25, 53,-32768, 116,-32768, 3,-32768, 8,
-32768, 90,-32768, 89,-32768,-32768,-32768, 122, 123,-32768
};
static const short yypgoto[] = {-32768,
-32768,-32768,-32768,-32768,-32768,-32768,-32768,-32768, 91, 104,
-32768,-32768,-32768,-32768, 62, 77, -43,-32768, 54, -58,
-32768, 63,-32768,-32768
};
static const short yytable[] = { 46,
76, 47, 86, 82, 107, -24, 112, 48, 49, 67,
62, 114, 63, 26, 74, 108, 87, 88, 89, 90,
91, 92, 93, 94, 95, 96, 97, 98, 47, 13,
41, 25, 113, 72, 48, 50, 14, 42, 86, 115,
84, 27, 76, 22, 47, 51, 52, 53, 83, 54,
48, 99, 87, 88, 89, 90, 91, 92, 93, 94,
95, 96, 97, 98, 28, 4, 5, 6, 77, 29,
75, 7, 51, 52, 53, 2, 54, 78, 30, -5,
-5, -5, 79, 80, 109, -5, 31, 105, 51, 52,
53, 33, 54, 110, 16, 17, 18, 19, 20, 71,
72, 73, 64, 35, 22, 102, 72, 36, 37, 38,
39, 40, 68, 70, 42, 103, 104, 106, 111, 116,
117, 119, 120, 45, 81, 101, 65, 34, 0, 0,
85
};
static const short yycheck[] = { 1,
59, 3, 3, 3, 30, 0, 4, 9, 10, 53,
39, 4, 41, 33, 58, 41, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 3, 1,
1, 8, 30, 43, 9, 37, 8, 8, 3, 32,
50, 33, 101, 38, 3, 47, 48, 49, 48, 51,
9, 52, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 33, 5, 6, 7, 31, 33,
29, 11, 47, 48, 49, 1, 51, 40, 33, 5,
6, 7, 45, 46, 32, 11, 40, 52, 47, 48,
49, 35, 51, 41, 12, 13, 14, 15, 16, 42,
43, 44, 36, 8, 38, 42, 43, 8, 8, 8,
8, 39, 37, 34, 8, 4, 4, 53, 3, 30,
32, 0, 0, 33, 63, 72, 50, 24, -1, -1,
68
};
# 3 "/usr/lib/bison.simple"
# 137 "/usr/lib/bison.simple"
int yychar;
int yylval;
int yynerrs;
# 217 "/usr/lib/bison.simple"
# 242 "/usr/lib/bison.simple"
int yyparse (void);
int
yyparse()
{
register int yystate;
register int yyn;
register short *yyssp;
register int *yyvsp;
int yyerrstatus;
int yychar1 = 0;
short yyssa[200];
int yyvsa[200];
short *yyss = yyssa;
int *yyvs = yyvsa;
# 273 "/usr/lib/bison.simple"
int yystacksize = 200;
int yyfree_stacks = 0;
# 285 "/usr/lib/bison.simple"
int yyval;
int yylen;
yystate = 0;
yyerrstatus = 0;
yynerrs = 0;
yychar = -2;
yyssp = yyss - 1;
yyvsp = yyvs;
yynewstate:
*++yyssp = yystate;
if (yyssp >= yyss + yystacksize - 1)
{
int *yyvs1 = yyvs;
short *yyss1 = yyss;
int size = yyssp - yyss + 1;
# 356 "/usr/lib/bison.simple"
if (yystacksize >= 10000)
{
yyerror("parser stack overflow");
if (yyfree_stacks)
{
free (yyss);
free (yyvs);
}
return 2;
}
yystacksize *= 2;
if (yystacksize > 10000)
yystacksize = 10000;
yyss = (short *) __builtin_alloca(yystacksize * sizeof (*yyssp));
__builtin_memcpy((char *)yyss,(char *)yyss1,size * (unsigned int) sizeof (*yyssp));
yyvs = (int *) __builtin_alloca(yystacksize * sizeof (*yyvsp));
__builtin_memcpy((char *)yyvs,(char *)yyvs1,size * (unsigned int) sizeof (*yyvsp));
# 388 "/usr/lib/bison.simple"
yyssp = yyss + size - 1;
yyvsp = yyvs + size - 1;
# 399 "/usr/lib/bison.simple"
if (yyssp >= yyss + yystacksize - 1)
goto yyabortlab;
}
goto yybackup;
yybackup:
yyn = yypact[yystate];
if (yyn == -32768)
goto yydefault;
if (yychar == -2)
{
yychar = yylex();
}
if (yychar <= 0)
{
yychar1 = 0;
yychar = 0;
}
else
{
yychar1 = ((unsigned)(yychar) <= 286 ? yytranslate[yychar] : 79);
# 463 "/usr/lib/bison.simple"
}
yyn += yychar1;
if (yyn < 0 || yyn > 131 || yycheck[yyn] != yychar1)
goto yydefault;
yyn = yytable[yyn];
# 478 "/usr/lib/bison.simple"
if (yyn < 0)
{
if (yyn == -32768)
goto yyerrlab;
yyn = -yyn;
goto yyreduce;
}
else if (yyn == 0)
goto yyerrlab;
if (yyn == 120)
goto yyacceptlab;
# 499 "/usr/lib/bison.simple"
if (yychar != 0)
yychar = -2;
*++yyvsp = yylval;
if (yyerrstatus) yyerrstatus--;
yystate = yyn;
goto yynewstate;
yydefault:
yyn = yydefact[yystate];
if (yyn == 0)
goto yyerrlab;
yyreduce:
yylen = yyr2[yyn];
if (yylen > 0)
yyval = yyvsp[1-yylen];
# 542 "/usr/lib/bison.simple"
switch (yyn) {
case 1:
# 143 "parse.y"
{
int def_rule;
pat = cclinit();
cclnegate( pat );
def_rule = mkstate( -pat );
default_rule = num_rules;
finish_rule( def_rule, 0, 0, 0, 0);
for ( i = 1; i <= lastsc; ++i )
scset[i] = mkbranch( scset[i], def_rule );
if ( spprdflt )
add_action(
"YY_FATAL_ERROR( \"flex scanner jammed\" )" );
else
add_action( "ECHO" );
add_action( ";\n\tYY_BREAK\n" );
;
break;}
case 2:
# 172 "parse.y"
{
scinstal( "INITIAL", 0 );
;
break;}
case 6:
# 183 "parse.y"
{ synerr( "unknown error processing section 1" ); ;
break;}
case 7:
# 187 "parse.y"
{
check_options();
scon_stk = (int *) allocate_array( lastsc + 1, sizeof( int ) );
scon_stk_ptr = 0;
;
break;}
case 8:
# 195 "parse.y"
{ xcluflg = 0; ;
break;}
case 9:
# 198 "parse.y"
{ xcluflg = 1; ;
break;}
case 10:
# 202 "parse.y"
{ scinstal( nmstr, xcluflg ); ;
break;}
case 11:
# 205 "parse.y"
{ scinstal( nmstr, xcluflg ); ;
break;}
case 12:
# 208 "parse.y"
{ synerr( "bad start condition list" ); ;
break;}
case 16:
# 219 "parse.y"
{
outfilename = copy_string( nmstr );
did_outfilename = 1;
;
break;}
case 17:
# 224 "parse.y"
{ prefix = copy_string( nmstr ); ;
break;}
case 18:
# 226 "parse.y"
{ yyclass = copy_string( nmstr ); ;
break;}
case 19:
# 228 "parse.y"
{ headerfilename = copy_string( nmstr ); ;
break;}
case 20:
# 230 "parse.y"
{ tablesext = 1; tablesfilename = copy_string( nmstr ); ;
break;}
case 21:
# 234 "parse.y"
{ scon_stk_ptr = yyvsp[-3]; ;
break;}
case 22:
# 236 "parse.y"
{ scon_stk_ptr = yyvsp[-3]; ;
break;}
case 24:
# 241 "parse.y"
{
trlcontxt = variable_trail_rule = varlength = 0;
trailcnt = headcnt = rulelen = 0;
current_state_type = 0x1;
previous_continued_action = continued_action;
in_rule = 1;
new_rule();
;
break;}
case 25:
# 254 "parse.y"
{
pat = yyvsp[0];
finish_rule( pat, variable_trail_rule,
headcnt, trailcnt , previous_continued_action);
if ( scon_stk_ptr > 0 )
{
for ( i = 1; i <= scon_stk_ptr; ++i )
scbol[scon_stk[i]] =
mkbranch( scbol[scon_stk[i]],
pat );
}
else
{
for ( i = 1; i <= lastsc; ++i )
if ( ! scxclu[i] )
scbol[i] = mkbranch( scbol[i],
pat );
}
if ( ! bol_needed )
{
bol_needed = 1;
if ( performance_report > 1 )
pinpoint_message(
"'^' operator results in sub-optimal performance" );
}
;
break;}
case 26:
# 290 "parse.y"
{
pat = yyvsp[0];
finish_rule( pat, variable_trail_rule,
headcnt, trailcnt , previous_continued_action);
if ( scon_stk_ptr > 0 )
{
for ( i = 1; i <= scon_stk_ptr; ++i )
scset[scon_stk[i]] =
mkbranch( scset[scon_stk[i]],
pat );
}
else
{
for ( i = 1; i <= lastsc; ++i )
if ( ! scxclu[i] )
scset[i] =
mkbranch( scset[i],
pat );
}
;
break;}
case 27:
# 314 "parse.y"
{
if ( scon_stk_ptr > 0 )
build_eof_action();
else
{
for ( i = 1; i <= lastsc; ++i )
if ( ! sceof[i] )
scon_stk[++scon_stk_ptr] = i;
if ( scon_stk_ptr == 0 )
warn(
"all start conditions already have <<EOF>> rules" );
else
build_eof_action();
}
;
break;}
case 28:
# 337 "parse.y"
{ synerr( "unrecognized rule" ); ;
break;}
case 29:
# 341 "parse.y"
{ yyval = scon_stk_ptr; ;
break;}
case 30:
# 345 "parse.y"
{ yyval = yyvsp[-2]; ;
break;}
case 31:
# 348 "parse.y"
{
yyval = scon_stk_ptr;
for ( i = 1; i <= lastsc; ++i )
{
int j;
for ( j = 1; j <= scon_stk_ptr; ++j )
if ( scon_stk[j] == i )
break;
if ( j > scon_stk_ptr )
scon_stk[++scon_stk_ptr] = i;
}
;
break;}
case 32:
# 365 "parse.y"
{ yyval = scon_stk_ptr; ;
break;}
case 35:
# 373 "parse.y"
{ synerr( "bad start condition list" ); ;
break;}
case 36:
# 377 "parse.y"
{
if ( (scnum = sclookup( nmstr )) == 0 )
format_pinpoint_message(
"undeclared start condition %s",
nmstr );
else
{
for ( i = 1; i <= scon_stk_ptr; ++i )
if ( scon_stk[i] == scnum )
{
format_warn(
"<%s> specified twice",
scname[scnum] );
break;
}
if ( i > scon_stk_ptr )
scon_stk[++scon_stk_ptr] = scnum;
}
;
break;}
case 37:
# 400 "parse.y"
{
if ( transchar[lastst[yyvsp[0]]] != (256 + 1) )
yyvsp[0] = link_machines( yyvsp[0],
mkstate( (256 + 1) ) );
mark_beginning_as_normal( yyvsp[0] );
current_state_type = 0x1;
if ( previous_continued_action )
{
# 422 "parse.y"
if ( ! varlength || headcnt != 0 )
warn(
"trailing context made variable due to preceding '|' action" );
varlength = 1;
headcnt = 0;
}
if ( lex_compat || (varlength && headcnt == 0) )
{
# 444 "parse.y"
add_accept( yyvsp[-1],
num_rules | 0x4000 );
variable_trail_rule = 1;
}
else
trailcnt = rulelen;
yyval = link_machines( yyvsp[-1], yyvsp[0] );
;
break;}
case 38:
# 456 "parse.y"
{ synerr( "trailing context used twice" ); ;
break;}
case 39:
# 459 "parse.y"
{
headcnt = 0;
trailcnt = 1;
rulelen = 1;
varlength = 0;
current_state_type = 0x2;
if ( trlcontxt )
{
synerr( "trailing context used twice" );
yyval = mkstate( (256 + 1) );
}
else if ( previous_continued_action )
{
warn(
"trailing context made variable due to preceding '|' action" );
varlength = 1;
}
if ( lex_compat || varlength )
{
add_accept( yyvsp[-1],
num_rules | 0x4000 );
variable_trail_rule = 1;
}
trlcontxt = 1;
eps = mkstate( (256 + 1) );
yyval = link_machines( yyvsp[-1],
link_machines( eps, mkstate( '\n' ) ) );
;
break;}
case 40:
# 502 "parse.y"
{
yyval = yyvsp[0];
if ( trlcontxt )
{
if ( lex_compat || (varlength && headcnt == 0) )
variable_trail_rule = 1;
else
trailcnt = rulelen;
}
;
break;}
case 41:
# 520 "parse.y"
{
varlength = 1;
yyval = mkor( yyvsp[-2], yyvsp[0] );
;
break;}
case 42:
# 526 "parse.y"
{ yyval = yyvsp[0]; ;
break;}
case 43:
# 531 "parse.y"
{
if ( trlcontxt )
synerr( "trailing context used twice" );
else
trlcontxt = 1;
if ( varlength )
varlength = 0;
else
headcnt = rulelen;
rulelen = 0;
current_state_type = 0x2;
yyval = yyvsp[-1];
;
break;}
case 44:
# 558 "parse.y"
{
yyval = link_machines( yyvsp[-1], yyvsp[0] );
;
break;}
case 45:
# 566 "parse.y"
{ yyval = yyvsp[0]; ;
break;}
case 46:
# 569 "parse.y"
{
varlength = 1;
if ( yyvsp[-3] > yyvsp[-1] || yyvsp[-3] < 0 )
{
synerr( "bad iteration values" );
yyval = yyvsp[-5];
}
else
{
if ( yyvsp[-3] == 0 )
{
if ( yyvsp[-1] <= 0 )
{
synerr(
"bad iteration values" );
yyval = yyvsp[-5];
}
else
yyval = mkopt(
mkrep( yyvsp[-5], 1, yyvsp[-1] ) );
}
else
yyval = mkrep( yyvsp[-5], yyvsp[-3], yyvsp[-1] );
}
;
break;}
case 47:
# 597 "parse.y"
{
varlength = 1;
if ( yyvsp[-2] <= 0 )
{
synerr( "iteration value must be positive" );
yyval = yyvsp[-4];
}
else
yyval = mkrep( yyvsp[-4], yyvsp[-2], -1 );
;
break;}
case 48:
# 611 "parse.y"
{
varlength = 1;
if ( yyvsp[-1] <= 0 )
{
synerr( "iteration value must be positive"
);
yyval = yyvsp[-3];
}
else
yyval = link_machines( yyvsp[-3],
copysingl( yyvsp[-3], yyvsp[-1] - 1 ) );
;
break;}
case 49:
# 633 "parse.y"
{
varlength = 1;
yyval = mkclos( yyvsp[-1] );
;
break;}
case 50:
# 640 "parse.y"
{
varlength = 1;
yyval = mkposcl( yyvsp[-1] );
;
break;}
case 51:
# 646 "parse.y"
{
varlength = 1;
yyval = mkopt( yyvsp[-1] );
;
break;}
case 52:
# 652 "parse.y"
{
varlength = 1;
if ( yyvsp[-3] > yyvsp[-1] || yyvsp[-3] < 0 )
{
synerr( "bad iteration values" );
yyval = yyvsp[-5];
}
else
{
if ( yyvsp[-3] == 0 )
{
if ( yyvsp[-1] <= 0 )
{
synerr(
"bad iteration values" );
yyval = yyvsp[-5];
}
else
yyval = mkopt(
mkrep( yyvsp[-5], 1, yyvsp[-1] ) );
}
else
yyval = mkrep( yyvsp[-5], yyvsp[-3], yyvsp[-1] );
}
;
break;}
case 53:
# 680 "parse.y"
{
varlength = 1;
if ( yyvsp[-2] <= 0 )
{
synerr( "iteration value must be positive" );
yyval = yyvsp[-4];
}
else
yyval = mkrep( yyvsp[-4], yyvsp[-2], -1 );
;
break;}
case 54:
# 694 "parse.y"
{
varlength = 1;
if ( yyvsp[-1] <= 0 )
{
synerr( "iteration value must be positive" );
yyval = yyvsp[-3];
}
else
yyval = link_machines( yyvsp[-3],
copysingl( yyvsp[-3], yyvsp[-1] - 1 ) );
;
break;}
case 55:
# 713 "parse.y"
{
if ( ! madeany )
{
anyccl = cclinit();
ccladd( anyccl, '\n' );
cclnegate( anyccl );
if ( useecs )
mkeccl( ccltbl + cclmap[anyccl],
ccllen[anyccl], nextecm,
ecgroup, csize, csize );
madeany = 1;
}
++rulelen;
yyval = mkstate( -anyccl );
;
break;}
case 56:
# 735 "parse.y"
{
if ( ! cclsorted )
cshell( ccltbl + cclmap[yyvsp[0]], ccllen[yyvsp[0]], 1 );
if ( useecs )
mkeccl( ccltbl + cclmap[yyvsp[0]], ccllen[yyvsp[0]],
nextecm, ecgroup, csize, csize );
++rulelen;
if (ccl_has_nl[yyvsp[0]])
rule_has_nl[num_rules] = 1;
yyval = mkstate( -yyvsp[0] );
;
break;}
case 57:
# 756 "parse.y"
{
++rulelen;
if (ccl_has_nl[yyvsp[0]])
rule_has_nl[num_rules] = 1;
yyval = mkstate( -yyvsp[0] );
;
break;}
case 58:
# 766 "parse.y"
{ yyval = yyvsp[-1]; ;
break;}
case 59:
# 769 "parse.y"
{ yyval = yyvsp[-1]; ;
break;}
case 60:
# 772 "parse.y"
{
++rulelen;
if ( caseins && yyvsp[0] >= 'A' && yyvsp[0] <= 'Z' )
yyvsp[0] = clower( yyvsp[0] );
if (yyvsp[0] == nlch)
rule_has_nl[num_rules] = 1;
yyval = mkstate( yyvsp[0] );
;
break;}
case 61:
# 786 "parse.y"
{ yyval = yyvsp[-1]; ;
break;}
case 62:
# 789 "parse.y"
{
cclnegate( yyvsp[-1] );
yyval = yyvsp[-1];
;
break;}
case 63:
# 796 "parse.y"
{
if (caseins)
{
if (((__ctype_ptr)[(unsigned)(yyvsp[-2])]&01) && ((__ctype_ptr)[(unsigned)(yyvsp[0])]&01))
{
yyvsp[-2] = __extension__ ({ int __x = (yyvsp[-2]); ((__ctype_ptr)[(unsigned)(__x)]&01) ? (__x - 'A' + 'a') : __x;});
yyvsp[0] = __extension__ ({ int __x = (yyvsp[0]); ((__ctype_ptr)[(unsigned)(__x)]&01) ? (__x - 'A' + 'a') : __x;});
}
else if (has_case (yyvsp[-2]) != has_case (yyvsp[0])
|| (has_case (yyvsp[-2]) && ((((__ctype_ptr)[(unsigned)(yyvsp[-2])]&02)?1:0) != (((__ctype_ptr)[(unsigned)(yyvsp[0])]&02)?1:0))))
do{ char fw3_msg[2048]; snprintf( fw3_msg, 2048,("the character range [%c-%c] is ambiguous in a case-insensitive scanner"), (yyvsp[-2]), (yyvsp[0]) ); warn( fw3_msg ); }while(0);
# 825 "parse.y"
else if (!has_case (yyvsp[-2]) && !has_case (yyvsp[0]) && !range_covers_case (yyvsp[-2], yyvsp[0]))
do{ char fw3_msg[2048]; snprintf( fw3_msg, 2048,("the character range [%c-%c] is ambiguous in a case-insensitive scanner"), (yyvsp[-2]), (yyvsp[0]) ); warn( fw3_msg ); }while(0);
}
if ( yyvsp[-2] > yyvsp[0] )
synerr( "negative range in character class" );
else
{
for ( i = yyvsp[-2]; i <= yyvsp[0]; ++i )
ccladd( yyvsp[-3], i );
cclsorted = cclsorted && (yyvsp[-2] > lastchar);
lastchar = yyvsp[0];
}
yyval = yyvsp[-3];
;
break;}
case 64:
# 850 "parse.y"
{
if ( caseins && yyvsp[0] >= 'A' && yyvsp[0] <= 'Z' )
yyvsp[0] = clower( yyvsp[0] );
ccladd( yyvsp[-1], yyvsp[0] );
cclsorted = cclsorted && (yyvsp[0] > lastchar);
lastchar = yyvsp[0];
yyval = yyvsp[-1];
;
break;}
case 65:
# 861 "parse.y"
{
cclsorted = 0;
yyval = yyvsp[-1];
;
break;}
case 66:
# 868 "parse.y"
{
cclsorted = 1;
lastchar = 0;
currccl = yyval = cclinit();
;
break;}
case 67:
# 875 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&(01|02|04)) ) ccladd( currccl, c ); }while(0); ;
break;}
case 68:
# 876 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&(01|02)) ) ccladd( currccl, c ); }while(0); ;
break;}
case 69:
# 877 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((c) == ' ' || (c) == '\t') ) ccladd( currccl, c ); }while(0); ;
break;}
case 70:
# 878 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&040) ) ccladd( currccl, c ); }while(0); ;
break;}
case 71:
# 879 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&04) ) ccladd( currccl, c ); }while(0); ;
break;}
case 72:
# 880 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&(020|01|02|04)) ) ccladd( currccl, c ); }while(0); ;
break;}
case 73:
# 881 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&02) ) ccladd( currccl, c ); }while(0); ;
break;}
case 74:
# 882 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&(020|01|02|04|0200)) ) ccladd( currccl, c ); }while(0); ;
break;}
case 75:
# 883 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&020) ) ccladd( currccl, c ); }while(0); ;
break;}
case 76:
# 884 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&010) ) ccladd( currccl, c ); }while(0); ;
break;}
case 77:
# 885 "parse.y"
{
if ( caseins )
do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&02) ) ccladd( currccl, c ); }while(0);
else
do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&01) ) ccladd( currccl, c ); }while(0);
;
break;}
case 78:
# 891 "parse.y"
{ do{ int c; for ( c = 0; c < csize; ++c ) if ( ((unsigned)(c)<=0177) && ((__ctype_ptr)[(unsigned)(c)]&(0100|04)) ) ccladd( currccl, c ); }while(0); ;
break;}
case 79:
# 895 "parse.y"
{
if ( caseins && yyvsp[0] >= 'A' && yyvsp[0] <= 'Z' )
yyvsp[0] = clower( yyvsp[0] );
if ( yyvsp[0] == nlch )
rule_has_nl[num_rules] = 1;
++rulelen;
yyval = link_machines( yyvsp[-1], mkstate( yyvsp[0] ) );
;
break;}
case 80:
# 908 "parse.y"
{ yyval = mkstate( (256 + 1) ); ;
break;}
}
# 543 "/usr/lib/bison.simple"
yyvsp -= yylen;
yyssp -= yylen;
# 561 "/usr/lib/bison.simple"
*++yyvsp = yyval;
# 585 "/usr/lib/bison.simple"
yyn = yyr1[yyn];
yystate = yypgoto[yyn - 54] + *yyssp;
if (yystate >= 0 && yystate <= 131 && yycheck[yystate] == *yyssp)
yystate = yytable[yystate];
else
yystate = yydefgoto[yyn - 54];
goto yynewstate;
yyerrlab:
if (! yyerrstatus)
{
++yynerrs;
# 643 "/usr/lib/bison.simple"
yyerror("parse error");
}
goto yyerrlab1;
yyerrlab1:
if (yyerrstatus == 3)
{
if (yychar == 0)
goto yyabortlab;
yychar = -2;
}
yyerrstatus = 3;
goto yyerrhandle;
yyerrdefault:
# 681 "/usr/lib/bison.simple"
yyerrpop:
if (yyssp == yyss) goto yyabortlab;
yyvsp--;
yystate = *--yyssp;
# 701 "/usr/lib/bison.simple"
yyerrhandle:
yyn = yypact[yystate];
if (yyn == -32768)
goto yyerrdefault;
yyn += 1;
if (yyn < 0 || yyn > 131 || yycheck[yyn] != 1)
goto yyerrdefault;
yyn = yytable[yyn];
if (yyn < 0)
{
if (yyn == -32768)
goto yyerrpop;
yyn = -yyn;
goto yyreduce;
}
else if (yyn == 0)
goto yyerrpop;
if (yyn == 120)
goto yyacceptlab;
*++yyvsp = yylval;
yystate = yyn;
goto yynewstate;
yyacceptlab:
if (yyfree_stacks)
{
free (yyss);
free (yyvs);
}
return 0;
yyabortlab:
if (yyfree_stacks)
{
free (yyss);
free (yyvs);
}
return 1;
}
# 911 "parse.y"
void build_eof_action()
{
register int i;
char action_text[2048];
for ( i = 1; i <= scon_stk_ptr; ++i )
{
if ( sceof[scon_stk[i]] )
format_pinpoint_message(
"multiple <<EOF>> rules for start condition %s",
scname[scon_stk[i]] );
else
{
sceof[scon_stk[i]] = 1;
sprintf( action_text, "case YY_STATE_EOF(%s):\n",
scname[scon_stk[i]] );
add_action( action_text );
}
}
line_directive_out( (FILE *) 0, 1 );
--num_rules;
++num_eof_rules;
}
void format_synerr( msg, arg )
const char *msg, arg[];
{
char errmsg[2048];
(void) sprintf( errmsg, msg, arg );
synerr( errmsg );
}
void synerr( str )
const char *str;
{
syntaxerror = 1;
pinpoint_message( str );
}
void format_warn( msg, arg )
const char *msg, arg[];
{
char warn_msg[2048];
(void) sprintf( warn_msg, msg, arg );
warn( warn_msg );
}
void warn( str )
const char *str;
{
line_warning( str, linenum );
}
void format_pinpoint_message( msg, arg )
const char *msg, arg[];
{
char errmsg[2048];
(void) sprintf( errmsg, msg, arg );
pinpoint_message( errmsg );
}
void pinpoint_message( str )
const char *str;
{
line_pinpoint( str, linenum );
}
void line_warning( str, line )
const char *str;
int line;
{
char warning[2048];
if ( ! nowarn )
{
sprintf( warning, "warning, %s", str );
line_pinpoint( warning, line );
}
}
void line_pinpoint( str, line )
const char *str;
int line;
{
fprintf( (_impure_ptr->_stderr), "%s:%d: %s\n", infilename, line, str );
}
void yyerror( msg )
const char *msg;
{
}
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: Huge compile time regressions
2006-01-05 22:06 ` Joern RENNECKE
@ 2006-01-05 22:10 ` Joern RENNECKE
2006-01-05 22:20 ` Joern RENNECKE
0 siblings, 1 reply; 16+ messages in thread
From: Joern RENNECKE @ 2006-01-05 22:10 UTC (permalink / raw)
To: Joern Rennecke; +Cc: Bernd Schmidt, Daniel Berlin, Steven Bosscher, gcc
[-- Attachment #1: Type: text/plain, Size: 323 bytes --]
Joern Rennecke wrote:
> I've found that the most striking compilation time increase was for
> flex / parse.c, which is a bison parser.
> -Os compilation for i686-pc-linux-gnu X sh-elf --disable-checking went
> from 0.95 to 4.5 seconds.
>
Optimizing the REG_SET_EQ invocations gave a moderate win, down to 3.5
seconds.
[-- Attachment #2: cmove_diff-20060105-eq-opt --]
[-- Type: text/plain, Size: 28714 bytes --]
2006-01-05 J"orn Rennecke <joern.rennecke@st.com>
* cfgcleanup.c: Reinstate patches for PR 20070
* struct-equiv.c (struct_equiv_regs_eq_p): New function.
(struct_equiv_init): Only call update_life_info_in_dirty_blocks
in order to initialize regsets if both blocks are dirty.
Make do sanity check of registers bening equal for STRUCT_EQUIV_FINAL.
Add new parameter check_regs_eq. Changed all callers.
* basic-block.h (struct_equiv_init): Update prototype.
Index: cfgcleanup.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L cfgcleanup.c (revision 109329) -L cfgcleanup.c (working copy) .svn/text-base/cfgcleanup.c.svn-base cfgcleanup.c
--- cfgcleanup.c (revision 109329)
+++ cfgcleanup.c (working copy)
@@ -60,9 +60,7 @@ Software Foundation, 51 Franklin Street,
static bool first_pass;
static bool try_crossjump_to_edge (int, edge, edge);
static bool try_crossjump_bb (int, basic_block);
-static bool outgoing_edges_match (int, basic_block, basic_block);
-static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
-static bool old_insns_match_p (int, rtx, rtx);
+static bool outgoing_edges_match (int *, struct equiv_info *);
static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
@@ -74,7 +72,6 @@ static bool mark_effect (rtx, bitmap);
static void notice_new_block (basic_block);
static void update_forwarder_flag (basic_block);
static int mentions_nonequal_regs (rtx *, void *);
-static void merge_memattrs (rtx, rtx);
\f
/* Set flags for newly created block. */
@@ -881,319 +878,6 @@ merge_blocks_move (edge e, basic_block b
return NULL;
}
\f
-
-/* Removes the memory attributes of MEM expression
- if they are not equal. */
-
-void
-merge_memattrs (rtx x, rtx y)
-{
- int i;
- int j;
- enum rtx_code code;
- const char *fmt;
-
- if (x == y)
- return;
- if (x == 0 || y == 0)
- return;
-
- code = GET_CODE (x);
-
- if (code != GET_CODE (y))
- return;
-
- if (GET_MODE (x) != GET_MODE (y))
- return;
-
- if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
- {
- if (! MEM_ATTRS (x))
- MEM_ATTRS (y) = 0;
- else if (! MEM_ATTRS (y))
- MEM_ATTRS (x) = 0;
- else
- {
- rtx mem_size;
-
- if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
- {
- set_mem_alias_set (x, 0);
- set_mem_alias_set (y, 0);
- }
-
- if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
- {
- set_mem_expr (x, 0);
- set_mem_expr (y, 0);
- set_mem_offset (x, 0);
- set_mem_offset (y, 0);
- }
- else if (MEM_OFFSET (x) != MEM_OFFSET (y))
- {
- set_mem_offset (x, 0);
- set_mem_offset (y, 0);
- }
-
- if (!MEM_SIZE (x))
- mem_size = NULL_RTX;
- else if (!MEM_SIZE (y))
- mem_size = NULL_RTX;
- else
- mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
- INTVAL (MEM_SIZE (y))));
- set_mem_size (x, mem_size);
- set_mem_size (y, mem_size);
-
- set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
- set_mem_align (y, MEM_ALIGN (x));
- }
- }
-
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- switch (fmt[i])
- {
- case 'E':
- /* Two vectors must have the same length. */
- if (XVECLEN (x, i) != XVECLEN (y, i))
- return;
-
- for (j = 0; j < XVECLEN (x, i); j++)
- merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
-
- break;
-
- case 'e':
- merge_memattrs (XEXP (x, i), XEXP (y, i));
- }
- }
- return;
-}
-
-
-/* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
-
-static bool
-old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
-{
- rtx p1, p2;
-
- /* Verify that I1 and I2 are equivalent. */
- if (GET_CODE (i1) != GET_CODE (i2))
- return false;
-
- p1 = PATTERN (i1);
- p2 = PATTERN (i2);
-
- if (GET_CODE (p1) != GET_CODE (p2))
- return false;
-
- /* If this is a CALL_INSN, compare register usage information.
- If we don't check this on stack register machines, the two
- CALL_INSNs might be merged leaving reg-stack.c with mismatching
- numbers of stack registers in the same basic block.
- If we don't check this on machines with delay slots, a delay slot may
- be filled that clobbers a parameter expected by the subroutine.
-
- ??? We take the simple route for now and assume that if they're
- equal, they were constructed identically. */
-
- if (CALL_P (i1)
- && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
- CALL_INSN_FUNCTION_USAGE (i2))
- || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
- return false;
-
-#ifdef STACK_REGS
- /* If cross_jump_death_matters is not 0, the insn's mode
- indicates whether or not the insn contains any stack-like
- regs. */
-
- if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
- {
- /* If register stack conversion has already been done, then
- death notes must also be compared before it is certain that
- the two instruction streams match. */
-
- rtx note;
- HARD_REG_SET i1_regset, i2_regset;
-
- CLEAR_HARD_REG_SET (i1_regset);
- CLEAR_HARD_REG_SET (i2_regset);
-
- for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
- SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
-
- for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
- SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
-
- GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
-
- return false;
-
- done:
- ;
- }
-#endif
-
- if (reload_completed
- ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
- return true;
-
- /* Do not do EQUIV substitution after reload. First, we're undoing the
- work of reload_cse. Second, we may be undoing the work of the post-
- reload splitting pass. */
- /* ??? Possibly add a new phase switch variable that can be used by
- targets to disallow the troublesome insns after splitting. */
- if (!reload_completed)
- {
- /* The following code helps take care of G++ cleanups. */
- rtx equiv1 = find_reg_equal_equiv_note (i1);
- rtx equiv2 = find_reg_equal_equiv_note (i2);
-
- if (equiv1 && equiv2
- /* If the equivalences are not to a constant, they may
- reference pseudos that no longer exist, so we can't
- use them. */
- && (! reload_completed
- || (CONSTANT_P (XEXP (equiv1, 0))
- && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
- {
- rtx s1 = single_set (i1);
- rtx s2 = single_set (i2);
- if (s1 != 0 && s2 != 0
- && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
- {
- validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
- validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
- if (! rtx_renumbered_equal_p (p1, p2))
- cancel_changes (0);
- else if (apply_change_group ())
- return true;
- }
- }
- }
-
- return false;
-}
-\f
-/* Look through the insns at the end of BB1 and BB2 and find the longest
- sequence that are equivalent. Store the first insns for that sequence
- in *F1 and *F2 and return the sequence length.
-
- To simplify callers of this function, if the blocks match exactly,
- store the head of the blocks in *F1 and *F2. */
-
-static int
-flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
- basic_block bb2, rtx *f1, rtx *f2)
-{
- rtx i1, i2, last1, last2, afterlast1, afterlast2;
- int ninsns = 0;
-
- /* Skip simple jumps at the end of the blocks. Complex jumps still
- need to be compared for equivalence, which we'll do below. */
-
- i1 = BB_END (bb1);
- last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
- if (onlyjump_p (i1)
- || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
- {
- last1 = i1;
- i1 = PREV_INSN (i1);
- }
-
- i2 = BB_END (bb2);
- if (onlyjump_p (i2)
- || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
- {
- last2 = i2;
- /* Count everything except for unconditional jump as insn. */
- if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
- ninsns++;
- i2 = PREV_INSN (i2);
- }
-
- while (true)
- {
- /* Ignore notes. */
- while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
- i1 = PREV_INSN (i1);
-
- while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
- i2 = PREV_INSN (i2);
-
- if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
- break;
-
- if (!old_insns_match_p (mode, i1, i2))
- break;
-
- merge_memattrs (i1, i2);
-
- /* Don't begin a cross-jump with a NOTE insn. */
- if (INSN_P (i1))
- {
- /* If the merged insns have different REG_EQUAL notes, then
- remove them. */
- rtx equiv1 = find_reg_equal_equiv_note (i1);
- rtx equiv2 = find_reg_equal_equiv_note (i2);
-
- if (equiv1 && !equiv2)
- remove_note (i1, equiv1);
- else if (!equiv1 && equiv2)
- remove_note (i2, equiv2);
- else if (equiv1 && equiv2
- && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
- {
- remove_note (i1, equiv1);
- remove_note (i2, equiv2);
- }
-
- afterlast1 = last1, afterlast2 = last2;
- last1 = i1, last2 = i2;
- ninsns++;
- }
-
- i1 = PREV_INSN (i1);
- i2 = PREV_INSN (i2);
- }
-
-#ifdef HAVE_cc0
- /* Don't allow the insn after a compare to be shared by
- cross-jumping unless the compare is also shared. */
- if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
- last1 = afterlast1, last2 = afterlast2, ninsns--;
-#endif
-
- /* Include preceding notes and labels in the cross-jump. One,
- this may bring us to the head of the blocks as requested above.
- Two, it keeps line number notes as matched as may be. */
- if (ninsns)
- {
- while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
- last1 = PREV_INSN (last1);
-
- if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
- last1 = PREV_INSN (last1);
-
- while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
- last2 = PREV_INSN (last2);
-
- if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
- last2 = PREV_INSN (last2);
-
- *f1 = last1;
- *f2 = last2;
- }
-
- return ninsns;
-}
-
/* Return true iff the condbranches at the end of BB1 and BB2 match. */
bool
condjump_equiv_p (struct equiv_info *info, bool call_init)
@@ -1252,8 +936,8 @@ condjump_equiv_p (struct equiv_info *inf
if (code2 == UNKNOWN)
return false;
- if (call_init && !struct_equiv_init (STRUCT_EQUIV_START | info->mode, info))
- gcc_unreachable ();
+ if (call_init)
+ struct_equiv_init (STRUCT_EQUIV_START | info->mode, info, false);
/* Make the sources of the pc sets unreadable so that when we call
insns_match_p it won't process them.
The death_notes_match_p from insns_match_p won't see the local registers
@@ -1322,15 +1006,20 @@ condjump_equiv_p (struct equiv_info *inf
return match;
}
-/* Return true iff outgoing edges of BB1 and BB2 match, together with
- the branch instruction. This means that if we commonize the control
- flow before end of the basic block, the semantic remains unchanged.
+/* Return true iff outgoing edges of INFO->y_block and INFO->x_block match,
+ together with the branch instruction. This means that if we commonize the
+ control flow before end of the basic block, the semantic remains unchanged.
+ If we need to compare jumps, we set STRUCT_EQUIV_MATCH_JUMPS in *MODE,
+ and pass *MODE to struct_equiv_init or assign it to INFO->mode, as
+ appropriate.
We may assume that there exists one edge with a common destination. */
static bool
-outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
+outgoing_edges_match (int *mode, struct equiv_info *info)
{
+ basic_block bb1 = info->y_block;
+ basic_block bb2 = info->x_block;
int nehedges1 = 0, nehedges2 = 0;
edge fallthru1 = 0, fallthru2 = 0;
edge e1, e2;
@@ -1346,114 +1035,19 @@ outgoing_edges_match (int mode, basic_bl
& (EDGE_COMPLEX | EDGE_FAKE)) == 0
&& (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
+ *mode |= STRUCT_EQUIV_MATCH_JUMPS;
/* Match conditional jumps - this may get tricky when fallthru and branch
edges are crossed. */
if (EDGE_COUNT (bb1->succs) == 2
&& any_condjump_p (BB_END (bb1))
&& onlyjump_p (BB_END (bb1)))
{
- edge b1, f1, b2, f2;
- bool reverse, match;
- rtx set1, set2, cond1, cond2;
- enum rtx_code code1, code2;
-
if (EDGE_COUNT (bb2->succs) != 2
|| !any_condjump_p (BB_END (bb2))
|| !onlyjump_p (BB_END (bb2)))
return false;
-
- b1 = BRANCH_EDGE (bb1);
- b2 = BRANCH_EDGE (bb2);
- f1 = FALLTHRU_EDGE (bb1);
- f2 = FALLTHRU_EDGE (bb2);
-
- /* Get around possible forwarders on fallthru edges. Other cases
- should be optimized out already. */
- if (FORWARDER_BLOCK_P (f1->dest))
- f1 = single_succ_edge (f1->dest);
-
- if (FORWARDER_BLOCK_P (f2->dest))
- f2 = single_succ_edge (f2->dest);
-
- /* To simplify use of this function, return false if there are
- unneeded forwarder blocks. These will get eliminated later
- during cleanup_cfg. */
- if (FORWARDER_BLOCK_P (f1->dest)
- || FORWARDER_BLOCK_P (f2->dest)
- || FORWARDER_BLOCK_P (b1->dest)
- || FORWARDER_BLOCK_P (b2->dest))
- return false;
-
- if (f1->dest == f2->dest && b1->dest == b2->dest)
- reverse = false;
- else if (f1->dest == b2->dest && b1->dest == f2->dest)
- reverse = true;
- else
- return false;
-
- set1 = pc_set (BB_END (bb1));
- set2 = pc_set (BB_END (bb2));
- if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
- != (XEXP (SET_SRC (set2), 1) == pc_rtx))
- reverse = !reverse;
-
- cond1 = XEXP (SET_SRC (set1), 0);
- cond2 = XEXP (SET_SRC (set2), 0);
- code1 = GET_CODE (cond1);
- if (reverse)
- code2 = reversed_comparison_code (cond2, BB_END (bb2));
- else
- code2 = GET_CODE (cond2);
-
- if (code2 == UNKNOWN)
- return false;
-
- /* Verify codes and operands match. */
- match = ((code1 == code2
- && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
- && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
- || (code1 == swap_condition (code2)
- && rtx_renumbered_equal_p (XEXP (cond1, 1),
- XEXP (cond2, 0))
- && rtx_renumbered_equal_p (XEXP (cond1, 0),
- XEXP (cond2, 1))));
-
- /* If we return true, we will join the blocks. Which means that
- we will only have one branch prediction bit to work with. Thus
- we require the existing branches to have probabilities that are
- roughly similar. */
- if (match
- && !optimize_size
- && maybe_hot_bb_p (bb1)
- && maybe_hot_bb_p (bb2))
- {
- int prob2;
-
- if (b1->dest == b2->dest)
- prob2 = b2->probability;
- else
- /* Do not use f2 probability as f2 may be forwarded. */
- prob2 = REG_BR_PROB_BASE - b2->probability;
-
- /* Fail if the difference in probabilities is greater than 50%.
- This rules out two well-predicted branches with opposite
- outcomes. */
- if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
- {
- if (dump_file)
- fprintf (dump_file,
- "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
- bb1->index, bb2->index, b1->probability, prob2);
-
- return false;
- }
- }
-
- if (dump_file && match)
- fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
- bb1->index, bb2->index);
-
- return match;
+ info->mode = *mode;
+ return condjump_equiv_p (info, true);
}
/* Generic case - we are seeing a computed jump, table jump or trapping
@@ -1501,31 +1095,22 @@ outgoing_edges_match (int mode, basic_bl
identical = false;
}
- if (identical)
+ if (identical
+ && struct_equiv_init (STRUCT_EQUIV_START | *mode, info, true))
{
- replace_label_data rr;
bool match;
- /* Temporarily replace references to LABEL1 with LABEL2
+ /* Indicate that LABEL1 is to be replaced with LABEL2
in BB1->END so that we could compare the instructions. */
- rr.r1 = label1;
- rr.r2 = label2;
- rr.update_label_nuses = false;
- for_each_rtx (&BB_END (bb1), replace_label, &rr);
+ info->y_label = label1;
+ info->x_label = label2;
- match = old_insns_match_p (mode, BB_END (bb1), BB_END (bb2));
+ match = insns_match_p (BB_END (bb1), BB_END (bb2), info);
if (dump_file && match)
fprintf (dump_file,
"Tablejumps in bb %i and %i match.\n",
bb1->index, bb2->index);
- /* Set the original label in BB1->END because when deleting
- a block whose end is a tablejump, the tablejump referenced
- from the instruction is deleted too. */
- rr.r1 = label2;
- rr.r2 = label1;
- for_each_rtx (&BB_END (bb1), replace_label, &rr);
-
return match;
}
}
@@ -1535,7 +1120,10 @@ outgoing_edges_match (int mode, basic_bl
/* First ensure that the instructions match. There may be many outgoing
edges so this test is generally cheaper. */
- if (!old_insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
+ /* FIXME: the regset compare might be costly. We should try to get a cheap
+ and reasonably effective test first. */
+ if (!struct_equiv_init (STRUCT_EQUIV_START | *mode, info, true)
+ || !insns_match_p (BB_END (bb1), BB_END (bb2), info))
return false;
/* Search the outgoing edges, ensure that the counts do match, find possible
@@ -1601,22 +1189,21 @@ outgoing_edges_match (int mode, basic_bl
static bool
try_crossjump_to_edge (int mode, edge e1, edge e2)
{
- int nmatch;
+ int nmatch, i;
basic_block src1 = e1->src, src2 = e2->src;
basic_block redirect_to, redirect_from, to_remove;
- rtx newpos1, newpos2;
edge s;
edge_iterator ei;
-
- newpos1 = newpos2 = NULL_RTX;
+ struct equiv_info info;
+ rtx x_active, y_active;
/* If we have partitioned hot/cold basic blocks, it is a bad idea
- to try this optimization.
+ to try this optimization.
Basic block partitioning may result in some jumps that appear to
- be optimizable (or blocks that appear to be mergeable), but which really
- must be left untouched (they are required to make it safely across
- partition boundaries). See the comments at the top of
+ be optimizable (or blocks that appear to be mergeable), but which really
+ must be left untouched (they are required to make it safely across
+ partition boundaries). See the comments at the top of
bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
if (flag_reorder_blocks_and_partition && no_new_pseudos)
@@ -1655,19 +1242,66 @@ try_crossjump_to_edge (int mode, edge e1
return false;
/* Look for the common insn sequence, part the first ... */
- if (!outgoing_edges_match (mode, src1, src2))
+ info.x_block = src2;
+ info.y_block = src1;
+ if (!outgoing_edges_match (&mode, &info))
return false;
/* ... and part the second. */
- nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
+ info.input_cost = optimize_size ? COSTS_N_INSNS (1) : -1;
+ nmatch = struct_equiv_block_eq (STRUCT_EQUIV_START | mode, &info);
/* Don't proceed with the crossjump unless we found a sufficient number
of matching instructions or the 'from' block was totally matched
(such that its predecessors will hopefully be redirected and the
block removed). */
- if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
- && (newpos1 != BB_HEAD (src1)))
+ if (!nmatch)
return false;
+ if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+ && (info.cur.y_start != BB_HEAD (src1)))
+ return false;
+ while (info.need_rerun)
+ {
+ nmatch = struct_equiv_block_eq (STRUCT_EQUIV_RERUN | mode, &info);
+ if (!nmatch)
+ return false;
+ if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+ && (info.cur.y_start != BB_HEAD (src1)))
+ return false;
+ }
+ nmatch = struct_equiv_block_eq (STRUCT_EQUIV_FINAL | mode, &info);
+ if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+ && (info.cur.y_start != BB_HEAD (src1)))
+ return false;
+
+ /* Skip possible basic block header. */
+ x_active = info.cur.x_start;
+ if (LABEL_P (x_active))
+ x_active = NEXT_INSN (x_active);
+ if (NOTE_P (x_active))
+ x_active = NEXT_INSN (x_active);
+
+ y_active = info.cur.y_start;
+ if (LABEL_P (y_active))
+ y_active = NEXT_INSN (y_active);
+ if (NOTE_P (y_active))
+ y_active = NEXT_INSN (y_active);
+
+ /* In order for this code to become active, either we have to be called
+ before reload, or struct_equiv_block_eq needs to add register scavenging
+ code to allocate input_reg after reload. */
+ if (info.input_reg)
+ {
+ emit_insn_before (gen_move_insn (info.input_reg, info.x_input),
+ x_active);
+ emit_insn_before (gen_move_insn (info.input_reg, info.y_input),
+ y_active);
+ }
+
+ for (i = 0; i < info.cur.local_count; i++)
+ if (info.local_rvalue[i])
+ emit_insn_before (gen_move_insn (info.x_local[i], info.y_local[i]),
+ y_active);
/* Here we know that the insns in the end of SRC1 which are common with SRC2
will be deleted.
@@ -1703,30 +1337,36 @@ try_crossjump_to_edge (int mode, edge e1
/* Avoid splitting if possible. We must always split when SRC2 has
EH predecessor edges, or we may end up with basic blocks with both
normal and EH predecessor edges. */
- if (newpos2 == BB_HEAD (src2)
+ if (info.cur.x_start == BB_HEAD (src2)
&& !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
redirect_to = src2;
else
{
- if (newpos2 == BB_HEAD (src2))
+ if (info.cur.x_start == BB_HEAD (src2))
{
/* Skip possible basic block header. */
- if (LABEL_P (newpos2))
- newpos2 = NEXT_INSN (newpos2);
- if (NOTE_P (newpos2))
- newpos2 = NEXT_INSN (newpos2);
+ if (LABEL_P (info.cur.x_start))
+ info.cur.x_start = NEXT_INSN (info.cur.x_start);
+ if (NOTE_P (info.cur.x_start))
+ info.cur.x_start = NEXT_INSN (info.cur.x_start);
}
if (dump_file)
fprintf (dump_file, "Splitting bb %i before %i insns\n",
src2->index, nmatch);
- redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
+ redirect_to = split_block (src2, PREV_INSN (info.cur.x_start))->dest;
+ COPY_REG_SET (info.y_block->il.rtl->global_live_at_end,
+ info.x_block->il.rtl->global_live_at_end);
}
if (dump_file)
- fprintf (dump_file,
- "Cross jumping from bb %i to bb %i; %i common insns\n",
- src1->index, src2->index, nmatch);
+ {
+ fprintf (dump_file, "Cross jumping from bb %i to bb %i; %i common insns",
+ src1->index, src2->index, nmatch);
+ if (info.cur.local_count)
+ fprintf (dump_file, ", %i local registers", info.cur.local_count);
+ fprintf (dump_file, "\n");
+ }
redirect_to->count += src1->count;
redirect_to->frequency += src1->frequency;
@@ -1790,14 +1430,7 @@ try_crossjump_to_edge (int mode, edge e1
/* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
- /* Skip possible basic block header. */
- if (LABEL_P (newpos1))
- newpos1 = NEXT_INSN (newpos1);
-
- if (NOTE_P (newpos1))
- newpos1 = NEXT_INSN (newpos1);
-
- redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
+ redirect_from = split_block (src1, PREV_INSN (y_active))->src;
to_remove = single_succ (redirect_from);
redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
Index: basic-block.h
===================================================================
/usr/bin/diff -p -d -F^( -u -L basic-block.h (revision 109329) -L basic-block.h (working copy) .svn/text-base/basic-block.h.svn-base basic-block.h
--- basic-block.h (revision 109329)
+++ basic-block.h (working copy)
@@ -1169,7 +1169,7 @@ struct equiv_info
extern bool insns_match_p (rtx, rtx, struct equiv_info *);
extern int struct_equiv_block_eq (int, struct equiv_info *);
-extern bool struct_equiv_init (int, struct equiv_info *);
+extern bool struct_equiv_init (int, struct equiv_info *, bool);
extern bool rtx_equiv_p (rtx *, rtx, int, struct equiv_info *);
/* In cfgrtl.c */
Index: struct-equiv.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L struct-equiv.c (revision 109329) -L struct-equiv.c (working copy) .svn/text-base/struct-equiv.c.svn-base struct-equiv.c
--- struct-equiv.c (revision 109329)
+++ struct-equiv.c (working copy)
@@ -987,38 +987,54 @@ insns_match_p (rtx i1, rtx i2, struct eq
return false;
}
-/* Set up mode and register information in INFO. Return true for success. */
-bool
-struct_equiv_init (int mode, struct equiv_info *info)
+static bool
+struct_equiv_regs_eq_p (struct equiv_info *info)
{
if ((info->x_block->flags | info->y_block->flags) & BB_DIRTY)
update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
(PROP_DEATH_NOTES
- | ((mode & CLEANUP_POST_REGSTACK)
+ | ((info->mode & CLEANUP_POST_REGSTACK)
? PROP_POST_REGSTACK : 0)));
- if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
- info->y_block->il.rtl->global_live_at_end))
- {
#ifdef STACK_REGS
- unsigned rn;
+ if (info->mode & CLEANUP_POST_REGSTACK)
+ {
+ unsigned regnum;
+ bitmap_iterator rsi;
- if (!(mode & CLEANUP_POST_REGSTACK))
- return false;
- /* After reg-stack. Remove bogus live info about stack regs. N.B.
- these regs are not necessarily all dead - we swap random bogosity
- against constant bogosity. However, clearing these bits at
- least makes the regsets comparable. */
- for (rn = FIRST_STACK_REG; rn <= LAST_STACK_REG; rn++)
+ EXECUTE_IF_AND_IN_BITMAP (info->x_block->il.rtl->global_live_at_end,
+ info->y_block->il.rtl->global_live_at_end,
+ 0, regnum, rsi)
{
- CLEAR_REGNO_REG_SET (info->x_block->il.rtl->global_live_at_end, rn);
- CLEAR_REGNO_REG_SET (info->y_block->il.rtl->global_live_at_end, rn);
+ if (regnum < FIRST_STACK_REG || regnum > LAST_STACK_REG)
+ return false;
}
- if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
- info->y_block->il.rtl->global_live_at_end))
+ return true;
+ }
#endif
+ return (REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
+ info->y_block->il.rtl->global_live_at_end));
+}
+
+/* Set up mode and register information in INFO. Return true for success.
+ Nonzero CHECK_REGS_EQ indicates that we might be called with blocks that
+ have non-matching successor sets, and thus need to check their live_at_end
+ regsets for match in the first pass. */
+bool
+struct_equiv_init (int mode, struct equiv_info *info, bool check_regs_eq)
+{
+ if ((info->x_block->flags & info->y_block->flags) & BB_DIRTY)
+ update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
+ (PROP_DEATH_NOTES
+ | ((mode & CLEANUP_POST_REGSTACK)
+ ? PROP_POST_REGSTACK : 0)));
+ info->mode = mode;
+ if (check_regs_eq && (mode & STRUCT_EQUIV_START))
+ {
+ if (!struct_equiv_regs_eq_p (info))
return false;
}
- info->mode = mode;
+ else if (mode & STRUCT_EQUIV_FINAL)
+ gcc_assert (struct_equiv_regs_eq_p (info));
if (mode & STRUCT_EQUIV_START)
{
info->x_input = info->y_input = info->input_reg = NULL_RTX;
@@ -1036,7 +1052,10 @@ struct_equiv_init (int mode, struct equi
info->common_live = ALLOC_REG_SET (®_obstack);
info->x_local_live = ALLOC_REG_SET (®_obstack);
info->y_local_live = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (info->common_live, info->x_block->il.rtl->global_live_at_end);
+ COPY_REG_SET (info->common_live,
+ ((info->x_block->flags & BB_DIRTY
+ ? info->y_block : info->x_block)
+ ->il.rtl->global_live_at_end));
struct_equiv_make_checkpoint (&info->best_match, info);
return true;
}
@@ -1100,8 +1119,7 @@ struct_equiv_block_eq (int mode, struct
x_stop = info->cur.x_start;
y_stop = info->cur.y_start;
}
- if (!struct_equiv_init (mode, info))
- gcc_unreachable ();
+ struct_equiv_init (mode, info, false);
/* Skip simple jumps at the end of the blocks. Complex jumps still
need to be compared for equivalence, which we'll do below. */
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: Huge compile time regressions
2006-01-05 22:10 ` Joern RENNECKE
@ 2006-01-05 22:20 ` Joern RENNECKE
2006-01-13 15:15 ` RFA: re-instate struct_equiv code (Was: Re: Huge compile time regressions) Joern RENNECKE
0 siblings, 1 reply; 16+ messages in thread
From: Joern RENNECKE @ 2006-01-05 22:20 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: Daniel Berlin, Steven Bosscher, gcc
[-- Attachment #1: Type: text/plain, Size: 647 bytes --]
Joern Rennecke wrote:
> Joern Rennecke wrote:
>
>> I've found that the most striking compilation time increase was for
>> flex / parse.c, which is a bison parser.
>> -Os compilation for i686-pc-linux-gnu X sh-elf --disable-checking
>> went from 0.95 to 4.5 seconds.
>>
> Optimizing the REG_SET_EQ invocations gave a moderate win, down to 3.5
> seconds.
Doing only one update_life_info_in_dirty_blocks before the crossjumping
makes the compilation time go right back to 0.95 seconds. If that
works, is another question... if there are any transformations that
invalidate global_live_at_end, we'll have to make them update these regsets.
[-- Attachment #2: cmove_diff-20060105-upd-opt --]
[-- Type: text/plain, Size: 30994 bytes --]
2006-01-05 J"orn Rennecke <joern.rennecke@st.com>
* cfgcleanup.c: Reinstate patches for PR 20070
* struct-equiv.c (struct_equiv_regs_eq_p): New function.
(struct_equiv_init): Only call update_life_info_in_dirty_blocks
in order to initialize regsets if both blocks are dirty.
Make do sanity check of registers bening equal for STRUCT_EQUIV_FINAL.
Add new parameter check_regs_eq. Changed all callers.
* basic-block.h (struct_equiv_init): Update prototype.
* basic_block.h (STRUCT_EQUIV_SUSPEND_UPDATE): Define.
* struct-equiv.c (struct_equiv_regs_eq_p): Don't call
update_life_info_in_dirty_blocks if STRUCT_EQUIV_SUSPEND_UPDATE
is set in info->mode.
(struct_equiv_init): Likewise. Also, add sanity check of
global_live_at_end in that case.
* cfgcleanup.c (try_optimize_cfg): Call
update_life_info_in_dirty_blocks before start of loop. Set
STRUCT_EQUIV_SUSPEND_UPDATE in mode argument passed to
try_crossjump_bb.
Index: cfgcleanup.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L cfgcleanup.c (revision 109329) -L cfgcleanup.c (working copy) .svn/text-base/cfgcleanup.c.svn-base cfgcleanup.c
--- cfgcleanup.c (revision 109329)
+++ cfgcleanup.c (working copy)
@@ -60,9 +60,7 @@ Software Foundation, 51 Franklin Street,
static bool first_pass;
static bool try_crossjump_to_edge (int, edge, edge);
static bool try_crossjump_bb (int, basic_block);
-static bool outgoing_edges_match (int, basic_block, basic_block);
-static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
-static bool old_insns_match_p (int, rtx, rtx);
+static bool outgoing_edges_match (int *, struct equiv_info *);
static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
@@ -74,7 +72,6 @@ static bool mark_effect (rtx, bitmap);
static void notice_new_block (basic_block);
static void update_forwarder_flag (basic_block);
static int mentions_nonequal_regs (rtx *, void *);
-static void merge_memattrs (rtx, rtx);
\f
/* Set flags for newly created block. */
@@ -881,319 +878,6 @@ merge_blocks_move (edge e, basic_block b
return NULL;
}
\f
-
-/* Removes the memory attributes of MEM expression
- if they are not equal. */
-
-void
-merge_memattrs (rtx x, rtx y)
-{
- int i;
- int j;
- enum rtx_code code;
- const char *fmt;
-
- if (x == y)
- return;
- if (x == 0 || y == 0)
- return;
-
- code = GET_CODE (x);
-
- if (code != GET_CODE (y))
- return;
-
- if (GET_MODE (x) != GET_MODE (y))
- return;
-
- if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
- {
- if (! MEM_ATTRS (x))
- MEM_ATTRS (y) = 0;
- else if (! MEM_ATTRS (y))
- MEM_ATTRS (x) = 0;
- else
- {
- rtx mem_size;
-
- if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
- {
- set_mem_alias_set (x, 0);
- set_mem_alias_set (y, 0);
- }
-
- if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
- {
- set_mem_expr (x, 0);
- set_mem_expr (y, 0);
- set_mem_offset (x, 0);
- set_mem_offset (y, 0);
- }
- else if (MEM_OFFSET (x) != MEM_OFFSET (y))
- {
- set_mem_offset (x, 0);
- set_mem_offset (y, 0);
- }
-
- if (!MEM_SIZE (x))
- mem_size = NULL_RTX;
- else if (!MEM_SIZE (y))
- mem_size = NULL_RTX;
- else
- mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
- INTVAL (MEM_SIZE (y))));
- set_mem_size (x, mem_size);
- set_mem_size (y, mem_size);
-
- set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
- set_mem_align (y, MEM_ALIGN (x));
- }
- }
-
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- switch (fmt[i])
- {
- case 'E':
- /* Two vectors must have the same length. */
- if (XVECLEN (x, i) != XVECLEN (y, i))
- return;
-
- for (j = 0; j < XVECLEN (x, i); j++)
- merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
-
- break;
-
- case 'e':
- merge_memattrs (XEXP (x, i), XEXP (y, i));
- }
- }
- return;
-}
-
-
-/* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
-
-static bool
-old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
-{
- rtx p1, p2;
-
- /* Verify that I1 and I2 are equivalent. */
- if (GET_CODE (i1) != GET_CODE (i2))
- return false;
-
- p1 = PATTERN (i1);
- p2 = PATTERN (i2);
-
- if (GET_CODE (p1) != GET_CODE (p2))
- return false;
-
- /* If this is a CALL_INSN, compare register usage information.
- If we don't check this on stack register machines, the two
- CALL_INSNs might be merged leaving reg-stack.c with mismatching
- numbers of stack registers in the same basic block.
- If we don't check this on machines with delay slots, a delay slot may
- be filled that clobbers a parameter expected by the subroutine.
-
- ??? We take the simple route for now and assume that if they're
- equal, they were constructed identically. */
-
- if (CALL_P (i1)
- && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
- CALL_INSN_FUNCTION_USAGE (i2))
- || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
- return false;
-
-#ifdef STACK_REGS
- /* If cross_jump_death_matters is not 0, the insn's mode
- indicates whether or not the insn contains any stack-like
- regs. */
-
- if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
- {
- /* If register stack conversion has already been done, then
- death notes must also be compared before it is certain that
- the two instruction streams match. */
-
- rtx note;
- HARD_REG_SET i1_regset, i2_regset;
-
- CLEAR_HARD_REG_SET (i1_regset);
- CLEAR_HARD_REG_SET (i2_regset);
-
- for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
- SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
-
- for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
- SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
-
- GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
-
- return false;
-
- done:
- ;
- }
-#endif
-
- if (reload_completed
- ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
- return true;
-
- /* Do not do EQUIV substitution after reload. First, we're undoing the
- work of reload_cse. Second, we may be undoing the work of the post-
- reload splitting pass. */
- /* ??? Possibly add a new phase switch variable that can be used by
- targets to disallow the troublesome insns after splitting. */
- if (!reload_completed)
- {
- /* The following code helps take care of G++ cleanups. */
- rtx equiv1 = find_reg_equal_equiv_note (i1);
- rtx equiv2 = find_reg_equal_equiv_note (i2);
-
- if (equiv1 && equiv2
- /* If the equivalences are not to a constant, they may
- reference pseudos that no longer exist, so we can't
- use them. */
- && (! reload_completed
- || (CONSTANT_P (XEXP (equiv1, 0))
- && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
- {
- rtx s1 = single_set (i1);
- rtx s2 = single_set (i2);
- if (s1 != 0 && s2 != 0
- && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
- {
- validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
- validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
- if (! rtx_renumbered_equal_p (p1, p2))
- cancel_changes (0);
- else if (apply_change_group ())
- return true;
- }
- }
- }
-
- return false;
-}
-\f
-/* Look through the insns at the end of BB1 and BB2 and find the longest
- sequence that are equivalent. Store the first insns for that sequence
- in *F1 and *F2 and return the sequence length.
-
- To simplify callers of this function, if the blocks match exactly,
- store the head of the blocks in *F1 and *F2. */
-
-static int
-flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
- basic_block bb2, rtx *f1, rtx *f2)
-{
- rtx i1, i2, last1, last2, afterlast1, afterlast2;
- int ninsns = 0;
-
- /* Skip simple jumps at the end of the blocks. Complex jumps still
- need to be compared for equivalence, which we'll do below. */
-
- i1 = BB_END (bb1);
- last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
- if (onlyjump_p (i1)
- || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
- {
- last1 = i1;
- i1 = PREV_INSN (i1);
- }
-
- i2 = BB_END (bb2);
- if (onlyjump_p (i2)
- || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
- {
- last2 = i2;
- /* Count everything except for unconditional jump as insn. */
- if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
- ninsns++;
- i2 = PREV_INSN (i2);
- }
-
- while (true)
- {
- /* Ignore notes. */
- while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
- i1 = PREV_INSN (i1);
-
- while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
- i2 = PREV_INSN (i2);
-
- if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
- break;
-
- if (!old_insns_match_p (mode, i1, i2))
- break;
-
- merge_memattrs (i1, i2);
-
- /* Don't begin a cross-jump with a NOTE insn. */
- if (INSN_P (i1))
- {
- /* If the merged insns have different REG_EQUAL notes, then
- remove them. */
- rtx equiv1 = find_reg_equal_equiv_note (i1);
- rtx equiv2 = find_reg_equal_equiv_note (i2);
-
- if (equiv1 && !equiv2)
- remove_note (i1, equiv1);
- else if (!equiv1 && equiv2)
- remove_note (i2, equiv2);
- else if (equiv1 && equiv2
- && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
- {
- remove_note (i1, equiv1);
- remove_note (i2, equiv2);
- }
-
- afterlast1 = last1, afterlast2 = last2;
- last1 = i1, last2 = i2;
- ninsns++;
- }
-
- i1 = PREV_INSN (i1);
- i2 = PREV_INSN (i2);
- }
-
-#ifdef HAVE_cc0
- /* Don't allow the insn after a compare to be shared by
- cross-jumping unless the compare is also shared. */
- if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
- last1 = afterlast1, last2 = afterlast2, ninsns--;
-#endif
-
- /* Include preceding notes and labels in the cross-jump. One,
- this may bring us to the head of the blocks as requested above.
- Two, it keeps line number notes as matched as may be. */
- if (ninsns)
- {
- while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
- last1 = PREV_INSN (last1);
-
- if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
- last1 = PREV_INSN (last1);
-
- while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
- last2 = PREV_INSN (last2);
-
- if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
- last2 = PREV_INSN (last2);
-
- *f1 = last1;
- *f2 = last2;
- }
-
- return ninsns;
-}
-
/* Return true iff the condbranches at the end of BB1 and BB2 match. */
bool
condjump_equiv_p (struct equiv_info *info, bool call_init)
@@ -1252,8 +936,8 @@ condjump_equiv_p (struct equiv_info *inf
if (code2 == UNKNOWN)
return false;
- if (call_init && !struct_equiv_init (STRUCT_EQUIV_START | info->mode, info))
- gcc_unreachable ();
+ if (call_init)
+ struct_equiv_init (STRUCT_EQUIV_START | info->mode, info, false);
/* Make the sources of the pc sets unreadable so that when we call
insns_match_p it won't process them.
The death_notes_match_p from insns_match_p won't see the local registers
@@ -1322,15 +1006,20 @@ condjump_equiv_p (struct equiv_info *inf
return match;
}
-/* Return true iff outgoing edges of BB1 and BB2 match, together with
- the branch instruction. This means that if we commonize the control
- flow before end of the basic block, the semantic remains unchanged.
+/* Return true iff outgoing edges of INFO->y_block and INFO->x_block match,
+ together with the branch instruction. This means that if we commonize the
+ control flow before end of the basic block, the semantic remains unchanged.
+ If we need to compare jumps, we set STRUCT_EQUIV_MATCH_JUMPS in *MODE,
+ and pass *MODE to struct_equiv_init or assign it to INFO->mode, as
+ appropriate.
We may assume that there exists one edge with a common destination. */
static bool
-outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
+outgoing_edges_match (int *mode, struct equiv_info *info)
{
+ basic_block bb1 = info->y_block;
+ basic_block bb2 = info->x_block;
int nehedges1 = 0, nehedges2 = 0;
edge fallthru1 = 0, fallthru2 = 0;
edge e1, e2;
@@ -1346,114 +1035,19 @@ outgoing_edges_match (int mode, basic_bl
& (EDGE_COMPLEX | EDGE_FAKE)) == 0
&& (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
+ *mode |= STRUCT_EQUIV_MATCH_JUMPS;
/* Match conditional jumps - this may get tricky when fallthru and branch
edges are crossed. */
if (EDGE_COUNT (bb1->succs) == 2
&& any_condjump_p (BB_END (bb1))
&& onlyjump_p (BB_END (bb1)))
{
- edge b1, f1, b2, f2;
- bool reverse, match;
- rtx set1, set2, cond1, cond2;
- enum rtx_code code1, code2;
-
if (EDGE_COUNT (bb2->succs) != 2
|| !any_condjump_p (BB_END (bb2))
|| !onlyjump_p (BB_END (bb2)))
return false;
-
- b1 = BRANCH_EDGE (bb1);
- b2 = BRANCH_EDGE (bb2);
- f1 = FALLTHRU_EDGE (bb1);
- f2 = FALLTHRU_EDGE (bb2);
-
- /* Get around possible forwarders on fallthru edges. Other cases
- should be optimized out already. */
- if (FORWARDER_BLOCK_P (f1->dest))
- f1 = single_succ_edge (f1->dest);
-
- if (FORWARDER_BLOCK_P (f2->dest))
- f2 = single_succ_edge (f2->dest);
-
- /* To simplify use of this function, return false if there are
- unneeded forwarder blocks. These will get eliminated later
- during cleanup_cfg. */
- if (FORWARDER_BLOCK_P (f1->dest)
- || FORWARDER_BLOCK_P (f2->dest)
- || FORWARDER_BLOCK_P (b1->dest)
- || FORWARDER_BLOCK_P (b2->dest))
- return false;
-
- if (f1->dest == f2->dest && b1->dest == b2->dest)
- reverse = false;
- else if (f1->dest == b2->dest && b1->dest == f2->dest)
- reverse = true;
- else
- return false;
-
- set1 = pc_set (BB_END (bb1));
- set2 = pc_set (BB_END (bb2));
- if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
- != (XEXP (SET_SRC (set2), 1) == pc_rtx))
- reverse = !reverse;
-
- cond1 = XEXP (SET_SRC (set1), 0);
- cond2 = XEXP (SET_SRC (set2), 0);
- code1 = GET_CODE (cond1);
- if (reverse)
- code2 = reversed_comparison_code (cond2, BB_END (bb2));
- else
- code2 = GET_CODE (cond2);
-
- if (code2 == UNKNOWN)
- return false;
-
- /* Verify codes and operands match. */
- match = ((code1 == code2
- && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
- && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
- || (code1 == swap_condition (code2)
- && rtx_renumbered_equal_p (XEXP (cond1, 1),
- XEXP (cond2, 0))
- && rtx_renumbered_equal_p (XEXP (cond1, 0),
- XEXP (cond2, 1))));
-
- /* If we return true, we will join the blocks. Which means that
- we will only have one branch prediction bit to work with. Thus
- we require the existing branches to have probabilities that are
- roughly similar. */
- if (match
- && !optimize_size
- && maybe_hot_bb_p (bb1)
- && maybe_hot_bb_p (bb2))
- {
- int prob2;
-
- if (b1->dest == b2->dest)
- prob2 = b2->probability;
- else
- /* Do not use f2 probability as f2 may be forwarded. */
- prob2 = REG_BR_PROB_BASE - b2->probability;
-
- /* Fail if the difference in probabilities is greater than 50%.
- This rules out two well-predicted branches with opposite
- outcomes. */
- if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
- {
- if (dump_file)
- fprintf (dump_file,
- "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
- bb1->index, bb2->index, b1->probability, prob2);
-
- return false;
- }
- }
-
- if (dump_file && match)
- fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
- bb1->index, bb2->index);
-
- return match;
+ info->mode = *mode;
+ return condjump_equiv_p (info, true);
}
/* Generic case - we are seeing a computed jump, table jump or trapping
@@ -1501,31 +1095,22 @@ outgoing_edges_match (int mode, basic_bl
identical = false;
}
- if (identical)
+ if (identical
+ && struct_equiv_init (STRUCT_EQUIV_START | *mode, info, true))
{
- replace_label_data rr;
bool match;
- /* Temporarily replace references to LABEL1 with LABEL2
+ /* Indicate that LABEL1 is to be replaced with LABEL2
in BB1->END so that we could compare the instructions. */
- rr.r1 = label1;
- rr.r2 = label2;
- rr.update_label_nuses = false;
- for_each_rtx (&BB_END (bb1), replace_label, &rr);
+ info->y_label = label1;
+ info->x_label = label2;
- match = old_insns_match_p (mode, BB_END (bb1), BB_END (bb2));
+ match = insns_match_p (BB_END (bb1), BB_END (bb2), info);
if (dump_file && match)
fprintf (dump_file,
"Tablejumps in bb %i and %i match.\n",
bb1->index, bb2->index);
- /* Set the original label in BB1->END because when deleting
- a block whose end is a tablejump, the tablejump referenced
- from the instruction is deleted too. */
- rr.r1 = label2;
- rr.r2 = label1;
- for_each_rtx (&BB_END (bb1), replace_label, &rr);
-
return match;
}
}
@@ -1535,7 +1120,10 @@ outgoing_edges_match (int mode, basic_bl
/* First ensure that the instructions match. There may be many outgoing
edges so this test is generally cheaper. */
- if (!old_insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
+ /* FIXME: the regset compare might be costly. We should try to get a cheap
+ and reasonably effective test first. */
+ if (!struct_equiv_init (STRUCT_EQUIV_START | *mode, info, true)
+ || !insns_match_p (BB_END (bb1), BB_END (bb2), info))
return false;
/* Search the outgoing edges, ensure that the counts do match, find possible
@@ -1601,22 +1189,21 @@ outgoing_edges_match (int mode, basic_bl
static bool
try_crossjump_to_edge (int mode, edge e1, edge e2)
{
- int nmatch;
+ int nmatch, i;
basic_block src1 = e1->src, src2 = e2->src;
basic_block redirect_to, redirect_from, to_remove;
- rtx newpos1, newpos2;
edge s;
edge_iterator ei;
-
- newpos1 = newpos2 = NULL_RTX;
+ struct equiv_info info;
+ rtx x_active, y_active;
/* If we have partitioned hot/cold basic blocks, it is a bad idea
- to try this optimization.
+ to try this optimization.
Basic block partitioning may result in some jumps that appear to
- be optimizable (or blocks that appear to be mergeable), but which really
- must be left untouched (they are required to make it safely across
- partition boundaries). See the comments at the top of
+ be optimizable (or blocks that appear to be mergeable), but which really
+ must be left untouched (they are required to make it safely across
+ partition boundaries). See the comments at the top of
bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
if (flag_reorder_blocks_and_partition && no_new_pseudos)
@@ -1655,19 +1242,66 @@ try_crossjump_to_edge (int mode, edge e1
return false;
/* Look for the common insn sequence, part the first ... */
- if (!outgoing_edges_match (mode, src1, src2))
+ info.x_block = src2;
+ info.y_block = src1;
+ if (!outgoing_edges_match (&mode, &info))
return false;
/* ... and part the second. */
- nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
+ info.input_cost = optimize_size ? COSTS_N_INSNS (1) : -1;
+ nmatch = struct_equiv_block_eq (STRUCT_EQUIV_START | mode, &info);
/* Don't proceed with the crossjump unless we found a sufficient number
of matching instructions or the 'from' block was totally matched
(such that its predecessors will hopefully be redirected and the
block removed). */
- if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
- && (newpos1 != BB_HEAD (src1)))
+ if (!nmatch)
return false;
+ if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+ && (info.cur.y_start != BB_HEAD (src1)))
+ return false;
+ while (info.need_rerun)
+ {
+ nmatch = struct_equiv_block_eq (STRUCT_EQUIV_RERUN | mode, &info);
+ if (!nmatch)
+ return false;
+ if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+ && (info.cur.y_start != BB_HEAD (src1)))
+ return false;
+ }
+ nmatch = struct_equiv_block_eq (STRUCT_EQUIV_FINAL | mode, &info);
+ if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+ && (info.cur.y_start != BB_HEAD (src1)))
+ return false;
+
+ /* Skip possible basic block header. */
+ x_active = info.cur.x_start;
+ if (LABEL_P (x_active))
+ x_active = NEXT_INSN (x_active);
+ if (NOTE_P (x_active))
+ x_active = NEXT_INSN (x_active);
+
+ y_active = info.cur.y_start;
+ if (LABEL_P (y_active))
+ y_active = NEXT_INSN (y_active);
+ if (NOTE_P (y_active))
+ y_active = NEXT_INSN (y_active);
+
+ /* In order for this code to become active, either we have to be called
+ before reload, or struct_equiv_block_eq needs to add register scavenging
+ code to allocate input_reg after reload. */
+ if (info.input_reg)
+ {
+ emit_insn_before (gen_move_insn (info.input_reg, info.x_input),
+ x_active);
+ emit_insn_before (gen_move_insn (info.input_reg, info.y_input),
+ y_active);
+ }
+
+ for (i = 0; i < info.cur.local_count; i++)
+ if (info.local_rvalue[i])
+ emit_insn_before (gen_move_insn (info.x_local[i], info.y_local[i]),
+ y_active);
/* Here we know that the insns in the end of SRC1 which are common with SRC2
will be deleted.
@@ -1703,30 +1337,36 @@ try_crossjump_to_edge (int mode, edge e1
/* Avoid splitting if possible. We must always split when SRC2 has
EH predecessor edges, or we may end up with basic blocks with both
normal and EH predecessor edges. */
- if (newpos2 == BB_HEAD (src2)
+ if (info.cur.x_start == BB_HEAD (src2)
&& !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
redirect_to = src2;
else
{
- if (newpos2 == BB_HEAD (src2))
+ if (info.cur.x_start == BB_HEAD (src2))
{
/* Skip possible basic block header. */
- if (LABEL_P (newpos2))
- newpos2 = NEXT_INSN (newpos2);
- if (NOTE_P (newpos2))
- newpos2 = NEXT_INSN (newpos2);
+ if (LABEL_P (info.cur.x_start))
+ info.cur.x_start = NEXT_INSN (info.cur.x_start);
+ if (NOTE_P (info.cur.x_start))
+ info.cur.x_start = NEXT_INSN (info.cur.x_start);
}
if (dump_file)
fprintf (dump_file, "Splitting bb %i before %i insns\n",
src2->index, nmatch);
- redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
+ redirect_to = split_block (src2, PREV_INSN (info.cur.x_start))->dest;
+ COPY_REG_SET (info.y_block->il.rtl->global_live_at_end,
+ info.x_block->il.rtl->global_live_at_end);
}
if (dump_file)
- fprintf (dump_file,
- "Cross jumping from bb %i to bb %i; %i common insns\n",
- src1->index, src2->index, nmatch);
+ {
+ fprintf (dump_file, "Cross jumping from bb %i to bb %i; %i common insns",
+ src1->index, src2->index, nmatch);
+ if (info.cur.local_count)
+ fprintf (dump_file, ", %i local registers", info.cur.local_count);
+ fprintf (dump_file, "\n");
+ }
redirect_to->count += src1->count;
redirect_to->frequency += src1->frequency;
@@ -1790,14 +1430,7 @@ try_crossjump_to_edge (int mode, edge e1
/* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
- /* Skip possible basic block header. */
- if (LABEL_P (newpos1))
- newpos1 = NEXT_INSN (newpos1);
-
- if (NOTE_P (newpos1))
- newpos1 = NEXT_INSN (newpos1);
-
- redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
+ redirect_from = split_block (src1, PREV_INSN (y_active))->src;
to_remove = single_succ (redirect_from);
redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
@@ -1969,6 +1602,11 @@ try_optimize_cfg (int mode)
if (! targetm.cannot_modify_jumps_p ())
{
+ if (mode & CLEANUP_CROSSJUMP)
+ update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
+ (PROP_DEATH_NOTES
+ | ((mode & CLEANUP_POST_REGSTACK)
+ ? PROP_POST_REGSTACK : 0)));
first_pass = true;
/* Attempt to merge blocks as made possible by edge removal. If
a block has only one successor, and the successor has only
@@ -2124,7 +1762,7 @@ try_optimize_cfg (int mode)
/* Look for shared code between blocks. */
if ((mode & CLEANUP_CROSSJUMP)
- && try_crossjump_bb (mode, b))
+ && try_crossjump_bb (mode | STRUCT_EQUIV_SUSPEND_UPDATES, b))
changed_here = true;
/* Don't get confused by the index shift caused by
@@ -2136,7 +1774,8 @@ try_optimize_cfg (int mode)
}
if ((mode & CLEANUP_CROSSJUMP)
- && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
+ && try_crossjump_bb (mode | STRUCT_EQUIV_SUSPEND_UPDATES,
+ EXIT_BLOCK_PTR))
changed = true;
#ifdef ENABLE_CHECKING
Index: basic-block.h
===================================================================
/usr/bin/diff -p -d -F^( -u -L basic-block.h (revision 109329) -L basic-block.h (working copy) .svn/text-base/basic-block.h.svn-base basic-block.h
--- basic-block.h (revision 109329)
+++ basic-block.h (working copy)
@@ -850,6 +850,8 @@ enum update_life_extent
to match only full blocks */
#define STRUCT_EQUIV_MATCH_JUMPS 8192 /* Also include the jumps at the end of the block in the comparison. */
+#define STRUCT_EQUIV_SUSPEND_UPDATES 16384 /* Assume global_live_at_end is up-to-date even if the block isn't. */
+
extern void life_analysis (FILE *, int);
extern int update_life_info (sbitmap, enum update_life_extent, int);
extern int update_life_info_in_dirty_blocks (enum update_life_extent, int);
@@ -1169,7 +1171,7 @@ struct equiv_info
extern bool insns_match_p (rtx, rtx, struct equiv_info *);
extern int struct_equiv_block_eq (int, struct equiv_info *);
-extern bool struct_equiv_init (int, struct equiv_info *);
+extern bool struct_equiv_init (int, struct equiv_info *, bool);
extern bool rtx_equiv_p (rtx *, rtx, int, struct equiv_info *);
/* In cfgrtl.c */
Index: struct-equiv.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L struct-equiv.c (revision 109329) -L struct-equiv.c (working copy) .svn/text-base/struct-equiv.c.svn-base struct-equiv.c
--- struct-equiv.c (revision 109329)
+++ struct-equiv.c (working copy)
@@ -987,38 +987,56 @@ insns_match_p (rtx i1, rtx i2, struct eq
return false;
}
-/* Set up mode and register information in INFO. Return true for success. */
-bool
-struct_equiv_init (int mode, struct equiv_info *info)
+static bool
+struct_equiv_regs_eq_p (struct equiv_info *info)
{
- if ((info->x_block->flags | info->y_block->flags) & BB_DIRTY)
+ if (!(info->mode & STRUCT_EQUIV_SUSPEND_UPDATES)
+ && ((info->x_block->flags | info->y_block->flags) & BB_DIRTY))
update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
(PROP_DEATH_NOTES
- | ((mode & CLEANUP_POST_REGSTACK)
+ | ((info->mode & CLEANUP_POST_REGSTACK)
? PROP_POST_REGSTACK : 0)));
- if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
- info->y_block->il.rtl->global_live_at_end))
- {
#ifdef STACK_REGS
- unsigned rn;
+ if (info->mode & CLEANUP_POST_REGSTACK)
+ {
+ unsigned regnum;
+ bitmap_iterator rsi;
- if (!(mode & CLEANUP_POST_REGSTACK))
- return false;
- /* After reg-stack. Remove bogus live info about stack regs. N.B.
- these regs are not necessarily all dead - we swap random bogosity
- against constant bogosity. However, clearing these bits at
- least makes the regsets comparable. */
- for (rn = FIRST_STACK_REG; rn <= LAST_STACK_REG; rn++)
+ EXECUTE_IF_AND_IN_BITMAP (info->x_block->il.rtl->global_live_at_end,
+ info->y_block->il.rtl->global_live_at_end,
+ 0, regnum, rsi)
{
- CLEAR_REGNO_REG_SET (info->x_block->il.rtl->global_live_at_end, rn);
- CLEAR_REGNO_REG_SET (info->y_block->il.rtl->global_live_at_end, rn);
+ if (regnum < FIRST_STACK_REG || regnum > LAST_STACK_REG)
+ return false;
}
- if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
- info->y_block->il.rtl->global_live_at_end))
+ return true;
+ }
#endif
+ return (REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
+ info->y_block->il.rtl->global_live_at_end));
+}
+
+/* Set up mode and register information in INFO. Return true for success.
+ Nonzero CHECK_REGS_EQ indicates that we might be called with blocks that
+ have non-matching successor sets, and thus need to check their live_at_end
+ regsets for match in the first pass. */
+bool
+struct_equiv_init (int mode, struct equiv_info *info, bool check_regs_eq)
+{
+ if (!(info->mode & STRUCT_EQUIV_SUSPEND_UPDATES)
+ && ((info->x_block->flags & info->y_block->flags) & BB_DIRTY))
+ update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
+ (PROP_DEATH_NOTES
+ | ((mode & CLEANUP_POST_REGSTACK)
+ ? PROP_POST_REGSTACK : 0)));
+ info->mode = mode;
+ if (check_regs_eq && (mode & STRUCT_EQUIV_START))
+ {
+ if (!struct_equiv_regs_eq_p (info))
return false;
}
- info->mode = mode;
+ else if (mode & (STRUCT_EQUIV_FINAL | STRUCT_EQUIV_SUSPEND_UPDATES))
+ gcc_assert (struct_equiv_regs_eq_p (info));
if (mode & STRUCT_EQUIV_START)
{
info->x_input = info->y_input = info->input_reg = NULL_RTX;
@@ -1036,7 +1054,10 @@ struct_equiv_init (int mode, struct equi
info->common_live = ALLOC_REG_SET (®_obstack);
info->x_local_live = ALLOC_REG_SET (®_obstack);
info->y_local_live = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (info->common_live, info->x_block->il.rtl->global_live_at_end);
+ COPY_REG_SET (info->common_live,
+ ((info->x_block->flags & BB_DIRTY
+ ? info->y_block : info->x_block)
+ ->il.rtl->global_live_at_end));
struct_equiv_make_checkpoint (&info->best_match, info);
return true;
}
@@ -1100,8 +1121,7 @@ struct_equiv_block_eq (int mode, struct
x_stop = info->cur.x_start;
y_stop = info->cur.y_start;
}
- if (!struct_equiv_init (mode, info))
- gcc_unreachable ();
+ struct_equiv_init (mode, info, false);
/* Skip simple jumps at the end of the blocks. Complex jumps still
need to be compared for equivalence, which we'll do below. */
^ permalink raw reply [flat|nested] 16+ messages in thread
* RFA: re-instate struct_equiv code (Was: Re: Huge compile time regressions)
2006-01-05 22:20 ` Joern RENNECKE
@ 2006-01-13 15:15 ` Joern RENNECKE
2006-01-13 15:30 ` How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code) Joern RENNECKE
0 siblings, 1 reply; 16+ messages in thread
From: Joern RENNECKE @ 2006-01-13 15:15 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: Daniel Berlin, Steven Bosscher, gcc
[-- Attachment #1: Type: text/plain, Size: 1260 bytes --]
Joern Rennecke wrote:
>
> Doing only one update_life_info_in_dirty_blocks before the
> crossjumping makes the compilation time go right back to 0.95
> seconds. If that works, is another question... if there are any
> transformations that invalidate global_live_at_end, we'll have to make
> them update these regsets.
:ADDPATCH rtl-optimization:
In the previously posted patch, I used EXECUTE_IF_AND_IN_BITMAP, when I
really meant EXECUTE_IF_XOR_IN_BITMAP - except that that doesn't exist.
Replaced with bitmap_xor and EXECUTE_IF_SET_IN_BITMAP.
Testing also found one place where register live information
inconsistency came from: when cross-jumping succeeds, the
global_live_at_end set of the block that is made to jump into
the other block needs adjusting. There is a copy_reg_set which could
have done it, except it is done before the blocks are split, and the
blocks still contain the old instructions
with the different local registers. Hence split_block calculates an
incorrect new global_live_at_end for redirect_from.
Fixed by copying redirect_to->global_live_at_start into
redirect_from->global_live_at_end after the splits.
Moreover, I've found that update_life_info_in_dirty_blocks must not be
called while fake edges exist.
[-- Attachment #2: cmove_diff-20060112-upd-opt --]
[-- Type: text/plain, Size: 32976 bytes --]
regression tested on i686-pc-linux-gnu native, X sh-elf and X sh64-elf.
2006-01-12 J"orn Rennecke <joern.rennecke@st.com>
* cfgcleanup.c: Reinstate patches for PR 20070
* struct-equiv.c (struct_equiv_regs_eq_p): New function.
(struct_equiv_init): Only call update_life_info_in_dirty_blocks
in order to initialize regsets if both blocks are dirty.
Make do sanity check of registers bening equal for STRUCT_EQUIV_FINAL.
Add new parameter check_regs_eq. Changed all callers.
* basic-block.h (struct_equiv_init): Update prototype.
* basic_block.h (STRUCT_EQUIV_SUSPEND_UPDATE): Define.
* struct-equiv.c (struct_equiv_regs_eq_p): Don't call
update_life_info_in_dirty_blocks if STRUCT_EQUIV_SUSPEND_UPDATE
is set in info->mode.
(struct_equiv_init): Likewise. Also, add sanity check of
global_live_at_end in that case.
* cfgcleanup.c (try_optimize_cfg): Call
update_life_info_in_dirty_blocks before start of loop. Set
STRUCT_EQUIV_SUSPEND_UPDATE in mode argument passed to
try_crossjump_bb.
(try_crossjump_to_edge): Set global_live_at_end of redirect_from
from global_live_at_start of redirect_to.
(outgoing_edges_match): Check number of edges before comparing
patterns.
Index: cfgcleanup.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L cfgcleanup.c (revision 109499) -L cfgcleanup.c (working copy) .svn/text-base/cfgcleanup.c.svn-base cfgcleanup.c
--- cfgcleanup.c (revision 109499)
+++ cfgcleanup.c (working copy)
@@ -60,9 +60,7 @@ Software Foundation, 51 Franklin Street,
static bool first_pass;
static bool try_crossjump_to_edge (int, edge, edge);
static bool try_crossjump_bb (int, basic_block);
-static bool outgoing_edges_match (int, basic_block, basic_block);
-static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
-static bool old_insns_match_p (int, rtx, rtx);
+static bool outgoing_edges_match (int *, struct equiv_info *);
static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
@@ -74,7 +72,6 @@ static bool mark_effect (rtx, bitmap);
static void notice_new_block (basic_block);
static void update_forwarder_flag (basic_block);
static int mentions_nonequal_regs (rtx *, void *);
-static void merge_memattrs (rtx, rtx);
\f
/* Set flags for newly created block. */
@@ -881,319 +878,6 @@ merge_blocks_move (edge e, basic_block b
return NULL;
}
\f
-
-/* Removes the memory attributes of MEM expression
- if they are not equal. */
-
-void
-merge_memattrs (rtx x, rtx y)
-{
- int i;
- int j;
- enum rtx_code code;
- const char *fmt;
-
- if (x == y)
- return;
- if (x == 0 || y == 0)
- return;
-
- code = GET_CODE (x);
-
- if (code != GET_CODE (y))
- return;
-
- if (GET_MODE (x) != GET_MODE (y))
- return;
-
- if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
- {
- if (! MEM_ATTRS (x))
- MEM_ATTRS (y) = 0;
- else if (! MEM_ATTRS (y))
- MEM_ATTRS (x) = 0;
- else
- {
- rtx mem_size;
-
- if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
- {
- set_mem_alias_set (x, 0);
- set_mem_alias_set (y, 0);
- }
-
- if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
- {
- set_mem_expr (x, 0);
- set_mem_expr (y, 0);
- set_mem_offset (x, 0);
- set_mem_offset (y, 0);
- }
- else if (MEM_OFFSET (x) != MEM_OFFSET (y))
- {
- set_mem_offset (x, 0);
- set_mem_offset (y, 0);
- }
-
- if (!MEM_SIZE (x))
- mem_size = NULL_RTX;
- else if (!MEM_SIZE (y))
- mem_size = NULL_RTX;
- else
- mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
- INTVAL (MEM_SIZE (y))));
- set_mem_size (x, mem_size);
- set_mem_size (y, mem_size);
-
- set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
- set_mem_align (y, MEM_ALIGN (x));
- }
- }
-
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- switch (fmt[i])
- {
- case 'E':
- /* Two vectors must have the same length. */
- if (XVECLEN (x, i) != XVECLEN (y, i))
- return;
-
- for (j = 0; j < XVECLEN (x, i); j++)
- merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
-
- break;
-
- case 'e':
- merge_memattrs (XEXP (x, i), XEXP (y, i));
- }
- }
- return;
-}
-
-
-/* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
-
-static bool
-old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
-{
- rtx p1, p2;
-
- /* Verify that I1 and I2 are equivalent. */
- if (GET_CODE (i1) != GET_CODE (i2))
- return false;
-
- p1 = PATTERN (i1);
- p2 = PATTERN (i2);
-
- if (GET_CODE (p1) != GET_CODE (p2))
- return false;
-
- /* If this is a CALL_INSN, compare register usage information.
- If we don't check this on stack register machines, the two
- CALL_INSNs might be merged leaving reg-stack.c with mismatching
- numbers of stack registers in the same basic block.
- If we don't check this on machines with delay slots, a delay slot may
- be filled that clobbers a parameter expected by the subroutine.
-
- ??? We take the simple route for now and assume that if they're
- equal, they were constructed identically. */
-
- if (CALL_P (i1)
- && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
- CALL_INSN_FUNCTION_USAGE (i2))
- || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
- return false;
-
-#ifdef STACK_REGS
- /* If cross_jump_death_matters is not 0, the insn's mode
- indicates whether or not the insn contains any stack-like
- regs. */
-
- if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
- {
- /* If register stack conversion has already been done, then
- death notes must also be compared before it is certain that
- the two instruction streams match. */
-
- rtx note;
- HARD_REG_SET i1_regset, i2_regset;
-
- CLEAR_HARD_REG_SET (i1_regset);
- CLEAR_HARD_REG_SET (i2_regset);
-
- for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
- SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
-
- for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
- SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
-
- GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
-
- return false;
-
- done:
- ;
- }
-#endif
-
- if (reload_completed
- ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
- return true;
-
- /* Do not do EQUIV substitution after reload. First, we're undoing the
- work of reload_cse. Second, we may be undoing the work of the post-
- reload splitting pass. */
- /* ??? Possibly add a new phase switch variable that can be used by
- targets to disallow the troublesome insns after splitting. */
- if (!reload_completed)
- {
- /* The following code helps take care of G++ cleanups. */
- rtx equiv1 = find_reg_equal_equiv_note (i1);
- rtx equiv2 = find_reg_equal_equiv_note (i2);
-
- if (equiv1 && equiv2
- /* If the equivalences are not to a constant, they may
- reference pseudos that no longer exist, so we can't
- use them. */
- && (! reload_completed
- || (CONSTANT_P (XEXP (equiv1, 0))
- && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
- {
- rtx s1 = single_set (i1);
- rtx s2 = single_set (i2);
- if (s1 != 0 && s2 != 0
- && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
- {
- validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
- validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
- if (! rtx_renumbered_equal_p (p1, p2))
- cancel_changes (0);
- else if (apply_change_group ())
- return true;
- }
- }
- }
-
- return false;
-}
-\f
-/* Look through the insns at the end of BB1 and BB2 and find the longest
- sequence that are equivalent. Store the first insns for that sequence
- in *F1 and *F2 and return the sequence length.
-
- To simplify callers of this function, if the blocks match exactly,
- store the head of the blocks in *F1 and *F2. */
-
-static int
-flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
- basic_block bb2, rtx *f1, rtx *f2)
-{
- rtx i1, i2, last1, last2, afterlast1, afterlast2;
- int ninsns = 0;
-
- /* Skip simple jumps at the end of the blocks. Complex jumps still
- need to be compared for equivalence, which we'll do below. */
-
- i1 = BB_END (bb1);
- last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
- if (onlyjump_p (i1)
- || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
- {
- last1 = i1;
- i1 = PREV_INSN (i1);
- }
-
- i2 = BB_END (bb2);
- if (onlyjump_p (i2)
- || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
- {
- last2 = i2;
- /* Count everything except for unconditional jump as insn. */
- if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
- ninsns++;
- i2 = PREV_INSN (i2);
- }
-
- while (true)
- {
- /* Ignore notes. */
- while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
- i1 = PREV_INSN (i1);
-
- while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
- i2 = PREV_INSN (i2);
-
- if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
- break;
-
- if (!old_insns_match_p (mode, i1, i2))
- break;
-
- merge_memattrs (i1, i2);
-
- /* Don't begin a cross-jump with a NOTE insn. */
- if (INSN_P (i1))
- {
- /* If the merged insns have different REG_EQUAL notes, then
- remove them. */
- rtx equiv1 = find_reg_equal_equiv_note (i1);
- rtx equiv2 = find_reg_equal_equiv_note (i2);
-
- if (equiv1 && !equiv2)
- remove_note (i1, equiv1);
- else if (!equiv1 && equiv2)
- remove_note (i2, equiv2);
- else if (equiv1 && equiv2
- && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
- {
- remove_note (i1, equiv1);
- remove_note (i2, equiv2);
- }
-
- afterlast1 = last1, afterlast2 = last2;
- last1 = i1, last2 = i2;
- ninsns++;
- }
-
- i1 = PREV_INSN (i1);
- i2 = PREV_INSN (i2);
- }
-
-#ifdef HAVE_cc0
- /* Don't allow the insn after a compare to be shared by
- cross-jumping unless the compare is also shared. */
- if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
- last1 = afterlast1, last2 = afterlast2, ninsns--;
-#endif
-
- /* Include preceding notes and labels in the cross-jump. One,
- this may bring us to the head of the blocks as requested above.
- Two, it keeps line number notes as matched as may be. */
- if (ninsns)
- {
- while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
- last1 = PREV_INSN (last1);
-
- if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
- last1 = PREV_INSN (last1);
-
- while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
- last2 = PREV_INSN (last2);
-
- if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
- last2 = PREV_INSN (last2);
-
- *f1 = last1;
- *f2 = last2;
- }
-
- return ninsns;
-}
-
/* Return true iff the condbranches at the end of BB1 and BB2 match. */
bool
condjump_equiv_p (struct equiv_info *info, bool call_init)
@@ -1252,8 +936,8 @@ condjump_equiv_p (struct equiv_info *inf
if (code2 == UNKNOWN)
return false;
- if (call_init && !struct_equiv_init (STRUCT_EQUIV_START | info->mode, info))
- gcc_unreachable ();
+ if (call_init)
+ struct_equiv_init (STRUCT_EQUIV_START | info->mode, info, false);
/* Make the sources of the pc sets unreadable so that when we call
insns_match_p it won't process them.
The death_notes_match_p from insns_match_p won't see the local registers
@@ -1322,15 +1006,20 @@ condjump_equiv_p (struct equiv_info *inf
return match;
}
-/* Return true iff outgoing edges of BB1 and BB2 match, together with
- the branch instruction. This means that if we commonize the control
- flow before end of the basic block, the semantic remains unchanged.
+/* Return true iff outgoing edges of INFO->y_block and INFO->x_block match,
+ together with the branch instruction. This means that if we commonize the
+ control flow before end of the basic block, the semantic remains unchanged.
+ If we need to compare jumps, we set STRUCT_EQUIV_MATCH_JUMPS in *MODE,
+ and pass *MODE to struct_equiv_init or assign it to INFO->mode, as
+ appropriate.
We may assume that there exists one edge with a common destination. */
static bool
-outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
+outgoing_edges_match (int *mode, struct equiv_info *info)
{
+ basic_block bb1 = info->y_block;
+ basic_block bb2 = info->x_block;
int nehedges1 = 0, nehedges2 = 0;
edge fallthru1 = 0, fallthru2 = 0;
edge e1, e2;
@@ -1346,114 +1035,19 @@ outgoing_edges_match (int mode, basic_bl
& (EDGE_COMPLEX | EDGE_FAKE)) == 0
&& (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
+ *mode |= STRUCT_EQUIV_MATCH_JUMPS;
/* Match conditional jumps - this may get tricky when fallthru and branch
edges are crossed. */
if (EDGE_COUNT (bb1->succs) == 2
&& any_condjump_p (BB_END (bb1))
&& onlyjump_p (BB_END (bb1)))
{
- edge b1, f1, b2, f2;
- bool reverse, match;
- rtx set1, set2, cond1, cond2;
- enum rtx_code code1, code2;
-
if (EDGE_COUNT (bb2->succs) != 2
|| !any_condjump_p (BB_END (bb2))
|| !onlyjump_p (BB_END (bb2)))
return false;
-
- b1 = BRANCH_EDGE (bb1);
- b2 = BRANCH_EDGE (bb2);
- f1 = FALLTHRU_EDGE (bb1);
- f2 = FALLTHRU_EDGE (bb2);
-
- /* Get around possible forwarders on fallthru edges. Other cases
- should be optimized out already. */
- if (FORWARDER_BLOCK_P (f1->dest))
- f1 = single_succ_edge (f1->dest);
-
- if (FORWARDER_BLOCK_P (f2->dest))
- f2 = single_succ_edge (f2->dest);
-
- /* To simplify use of this function, return false if there are
- unneeded forwarder blocks. These will get eliminated later
- during cleanup_cfg. */
- if (FORWARDER_BLOCK_P (f1->dest)
- || FORWARDER_BLOCK_P (f2->dest)
- || FORWARDER_BLOCK_P (b1->dest)
- || FORWARDER_BLOCK_P (b2->dest))
- return false;
-
- if (f1->dest == f2->dest && b1->dest == b2->dest)
- reverse = false;
- else if (f1->dest == b2->dest && b1->dest == f2->dest)
- reverse = true;
- else
- return false;
-
- set1 = pc_set (BB_END (bb1));
- set2 = pc_set (BB_END (bb2));
- if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
- != (XEXP (SET_SRC (set2), 1) == pc_rtx))
- reverse = !reverse;
-
- cond1 = XEXP (SET_SRC (set1), 0);
- cond2 = XEXP (SET_SRC (set2), 0);
- code1 = GET_CODE (cond1);
- if (reverse)
- code2 = reversed_comparison_code (cond2, BB_END (bb2));
- else
- code2 = GET_CODE (cond2);
-
- if (code2 == UNKNOWN)
- return false;
-
- /* Verify codes and operands match. */
- match = ((code1 == code2
- && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
- && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
- || (code1 == swap_condition (code2)
- && rtx_renumbered_equal_p (XEXP (cond1, 1),
- XEXP (cond2, 0))
- && rtx_renumbered_equal_p (XEXP (cond1, 0),
- XEXP (cond2, 1))));
-
- /* If we return true, we will join the blocks. Which means that
- we will only have one branch prediction bit to work with. Thus
- we require the existing branches to have probabilities that are
- roughly similar. */
- if (match
- && !optimize_size
- && maybe_hot_bb_p (bb1)
- && maybe_hot_bb_p (bb2))
- {
- int prob2;
-
- if (b1->dest == b2->dest)
- prob2 = b2->probability;
- else
- /* Do not use f2 probability as f2 may be forwarded. */
- prob2 = REG_BR_PROB_BASE - b2->probability;
-
- /* Fail if the difference in probabilities is greater than 50%.
- This rules out two well-predicted branches with opposite
- outcomes. */
- if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
- {
- if (dump_file)
- fprintf (dump_file,
- "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
- bb1->index, bb2->index, b1->probability, prob2);
-
- return false;
- }
- }
-
- if (dump_file && match)
- fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
- bb1->index, bb2->index);
-
- return match;
+ info->mode = *mode;
+ return condjump_equiv_p (info, true);
}
/* Generic case - we are seeing a computed jump, table jump or trapping
@@ -1501,31 +1095,22 @@ outgoing_edges_match (int mode, basic_bl
identical = false;
}
- if (identical)
+ if (identical
+ && struct_equiv_init (STRUCT_EQUIV_START | *mode, info, true))
{
- replace_label_data rr;
bool match;
- /* Temporarily replace references to LABEL1 with LABEL2
+ /* Indicate that LABEL1 is to be replaced with LABEL2
in BB1->END so that we could compare the instructions. */
- rr.r1 = label1;
- rr.r2 = label2;
- rr.update_label_nuses = false;
- for_each_rtx (&BB_END (bb1), replace_label, &rr);
+ info->y_label = label1;
+ info->x_label = label2;
- match = old_insns_match_p (mode, BB_END (bb1), BB_END (bb2));
+ match = insns_match_p (BB_END (bb1), BB_END (bb2), info);
if (dump_file && match)
fprintf (dump_file,
"Tablejumps in bb %i and %i match.\n",
bb1->index, bb2->index);
- /* Set the original label in BB1->END because when deleting
- a block whose end is a tablejump, the tablejump referenced
- from the instruction is deleted too. */
- rr.r1 = label2;
- rr.r2 = label1;
- for_each_rtx (&BB_END (bb1), replace_label, &rr);
-
return match;
}
}
@@ -1533,16 +1118,20 @@ outgoing_edges_match (int mode, basic_bl
}
}
+ /* Ensure that the edge counts do match. */
+ if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
+ return false;
+
/* First ensure that the instructions match. There may be many outgoing
edges so this test is generally cheaper. */
- if (!old_insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
+ /* FIXME: the regset compare might be costly. We should try to get a cheap
+ and reasonably effective test first. */
+ if (!struct_equiv_init (STRUCT_EQUIV_START | *mode, info, true)
+ || !insns_match_p (BB_END (bb1), BB_END (bb2), info))
return false;
- /* Search the outgoing edges, ensure that the counts do match, find possible
- fallthru and exception handling edges since these needs more
- validation. */
- if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
- return false;
+ /* Search the outgoing edges, find possible fallthru and exception
+ handling edges since these needs more validation. */
FOR_EACH_EDGE (e1, ei, bb1->succs)
{
@@ -1601,22 +1190,21 @@ outgoing_edges_match (int mode, basic_bl
static bool
try_crossjump_to_edge (int mode, edge e1, edge e2)
{
- int nmatch;
+ int nmatch, i;
basic_block src1 = e1->src, src2 = e2->src;
basic_block redirect_to, redirect_from, to_remove;
- rtx newpos1, newpos2;
edge s;
edge_iterator ei;
-
- newpos1 = newpos2 = NULL_RTX;
+ struct equiv_info info;
+ rtx x_active, y_active;
/* If we have partitioned hot/cold basic blocks, it is a bad idea
- to try this optimization.
+ to try this optimization.
Basic block partitioning may result in some jumps that appear to
- be optimizable (or blocks that appear to be mergeable), but which really
- must be left untouched (they are required to make it safely across
- partition boundaries). See the comments at the top of
+ be optimizable (or blocks that appear to be mergeable), but which really
+ must be left untouched (they are required to make it safely across
+ partition boundaries). See the comments at the top of
bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
if (flag_reorder_blocks_and_partition && no_new_pseudos)
@@ -1655,20 +1243,67 @@ try_crossjump_to_edge (int mode, edge e1
return false;
/* Look for the common insn sequence, part the first ... */
- if (!outgoing_edges_match (mode, src1, src2))
+ info.x_block = src2;
+ info.y_block = src1;
+ if (!outgoing_edges_match (&mode, &info))
return false;
/* ... and part the second. */
- nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
+ info.input_cost = optimize_size ? COSTS_N_INSNS (1) : -1;
+ nmatch = struct_equiv_block_eq (STRUCT_EQUIV_START | mode, &info);
/* Don't proceed with the crossjump unless we found a sufficient number
of matching instructions or the 'from' block was totally matched
(such that its predecessors will hopefully be redirected and the
block removed). */
- if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
- && (newpos1 != BB_HEAD (src1)))
+ if (!nmatch)
+ return false;
+ if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+ && (info.cur.y_start != BB_HEAD (src1)))
+ return false;
+ while (info.need_rerun)
+ {
+ nmatch = struct_equiv_block_eq (STRUCT_EQUIV_RERUN | mode, &info);
+ if (!nmatch)
+ return false;
+ if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+ && (info.cur.y_start != BB_HEAD (src1)))
+ return false;
+ }
+ nmatch = struct_equiv_block_eq (STRUCT_EQUIV_FINAL | mode, &info);
+ if ((nmatch -info.cur.input_count < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
+ && (info.cur.y_start != BB_HEAD (src1)))
return false;
+ /* Skip possible basic block header. */
+ x_active = info.cur.x_start;
+ if (LABEL_P (x_active))
+ x_active = NEXT_INSN (x_active);
+ if (NOTE_P (x_active))
+ x_active = NEXT_INSN (x_active);
+
+ y_active = info.cur.y_start;
+ if (LABEL_P (y_active))
+ y_active = NEXT_INSN (y_active);
+ if (NOTE_P (y_active))
+ y_active = NEXT_INSN (y_active);
+
+ /* In order for this code to become active, either we have to be called
+ before reload, or struct_equiv_block_eq needs to add register scavenging
+ code to allocate input_reg after reload. */
+ if (info.input_reg)
+ {
+ emit_insn_before (gen_move_insn (info.input_reg, info.x_input),
+ x_active);
+ emit_insn_before (gen_move_insn (info.input_reg, info.y_input),
+ y_active);
+ }
+
+ for (i = 0; i < info.cur.local_count; i++)
+ if (info.local_rvalue[i])
+ emit_insn_before (gen_move_insn (info.x_local[i], info.y_local[i]),
+ y_active);
+
/* Here we know that the insns in the end of SRC1 which are common with SRC2
will be deleted.
If we have tablejumps in the end of SRC1 and SRC2
@@ -1703,30 +1338,34 @@ try_crossjump_to_edge (int mode, edge e1
/* Avoid splitting if possible. We must always split when SRC2 has
EH predecessor edges, or we may end up with basic blocks with both
normal and EH predecessor edges. */
- if (newpos2 == BB_HEAD (src2)
+ if (info.cur.x_start == BB_HEAD (src2)
&& !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
redirect_to = src2;
else
{
- if (newpos2 == BB_HEAD (src2))
+ if (info.cur.x_start == BB_HEAD (src2))
{
/* Skip possible basic block header. */
- if (LABEL_P (newpos2))
- newpos2 = NEXT_INSN (newpos2);
- if (NOTE_P (newpos2))
- newpos2 = NEXT_INSN (newpos2);
+ if (LABEL_P (info.cur.x_start))
+ info.cur.x_start = NEXT_INSN (info.cur.x_start);
+ if (NOTE_P (info.cur.x_start))
+ info.cur.x_start = NEXT_INSN (info.cur.x_start);
}
if (dump_file)
fprintf (dump_file, "Splitting bb %i before %i insns\n",
src2->index, nmatch);
- redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
+ redirect_to = split_block (src2, PREV_INSN (info.cur.x_start))->dest;
}
if (dump_file)
- fprintf (dump_file,
- "Cross jumping from bb %i to bb %i; %i common insns\n",
- src1->index, src2->index, nmatch);
+ {
+ fprintf (dump_file, "Cross jumping from bb %i to bb %i; %i common insns",
+ src1->index, src2->index, nmatch);
+ if (info.cur.local_count)
+ fprintf (dump_file, ", %i local registers", info.cur.local_count);
+ fprintf (dump_file, "\n");
+ }
redirect_to->count += src1->count;
redirect_to->frequency += src1->frequency;
@@ -1790,17 +1429,12 @@ try_crossjump_to_edge (int mode, edge e1
/* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
- /* Skip possible basic block header. */
- if (LABEL_P (newpos1))
- newpos1 = NEXT_INSN (newpos1);
-
- if (NOTE_P (newpos1))
- newpos1 = NEXT_INSN (newpos1);
-
- redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
+ redirect_from = split_block (src1, PREV_INSN (y_active))->src;
to_remove = single_succ (redirect_from);
redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
+ COPY_REG_SET (redirect_from->il.rtl->global_live_at_end,
+ redirect_to->il.rtl->global_live_at_start);
delete_basic_block (to_remove);
update_forwarder_flag (redirect_from);
@@ -1957,9 +1591,22 @@ try_optimize_cfg (int mode)
bool changed;
int iterations = 0;
basic_block bb, b, next;
+ bool can_modify_jumps = ! targetm.cannot_modify_jumps_p ();
+ bool do_crossjump = false;
- if (mode & CLEANUP_CROSSJUMP)
- add_noreturn_fake_exit_edges ();
+ if (can_modify_jumps && (mode & CLEANUP_CROSSJUMP))
+ {
+ do_crossjump = true;
+ /* Life info updates malfunction in the presence of fake edges.
+ If we want to do any updates while fake edges are present, we'll have
+ to make sure to exclude them when recomputing global_live_at_end,
+ or treat them like EH edges. */
+ update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
+ (PROP_DEATH_NOTES
+ | ((mode & CLEANUP_POST_REGSTACK)
+ ? PROP_POST_REGSTACK : 0)));
+ add_noreturn_fake_exit_edges ();
+ }
if (mode & (CLEANUP_UPDATE_LIFE | CLEANUP_CROSSJUMP | CLEANUP_THREADING))
clear_bb_flags ();
@@ -1967,7 +1614,7 @@ try_optimize_cfg (int mode)
FOR_EACH_BB (bb)
update_forwarder_flag (bb);
- if (! targetm.cannot_modify_jumps_p ())
+ if (can_modify_jumps)
{
first_pass = true;
/* Attempt to merge blocks as made possible by edge removal. If
@@ -2123,8 +1770,8 @@ try_optimize_cfg (int mode)
changed_here = true;
/* Look for shared code between blocks. */
- if ((mode & CLEANUP_CROSSJUMP)
- && try_crossjump_bb (mode, b))
+ if (do_crossjump
+ && try_crossjump_bb (mode | STRUCT_EQUIV_SUSPEND_UPDATES, b))
changed_here = true;
/* Don't get confused by the index shift caused by
@@ -2135,8 +1782,9 @@ try_optimize_cfg (int mode)
changed = true;
}
- if ((mode & CLEANUP_CROSSJUMP)
- && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
+ if (do_crossjump
+ && try_crossjump_bb (mode | STRUCT_EQUIV_SUSPEND_UPDATES,
+ EXIT_BLOCK_PTR))
changed = true;
#ifdef ENABLE_CHECKING
@@ -2150,7 +1798,7 @@ try_optimize_cfg (int mode)
while (changed);
}
- if (mode & CLEANUP_CROSSJUMP)
+ if (do_crossjump)
remove_fake_exit_edges ();
FOR_ALL_BB (b)
Index: basic-block.h
===================================================================
/usr/bin/diff -p -d -F^( -u -L basic-block.h (revision 109499) -L basic-block.h (working copy) .svn/text-base/basic-block.h.svn-base basic-block.h
--- basic-block.h (revision 109499)
+++ basic-block.h (working copy)
@@ -850,6 +850,8 @@ enum update_life_extent
to match only full blocks */
#define STRUCT_EQUIV_MATCH_JUMPS 8192 /* Also include the jumps at the end of the block in the comparison. */
+#define STRUCT_EQUIV_SUSPEND_UPDATES 16384 /* Assume global_live_at_end is up-to-date even if the block isn't. */
+
extern void life_analysis (FILE *, int);
extern int update_life_info (sbitmap, enum update_life_extent, int);
extern int update_life_info_in_dirty_blocks (enum update_life_extent, int);
@@ -1169,7 +1171,7 @@ struct equiv_info
extern bool insns_match_p (rtx, rtx, struct equiv_info *);
extern int struct_equiv_block_eq (int, struct equiv_info *);
-extern bool struct_equiv_init (int, struct equiv_info *);
+extern bool struct_equiv_init (int, struct equiv_info *, bool);
extern bool rtx_equiv_p (rtx *, rtx, int, struct equiv_info *);
/* In cfgrtl.c */
Index: struct-equiv.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L struct-equiv.c (revision 109668) -L struct-equiv.c (working copy) .svn/text-base/struct-equiv.c.svn-base struct-equiv.c
--- struct-equiv.c (revision 109668)
+++ struct-equiv.c (working copy)
@@ -987,38 +987,59 @@ insns_match_p (rtx i1, rtx i2, struct eq
return false;
}
-/* Set up mode and register information in INFO. Return true for success. */
-bool
-struct_equiv_init (int mode, struct equiv_info *info)
+static bool
+struct_equiv_regs_eq_p (struct equiv_info *info)
{
- if ((info->x_block->flags | info->y_block->flags) & BB_DIRTY)
+ if (!(info->mode & STRUCT_EQUIV_SUSPEND_UPDATES)
+ && ((info->x_block->flags | info->y_block->flags) & BB_DIRTY))
update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
(PROP_DEATH_NOTES
- | ((mode & CLEANUP_POST_REGSTACK)
+ | ((info->mode & CLEANUP_POST_REGSTACK)
? PROP_POST_REGSTACK : 0)));
- if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
- info->y_block->il.rtl->global_live_at_end))
- {
#ifdef STACK_REGS
- unsigned rn;
+ if (info->mode & CLEANUP_POST_REGSTACK)
+ {
+ regset_head diff;
+ unsigned regnum;
+ bitmap_iterator rsi;
- if (!(mode & CLEANUP_POST_REGSTACK))
- return false;
- /* After reg-stack. Remove bogus live info about stack regs. N.B.
- these regs are not necessarily all dead - we swap random bogosity
- against constant bogosity. However, clearing these bits at
- least makes the regsets comparable. */
- for (rn = FIRST_STACK_REG; rn <= LAST_STACK_REG; rn++)
+ INIT_REG_SET (&diff);
+ bitmap_xor (&diff,
+ info->x_block->il.rtl->global_live_at_end,
+ info->y_block->il.rtl->global_live_at_end);
+ EXECUTE_IF_SET_IN_BITMAP (&diff, 0, regnum, rsi)
{
- CLEAR_REGNO_REG_SET (info->x_block->il.rtl->global_live_at_end, rn);
- CLEAR_REGNO_REG_SET (info->y_block->il.rtl->global_live_at_end, rn);
+ if (regnum < FIRST_STACK_REG || regnum > LAST_STACK_REG)
+ return false;
}
- if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
- info->y_block->il.rtl->global_live_at_end))
+ return true;
+ }
#endif
+ return (REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end,
+ info->y_block->il.rtl->global_live_at_end));
+}
+
+/* Set up mode and register information in INFO. Return true for success.
+ Nonzero CHECK_REGS_EQ indicates that we might be called with blocks that
+ have non-matching successor sets, and thus need to check their live_at_end
+ regsets for match in the first pass. */
+bool
+struct_equiv_init (int mode, struct equiv_info *info, bool check_regs_eq)
+{
+ if (!(mode & STRUCT_EQUIV_SUSPEND_UPDATES)
+ && ((info->x_block->flags & info->y_block->flags) & BB_DIRTY))
+ update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
+ (PROP_DEATH_NOTES
+ | ((mode & CLEANUP_POST_REGSTACK)
+ ? PROP_POST_REGSTACK : 0)));
+ info->mode = mode;
+ if (check_regs_eq && (mode & STRUCT_EQUIV_START))
+ {
+ if (!struct_equiv_regs_eq_p (info))
return false;
}
- info->mode = mode;
+ else if (mode & (STRUCT_EQUIV_FINAL | STRUCT_EQUIV_SUSPEND_UPDATES))
+ gcc_assert (struct_equiv_regs_eq_p (info));
if (mode & STRUCT_EQUIV_START)
{
info->x_input = info->y_input = info->input_reg = NULL_RTX;
@@ -1036,7 +1057,10 @@ struct_equiv_init (int mode, struct equi
info->common_live = ALLOC_REG_SET (®_obstack);
info->x_local_live = ALLOC_REG_SET (®_obstack);
info->y_local_live = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (info->common_live, info->x_block->il.rtl->global_live_at_end);
+ COPY_REG_SET (info->common_live,
+ ((info->x_block->flags & BB_DIRTY
+ ? info->y_block : info->x_block)
+ ->il.rtl->global_live_at_end));
struct_equiv_make_checkpoint (&info->best_match, info);
return true;
}
@@ -1100,8 +1124,7 @@ struct_equiv_block_eq (int mode, struct
x_stop = info->cur.x_start;
y_stop = info->cur.y_start;
}
- if (!struct_equiv_init (mode, info))
- gcc_unreachable ();
+ struct_equiv_init (mode, info, false);
/* Skip simple jumps at the end of the blocks. Complex jumps still
need to be compared for equivalence, which we'll do below. */
^ permalink raw reply [flat|nested] 16+ messages in thread
* How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code)
2006-01-13 15:15 ` RFA: re-instate struct_equiv code (Was: Re: Huge compile time regressions) Joern RENNECKE
@ 2006-01-13 15:30 ` Joern RENNECKE
2006-01-26 10:20 ` Bernd Schmidt
0 siblings, 1 reply; 16+ messages in thread
From: Joern RENNECKE @ 2006-01-13 15:30 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: Daniel Berlin, Steven Bosscher, gcc
[-- Attachment #1: Type: text/plain, Size: 369 bytes --]
For easier reviewing, I have attached the diff to the cfgcleanup
version previous to the patch backout.
I'm not sure what the best way to keep the svn history sane is. When/if
the patch is approved, should I first do an
svn merge -r108792:108791, check that in, and then apply the patch with
the actual new stuff?
Or will an svn copy of cfgcleanup.c work better?
[-- Attachment #2: tmp --]
[-- Type: text/plain, Size: 4998 bytes --]
Index: cfgcleanup.c
===================================================================
/usr/bin/diff -p -d -F^( -u -L cfgcleanup.c (revision 108713) -L cfgcleanup.c (working copy) .svn/tmp/text-base/cfgcleanup.c.svn-base cfgcleanup.c
--- cfgcleanup.c (revision 108713)
+++ cfgcleanup.c (working copy)
@@ -936,8 +936,8 @@ condjump_equiv_p (struct equiv_info *inf
if (code2 == UNKNOWN)
return false;
- if (call_init && !struct_equiv_init (STRUCT_EQUIV_START | info->mode, info))
- gcc_unreachable ();
+ if (call_init)
+ struct_equiv_init (STRUCT_EQUIV_START | info->mode, info, false);
/* Make the sources of the pc sets unreadable so that when we call
insns_match_p it won't process them.
The death_notes_match_p from insns_match_p won't see the local registers
@@ -1096,7 +1096,7 @@ outgoing_edges_match (int *mode, struct
}
if (identical
- && struct_equiv_init (STRUCT_EQUIV_START | *mode, info))
+ && struct_equiv_init (STRUCT_EQUIV_START | *mode, info, true))
{
bool match;
@@ -1118,17 +1118,20 @@ outgoing_edges_match (int *mode, struct
}
}
+ /* Ensure that the edge counts do match. */
+ if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
+ return false;
+
/* First ensure that the instructions match. There may be many outgoing
edges so this test is generally cheaper. */
- if (!struct_equiv_init (STRUCT_EQUIV_START | *mode, info)
+ /* FIXME: the regset compare might be costly. We should try to get a cheap
+ and reasonably effective test first. */
+ if (!struct_equiv_init (STRUCT_EQUIV_START | *mode, info, true)
|| !insns_match_p (BB_END (bb1), BB_END (bb2), info))
return false;
- /* Search the outgoing edges, ensure that the counts do match, find possible
- fallthru and exception handling edges since these needs more
- validation. */
- if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
- return false;
+ /* Search the outgoing edges, find possible fallthru and exception
+ handling edges since these needs more validation. */
FOR_EACH_EDGE (e1, ei, bb1->succs)
{
@@ -1353,8 +1356,6 @@ try_crossjump_to_edge (int mode, edge e1
fprintf (dump_file, "Splitting bb %i before %i insns\n",
src2->index, nmatch);
redirect_to = split_block (src2, PREV_INSN (info.cur.x_start))->dest;
- COPY_REG_SET (info.y_block->il.rtl->global_live_at_end,
- info.x_block->il.rtl->global_live_at_end);
}
if (dump_file)
@@ -1432,6 +1433,8 @@ try_crossjump_to_edge (int mode, edge e1
to_remove = single_succ (redirect_from);
redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
+ COPY_REG_SET (redirect_from->il.rtl->global_live_at_end,
+ redirect_to->il.rtl->global_live_at_start);
delete_basic_block (to_remove);
update_forwarder_flag (redirect_from);
@@ -1588,9 +1591,22 @@ try_optimize_cfg (int mode)
bool changed;
int iterations = 0;
basic_block bb, b, next;
+ bool can_modify_jumps = ! targetm.cannot_modify_jumps_p ();
+ bool do_crossjump = false;
- if (mode & CLEANUP_CROSSJUMP)
- add_noreturn_fake_exit_edges ();
+ if (can_modify_jumps && (mode & CLEANUP_CROSSJUMP))
+ {
+ do_crossjump = true;
+ /* Life info updates malfunction in the presence of fake edges.
+ If we want to do any updates while fake edges are present, we'll have
+ to make sure to exclude them when recomputing global_live_at_end,
+ or treat them like EH edges. */
+ update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
+ (PROP_DEATH_NOTES
+ | ((mode & CLEANUP_POST_REGSTACK)
+ ? PROP_POST_REGSTACK : 0)));
+ add_noreturn_fake_exit_edges ();
+ }
if (mode & (CLEANUP_UPDATE_LIFE | CLEANUP_CROSSJUMP | CLEANUP_THREADING))
clear_bb_flags ();
@@ -1598,7 +1614,7 @@ try_optimize_cfg (int mode)
FOR_EACH_BB (bb)
update_forwarder_flag (bb);
- if (! targetm.cannot_modify_jumps_p ())
+ if (can_modify_jumps)
{
first_pass = true;
/* Attempt to merge blocks as made possible by edge removal. If
@@ -1754,8 +1770,8 @@ try_optimize_cfg (int mode)
changed_here = true;
/* Look for shared code between blocks. */
- if ((mode & CLEANUP_CROSSJUMP)
- && try_crossjump_bb (mode, b))
+ if (do_crossjump
+ && try_crossjump_bb (mode | STRUCT_EQUIV_SUSPEND_UPDATES, b))
changed_here = true;
/* Don't get confused by the index shift caused by
@@ -1766,8 +1782,9 @@ try_optimize_cfg (int mode)
changed = true;
}
- if ((mode & CLEANUP_CROSSJUMP)
- && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
+ if (do_crossjump
+ && try_crossjump_bb (mode | STRUCT_EQUIV_SUSPEND_UPDATES,
+ EXIT_BLOCK_PTR))
changed = true;
#ifdef ENABLE_CHECKING
@@ -1781,7 +1798,7 @@ try_optimize_cfg (int mode)
while (changed);
}
- if (mode & CLEANUP_CROSSJUMP)
+ if (do_crossjump)
remove_fake_exit_edges ();
FOR_ALL_BB (b)
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code)
2006-01-13 15:30 ` How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code) Joern RENNECKE
@ 2006-01-26 10:20 ` Bernd Schmidt
2006-01-26 14:40 ` Daniel Berlin
2006-01-26 14:40 ` Joern RENNECKE
0 siblings, 2 replies; 16+ messages in thread
From: Bernd Schmidt @ 2006-01-26 10:20 UTC (permalink / raw)
To: Joern RENNECKE; +Cc: Daniel Berlin, Steven Bosscher, gcc
Joern RENNECKE wrote:
> For easier reviewing, I have attached the diff to the cfgcleanup version
> previous to the patch backout.
Thanks. Let me see if I understood the problem - please correct me if I
describe anything incorrectly.
The previous cross jumping code didn't care about register liveness,
since it just checked for identical instruction streams. The new, more
clever code, requires that regsets are identical at the end of the
blocks we're trying to match. In addition, cross-jumping can modify
blocks, requiring us to update life information (by calling a global
update_life_info in struct_equiv_init), which is the really expensive
part that caused the slowdown (how often did we end up updating life info?).
The new patch prevents multiple updates by introducing
STRUCT_EQUIV_SUSPEND_UPDATE. However, I don't see how this is safe
given that cross jumping will modify basic blocks and change the set of
registers live at their ends.
Is there a way to keep life info accurate when doing the cross jump (so
we don't set any dirty flags)? Or, possibly, change the algorithm so
that it visits blocks in a different order - dirtying more blocks before
doing a global life update?
> I'm not sure what the best way to keep the svn history sane is. When/if
> the patch is approved, should I first do an
> svn merge -r108792:108791, check that in, and then apply the patch with
> the actual new stuff?
Maybe
svn diff -r108792:108791 |patch -p0
patch <fixes.diff
svn commit
Bernd
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code)
2006-01-26 10:20 ` Bernd Schmidt
2006-01-26 14:40 ` Daniel Berlin
@ 2006-01-26 14:40 ` Joern RENNECKE
2006-01-30 0:16 ` Bernd Schmidt
1 sibling, 1 reply; 16+ messages in thread
From: Joern RENNECKE @ 2006-01-26 14:40 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: Daniel Berlin, Steven Bosscher, gcc
Bernd Schmidt wrote:
> Thanks. Let me see if I understood the problem - please correct me
> if I describe anything incorrectly.
>
> The previous cross jumping code didn't care about register liveness,
> since it just checked for identical instruction streams. The new,
> more clever code, requires that regsets are identical at the end of
> the blocks we're trying to match. In addition, cross-jumping can
> modify blocks, requiring us to update life information (by calling a
> global update_life_info in struct_equiv_init), which is the really
> expensive part that caused the slowdown (how often did we end up
> updating life info?).
The code has always required that the set of sucessor blocks is
identical, which implies that the regsets of live registers at the end
of the blocks must be identical too. The old code didn't require
up-to-date liveness information. The new code does. As a sanity check,
it verifies that the regsets are equal.
Because the new code as of December actually updated life information
incorrectly, the global updates that were done had also quite a lot of
work to do (and didn't really do it right, because of the presence of
fake edges).
> The new patch prevents multiple updates by introducing
> STRUCT_EQUIV_SUSPEND_UPDATE. However, I don't see how this is safe
> given that cross jumping will modify basic blocks and change the set
> of registers live at their ends.
>
> Is there a way to keep life info accurate when doing the cross jump
> (so we don't set any dirty flags)? Or, possibly, change the algorithm
> so that it visits blocks in a different order - dirtying more blocks
> before doing a global life update?
As far as I can tell, the global_live_{start,end} information is now
kept up to date, although I have to admit that I don't really understand
what was meant with the comment
/* We may have some registers visible trought the block. */
that is placed before setting the dirty flag on the block.
The REG_DEAD / REG_UNUSED notes may get out date, but AFAICS they are
not needed inside the loop that does the cross-jumping, and there is a
global update afterwards.
>
>> I'm not sure what the best way to keep the svn history sane is.
>> When/if the patch is approved, should I first do an
>> svn merge -r108792:108791, check that in, and then apply the patch
>> with the actual new stuff?
>
>
> Maybe
>
> svn diff -r108792:108791 |patch -p0
> patch <fixes.diff
> svn commit
That is the easy way, but my concern was with keeping the information
from svn annotate as sane as possible. Presumably a merge or svn copy
could have preserved the old
history from before the patch back-out, but since another patch to
cfgcleanup has gone in in the meantime, an svn copy is no longer a
realistic option.
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code)
2006-01-26 10:20 ` Bernd Schmidt
@ 2006-01-26 14:40 ` Daniel Berlin
2006-01-29 19:12 ` Bernd Schmidt
2006-01-26 14:40 ` Joern RENNECKE
1 sibling, 1 reply; 16+ messages in thread
From: Daniel Berlin @ 2006-01-26 14:40 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: Joern RENNECKE, Steven Bosscher, gcc
On Thu, 2006-01-26 at 11:20 +0100, Bernd Schmidt wrote:
> Joern RENNECKE wrote:
> > For easier reviewing, I have attached the diff to the cfgcleanup version
> > previous to the patch backout.
>
> Thanks. Let me see if I understood the problem - please correct me if I
> describe anything incorrectly.
>
> The previous cross jumping code didn't care about register liveness,
> since it just checked for identical instruction streams. The new, more
> clever code, requires that regsets are identical at the end of the
> blocks we're trying to match. In addition, cross-jumping can modify
> blocks, requiring us to update life information (by calling a global
> update_life_info in struct_equiv_init), which is the really expensive
> part that caused the slowdown (how often did we end up updating life info?).
We already update life info way too much, even without struct-equiv
(Before struct equiv, this was done because flow's dce relied on
register liveness, and we called it from everywhere under the sun,
usually deep within other functions nobody realized were doing it). I
can tell you that *without* struct equiv, we update liveness at least 19
or 20 times per compile, on average. Some are much much higher, because
each cleanup_cfg iteration causes a life update. This is a true time
sink in the compiler.
>
> The new patch prevents multiple updates by introducing
> STRUCT_EQUIV_SUSPEND_UPDATE. However, I don't see how this is safe
> given that cross jumping will modify basic blocks and change the set of
> registers live at their ends.
>
> Is there a way to keep life info accurate when doing the cross jump (so
> we don't set any dirty flags)?
Hard, but probably possible. It's also probably expensive.
> Or, possibly, change the algorithm so
> that it visits blocks in a different order - dirtying more blocks before
> doing a global life update?
If Joern has found a way to avoid updating liveness until he is done
with the struct-equiv stuff (even if this means avoiding checking
certain blocks because the liveness may be out of date), IMHO that is
the best solution.
No algorithm that has to iterate, *and update global liveness on each
iteration*, will ever really be fast enough that you want it on all the
time. IMHO.
We already do it with cleanup_cfg (where we do it because we run flow's
dce in the middle of cfg cleanups on each iteration), and it is one of
the slowest parts of the backend we've got right now.
> > I'm not sure what the best way to keep the svn history sane is. When/if
> > the patch is approved, should I first do an
> > svn merge -r108792:108791, check that in, and then apply the patch with
> > the actual new stuff?
>
> Maybe
>
> svn diff -r108792:108791 |patch -p0
> patch <fixes.diff
> svn commit
>
change the first command to svn merge -r108792:108791 and you've got it
right (the difference being that merge in reverse will properly
delete/readd files, and patch -p0 will not)
>
> Bernd
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code)
2006-01-26 14:40 ` Daniel Berlin
@ 2006-01-29 19:12 ` Bernd Schmidt
2006-01-30 6:35 ` Ian Lance Taylor
0 siblings, 1 reply; 16+ messages in thread
From: Bernd Schmidt @ 2006-01-29 19:12 UTC (permalink / raw)
To: Daniel Berlin; +Cc: Joern RENNECKE, Steven Bosscher, gcc, hubicka
Daniel Berlin wrote:
> We already update life info way too much, even without struct-equiv
> (Before struct equiv, this was done because flow's dce relied on
> register liveness, and we called it from everywhere under the sun,
> usually deep within other functions nobody realized were doing it). I
> can tell you that *without* struct equiv, we update liveness at least 19
> or 20 times per compile, on average. Some are much much higher, because
> each cleanup_cfg iteration causes a life update. This is a true time
> sink in the compiler.
Let me ask a really stupid question. Where are we supposed to be
clearing BB_DIRTY flags?
I instrumented the old version of the struct-equiv patches to give me
some information about the basic blocks it's being called for, and
noticed that blocks always remain dirty, even though we're calling
update_life_info_in_dirty_blocks. A quick grep showed no place in the
compiler where the flag is cleared. Under these circumstances, it's no
surprise that we keep doing global liveness updates during crossjumping.
Sadly, a simple patch to clear the flag in update_life_info just failed
to bootstrap with an internal compiler error.
Jan... the ChangeLogs suggest that you came up with BB_DIRTY. How is
this intended to work?
Bernd
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code)
2006-01-26 14:40 ` Joern RENNECKE
@ 2006-01-30 0:16 ` Bernd Schmidt
2006-01-30 14:49 ` Joern RENNECKE
0 siblings, 1 reply; 16+ messages in thread
From: Bernd Schmidt @ 2006-01-30 0:16 UTC (permalink / raw)
To: Joern RENNECKE; +Cc: Daniel Berlin, Steven Bosscher, gcc
Joern RENNECKE wrote:
> Because the new code as of December actually updated life information
> incorrectly, the global updates that were done had also quite a lot of
> work to do (and didn't really do it right, because of the presence of
> fake edges).
Could you elaborate on the problem with fake edges?
Bernd
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code)
2006-01-29 19:12 ` Bernd Schmidt
@ 2006-01-30 6:35 ` Ian Lance Taylor
0 siblings, 0 replies; 16+ messages in thread
From: Ian Lance Taylor @ 2006-01-30 6:35 UTC (permalink / raw)
To: Bernd Schmidt
Cc: Daniel Berlin, Joern RENNECKE, Steven Bosscher, gcc, hubicka
Bernd Schmidt <bernds_cb1@t-online.de> writes:
> Let me ask a really stupid question. Where are we supposed to be
> clearing BB_DIRTY flags?
>
> I instrumented the old version of the struct-equiv patches to give me
> some information about the basic blocks it's being called for, and
> noticed that blocks always remain dirty, even though we're calling
> update_life_info_in_dirty_blocks. A quick grep showed no place in the
> compiler where the flag is cleared. Under these circumstances, it's
> no surprise that we keep doing global liveness updates during
> crossjumping.
The function clear_bb_flags clears the BB_DIRTY flag. It is called
from a few places, including cleanup_cfg.
Ian
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code)
2006-01-30 0:16 ` Bernd Schmidt
@ 2006-01-30 14:49 ` Joern RENNECKE
0 siblings, 0 replies; 16+ messages in thread
From: Joern RENNECKE @ 2006-01-30 14:49 UTC (permalink / raw)
To: Bernd Schmidt; +Cc: Daniel Berlin, Steven Bosscher, gcc
Bernd Schmidt wrote:
> Joern RENNECKE wrote:
>
>> Because the new code as of December actually updated life information
>> incorrectly, the global updates that were done had also quite a lot
>> of work to do (and didn't really do it right, because of the presence
>> of fake edges).
>
>
> Could you elaborate on the problem with fake edges?
A fake edge is an edge from a node where there control might flow out of
the function (or not at all), e.g. a call to a noreturn function, to the
exit block. As far as I can tell, these are inserted for the
crossjumping pass so that we will cover matches involving such nodes, as
they otherwise might not have any successor.
The problem with doing live updates in the presence of fake edges is
that a number of registers are live in the exit block, in particular all
the call-saved registers with are restored in the epilogue (the epilogue
is a proper predecessor of the exit block, and the register restores are
kept live by marking these registers as live in the exit block).
If you do an live update while fake edges are present, the liveness of
registers in the exit block is propagated into the sources of the fake
edges, even though most or all of these registers
are not actually live there.
^ permalink raw reply [flat|nested] 16+ messages in thread
end of thread, other threads:[~2006-01-30 14:39 UTC | newest]
Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-12-15 2:12 Huge compile time regressions Steven Bosscher
2005-12-15 7:58 ` Daniel Berlin
2005-12-16 13:46 ` Bernd Schmidt
2006-01-05 22:06 ` Joern RENNECKE
2006-01-05 22:10 ` Joern RENNECKE
2006-01-05 22:20 ` Joern RENNECKE
2006-01-13 15:15 ` RFA: re-instate struct_equiv code (Was: Re: Huge compile time regressions) Joern RENNECKE
2006-01-13 15:30 ` How to reverse patch reversal in cfgcleanup.c (Was: RFA: re-instate struct_equiv code) Joern RENNECKE
2006-01-26 10:20 ` Bernd Schmidt
2006-01-26 14:40 ` Daniel Berlin
2006-01-29 19:12 ` Bernd Schmidt
2006-01-30 6:35 ` Ian Lance Taylor
2006-01-26 14:40 ` Joern RENNECKE
2006-01-30 0:16 ` Bernd Schmidt
2006-01-30 14:49 ` Joern RENNECKE
2005-12-19 13:58 ` Huge compile time regressions Joern RENNECKE
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).