sp.c 4.6 KB

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