* Copyright (c) 1980 Regents of the University of California.
* All rights reserved. The Berkeley software License Agreement
* specifies the terms and conditions for redistribution.
static char sccsid
[] = "@(#)optim.c 5.4 (Berkeley) 1/3/88";
* Miscellaneous optimizer routines, f77 compiler pass 1.
* UCSD Chemistry modification history:
* Revision 5.2 86/03/04 17:47:08 donn
* Change buffcat() and buffct1() analogously to putcat and putct1() --
* ensure that memoffset is evaluated before vleng. Take care not to
* screw up and return something other than an expression.
* Revision 5.1 85/08/10 03:48:42 donn
* Revision 2.12 85/06/08 22:57:01 donn
* Prevent core dumps -- bug in optinsert was causing lastslot to be wrong
* when a slot was inserted at the end of the buffer.
* Revision 2.11 85/03/18 08:05:05 donn
* Prevent warnings about implicit conversions.
* Revision 2.10 85/02/12 20:13:00 donn
* Resurrected the hack in 2.6.1.1 to avoid creating a temporary when
* there is a concatenation on the rhs of an assignment, and threw out
* all the code dealing with starcat(). It seems that we can't use a
* temporary because the lhs as well as the rhs may have nonconstant length.
* Revision 2.9 85/01/18 00:53:52 donn
* Missed a call to free() in the last change...
* Revision 2.8 85/01/18 00:50:03 donn
* Fixed goof made when modifying buffmnmx() to explicitly call expand().
* Revision 2.7 85/01/15 18:47:35 donn
* Changes to allow character*(*) variables to appear in concatenations in
* the rhs of an assignment statement.
* Revision 2.6 84/12/16 21:46:27 donn
* Fixed bug that prevented concatenations from being run together. Changed
* buffpower() to not touch exponents greater than 64 -- let putpower do them.
* Revision 2.5 84/10/29 08:41:45 donn
* Added hack to flushopt() to prevent the compiler from trying to generate
* intermediate code after an error.
* Revision 2.4 84/08/07 21:28:00 donn
* Removed call to p2flush() in putopt() -- this allows us to make better use
* of the buffering on the intermediate code file.
* Revision 2.3 84/08/01 16:06:24 donn
* Forced expand() to expand subscripts.
* Revision 2.2 84/07/19 20:21:55 donn
* Decided I liked the expression tree algorithm after all. The algorithm
* which repeatedly squares temporaries is now checked in as rev. 2.1.
* Revision 1.3.1.1 84/07/10 14:18:18 donn
* I'm taking this branch off the trunk -- it works but it's not as good as
* the old version would be if it worked right.
* Revision 1.5 84/07/09 22:28:50 donn
* Added fix to buffpower() to prevent it chasing after huge exponents.
* Revision 1.4 84/07/09 20:13:59 donn
* Replaced buffpower() routine with a new one that generates trees which can
* be handled by CSE later on.
* Revision 1.3 84/05/04 21:02:07 donn
* Added fix for a bug in buffpower() that caused func(x)**2 to turn into
* func(x) * func(x). This bug had already been fixed in putpower()...
* Revision 1.2 84/03/23 22:47:21 donn
* The subroutine argument temporary fixes from Bob Corbett didn't take into
* account the fact that the code generator collects all the assignments to
* temporaries at the start of a statement -- hence the temporaries need to
* be initialized once per statement instead of once per call.
* Information buffered for each slot type
* slot type expptr integer pointer
* CMGOTO expr num labellist*
* ASGOTO expr - labellist*
* Note [1]: the nullslot field is a pointer to a fake slot which is
* at the end of the slots which may be replaced by this slot. In
* other words, it looks like this:
* slot > ordinary IF, GOTO, LABEL slots which implement the DO
* turns off optimization option
* initializes the code buffer for optimization
for (sp
= firstslot
; sp
; sp
= sp
->next
)
firstslot
= lastslot
= NULL
;
* flushes the code buffer
LOCAL
int alreadycalled
= 0;
if (alreadycalled
) return; /* to prevent recursive call during errors */
for (sp
= firstslot
; sp
; sp
= sp
->next
)
if(sp
->ctlinfo
) free ( (charptr
) sp
->ctlinfo
);
firstslot
= lastslot
= NULL
;
* puts out code for the given slot (from the code buffer)
putif(sp
->expr
, sp
->label
);
putcmgo(sp
->expr
, sp
->label
, sp
->ctlinfo
);
putexpr (call1 (TYSUBR
, "s_stop", sp
->expr
));
putexpr (call1 (TYSUBR
, "s_paus", sp
->expr
));
intrconv(sp
->expr
->headblock
.vtype
, mkaddcon(sp
->label
)));
#define LM ((struct Labelblock * *)sp->ctlinfo)[0]->labelno
#define LZ ((struct Labelblock * *)sp->ctlinfo)[1]->labelno
#define LP ((struct Labelblock * *)sp->ctlinfo)[2]->labelno
prarif(sp
->expr
, LM
, LZ
, LP
);
putbranch((Addrp
) sp
->expr
);
putforce(TYINT
, sp
->expr
);
templist
= mkchain (sp
->expr
,templist
);
badthing("SKtype", "putopt", sp
->type
);
* Recycle argument temporaries here. This must get done on a
* statement-by-statement basis because the code generator
* makes side effects happen at the start of a statement.
argtemplist
= hookup(argtemplist
, activearglist
);
* copies one element of the control stack
LOCAL
struct Ctlframe
*cpframe(p
)
static int size
= sizeof (struct Ctlframe
);
* copies an array of labelblock pointers
LOCAL
struct Labelblock
**cplabarr(n
,arr
)
struct Labelblock
*arr
[];
struct Labelblock
**newarr
;
newarr
= (struct Labelblock
**) ckalloc (n
* sizeof (char *));
newarr
[i
] = ALLOC (Labelblock
);
out
= (char *) newarr
[i
];
j
= sizeof (struct Labelblock
);
* creates a new slot in the code buffer
lastslot
= lastslot
->next
= sp
;
firstslot
= lastslot
= sp
;
* removes (but not deletes) the specified slot from the code buffer
sl
->next
->prev
= sl
->prev
;
sl
->prev
->next
= sl
->next
;
sl
->next
= sl
->prev
= NULL
;
* inserts slot s1 before existing slot s2 in the code buffer;
* appends to end of list if s2 is NULL.
* deletes the specified slot from the code buffer
free ((charptr
) sl
->ctlinfo
);
* inserts a slot before the specified slot; if given NULL, it is
* inserted at the end of the buffer
Slotp
optinsert (type
,p
,l
,c
,currslot
)
lastslot
= currslot
->prev
;
new = optbuff (type
,p
,l
,c
);
new->lineno
= -1; /* who knows what the line number should be ??!! */
* buffers the FRTEMP slots which have been waiting
for (ht
= holdtemps
; ht
; ht
= ht
->nextp
)
/* this slot actually belongs to some previous source line */
sp
->lineno
= sp
->lineno
- 1;
sp
->expr
= (expptr
) ht
->datap
;
* puts the given information into a slot at the end of the code buffer
Slotp
optbuff (type
,p
,l
,c
)
fprintf (diagfile
,"-----optbuff-----"); showslottype (type
);
showexpr (p
,0); fprintf (diagfile
,"\n");
sp
->ctlinfo
= (int*) cplabarr (l
, (struct Labelblock
**) c
);
sp
->ctlinfo
= (int*) cplabarr (3, (struct Labelblock
**) c
);
sp
->ctlinfo
= (int*) cpframe ((struct Ctlframe
*) c
);
* expands the given expression, if possible (e.g., concat, min, max, etc.);
* also frees temporaries when they are indicated as being the last use
res = res->exprblock.rightp = mkexpr (OPCOMMA, z, newtemp)
expptr
buffmnmx(), buffpower(), buffcat();
switch (p
->exprblock
.opcode
)
case OPASSIGN
: /* handle a = b // c */
if (p
->exprblock
.vtype
!= TYCHAR
)
q
->exprblock
.opcode
== OPCONCAT
))
t
= (Addrp
) expand(p
->exprblock
.leftp
);
frexpr(p
->exprblock
.vleng
);
t
= mktemp (TYCHAR
, ICON(lencat(p
)));
q
= (expptr
) cpexpr (p
->exprblock
.vleng
);
p
= (tagptr
) buffcat (t
, p
);
frexpr (p
->headblock
.vleng
);
p
= (tagptr
) buffmnmx (p
);
p
= (tagptr
) buffpower (p
);
expand (p
->exprblock
.leftp
);
expand (p
->exprblock
.rightp
);
for (t
= p
->listblock
.listp
; t
; t
= t
->nextp
)
t
->datap
= (tagptr
) expand (t
->datap
);
p
->addrblock
.memoffset
= expand( p
->addrblock
.memoffset
);
* local version of routine putcat in putpcc.c, called by expand
LOCAL expptr
buffcat(lhs
, rhs
)
lp
= (Addrp
) mkaltmpn(n
, TYLENG
, PNULL
);
cp
= (Addrp
) mkaltmpn(n
, TYADDR
, PNULL
);
ep
= buffct1(rhs
, lp
, cp
, &n
);
call4(TYSUBR
, "s_cat", lhs
, cp
, lp
, mkconv(TYLONG
, ICON(n
))));
* local version of routine putct1 in putpcc.c, called by expand
LOCAL expptr
buffct1(q
, lp
, cp
, ip
)
if(q
->tag
==TEXPR
&& q
->exprblock
.opcode
==OPCONCAT
)
eleft
= buffct1(q
->exprblock
.leftp
, lp
, cp
, ip
);
eright
= buffct1(q
->exprblock
.rightp
, lp
, cp
, ip
);
frexpr(q
->exprblock
.vleng
);
cp1
= (Addrp
) cpexpr(cp
);
cp1
->memoffset
= mkexpr(OPPLUS
, cp1
->memoffset
, ICON(i
*SZADDR
));
lp1
= (Addrp
) cpexpr(lp
);
lp1
->memoffset
= mkexpr(OPPLUS
, lp1
->memoffset
, ICON(i
*SZLENG
));
eleft
= mkexpr(OPASSIGN
, cp1
, addrof(expand(cpexpr(q
))));
eright
= mkexpr(OPASSIGN
, lp1
, cpexpr(q
->headblock
.vleng
));
return (mkexpr(OPCOMMA
, eleft
, eright
));
* local version of routine putmnmx in putpcc.c, called by expand
badtag("buffmnmx", p
->tag
);
type
= p
->exprblock
.vtype
;
op
= (p
->exprblock
.opcode
==OPMIN
? OPLT
: OPGT
);
qp
= expand(p
->exprblock
.leftp
);
badtag("buffmnmx list", qp
->tag
);
p0
= qp
->listblock
.listp
;
sp
= mktemp(type
, PNULL
);
tp
= mktemp(type
, PNULL
);
qp
= mkexpr(OPCOLON
, cpexpr(tp
), cpexpr(sp
));
qp
= mkexpr(OPQUEST
, mkexpr(op
, cpexpr(tp
),cpexpr(sp
)), qp
);
newtemp
= mktemp (type
,PNULL
);
result
= res
= mkexpr (OPCOMMA
,
mkexpr( OPASSIGN
, cpexpr(sp
), p0
->datap
), cpexpr(newtemp
));
for(p1
= p0
->nextp
; p1
; p1
= p1
->nextp
)
APPEND (mkexpr( OPASSIGN
, cpexpr(tp
), p1
->datap
));
APPEND (mkexpr (OPASSIGN
, cpexpr(sp
), cpexpr(qp
)) );
APPEND (mkexpr (OPASSIGN
, cpexpr(newtemp
), qp
));
* Called by expand() to eliminate exponentiations to integer constants.
LOCAL expptr
buffpower( p
)
expptr storetemp
= ENULL
;
if ( ! ISICON( p
->exprblock
.rightp
) )
fatal( "buffpower: bad non-integer exponent" );
base
= expand(p
->exprblock
.leftp
);
exp
= p
->exprblock
.rightp
->constblock
.constant
.ci
;
fatal( "buffpower: bad exponent less than 2" );
* Let's be reasonable, here... Let putpower() do the job.
p
->exprblock
.leftp
= base
;
* If the base is not a simple variable, evaluate it and copy the
* result into a temporary.
if ( ! (base
->tag
== TADDR
&& ISCONST( base
->addrblock
.memoffset
)) ) {
newtemp
= mktemp( base
->headblock
.vtype
, PNULL
);
storetemp
= mkexpr( OPASSIGN
,
cpexpr( (expptr
) newtemp
),
result
= powtree( base
, exp
);
if ( storetemp
!= ENULL
)
result
= mkexpr( OPCOMMA
, storetemp
, result
);
* powtree( base, exp ) -- Create a tree of multiplications which computes
* base ** exp. The tree is built so that CSE will compact it if
* possible. The routine works by creating subtrees that compute
* exponents which are powers of two, then multiplying these
* together to get the result; this gives a log2( exp ) tree depth
* and lots of subexpressions which can be eliminated.
LOCAL expptr
powtree( base
, exp
)
register expptr r
= ENULL
, r1
;
for ( i
= 0; exp
; ++i
, exp
>>= 1 )
r
= (expptr
) cpexpr( base
);
r1
= powtree( base
, 1 << (i
- 1) );
r1
= mkexpr( OPSTAR
, r1
, cpexpr( r1
) );
r
= (r
? mkexpr( OPSTAR
, r1
, r
) : r1
);