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