pcc speed hacking
Chris Torek
chris at umcp-cs.UUCP
Fri Jul 12 13:27:49 AEST 1985
Index: 4.2BSD lib/mip Not-a-Bug-Actually-but-with-a Fix anyway
I ran some short profiles on the 4.2 (well, 4.2 1/2) BSD Portable
C Compiler, and discovered that it spent about 10% of its time in
a routine called "clearst" (with the next highest CPU eater being
the parser: no surprise). Looking at the source showed what
clearst does: it removes symbol table entries that are no longer
in scope. That is, if I write
f() {
int flags = somefunc();
if (flag != 0) {
register char *p = foo(flags);
bar(p);
}
}
then clearst is called at that first } to delete "p", and at the
second to delete "flags". In both cases the clearst routine searches
the ENTIRE symbol table (3000 entries!). This is silly. In general
only a few symbols will need to be deleted. The obvious thing to do
was to chain together all the symbols at any particular scope level,
and that is what I have done.
The changes listed here will (a) not match your line numbers and (b)
not match your file names, unless you are running a VERY late version
of the C compiler (with the Fortran fixes from Donn Seely) in some
cases. I belive the file that is now "manifest.h" was once "manifest"
and that the constants in "config.h" were previously scattered about.
The file that is now "pass1.h" used to be "mfile1".
In any case you can put the MAXSDEPTH definition in ptfn.c, or you
can just use 100. I probably could have made MAXSDEPTH from one
of the other constants, but this was easier. (If you think 100
scope levels is small, think again; and the compiler already dies
if you use more than 50 left braces anyway.)
So, first: the configuration parameter for maximum scope depth:
RCS file: RCS/config.h,v
retrieving revision 1.1
diff -c1 -r1.1 config.h
*** /tmp/,RCSt1007610 Thu Jul 11 22:49:13 1985
--- config.h Tue Jul 9 06:29:35 1985
***************
*** 30,31
#define NRECUR (10*TREESZ) /* maximum eval recursion depth */
--- 30,33 -----
#define NRECUR (10*TREESZ) /* maximum eval recursion depth */
+ #define MAXSDEPTH 100 /* max # active scopes */
+ /* actually we're limited to about 50, but ... */
---------------------------------------------------------------------
Next, the changes to "struct symtab" in mfile1. The "suse" change was
in case you compile something with more than 32767 lines.... I moved
"offset" only so that things would be on nice boundaries, making the
structure stay packed.
RCS file: RCS/pass1.h,v
retrieving revision 1.1
diff -c1 -r1.1 pass1.h
*** /tmp/,RCSt1007615 Thu Jul 11 22:49:23 1985
--- pass1.h Tue Jul 9 06:28:59 1985
***************
*** 10,11
* Symbol table definition.
*/
--- 10,15 -----
* Symbol table definition.
+ *
+ * Colliding entries are moved down with a standard
+ * probe (no quadratic rehash here) and moved back when
+ * entries are cleared.
*/
***************
*** 12,13
struct symtab {
#ifndef FLEXNAMES
--- 16,18 -----
struct symtab {
+ struct symtab *snext; /* scope chain, when clearing */
#ifndef FLEXNAMES
***************
*** 21,23
char sflags; /* flags, see below */
- int offset; /* offset or value */
short dimoff; /* offset into the dimension table */
--- 26,27 -----
char sflags; /* flags, see below */
short dimoff; /* offset into the dimension table */
***************
*** 24,26
short sizoff; /* offset into the size table */
! short suse; /* line number of last use of the variable */
};
--- 28,31 -----
short sizoff; /* offset into the size table */
! int offset; /* offset or value */
! int suse; /* line number of last use of the variable */
};
---------------------------------------------------------------------
Now, the real change. pftn gets a new version of clearst, and
declares symchain and chaintop. I also replaced the two calls to
movestab with structure assignments (since that's all movestab
did). There are a number of new register declarations as well
(efficiency hacking). WARNING: I've edited this diff by hand to
delete the old clearst, and appended the new one at the bottom, so
as to avoid displaying lots of AT&T code. Do not try to use
patch....
RCS file: RCS/pftn.c,v
retrieving revision 1.1
diff -c1 -r1.1 pftn.c
*** /tmp/,RCSt1007621 Thu Jul 11 22:49:38 1985
--- pftn.c Tue Jul 9 06:33:59 1985
***************
*** 8,9
struct instk {
--- 8,12 -----
+ struct symtab *schain[MAXSDEPTH]; /* sym chains for clearst */
+ int chaintop; /* highest active entry */
+
struct instk {
***************
*** 32,34
! defid( q, class ) NODE *q; {
register struct symtab *p;
--- 35,37 -----
! defid( q, class ) register NODE *q; register int class; {
register struct symtab *p;
***************
*** 35,37
int idp;
! TWORD type;
TWORD stp;
--- 38,40 -----
int idp;
! register TWORD type;
TWORD stp;
***************
*** 37,39
TWORD stp;
! int scl;
int dsym, ddef;
--- 40,42 -----
TWORD stp;
! register int scl;
int dsym, ddef;
***************
*** 249,251
if( class==MOU || class==MOS || class & FIELD ){/* make a new entry */
! int * memp;
p->sflags |= SNONUNIQ; /* old entry is nonunique */
--- 252,254 -----
if( class==MOU || class==MOS || class & FIELD ){/* make a new entry */
! register int *memp;
p->sflags |= SNONUNIQ; /* old entry is nonunique */
***************
*** 372,373
/* user-supplied routine to fix up new definitions */
--- 375,388 -----
+ {
+ register int l = p->slevel;
+
+ if( l >= MAXSDEPTH )
+ cerror( "scopes nested too deep" );
+
+ p->snext = schain[l];
+ schain[l] = p;
+ if( l >= chaintop )
+ chaintop = l + 1;
+ }
+
/* user-supplied routine to fix up new definitions */
***************
*** 1811,1815
Old vs new clearst diff deleted!! (New clearst given below)
***************
*** 1874,1896
movestab( p, q ) used to live here (again diff text deleted... just delete
all of movestab; it isn't used anymore.)
***************
*** 1902,1904
}
! movestab( q, p );
p->sflags |= SHIDDEN;
--- 1901,1903 -----
}
! *q = *p;
p->sflags |= SHIDDEN;
---------------------------------------------------------------------
Finally, here is the replacement clearst. (The code looks the way
it does only because I'm trying not to change formatting styles in
midcompiler, not because I like it looking like that. . . .)
clearst( lev ) register int lev; {
register struct symtab *p, *q;
register int temp;
struct symtab *clist = 0;
temp = lineno;
aobeg();
/* step 1: remove entries */
while( chaintop-1 > lev ){
register int type;
p = schain[--chaintop];
schain[chaintop] = 0;
for( ; p; p = q ){
q = p->snext;
type = p->stype;
if( p->stype == TNULL || p->slevel <= lev )
cerror( "schain botch" );
lineno = p->suse < 0 ? -p->suse : p->suse;
if( p->stype==UNDEF || ( p->sclass==ULABEL && lev<2 ) ){
lineno = temp;
#ifndef FLEXNAMES
uerror( "%.8s undefined", p->sname );
#else
uerror( "%s undefined", p->sname );
#endif
}
else aocode(p);
# ifndef BUG1
if( ddebug ){
#ifndef FLEXNAMES
printf( "removing %.8s", p->sname );
#else
printf( "removing %s", p->sname );
#endif
printf( " from stab[%d], flags %o level %d\n",
p-stab, p->sflags, p->slevel);
}
# endif
if( p->sflags & SHIDES )unhide( p );
p->stype = TNULL;
p->snext = clist;
clist = p;
}
}
/* step 2: fix any mishashed entries */
p = clist;
while( p ){
register struct symtab *r;
q = p;
for(;;){
if( ++q >= &stab[SYMTSZ] )q = stab;
if( q == p || q->stype == TNULL )break;
if( (r = relook(q)) != q ) {
*r = *q;
q->stype = NULL;
}
}
p = p->snext;
}
lineno = temp;
aoend();
}
---------------------------------------------------------------------
Well, that's all there is to it. Be sure to save the old compiler
someplace, and I'd suggest doing a "make clean" before doing a
"make"; I thought my code was wrong and it turned out that make
hadn't recompiled stab.o because it had no dependency list. . . .
(By the way, the make has to be done in ../pcc, in case that isn't
obvious.)
Today clearst, tommorrow yyparse! :-)
--
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 4251)
UUCP: seismo!umcp-cs!chris
CSNet: chris at umcp-cs ARPA: chris at maryland
More information about the Comp.bugs.4bsd.ucb-fixes
mailing list