sp.c 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247
  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 A C K P O L L U T I O N
  7. *
  8. * S P . C
  9. */
  10. #include <stdlib.h>
  11. #include <stdio.h>
  12. #include <em_mnem.h>
  13. #include <em_spec.h>
  14. #include "../share/types.h"
  15. #include "../share/debug.h"
  16. #include "../share/global.h"
  17. #include "../share/files.h"
  18. #include "../share/get.h"
  19. #include "../share/put.h"
  20. #include "../share/lset.h"
  21. #include "../share/map.h"
  22. #include "../share/alloc.h"
  23. #include "../share/aux.h"
  24. #include "../share/go.h"
  25. #include "../share/stack_chg.h"
  26. /* Stack pollution throws away the ASP instructions after a procedure call.
  27. * This saves a lot of code, at the cost of some extra stack space.
  28. * ASPs that are part of a loop are not removed.
  29. */
  30. #define BF_MARK 04
  31. #define MARK(b) b->b_flags |= BF_MARK
  32. #define NOT_MARKED(b) (!(b->b_flags&BF_MARK))
  33. #define IN_LOOP(b) (Lnrelems(b->b_loops) > 0)
  34. STATIC int Ssp; /* number of optimizations */
  35. /* According to the EM definition, the stack must be cleaned up
  36. * before any return. However, for some backends it causes no harm
  37. * if the stack is not cleaned up. If so, we can do Stack Pollution
  38. * more globally.
  39. */
  40. STATIC int globl_sp_allowed;
  41. #define IS_ASP(l) (INSTR(l) == op_asp && TYPE(l) == OPSHORT && SHORT(l) > 0)
  42. STATIC sp_machinit(f)
  43. FILE *f;
  44. {
  45. /* Read target machine dependent information for this phase */
  46. char s[100];
  47. for (;;) {
  48. while(getc(f) != '\n');
  49. fscanf(f,"%s",s);
  50. if (strcmp(s,"%%SP") == 0)break;
  51. }
  52. fscanf(f,"%d",&globl_sp_allowed);
  53. }
  54. comb_asps(l1,l2,b)
  55. line_p l1,l2;
  56. bblock_p b;
  57. {
  58. assert(INSTR(l1) == op_asp);
  59. assert(INSTR(l2) == op_asp);
  60. assert(TYPE(l1) == OPSHORT);
  61. assert(TYPE(l2) == OPSHORT);
  62. SHORT(l2) += SHORT(l1);
  63. rm_line(l1,b);
  64. }
  65. stack_pollution(b)
  66. bblock_p b;
  67. {
  68. /* For every pair of successive ASP instructions in basic
  69. * block b, try to combine the two into one ASP.
  70. */
  71. register line_p l;
  72. line_p asp,next = b->b_start;
  73. bool asp_seen = FALSE;
  74. int stack_diff,pop,push;
  75. bool ok;
  76. do {
  77. stack_diff = 0;
  78. for (l = next; l != (line_p) 0; l = next) {
  79. next = l->l_next;
  80. if (IS_ASP(l)) break;
  81. if (asp_seen) {
  82. if (INSTR(l) == op_ret) {
  83. stack_diff -= SHORT(l);
  84. } else {
  85. line_change(l,&ok,&pop,&push);
  86. if (!ok || (stack_diff -= pop) < 0) {
  87. /* can't eliminate last ASP */
  88. asp_seen = FALSE;
  89. } else {
  90. stack_diff += push;
  91. }
  92. }
  93. }
  94. }
  95. if (asp_seen) {
  96. if (l == (line_p) 0) {
  97. /* last asp of basic block */
  98. if (globl_sp_allowed &&
  99. NOT_MARKED(b) && !IN_LOOP(b)) {
  100. Ssp++;
  101. rm_line(asp,b);
  102. }
  103. } else {
  104. /* try to combine with previous asp */
  105. if (SHORT(l) == stack_diff) {
  106. Ssp++;
  107. comb_asps(asp,l,b);
  108. }
  109. }
  110. }
  111. asp = l;
  112. asp_seen = TRUE; /* use new ASP for next try! */
  113. } while (asp != (line_p) 0);
  114. }
  115. STATIC bool block_save(b)
  116. bblock_p b;
  117. {
  118. register line_p l;
  119. int stack_diff,pop,push;
  120. bool ok;
  121. stack_diff = 0;
  122. for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
  123. if (INSTR(l) == op_ret) {
  124. stack_diff -= SHORT(l);
  125. break;
  126. }
  127. line_change(l,&ok,&pop,&push);
  128. /* printf("instr %d, pop %d,push %d,ok %d\n",INSTR(l),pop,push,ok); */
  129. if (!ok || (stack_diff -= pop) < 0) {
  130. return FALSE;
  131. } else {
  132. stack_diff += push;
  133. }
  134. }
  135. return stack_diff >= 0;
  136. }
  137. STATIC mark_pred(b)
  138. bblock_p b;
  139. {
  140. Lindex i;
  141. bblock_p x;
  142. for (i = Lfirst(b->b_pred); i != (Lindex) 0; i = Lnext(i,b->b_pred)) {
  143. x = (bblock_p) Lelem(i);
  144. if (NOT_MARKED(x)) {
  145. MARK(x);
  146. mark_pred(x);
  147. }
  148. }
  149. }
  150. STATIC mark_unsave_blocks(p)
  151. proc_p p;
  152. {
  153. register bblock_p b;
  154. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  155. if (NOT_MARKED(b) && !block_save(b)) {
  156. MARK(b);
  157. mark_pred(b);
  158. }
  159. }
  160. }
  161. sp_optimize(p)
  162. proc_p p;
  163. {
  164. register bblock_p b;
  165. if (IS_ENTERED_WITH_GTO(p)) return;
  166. mark_unsave_blocks(p);
  167. for (b = p->p_start; b != 0; b = b->b_next) {
  168. stack_pollution(b);
  169. }
  170. }
  171. main(argc,argv)
  172. int argc;
  173. char *argv[];
  174. {
  175. go(argc,argv,no_action,sp_optimize,sp_machinit,no_action);
  176. report("stack adjustments deleted",Ssp);
  177. exit(0);
  178. }
  179. /***** DEBUGGING:
  180. debug_stack_pollution(p)
  181. proc_p p;
  182. {
  183. register bblock_p b;
  184. register line_p l;
  185. int lcnt,aspcnt,instr;
  186. for (b = p->p_start; b != 0; b = b->b_next) {
  187. lcnt = 0; aspcnt = 0;
  188. for (l = b->b_start; l != 0; l= l->l_next) {
  189. instr = INSTR(l);
  190. if (instr >= sp_fmnem && instr <= sp_lmnem) {
  191. lcnt++;
  192. if (instr == op_asp && off_set(l) > 0) {
  193. aspcnt++;
  194. }
  195. }
  196. }
  197. printf("%d\t%d\n",aspcnt,lcnt);
  198. }
  199. }
  200. */