123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240 |
- /* $Id$ */
- /*
- * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
- * See the copyright notice in the ACK home directory, in the file "Copyright".
- */
- /* S T R E N G T H R E D U C T I O N */
- #include <stdlib.h>
- #include <stdio.h>
- #include "../share/types.h"
- #include "sr.h"
- #include "../share/debug.h"
- #include "../share/global.h"
- #include "../share/files.h"
- #include "../share/get.h"
- #include "../share/put.h"
- #include "../share/lset.h"
- #include "../share/map.h"
- #include "../share/alloc.h"
- #include "../share/go.h"
- #include "../share/aux.h"
- #include "sr_aux.h"
- #include "sr_iv.h"
- /* Strength reduction tries to change expensive operators occurring
- * in a loop into cheaper operators. The expensive operators considered
- * are multiplication, left-shift and array referencing.
- * The transformations can be expressed in C as:
- *
- * [1]: for (i = e1; i <= e2; i++)
- * print(118*i);
- * becomes:
- * for (i = e1, t = 118*e1; i <= e2; i++, t += 118)
- * print(t);
- *
- * [2]: for (i = e1; i <= e2; i++)
- * print(a[i]);
- * becomes:
- * for (i = e1, p = &a[i]; i <= e2; i++, p++)
- * print(*p);
- * The latter optimization is suppressed if array bound checking
- * is required.
- */
- /* Machine and/or language dependent parameters: */
- int ovfl_harmful;
- int arrbound_harmful;
- int sli_threshold;
- int Ssr; /* #optimizations found */
- sr_machinit(f)
- FILE *f;
- {
- /* Read target machine dependent information */
- char s[100];
- for (;;) {
- while(getc(f) != '\n');
- fscanf(f,"%s",s);
- if (strcmp(s,"%%SR") == 0)break;
- }
- fscanf(f,"%d",&ovfl_harmful);
- fscanf(f,"%d",&arrbound_harmful);
- fscanf(f,"%d",&sli_threshold);
- }
- STATIC del_ivs(ivs)
- lset ivs;
- {
- /* Delete the set of iv structs */
- Lindex i;
- for (i = Lfirst(ivs); i != (Lindex) 0; i = Lnext(i,ivs)) {
- oldiv(Lelem(i));
- }
- Ldeleteset(ivs);
- }
- STATIC do_loop(loop)
- loop_p loop;
- {
- lset ivs, vars;
- OUTTRACE("going to process loop %d",loop->lp_id);
- induc_vars(loop,&ivs, &vars);
- /* Build a set of iv_structs, one for every induction
- * variable of the loop, i.e. a variable i that
- * is changed only by i := i + c, where c is a loop constant.
- * Also detects variables that are changed (including induction
- * variables!).
- */
- OUTTRACE("loop has %d induction variables",Lnrelems(ivs));
- if (Lnrelems(ivs) > 0) {
- strength_reduction(loop,ivs,vars);
- /* Perform strength reduction. Reduce:
- * iv * c to addition
- * a[iv] to indirection (*p)
- * (unless array bound checking is required)
- */
- }
- del_ivs(ivs);
- Ldeleteset(vars);
- }
- STATIC loopblocks(p)
- proc_p p;
- {
- /* Compute the LP_BLOCKS sets for all loops of p */
- register bblock_p b;
- register Lindex i;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- for (i = Lfirst(b->b_loops); i != (Lindex) 0;
- i = Lnext(i,b->b_loops)) {
- Ladd(b,&(((loop_p) Lelem(i))->LP_BLOCKS));
- }
- }
- }
- STATIC opt_proc(p)
- proc_p p;
- {
- /* Optimize all loops of one procedure. We first do all
- * outer loops at the lowest nesting level and proceed
- * in the inwards direction.
- */
- Lindex i;
- loop_p lp,outermost;
- int min_level;
- for (;;) {
- min_level = 1000;
- outermost = 0;
- for (i = Lfirst(p->p_loops); i != (Lindex) 0;
- i = Lnext(i,p->p_loops)) {
- lp = (loop_p) Lelem(i);
- if (!lp->LP_DONE && lp->lp_level < min_level) {
- min_level = lp->lp_level;
- outermost = lp;
- }
- }
- if (! outermost) break;
- do_loop(outermost);
- outermost->LP_DONE = TRUE;
- OUTTRACE("loop %d processed",outermost->lp_id);
- }
- }
- STATIC bblock_p header(lp)
- loop_p lp;
- {
- /* Try to determine the 'header' block of loop lp.
- * If 'e' is the entry block of loop L, then block 'b' is
- * called the header block of L, iff:
- * SUCC(b) = {e} & b dominates e.
- * If lp has no header block, 0 is returned.
- */
- bblock_p x = lp->lp_entry->b_idom;
- if (x != (bblock_p) 0 && Lnrelems(x->b_succ) == 1 &&
- (bblock_p) Lelem(Lfirst(x->b_succ)) == lp->lp_entry) {
- return x;
- }
- return (bblock_p) 0;
- }
- STATIC sr_extproc(p)
- proc_p p;
- {
- /* Allocate the extended data structures for procedure p */
- register loop_p lp;
- register Lindex pi;
- for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
- pi = Lnext(pi,p->p_loops)) {
- lp = (loop_p) Lelem(pi);
- lp->lp_extend = newsrlpx();
- lp->LP_HEADER = header(lp);
- if (lp->LP_HEADER) {
- lp->LP_INSTR = last_instr(lp->LP_HEADER);
- }
- }
- }
- STATIC sr_cleanproc(p)
- proc_p p;
- {
- /* Remove the extended data structures for procedure p */
- register loop_p lp;
- register Lindex pi;
- for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
- pi = Lnext(pi,p->p_loops)) {
- lp = (loop_p) Lelem(pi);
- oldsrlpx(lp->lp_extend);
- }
- }
- sr_optimize(p)
- proc_p p;
- {
- if (IS_ENTERED_WITH_GTO(p)) return;
- sr_extproc(p);
- loopblocks(p);
- opt_proc(p);
- sr_cleanproc(p);
- }
- main(argc,argv)
- int argc;
- char *argv[];
- {
- go(argc,argv,no_action,sr_optimize,sr_machinit,no_action);
- report("strength reductions",Ssr);
- exit(0);
- }
|