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