Quick Search:

Mode

Context

Displaying the whole file. None | Less | More | Full

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.49
 
1.50
 
MAIN:ragge:20071230103150
 
optim2.c
_>11 /*      $Id$    */
 22 /*
 33  * Copyright (c) 2004 Anders Magnusson (ragge@ludd.luth.se).
 44  * All rights reserved.
 55  *
 66  * Redistribution and use in source and binary forms, with or without
 77  * modification, are permitted provided that the following conditions
 88  * are met:
 99  * 1. Redistributions of source code must retain the above copyright
 1010  *    notice, this list of conditions and the following disclaimer.
 1111  * 2. Redistributions in binary form must reproduce the above copyright
 1212  *    notice, this list of conditions and the following disclaimer in the
 1313  *    documentation and/or other materials provided with the distribution.
 1414  * 3. The name of the author may not be used to endorse or promote products
 1515  *    derived from this software without specific prior written permission
 1616  *
 1717  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 1818  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 1919  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 2020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 2121  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 2222  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 2323  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 2424  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 2525  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 2626  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 2727  */
 2828 
 2929 #include "pass2.h"
 3030 
 3131 #include <string.h>
 3232 #include <stdlib.h>
 3333 
 3434 #ifndef MIN
 3535 #define MIN(a,b) (((a)<(b))?(a):(b))
 3636 #endif
 3737 
 3838 #ifndef MAX
 3939 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
 4040 #endif
 4141 
 4242 #define BDEBUG(x)       if (b2debug) printf x
 4343 
<> 44+#define mktemp(n, t)    mklnode(TEMP, 0, n, t)
  45+
4446 static int dfsnum;
 4547 
 4648 void saveip(struct interpass *ip);
 4749 void deljumps(struct interpass *);
 4850 void optdump(struct interpass *ip);
 4951 void printip(struct interpass *pole);
 5052 
 5153 static struct varinfo defsites;
 5254 struct interpass *storesave;
 5355 static struct interpass_prolog *ipp, *epp; /* prolog/epilog */
 5456 
 5557 void bblocks_build(struct interpass *, struct labelinfo *, struct bblockinfo *);
 5658 void cfg_build(struct labelinfo *labinfo);
 5759 void cfg_dfs(struct basicblock *bb, unsigned int parent,
 5860              struct bblockinfo *bbinfo);
 5961 void dominators(struct bblockinfo *bbinfo);
 6062 struct basicblock *
 6163 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo);
 6264 void link(struct basicblock *parent, struct basicblock *child);
 6365 void computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo);
 6466 void findTemps(struct interpass *ip);
 6567 void placePhiFunctions(struct bblockinfo *bbinfo);
 6668 void remunreach(void);
 6769 
 6870 struct basicblock bblocks;
 6971 int nbblocks;
 7072 static struct interpass *cvpole;
 7173 
 7274 struct addrof {
 7375         struct addrof *next;
 7476         int tempnum;
 7577         int oregoff;
 7678 } *otlink;
 7779 
 7880 static int
 7981 getoff(int num)
 8082 {
 8183         struct addrof *w;
 8284 
 8385         for (w = otlink; w; w = w->next)
 8486                 if (w->tempnum == num)
 8587                         return w->oregoff;
 8688         return 0;
 8789 }
 8890 
 8991 /*
 9092  * Use stack argument addresses instead of copying if & is used on a var.
 9193  */
 9294 static int
 9395 setargs(int tval, struct addrof *w)
 9496 {
 9597         struct interpass *ip;
 9698         NODE *p;
 9799 
 98100         ip = DLIST_NEXT(cvpole, qelem); /* PROLOG */
 99101         ip = DLIST_NEXT(ip, qelem); /* first DEFLAB */
 100102         ip = DLIST_NEXT(ip, qelem); /* first NODE */
 101103         for (; ip->type != IP_DEFLAB; ip = DLIST_NEXT(ip, qelem)) {
 102104                 p = ip->ip_node;
 103105 #ifdef PCC_DEBUG
 104106                 if (p->n_op != ASSIGN || p->n_left->n_op != TEMP)
 105107                         comperr("temparg");
 106108 #endif
 107109                 if (p->n_right->n_op != OREG)
 108110                         continue; /* arg in register */
<>109 -                if (tval != p->n_left->n_lval)
  111+                if (tval != regno(p->n_left))
110112                         continue; /* wrong assign */
 111113                 w->oregoff = p->n_right->n_lval;
 112114                 tfree(p);
 113115                 DLIST_REMOVE(ip, qelem);
 114116                 return 1;
 115117         }
 116118         return 0;
 117119 }
 118120 
 119121 /*
 120122  * Search for ADDROF elements and, if found, record them.
 121123  */
 122124 static void
 123125 findaddrof(NODE *p)
 124126 {
 125127         struct addrof *w;
<> 128+        int tnr;
126129 
 127130         if (p->n_op != ADDROF)
 128131                 return;
<>129 -        if (getoff(p->n_left->n_lval))
  132+        tnr = regno(p->n_left);
  133+        if (getoff(tnr))
130134                 return;
 131135         w = tmpalloc(sizeof(struct addrof));
<>132 -        w->tempnum = p->n_left->n_lval;
 133 -        if (setargs(p->n_left->n_lval, w) == 0)
  136+        w->tempnum = tnr;
  137+        if (setargs(tnr, w) == 0)
134138                 w->oregoff = BITOOR(freetemp(szty(p->n_left->n_type)));
 135139         w->next = otlink;
 136140         otlink = w;
 137141 }
 138142 
 139143 
 140144 /*
 141145  * Convert address-taken temps to OREGs.
 142146  */
 143147 static void
 144148 cvtaddrof(NODE *p)
 145149 {
 146150         NODE *l;
 147151         int n;
 148152 
 149153         if (p->n_op != ADDROF && p->n_op != TEMP)
 150154                 return;
 151155         if (p->n_op == TEMP) {
<>152 -                n = getoff(p->n_lval);
  156+                n = getoff(regno(p));
153157                 if (n == 0)
 154158                         return;
 155159                 p->n_op = OREG;
 156160                 p->n_lval = n;
<>157 -                p->n_rval = FPREG;
  161+                regno(p) = FPREG;
158162         } else {
 159163                 l = p->n_left;
 160164                 l->n_type = p->n_type;
 161165                 p->n_right = mklnode(ICON, l->n_lval, 0, l->n_type);
 162166                 p->n_op = PLUS;
 163167                 l->n_op = REG;
 164168                 l->n_lval = 0;
 165169                 l->n_rval = FPREG;
 166170                 
 167171         }
 168172 }
 169173 
 170174 void
 171175 optimize(struct interpass *ipole)
 172176 {
 173177         struct interpass *ip;
 174178         struct labelinfo labinfo;
 175179         struct bblockinfo bbinfo;
 176180 
 177181         ipp = (struct interpass_prolog *)DLIST_NEXT(ipole, qelem);
 178182         epp = (struct interpass_prolog *)DLIST_PREV(ipole, qelem);
 179183 
 180184         if (b2debug) {
 181185                 printf("initial links\n");
 182186                 printip(ipole);
 183187         }
 184188 
 185189         /*
 186190          * Convert ADDROF TEMP to OREGs.
 187191          */
 188192         if (xtemps) {
 189193                 otlink = NULL;
 190194                 cvpole = ipole;
 191195                 DLIST_FOREACH(ip, ipole, qelem) {
 192196                         if (ip->type != IP_NODE)
 193197                                 continue;
 194198                         walkf(ip->ip_node, findaddrof);
 195199                 }
 196200                 if (otlink) {
 197201                         DLIST_FOREACH(ip, ipole, qelem) {
 198202                                 if (ip->type != IP_NODE)
 199203                                         continue;
 200204                                 walkf(ip->ip_node, cvtaddrof);
 201205                         }
 202206                 }
 203207         }
 204208                 
 205209         if (xdeljumps)
 206210                 deljumps(ipole); /* Delete redundant jumps and dead code */
 207211 
 208212 #ifdef PCC_DEBUG
 209213         if (b2debug) {
 210214                 printf("links after deljumps\n");
 211215                 printip(ipole);
 212216         }
 213217 #endif
 214218         if (xssaflag || xtemps) {
 215219                 DLIST_INIT(&bblocks, bbelem);
 216220                 bblocks_build(ipole, &labinfo, &bbinfo);
 217221                 BDEBUG(("Calling cfg_build\n"));
 218222                 cfg_build(&labinfo);
 219223         }
 220224         if (xssaflag) {
 221225                 BDEBUG(("Calling dominators\n"));
 222226                 dominators(&bbinfo);
 223227                 BDEBUG(("Calling computeDF\n"));
 224228                 computeDF(DLIST_NEXT(&bblocks, bbelem), &bbinfo);
 225229                 BDEBUG(("Calling remunreach\n"));
 226230                 remunreach();
 227231 #if 0
 228232                 dfg = dfg_build(cfg);
 229233                 ssa = ssa_build(cfg, dfg);
 230234 #endif
 231235         }
 232236 
 233237 #ifdef PCC_DEBUG
 234238         if (epp->ipp_regs != 0)
 235239                 comperr("register error");
 236240 #endif
 237241 
 238242         myoptim(ipole);
 239243 }
 240244 
 241245 /*
 242246  * Delete unused labels, excess of labels, gotos to gotos.
 243247  * This routine can be made much more efficient.
 244248  */
 245249 void
 246250 deljumps(struct interpass *ipole)
 247251 {
 248252         struct interpass *ip, *n, *ip2, *start;
 249253         int gotone,low, high;
 250254         int *lblary, *jmpary, sz, o, i, j, lab1, lab2;
 251255         int del;
 252256         extern int negrel[];
 253257         extern size_t negrelsize;
 254258 
 255259         low = ipp->ip_lblnum;
 256260         high = epp->ip_lblnum;
 257261 
 258262 #ifdef notyet
 259263         mark = tmpmark(); /* temporary used memory */
 260264 #endif
 261265 
 262266         sz = (high-low) * sizeof(int);
 263267         lblary = tmpalloc(sz);
 264268         jmpary = tmpalloc(sz);
 265269 
 266270         /*
 267271          * XXX: Find the first two labels. They may not be deleted,
 268272          * because the register allocator expects them to be there.
 269273          * These will not be coalesced with any other label.
 270274          */
 271275         lab1 = lab2 = -1;
 272276         start = NULL;
 273277         DLIST_FOREACH(ip, ipole, qelem) {
 274278                 if (ip->type != IP_DEFLAB)
 275279                         continue;
 276280                 if (lab1 < 0)
 277281                         lab1 = ip->ip_lbl;
 278282                 else if (lab2 < 0) {
 279283                         lab2 = ip->ip_lbl;
 280284                         start = ip;
 281285                 } else  /* lab1 >= 0 && lab2 >= 0, we're done. */
 282286                         break;
 283287         }
 284288         if (lab1 < 0 || lab2 < 0)
 285289                 comperr("deljumps");
 286290 
 287291 again:  gotone = 0;
 288292         memset(lblary, 0, sz);
 289293         lblary[lab1 - low] = lblary[lab2 - low] = 1;
 290294         memset(jmpary, 0, sz);
 291295 
 292296         /* refcount and coalesce all labels */
 293297         DLIST_FOREACH(ip, ipole, qelem) {
 294298                 if (ip->type == IP_DEFLAB && ip->ip_lbl != lab1 &&
 295299                     ip->ip_lbl != lab2) {
 296300                         n = DLIST_NEXT(ip, qelem);
 297301 
 298302                         /*
 299303                          * Find unconditional jumps directly following a
 300304                          * label.
 301305                          */
 302306                         if (n->type == IP_NODE && n->ip_node->n_op == GOTO) {
 303307                                 i = n->ip_node->n_left->n_lval;
 304308                                 jmpary[ip->ip_lbl - low] = i;
 305309                         }
 306310 
 307311                         while (n->type == IP_DEFLAB) {
 308312                                 if (n->ip_lbl != lab1 && n->ip_lbl != lab2 &&
 309313                                     lblary[n->ip_lbl-low] >= 0) {
 310314                                         /*
 311315                                          * If the label is used, mark the
 312316                                          * label to be coalesced with as
 313317                                          * used, too.
 314318                                          */
 315319                                         if (lblary[n->ip_lbl - low] > 0 &&
 316320                                             lblary[ip->ip_lbl - low] == 0)
 317321                                                 lblary[ip->ip_lbl - low] = 1;
 318322                                         lblary[n->ip_lbl - low] = -ip->ip_lbl;
 319323                                 }
 320324                                 n = DLIST_NEXT(n, qelem);
 321325                         }
 322326                 }
 323327                 if (ip->type != IP_NODE)
 324328                         continue;
 325329                 o = ip->ip_node->n_op;
 326330                 if (o == GOTO)
 327331                         i = ip->ip_node->n_left->n_lval;
 328332                 else if (o == CBRANCH)
 329333                         i = ip->ip_node->n_right->n_lval;
 330334                 else
 331335                         continue;
 332336 
 333337                 /*
 334338                  * Mark destination label i as used, if it is not already.
 335339                  * If i is to be merged with label j, mark j as used, too.
 336340                  */
 337341                 if (lblary[i - low] == 0)
 338342                         lblary[i-low] = 1;
 339343                 else if ((j = lblary[i - low]) < 0 && lblary[-j - low] == 0)
 340344                         lblary[-j - low] = 1;
 341345         }
 342346 
 343347         /* delete coalesced/unused labels and rename gotos */
 344348         DLIST_FOREACH(ip, ipole, qelem) {
 345349                 n = DLIST_NEXT(ip, qelem);
 346350                 if (n->type == IP_DEFLAB) {
 347351                         if (lblary[n->ip_lbl-low] <= 0) {
 348352                                 DLIST_REMOVE(n, qelem);
 349353                                 gotone = 1;
 350354                         }
 351355                 }
 352356                 if (ip->type != IP_NODE)
 353357                         continue;
 354358                 o = ip->ip_node->n_op;
 355359                 if (o == GOTO)
 356360                         i = ip->ip_node->n_left->n_lval;
 357361                 else if (o == CBRANCH)
 358362                         i = ip->ip_node->n_right->n_lval;
 359363                 else
 360364                         continue;
 361365 
 362366                 /* Simplify (un-)conditional jumps to unconditional jumps. */
 363367                 if (jmpary[i - low] > 0) {
 364368                         gotone = 1;
 365369                         i = jmpary[i - low];
 366370                         if (o == GOTO)
 367371                                 ip->ip_node->n_left->n_lval = i;
 368372                         else
 369373                                 ip->ip_node->n_right->n_lval = i;
 370374                 }
 371375 
 372376                 /* Fixup for coalesced labels. */
 373377                 if (lblary[i-low] < 0) {
 374378                         if (o == GOTO)
 375379                                 ip->ip_node->n_left->n_lval = -lblary[i-low];
 376380                         else
 377381                                 ip->ip_node->n_right->n_lval = -lblary[i-low];
 378382                 }
 379383         }
 380384 
 381385         /* Delete gotos to the next statement */
 382386         DLIST_FOREACH(ip, ipole, qelem) {
 383387                 n = DLIST_NEXT(ip, qelem);
 384388                 if (n->type != IP_NODE)
 385389                         continue;
 386390                 o = n->ip_node->n_op;
 387391                 if (o == GOTO)
 388392                         i = n->ip_node->n_left->n_lval;
 389393                 else if (o == CBRANCH)
 390394                         i = n->ip_node->n_right->n_lval;
 391395                 else
 392396                         continue;
 393397 
 394398                 ip2 = n;
 395399                 ip2 = DLIST_NEXT(ip2, qelem);
 396400 
 397401                 if (ip2->type != IP_DEFLAB)
 398402                         continue;
 399403                 if (ip2->ip_lbl == i && i != lab1 && i != lab2) {
 400404                         tfree(n->ip_node);
 401405                         DLIST_REMOVE(n, qelem);
 402406                         gotone = 1;
 403407                 }
 404408         }
 405409 
 406410         /*
 407411          * Transform cbranch cond, 1; goto 2; 1: ... into
 408412          * cbranch !cond, 2; 1: ...
 409413          */
 410414         DLIST_FOREACH(ip, ipole, qelem) {
 411415                 n = DLIST_NEXT(ip, qelem);
 412416                 ip2 = DLIST_NEXT(n, qelem);
 413417                 if (ip->type != IP_NODE || ip->ip_node->n_op != CBRANCH)
 414418                         continue;
 415419                 if (n->type != IP_NODE || n->ip_node->n_op != GOTO)
 416420                         continue;
 417421                 if (ip2->type != IP_DEFLAB)
 418422                         continue;
 419423                 i = ip->ip_node->n_right->n_lval;
 420424                 j = n->ip_node->n_left->n_lval;
 421425                 if (j == lab1 || j == lab2)
 422426                         continue;
 423427                 if (i != ip2->ip_lbl || i == lab1 || i == lab2)
 424428                         continue;
 425429                 ip->ip_node->n_right->n_lval = j;
 426430                 i = ip->ip_node->n_left->n_op;
 427431                 if (i < EQ || i - EQ >= negrelsize)
 428432                         comperr("deljumps: unexpected op");
 429433                 ip->ip_node->n_left->n_op = negrel[i - EQ];
 430434                 tfree(n->ip_node);
 431435                 DLIST_REMOVE(n, qelem);
 432436                 gotone = 1;
 433437         }
 434438 
 435439         /* Delete everything after a goto up to the next label. */
 436440         for (ip = start, del = 0; ip != DLIST_ENDMARK(ipole);
 437441              ip = DLIST_NEXT(ip, qelem)) {
 438442 loop:
 439443                 if ((n = DLIST_NEXT(ip, qelem)) == DLIST_ENDMARK(ipole))
 440444                         break;
 441445                 if (n->type != IP_NODE) {
 442446                         del = 0;
 443447                         continue;
 444448                 }
 445449                 if (del) {
 446450                         tfree(n->ip_node);
 447451                         DLIST_REMOVE(n, qelem);
 448452                         gotone = 1;
 449453                         goto loop;
 450454                 } else if (n->ip_node->n_op == GOTO)
 451455                         del = 1;
 452456         }
 453457 
 454458         if (gotone)
 455459                 goto again;
 456460 
 457461 #ifdef notyet
 458462         tmpfree(mark);
 459463 #endif
 460464 }
 461465 
 462466 void
 463467 optdump(struct interpass *ip)
 464468 {
 465469         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 466470                 "deflab", "defnam", "asm" };
 467471         printf("type %s\n", nm[ip->type-1]);
 468472         switch (ip->type) {
 469473         case IP_NODE:
 470474                 fwalk(ip->ip_node, e2print, 0);
 471475                 break;
 472476         case IP_DEFLAB:
 473477                 printf("label " LABFMT "\n", ip->ip_lbl);
 474478                 break;
 475479         case IP_ASM:
 476480                 printf(": %s\n", ip->ip_asm);
 477481                 break;
 478482         }
 479483 }
 480484 
 481485 /*
 482486  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 483487  *
 484488  * Also fills the labelinfo struct with information about which bblocks
 485489  * that contain which label.
 486490  */
 487491 
 488492 void
 489493 bblocks_build(struct interpass *ipole, struct labelinfo *labinfo,
 490494     struct bblockinfo *bbinfo)
 491495 {
 492496         struct interpass *ip;
 493497         struct basicblock *bb = NULL;
 494498         int low, high;
 495499         int count = 0;
 496500         int i;
 497501 
 498502         BDEBUG(("bblocks_build (%p, %p)\n", labinfo, bbinfo));
 499503         low = ipp->ip_lblnum;
 500504         high = epp->ip_lblnum;
 501505 
 502506         /*
 503507          * First statement is a leader.
 504508          * Any statement that is target of a jump is a leader.
 505509          * Any statement that immediately follows a jump is a leader.
 506510          */
 507511         DLIST_FOREACH(ip, ipole, qelem) {
 508512                 if (bb == NULL || (ip->type == IP_EPILOG) ||
 509513                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
 510514                         bb = tmpalloc(sizeof(struct basicblock));
 511515                         bb->first = ip;
 512516                         SLIST_INIT(&bb->children);
 513517                         SLIST_INIT(&bb->parents);
 514518                         bb->dfnum = 0;
 515519                         bb->dfparent = 0;
 516520                         bb->semi = 0;
 517521                         bb->ancestor = 0;
 518522                         bb->idom = 0;
 519523                         bb->samedom = 0;
 520524                         bb->bucket = NULL;
 521525                         bb->df = NULL;
 522526                         bb->dfchildren = NULL;
 523527                         bb->Aorig = NULL;
 524528                         bb->Aphi = NULL;
 525529                         bb->bbnum = count;
 526530                         DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
 527531                         count++;
 528532                 }
 529533                 bb->last = ip;
 530534                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO ||
 531535                     ip->ip_node->n_op == CBRANCH))
 532536                         bb = NULL;
 533537                 if (ip->type == IP_PROLOG)
 534538                         bb = NULL;
 535539         }
 536540         nbblocks = count;
 537541 
 538542         if (b2debug) {
 539543                 printf("Basic blocks in func: %d, low %d, high %d\n",
 540544                     count, low, high);
 541545                 DLIST_FOREACH(bb, &bblocks, bbelem) {
 542546                         printf("bb %p: first %p last %p\n", bb,
 543547                             bb->first, bb->last);
 544548                 }
 545549         }
 546550 
 547551         labinfo->low = low;
 548552         labinfo->size = high - low + 1;
 549553         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
 550554         for (i = 0; i < labinfo->size; i++) {
 551555                 labinfo->arr[i] = NULL;
 552556         }
 553557         
 554558         bbinfo->size = count + 1;
 555559         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
 556560         for (i = 0; i < bbinfo->size; i++) {
 557561                 bbinfo->arr[i] = NULL;
 558562         }
 559563 
 560564         /* Build the label table */
 561565         DLIST_FOREACH(bb, &bblocks, bbelem) {
 562566                 if (bb->first->type == IP_DEFLAB)
 563567                         labinfo->arr[bb->first->ip_lbl - low] = bb;
 564568         }
 565569 
 566570         if (b2debug) {
 567571                 printf("Label table:\n");
 568572                 for (i = 0; i < labinfo->size; i++)
 569573                         if (labinfo->arr[i])
 570574                                 printf("Label %d bblock %p\n", i+low,
 571575                                     labinfo->arr[i]);
 572576         }
 573577 }
 574578 
 575579 /*
 576580  * Build the control flow graph.
 577581  */
 578582 
 579583 void
 580584 cfg_build(struct labelinfo *labinfo)
 581585 {
 582586         /* Child and parent nodes */
 583587         struct cfgnode *cnode;
 584588         struct cfgnode *pnode;
 585589         struct basicblock *bb;
 586590         
 587591         DLIST_FOREACH(bb, &bblocks, bbelem) {
 588592 
 589593                 if (bb->first->type == IP_EPILOG) {
 590594                         break;
 591595                 }
 592596 
 593597                 cnode = tmpalloc(sizeof(struct cfgnode));
 594598                 pnode = tmpalloc(sizeof(struct cfgnode));
 595599                 pnode->bblock = bb;
 596600 
 597601                 if ((bb->last->type == IP_NODE) &&
 598602                     (bb->last->ip_node->n_op == GOTO) &&
 599603                     (bb->last->ip_node->n_left->n_op == ICON))  {
 600604                         if (bb->last->ip_node->n_left->n_lval - labinfo->low >
 601605                             labinfo->size) {
 602606                                 comperr("Label out of range: %d, base %d",
 603607                                         bb->last->ip_node->n_left->n_lval,
 604608                                         labinfo->low);
 605609                         }
 606610                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
 607611                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 608612                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 609613                         continue;
 610614                 }
 611615                 if ((bb->last->type == IP_NODE) &&
 612616                     (bb->last->ip_node->n_op == CBRANCH)) {
 613617                         if (bb->last->ip_node->n_right->n_lval - labinfo->low >
 614618                             labinfo->size)
 615619                                 comperr("Label out of range: %d",
 616620                                         bb->last->ip_node->n_left->n_lval);
 617621                         
 618622                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
 619623                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 620624                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 621625                         cnode = tmpalloc(sizeof(struct cfgnode));
 622626                         pnode = tmpalloc(sizeof(struct cfgnode));
 623627                         pnode->bblock = bb;
 624628                 }
 625629 
 626630                 cnode->bblock = DLIST_NEXT(bb, bbelem);
 627631                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 628632                 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 629633         }
 630634 }
 631635 
 632636 void
 633637 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 634638 {
 635639         struct cfgnode *cnode;
 636640         
 637641         if (bb->dfnum != 0)
 638642                 return;
 639643 
 640644         bb->dfnum = ++dfsnum;
 641645         bb->dfparent = parent;
 642646         bbinfo->arr[bb->dfnum] = bb;
 643647         SLIST_FOREACH(cnode, &bb->children, cfgelem) {
 644648                 cfg_dfs(cnode->bblock, bb->dfnum, bbinfo);
 645649         }
 646650         /* Don't bring in unreachable nodes in the future */
 647651         bbinfo->size = dfsnum + 1;
 648652 }
 649653 
 650654 static bittype *
 651655 setalloc(int nelem)
 652656 {
 653657         bittype *b;
 654658         int sz = (nelem+NUMBITS-1)/NUMBITS;
 655659 
 656660         b = tmpalloc(sz * sizeof(bittype));
 657661         memset(b, 0, sz * sizeof(bittype));
 658662         return b;
 659663 }
 660664 
 661665 /*
 662666  * Algorithm 19.9, pp 414 from Appel.
 663667  */
 664668 
 665669 void
 666670 dominators(struct bblockinfo *bbinfo)
 667671 {
 668672         struct cfgnode *cnode;
 669673         struct basicblock *bb, *y, *v;
 670674         struct basicblock *s, *sprime, *p;
 671675         int h, i;
 672676 
 673677         DLIST_FOREACH(bb, &bblocks, bbelem) {
 674678                 bb->bucket = setalloc(bbinfo->size);
 675679                 bb->df = setalloc(bbinfo->size);
 676680                 bb->dfchildren = setalloc(bbinfo->size);
 677681         }
 678682 
 679683         dfsnum = 0;
 680684         cfg_dfs(DLIST_NEXT(&bblocks, bbelem), 0, bbinfo);
 681685 
 682686         if (b2debug) {
 683687                 struct basicblock *bbb;
 684688                 struct cfgnode *ccnode;
 685689 
 686690                 DLIST_FOREACH(bbb, &bblocks, bbelem) {
 687691                         printf("Basic block %d, parents: ", bbb->dfnum);
 688692                         SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
 689693                                 printf("%d, ", ccnode->bblock->dfnum);
 690694                         }
 691695                         printf("\nChildren: ");
 692696                         SLIST_FOREACH(ccnode, &bbb->children, cfgelem) {
 693697                                 printf("%d, ", ccnode->bblock->dfnum);
 694698                         }
 695699                         printf("\n");
 696700                 }
 697701         }
 698702 
 699703         for(h = bbinfo->size - 1; h > 1; h--) {
 700704                 bb = bbinfo->arr[h];
 701705                 p = s = bbinfo->arr[bb->dfparent];
 702706                 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
 703707                         if (cnode->bblock->dfnum <= bb->dfnum)
 704708                                 sprime = cnode->bblock;
 705709                         else
 706710                                 sprime = bbinfo->arr[ancestorwithlowestsemi
 707711                                               (cnode->bblock, bbinfo)->semi];
 708712                         if (sprime->dfnum < s->dfnum)
 709713                                 s = sprime;
 710714                 }
 711715                 bb->semi = s->dfnum;
 712716                 BITSET(s->bucket, bb->dfnum);
 713717                 link(p, bb);
 714718                 for (i = 1; i < bbinfo->size; i++) {
 715719                         if(TESTBIT(p->bucket, i)) {
 716720                                 v = bbinfo->arr[i];
 717721                                 y = ancestorwithlowestsemi(v, bbinfo);
 718722                                 if (y->semi == v->semi)
 719723                                         v->idom = p->dfnum;
 720724                                 else
 721725                                         v->samedom = y->dfnum;
 722726                         }
 723727                 }
 724728                 memset(p->bucket, 0, (bbinfo->size + 7)/8);
 725729         }
 726730 
 727731         if (b2debug) {
 728732                 printf("Num\tSemi\tAncest\tidom\n");
 729733                 DLIST_FOREACH(bb, &bblocks, bbelem) {
 730734                         printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi,
 731735                             bb->ancestor, bb->idom);
 732736                 }
 733737         }
 734738 
 735739         for(h = 2; h < bbinfo->size; h++) {
 736740                 bb = bbinfo->arr[h];
 737741                 if (bb->samedom != 0) {
 738742                         bb->idom = bbinfo->arr[bb->samedom]->idom;
 739743                 }
 740744         }
 741745         DLIST_FOREACH(bb, &bblocks, bbelem) {
 742746                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
 743747                         BDEBUG(("Setting child %d of %d\n",
 744748                             bb->dfnum, bbinfo->arr[bb->idom]->dfnum));
 745749                         BITSET(bbinfo->arr[bb->idom]->dfchildren, bb->dfnum);
 746750                 }
 747751         }
 748752 }
 749753 
 750754 
 751755 struct basicblock *
 752756 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 753757 {
 754758         struct basicblock *u = bblock;
 755759         struct basicblock *v = bblock;
 756760 
 757761         while (v->ancestor != 0) {
 758762                 if (bbinfo->arr[v->semi]->dfnum <
 759763                     bbinfo->arr[u->semi]->dfnum)
 760764                         u = v;
 761765                 v = bbinfo->arr[v->ancestor];
 762766         }
 763767         return u;
 764768 }
 765769 
 766770 void
 767771 link(struct basicblock *parent, struct basicblock *child)
 768772 {
 769773         child->ancestor = parent->dfnum;
 770774 }
 771775 
 772776 void
 773777 computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo)
 774778 {
 775779         struct cfgnode *cnode;
 776780         int h, i;
 777781         
 778782         SLIST_FOREACH(cnode, &bblock->children, cfgelem) {
 779783                 if (cnode->bblock->idom != bblock->dfnum)
 780784                         BITSET(bblock->df, cnode->bblock->dfnum);
 781785         }
 782786         for (h = 1; h < bbinfo->size; h++) {
 783787                 if (!TESTBIT(bblock->dfchildren, h))
 784788                         continue;
 785789                 computeDF(bbinfo->arr[h], bbinfo);
 786790                 for (i = 1; i < bbinfo->size; i++) {
 787791                         if (TESTBIT(bbinfo->arr[h]->df, i) &&
 788792                             (bbinfo->arr[h] == bblock ||
 789793                              (bblock->idom != bbinfo->arr[h]->dfnum)))
 790794                             BITSET(bblock->df, i);
 791795                 }
 792796         }
 793797 }
 794798 
 795799 static struct basicblock *currbb;
 796800 static struct interpass *currip;
 797801 
 798802 /* Helper function for findTemps, Find assignment nodes. */
 799803 static void
 800804 searchasg(NODE *p)
 801805 {
 802806         struct pvarinfo *pv;
 803807 
 804808         if (p->n_op != ASSIGN)
 805809                 return;
 806810 
 807811         if (p->n_left->n_op != TEMP)
 808812                 return;
 809813 
 810814         pv = tmpcalloc(sizeof(struct pvarinfo));
 811815         pv->next = defsites.arr[p->n_left->n_lval];
 812816         pv->bb = currbb;
 813817         pv->top = currip->ip_node;
 814818         pv->n = p->n_left;
 815819         BITSET(currbb->Aorig, p->n_left->n_lval);
 816820 
 817821         defsites.arr[p->n_left->n_lval] = pv;
 818822 }
 819823 
 820824 /* Walk the interpass looking for assignment nodes. */
 821825 void findTemps(struct interpass *ip)
 822826 {
 823827         if (ip->type != IP_NODE)
 824828                 return;
 825829 
 826830         currip = ip;
 827831 
 828832         walkf(ip->ip_node, searchasg);
 829833 }
 830834 
 831835 /*
 832836  * Algorithm 19.6 from Appel.
 833837  */
 834838 
 835839 void
 836840 placePhiFunctions(struct bblockinfo *bbinfo)
 837841 {
 838842         struct basicblock *bb;
 839843         struct interpass *ip;
 840844         int maxtmp, i, j, k, l;
 841845         struct pvarinfo *n;
 842846         struct cfgnode *cnode;
 843847         TWORD ntype;
 844848         NODE *p;
 845849         struct pvarinfo *pv;
 846850 
 847851         bb = DLIST_NEXT(&bblocks, bbelem);
 848852         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 849853         bb = DLIST_PREV(&bblocks, bbelem);
 850854         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 851855         defsites.size = maxtmp - defsites.low + 1;
 852856         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
 853857 
 854858         /* Find all defsites */
 855859         DLIST_FOREACH(bb, &bblocks, bbelem) {
 856860                 currbb = bb;
 857861                 ip = bb->first;
 858862                 bb->Aorig = setalloc(defsites.size);
 859863                 bb->Aphi = setalloc(defsites.size);
 860864                 
 861865 
 862866                 while (ip != bb->last) {
 863867                         findTemps(ip);
 864868                         ip = DLIST_NEXT(ip, qelem);
 865869                 }
 866870                 /* Make sure we get the last statement in the bblock */
 867871                 findTemps(ip);
 868872         }
 869873         /* For each variable */
 870874         for (i = defsites.low; i < defsites.size; i++) {
 871875                 /* While W not empty */
 872876                 while (defsites.arr[i] != NULL) {
 873877                         /* Remove some node n from W */
 874878                         n = defsites.arr[i];
 875879                         defsites.arr[i] = n->next;
 876880                         /* For each y in n->bb->df */
 877881                         for (j = 0; j < bbinfo->size; j++) {
 878882                                 if (!TESTBIT(n->bb->df, j))
 879883                                         continue;
 880884                                 
 881885                                 if (TESTBIT(bbinfo->arr[j]->Aphi, i))
 882886                                         continue;
 883887 
 884888                                 ntype = n->n->n_type;
 885889                                 k = 0;
 886890                                 /* Amount of predecessors for y */
 887891                                 SLIST_FOREACH(cnode, &n->bb->parents, cfgelem)
 888892                                         k++;
 889893                                 /* Construct phi(...) */
<>890 -                                p = mklnode(TEMP, i, 0, ntype);
  894+                                p = mktemp(i, ntype);
891895                                 for (l = 0; l < k-1; l++)
 892896                                         p = mkbinode(PHI, p,
<>893 -                                            mklnode(TEMP, i, 0, ntype), ntype);
  897+                                            mktemp(i, ntype), ntype);
894898                                 ip = ipnode(mkbinode(ASSIGN,
<>895 -                                    mklnode(TEMP, i, 0, ntype), p, ntype));
  899+                                    mktemp(i, ntype), p, ntype));
<_896900                                 /* Insert phi at top of basic block */
 897901                                 DLIST_INSERT_BEFORE(((struct interpass*)&n->bb->first), ip, qelem);
 898902                                 n->bb->first = ip;
 899903                                 BITSET(bbinfo->arr[j]->Aphi, i);
 900904                                 if (!TESTBIT(bbinfo->arr[j]->Aorig, i)) {
 901905                                         pv = tmpalloc(sizeof(struct pvarinfo));
 902906                                         // XXXpj Ej fullständig information.
 903907                                         pv->bb = bbinfo->arr[j];
 904908                                         pv->next = defsites.arr[i]->next;
 905909                                         defsites.arr[i] = pv;
 906910                                 }
 907911                                         
 908912 
 909913                         }
 910914                 }
 911915         }
 912916 }
 913917 
 914918 /*
 915919  * Remove unreachable nodes in the CFG.
 916920  */
 917921 
 918922 void
 919923 remunreach(void)
 920924 {
 921925         struct basicblock *bb, *nbb;
 922926         struct interpass *next, *ctree;
 923927 
 924928         bb = DLIST_NEXT(&bblocks, bbelem);
 925929         while (bb != &bblocks) {
 926930                 nbb = DLIST_NEXT(bb, bbelem);
 927931 
 928932                 /* Code with dfnum 0 is unreachable */
 929933                 if (bb->dfnum != 0) {
 930934                         bb = nbb;
 931935                         continue;
 932936                 }
 933937 
 934938                 /* Need the epilogue node for other parts of the
 935939                    compiler, set its label to 0 and backend will
 936940                    handle it. */
 937941                 if (bb->first->type == IP_EPILOG) {
 938942                         bb->first->ip_lbl = 0;
 939943                         bb = nbb;
 940944                         continue;
 941945                 }
 942946 
 943947                 next = bb->first;
 944948                 do {
 945949                         ctree = next;
 946950                         next = DLIST_NEXT(ctree, qelem);
 947951                         
 948952                         if (ctree->type == IP_NODE)
 949953                                 tfree(ctree->ip_node);
 950954                         DLIST_REMOVE(ctree, qelem);
 951955                 } while (ctree != bb->last);
 952956                         
 953957                 DLIST_REMOVE(bb, bbelem);
 954958                 bb = nbb;
 955959         }
 956960 }
 957961 
 958962 void
 959963 printip(struct interpass *pole)
 960964 {
 961965         static char *foo[] = {
 962966            0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
 963967         struct interpass *ip;
 964968         struct interpass_prolog *ipp, *epp;
 965969 
 966970         DLIST_FOREACH(ip, pole, qelem) {
 967971                 if (ip->type > MAXIP)
 968972                         printf("IP(%d) (%p): ", ip->type, ip);
 969973                 else
 970974                         printf("%s (%p): ", foo[ip->type], ip);
 971975                 switch (ip->type) {
 972976                 case IP_NODE: printf("\n");
 973977                         fwalk(ip->ip_node, e2print, 0); break;
 974978                 case IP_PROLOG:
 975979                         ipp = (struct interpass_prolog *)ip;
 976980                         printf("%s %s regs %x autos %d mintemp %d minlbl %d\n",
 977981                             ipp->ipp_name, ipp->ipp_vis ? "(local)" : "",
 978982                             ipp->ipp_regs, ipp->ipp_autos, ipp->ip_tmpnum,
 979983                             ipp->ip_lblnum);
 980984                         break;
 981985                 case IP_EPILOG:
 982986                         epp = (struct interpass_prolog *)ip;
 983987                         printf("%s %s regs %x autos %d mintemp %d minlbl %d\n",
 984988                             epp->ipp_name, epp->ipp_vis ? "(local)" : "",
 985989                             epp->ipp_regs, epp->ipp_autos, epp->ip_tmpnum,
 986990                             epp->ip_lblnum);
 987991                         break;
 988992                 case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
 989993                 case IP_DEFNAM: printf("\n"); break;
 990994                 case IP_ASM: printf("%s\n", ip->ip_asm); break;
 991995                 default:
 992996                         break;
 993997                 }
 994998         }
 995999 }
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-09-19 21:53 +0200