home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / alib / d1xx / d110 / pdc.lha / Pdc / src / Analyze.c next >
C/C++ Source or Header  |  1987-10-28  |  17KB  |  485 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. extern struct amode *gen_expr(), *makedreg(), *makeareg(), *make_mask();
  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 == NULL || node2 == NULL )
  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 NULL;
  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 == NULL )
  91.                 return NULL;
  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. struct cse * 
  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)) == NULL ) {   /* 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 != NULL ) {
  133.                 if( lvalue(csp->exp) && equalnode(node,csp->exp->v.p[0]) ) {
  134.                         if( csp->voidf )
  135.                                 return NULL;
  136.                         csp->voidf = 1;
  137.                         return csp;
  138.                         }
  139.                 csp = csp->next;
  140.                 }
  141.         return NULL;
  142. }
  143.  
  144. void 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.  
  155.         if( node == NULL )
  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)) != NULL ) {
  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.         case en_info:
  187.                         scanexpr(node->v.p[0],duse);
  188.                         break;
  189.                 case en_asadd:  case en_assub:
  190.                 case en_add:    case en_sub:
  191.                         scanexpr(node->v.p[0],duse);
  192.                         scanexpr(node->v.p[1],duse);
  193.                         break;
  194.                 case en_mul:    case en_div:
  195.                 case en_lsh:    case en_rsh:
  196.                 case en_mod:    case en_and:
  197.                 case en_or:     case en_xor:
  198.                 case en_lor:    case en_land:
  199.                 case en_eq:     case en_ne:
  200.                 case en_gt:     case en_ge:
  201.                 case en_lt:     case en_le:
  202.                 case en_asmul:  case en_asdiv:
  203.                 case en_asmod:  case en_aslsh:
  204.                 case en_asrsh:  case en_asand:
  205.                 case en_asor:   case en_cond:
  206.                 case en_void:   case en_assign:
  207.             scanexpr(node->v.p[0],0);
  208.             scanexpr(node->v.p[1],0);
  209.             break;
  210.                 case en_fcall:
  211.             scanexpr(node->v.p[0],1);
  212.             scanexpr(node->v.p[1],0);
  213.                         break;
  214.                 }
  215. }
  216.  
  217. void scan(block)
  218. /*
  219.  *      scan will gather all optimizable expressions into the expression
  220.  *      list for a block of statements.
  221.  */
  222. struct snode    *block;
  223. {       while( block != NULL ) {
  224.                 switch( block->stype ) {
  225.                         case st_return:
  226.                         case st_expr:
  227.                                 opt4(&block->exp);
  228.                                 scanexpr(block->exp,0);
  229.                                 break;
  230.                         case st_while:
  231.                         case st_do:
  232.                                 opt4(&block->exp);
  233.                                 scanexpr(block->exp,0);
  234.                                 scan(block->s1);
  235.                                 break;
  236.                         case st_for:
  237.                                 opt4(&block->label);
  238.                                 scanexpr(block->label,0);
  239.                                 opt4(&block->exp);
  240.                                 scanexpr(block->exp,0);
  241.                                 scan(block->s1);
  242.                                 opt4(&block->s2);
  243.                                 scanexpr(block->s2,0);
  244.                                 break;
  245.                         case st_if:
  246.                                 opt4(&block->exp);
  247.                                 scanexpr(block->exp,0);
  248.                                 scan(block->s1);
  249.                                 scan(block->s2);
  250.                                 break;
  251.                         case st_switch:
  252.                                 opt4(&block->exp);
  253.                                 scanexpr(block->exp,0);
  254.                                 scan(block->s1);
  255.                                 break;
  256.                         case st_case:
  257.                                 scan(block->s1);
  258.                                 break;
  259.                         }
  260.                 block = block->next;
  261.                 }
  262. }
  263.  
  264. void exchange(c1)
  265. /*
  266.  *      exchange will exchange the order of two expression entries
  267.  *      following c1 in the linked list.
  268.  */
  269. struct cse      **c1;
  270. {       struct cse      *csp1, *csp2;
  271.         csp1 = *c1;
  272.         csp2 = csp1->next;
  273.         csp1->next = csp2->next;
  274.         csp2->next = csp1;
  275.         *c1 = csp2;
  276. }
  277.  
  278. int     desire(csp)
  279. /*
  280.  *      returns the desirability of optimization for a subexpression.
  281.  */
  282. struct cse      *csp;
  283. {       if( csp->voidf || (csp->exp->nodetype == en_icon &&
  284.                         csp->exp->v.i < 16 && csp->exp->v.i >= 0))
  285.                 return 0;
  286.         if( lvalue(csp->exp) )
  287.                 return 2 * csp->uses;
  288.         return csp->uses;
  289. }
  290.  
  291. int     bsort(list)
  292. /*
  293.  *      bsort implements a bubble sort on the expression list.
  294.  */
  295. struct cse      **list;
  296. {       struct cse      *csp1, *csp2;
  297.     int i;
  298.  
  299.         csp1 = *list;
  300.         if( csp1 == NULL || csp1->next == NULL )
  301.                 return 0;
  302.         i = bsort( &(csp1->next));
  303.         csp2 = csp1->next;
  304.         if( desire(csp1) < desire(csp2) ) {
  305.                 exchange(list);
  306.                 return 1;
  307.                 }
  308.         return 0;
  309. }
  310.  
  311. void allocate()
  312. /*
  313.  *      allocate will allocate registers for the expressions that have
  314.  *      a high enough desirability.
  315.  */
  316. {       struct cse      *csp;
  317.         struct enode    *exptr;
  318.         int             datareg, addreg, mask;
  319.         struct amode    *ap, *ap2;
  320.         datareg = 3;
  321.         addreg = 10;
  322.         mask = 0;
  323.         while( bsort(&olist) );         /* sort the expression list */
  324.         csp = olist;
  325.         while( csp != 0 ) {
  326.                 if( desire(csp) < 3 )
  327.                         csp->reg = -1;
  328.                 else if( csp->duses > csp->uses / 4 && addreg < 14 )
  329.                         csp->reg = addreg++;
  330.                 else if( datareg < 8 )
  331.                         csp->reg = datareg++;
  332.                 else
  333.                         csp->reg = -1;
  334.                 if( csp->reg != -1 )
  335.            {
  336.                         mask = mask | (1 << csp->reg);
  337.            }
  338.                 csp = csp->next;
  339.                 }
  340.         if( mask != 0 )
  341.                 gen_code(op_movem,4,make_mask(mask),push);
  342.         save_mask = mask;
  343.         csp = olist;
  344.         while( csp != NULL ) {
  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((enum e_am)(csp->reg));
  354.                                 else
  355.                                         ap2 = makeareg((enum e_am)((int)csp->reg - 8));
  356.                                 gen_code(op_move,4,ap,ap2);
  357.                                 freeop(ap);
  358.                                 }
  359.                         }
  360.                 csp = csp->next;
  361.                 }
  362. }
  363.  
  364. void 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 == NULL )
  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)) != NULL )
  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)) != NULL ) {
  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.         case en_info:
  403.                         repexpr(node->v.p[0]);
  404.                         break;
  405.                 case en_add:    case en_sub:
  406.                 case en_mul:    case en_div:
  407.                 case en_mod:    case en_lsh:
  408.                 case en_rsh:    case en_and:
  409.                 case en_or:     case en_xor:
  410.                 case en_land:   case en_lor:
  411.                 case en_eq:     case en_ne:
  412.                 case en_lt:     case en_le:
  413.                 case en_gt:     case en_ge:
  414.                 case en_cond:   case en_void:
  415.                 case en_asadd:  case en_assub:
  416.                 case en_asmul:  case en_asdiv:
  417.                 case en_asor:   case en_asand:
  418.                 case en_asmod:  case en_aslsh:
  419.                 case en_asrsh:  case en_fcall:
  420.                 case en_assign:
  421.                         repexpr(node->v.p[0]);
  422.                         repexpr(node->v.p[1]);
  423.                         break;
  424.                 }
  425. }
  426.  
  427. void repcse(block)
  428. /*
  429.  *      repcse will scan through a block of statements replacing the
  430.  *      optimized expressions with their temporary references.
  431.  */
  432. struct snode    *block;
  433. {       while( block != NULL ) {
  434.                 switch( block->stype ) {
  435.                         case st_return:
  436.                         case st_expr:
  437.                                 repexpr(block->exp);
  438.                                 break;
  439.                         case st_while:
  440.                         case st_do:
  441.                                 repexpr(block->exp);
  442.                                 repcse(block->s1);
  443.                                 break;
  444.                         case st_for:
  445.                                 repexpr(block->label);
  446.                                 repexpr(block->exp);
  447.                                 repcse(block->s1);
  448.                                 repexpr(block->s2);
  449.                                 break;
  450.                         case st_if:
  451.                                 repexpr(block->exp);
  452.                                 repcse(block->s1);
  453.                                 repcse(block->s2);
  454.                                 break;
  455.                         case st_switch:
  456.                                 repexpr(block->exp);
  457.                                 repcse(block->s1);
  458.                                 break;
  459.                         case st_case:
  460.                                 repcse(block->s1);
  461.                                 break;
  462.                         }
  463.                 block = block->next;
  464.                 }
  465. }
  466.  
  467. opt1(block)
  468. /*
  469.  *      opt1 is the externally callable optimization routine. it will
  470.  *      collect and allocate common subexpressions and substitute the
  471.  *      tempref for all occurrances of the expression within the block.
  472.  *
  473.  */
  474. struct snode    *block;
  475. {
  476.    if ( Options.Optimize )
  477.      {
  478.     olist = 0;
  479.         scan(block);     /* collect expressions */
  480.         allocate();     /* allocate registers */
  481.         repcse(block);    /* replace allocated expressions */
  482.      }
  483. }
  484.  
  485.