home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 204_01 / optimize.c < prev    next >
Text File  |  1979-12-31  |  15KB  |  391 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. dooper(node)
  26. /*
  27.  *      dooper will execute a constant operation in a node and
  28.  *      modify the node to be the result of the operation.
  29.  */
  30. struct enode    **node;
  31. {       struct enode    *ep;
  32.         ep = *node;
  33.         switch( ep->nodetype ) {
  34.                 case en_add:
  35.                         ep->nodetype = en_icon;
  36.                         ep->v.i = ep->v.p[0]->v.i + ep->v.p[1]->v.i;
  37.                         break;
  38.                 case en_sub:
  39.                         ep->nodetype = en_icon;
  40.                         ep->v.i = ep->v.p[0]->v.i - ep->v.p[1]->v.i;
  41.                         break;
  42.                 case en_mul:
  43.                         ep->nodetype = en_icon;
  44.                         ep->v.i = ep->v.p[0]->v.i * ep->v.p[1]->v.i;
  45.                         break;
  46.                 case en_div:
  47.                         ep->nodetype = en_icon;
  48.                         ep->v.i = ep->v.p[0]->v.i / ep->v.p[1]->v.i;
  49.                         break;
  50.                 case en_lsh:
  51.                         ep->nodetype = en_icon;
  52.                         ep->v.i = ep->v.p[0]->v.i << ep->v.p[1]->v.i;
  53.                         break;
  54.                 case en_rsh:
  55.                         ep->nodetype = en_icon;
  56.                         ep->v.i = ep->v.p[0]->v.i >> ep->v.p[1]->v.i;
  57.                         break;
  58.                 case en_and:
  59.                         ep->nodetype = en_icon;
  60.                         ep->v.i = ep->v.p[0]->v.i & ep->v.p[1]->v.i;
  61.                         break;
  62.                 case en_or:
  63.                         ep->nodetype = en_icon;
  64.                         ep->v.i = ep->v.p[0]->v.i | ep->v.p[1]->v.i;
  65.                         break;
  66.                 case en_xor:
  67.                         ep->nodetype = en_icon;
  68.                         ep->v.i = ep->v.p[0]->v.i ^ ep->v.p[1]->v.i;
  69.                         break;
  70.                 }
  71. }
  72.  
  73. int     pwrof2(i)
  74. /*
  75.  *      return which power of two i is or -1.
  76.  */
  77. int     i;
  78. {       int     p, q;
  79.         q = 2;
  80.         p = 1;
  81.         while( q > 0 )
  82.                 {
  83.                 if( q == i )
  84.                         return p;
  85.                 q <<= 1;
  86.                 ++p;
  87.                 }
  88.         return -1;
  89. }
  90.  
  91. int     mod_mask(i)
  92. /*
  93.  *      make a mod mask for a power of two.
  94.  */
  95. int     i;
  96. {       int     m;
  97.         m = 0;
  98.         while( i-- )
  99.                 m = (m << 1) | 1;
  100.         return m;
  101. }
  102.  
  103. opt0(node)
  104. /*
  105.  *      opt0 - delete useless expressions and combine constants.
  106.  *
  107.  *      opt0 will delete expressions such as x + 0, x - 0, x * 0,
  108.  *      x * 1, 0 / x, x / 1, x mod 0, etc from the tree pointed to
  109.  *      by node and combine obvious constant operations. It cannot
  110.  *      combine name and label constants but will combine icon type
  111.  *      nodes.
  112.  */
  113. struct enode    **node;
  114. {       struct enode    *ep;
  115.         int             val, sc;
  116.         ep = *node;
  117.         if( ep == 0 )
  118.                 return;
  119.         switch( (*node)->nodetype ) {
  120.                 case en_b_ref:
  121.                 case en_w_ref:          /* optimize unary node */
  122.                 case en_l_ref:
  123.                 case en_cbw:
  124.                 case en_cbl:
  125.                 case en_cwl:
  126.                 case en_ainc:
  127.                 case en_adec:
  128.                 case en_not:
  129.                 case en_compl:
  130.                         opt0( &((*node)->v.p[0]));
  131.                         return;
  132.                 case en_uminus:
  133.                         opt0( &(ep->v.p[0]));
  134.                         if( ep->v.p[0]->nodetype == en_icon )
  135.                                 {
  136.                                 ep->nodetype = en_icon;
  137.                                 ep->v.i = -ep->v.p[0]->v.i;
  138.                                 }
  139.                         return;
  140.                 case en_add:
  141.                 case en_sub:
  142.                         opt0(&(ep->v.p[0]));
  143.                         opt0(&(ep->v.p[1]));
  144.                         if( ep->v.p[0]->nodetype == en_icon ) {
  145.                                 if( ep->v.p[1]->nodetype == en_icon ) {
  146.                                         dooper(node);
  147.                                         return;
  148.                                         }
  149.                                 if( ep->v.p[0]->v.i == 0 ) {
  150.                     if( ep->nodetype == en_sub )
  151.                     {
  152.                         ep->v.p[0] = ep->v.p[1];
  153.                                             ep->nodetype = en_uminus;
  154.                     }
  155.                     else
  156.                         *node = ep->v.p[1];
  157.                                         return;
  158.                                         }
  159.                                 }
  160.                         else if( ep->v.p[1]->nodetype == en_icon ) {
  161.                                 if( ep->v.p[1]->v.i == 0 ) {
  162.                                         *node = ep->v.p[0];
  163.                                         return;
  164.                                         }
  165.                                 }
  166.                         return;
  167.                 case en_mul:
  168.                         opt0(&(ep->v.p[0]));
  169.                         opt0(&(ep->v.p[1]));
  170.                         if( ep->v.p[0]->nodetype == en_icon ) {
  171.                                 if( ep->v.p[1]->nodetype == en_icon ) {
  172.                                         dooper(node);
  173.                                         return;
  174.                                         }
  175.                                 val = ep->v.p[0]->v.i;
  176.                                 if( val == 0 ) {
  177.                                         *node = ep->v.p[0];
  178.                                         return;
  179.                                         }
  180.                                 if( val == 1 ) {
  181.                                         *node = ep->v.p[1];
  182.                                         return;
  183.                                         }
  184.                                 sc = pwrof2(val);
  185.                                 if( sc != -1 )
  186.                                         {
  187.                                         swap_nodes(ep);
  188.                                         ep->v.p[1]->v.i = sc;
  189.                                         ep->nodetype = en_lsh;
  190.                                         }
  191.                                 }
  192.                         else if( ep->v.p[1]->nodetype == en_icon ) {
  193.                                 val = ep->v.p[1]->v.i;
  194.                                 if( val == 0 ) {
  195.                                         *node = ep->v.p[1];
  196.                                         return;
  197.                                         }
  198.                                 if( val == 1 ) {
  199.                                         *node = ep->v.p[0];
  200.                                         return;
  201.                                         }
  202.                                 sc = pwrof2(val);
  203.                                 if( sc != -1 )
  204.                                         {
  205.                                         ep->v.p[1]->v.i = sc;
  206.                                         ep->nodetype = en_lsh;
  207.                                         }
  208.                                 }
  209.                         break;
  210.                 case en_div:
  211.                         opt0(&(ep->v.p[0]));
  212.                         opt0(&(ep->v.p[1]));
  213.                         if( ep->v.p[0]->nodetype == en_icon ) {
  214.                                 if( ep->v.p[1]->nodetype == en_icon ) {
  215.                                         dooper(node);
  216.                                         return;
  217.                                         }
  218.                                 if( ep->v.p[0]->v.i == 0 ) {    /* 0/x */
  219.                                         *node = ep->v.p[0];
  220.                                         return;
  221.                                         }
  222.                                 }
  223.                         else if( ep->v.p[1]->nodetype == en_icon ) {
  224.                                 val = ep->v.p[1]->v.i;
  225.                                 if( val == 1 ) {        /* x/1 */
  226.                                         *node = ep->v.p[0];
  227.                                         return;
  228.                                         }
  229.                                 sc = pwrof2(val);
  230.                                 if( sc != -1 )
  231.                                         {
  232.                                         ep->v.p[1]->v.i = sc;
  233.                                         ep->nodetype = en_rsh;
  234.                                         }
  235.                                 }
  236.                         break;
  237.                 case en_mod:
  238.                         opt0(&(ep->v.p[0]));
  239.                         opt0(&(ep->v.p[1]));
  240.                         if( ep->v.p[1]->nodetype == en_icon )
  241.                                 {
  242.                                 if( ep->v.p[0]->nodetype == en_icon )
  243.                                         {
  244.                                         dooper(node);
  245.                                         return;
  246.                                         }
  247.                                 sc = pwrof2(ep->v.p[1]->v.i);
  248.                                 if( sc != -1 )
  249.                                         {
  250.                                         ep->v.p[1]->v.i = mod_mask(sc);
  251.                                         ep->nodetype = en_and;
  252.                                         }
  253.                                 }
  254.                         break;
  255.                 case en_and:    case en_or:
  256.                 case en_xor:    case en_rsh:
  257.                 case en_lsh:
  258.                         opt0(&(ep->v.p[0]));
  259.                         opt0(&(ep->v.p[1]));
  260.                         if( ep->v.p[0]->nodetype == en_icon &&
  261.                                 ep->v.p[1]->nodetype == en_icon )
  262.                                 dooper(node);
  263.                         break;
  264.                 case en_land:   case en_lor:
  265.                 case en_lt:        case en_le:
  266.                 case en_gt:        case en_ge:
  267.                 case en_eq:        case en_ne:
  268.                 case en_asand:  case en_asor:
  269.                 case en_asadd:  case en_assub:
  270.                 case en_asmul:  case en_asdiv:
  271.                 case en_asmod:  case en_asrsh:
  272.                 case en_aslsh:  case en_cond:
  273.                 case en_fcall:  case en_void:
  274.                 case en_assign:
  275.                         opt0(&(ep->v.p[0]));
  276.                         opt0(&(ep->v.p[1]));
  277.                         break;
  278.                 }
  279. }
  280.  
  281. int     xfold(node)
  282. /*
  283.  *      xfold will remove constant nodes and return the values to
  284.  *      the calling routines.
  285.  */
  286. struct enode    *node;
  287. {       int     i;
  288.         if( node == 0 )
  289.                 return 0;
  290.         switch( node->nodetype )
  291.                 {
  292.                 case en_icon:
  293.                         i = node->v.i;
  294.                         node->v.i = 0;
  295.                         return i;
  296.                 case en_add:
  297.                         return xfold(node->v.p[0]) + xfold(node->v.p[1]);
  298.                 case en_sub:
  299.                         return xfold(node->v.p[0]) - xfold(node->v.p[1]);
  300.                 case en_mul:
  301.                         if( node->v.p[0]->nodetype == en_icon )
  302.                                 return xfold(node->v.p[1]) * node->v.p[0]->v.i;
  303.                         else if( node->v.p[1]->nodetype == en_icon )
  304.                                 return xfold(node->v.p[0]) * node->v.p[1]->v.i;
  305.                         else return 0;
  306.                 case en_lsh:
  307.                         if( node->v.p[0]->nodetype == en_icon )
  308.                                 return xfold(node->v.p[1]) << node->v.p[0]->v.i;
  309.                         else if( node->v.p[1]->nodetype == en_icon )
  310.                                 return xfold(node->v.p[0]) << node->v.p[1]->v.i;
  311.                         else return 0;
  312.                 case en_uminus:
  313.                         return - xfold(node->v.p[0]);
  314.                 case en_rsh:    case en_div:
  315.                 case en_mod:    case en_asadd:
  316.                 case en_assub:  case en_asmul:
  317.                 case en_asdiv:  case en_asmod:
  318.                 case en_and:    case en_land:
  319.                 case en_or:     case en_lor:
  320.                 case en_xor:    case en_asand:
  321.                 case en_asor:   case en_void:
  322.                 case en_fcall:  case en_assign:
  323.                         fold_const(&node->v.p[0]);
  324.                         fold_const(&node->v.p[1]);
  325.                         return 0;
  326.                 case en_b_ref:  case en_w_ref:
  327.                 case en_l_ref:  case en_compl:
  328.                 case en_not:
  329.                         fold_const(&node->v.p[0]);
  330.                         return 0;
  331.                 }
  332.         return 0;
  333. }
  334.  
  335. fold_const(node)
  336. /*
  337.  *      reorganize an expression for optimal constant grouping.
  338.  */
  339. struct enode    **node;
  340. {       struct enode    *ep;
  341.         int             i;
  342.         ep = *node;
  343.         if( ep == 0 )
  344.                 return;
  345.         if( ep->nodetype == en_add )
  346.                 {
  347.                 if( ep->v.p[0]->nodetype == en_icon )
  348.                         {
  349.                         ep->v.p[0]->v.i += xfold(ep->v.p[1]);
  350.                         return;
  351.                         }
  352.                 else if( ep->v.p[1]->nodetype == en_icon )
  353.                         {
  354.                         ep->v.p[1]->v.i += xfold(ep->v.p[0]);
  355.                         return;
  356.                         }
  357.                 }
  358.         else if( ep->nodetype == en_sub )
  359.                 {
  360.                 if( ep->v.p[0]->nodetype == en_icon )
  361.                         {
  362.                         ep->v.p[0]->v.i -= xfold(ep->v.p[1]);
  363.                         return;
  364.                         }
  365.                 else if( ep->v.p[1]->nodetype == en_icon )
  366.                         {
  367.                         ep->v.p[1]->v.i -= xfold(ep->v.p[0]);
  368.                         return;
  369.                         }
  370.                 }
  371.         i = xfold(ep);
  372.         if( i != 0 )
  373.                 {
  374.                 ep = makenode(en_icon,i,0);
  375.                 ep = makenode(en_add,ep,*node);
  376.                 *node = ep;
  377.                 }
  378. }
  379.  
  380. opt4(node)
  381. /*
  382.  *      apply all constant optimizations.
  383.  */
  384. struct enode    **node;
  385. {
  386.         opt0(node);
  387.         fold_const(node);
  388.         opt0(node);
  389. }
  390.  
  391.