util/ego/sr/sr_reduce.c

   1 /* $Id: sr_reduce.c,v 1.11 1994/06/24 10:32:27 ceriel Exp $ */
   2 /*
   3  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   4  * See the copyright notice in the ACK home directory, in the file "Copyright".
   5  */
   6 /* S T R E N G T H   R E D U C T I O N
   7  *
   8  * S R _ R E D U C E . C
   9  *
  10  */
  11
  12
  13 #include <em_pseu.h>
  14 #include <em_reg.h>
  15 #include <em_mes.h>
  16 #include <em_mnem.h>
  17 #include <em_spec.h>
  18 #include "../share/types.h"
  19 #include "sr.h"
  20 #include "../share/debug.h"
  21 #include "../share/alloc.h"
  22 #include "../share/def.h"
  23 #include "../share/global.h"
  24 #include "../share/aux.h"
  25 #include "sr_aux.h"
  26 #include "../share/lset.h"
  27 #include "sr_xform.h"
  28 #include "sr_reduce.h"
  29 #include "sr_expr.h"
  30
  31
  32
  33 STATIC lset avail;
  34 /* If an expression such as "iv * const" or "A[iv]" is
  35  * used more than once in a loop, we only use one temporary
  36  * local for it and reuse this local each time.
  37  * After the first occurrence, the expression is said to
  38  * be available.
  39  */
  40
  41 STATIC int regtyp(code)
  42         code_p code;
  43 {
  44         switch(code->co_instr) {
  45                 case op_mli:
  46                 case op_mlu:
  47                 case op_sli:
  48                 case op_slu:
  49                         return reg_any;
  50                 default:
  51                         return reg_pointer;
  52         }
  53         /* NOTREACHED */
  54 }
  55
  56
  57 STATIC gen_regmes(tmp,score,code,p)
  58         offset tmp;
  59         int score;
  60         code_p code;
  61         proc_p p;
  62 {
  63         /* generate a register message for the temporary variable and
  64          * insert it at the start of the procedure.
  65          */
  66
  67         line_p l,pro;
  68
  69         l = reg_mes(tmp,code->co_tmpsize,regtyp(code),score);
  70         pro = p->p_start->b_start; /* every proc. begins with a PRO pseudo */
  71         l->l_next = pro->l_next;
  72         PREV(l->l_next) = l;
  73         pro->l_next = l;
  74         PREV(l) = pro;
  75 }
  76
  77
  78 STATIC line_p newcode(code,tmp)
  79         code_p code;
  80         offset tmp;
  81 {
  82         /* Construct the EM code that will replace the reducible code,
  83          * e.g.   iv * c   ->   tmp
  84          *        a[iv]    ->   *tmp
  85          */
  86
  87         line_p l;
  88
  89         switch(code->co_instr) {
  90                 case op_mli:
  91                 case op_mlu:
  92                 case op_sli:
  93                 case op_slu:
  94                         /* new code is just a LOL tmp */
  95                         l = int_line(tmp);
  96                         l->l_instr = op_lol;
  97                         break;
  98                 case op_aar:
  99                         /* New code is a LOAD tmp, where tmp is a
 100                          * pointer variable, so the actual EM code
 101                          * depends on the pointer size.
 102                          */
 103                         l = move_pointer(tmp,LOAD);
 104                         break;
 105                 case op_lar:
 106                         /* New code is a load-indirect */
 107                         l = int_line(tmp);
 108                         l->l_instr = op_lil;
 109                         break;
 110                 case op_sar:
 111                         /* New code is a store-indirect */
 112                         l = int_line(tmp);
 113                         l->l_instr = op_sil;
 114                         break;
 115                 default:
 116                         assert(FALSE);
 117         }
 118         return l;
 119 }
 120
 121
 122
 123 STATIC replcode(code,text)
 124         code_p code;
 125         line_p text;
 126 {
 127         /* Replace old code (extending from code->co_lfirst to
 128          * code->co_llast) by new code (headed by 'text').
 129          */
 130
 131         line_p l, l1, l2;
 132
 133         for (l = text; l->l_next != (line_p) 0; l = l->l_next);
 134         /* 'l' now points to last instruction of text */
 135         l1 = PREV(code->co_lfirst); /* instruction just before old code */
 136         l2 = code->co_llast->l_next; /* instruction just behind old code */
 137         if (l1 == (line_p) 0) {
 138                 code->co_block->b_start = text;
 139                 PREV(text) = (line_p) 0;
 140         } else {
 141                 l1->l_next = text;
 142                 PREV(text) = l1;
 143         }
 144         if (l2 != (line_p) 0) {
 145                 PREV(l2) = l;
 146         }
 147         l->l_next = l2;
 148         code->co_llast->l_next = (line_p) 0;
 149         /* Note that the old code is still accessible via code->co_lfirst */
 150 }
 151
 152 STATIC line_p add_code(pl, l)
 153         line_p pl, l;
 154 {
 155         if (! pl) {
 156                 PREV(l) = 0;
 157         }
 158         else {
 159                 line_p n = pl->l_next;
 160
 161                 DLINK(pl, l);
 162                 if (n) {
 163                         while (l->l_next) l = l->l_next;
 164                         DLINK(l, n);
 165                 }
 166                 l = pl;
 167         }
 168         return l;
 169 }
 170
 171
 172
 173 STATIC init_code(code,tmp)
 174         code_p code;
 175         offset tmp;
 176 {
 177         /* Generate code to set up the temporary local.
 178          * For multiplication, its initial value is const*iv_expr,
 179          * for array operations it is &a[iv_expr] (where iv_expr is
 180          * an expression that is a linear function of the induc. var.
 181          * This code is inserted immediately before the loop entry.
 182          * As the initializing code looks very much like the
 183          * reduced code, we reuse that (old) code.
 184          */
 185
 186         line_p l, *p;
 187
 188         l = code->co_llast; /* the mli, lar etc. instruction */
 189         switch(INSTR(l)) {
 190                 case op_mli:
 191                 case op_mlu:
 192                         /* reduced code is: iv_expr * lc  (or lc * iv_expr)
 193                          * init_code is:    tmp = iv_expr * lc  (or lc*iv_expr)
 194                          * So we just insert a 'STL tmp'.
 195                          */
 196                         l->l_next = int_line(tmp);
 197                         l->l_next->l_instr = op_stl;
 198                         break;
 199                 case op_sli:
 200                 case op_slu:
 201                         /* reduced code is: iv_expr << lc
 202                          * init_code is:    tmp = iv_expr << lc
 203                          * So we just insert a 'STL tmp'.
 204                          */
 205                         l->l_next = int_line(tmp);
 206                         l->l_next->l_instr = op_stl;
 207                         break;
 208                 case op_lar:
 209                 case op_sar:
 210                         /* reduced code is: ...= A[iv_expr] resp.
 211                          *                  A[iv]_expr = ..
 212                          * init_code is: tmp = &A[iv_expr].
 213                          * So just change the lar or sar into a aar ...
 214                          */
 215                         l->l_instr = (byte) op_aar;
 216                         /* ... and fall through !! */
 217                 case op_aar:
 218                         /* append code to store a pointer in temp. local */
 219                         l->l_next = move_pointer(tmp,STORE);
 220                         break;
 221                 default:
 222                         assert(FALSE); /* non-reducible instruction */
 223         }
 224         PREV(l->l_next) = l;
 225         /* Now insert the code at the end of the header block */
 226         p = &code->co_loop->LP_INSTR;
 227         if (*p == (line_p) 0 || (PREV((*p)) == 0 && INSTR((*p)) == op_bra)) {
 228                 /* LP_INSTR points to last instruction of header block,
 229                  * so if it is 0, the header block is empty yet.
 230                  */
 231                 code->co_loop->LP_HEADER->b_start =
 232                   add_code(code->co_loop->LP_HEADER->b_start, code->co_lfirst);
 233         } else if (INSTR((*p)) == op_bra) {
 234                 add_code(PREV((*p)), code->co_lfirst);
 235         }
 236         else    add_code(*p, code->co_lfirst);
 237         while (l->l_next) l = l->l_next;
 238         *p = l; /* new last instruction */
 239 }
 240
 241 STATIC incr_code(code,tmp)
 242         code_p  code;
 243         offset  tmp;
 244 {
 245         /* Generate code to increment the temporary local variable.
 246          * The variable is incremented by
 247          *  1) multiply -->   step value of iv * loop constant
 248          *  2) array    -->   step value of iv * element size
 249          * This value can be determined statically.
 250          * If the induction variable is used in a linear
 251          * expression in which its sign is negative
 252          * (such as in: "5-(6-(-iv))" ), this value is negated.
 253          * The generated code looks like:
 254          *  LOL tmp ; LOC incr ; ADI ws ; STL tmp
 255          * For pointer-increments we generate a "ADP c", rather than
 256          * a "LOC c; ADS ws".
 257          * This code is put just after the code that increments
 258          * the induction variable.
 259          */
 260
 261         line_p load_tmp, loc, add, store_tmp, l;
 262
 263         add = newline(OPSHORT);
 264         SHORT(add) = ws;  /* the add instruction, can be ADI,ADU or ADS */
 265         switch(code->co_instr) {
 266                 case op_mli:
 267                 case op_mlu:
 268                         loc = int_line(
 269                                   code->co_sign *
 270                                   off_set(code->c_o.co_loadlc) *
 271                                   code->co_iv->iv_step);
 272                         loc->l_instr = op_loc;
 273                         add->l_instr = op_adi;
 274                         load_tmp = int_line(tmp);
 275                         load_tmp->l_instr = op_lol;
 276                         store_tmp = int_line(tmp);
 277                         store_tmp->l_instr = op_stl;
 278                         break;
 279                 case op_sli:
 280                 case op_slu:
 281                         loc = int_line(
 282                                   code->co_sign *
 283                                   code->co_iv->iv_step *
 284                                   (1 << off_set(code->c_o.co_loadlc)));
 285                         loc->l_instr = op_loc;
 286                         add->l_instr = op_adi;
 287                         load_tmp = int_line(tmp);
 288                         load_tmp->l_instr = op_lol;
 289                         store_tmp = int_line(tmp);
 290                         store_tmp->l_instr = op_stl;
 291                         break;
 292                 case op_lar:
 293                 case op_sar:
 294                 case op_aar:
 295                         loc = (line_p) 0;
 296                         add = int_line(
 297                                 code->co_sign *
 298                                 code->co_iv->iv_step *
 299                                 elemsize(code->c_o.co_desc));
 300                         add->l_instr = op_adp;
 301                         load_tmp = move_pointer(tmp,LOAD);
 302                         store_tmp = move_pointer(tmp,STORE);
 303                         break;
 304                 default:
 305                         assert(FALSE);
 306         }
 307         /* Now we've got pieces of code to load the temp. local,
 308          * load the constant, add the two and store the result in
 309          * the local. This code will be put just after the code that
 310          * increments the induction variable.
 311          */
 312         if (loc != (line_p) 0) concatenate(load_tmp,loc);
 313         concatenate(load_tmp,add);
 314         concatenate(load_tmp,store_tmp);
 315         /* Now load_tmp points to a list of EM instructions */
 316         l = code->co_iv->iv_incr;
 317         if (l->l_next != (line_p) 0) {
 318                 DLINK(store_tmp,l->l_next);
 319         }
 320         DLINK(l,load_tmp); /* doubly link them */
 321 }
 322
 323
 324 STATIC remcode(c)
 325         code_p c;
 326 {
 327         line_p l, next;
 328
 329         for (l = c->co_lfirst; l != (line_p) 0; l = next) {
 330                 next = l->l_next;
 331                 oldline(l);
 332         }
 333         oldcinfo(c);
 334 }
 335
 336
 337 STATIC bool same_address(l1,l2,vars)
 338         line_p l1,l2;
 339         lset   vars;
 340 {
 341         /* See if l1 and l2 load the same address */
 342
 343         if (INSTR(l1) != INSTR(l2)) return FALSE;
 344         switch(INSTR(l1)) {
 345                 case op_lae:
 346                         return OBJ(l1) == OBJ(l2);
 347                 case op_lal:
 348                         return off_set(l1) == off_set(l2);
 349                 case op_lol:
 350                         return ps == ws &&
 351                           off_set(l1) == off_set(l2) &&
 352                           is_loopconst(l1,vars);
 353                 case op_ldl:
 354                         return ps == 2*ws &&
 355                           off_set(l1) == off_set(l2) &&
 356                           is_loopconst(l1,vars);
 357                 default:
 358                         return FALSE;
 359         }
 360 }
 361
 362
 363 STATIC bool same_expr(lb1,le1,lb2,le2)
 364         line_p lb1,le1,lb2,le2;
 365 {
 366         /* See if the code from lb1 to le1 is the same
 367          * expression as the code from lb2 to le2.
 368          */
 369
 370
 371         register line_p l1,l2;
 372
 373         l1 = lb1;
 374         l2 = lb2;
 375         for (;;) {
 376                 if (INSTR(l1) != INSTR(l2)) return FALSE;
 377                 switch(TYPE(l1)) {
 378                         case OPSHORT:
 379                                 if (TYPE(l2) != OPSHORT ||
 380                                     SHORT(l1) != SHORT(l2)) return FALSE;
 381                                 break;
 382                         case OPOFFSET:
 383                                 if (TYPE(l2) != OPOFFSET ||
 384                                     OFFSET(l1) != OFFSET(l2)) return FALSE;
 385                                 break;
 386                         case OPNO:
 387                                 break;
 388                         default:
 389                                 return FALSE;
 390                 }
 391                 if (l1 == le1 ) return l2 == le2;
 392                 if (l2 == le2) return FALSE;
 393                 l1 = l1->l_next;
 394                 l2 = l2->l_next;
 395         }
 396 }
 397
 398 STATIC bool same_code(c1,c2,vars)
 399         code_p c1,c2;
 400         lset   vars;
 401 {
 402         /* See if c1 and c2 compute the same expression. Two array
 403          * references can be the same even if one is e.g a fetch
 404          * and the other a store.
 405          */
 406
 407         switch(c1->co_instr) {
 408                 case op_mli:
 409                 case op_mlu:
 410                 case op_sli:
 411                 case op_slu:
 412                         return c1->co_instr == c2->co_instr &&
 413                         off_set(c1->c_o.co_loadlc) ==
 414                         off_set(c2->c_o.co_loadlc) &&
 415                         same_expr(c1->co_ivexpr,c1->co_endexpr,
 416                                   c2->co_ivexpr,c2->co_endexpr);
 417                 case op_aar:
 418                 case op_lar:
 419                 case op_sar:
 420                         return ( c2->co_instr == op_aar ||
 421                                  c2->co_instr == op_lar ||
 422                                  c2->co_instr == op_sar) &&
 423                         same_expr(c1->co_ivexpr,c1->co_endexpr,
 424                                   c2->co_ivexpr,c2->co_endexpr) &&
 425                         same_address(c1->c_o.co_desc,c2->c_o.co_desc,vars) &&
 426                         same_address(c1->co_lfirst,c2->co_lfirst,vars);
 427                 default:
 428                         assert(FALSE);
 429         }
 430         /* NOTREACHED */
 431 }
 432
 433
 434 STATIC code_p available(c,vars)
 435         code_p c;
 436         lset   vars;
 437 {
 438         /* See if the code is already available.
 439          * If so, return a pointer to the first occurrence
 440          * of the code.
 441          */
 442
 443         Lindex i;
 444         code_p cp;
 445
 446         for (i = Lfirst(avail); i != (Lindex) 0; i = Lnext(i,avail)) {
 447                 cp = (code_p) Lelem(i);
 448                 if (same_code(c,cp,vars)) {
 449                         return cp;
 450                 }
 451         }
 452         return (code_p) 0;
 453 }
 454
 455 STATIC fix_header(lp)
 456         loop_p lp;
 457 {
 458         /* Check if a header block was added, and if so, add a branch to
 459          * the entry block.
 460          * If it was added, it was added to the end of the procedure, so
 461          * move the END pseudo.
 462          */
 463         bblock_p b = curproc->p_start;
 464
 465         if (lp->LP_HEADER->b_next == 0) {
 466                 line_p l = last_instr(lp->LP_HEADER);
 467                 line_p e;
 468
 469                 assert(l != 0);
 470                 if (INSTR(l) != op_bra) {
 471                         line_p j = newline(OPINSTRLAB);
 472
 473                         assert(INSTR(lp->lp_entry->b_start) == op_lab);
 474                         INSTRLAB(j) = INSTRLAB(lp->lp_entry->b_start);
 475                         j->l_instr = op_bra;
 476                         DLINK(l, j);
 477                         l = j;
 478                 }
 479
 480                 while (b->b_next != lp->LP_HEADER) b = b->b_next;
 481                 e = last_instr(b);
 482                 assert(INSTR(e) == ps_end);
 483                 assert(PREV(e) != 0);
 484                 PREV(e)->l_next = 0;
 485                 DLINK(l, e);
 486         }
 487 }
 488
 489 STATIC reduce(code,vars)
 490         code_p code;
 491         lset   vars;
 492 {
 493         /* Perform the actual transformations. The code on the left
 494          * gets transformed into the code on the right. Note that
 495          * each piece of code is assigned a name, that will be
 496          * used to describe the whole process.
 497          *
 498          *                                      t = iv * 118;   (init_code)
 499          *      do              --->            do
 500          *         .. iv * 118 ..                  .. t ..      (new_code)
 501          *         iv++;                           iv++;
 502          *                                         t += 118;    (incr_code)
 503          *      od                              od
 504          */
 505
 506         offset tmp;
 507         code_p ac;
 508
 509         OUTTRACE("succeeded!!",0);
 510         if ((ac = available(code,vars)) != (code_p) 0) {
 511                 /* The expression is already available, so we
 512                  * don't have to generate a new temporary local for it.
 513                  */
 514                 OUTTRACE("expression was already available",0);
 515                 replcode(code,newcode(code,ac->co_temp));
 516                 remcode(code);
 517         } else {
 518                 make_header(code->co_loop);
 519                 /* make sure there's a header block */
 520                 tmp = tmplocal(curproc,(offset) code->co_tmpsize);
 521                 code->co_temp = tmp;
 522                 /* create a new local variable in the stack frame
 523                  * of current proc.
 524                  */
 525                 gen_regmes(tmp,3,code,curproc); /* generate register message */
 526                 /* score is set to 3, as TMP is used at least 3 times */
 527                 replcode(code,newcode(code,tmp));
 528                 OUTTRACE("replaced old code by new code",0);
 529                 /* Construct the EM-code that will replace the reducible code
 530                  * and replace the old code by the new code.
 531                  */
 532                 init_code(code,tmp);
 533                 OUTTRACE("emitted initializing code",0);
 534                 /* Emit code to initialize the temporary local. This code is
 535                  * put in the loop header block.
 536                  */
 537                 incr_code(code,tmp); /* emit code to increment temp. local */
 538                 OUTTRACE("emitted increment code",0);
 539                 Ladd(code,&avail);
 540                 fix_header(code->co_loop);
 541         }
 542 }
 543
 544
 545
 546 STATIC try_multiply(lp,ivs,vars,b,mul)
 547         loop_p   lp;
 548         lset     ivs,vars;
 549         bblock_p b;
 550         line_p   mul;
 551 {
 552         /* See if we can reduce the strength of the multiply
 553          * instruction. If so, then set up the global common
 554          * data structure 'c' (containing information about the
 555          * code to be reduced) and call 'reduce'.
 556          */
 557
 558         line_p l2,lbegin;
 559         iv_p   iv;
 560         code_p c;
 561         int    sign;
 562
 563         VL(mul);
 564         OUTTRACE("trying multiply instruction on line %d",linecount);
 565         if (ovfl_harmful && !IS_STRONG(b)) return;
 566         /* If b is not a strong block, optimization may
 567          * introduce an overflow error in the initializing code.
 568          */
 569
 570         l2 = PREV(mul); /* Instruction before the multiply */
 571         if ( (is_ivexpr(l2,ivs,vars,&lbegin,&iv,&sign)) &&
 572                 is_const(PREV(lbegin)) ) {
 573                         /* recognized expression "const * iv_expr" */
 574                         c = newcinfo();
 575                         c->c_o.co_loadlc = PREV(l2);
 576                         c->co_endexpr = l2;
 577                         c->co_lfirst = PREV(lbegin);
 578         } else {
 579                 if (is_const(l2) &&
 580                         (is_ivexpr(PREV(l2),ivs,vars,&lbegin,&iv,&sign))) {
 581                                 /* recognized "iv * const " */
 582                                 c = newcinfo();
 583                                 c->c_o.co_loadlc = l2;
 584                                 c->co_endexpr = PREV(l2);
 585                                 c->co_lfirst = lbegin;
 586                 } else {
 587                         OUTTRACE("failed",0);
 588                         return;
 589                 }
 590         }
 591         /* common part for both patterns */
 592         c->co_iv = iv;
 593         c->co_loop = lp;
 594         c->co_block = b;
 595         c->co_llast = mul;
 596         c->co_ivexpr = lbegin;
 597         c->co_sign = sign;
 598         c->co_tmpsize = ws; /* temp. local is a word */
 599         c->co_instr = INSTR(mul);
 600         OUTVERBOSE("sr: multiply in proc %d loop %d",
 601                 curproc->p_id, lp->lp_id);
 602         Ssr++;
 603         reduce(c,vars);
 604 }
 605
 606
 607
 608 STATIC try_leftshift(lp,ivs,vars,b,shft)
 609         loop_p   lp;
 610         lset     ivs,vars;
 611         bblock_p b;
 612         line_p   shft;
 613 {
 614         /* See if we can reduce the strength of the leftshift
 615          * instruction. If so, then set up the global common
 616          * data structure 'c' (containing information about the
 617          * code to be reduced) and call 'reduce'.
 618          */
 619
 620         line_p l2,lbegin;
 621         iv_p   iv;
 622         code_p c;
 623         int    sign;
 624
 625         VL(shft);
 626         OUTTRACE("trying leftshift instruction on line %d",linecount);
 627         if (ovfl_harmful && !IS_STRONG(b)) return;
 628         /* If b is not a strong block, optimization may
 629          * introduce an overflow error in the initializing code.
 630          */
 631
 632         l2 = PREV(shft); /* Instruction before the shift */
 633         if (is_const(l2) && off_set(l2) > sli_threshold &&
 634                 (is_ivexpr(PREV(l2),ivs,vars,&lbegin,&iv,&sign))) {
 635                         /* recognized "iv << const " */
 636                         c = newcinfo();
 637                         c->c_o.co_loadlc = l2;
 638                         c->co_endexpr = PREV(l2);
 639                         c->co_lfirst = lbegin;
 640         } else {
 641                 OUTTRACE("failed",0);
 642                 return;
 643         }
 644         c->co_iv = iv;
 645         c->co_loop = lp;
 646         c->co_block = b;
 647         c->co_llast = shft;
 648         c->co_ivexpr = lbegin;
 649         c->co_sign = sign;
 650         c->co_tmpsize = ws; /* temp. local is a word */
 651         c->co_instr = INSTR(shft);
 652         OUTVERBOSE("sr: leftshift in proc %d loop %d",
 653                 curproc->p_id, lp->lp_id);
 654         Ssr++;
 655         reduce(c,vars);
 656 }
 657
 658
 659 STATIC try_array(lp,ivs,vars,b,arr)
 660         loop_p   lp;
 661         lset     ivs,vars;
 662         bblock_p b;
 663         line_p   arr;
 664 {
 665         /* See if we can reduce the strength of the array reference
 666          * instruction 'arr'.
 667          */
 668
 669         line_p l2,l3,lbegin;
 670         iv_p   iv;
 671         code_p c;
 672         int    sign;
 673
 674         /* Try to recognize the pattern:
 675          *      LOAD ADDRES OF A
 676          *      LOAD IV
 677          *      LOAD ADDRESS OF DESCRIPTOR
 678          */
 679         VL(arr);
 680         OUTTRACE("trying array instruction on line %d",linecount);
 681         if (arrbound_harmful && !IS_STRONG(b)) return;
 682         /* If b is not a strong block, optimization may
 683          * introduce an array bound error in the initializing code.
 684          */
 685         l2 = PREV(arr);
 686         if (is_caddress(l2,vars) &&
 687                 (INSTR(arr) == op_aar || elemsize(l2) == ws) &&
 688                 (is_ivexpr(PREV(l2),ivs,vars,&lbegin,&iv,&sign)) ) {
 689                 l3 = PREV(lbegin);
 690                 if (is_caddress(l3,vars)) {
 691                         c = newcinfo();
 692                         c->co_iv = iv;
 693                         c->co_loop = lp;
 694                         c->co_block = b;
 695                         c->co_lfirst = l3;
 696                         c->co_llast = arr;
 697                         c->co_ivexpr = lbegin;
 698                         c->co_endexpr = PREV(l2);
 699                         c->co_sign = sign;
 700                         c->co_tmpsize = ps; /* temp. local is pointer */
 701                         c->co_instr = INSTR(arr);
 702                         c->c_o.co_desc = l2;
 703                         OUTVERBOSE("sr: array in proc %d loop %d",
 704                                 curproc->p_id,lp->lp_id);
 705                         Ssr++;
 706                         reduce(c,vars);
 707                 }
 708         }
 709 }
 710
 711
 712
 713 STATIC clean_avail()
 714 {
 715         Lindex i;
 716
 717         for (i = Lfirst(avail); i != (Lindex) 0; i = Lnext(i,avail)) {
 718                 oldcinfo(Lelem(i));
 719         }
 720         Ldeleteset(avail);
 721 }
 722
 723
 724
 725 strength_reduction(lp,ivs,vars)
 726         loop_p lp;      /* description of the loop */
 727         lset    ivs;    /* set of induction variables of the loop */
 728         lset    vars;   /* set of local variables changed in loop */
 729 {
 730         /* Find all expensive instructions (leftshift, multiply, array) and see
 731          * if they can be reduced. We branch to several instruction-specific
 732          * routines (try_...) that check if reduction is possible,
 733          * and that set up a common data structure (code_info).
 734          * The actual transformations are done by 'reduce', that is
 735          * essentially instruction-independend.
 736          */
 737
 738         bblock_p b;
 739         line_p   l, next;
 740         Lindex   i;
 741
 742         avail = Lempty_set();
 743         for (i = Lfirst(lp->LP_BLOCKS); i != (Lindex) 0;
 744                         i = Lnext(i,lp->LP_BLOCKS)) {
 745                 b = (bblock_p) Lelem(i);
 746                 for (l = b->b_start; l != (line_p) 0; l = next) {
 747                         next = l->l_next;
 748                         if (TYPE(l) == OPSHORT && SHORT(l) == ws) {
 749                                 switch(INSTR(l)) {
 750                                         case op_sli:
 751                                         case op_slu:
 752                                                 try_leftshift(lp,ivs,vars,b,l);
 753                                                 break;
 754                                         case op_mlu:
 755                                         case op_mli:
 756                                                 try_multiply(lp,ivs,vars,b,l);
 757                                                 break;
 758                                         case op_lar:
 759                                         case op_sar:
 760                                         case op_aar:
 761                                                 try_array(lp,ivs,vars,b,l);
 762                                                 break;
 763                                 }
 764                         }
 765                 }
 766         }
 767         clean_avail();
 768 }