Quick Search:

Mode

Context

Displaying 3 lines of context. None | Less | More | Full

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.71
 
1.72
 
MAIN:ragge:20100502163119
 
optim2.c
_>227227 /*
 228228  * Delete unused labels, excess of labels, gotos to gotos.
 229229  * This routine can be made much more efficient.
<> 230+ *
  231+ * Layout of the statement list here (_must_ look this way!):
  232+ *      PROLOG
  233+ *      LABEL   - states beginning of function argument moves
  234+ *      ...code to save/move arguments
  235+ *      LABEL   - states beginning of execution code
  236+ *      ...code + labels in function in function
  237+ *      EPILOG
  238+ *
  239+ * This version of deljumps is based on the c2 implementation
  240+ * that were included in 2BSD.
230241  */
<>231 -void
 232 -deljumps(struct p2env *p2e)
  242+#define LABEL 1
  243+#define JBR     2
  244+#define CBR     3
  245+#define STMT    4
  246+#define EROU    5
  247+struct dlnod {
  248+        int op;
  249+        struct interpass *dlip;
  250+        struct dlnod *forw;
  251+        struct dlnod *back;
  252+        struct dlnod *ref;
  253+        int labno;
  254+        int refc;
  255+};
  256+
  257+#ifdef DLJDEBUG
  258+static void
  259+dumplink(struct dlnod *dl)
233260 {
<>234 -        struct interpass *ipole = &p2e->ipole;
 235 -        struct interpass *ip, *n, *ip2, *start;
 236 -        int gotone,low, high;
 237 -        int *lblary, *jmpary, sz, o, i, j, lab1, lab2;
 238 -        int del;
 239 -        extern int negrel[];
 240 -        extern size_t negrelsize;
  261+        printf("dumplink %p\n", dl);
  262+        for (; dl; dl = dl->forw) {
  263+                if (dl->op == STMT) {
  264+                        printf("STMT(%p)\n", dl);
  265+                        fwalk(dl->dlip->ip_node, e2print, 0);
  266+                } else if (dl->op == EROU) {
  267+                        printf("EROU(%p)\n", dl);
  268+                } else {
  269+                        static char *str[] = { 0, "LABEL", "JBR", "CBR" };
  270+                        printf("%s(%p) %d refc %d ref %p\n", str[dl->op],
  271+                            dl, dl->labno, dl->refc, dl->ref);
  272+                }
  273+        }
  274+        printf("end dumplink\n");
  275+}
  276+#endif
241277 
<>242 -        low = p2e->ipp->ip_lblnum;
 243 -        high = p2e->epp->ip_lblnum;
  278+/*
  279+ * Create the linked list that we can work on.
  280+ */
  281+static void
  282+listsetup(struct interpass *ipole, struct dlnod *dl)
  283+{
  284+        struct interpass *ip = DLIST_NEXT(ipole, qelem);
  285+        struct dlnod *p, *lastp;
  286+        NODE *q;
244287 
<>245 -#ifdef notyet
 246 -        mark = tmpmark(); /* temporary used memory */
 247 -#endif
  288+        lastp = dl;
  289+        while (ip->type != IP_DEFLAB)
  290+                ip = DLIST_NEXT(ip,qelem);
  291+        ip = DLIST_NEXT(ip,qelem);
  292+        while (ip->type != IP_DEFLAB)
  293+                ip = DLIST_NEXT(ip,qelem);
  294+        /* Now ip is at the beginning */
  295+        for (;;) {
  296+                ip = DLIST_NEXT(ip,qelem);
  297+                if (ip == ipole)
  298+                        break;
  299+                p = tmpalloc(sizeof(struct dlnod));
  300+                p->labno = 0;
  301+                p->dlip = ip;
  302+                switch (ip->type) {
  303+                case IP_DEFLAB:
  304+                        p->op = LABEL;
  305+                        p->labno = ip->ip_lbl;
  306+                        break;
248307 
<>249 -        sz = (high-low) * sizeof(int);
 250 -        lblary = tmpalloc(sz);
 251 -        jmpary = tmpalloc(sz);
  308+                case IP_NODE:
  309+                        q = ip->ip_node;
  310+                        switch (q->n_op) {
  311+                        case GOTO:
  312+                                p->op = JBR;
  313+                                p->labno = q->n_left->n_lval;
  314+                                break;
  315+                        case CBRANCH:
  316+                                p->op = CBR;
  317+                                p->labno = q->n_right->n_lval;
  318+                                break;
  319+                        default:
  320+                                p->op = STMT;
  321+                                break;
  322+                        }
  323+                        break;
252324 
<>253 -        /*
 254 -         * XXX: Find the first two labels. They may not be deleted,
 255 -         * because the register allocator expects them to be there.
 256 -         * These will not be coalesced with any other label.
 257 -         */
 258 -        lab1 = lab2 = -1;
 259 -        start = NULL;
 260 -        DLIST_FOREACH(ip, ipole, qelem) {
 261 -                if (ip->type != IP_DEFLAB)
 262 -                        continue;
 263 -                if (lab1 < 0)
 264 -                        lab1 = ip->ip_lbl;
 265 -                else if (lab2 < 0) {
 266 -                        lab2 = ip->ip_lbl;
 267 -                        start = ip;
 268 -                } else  /* lab1 >= 0 && lab2 >= 0, we're done. */
  325+                case IP_ASM:
  326+                        p->op = STMT;
269327                         break;
<> 328+
  329+                case IP_EPILOG:
  330+                        p->op = EROU;
  331+                        break;
  332+
  333+                default:
  334+                        comperr("listsetup: bad ip node %d", ip->type);
  335+                }
  336+                p->forw = 0;
  337+                p->back = lastp;
  338+                lastp->forw = p;
  339+                lastp = p;
  340+                p->ref = 0;
270341         }
<>271 -        if (lab1 < 0 || lab2 < 0)
 272 -                comperr("deljumps");
  342+}
273343 
<>274 -again:  gotone = 0;
 275 -        memset(lblary, 0, sz);
 276 -        lblary[lab1 - low] = lblary[lab2 - low] = 1;
 277 -        memset(jmpary, 0, sz);
  344+static struct dlnod *
  345+nonlab(struct dlnod *p)
  346+{
  347+        while (p && p->op==LABEL)
  348+                p = p->forw;
  349+        return(p);
  350+}
278351 
<>279 -        /* refcount and coalesce all labels */
 280 -        DLIST_FOREACH(ip, ipole, qelem) {
 281 -                if (ip->type == IP_DEFLAB && ip->ip_lbl != lab1 &&
 282 -                    ip->ip_lbl != lab2) {
 283 -                        n = DLIST_NEXT(ip, qelem);
  352+static void
  353+iprem(struct dlnod *p)
  354+{
  355+        if (p->dlip->type == IP_NODE)
  356+                tfree(p->dlip->ip_node);
  357+        DLIST_REMOVE(p->dlip, qelem);
  358+}
284359 
<>285 -                        /*
 286 -                         * Find unconditional jumps directly following a
 287 -                         * label. Jumps jumping to themselves are not
 288 -                         * taken into account.
 289 -                         */
 290 -                        if (n->type == IP_NODE && n->ip_node->n_op == GOTO) {
 291 -                                i = (int)n->ip_node->n_left->n_lval;
 292 -                                if (i != ip->ip_lbl)
 293 -                                        jmpary[ip->ip_lbl - low] = i;
 294 -                        }
  360+static void
  361+decref(struct dlnod *p)
  362+{
  363+        if (--p->refc <= 0) {
  364+                iprem(p);
  365+                p->back->forw = p->forw;
  366+                p->forw->back = p->back;
  367+        }
  368+}
295369 
<>296 -                        while (n->type == IP_DEFLAB) {
 297 -                                if (n->ip_lbl != lab1 && n->ip_lbl != lab2 &&
 298 -                                    lblary[n->ip_lbl-low] >= 0) {
 299 -                                        /*
 300 -                                         * If the label is used, mark the
 301 -                                         * label to be coalesced with as
 302 -                                         * used, too.
 303 -                                         */
 304 -                                        if (lblary[n->ip_lbl - low] > 0 &&
 305 -                                            lblary[ip->ip_lbl - low] == 0)
 306 -                                                lblary[ip->ip_lbl - low] = 1;
 307 -                                        lblary[n->ip_lbl - low] = -ip->ip_lbl;
  370+static void
  371+setlab(struct dlnod *p, int labno)
  372+{
  373+        p->labno = labno;
  374+        if (p->op == JBR)
  375+                p->dlip->ip_node->n_left->n_lval = labno;
  376+        else if (p->op == CBR)
  377+                p->dlip->ip_node->n_right->n_lval = labno;
  378+        else
  379+                comperr("setlab bad op %d", p->op);
  380+}
  381+
  382+/*
  383+ * Label reference counting and removal of unused labels.
  384+ */
  385+#define LABHS 127
  386+static void
  387+refcount(struct p2env *p2e, struct dlnod *dl)
  388+{
  389+        struct dlnod *p, *lp;
  390+        struct dlnod *labhash[LABHS];
  391+        struct dlnod **hp, *tp;
  392+
  393+        /* Clear label hash */
  394+        for (hp = labhash; hp < &labhash[LABHS];)
  395+                *hp++ = 0;
  396+        /* Enter labels into hash.  Later overwrites earlier */
  397+        for (p = dl->forw; p!=0; p = p->forw)
  398+                if (p->op==LABEL) {
  399+                        labhash[p->labno % LABHS] = p;
  400+                        p->refc = 0;
  401+                }
  402+
  403+        /* search for jumps to labels and fill in reference */
  404+        for (p = dl->forw; p!=0; p = p->forw) {
  405+                if (p->op==JBR || p->op==CBR) {
  406+                        p->ref = 0;
  407+                        lp = labhash[p->labno % LABHS];
  408+                        if (lp==0 || p->labno!=lp->labno)
  409+                            for (lp = dl->forw; lp!=0; lp = lp->forw) {
  410+                                if (lp->op==LABEL && p->labno==lp->labno)
  411+                                        break;
  412+                            }
  413+                        if (lp) {
  414+                                tp = nonlab(lp)->back;
  415+                                if (tp!=lp) {
  416+                                        setlab(p, tp->labno);
  417+                                        lp = tp;
308418                                 }
<>309 -                                n = DLIST_NEXT(n, qelem);
  419+                                p->ref = lp;
  420+                                lp->refc++;
310421                         }
 311422                 }
<>312 -                if (ip->type != IP_NODE)
 313 -                        continue;
 314 -                o = ip->ip_node->n_op;
 315 -                if (o == GOTO)
 316 -                        i = (int)ip->ip_node->n_left->n_lval;
 317 -                else if (o == CBRANCH)
 318 -                        i = (int)ip->ip_node->n_right->n_lval;
 319 -                else
 320 -                        continue;
 321 -
 322 -                /*
 323 -                 * Mark destination label i as used, if it is not already.
 324 -                 * If i is to be merged with label j, mark j as used, too.
 325 -                 */
 326 -                if (lblary[i - low] == 0)
 327 -                        lblary[i-low] = 1;
 328 -                else if ((j = lblary[i - low]) < 0 && lblary[-j - low] == 0)
 329 -                        lblary[-j - low] = 1;
330423         }
<> 424+        for (p = dl->forw; p!=0; p = p->forw)
  425+                if (p->op==LABEL && p->refc==0
  426+                 && (lp = nonlab(p))->op)
  427+                        decref(p);
  428+}
331429 
<>332 -        /* delete coalesced/unused labels and rename gotos */
 333 -        DLIST_FOREACH(ip, ipole, qelem) {
 334 -                n = DLIST_NEXT(ip, qelem);
 335 -                if (n->type == IP_DEFLAB) {
 336 -                        if (lblary[n->ip_lbl-low] <= 0) {
 337 -                                DLIST_REMOVE(n, qelem);
 338 -                                gotone = 1;
 339 -                        }
 340 -                }
 341 -                if (ip->type != IP_NODE)
 342 -                        continue;
 343 -                o = ip->ip_node->n_op;
 344 -                if (o == GOTO)
 345 -                        i = (int)ip->ip_node->n_left->n_lval;
 346 -                else if (o == CBRANCH)
 347 -                        i = (int)ip->ip_node->n_right->n_lval;
 348 -                else
 349 -                        continue;
  430+static int nchange;
350431 
<>351 -                /* Simplify (un-)conditional jumps to unconditional jumps. */
 352 -                if (jmpary[i - low] > 0) {
 353 -                        gotone = 1;
 354 -                        i = jmpary[i - low];
 355 -                        if (o == GOTO)
 356 -                                ip->ip_node->n_left->n_lval = i;
 357 -                        else
 358 -                                ip->ip_node->n_right->n_lval = i;
 359 -                }
  432+static struct dlnod *
  433+codemove(struct dlnod *p)
  434+{
  435+        struct dlnod *p1, *p2, *p3;
  436+#ifdef notyet
  437+        struct dlnod *t, *tl;
  438+        int n;
  439+#endif
360440 
<>361 -                /* Fixup for coalesced labels. */
 362 -                if (lblary[i-low] < 0) {
 363 -                        if (o == GOTO)
 364 -                                ip->ip_node->n_left->n_lval = -lblary[i-low];
 365 -                        else
 366 -                                ip->ip_node->n_right->n_lval = -lblary[i-low];
 367 -                }
  441+        p1 = p;
  442+        if (p1->op!=JBR || (p2 = p1->ref)==0)
  443+                return(p1);
  444+        while (p2->op == LABEL)
  445+                if ((p2 = p2->back) == 0)
  446+                        return(p1);
  447+        if (p2->op!=JBR)
  448+                goto ivloop;
  449+        if (p1==p2)
  450+                return(p1);
  451+        p2 = p2->forw;
  452+        p3 = p1->ref;
  453+        while (p3) {
  454+                if (p3->op==JBR) {
  455+                        if (p1==p3 || p1->forw==p3 || p1->back==p3)
  456+                                return(p1);
  457+                        nchange++;
  458+                        p1->back->forw = p2;
  459+                        p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip;
  460+
  461+                        p1->forw->back = p3;
  462+                        p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip;
  463+
  464+
  465+                        p2->back->forw = p3->forw;
  466+                        p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip;
  467+
  468+                        p3->forw->back = p2->back;
  469+                        p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip;
  470+
  471+                        p2->back = p1->back;
  472+                        p2->dlip->qelem.q_back = p1->dlip->qelem.q_back;
  473+
  474+                        p3->forw = p1->forw;
  475+                        p3->dlip->qelem.q_forw = p1->forw->dlip;
  476+
  477+                        decref(p1->ref);
  478+                        if (p1->dlip->type == IP_NODE)
  479+                                tfree(p1->dlip->ip_node);
  480+
  481+                        return(p2);
  482+                } else
  483+                        p3 = p3->forw;
368484         }
<> 485+        return(p1);
369486 
<>370 -        /* Delete gotos to the next statement */
 371 -        DLIST_FOREACH(ip, ipole, qelem) {
 372 -                n = DLIST_NEXT(ip, qelem);
 373 -                if (n->type != IP_NODE)
 374 -                        continue;
 375 -                o = n->ip_node->n_op;
 376 -                if (o == GOTO)
 377 -                        i = (int)n->ip_node->n_left->n_lval;
 378 -#if 0 /* XXX must check for side effects in expression */
 379 -                else if (o == CBRANCH)
 380 -                        i = (int)n->ip_node->n_right->n_lval;
  487+ivloop:
  488+        if (p1->forw->op!=LABEL)
  489+                return(p1);
  490+        return(p1);
  491+
  492+#ifdef notyet
  493+        p3 = p2 = p2->forw;
  494+        n = 16;
  495+        do {
  496+                if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
  497+                        return(p1);
  498+        } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
  499+        do
  500+                if ((p1 = p1->back) == 0)
  501+                        return(p);
  502+        while (p1!=p3);
  503+        p1 = p;
  504+        tl = insertl(p1);
  505+        p3->subop = revbr[p3->subop];
  506+        decref(p3->ref);
  507+                p2->back->forw = p1;
  508+        p3->forw->back = p1;
  509+        p1->back->forw = p2;
  510+        p1->forw->back = p3;
  511+        t = p1->back;
  512+        p1->back = p2->back;
  513+        p2->back = t;
  514+        t = p1->forw;
  515+        p1->forw = p3->forw;
  516+        p3->forw = t;
  517+        p2 = insertl(p1->forw);
  518+        p3->labno = p2->labno;
  519+        p3->ref = p2;
  520+        decref(tl);
  521+        if (tl->refc<=0)
  522+                nrlab--;
  523+        nchange++;
  524+        return(p3);
381525 #endif
<>382 -                else
 383 -                        continue;
  526+}
384527 
<>385 -                ip2 = n;
 386 -                ip2 = DLIST_NEXT(ip2, qelem);
  528+static void
  529+iterate(struct p2env *p2e, struct dlnod *dl)
  530+{
  531+        struct dlnod *p, *rp, *p1;
  532+        extern int negrel[];
  533+        extern size_t negrelsize;
  534+        int i;
387535 
<>388 -                if (ip2->type != IP_DEFLAB)
 389 -                        continue;
 390 -                if (ip2->ip_lbl == i && i != lab1 && i != lab2) {
 391 -                        tfree(n->ip_node);
 392 -                        DLIST_REMOVE(n, qelem);
 393 -                        gotone = 1;
  536+        nchange = 0;
  537+        for (p = dl->forw; p!=0; p = p->forw) {
  538+                if ((p->op==JBR||p->op==CBR) && p->ref) {
  539+                        /* Resolves:
  540+                         * jbr L7
  541+                         * ...
  542+                         * L7: jbr L8
  543+                         */
  544+                        rp = nonlab(p->ref);
  545+                        if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
  546+                                setlab(p, rp->labno);
  547+                                decref(p->ref);
  548+                                rp->ref->refc++;
  549+                                p->ref = rp->ref;
  550+                                nchange++;
  551+                        }
394552                 }
<>395 -        }
  553+                if (p->op==CBR && (p1 = p->forw)->op==JBR) {
  554+                        /* Resolves:
  555+                         * cbr L7
  556+                         * jbr L8
  557+                         * L7:
  558+                         */
  559+                        rp = p->ref;
  560+                        do
  561+                                rp = rp->back;
  562+                        while (rp->op==LABEL);
  563+                        if (rp==p1) {
  564+                                decref(p->ref);
  565+                                p->ref = p1->ref;
  566+                                setlab(p, p1->labno);
396567 
<>397 -        /*
 398 -         * Transform cbranch cond, 1; goto 2; 1: ... into
 399 -         * cbranch !cond, 2; 1: ...
 400 -         */
 401 -        DLIST_FOREACH(ip, ipole, qelem) {
 402 -                n = DLIST_NEXT(ip, qelem);
 403 -                ip2 = DLIST_NEXT(n, qelem);
 404 -                if (ip->type != IP_NODE || ip->ip_node->n_op != CBRANCH)
 405 -                        continue;
 406 -                if (n->type != IP_NODE || n->ip_node->n_op != GOTO)
 407 -                        continue;
 408 -                if (ip2->type != IP_DEFLAB)
 409 -                        continue;
 410 -                i = (int)ip->ip_node->n_right->n_lval;
 411 -                j = (int)n->ip_node->n_left->n_lval;
 412 -                if (j == lab1 || j == lab2)
 413 -                        continue;
 414 -                if (i != ip2->ip_lbl || i == lab1 || i == lab2)
 415 -                        continue;
 416 -                ip->ip_node->n_right->n_lval = j;
 417 -                i = ip->ip_node->n_left->n_op;
 418 -                if (i < EQ || i - EQ >= (int)negrelsize)
 419 -                        comperr("deljumps: unexpected op");
 420 -                ip->ip_node->n_left->n_op = negrel[i - EQ];
 421 -                tfree(n->ip_node);
 422 -                DLIST_REMOVE(n, qelem);
 423 -                gotone = 1;
 424 -        }
  568+                                iprem(p1);
425569 
<>426 -        /* Delete everything after a goto up to the next label. */
 427 -        for (ip = start, del = 0; ip != DLIST_ENDMARK(ipole);
 428 -             ip = DLIST_NEXT(ip, qelem)) {
 429 -loop:
 430 -                if ((n = DLIST_NEXT(ip, qelem)) == DLIST_ENDMARK(ipole))
 431 -                        break;
 432 -                if (n->type != IP_NODE) {
 433 -                        del = 0;
 434 -                        continue;
  570+                                p1->forw->back = p;
  571+                                p->forw = p1->forw;
  572+
  573+                                i = p->dlip->ip_node->n_left->n_op;
  574+                                if (i < EQ || i - EQ >= (int)negrelsize)
  575+                                        comperr("deljumps: unexpected op");
  576+                                p->dlip->ip_node->n_left->n_op = negrel[i - EQ];
  577+                                nchange++;
  578+                        }
435579                 }
<>436 -                if (del) {
 437 -                        tfree(n->ip_node);
 438 -                        DLIST_REMOVE(n, qelem);
 439 -                        gotone = 1;
 440 -                        goto loop;
 441 -                } else if (n->ip_node->n_op == GOTO)
 442 -                        del = 1;
  580+                if (p->op == JBR) {
  581+                        /* Removes dead code */
  582+                        while (p->forw && p->forw->op!=LABEL &&
  583+                            p->forw->op!=EROU) {
  584+                                nchange++;
  585+                                if (p->forw->ref)
  586+                                        decref(p->forw->ref);
  587+
  588+                                iprem(p->forw);
  589+
  590+                                p->forw = p->forw->forw;
  591+                                p->forw->back = p;
  592+                        }
  593+                        rp = p->forw;
  594+                        while (rp && rp->op==LABEL) {
  595+                                if (p->ref == rp) {
  596+                                        p->back->forw = p->forw;
  597+                                        p->forw->back = p->back;
  598+                                        iprem(p);
  599+                                        p = p->back;
  600+                                        decref(rp);
  601+                                        nchange++;
  602+                                        break;
  603+                                }
  604+                                rp = rp->forw;
  605+                        }
  606+                }
  607+                if (p->op == JBR) {
  608+                        /* xjump(p); * needs tree rewrite; not yet */
  609+                        p = codemove(p);
  610+                }
443611         }
<> 612+}
444613 
<>445 -        if (gotone)
 446 -                goto again;
  614+void
  615+deljumps(struct p2env *p2e)
  616+{
  617+        struct interpass *ipole = &p2e->ipole;
  618+        struct dlnod dln;
  619+        MARK mark;
447620 
<> 621+        markset(&mark);
  622+
  623+        memset(&dln, 0, sizeof(dln));
  624+        listsetup(ipole, &dln);
  625+        do {
  626+                refcount(p2e, &dln);
  627+                do {
  628+                        iterate(p2e, &dln);
  629+                } while (nchange);
448630 #ifdef notyet
<>449 -        tmpfree(mark);
  631+                comjump();
450632 #endif
<> 633+        } while (nchange);
  634+
  635+        markfree(&mark);
<_451636 }
 452637 
 453638 void
FishEye: Open Source License registered to PCC.
Your maintenance has expired. You can renew your license at http://www.atlassian.com/fisheye/renew
Atlassian FishEye, CVS analysis. (Version:1.6.3 Build:build-336 2008-11-04) - Administration - Page generated 2014-10-31 18:57 +0100