home *** CD-ROM | disk | FTP | other *** search
/ Crawly Crypt Collection 2 / crawlyvol2.bin / program / c / c68k_src / analyze.c next >
Encoding:
C/C++ Source or Header  |  1987-12-10  |  16.8 KB  |  481 lines
  1. #include        <stdio.h>
  2. #include        "c.h"
  3. #include        "expr.h"
  4. #include        "gen.h"
  5. #include        "cglbdec.h"
  6.  
  7. /*
  8.  *    68000 C compiler
  9.  *
  10.  *    Copyright 1984, 1985, 1986 Matthew Brandt.
  11.  *  all commercial rights reserved.
  12.  *
  13.  *    This compiler is intended as an instructive tool for personal use. Any
  14.  *    use for profit without the written consent of the author is prohibited.
  15.  *
  16.  *    This compiler may be distributed freely for non-commercial use as long
  17.  *    as this notice stays intact. Please forward any enhancements or question
  18. s
  19.  *    to:
  20.  *
  21.  *        Matthew Brandt
  22.  *        Box 920337
  23.  *        Norcross, Ga 30092
  24.  */
  25.  
  26. extern struct amode     push[], pop[];
  27.  
  28. /*
  29.  *      this module will step through the parse tree and find all
  30.  *      optimizable expressions. at present these expressions are
  31.  *      limited to expressions that are valid throughout the scope
  32.  *      of the function. the list of optimizable expressions is:
  33.  *
  34.  *              constants
  35.  *              global and static addresses
  36.  *              auto addresses
  37.  *              contents of auto addresses.
  38.  *
  39.  *      contents of auto addresses are valid only if the address is
  40.  *      never referred to without dereferencing.
  41.  *
  42.  *      scan will build a list of optimizable expressions which
  43.  *      opt1 will replace during the second optimization pass.
  44.  */
  45.  
  46. static struct cse       *olist;         /* list of optimizable expressions */
  47.  
  48. equalnode(node1, node2)
  49. /*
  50.  *      equalnode will return 1 if the expressions pointed to by
  51.  *      node1 and node2 are equivalent.
  52.  */
  53. struct enode    *node1, *node2;
  54. {       if( node1 == 0 || node2 == 0 )
  55.                 return 0;
  56.         if( node1->nodetype != node2->nodetype )
  57.                 return 0;
  58.         if( (node1->nodetype == en_icon || node1->nodetype == en_labcon ||
  59.             node1->nodetype == en_nacon || node1->nodetype == en_autocon) &&
  60.             node1->v.i == node2->v.i )
  61.                 return 1;
  62.         if( lvalue(node1) && equalnode(node1->v.p[0], node2->v.p[0]) )
  63.                 return 1;
  64.         return 0;
  65. }
  66.  
  67. struct cse      *searchnode(node)
  68. /*
  69.  *      searchnode will search the common expression table for an entry
  70.  *      that matches the node passed and return a pointer to it.
  71.  */
  72. struct enode    *node;
  73. {       struct cse      *csp;
  74.         csp = olist;
  75.         while( csp != 0 ) {
  76.                 if( equalnode(node,csp->exp) )
  77.                         return csp;
  78.                 csp = csp->next;
  79.                 }
  80.         return 0;
  81. }
  82.  
  83. struct enode    *copynode(node)
  84. /*
  85.  *      copy the node passed into a new enode so it wont get
  86.  *      corrupted during substitution.
  87.  */
  88. struct enode    *node;
  89. {       struct enode    *temp;
  90.         if( node == 0 )
  91.                 return 0;
  92.         temp = xalloc(sizeof(struct enode));
  93.         temp->nodetype = node->nodetype;
  94.         temp->v.p[0] = node->v.p[0];
  95.         temp->v.p[1] = node->v.p[1];
  96.         return temp;
  97. }
  98.  
  99. enternode(node,duse)
  100. /*
  101.  *      enternode will enter a reference to an expression node into the
  102.  *      common expression table. duse is a flag indicating whether or not
  103.  *      this reference will be dereferenced.
  104.  */
  105. struct enode    *node;
  106. int             duse;
  107. {       struct cse      *csp;
  108.         if( (csp = searchnode(node)) == 0 ) {   /* add to tree */
  109.                 csp = xalloc(sizeof(struct cse));
  110.                 csp->next = olist;
  111.                 csp->uses = 1;
  112.                 csp->duses = (duse != 0);
  113.                 csp->exp = copynode(node);
  114.                 csp->voidf = 0;
  115.                 olist = csp;
  116.                 return csp;
  117.                 }
  118.         ++(csp->uses);
  119.         if( duse )
  120.                 ++(csp->duses);
  121.         return csp;
  122. }
  123.  
  124. struct cse      *voidauto(node)
  125. /*
  126.  *      voidauto will void an auto dereference node which points to
  127.  *      the same auto constant as node.
  128.  */
  129. struct enode    *node;
  130. {       struct cse      *csp;
  131.         csp = olist;
  132.         while( csp != 0 ) {
  133.                 if( lvalue(csp->exp) && equalnode(node,csp->exp->v.p[0]) ) {
  134.                         if( csp->voidf )
  135.                                 return 0;
  136.                         csp->voidf = 1;
  137.                         return csp;
  138.                         }
  139.                 csp = csp->next;
  140.                 }
  141.         return 0;
  142. }
  143.  
  144. scanexpr(node,duse)
  145. /*
  146.  *      scanexpr will scan the expression pointed to by node for optimizable
  147.  *      subexpressions. when an optimizable expression is found it is entered
  148.  *      into the tree. if a reference to an autocon node is scanned the
  149.  *      corresponding auto dereferenced node will be voided. duse should be
  150.  *      set if the expression will be dereferenced.
  151.  */
  152. struct enode    *node;
  153. {       struct cse      *csp, *csp1;
  154.         int             n;
  155.         if( node == 0 )
  156.                 return;
  157.         switch( node->nodetype ) {
  158.                 case en_icon:
  159.                 case en_labcon:
  160.                 case en_nacon:
  161.                         enternode(node,duse);
  162.                         break;
  163.                 case en_autocon:
  164.                         if( (csp = voidauto(node)) != 0 ) {
  165.                                 csp1 = enternode(node,duse);
  166.                                 csp1->uses = (csp1->duses += csp->uses);
  167.                                 }
  168.                         else
  169.                                 enternode(node,duse);
  170.                         break;
  171.                 case en_b_ref:
  172.                 case en_w_ref:
  173.                 case en_l_ref:
  174.                         if( node->v.p[0]->nodetype == en_autocon ) {
  175.                                 csp = enternode(node,duse);
  176.                                 if( csp->voidf )
  177.                                         scanexpr(node->v.p[0],1);
  178.                                 }
  179.                         else
  180.                                 scanexpr(node->v.p[0],1);
  181.                         break;
  182.                 case en_cbl:    case en_cwl:
  183.                 case en_cbw:    case en_uminus:
  184.                 case en_compl:  case en_ainc:
  185.                 case en_adec:   case en_not:
  186.                         scanexpr(node->v.p[0],duse);
  187.                         break;
  188.                 case en_asadd:  case en_assub:
  189.                 case en_add:    case en_sub:
  190.                         scanexpr(node->v.p[0],duse);
  191.                         scanexpr(node->v.p[1],duse);
  192.                         break;
  193.                 case en_mul:    case en_div:
  194.                 case en_lsh:    case en_rsh:
  195.                 case en_mod:    case en_and:
  196.                 case en_or:     case en_xor:
  197.                 case en_lor:    case en_land:
  198.                 case en_eq:     case en_ne:
  199.                 case en_gt:     case en_ge:
  200.                 case en_lt:     case en_le:
  201.                 case en_asmul:  case en_asdiv:
  202.                 case en_asmod:  case en_aslsh:
  203.                 case en_asrsh:  case en_asand:
  204.                 case en_asor:   case en_cond:
  205.                 case en_void:   case en_assign:
  206.                         scanexpr(node->v.p[0],0);
  207.                         scanexpr(node->v.p[1],0);
  208.                         break;
  209.                 case en_fcall:
  210.                         scanexpr(node->v.p[0],1);
  211.                         scanexpr(node->v.p[1],0);
  212.                         break;
  213.                 }
  214. }
  215.  
  216. scan(block)
  217. /*
  218.  *      scan will gather all optimizable expressions into the expression
  219.  *      list for a block of statements.
  220.  */
  221. struct snode    *block;
  222. {       while( block != 0 ) {
  223.                 switch( block->stype ) {
  224.                         case st_return:
  225.                         case st_expr:
  226.                                 opt4(&block->exp);
  227.                                 scanexpr(block->exp,0);
  228.                                 break;
  229.                         case st_while:
  230.                         case st_do:
  231.                                 opt4(&block->exp);
  232.                                 scanexpr(block->exp,0);
  233.                                 scan(block->s1);
  234.                                 break;
  235.                         case st_for:
  236.                                 opt4(&block->label);
  237.                                 scanexpr(block->label,0);
  238.                                 opt4(&block->exp);
  239.                                 scanexpr(block->exp,0);
  240.                                 scan(block->s1);
  241.                                 opt4(&block->s2);
  242.                                 scanexpr(block->s2,0);
  243.                                 break;
  244.                         case st_if:
  245.                                 opt4(&block->exp);
  246.                                 scanexpr(block->exp,0);
  247.                                 scan(block->s1);
  248.                                 scan(block->s2);
  249.                                 break;
  250.                         case st_switch:
  251.                                 opt4(&block->exp);
  252.                                 scanexpr(block->exp,0);
  253.                                 scan(block->s1);
  254.                                 break;
  255.                         case st_case:
  256.                                 scan(block->s1);
  257.                                 break;
  258.                         }
  259.                 block = block->next;
  260.                 }
  261. }
  262.  
  263. exchange(c1)
  264. /*
  265.  *      exchange will exchange the order of two expression entries
  266.  *      following c1 in the linked list.
  267.  */
  268. struct cse      **c1;
  269. {       struct cse      *csp1, *csp2;
  270.         csp1 = *c1;
  271.         csp2 = csp1->next;
  272.         csp1->next = csp2->next;
  273.         csp2->next = csp1;
  274.         *c1 = csp2;
  275. }
  276.  
  277. int     desire(csp)
  278. /*
  279.  *      returns the desirability of optimization for a subexpression.
  280.  */
  281. struct cse      *csp;
  282. {       if( csp->voidf || (csp->exp->nodetype == en_icon &&
  283.                         csp->exp->v.i < 16 && csp->exp->v.i >= 0))
  284.                 return 0;
  285.         if( lvalue(csp->exp) )
  286.                 return 2 * csp->uses;
  287.         return csp->uses;
  288. }
  289.  
  290. int     bsort(list)
  291. /*
  292.  *      bsort implements a bubble sort on the expression list.
  293.  */
  294. struct cse      **list;
  295. {       struct cse      *csp1, *csp2;
  296.         int             i;
  297.         csp1 = *list;
  298.         if( csp1 == 0 || csp1->next == 0 )
  299.                 return 0;
  300.         i = bsort( &(csp1->next));
  301.         csp2 = csp1->next;
  302.         if( desire(csp1) < desire(csp2) ) {
  303.                 exchange(list);
  304.                 return 1;
  305.                 }
  306.         return 0;
  307. }
  308.  
  309. allocate()
  310. /*
  311.  *      allocate will allocate registers for the expressions that have
  312.  *      a high enough desirability.
  313.  */
  314. {       struct cse      *csp;
  315.         struct enode    *exptr;
  316.         int             datareg, addreg, mask, rmask, i;
  317.         struct amode    *ap, *ap2;
  318.         datareg = 3;
  319.         addreg = 10;
  320.         mask = 0;
  321.     rmask = 0;
  322.         while( bsort(&olist) );         /* sort the expression list */
  323.         csp = olist;
  324.         while( csp != 0 ) {
  325.                 if( desire(csp) < 3 )
  326.                         csp->reg = -1;
  327.                 else if( csp->duses > csp->uses / 4 && addreg < 14 )
  328.                         csp->reg = addreg++;
  329.                 else if( datareg < 8 )
  330.                         csp->reg = datareg++;
  331.                 else
  332.                         csp->reg = -1;
  333.                 if( csp->reg != -1 )
  334.                 {
  335.             rmask = rmask | (1 << (15 - csp->reg));
  336.                         mask = mask | (1 << csp->reg);
  337.                 }
  338.                 csp = csp->next;
  339.                 }
  340.         if( mask != 0 )
  341.                 gen_code(op_movem,4,make_mask(rmask),push);
  342.         save_mask = rmask;
  343.         csp = olist;
  344.         while( csp != 0 ) {
  345.                 if( csp->reg != -1 )
  346.                         {               /* see if preload needed */
  347.                         exptr = csp->exp;
  348.                         if( !lvalue(exptr) || (exptr->v.p[0]->v.i > 0) )
  349.                                 {
  350.                                 initstack();
  351.                                 ap = gen_expr(exptr,F_ALL,4);
  352.                                 if( csp->reg < 8 )
  353.                                         ap2 = makedreg(csp->reg);
  354.                                 else
  355.                                         ap2 = makeareg(csp->reg - 8);
  356.                                 gen_code(op_move,4,ap,ap2);
  357.                                 freeop(ap);
  358.                                 }
  359.                         }
  360.                 csp = csp->next;
  361.                 }
  362. }
  363.  
  364. repexpr(node)
  365. /*
  366.  *      repexpr will replace all allocated references within an expression
  367.  *      with tempref nodes.
  368.  */
  369. struct enode    *node;
  370. {       struct cse      *csp;
  371.         if( node == 0 )
  372.                 return;
  373.         switch( node->nodetype ) {
  374.                 case en_icon:
  375.                 case en_nacon:
  376.                 case en_labcon:
  377.                 case en_autocon:
  378.                         if( (csp = searchnode(node)) != 0 )
  379.                                 if( csp->reg > 0 ) {
  380.                                         node->nodetype = en_tempref;
  381.                                         node->v.i = csp->reg;
  382.                                         }
  383.                         break;
  384.                 case en_b_ref:
  385.                 case en_w_ref:
  386.                 case en_l_ref:
  387.                         if( (csp = searchnode(node)) != 0 ) {
  388.                                 if( csp->reg > 0 ) {
  389.                                         node->nodetype = en_tempref;
  390.                                         node->v.i = csp->reg;
  391.                                         }
  392.                                 else
  393.                                         repexpr(node->v.p[0]);
  394.                                 }
  395.                         else
  396.                                 repexpr(node->v.p[0]);
  397.                         break;
  398.                 case en_cbl:    case en_cbw:
  399.                 case en_cwl:    case en_uminus:
  400.                 case en_not:    case en_compl:
  401.                 case en_ainc:   case en_adec:
  402.                         repexpr(node->v.p[0]);
  403.                         break;
  404.                 case en_add:    case en_sub:
  405.                 case en_mul:    case en_div:
  406.                 case en_mod:    case en_lsh:
  407.                 case en_rsh:    case en_and:
  408.                 case en_or:     case en_xor:
  409.                 case en_land:   case en_lor:
  410.                 case en_eq:     case en_ne:
  411.                 case en_lt:     case en_le:
  412.                 case en_gt:     case en_ge:
  413.                 case en_cond:   case en_void:
  414.                 case en_asadd:  case en_assub:
  415.                 case en_asmul:  case en_asdiv:
  416.                 case en_asor:   case en_asand:
  417.                 case en_asmod:  case en_aslsh:
  418.                 case en_asrsh:  case en_fcall:
  419.                 case en_assign:
  420.                         repexpr(node->v.p[0]);
  421.                         repexpr(node->v.p[1]);
  422.                         break;
  423.                 }
  424. }
  425.  
  426. repcse(block)
  427. /*
  428.  *      repcse will scan through a block of statements replacing the
  429.  *      optimized expressions with their temporary references.
  430.  */
  431. struct snode    *block;
  432. {       while( block != 0 ) {
  433.                 switch( block->stype ) {
  434.                         case st_return:
  435.                         case st_expr:
  436.                                 repexpr(block->exp);
  437.                                 break;
  438.                         case st_while:
  439.                         case st_do:
  440.                                 repexpr(block->exp);
  441.                                 repcse(block->s1);
  442.                                 break;
  443.                         case st_for:
  444.                                 repexpr(block->label);
  445.                                 repexpr(block->exp);
  446.                                 repcse(block->s1);
  447.                                 repexpr(block->s2);
  448.                                 break;
  449.                         case st_if:
  450.                                 repexpr(block->exp);
  451.                                 repcse(block->s1);
  452.                                 repcse(block->s2);
  453.                                 break;
  454.                         case st_switch:
  455.                                 repexpr(block->exp);
  456.                                 repcse(block->s1);
  457.                                 break;
  458.                         case st_case:
  459.                                 repcse(block->s1);
  460.                                 break;
  461.                         }
  462.                 block = block->next;
  463.                 }
  464. }
  465.  
  466. opt1(block)
  467. /*
  468.  *      opt1 is the externally callable optimization routine. it will
  469.  *      collect and allocate common subexpressions and substitute the
  470.  *      tempref for all occurrances of the expression within the block.
  471.  *
  472.  *        optimizer is currently turned off...
  473.  */
  474. struct snode    *block;
  475. {
  476.         olist = 0;
  477.         scan(block);            /* collect expressions */
  478.         allocate();             /* allocate registers */
  479.         repcse(block);          /* replace allocated expressions */
  480. }
  481.