123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266 |
- /* $Id$ */
- /*
- * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
- * See the copyright notice in the ACK home directory, in the file "Copyright".
- */
- #include <em_reg.h>
- #include <em_mnem.h>
- #include "../share/types.h"
- #include "../share/alloc.h"
- #include "../share/lset.h"
- #include "../share/aux.h"
- #include "../share/global.h"
- #include "../share/debug.h"
- #include "cs.h"
- #include "cs_avail.h"
- #include "cs_alloc.h"
- #include "cs_aux.h"
- #include "cs_debug.h"
- #include "cs_profit.h"
- #include "cs_partit.h"
- #include "cs_debug.h"
- static void dlink(line_p l1, line_p l2)
- {
- /* Doubly link the lines in l1 and l2. */
- if (l1 != (line_p) 0)
- l1->l_next = l2;
- if (l2 != (line_p) 0)
- l2->l_prev = l1;
- }
- static void remove_lines(line_p first, line_p last)
- {
- /* Throw away the lines between and including first and last.
- * Don't worry about any pointers; the (must) have been taken care of.
- */
- line_p lnp, next;
- last->l_next = (line_p) 0; /* Delimit the list. */
- for (lnp = first; lnp != (line_p) 0; lnp = next) {
- next = lnp->l_next;
- oldline(lnp);
- }
- }
- static bool contained(occur_p ocp1, occur_p ocp2)
- {
- /* Determine whether ocp1 is contained within ocp2. */
- line_p lnp, next;
- for (lnp = ocp2->oc_lfirst; lnp != (line_p) 0; lnp = next) {
- next = lnp != ocp2->oc_llast ? lnp->l_next : (line_p) 0;
- if (lnp == ocp1->oc_llast) return TRUE;
- }
- return FALSE;
- }
- static void delete(occur_p ocp, avail_p start)
- {
- /* Delete all occurrences that are contained within ocp.
- * They must have been entered in the list before start:
- * if an expression is contained with an other, its operator line
- * appears before the operator line of the other because EM-expressions
- * are postfix.
- */
- avail_p ravp;
- Lindex i, next;
- for (ravp = start; ravp != (avail_p) 0; ravp = ravp->av_before) {
- for (i = Lfirst(ravp->av_occurs); i != (Lindex) 0; i = next) {
- next = Lnext(i, ravp->av_occurs);
- if (contained(occ_elem(i), ocp)) {
- OUTTRACE("delete contained occurrence", 0);
- # ifdef TRACE
- SHOWOCCUR(occ_elem(i));
- # endif
- oldoccur(occ_elem(i));
- Lremove(Lelem(i), &ravp->av_occurs);
- }
- }
- }
- }
- static void complete_aar(line_p lnp, int instr, valnum descr_vn)
- {
- /* Lnp is an instruction that loads the address of an array-element.
- * Instr tells us what effect we should achieve; load (instr is op_lar)
- * or store (instr is op_sar) this array-element. Descr_vn is the
- * valuenumber of the address of the descriptor of this array.
- * We append a loi or sti of the correct number of bytes.
- */
- line_p lindir;
- lindir = int_line(array_elemsize(descr_vn));
- lindir->l_instr = instr == op_lar ? op_loi : op_sti;
- dlink(lindir, lnp->l_next);
- dlink(lnp, lindir);
- }
- static void replace(occur_p ocp, offset tmp, avail_p avp)
- {
- /* Replace the lines in the occurrence in ocp by a load of the
- * temporary with offset tmp.
- */
- line_p lol, first, last;
- assert(avp->av_size == ws || avp->av_size == 2*ws);
- first = ocp->oc_lfirst; last = ocp->oc_llast;
- lol = int_line(tmp);
- lol->l_instr = avp->av_size == ws ? op_lol : op_ldl;
- dlink(lol, last->l_next);
- if (first->l_prev == (line_p) 0) ocp->oc_belongs->b_start = lol;
- dlink(first->l_prev, lol);
- if (avp->av_instr == (byte) op_aar) {
- /* There may actually be a LAR or a SAR instruction; in that
- * case we have to complete the array-instruction.
- */
- int instr = INSTR(last);
- if (instr != op_aar) complete_aar(lol, instr, avp->av_othird);
- }
- /* Throw away the by now useless lines. */
- remove_lines(first, last);
- }
- static void append(avail_p avp, offset tmp)
- {
- /* Avp->av_found points to a line with an operator in it. This
- * routine emits a sequence of instructions that saves the result
- * in a local with offset tmp. In most cases we just append
- * avp->av_found with stl/sdl tmp and lol/ldl tmp depending on
- * avp->av_size. If however the operator is an aar contained
- * within a lar or sar, we must first generate the aar.
- */
- line_p stl, lol;
- assert(avp->av_size == ws || avp->av_size == 2*ws);
- stl = int_line(tmp);
- stl->l_instr = avp->av_size == ws ? op_stl : op_sdl;
- lol = int_line(tmp);
- lol->l_instr = avp->av_size == ws ? op_lol : op_ldl;
- dlink(lol, avp->av_found->l_next);
- dlink(stl, lol);
- dlink(avp->av_found, stl);
- if (avp->av_instr == (byte) op_aar) {
- int instr = INSTR(avp->av_found);
- if (instr != op_aar) {
- complete_aar(lol, instr, avp->av_othird);
- avp->av_found->l_instr = op_aar;
- }
- }
- }
- static void set_replace(avail_p avp, offset tmp)
- {
- /* Avp->av_occurs is now a set of occurrences, each of which will be
- * replaced by a reference to a local.
- * Each time we eliminate an expression, we delete from our
- * list those expressions that are physically contained in them,
- * because we cannot eliminate them again.
- */
- Lindex i;
- lset s = avp->av_occurs;
- for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i, s)) {
- OUTVERBOSE("eliminate duplicate", 0);
- SHOWOCCUR(occ_elem(i));
- Scs++;
- delete(occ_elem(i), avp->av_before);
- replace(occ_elem(i), tmp, avp);
- }
- }
- static int reg_score(entity_p enp)
- {
- /* Enp is a local that will go into a register.
- * We return its score upto now.
- */
- assert(is_regvar(enp->en_loc));
- return regv_arg(enp->en_loc, 4);
- }
- static line_p gen_mesreg(offset off, avail_p avp, proc_p pp)
- {
- /* Generate a register message for the local that will hold the
- * result of the expression in avp, at the appropriate place in
- * the procedure in pp.
- */
- line_p reg;
- reg = reg_mes(off, (short) avp->av_size, regtype(avp->av_instr), 0);
- appnd_line(reg, pp->p_start->b_start);
- return reg;
- }
- static void change_score(line_p mes, int score)
- {
- /* Change the score in the register message in mes to score. */
- arg_p ap = ARG(mes);
- ap = ap->a_next; /* Offset. */
- ap = ap->a_next; /* Size. */
- ap = ap->a_next; /* Type. */
- ap = ap->a_next; /* Score. */
- ap->a_a.a_offset = score;
- }
- void eliminate(proc_p pp)
- {
- /* Eliminate costly common subexpressions within procedure pp.
- * We scan the available expressions in - with respect to time found -
- * reverse order, to find largest first, e.g. `A + B + C' before
- * `A + B'.
- * We do not eliminate an expression when the size
- * is not one of ws or 2*ws, because then we cannot use lol or ldl.
- * Code is appended to the first occurrence of the expression
- * to store the result into a local.
- */
- avail_p ravp;
- int score;
- offset tmp;
- line_p mes;
- for (ravp = avails; ravp != (avail_p) 0; ravp = ravp->av_before) {
- if (ravp->av_size != ws && ravp->av_size != 2*ws) continue;
- if (ravp->av_saveloc == (entity_p) 0) {
- /* We save it ourselves. */
- score = 2; /* Stl and lol. */
- } else {
- score = reg_score(ravp->av_saveloc);
- }
- if (desirable(ravp)) {
- score += Lnrelems(ravp->av_occurs);
- OUTTRACE("temporary local score %d", score);
- if (ravp->av_saveloc != (entity_p) 0) {
- tmp = ravp->av_saveloc->en_loc;
- mes = find_mesreg(tmp);
- OUTVERBOSE("re-using %ld(LB)", tmp);
- } else {
- tmp = tmplocal(pp, ravp->av_size);
- mes = gen_mesreg(tmp, ravp, pp);
- append(ravp, tmp);
- }
- change_score(mes, score);
- set_replace(ravp, tmp);
- }
- }
- }
|