Quick Search:

Mode

Context

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

Other Diffs

Ignore

Blank Lines Whitespace: Expand:

Diff

1.24
 
1.25
 
MAIN:ragge:20050618113013
 
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 extern int saving;
 4343 static int dfsnum;
 4444 
 4545 void saveip(struct interpass *ip);
 4646 void deljumps(void);
 4747 void deltemp(NODE *p);
 4848 void optdump(struct interpass *ip);
 4949 void printip(struct interpass *pole);
 5050 
 5151 static struct varinfo defsites;
 5252 static struct interpass ipole;
 5353 struct interpass *storesave;
 5454 
 5555 static struct rsv {
 5656         struct rsv *next;
 5757         int fpoff;
 5858         TWORD type;
 5959         int use;
 6060 } *rsv;
 6161 
 6262 int bblocks_build(struct labelinfo *labinfo, struct bblockinfo *bbinfo);
 6363 void cfg_build(struct labelinfo *labinfo);
 6464 void cfg_dfs(struct basicblock *bb, unsigned int parent,
 6565              struct bblockinfo *bbinfo);
 6666 void dominators(struct bblockinfo *bbinfo);
 6767 struct basicblock *
 6868 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo);
 6969 void link(struct basicblock *parent, struct basicblock *child);
 7070 void computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo);
 7171 void findTemps(struct interpass *ip);
 7272 void placePhiFunctions(struct bblockinfo *bbinfo);
 7373 void remunreach(void);
 7474 
 7575 static struct basicblock bblocks;
 7676 
 7777 static void
 7878 addcand(TWORD type, int off, int avoid)
 7979 {
 8080         struct rsv *w = rsv;
 8181 
 8282         while (w != NULL) {
 8383                 if (w->type == type && w->fpoff == off) {
 8484                         if (avoid)
 8585                                 w->use = -1;
 8686                         else if (w->use > 0)
 8787                                 w->use++;
 8888                         return;
 8989                 }
 9090                 w = w->next;
 9191         }
 9292         w = tmpalloc(sizeof(*w));
 9393         w->type = type;
 9494         w->fpoff = off;
 9595         w->use = avoid ? -1 : 1;
 9696         w->next = rsv;
 9797         rsv = w;
 9898 }
 9999 
 100100 /*
 101101  * walk through the tree and count the number of (possible)
 102102  * temporary nodes.
 103103  */
 104104 static void
 105105 cntuse(NODE *p)
 106106 {
 107107         NODE *l = p->n_left;
 108108         NODE *r = p->n_right;
 109109 
 110110         if (p->n_op == UMUL && l->n_op == REG && l->n_rval == FPREG) {
 111111                 /* found a candidate for register */
 112112                 addcand(p->n_type, 0, ISVOL(p->n_qual << TSHIFT));
 113113         } else if (p->n_op == UMUL && l->n_op == PLUS &&
 114114             l->n_right->n_op == ICON &&
 115115              (l->n_left->n_op == REG && l->n_left->n_rval == FPREG)) {
 116116                 /* The same as above */
 117117                 addcand(p->n_type, l->n_right->n_lval,
 118118                     ISVOL(p->n_qual << TSHIFT));
 119119         } else if (p->n_op == PLUS && l->n_op == REG && l->n_rval == FPREG &&
 120120             p->n_right->n_op == ICON) {
 121121                 /* Address taken of temporary, avoid register */
 122122                 addcand(DECREF(p->n_type), r->n_lval, 1);
 123123         } else {
 124124                 if (optype(p->n_op) == BITYPE)
 125125                         cntuse(r);
 126126                 if (optype(p->n_op) != LTYPE)
 127127                         cntuse(l);
 128128         }
 129129 }
 130130 
 131131 /*
 132132  * Insert a node into the register stack.
 133133  */
 134134 static void
 135135 insert(struct rsv *w, struct rsv **saved, int maxregs)
 136136 {
 137137         int i, j, size;
 138138 
 139139         size = szty(w->type);
 140140 
 141141         /* Find reg move position */
 142142         for (i = 0; i < maxregs; i++) {
 143143                 if (saved[i] == NULL)
 144144                         continue;
 145145                 if (saved[i]->use > w->use)
 146146                         break;
 147147         }
 148148         /* Move down other regs */
 149149         for (j = size; j < i; j++)
 150150                 saved[j-size] = saved[j];
 151151 
 152152         /* Insert new reg pointer */
 153153         if (i-size >= 0) {
 154154                 saved[i-size] = w;
 155155                 for (j = i-size+1; j < i; j++)
 156156                         saved[j] = NULL;
 157157         }
 158158 }
 159159 
 160160 /* Help routine to rconvert() */
 161161 static int
 162162 matches(TWORD type, int off, struct rsv **rsv, int maxregs)
 163163 {
 164164         int i;
 165165 
 166166         for (i = 0; i < maxregs; i++)
 167167                 if (rsv[i] && rsv[i]->type == type && rsv[i]->fpoff == off)
 168168                         return i;
 169169         return -1;
 170170 }
 171171 
 172172 /* Help routine to rconvert() */
 173173 static void
 174174 modify(NODE *p, int reg)
 175175 {
 176176         tfree(p->n_left);
 177177         p->n_op = REG;
 178178         p->n_rval = p->n_rall = reg + MINRVAR;
 179179         p->n_lval = 0;
 180180 }
 181181 
 182182 /*
 183183  * walk through the tree and convert nodes to registers
 184184  */
 185185 static void
 186186 rconvert(NODE *p, struct rsv **rsv, int maxregs)
 187187 {
 188188         NODE *l = p->n_left;
 189189         NODE *r = p->n_right;
 190190         int i;
 191191 
 192192         if (p->n_op == UMUL && l->n_op == REG && l->n_rval == FPREG) {
 193193                 /* found a candidate for register */
 194194                 if ((i = matches(p->n_type, 0, rsv, maxregs)) >= 0)
 195195                         modify(p, i);
 196196         } else if (p->n_op == UMUL && l->n_op == PLUS &&
 197197             l->n_right->n_op == ICON &&
 198198              (l->n_left->n_op == REG && l->n_left->n_rval == FPREG)) {
 199199                 /* The same as above */
 200200                 if ((i = matches(p->n_type,
 201201                     l->n_right->n_lval, rsv, maxregs)) >= 0)
 202202                         modify(p, i);
 203203 #if 0
 204204         } else if (p->n_op == PLUS && l->n_op == REG && l->n_rval == FPREG &&
 205205             p->n_right->n_op == ICON) {
 206206                 /* Address taken of temporary, avoid register */
 207207                 addcand(DECREF(p->n_type), r->n_lval, 1);
 208208 #endif
 209209         } else {
 210210                 if (optype(p->n_op) == BITYPE)
 211211                         rconvert(r, rsv, maxregs);
 212212                 if (optype(p->n_op) != LTYPE)
 213213                         rconvert(l, rsv, maxregs);
 214214         }
 215215 }
 216216 
 217217 /*
 218218  * Assign non-temporary registers to variables.
 219219  * Cannot do it if:
 220220  * - address is taken of the temporary
 221221  * - variable is declared "volatile".
 222222  */
 223223 int asgregs(void);
 224224 int
 225225 asgregs(void)
 226226 {
 227227         struct interpass *ip;
 228228         struct rsv *w, **saved;
 229229         int i, maxregs = MAXRVAR - MINRVAR + 1;
 230230 
 231231         if (maxregs == 0)
 232232                 return MAXRVAR; /* No register usage */
 233233         rsv = NULL;
 234234 
 235235         /* Loop over the function to do a usage count */
 236236         DLIST_FOREACH(ip, &ipole, qelem) {
 237237                 if (ip->type != IP_NODE)
 238238                         continue;
 239239                 cntuse(ip->ip_node);
 240240         }
 241241         /* Check which nodes that shall be converted to registers */
 242242         saved = tmpalloc(sizeof(struct rsv *) * maxregs);
 243243         memset(saved, 0, sizeof(struct rsv *) * maxregs);
 244244         w = rsv;
 245245         for (w = rsv; w; w = w->next) {
 246246                 if (w->use < 0)
 247247                         continue; /* Not allowed to be in register */
 248248 
 249249                 /* XXX check here if type is allowed to be in register */
 250250 
 251251                 insert(w, saved, maxregs);
 252252         }
 253253 
 254254         /* Convert found nodes to registers */
 255255         DLIST_FOREACH(ip, &ipole, qelem) {
 256256                 if (ip->type != IP_NODE)
 257257                         continue;
 258258                 rconvert(ip->ip_node, saved, maxregs);
 259259         }
 260260         for (i = 0; i < maxregs; i++)
 261261                 if (saved[i] != NULL)
 262262                         break;
 263263         return MINRVAR+i-1;
 264264 }
 265265 
 266266 void
 267267 saveip(struct interpass *ip)
 268268 {
 269269         struct interpass_prolog *ipp, *epp;
 270270         static int inftn;
 271271 
 272272 #if 0
 273273         int regs;
 274274 #endif
 275275         struct labelinfo labinfo;
 276276         struct bblockinfo bbinfo;
 277277 
 278278         if (ip->type == IP_PROLOG) {
 279279                 DLIST_INIT(&ipole, qelem);
 280280                 inftn = 1;
 281281         } else if (inftn == 0)
 282282                 comperr("saveip");
 283283 
 284284         DLIST_INSERT_BEFORE(&ipole, ip, qelem);
 285285 
 286286         if (ip->type != IP_EPILOG)
 287287                 return;
 288288         inftn = 0;
 289289         epp = (struct interpass_prolog *)ip;
 290290         saving = -1;
 291291 
 292292         //              deljumps();     /* Delete redundant jumps and dead code */
 293293         if (xssaflag) {
 294294                 DLIST_INIT(&bblocks, bbelem);
 295295                 if (bblocks_build(&labinfo, &bbinfo)) {
 296296                         cfg_build(&labinfo);
 297297                         dominators(&bbinfo);
 298298                         computeDF(DLIST_NEXT(&bblocks, bbelem), &bbinfo);
 299299                         remunreach();
 300300 #if 0
 301301                         if (xssaflag) {
 302302                                 dfg = dfg_build(cfg);
 303303                                 ssa = ssa_build(cfg, dfg);
 304304                         }
 305305 #endif
 306306                 }
 307307  
 308308         }
 309309 #if 0
 310310         regs = asgregs();       /* Assign non-temporary registers */
 311311 #endif
 312312 
 313313 #ifdef PCC_DEBUG
 314314         if (epp->ipp_regs != MAXRVAR)
 315315                 comperr("register error");
 316316 #endif
 317317 
 318318         ipp = (struct interpass_prolog *)DLIST_NEXT(&ipole, qelem);
 319319         ipp->ipp_autos = epp->ipp_autos;
 320320         ipp->ipp_regs = epp->ipp_regs; // = regs;
 321321 
 322322 #ifdef MYOPTIM
 323323         myoptim((struct interpass *)ipp);
 324324 #endif
 325325 
 326326 if (xnewreg == 0) {
 327327         int tmpautooff;
 328328         NODE *p;
 329329 
 330330         p2autooff = p2maxautooff = AUTOINIT;
 331331         /* Must verify stack usage first */
 332332         DLIST_FOREACH(ip, &ipole, qelem) {
 333333                 if (ip->type == IP_STKOFF) {
 334334                         p2autooff = ip->ip_off;
 335335                         if (p2autooff > p2maxautooff)
 336336                                 p2maxautooff = p2autooff;
 337337                 }
 338338         }
 339339         p2autooff = p2maxautooff; /* don't have live range analysis yet */
 340340 
 341341         DLIST_FOREACH(ip, &ipole, qelem) {
 342342                 if (ip->type == IPSTK) {
 343343                         struct interpass *ip3;
 344344                         p2autooff = ip->ip_off;
 345345                         ip3 = ip;
 346346                         ip = DLIST_NEXT(ip, qelem);
 347347                         DLIST_REMOVE(ip3, qelem);
 348348                 }
 349349                         
 350350                 if (ip->type != IP_NODE)
 351351                         continue;
 352352 
 353353                 p = ip->ip_node;
 354354                 walkf(p, deltemp);
 355355 
 356356                 tmpautooff = p2autooff;
 357357 
 358358                 geninsn(p, FOREFF);
 359359                 if (sucomp(p) < 0) {
 360360                         /* Create STKOFF entry */
 361361                         struct interpass *ip3;
 362362                         DLIST_INSERT_BEFORE(ip, storesave, qelem);
 363363                         ip3 = ipnode(NULL);
 364364                         ip3->type = IPSTK;
 365365                         ip3->ip_off = tmpautooff;
 366366                         DLIST_INSERT_AFTER(ip, ip3, qelem);
 367367                         ip = DLIST_PREV(storesave, qelem);
 368368                         continue;
 369369                 }
 370370 
 371371                 p2autooff = tmpautooff;
 372372 
 373373                 genregs(p);
 374374                 mygenregs(p);
 375375         }
 376376 
 377377 } else {
 378378         /*
 379379          * Loop over instruction assignment until the register assignment
 380380          * code is satisfied.
 381381          */
<> 382+#if 0
  383+        extern int tempmin, tempmax;
  384+
  385+        tempmin = ip->ip_tmpnum;
  386+        tempmin = ie->ip_tmpnum;
  387+#endif
<_382388         do {
 383389                 /* do instruction assignment */
 384390                 DLIST_FOREACH(ip, &ipole, qelem) {
 385391                         if (ip->type != IP_NODE)
 386392                                 continue;
 387393                         geninsn(ip->ip_node, FOREFF);
 388394                         nsucomp(ip->ip_node);
 389395                 }
 390396         } while (ngenregs(DLIST_NEXT(&ipole, qelem),
 391397             DLIST_PREV(&ipole, qelem)));
 392398 }
 393399 
 394400         DLIST_FOREACH(ip, &ipole, qelem) {
 395401                 emit(ip);
 396402         }
 397403         DLIST_INIT(&ipole, qelem);
 398404 }
 399405 
 400406 void
 401407 deljumps()
 402408 {
 403409         struct interpass *ip, *n;
 404410         int gotone;
 405411 
 406412 again:  gotone = 0;
 407413 
 408414         DLIST_FOREACH(ip, &ipole, qelem) {
 409415                 if (ip->type == IP_EPILOG)
 410416                         return;
 411417                 if (ip->type != IP_NODE)
 412418                         continue;
 413419                 n = DLIST_NEXT(ip, qelem);
 414420                 /* Check for nodes without side effects */
 415421                 if (ip->ip_node->n_op != GOTO)
 416422                         continue;
 417423                 switch (n->type) {
 418424                 case IP_NODE:
 419425                         tfree(n->ip_node);
 420426                         DLIST_REMOVE(n, qelem);
 421427                         break;
 422428                 case IP_DEFLAB:
 423429                         if (ip->ip_node->n_left->n_lval != n->ip_lbl)
 424430                                 continue;
 425431                         tfree(ip->ip_node);
 426432                         *ip = *n;
 427433                         break;
 428434                 default:
 429435                         continue;
 430436                 }
 431437                 gotone = 1;
 432438         }
 433439         if (gotone)
 434440                 goto again;
 435441 }
 436442 
 437443 void
 438444 optdump(struct interpass *ip)
 439445 {
 440446         static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
 441447                 "deflab", "defnam", "asm" };
 442448         printf("type %s\n", nm[ip->type-1]);
 443449         switch (ip->type) {
 444450         case IP_NODE:
 445451                 fwalk(ip->ip_node, e2print, 0);
 446452                 break;
 447453         case IP_DEFLAB:
 448454                 printf("label " LABFMT "\n", ip->ip_lbl);
 449455                 break;
 450456         case IP_ASM:
 451457                 printf(": %s\n", ip->ip_asm);
 452458                 break;
 453459         }
 454460 }
 455461 
 456462 /*
 457463  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
 458464  *
 459465  * Also fills the labelinfo struct with information about which bblocks
 460466  * that contain which label.
 461467  */
 462468 
 463469 int
 464470 bblocks_build(struct labelinfo *labinfo, struct bblockinfo *bbinfo)
 465471 {
 466472         struct interpass *ip;
 467473         struct basicblock *bb = NULL;
 468474         int leader = 1;
 469475         unsigned int low, high = 0;
 470476         int count = 0;
 471477         int i;
 472478 
 473479         low = sizeof(int) == 2 ? 65000 : 1000000000;
 474480         /*
 475481          * First statement is a leader.
 476482          * Any statement that is target of a jump is a leader.
 477483          * Any statement that immediately follows a jump is a leader.
 478484          */
 479485 
 480486         DLIST_FOREACH(ip, &ipole, qelem) {
 481487                 /* Garbage, skip it */
 482488                 if (leader) {
 483489                         bb = tmpalloc(sizeof(struct basicblock));
 484490                         bb->first = bb->last = ip;
 485491                         SLIST_INIT(&bb->children);
 486492                         SLIST_INIT(&bb->parents);
 487493                         bb->dfnum = 0;
 488494                         bb->dfparent = 0;
 489495                         bb->semi = 0;
 490496                         bb->ancestor = 0;
 491497                         bb->idom = 0;
 492498                         bb->samedom = 0;
 493499                         bb->bucket = NULL;
 494500                         bb->df = NULL;
 495501                         bb->dfchildren = NULL;
 496502                         bb->Aorig = NULL;
 497503                         bb->Aphi = NULL;
 498504                         DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
 499505                         leader = 0;
 500506                         count++;
 501507                 }
 502508                 
 503509                 /* Prologue and epilogue in their own bblock */
 504510                 if ((ip->type == IP_PROLOG) || (ip->type == IP_EPILOG)) {
 505511                         bb->last = ip;
 506512                         if (ip->type == IP_EPILOG)
 507513                                 high = MAX(ip->ip_lbl, high);
 508514                         leader = 1;
 509515                         continue;
 510516                 }
 511517                 
 512518                 /* Keep track of highest and lowest label number */
 513519                 if (ip->type == IP_DEFLAB) {
 514520                         low = MIN(ip->ip_lbl, low);
 515521                         high = MAX(ip->ip_lbl, high);
 516522                 }
 517523 
 518524                 /* Make sure each label is in a unique bblock */
 519525                 if (((ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) &&
 520526                     bb->first != ip) {
 521527                         bb = tmpalloc(sizeof(struct basicblock));
 522528                         bb->first = bb->last = ip;
 523529                         SLIST_INIT(&bb->children);
 524530                         SLIST_INIT(&bb->parents);
 525531                         bb->dfnum = 0;
 526532                         bb->dfparent = 0;
 527533                         bb->semi = 0;
 528534                         bb->ancestor = 0;
 529535                         bb->idom = 0;
 530536                         bb->samedom = 0;
 531537                         bb->bucket = NULL;
 532538                         bb->df = NULL;
 533539                         bb->dfchildren = NULL;
 534540                         bb->Aorig = NULL;
 535541                         bb->Aphi = NULL;
 536542                         DLIST_INSERT_BEFORE(&bblocks, bb, bbelem);
 537543                         count++;
 538544                         continue;
 539545                 }
 540546 
 541547                 if (ip->type == IP_ASM)
 542548                         return 0;
 543549 
 544550                 if (ip->type == IP_NODE) {
 545551                         switch(ip->ip_node->n_op) {
 546552                         case CBRANCH:
 547553                         case GOTO:
 548554                         case RETURN:
 549555                                 /* Jumps, last in bblock. */
 550556                                 leader = 1;
 551557                                 break;
 552558 
 553559                         case NAME:
 554560                         case ICON:
 555561                         case FCON:
 556562                         case REG:
 557563                         case OREG:
 558564                         case MOVE:
 559565                         case PLUS:
 560566                         case MINUS:
 561567                         case DIV:
 562568                         case MOD:
 563569                         case MUL:
 564570                         case AND:
 565571                         case OR:
 566572                         case ER:
 567573                         case LS:
 568574                         case COMPL:
 569575                         case INCR:
 570576                         case DECR:
 571577                         case UMUL:
 572578                         case UMINUS:
 573579                         case EQ:
 574580                         case NE:
 575581                         case LE:
 576582                         case GE:
 577583                         case GT:
 578584                         case ULE:
 579585                         case ULT:
 580586                         case UGE:
 581587                         case UGT:
 582588                         case ASSIGN:
 583589                         case FORCE:
 584590                         case FUNARG:
 585591                         case CALL:
 586592                         case UCALL:
 587593                         case FORTCALL:
 588594                         case UFORTCALL:
 589595                         case STCALL:
 590596                         case USTCALL:
 591597                                 /* Not jumps, continue with bblock. */
 592598                                 break;
 593599 
 594600                         default:
 595601                                 comperr("optim2:bblocks_build() %d",ip->ip_node->n_op );
 596602                                 break;
 597603                         }
 598604                 }
 599605 
 600606                 bb->last = ip;
 601607         }
 602608 #if 0
 603609         printf("Basic blocks in func: %d\n", count);
 604610         printf("Label range in func: %d\n", high - low + 1);
 605611 #endif
 606612 
 607613         labinfo->low = low;
 608614         labinfo->size = high - low + 1;
 609615         labinfo->arr = tmpalloc(labinfo->size * sizeof(struct basicblock *));
 610616         for (i = 0; i <= labinfo->size; i++) {
 611617                 labinfo->arr[i] = NULL;
 612618         }
 613619         
 614620         bbinfo->size = count + 1;
 615621         bbinfo->arr = tmpalloc(bbinfo->size * sizeof(struct basicblock *));
 616622         for (i = 0; i <= bbinfo->size; i++) {
 617623                 bbinfo->arr[i] = NULL;
 618624         }
 619625 
 620626         DLIST_FOREACH(bb, &bblocks, bbelem) {
 621627                 /* Build the label table */
 622628                 if (bb->first->type == IP_DEFLAB) {
 623629                         labinfo->arr[bb->first->ip_lbl - low] = bb;
 624630                 }
 625631                 if (bb->first->type == IP_EPILOG) {
 626632                         labinfo->arr[bb->first->ip_lbl - low] = bb;
 627633                 }
 628634         }
 629635 
 630636         return 1;
 631637 }
 632638 
 633639 /*
 634640  * Build the control flow graph.
 635641  */
 636642 
 637643 void
 638644 cfg_build(struct labelinfo *labinfo)
 639645 {
 640646         /* Child and parent nodes */
 641647         struct cfgnode *cnode;
 642648         struct cfgnode *pnode;
 643649         struct basicblock *bb;
 644650         
 645651         DLIST_FOREACH(bb, &bblocks, bbelem) {
 646652 
 647653                 if (bb->first->type == IP_EPILOG) {
 648654                         break;
 649655                 }
 650656 
 651657                 cnode = tmpalloc(sizeof(struct cfgnode));
 652658                 pnode = tmpalloc(sizeof(struct cfgnode));
 653659                 pnode->bblock = bb;
 654660 
 655661                 if ((bb->last->type == IP_NODE) &&
 656662                     (bb->last->ip_node->n_op == GOTO)) {
 657663                         if (bb->last->ip_node->n_left->n_lval - labinfo->low >
 658664                             labinfo->size) {
 659665                                 comperr("Label out of range: %d, base %d",
 660666                                         bb->last->ip_node->n_left->n_lval,
 661667                                         labinfo->low);
 662668                         }
 663669                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_left->n_lval - labinfo->low];
 664670                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 665671                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 666672                         continue;
 667673                 }
 668674                 if ((bb->last->type == IP_NODE) &&
 669675                     (bb->last->ip_node->n_op == CBRANCH)) {
 670676                         if (bb->last->ip_node->n_right->n_lval - labinfo->low >
 671677                             labinfo->size)
 672678                                 comperr("Label out of range: %d",
 673679                                         bb->last->ip_node->n_left->n_lval);
 674680                         
 675681                         cnode->bblock = labinfo->arr[bb->last->ip_node->n_right->n_lval - labinfo->low];
 676682                         SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 677683                         SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 678684                         cnode = tmpalloc(sizeof(struct cfgnode));
 679685                         pnode = tmpalloc(sizeof(struct cfgnode));
 680686                         pnode->bblock = bb;
 681687                 }
 682688 
 683689                 cnode->bblock = DLIST_NEXT(bb, bbelem);
 684690                 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
 685691                 SLIST_INSERT_LAST(&bb->children, cnode, cfgelem);
 686692         }
 687693 }
 688694 
 689695 void
 690696 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
 691697 {
 692698         struct cfgnode *cnode;
 693699         
 694700         if (bb->dfnum != 0)
 695701                 return;
 696702 
 697703         bb->dfnum = ++dfsnum;
 698704         bb->dfparent = parent;
 699705         bbinfo->arr[bb->dfnum] = bb;
 700706         SLIST_FOREACH(cnode, &bb->children, cfgelem) {
 701707                 cfg_dfs(cnode->bblock, bb->dfnum, bbinfo);
 702708         }
 703709         /* Don't bring in unreachable nodes in the future */
 704710         bbinfo->size = dfsnum + 1;
 705711 }
 706712 
 707713 static bittype *
 708714 setalloc(int nelem)
 709715 {
 710716         bittype *b;
 711717         int sz = (nelem+NUMBITS-1)/NUMBITS;
 712718 
 713719         b = tmpalloc(sz * sizeof(bittype));
 714720         memset(b, 0, sz * sizeof(bittype));
 715721         return b;
 716722 }
 717723 
 718724 /*
 719725  * Algorithm 19.9, pp 414 from Appel.
 720726  */
 721727 
 722728 void
 723729 dominators(struct bblockinfo *bbinfo)
 724730 {
 725731         struct cfgnode *cnode;
 726732         struct basicblock *bb, *y, *v;
 727733         struct basicblock *s, *sprime, *p;
 728734         int h, i;
 729735 
 730736         DLIST_FOREACH(bb, &bblocks, bbelem) {
 731737                 bb->bucket = setalloc(bbinfo->size);
 732738                 bb->df = setalloc(bbinfo->size);
 733739                 bb->dfchildren = setalloc(bbinfo->size);
 734740         }
 735741 
 736742         dfsnum = 0;
 737743         cfg_dfs(DLIST_NEXT(&bblocks, bbelem), 0, bbinfo);
 738744 
 739745 #if 0
 740746         { struct basicblock *bbb; struct cfgnode *ccnode;
 741747         DLIST_FOREACH(bbb, &bblocks, bbelem) {
 742748                 printf("Basic block %d, parents: ", bbb->dfnum);
 743749                 SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
 744750                         printf("%d, ", ccnode->bblock->dfnum);
 745751                 }
 746752                 printf("\nChildren: ");
 747753                 SLIST_FOREACH(ccnode, &bbb->children, cfgelem) {
 748754                         printf("%d, ", ccnode->bblock->dfnum);
 749755                 }
 750756                 printf("\n");
 751757         }
 752758         }
 753759 #endif
 754760 
 755761         for(h = bbinfo->size - 1; h > 1; h--) {
 756762                 bb = bbinfo->arr[h];
 757763                 p = s = bbinfo->arr[bb->dfparent];
 758764                 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
 759765                         if (cnode->bblock->dfnum <= bb->dfnum)
 760766                                 sprime = cnode->bblock;
 761767                         else
 762768                                 sprime = bbinfo->arr[ancestorwithlowestsemi
 763769                                               (cnode->bblock, bbinfo)->semi];
 764770                         if (sprime->dfnum < s->dfnum)
 765771                                 s = sprime;
 766772                 }
 767773                 bb->semi = s->dfnum;
 768774                 BITSET(s->bucket, bb->dfnum);
 769775                 link(p, bb);
 770776                 for (i = 1; i < bbinfo->size; i++) {
 771777                         if(TESTBIT(p->bucket, i)) {
 772778                                 v = bbinfo->arr[i];
 773779                                 y = ancestorwithlowestsemi(v, bbinfo);
 774780                                 if (y->semi == v->semi)
 775781                                         v->idom = p->dfnum;
 776782                                 else
 777783                                         v->samedom = y->dfnum;
 778784                         }
 779785                 }
 780786                 memset(p->bucket, 0, (bbinfo->size + 7)/8);
 781787         }
 782788 #if 0
 783789         printf("Num\tSemi\tAncest\tidom\n");
 784790         CIRCLEQ_FOREACH(bb, &bblocks, bbelem) {
 785791                 printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi, bb->ancestor, bb->idom);
 786792         }
 787793 #endif
 788794         for(h = 2; h < bbinfo->size; h++) {
 789795                 bb = bbinfo->arr[h];
 790796                 if (bb->samedom != 0) {
 791797                         bb->idom = bbinfo->arr[bb->samedom]->idom;
 792798                 }
 793799         }
 794800         DLIST_FOREACH(bb, &bblocks, bbelem) {
 795801                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
 796802 #if 0
 797803 
 798804                         printf("Setting child %d of %d\n", bb->dfnum, bbinfo->arr[bb->idom]->dfnum);
 799805 #endif
 800806 
 801807                         BITSET(bbinfo->arr[bb->idom]->dfchildren, bb->dfnum);
 802808                 }
 803809         }
 804810 }
 805811 
 806812 
 807813 struct basicblock *
 808814 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
 809815 {
 810816         struct basicblock *u = bblock;
 811817         struct basicblock *v = bblock;
 812818 
 813819         while (v->ancestor != 0) {
 814820                 if (bbinfo->arr[v->semi]->dfnum <
 815821                     bbinfo->arr[u->semi]->dfnum)
 816822                         u = v;
 817823                 v = bbinfo->arr[v->ancestor];
 818824         }
 819825         return u;
 820826 }
 821827 
 822828 void
 823829 link(struct basicblock *parent, struct basicblock *child)
 824830 {
 825831         child->ancestor = parent->dfnum;
 826832 }
 827833 
 828834 void
 829835 computeDF(struct basicblock *bblock, struct bblockinfo *bbinfo)
 830836 {
 831837         struct cfgnode *cnode;
 832838         int h, i;
 833839         
 834840         SLIST_FOREACH(cnode, &bblock->children, cfgelem) {
 835841                 if (cnode->bblock->idom != bblock->dfnum)
 836842                         BITSET(bblock->df, cnode->bblock->dfnum);
 837843         }
 838844         for (h = 1; h < bbinfo->size; h++) {
 839845                 if (!TESTBIT(bblock->dfchildren, h))
 840846                         continue;
 841847                 computeDF(bbinfo->arr[h], bbinfo);
 842848                 for (i = 1; i < bbinfo->size; i++) {
 843849                         if (TESTBIT(bbinfo->arr[h]->df, i) &&
 844850                             (bbinfo->arr[h] == bblock ||
 845851                              (bblock->idom != bbinfo->arr[h]->dfnum)))
 846852                             BITSET(bblock->df, i);
 847853                 }
 848854         }
 849855 }
 850856 
 851857 static struct basicblock *currbb;
 852858 static struct interpass *currip;
 853859 
 854860 /* Helper function for findTemps, Find assignment nodes. */
 855861 static void
 856862 findasg(NODE *p)
 857863 {
 858864         struct pvarinfo *pv;
 859865 
 860866         if (p->n_op != ASSIGN)
 861867                 return;
 862868 
 863869         if (p->n_left->n_op != TEMP)
 864870                 return;
 865871 
 866872         pv = tmpcalloc(sizeof(struct pvarinfo));
 867873         pv->next = defsites.arr[p->n_left->n_lval];
 868874         pv->bb = currbb;
 869875         pv->top = currip->ip_node;
 870876         pv->n = p->n_left;
 871877         BITSET(currbb->Aorig, p->n_left->n_lval);
 872878 
 873879         defsites.arr[p->n_left->n_lval] = pv;
 874880 }
 875881 
 876882 /* Walk the interpass looking for assignment nodes. */
 877883 void findTemps(struct interpass *ip)
 878884 {
 879885         if (ip->type != IP_NODE)
 880886                 return;
 881887 
 882888         currip = ip;
 883889 
 884890         walkf(ip->ip_node, findasg);
 885891 }
 886892 
 887893 /*
 888894  * Algorithm 19.6 from Appel.
 889895  */
 890896 
 891897 void
 892898 placePhiFunctions(struct bblockinfo *bbinfo)
 893899 {
 894900         struct basicblock *bb;
 895901         struct interpass *ip;
 896902         int maxtmp, i, j, k, l;
 897903         struct pvarinfo *n;
 898904         struct cfgnode *cnode;
 899905         TWORD ntype;
 900906         NODE *p;
 901907         struct pvarinfo *pv;
 902908 
 903909         bb = DLIST_NEXT(&bblocks, bbelem);
 904910         defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 905911         bb = DLIST_PREV(&bblocks, bbelem);
 906912         maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
 907913         defsites.size = maxtmp - defsites.low + 1;
 908914         defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
 909915 
 910916         /* Find all defsites */
 911917         DLIST_FOREACH(bb, &bblocks, bbelem) {
 912918                 currbb = bb;
 913919                 ip = bb->first;
 914920                 bb->Aorig = setalloc(defsites.size);
 915921                 bb->Aphi = setalloc(defsites.size);
 916922                 
 917923 
 918924                 while (ip != bb->last) {
 919925                         findTemps(ip);
 920926                         ip = DLIST_NEXT(ip, qelem);
 921927                 }
 922928                 /* Make sure we get the last statement in the bblock */
 923929                 findTemps(ip);
 924930         }
 925931         /* For each variable */
 926932         for (i = defsites.low; i < defsites.size; i++) {
 927933                 /* While W not empty */
 928934                 while (defsites.arr[i] != NULL) {
 929935                         /* Remove some node n from W */
 930936                         n = defsites.arr[i];
 931937                         defsites.arr[i] = n->next;
 932938                         /* For each y in n->bb->df */
 933939                         for (j = 0; j < bbinfo->size; j++) {
 934940                                 if (!TESTBIT(n->bb->df, j))
 935941                                         continue;
 936942                                 
 937943                                 if (TESTBIT(bbinfo->arr[j]->Aphi, i))
 938944                                         continue;
 939945 
 940946                                 ntype = n->n->n_type;
 941947                                 k = 0;
 942948                                 /* Amount of predecessors for y */
 943949                                 SLIST_FOREACH(cnode, &n->bb->parents, cfgelem)
 944950                                         k++;
 945951                                 /* Construct phi(...) */
 946952                                 p = mklnode(TEMP, i, 0, ntype);
 947953                                 for (l = 0; l < k-1; l++)
 948954                                         p = mkbinode(PHI, p,
 949955                                             mklnode(TEMP, i, 0, ntype), ntype);
 950956                                 ip = ipnode(mkbinode(ASSIGN,
 951957                                     mklnode(TEMP, i, 0, ntype), p, ntype));
 952958                                 /* Insert phi at top of basic block */
 953959                                 DLIST_INSERT_BEFORE(((struct interpass*)&n->bb->first), ip, qelem);
 954960                                 n->bb->first = ip;
 955961                                 BITSET(bbinfo->arr[j]->Aphi, i);
 956962                                 if (!TESTBIT(bbinfo->arr[j]->Aorig, i)) {
 957963                                         pv = tmpalloc(sizeof(struct pvarinfo));
 958964                                         // XXXpj Ej fullständig information.
 959965                                         pv->bb = bbinfo->arr[j];
 960966                                         pv->next = defsites.arr[i]->next;
 961967                                         defsites.arr[i] = pv;
 962968                                 }
 963969                                         
 964970 
 965971                         }
 966972                 }
 967973         }
 968974 }
 969975 
 970976 /*
 971977  * Remove unreachable nodes in the CFG.
 972978  */
 973979 
 974980 void
 975981 remunreach(void)
 976982 {
 977983         struct basicblock *bb, *nbb;
 978984         struct interpass *next, *ctree;
 979985 
 980986         bb = DLIST_NEXT(&bblocks, bbelem);
 981987         while (bb != &bblocks) {
 982988                 nbb = DLIST_NEXT(bb, bbelem);
 983989 
 984990                 /* Code with dfnum 0 is unreachable */
 985991                 if (bb->dfnum != 0) {
 986992                         bb = nbb;
 987993                         continue;
 988994                 }
 989995 
 990996                 /* Need the epilogue node for other parts of the
 991997                    compiler, set its label to 0 and backend will
 992998                    handle it. */
 993999                 if (bb->first->type == IP_EPILOG) {
 9941000                         bb->first->ip_lbl = 0;
 9951001                         bb = nbb;
 9961002                         continue;
 9971003                 }
 9981004 
 9991005                 next = bb->first;
 10001006                 do {
 10011007                         ctree = next;
 10021008                         next = DLIST_NEXT(ctree, qelem);
 10031009                         
 10041010                         if (ctree->type == IP_NODE)
 10051011                                 tfree(ctree->ip_node);
 10061012                         DLIST_REMOVE(ctree, qelem);
 10071013                 } while (ctree != bb->last);
 10081014                         
 10091015                 DLIST_REMOVE(bb, bbelem);
 10101016                 bb = nbb;
 10111017         }
 10121018 }
 10131019 
 10141020 void
 10151021 printip(struct interpass *pole)
 10161022 {
 10171023         static char *foo[] = {
 10181024            0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
 10191025         struct interpass *ip;
 10201026 
 10211027         DLIST_FOREACH(ip, pole, qelem) {
 10221028                 if (ip->type > MAXIP)
 10231029                         printf("IP(%d) (%p): ", ip->type, ip);
 10241030                 else
 10251031                         printf("%s (%p): ", foo[ip->type], ip);
 10261032                 switch (ip->type) {
 10271033                 case IP_NODE: printf("\n");
 10281034                         fwalk(ip->ip_node, e2print, 0); break;
 10291035                 case IP_PROLOG:
 10301036                         printf("%s\n",
 10311037                             ((struct interpass_prolog *)ip)->ipp_name); break;
 10321038                 case IP_STKOFF: printf("%d\n", ip->ip_off); break;
 10331039                 case IP_EPILOG: printf("\n"); break;
 10341040                 case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
 10351041                 }
 10361042         }
 10371043 }
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-30 19:58 +0100