123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354 |
- /* $Id$ */
- /*
- * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
- * See the copyright notice in the ACK home directory, in the file "Copyright".
- */
- /* C R O S S J U M P I N G
- *
- * CJ.H
- *
- */
- #include <stdlib.h>
- #include <stdio.h>
- #include <em_mnem.h>
- #include <em_spec.h>
- #include "../share/types.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/aux.h"
- #include "../share/def.h"
- #include "../share/stack_chg.h"
- #include "../share/go.h"
- /* Cross jumping performs optimzations like:
- *
- * if cond then goto L1; if cond then goto L1
- * S1; -----> S1;
- * S2; goto L3;
- * goto L2; L1:
- * L1: S3;
- * S3; L3:
- * S2; S2;
- * L2:
- *
- * CJ looks for two basic blocks b1 and b2 with the following properties:
- * - there exists a basic block S such that SUCC(b1) = SUCC(b2) = {S}
- * (so both have only 1 successor)
- * - the last N (N > 0) instructions of b1 and b2, not counting a possible
- * BRAnch instruction, are the same.
- * As a result of the first condition, at least of the two blocks must end
- * on an (unconditional) BRAnch instruction. If both end on a BRA, one block
- * is chosen at random. Assume this block is b1. A new label L is put just
- * before the N common instructions of block b2 (so this block is split
- * into two). The BRA of b1 is changed into a BRA L. So dynamically the same
- * instructions are executed in a slightly different order; yet the size of
- * the code has become smaller.
- */
- static int Scj; /* number of optimizations found */
- /* static void showinstr(line_p lnp); */
- #define DLINK(l1,l2) l1->l_next=l2; l2->l_prev=l1
- static bool same_instr(line_p l1, line_p l2)
- {
- /* See if l1 and l2 are the same instruction */
- if (l1 == 0 || l2 == 0 || TYPE(l1) != TYPE(l2)) return FALSE;
- if (INSTR(l1) != INSTR(l2)) return FALSE;
- switch(TYPE(l1)) {
- case OPSHORT: return SHORT(l1) == SHORT(l2);
- case OPOFFSET: return OFFSET(l1) == OFFSET(l2);
- case OPPROC: return PROC(l1) == PROC(l2);
- case OPOBJECT: return OBJ(l1) == OBJ(l2);
- case OPINSTRLAB: return INSTRLAB(l1) == INSTRLAB(l2);
- case OPNO: return TRUE;
- default: return FALSE;
- }
- }
- static line_p last_mnem(bblock_p b)
- {
- /* Determine the last line of a list */
- line_p l;
- for (l = b->b_start; l->l_next != (line_p) 0; l = l->l_next);
- while (l != (line_p) 0 && (INSTR(l) < sp_fmnem || INSTR(l) > sp_lmnem)) {
- l = PREV(l);
- }
- return l;
- }
- static bool is_desirable(line_p text)
- {
- /* We avoid to generate a BRAnch in the middle of some expression,
- * as the code generator will write the contents of the fakestack
- * to the real stack if it encounters a BRA. We do not avoid to
- * split the parameter-pushing code of a subroutine call into two,
- * as the parameters are pushed on the real stack anyway.
- * So e.g. "LOL a ; LOL b; ADI" will not be split, but
- * "LOL a; LOL b; CAL f" may be split.
- */
- line_p l;
- bool ok;
- int stack_diff,pop,push;
- stack_diff = 0;
- for (l = text; l != (line_p) 0; l = l->l_next) {
- switch(INSTR(l)) {
- case op_cal:
- case op_asp:
- case op_bra:
- return TRUE;
- }
- line_change(l,&ok,&pop,&push);
- /* printf("instr %d, pop %d, push %d, ok %d\n",INSTR(l),pop,push,ok); */
- if (!ok || (stack_diff -= pop) < 0) {
- return FALSE;
- } else {
- stack_diff += push;
- }
- }
- return TRUE;
- }
- static void cp_loops(bblock_p b1, bblock_p b2)
- {
- /* Copy the loopset of b2 to b1 */
- Lindex i;
- loop_p lp;
- for (i = Lfirst(b2->b_loops); i != (Lindex) 0;
- i = Lnext(i,b2->b_loops)) {
- lp = (loop_p) Lelem(i);
- Ladd(lp,&b1->b_loops);
- }
- }
- static void jump_cross(line_p l1, line_p l2, bblock_p b1, bblock_p b2)
- {
- /* A cross-jump from block b2 to block b1 is found; the code in
- * block b2 from line l2 up to the BRAnch is removed; block b1 is
- * split into two; the second part consists of a new label
- * followed by the code from l1 till the end of the block.
- */
- line_p l;
- bblock_p b;
- bblock_p s;
- /* First adjust the control flow graph */
- b = freshblock(); /* create a new basic block */
- b->b_succ = b1->b_succ;
- /* SUCC(b1) = {b} */
- b1->b_succ = Lempty_set(); Ladd(b,&b1->b_succ);
- /* SUCC(b2) = {b} */
- Ldeleteset(b2->b_succ); b2->b_succ = Lempty_set(); Ladd(b,&b2->b_succ);
- /* PRED(b) = {b1,b2} */
- b->b_pred = Lempty_set(); Ladd(b1,&b->b_pred); Ladd(b2,&b->b_pred);
- /* PRED(SUCC(b)) := PRED(SUCC(b)) - {b1,b2} + {b} */
- assert(Lnrelems(b->b_succ) == 1);
- s = (bblock_p) Lelem(Lfirst(b->b_succ));
- Lremove(b1,&s->b_pred); Lremove(b2,&s->b_pred); Ladd(b,&s->b_pred);
- cp_loops(b,b1);
- b->b_idom = common_dom(b1,b2);
- b->b_flags = b1->b_flags;
- b->b_next = b1->b_next;
- b1->b_next = b;
- /* Now adjust the EM text */
- l = PREV(l1);
- while (l && INSTR(l) == op_lab) {
- l1 = l;
- l = PREV(l);
- }
- if (l == (line_p) 0) {
- b1->b_start = (line_p) 0;
- } else {
- l->l_next = (line_p) 0;
- }
- if (INSTR(l1) == op_lab) {
- l = l1;
- }
- else {
- l = newline(OPINSTRLAB);
- l->l_instr = op_lab;
- INSTRLAB(l) = freshlabel();
- DLINK(l,l1);
- }
- b->b_start = l;
- for (l = l2; INSTR(l) != op_bra;) {
- line_p next = l->l_next;
- assert (l != (line_p) 0);
- rm_line(l,b2);
- l = next;
- }
- INSTRLAB(l) = INSTRLAB(b->b_start);
- }
- static bool try_tail(bblock_p b1, bblock_p b2)
- {
- /* See if b1 and b2 end on the same sequence of instructions */
- line_p l1,l2;
- bblock_p b = (bblock_p) 0;
- int cnt = 0;
- /* printf("try block %d and %d\n",b1->b_id,b2->b_id); */
- if (b1->b_start == (line_p) 0 || b2->b_start == (line_p) 0) return FALSE;
- l1 = last_mnem(b1);
- l2 = last_mnem(b2);
- if (l1 == (line_p) 0 || l2 == (line_p) 0) return FALSE;
- /* printf("consider:\n"); showinstr(l1); showinstr(l2); */
- if (INSTR(l1) == op_bra) {
- b = b1;
- l1 = PREV(l1);
- }
- if (INSTR(l2) == op_bra) {
- b = b2;
- l2 = PREV(l2);
- }
- assert(b != (bblock_p) 0);
- while(same_instr(l1,l2)) {
- cnt++;
- l1 = PREV(l1);
- l2 = PREV(l2);
- /* printf("consider:\n"); showinstr(l1); showinstr(l2); */
- }
- if (cnt >= 1) {
- l1 = (l1 == 0 ? b1->b_start : l1->l_next);
- l2 = (l2 == 0 ? b2->b_start : l2->l_next);
- if (is_desirable(l1)) {
- if (b == b1) {
- jump_cross(l2,l1,b2,b1);
- Scj++;
- } else {
- jump_cross(l1,l2,b1,b2);
- Scj++;
- }
- return TRUE;
- }
- }
- return FALSE;
- }
- static bool try_pred(bblock_p b)
- {
- /* See if there is any pair (b1,b2), both in PRED(b) for
- * which we can perform cross jumping.
- */
- register bblock_p b1,b2;
- register Lindex i,j;
- lset s = b->b_pred;
- for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i,s)) {
- b1 = (bblock_p) Lelem(i);
- if (Lnrelems(b1->b_succ) != 1) continue;
- for (j = Lfirst(s); j != (Lindex) 0; j = Lnext(j,s)) {
- b2 = (bblock_p) Lelem(j);
- if (b1 != b2 && Lnrelems(b2->b_succ) == 1) {
- if (try_tail(b1,b2)) return TRUE;
- }
- }
- }
- return FALSE;
- }
- int cj_optimize(void *param)
- {
- /* Perform cross jumping for procedure p.
- * In case cases a cross-jumping optimization which give
- * new opportunities for further cross-jumping optimizations.
- * Hence we repeat the whole process for the entire procedure,
- * untill we find no further optimizations.
- */
- proc_p p = (proc_p)param;
- bblock_p b;
- bool changes = TRUE;
- if (IS_ENTERED_WITH_GTO(p)) return 0;
- while(changes) {
- changes = FALSE;
- b = p->p_start;
- while (b != (bblock_p) 0) {
- if (try_pred(b)) {
- changes = TRUE;
- } else {
- b = b->b_next;
- }
- }
- }
- return 0;
- }
- int main(int argc, char *argv[])
- {
- go(argc,argv,no_action,cj_optimize,no_action,no_action);
- report("cross jumps",Scj);
- exit(0);
- }
- /******
- * Debugging stuff
- */
- #if 0
- extern char em_mnem[]; /* The mnemonics of the EM instructions. */
- static void showinstr(line_p lnp)
- {
- /* Makes the instruction in `lnp' human readable. Only lines that
- * can occur in expressions that are going to be eliminated are
- * properly handled.
- */
- if (lnp == 0) return;
- if (INSTR(lnp) < sp_fmnem || INSTR(lnp) > sp_lmnem) {
- printf("\t*** ?\n");
- return;
- }
- printf("\t%s", &em_mnem[4 * (INSTR(lnp)-sp_fmnem)]);
- switch (TYPE(lnp)) {
- case OPNO:
- break;
- case OPSHORT:
- printf(" %d", SHORT(lnp)); break;
- case OPOBJECT:
- printf(" %d", OBJ(lnp)->o_id); break;
- case OPOFFSET:
- printf(" %ld", OFFSET(lnp)); break;
- default:
- printf(" ?"); break;
- }
- printf("\n");
- } /* showinstr */
- #endif
|