home *** CD-ROM | disk | FTP | other *** search
/ Crawly Crypt Collection 1 / crawlyvol1.bin / program / compiler / sozobon / scsrc20 / top / branch.c next >
C/C++ Source or Header  |  1991-02-22  |  13KB  |  519 lines
  1. /* Copyright (c) 1988,1991 by Sozobon, Limited.  Author: Tony Andrews
  2.  *
  3.  * Permission is granted to anyone to use this software for any purpose
  4.  * on any computer system, and to redistribute it freely, with the
  5.  * following restrictions:
  6.  * 1) No charge may be made other than reasonable charges for reproduction.
  7.  * 2) Modified versions must be clearly marked as such.
  8.  * 3) The authors are not responsible for any harmful consequences
  9.  *    of using this software, even if they result from defects in it.
  10.  */
  11. #include "top.h"
  12.  
  13. #define    TOUCHED(bp)    ((bp)->flags & B_TOUCHED)
  14.  
  15. /*
  16.  * bcomp(bc) - return the complement of the given branch code
  17.  *
  18.  * Used when a branch reversal is needed.
  19.  */
  20. static    int
  21. bcomp(bc)
  22. register int    bc;
  23. {
  24.     switch (bc) {
  25.     case BHI: return BLS;
  26.     case BLS: return BHI;
  27.     case BCC: return BCS;
  28.     case BCS: return BCC;
  29.     case BNE: return BEQ;
  30.     case BEQ: return BNE;
  31.     case BVC: return BVS;
  32.     case BVS: return BVC;
  33.     case BPL: return BMI;
  34.     case BMI: return BPL;
  35.     case BGE: return BLT;
  36.     case BLT: return BGE;
  37.     case BGT: return BLE;
  38.     case BLE: return BGT;
  39.     default:
  40.         fprintf(stderr, "bcomp() - bad branch code %d\n", bc);
  41.         exit(1);
  42.     }
  43. }
  44.  
  45. /*
  46.  * isbranch(s) - determines if 's' is a branch opcode
  47.  *
  48.  * Returns 1 for branches whose destination is the first operand,
  49.  * and 2 for branches whose dest. is the second.
  50.  */
  51. static    int
  52. isbranch(c)
  53. register int    c;
  54. {
  55.     switch (c) {
  56.     case BRA: case BHI: case BLS: case BCC:
  57.     case BCS: case BNE: case BEQ: case BVC:
  58.     case BVS: case BPL: case BMI: case BGE:
  59.     case BLT: case BGT: case BLE:
  60.         return 1;
  61.  
  62.     case DBRA: case DBHI: case DBLS: case DBCC:
  63.     case DBCS: case DBNE: case DBEQ: case DBMI:
  64.     case DBGE: case DBLT: case DBGT: case DBLE:
  65.     case  DBT:
  66.         return 2;
  67.  
  68.     default:
  69.         return 0;
  70.     }
  71. }
  72.  
  73. /*
  74.  * cblock(cp) - return the first block containing some code
  75.  *
  76.  * Starting with 'cp', find a block that has one or more instructions
  77.  * in it. This is useful to collapse multiple null blocks into a single
  78.  * logical point. This happens at points in the generated code where
  79.  * there are multiple labels at the same logical location.
  80.  */
  81. static    BLOCK *
  82. cblock(bp)
  83. register BLOCK    *bp;
  84. {
  85.     while (bp->first == NULL && bp->bcond == NULL) {
  86.         if (bp->bfall == NULL) {
  87.             fprintf(ofp, "cblock() - error in block %s\n",
  88.                 bp->name);
  89.             exit(1);
  90.         }
  91.         bp = bp->bfall;
  92.     }
  93.  
  94.     return bp;
  95. }
  96.  
  97. /*
  98.  * bsplit() - split up blocks with branches inside them
  99.  *
  100.  * Look for branch instructions in each block. If somewhere in the middle of
  101.  * the block, split up the block. When done, the blocks are broken down into
  102.  * true basic blocks.
  103.  */
  104. static    void
  105. bsplit(bp)
  106. BLOCK    *bp;
  107. {
  108.     register BLOCK    *cp;    /* the current block */
  109.     register BLOCK    *np;    /* new block (if needed) */
  110.     register INST    *ip;    /* current instruction */
  111.  
  112.     for (cp = bp; cp != NULL ;cp = cp->chain) {
  113.         for (ip = cp->first; ip != NULL ;ip = ip->next) {
  114.             if (isbranch(ip->opcode) && ip->next != NULL) {
  115.                 np = mksym(mktmp());
  116.  
  117.                 np->chain = cp->chain;
  118.                 cp->chain = np;
  119.  
  120.                 np->next = cp->next;
  121.                 cp->next = np;
  122.  
  123.                 np->first = ip->next;
  124.                 np->first->prev = NULL;
  125.                 np->last = cp->last;
  126.  
  127.                 cp->last = ip;
  128.                 cp->last->next = NULL;
  129.  
  130.             } else if (ip->opcode == DC) {
  131.                 BLOCK    *db;
  132.  
  133.                 /*
  134.                  * If the instruction is part of a branch
  135.                  * table, both the current block and the
  136.                  * destination need to be marked as "reached".
  137.                  */
  138.                 cp->flags |= B_ISREACHED;
  139.  
  140.                 if ((db = getsym(ip->src.astr)) != NULL)
  141.                     db->flags |= B_ISREACHED;
  142.                 else {
  143.                     fprintf(stderr,
  144.                       "bsplit() - symbol '%s' not found\n",
  145.                       ip->src.astr);
  146.                     exit(1);
  147.                 }
  148.             }
  149.         }
  150.     }
  151. }
  152.  
  153. /*
  154.  * bfix() - fix up the branch pointers
  155.  *
  156.  * Go through each block setting up 'bcond' and 'bfall' properly. If the
  157.  * last instruction in the block is an unconditional branch, remove it
  158.  * and set 'bfall' instead. The idea is that there should be no branch
  159.  * instructions left when we're done. We remember the logical effect of
  160.  * each branch, but reconstruct the branches later in a more optimal way.
  161.  */
  162. static    void
  163. bfix(bp)
  164. register BLOCK    *bp;
  165. {
  166.     register BLOCK    *cp;    /* current block */
  167.     register INST    *ip;    /* current instruction */
  168.  
  169.     for (cp = bp; cp != NULL ;cp = cp->chain) {
  170.  
  171.         /* no instructions in the block */
  172.         if (cp->first == NULL) {
  173.             cp->bcond = NULL;
  174.             cp->bfall = cp->next;
  175.             continue;
  176.         }
  177.  
  178.         /* the last instruction is a "return" */
  179.         if (cp->last->opcode == RTS) {
  180.             cp->bcond = cp->bfall = NULL;
  181.             cp->flags |= B_RET;
  182.             continue;
  183.         }
  184.  
  185.         /* the last instruction isn't a branch */
  186.         if (!isbranch(cp->last->opcode)) {
  187.             cp->bcond = NULL;
  188.             cp->bfall = cp->next;
  189.             continue;
  190.         }
  191.  
  192.         /*
  193.          * If we reach this point, then we've got a branch we need
  194.          * to remove at the end of this block.
  195.          */
  196.         cp->bfall = cp->next;
  197.         if (isbranch(cp->last->opcode) == 1) {
  198.             cp->bcode = cp->last->opcode;
  199.             cp->bcond = getsym(cp->last->src.astr);
  200.         } else {
  201.             cp->bcode = -1;
  202.             cp->bcond = getsym(cp->last->dst.astr);
  203.         }
  204.  
  205.         if (cp->bcond == NULL) {
  206.             fprintf(stderr, "top: branch to bad label '%s'\n",
  207.                 cp->last->src.astr);
  208.             exit(1);
  209.         }
  210.  
  211.         if (cp->bcode < 0)
  212.             continue;
  213.  
  214.         for (ip = cp->first; ip != NULL ;ip = ip->next) {
  215.             if (ip->next == cp->last) {
  216.                 ip->next = NULL;
  217.                 break;
  218.             }
  219.         }
  220.         free(cp->last->src.astr);
  221.         free(cp->last);
  222.  
  223.         if (cp->first == cp->last)
  224.             cp->first = cp->last = NULL;
  225.         else
  226.             cp->last = ip;
  227.         /*
  228.          * If the branch was unconditional, we want to represent
  229.          * it as a "fall through", so fix the pointers to do that.
  230.          */
  231.         if (cp->bcode == BRA) {
  232.             s_bdel++;
  233.             cp->bfall = cp->bcond;
  234.             cp->bcond = NULL;
  235.         }
  236.     }
  237. }
  238.  
  239. /*
  240.  * bclean() - remove references to empty blocks
  241.  *
  242.  * Called after bsplit() and bfix().
  243.  */
  244. static    void
  245. bclean(bp)
  246. register BLOCK    *bp;
  247. {
  248.     register BLOCK    *cp;
  249.  
  250.     /*
  251.      * First clean up references to empty blocks
  252.      */
  253.     for (cp = bp; cp != NULL ;cp = cp->chain) {
  254.         if (cp->bcond != NULL)
  255.             cp->bcond = cblock(cp->bcond);
  256.         if (cp->bfall != NULL)
  257.             cp->bfall = cblock(cp->bfall);
  258.     }
  259.  
  260.     /*
  261.      * Now there are generally blocks that are still linked by the
  262.      * 'chain' pointers, but no longer referenced through 'bcond'
  263.      * or 'bfall' pointers. They don't actually need to be deleted
  264.      * since they won't cause trouble anywhere else.
  265.      */
  266. }
  267.  
  268. #if 0
  269. /*
  270.  * reachable(p1, p2) - is p2 reachable (with constraints) from p1
  271.  *
  272.  * Try to reach p2 from p1 by following the 'bfall' pointers, without
  273.  * going through a block that has already been touched. We stop searching
  274.  * after a while since this function doesn't have to be perfect, and we're
  275.  * mainly interested in improving small loops anyway.
  276.  */
  277. static    bool
  278. reachable(p1, p2)
  279. register BLOCK    *p1, *p2;
  280. {
  281.     register int    i;
  282.  
  283.     for (i=0; (i < 40) && (p1 != NULL) ;i++, p1 = p1->bfall) {
  284.  
  285.         if (TOUCHED(p1))
  286.             return FALSE;
  287.  
  288.         if (p1 == p2)
  289.             return TRUE;
  290.     }
  291.     return FALSE;
  292. }
  293. #endif
  294.  
  295. /*
  296.  * bwalk() - recursive walk through the branch graph
  297.  *
  298.  * Starting at the entry point, walk through the block graph placing
  299.  * blocks on the output list. By traversing the "bfall" nodes first
  300.  * we attempt to make blocks that fall through come in order so that
  301.  * branches are minimized.
  302.  *
  303.  * Joe describes this process as "grabbing the tree at the top and
  304.  * shaking".
  305.  *
  306.  * The 'lp' variable below maintains our position in the generated list
  307.  * of blocks.
  308.  */
  309. static    BLOCK    *lp;    /* pointer to the next block in the file */
  310.  
  311. static    bwalk(p)
  312. register BLOCK    *p;
  313. {
  314.     if (p == NULL || TOUCHED(p))
  315.         return;
  316.  
  317. #if 0
  318.     /*
  319.      * The following code still needs some work, so it is disabled
  320.      * for now...
  321.      */
  322.     /*
  323.      * Check to see if loop rotation is required. We "rotate" the loop
  324.      * by skipping the current node and traversing the 'bfall' node,
  325.      * and then the 'bcond' node. The function reachable() tells us
  326.      * that there's a loop through the 'bfall' nodes allowing us to
  327.      * make this optimization. The net result is that we try to move
  328.      * conditional branches to the bottoms of loops making the loop
  329.      * one instruction shorter. The overall number of branches remains
  330.      * the same.
  331.      *
  332.      * Rather than marking all the nodes again within the function
  333.      * "reachable", we just give up after a while if no loop is
  334.      * detected. This isn't perfect, but we get the biggest gain in
  335.      * small loops, and these will be detected accurately.
  336.      */
  337.     if (do_lrot && p->bcond != NULL && reachable(p->bfall, p)) {
  338.         s_lrot++;
  339.         bwalk(p->bfall);
  340.         bwalk(p->bcond);
  341.         return;
  342.     }
  343. #endif
  344.  
  345.     p->flags |= B_TOUCHED;
  346.     lp->next = p;
  347.     lp = lp->next;
  348.  
  349.     /*
  350.      * We should swap 'bfall' and 'bcond' and alter 'bcode' IF:
  351.      *
  352.      * 1. Both bfall and bcond are non-null.
  353.      * 2. The branch is a simple one (not a DBcc inst.)
  354.      * 3. Branch reversals are enabled.
  355.      * 4. The block at bfall has already been touched.
  356.      * 5. The block at bcond hasn't been touched.
  357.      *
  358.      * In this case, we can avoid an extra branch if we reverse the
  359.      * sense of the conditional branch, and swap the pointers.
  360.      */
  361.     if (p->bfall != NULL && p->bcond != NULL && p->bcode >= 0 &&
  362.         do_brev && TOUCHED(p->bfall) && !TOUCHED(p->bcond)) {
  363.         register BLOCK    *tmp;
  364.  
  365.         s_brev++;
  366.             tmp = p->bfall;
  367.             p->bfall = p->bcond;
  368.             p->bcond = tmp;
  369.             if ((p->bcode = bcomp(p->bcode)) < 0) {
  370.                 fprintf(stderr, "top: internal error in bwalk()\n");
  371.                 exit(1);
  372.             }
  373.     }
  374.     bwalk(p->bfall);
  375.     bwalk(p->bcond);
  376. }
  377.  
  378. /*
  379.  * bsort() - branch optimization
  380.  *
  381.  * Initialize and terminate the 'next' pointers before and after
  382.  * traversing the branch graph.
  383.  */
  384. static    void
  385. bsort(bp)
  386. register BLOCK    *bp;
  387. {
  388.     register BLOCK    *cb;
  389.  
  390.     lp = bp;
  391.  
  392.     bwalk(bp);    /* traverse the tree starting at the entry point */
  393.  
  394.     /*
  395.      * Now look for other parts of the tree that don't appear to be
  396.      * reachable, but really are. This can happen through the jump
  397.      * tables created for switch statements. For each such block,
  398.      * walk the subtree starting with it.
  399.      */
  400.     for (cb = bp; cb != NULL ;cb = cb->chain) {
  401.         if (!TOUCHED(cb) && (cb->flags & B_ISREACHED))
  402.             bwalk(cb);
  403.     }
  404.  
  405.     lp->next = NULL;
  406. }
  407.  
  408. /*
  409.  * bsetlab() - figure out which blocks really need labels
  410.  *
  411.  * This can be called AFTER bsort() to mark the blocks that are going to
  412.  * need labels. Anything that we're going to branch to later gets a label.
  413.  */
  414. static    void
  415. bsetlab(bp)
  416. register BLOCK    *bp;
  417. {
  418.     for (; bp != NULL ;bp = bp->next) {
  419.         if (bp->bcond != NULL)
  420.             cblock(bp->bcond)->flags |= B_LABEL;
  421.         if (bp->bfall != NULL && bp->bfall != bp->next)
  422.             cblock(bp->bfall)->flags |= B_LABEL;
  423.         /*
  424.          * If the block is reached via a jump table, then we
  425.          * need a label on THIS block directly.
  426.          */
  427.         if (bp->flags & B_ISREACHED)
  428.             bp->flags |= B_LABEL;
  429.     }
  430. }
  431.  
  432. /*
  433.  * bjoin() - join blocks that always come together
  434.  *
  435.  * If block 'b' always follows block 'a' unconditionally, then move the
  436.  * instructions in 'b' to the end of 'a', and remove 'b'. This allows us
  437.  * to do better peephole optimization since we can optimize sequences that
  438.  * used to span blocks.
  439.  */
  440. bjoin(bp)
  441. register BLOCK    *bp;
  442. {
  443.     BLOCK    *np, *bnext;
  444.  
  445.     for (; bp != NULL ;bp = bnext) {
  446.         bnext = bp->next;
  447.  
  448.         /*
  449.          * First block can't end with a conditional branch.
  450.          */
  451.         if (bp->bcond != NULL)
  452.             continue;
  453.  
  454.         /*
  455.          * Block must fall through to the next thing in the file.
  456.          */
  457.         if (bp->next == NULL || bp->next != bp->bfall)
  458.             continue;
  459.  
  460.         np = bp->next;
  461.  
  462.         /*
  463.          * Second block can't be the destination of a branch.
  464.          */
  465.         if (np->flags & B_LABEL)
  466.             continue;
  467.  
  468.         /*
  469.          * Join the blocks...
  470.          */
  471.         if (np->first != NULL)
  472.             np->first->prev = bp->last;
  473.  
  474.         if (bp->last != NULL)
  475.             bp->last->next = np->first;
  476.         else {
  477.             bp->first = np->first;
  478.             bp->last = np->last;
  479.         }
  480.  
  481.         if (np->flags & B_RET)
  482.             bp->flags |= B_RET;
  483.  
  484.         bp->last = np->last;
  485.         bp->bfall = np->bfall;
  486.         bp->bcond = np->bcond;
  487.         bp->bcode = np->bcode;
  488.         bp->next = np->next;
  489.  
  490.         /*
  491.          * Fix pointers so we don't free the instructions
  492.          * twice later on.
  493.          */
  494.         np->first = NULL;
  495.         np->last = NULL;
  496.  
  497.         /*
  498.          * If we've done a join, then we want to loop again on
  499.          * the current block to see if any others can be joined.
  500.          */
  501.         bnext = bp;
  502.     }
  503. }
  504.  
  505. /*
  506.  * bopt() - coordinates branch optimization for the given function
  507.  */
  508. void
  509. bopt(bp)
  510. register BLOCK    *bp;
  511. {
  512.     bsplit(bp);
  513.     bfix(bp);
  514.     bclean(bp);
  515.     bsort(bp);
  516.     bsetlab(bp);
  517.     bjoin(bp);
  518. }
  519.