home *** CD-ROM | disk | FTP | other *** search
/ Crawly Crypt Collection 1 / crawlyvol1.bin / program / compiler / sozobon / scsrc20 / top / health.c < prev    next >
C/C++ Source or Header  |  1991-02-22  |  4KB  |  186 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.  
  12. /*
  13.  * Routines for data flow analysis by block and function.
  14.  */
  15.  
  16. #include "top.h"
  17.  
  18. /*
  19.  * bprep() - initial analysis of a block
  20.  */
  21. void
  22. bprep(bp)
  23. BLOCK    *bp;
  24. {
  25.     register INST    *ip;
  26.     register int    ref, set;
  27.  
  28.     ref = set = 0;
  29.     for (ip = bp->first; ip != NULL ;ip = ip->next) {
  30.         ref |= (ip->rref = reg_ref(ip)) & ~set;
  31.         set |= (ip->rset = reg_set(ip));
  32.     }
  33.     bp->rref = ref;
  34.     bp->rset = set;
  35. }
  36.  
  37. /*
  38.  * fprep() - perform initial analysis of individual blocks in a function
  39.  */
  40. static    void
  41. fprep(bp)
  42. BLOCK    *bp;
  43. {
  44.     register BLOCK    *cp;
  45.  
  46.     for (cp = bp; cp != NULL ;cp = cp->next)
  47.         bprep(cp);
  48. }
  49.  
  50. static    bool
  51. scan_ref(bp, reg)
  52. register BLOCK    *bp;
  53. register int    reg;
  54. {
  55.     register INST    *ip;
  56.  
  57.     if (bp == NULL)
  58.         return FALSE;
  59.  
  60.     if (bp->rref & reg)
  61.         return TRUE;
  62.  
  63.     if (bp->rset & reg)
  64.         return FALSE;
  65.  
  66.     if (bp->flags & B_MARK)
  67.         return FALSE;
  68.  
  69.     if (bp->flags & B_RET)
  70.         return FALSE;
  71.  
  72.     bp->flags |= B_MARK;
  73.  
  74.     if (scan_ref(bp->bcond, reg))
  75.         return TRUE;
  76.  
  77.     if (scan_ref(bp->bfall, reg))
  78.         return TRUE;
  79.  
  80.     for (ip = bp->first; ip != NULL ;ip = ip->next) {
  81.         if (ip->opcode == DC && (ip->flags & LENL)) {
  82.             BLOCK    *db;
  83.  
  84.             if (is_astr(ip->src.amode) && (ip->src.astr != NULL) &&
  85.                 (db = getsym(ip->src.astr)) != NULL)
  86.                 if (scan_ref(db, reg))
  87.                     return TRUE;
  88.         }
  89.     }
  90.     return FALSE;
  91. }
  92.  
  93. /*
  94.  * is_live(bp, reg) - is 'reg' live at the end of block 'bp'
  95.  *
  96.  * Look ahead through the traversal graph to see what might happen to the
  97.  * given register. If we can find any reachable block that references 'reg'
  98.  * before setting it, the register is live. Scanning stops when the register
  99.  * is set, we loop back to the starting block, or the function returns.
  100.  */
  101. static    bool
  102. is_live(bp, reg)
  103. register BLOCK    *bp;
  104. register int    reg;
  105. {
  106.     register INST    *ip;
  107.     register BLOCK    *cp;
  108.  
  109.     /*
  110.      * Clear all the mark bits
  111.      */
  112.     for (cp = fhead; cp != NULL ;cp = cp->next)
  113.         cp->flags &= ~B_MARK;
  114.  
  115.     bp->flags |= B_MARK;
  116.  
  117.     if (scan_ref(bp->bfall, reg))
  118.         return TRUE;
  119.  
  120.     if (scan_ref(bp->bcond, reg))
  121.         return TRUE;
  122.  
  123.     for (ip = bp->first; ip != NULL ;ip = ip->next) {
  124.         if (ip->opcode == DC && (ip->flags & LENL)) {
  125.             BLOCK    *db;
  126.  
  127.             if (is_astr(ip->src.amode) && (ip->src.astr != NULL) &&
  128.                 (db = getsym(ip->src.astr)) != NULL)
  129.                 if (scan_ref(db, reg))
  130.                     return TRUE;
  131.         }
  132.     }
  133.     return FALSE;
  134. }
  135.  
  136. /*
  137.  * bflow() - live/dead analysis for a given block
  138.  *
  139.  * Work backward from the end of the block, checking the status of registers.
  140.  * To start with, figure out the state of each register as of the end of the
  141.  * block. Then work backward, checking registers only as necessary.
  142.  */
  143. static    void
  144. bflow(bp)
  145. BLOCK    *bp;
  146. {
  147.     register INST    *ip;
  148.     register int    live = 0;
  149.     register int    reg;
  150.  
  151.     /*
  152.      * Figure out what's alive at the end of this block.
  153.      */
  154.     for (reg = FIRSTREG; reg <= LASTREG ;reg++) {
  155.         if (is_live(bp, RM(reg)))
  156.             live |= RM(reg);
  157.     }
  158.     /*
  159.      * Now work through the instructions in the block.
  160.      */
  161.     for (ip = bp->last; ip != NULL ;ip = ip->prev) {
  162.         ip->live = live;
  163.  
  164.         for (reg = FIRSTREG; reg <= LASTREG ;reg++) {
  165.             if (ip->rref & RM(reg))
  166.                 live |= RM(reg);
  167.             else if (ip->rset & RM(reg))
  168.                 live &= ~RM(reg);
  169.         }
  170.     }
  171. }
  172.  
  173. void
  174. rhealth(bp, do_prep)
  175. BLOCK    *bp;
  176. bool    do_prep;
  177. {
  178.     register BLOCK    *cp;
  179.  
  180.     if (do_prep)
  181.         fprep(bp);
  182.  
  183.     for (cp = bp; cp != NULL ;cp = cp->next)
  184.         bflow(cp);
  185. }
  186.