sr.c 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240
  1. /* $Id$ */
  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. #include <stdlib.h>
  8. #include <stdio.h>
  9. #include "../share/types.h"
  10. #include "sr.h"
  11. #include "../share/debug.h"
  12. #include "../share/global.h"
  13. #include "../share/files.h"
  14. #include "../share/get.h"
  15. #include "../share/put.h"
  16. #include "../share/lset.h"
  17. #include "../share/map.h"
  18. #include "../share/alloc.h"
  19. #include "../share/go.h"
  20. #include "../share/aux.h"
  21. #include "sr_aux.h"
  22. #include "sr_iv.h"
  23. /* Strength reduction tries to change expensive operators occurring
  24. * in a loop into cheaper operators. The expensive operators considered
  25. * are multiplication, left-shift and array referencing.
  26. * The transformations can be expressed in C as:
  27. *
  28. * [1]: for (i = e1; i <= e2; i++)
  29. * print(118*i);
  30. * becomes:
  31. * for (i = e1, t = 118*e1; i <= e2; i++, t += 118)
  32. * print(t);
  33. *
  34. * [2]: for (i = e1; i <= e2; i++)
  35. * print(a[i]);
  36. * becomes:
  37. * for (i = e1, p = &a[i]; i <= e2; i++, p++)
  38. * print(*p);
  39. * The latter optimization is suppressed if array bound checking
  40. * is required.
  41. */
  42. /* Machine and/or language dependent parameters: */
  43. int ovfl_harmful;
  44. int arrbound_harmful;
  45. int sli_threshold;
  46. int Ssr; /* #optimizations found */
  47. sr_machinit(f)
  48. FILE *f;
  49. {
  50. /* Read target machine dependent information */
  51. char s[100];
  52. for (;;) {
  53. while(getc(f) != '\n');
  54. fscanf(f,"%s",s);
  55. if (strcmp(s,"%%SR") == 0)break;
  56. }
  57. fscanf(f,"%d",&ovfl_harmful);
  58. fscanf(f,"%d",&arrbound_harmful);
  59. fscanf(f,"%d",&sli_threshold);
  60. }
  61. STATIC del_ivs(ivs)
  62. lset ivs;
  63. {
  64. /* Delete the set of iv structs */
  65. Lindex i;
  66. for (i = Lfirst(ivs); i != (Lindex) 0; i = Lnext(i,ivs)) {
  67. oldiv(Lelem(i));
  68. }
  69. Ldeleteset(ivs);
  70. }
  71. STATIC do_loop(loop)
  72. loop_p loop;
  73. {
  74. lset ivs, vars;
  75. OUTTRACE("going to process loop %d",loop->lp_id);
  76. induc_vars(loop,&ivs, &vars);
  77. /* Build a set of iv_structs, one for every induction
  78. * variable of the loop, i.e. a variable i that
  79. * is changed only by i := i + c, where c is a loop constant.
  80. * Also detects variables that are changed (including induction
  81. * variables!).
  82. */
  83. OUTTRACE("loop has %d induction variables",Lnrelems(ivs));
  84. if (Lnrelems(ivs) > 0) {
  85. strength_reduction(loop,ivs,vars);
  86. /* Perform strength reduction. Reduce:
  87. * iv * c to addition
  88. * a[iv] to indirection (*p)
  89. * (unless array bound checking is required)
  90. */
  91. }
  92. del_ivs(ivs);
  93. Ldeleteset(vars);
  94. }
  95. STATIC loopblocks(p)
  96. proc_p p;
  97. {
  98. /* Compute the LP_BLOCKS sets for all loops of p */
  99. register bblock_p b;
  100. register Lindex i;
  101. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  102. for (i = Lfirst(b->b_loops); i != (Lindex) 0;
  103. i = Lnext(i,b->b_loops)) {
  104. Ladd(b,&(((loop_p) Lelem(i))->LP_BLOCKS));
  105. }
  106. }
  107. }
  108. STATIC opt_proc(p)
  109. proc_p p;
  110. {
  111. /* Optimize all loops of one procedure. We first do all
  112. * outer loops at the lowest nesting level and proceed
  113. * in the inwards direction.
  114. */
  115. Lindex i;
  116. loop_p lp,outermost;
  117. int min_level;
  118. for (;;) {
  119. min_level = 1000;
  120. outermost = 0;
  121. for (i = Lfirst(p->p_loops); i != (Lindex) 0;
  122. i = Lnext(i,p->p_loops)) {
  123. lp = (loop_p) Lelem(i);
  124. if (!lp->LP_DONE && lp->lp_level < min_level) {
  125. min_level = lp->lp_level;
  126. outermost = lp;
  127. }
  128. }
  129. if (! outermost) break;
  130. do_loop(outermost);
  131. outermost->LP_DONE = TRUE;
  132. OUTTRACE("loop %d processed",outermost->lp_id);
  133. }
  134. }
  135. STATIC bblock_p header(lp)
  136. loop_p lp;
  137. {
  138. /* Try to determine the 'header' block of loop lp.
  139. * If 'e' is the entry block of loop L, then block 'b' is
  140. * called the header block of L, iff:
  141. * SUCC(b) = {e} & b dominates e.
  142. * If lp has no header block, 0 is returned.
  143. */
  144. bblock_p x = lp->lp_entry->b_idom;
  145. if (x != (bblock_p) 0 && Lnrelems(x->b_succ) == 1 &&
  146. (bblock_p) Lelem(Lfirst(x->b_succ)) == lp->lp_entry) {
  147. return x;
  148. }
  149. return (bblock_p) 0;
  150. }
  151. STATIC sr_extproc(p)
  152. proc_p p;
  153. {
  154. /* Allocate the extended data structures for procedure p */
  155. register loop_p lp;
  156. register Lindex pi;
  157. for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
  158. pi = Lnext(pi,p->p_loops)) {
  159. lp = (loop_p) Lelem(pi);
  160. lp->lp_extend = newsrlpx();
  161. lp->LP_HEADER = header(lp);
  162. if (lp->LP_HEADER) {
  163. lp->LP_INSTR = last_instr(lp->LP_HEADER);
  164. }
  165. }
  166. }
  167. STATIC sr_cleanproc(p)
  168. proc_p p;
  169. {
  170. /* Remove the extended data structures for procedure p */
  171. register loop_p lp;
  172. register Lindex pi;
  173. for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
  174. pi = Lnext(pi,p->p_loops)) {
  175. lp = (loop_p) Lelem(pi);
  176. oldsrlpx(lp->lp_extend);
  177. }
  178. }
  179. sr_optimize(p)
  180. proc_p p;
  181. {
  182. if (IS_ENTERED_WITH_GTO(p)) return;
  183. sr_extproc(p);
  184. loopblocks(p);
  185. opt_proc(p);
  186. sr_cleanproc(p);
  187. }
  188. main(argc,argv)
  189. int argc;
  190. char *argv[];
  191. {
  192. go(argc,argv,no_action,sr_optimize,sr_machinit,no_action);
  193. report("strength reductions",Ssr);
  194. exit(0);
  195. }