optimize.c

类PASCAL语言的编译器,LINUX环境的,我没试过是否正确.

	 printf("%d + %d, ", a, b);
	 a += b;
	 break;

      case COMP_SHIFTLEFT:
	 printf("%d << %d, ", a, b);
	 a <<= b;
	 break;

      case COMP_SHIFTRIGHT:
	 printf("%d >> %d, ", a, b);
	 a >>= b;
	 break;

      case COMP_LESS:
	 printf("%d < %d, ", a, b);
	 a = (a < b);
	 break;

      case COMP_GREATER:
	 printf("%d > %d, ", a, b);
	 a = (a > b);
	 break;

      case COMP_LESSEQ:
	 printf("%d <= %d, ", a, b);
	 a = (a <= b);
	 break;

      case COMP_GREATEQ:
	 printf("%d >= %d, ", a, b);
	 a = (a >= b);
	 break;

      case COMP_EQUAL:
	 printf("%d == %d, ", a, b);
	 a = (a == b);
	 break;

      case COMP_NOTEQUAL:
	 printf("%d != %d, ", a, b);
	 a = (a != b);
	 break;

      case COMP_BINARYAND:
	 printf("%d & %d, ", a, b);
	 a &= b;
	 break;

      case COMP_XOR:
	 printf("%d ^ %d, ", a, b);
	 a ^= b;
	 break;

      case COMP_BINARYOR:
	 printf("%d | %d, ", a, b);
	 a |= b;
	 break;

      case COMP_LOGICAND:
	 printf("%d && %d, ", a, b);
	 a = (a && b);
	 break;

      case COMP_LOGICOR:
	 printf("%d || %d, ", a, b);
	 a = (a || b);
	 break;
   }
   return(a);
}

/*******************************************************************
** Reducable()	- Tells if a certain expression is reducable. It
**		  returns a code telling which optimization that can
**		  be done.
**		  Error codes are stored in 'OptError'
**
**********************/
OptType Reducable(Pass1 type, struct Oper *left, struct Oper *right)
{
   /* If the two operands are constant, then just combine them */
   if(left->constant && right->constant)
   {
      return(OPT_TWO_CONSTANTS);
   }

   /* If the expression is a logical AND, and the left operand is FALSE,
      then we can substitute the expression with 0 */
   if(type == COMP_LOGICAND)
   {
      if(left->constant && !left->num)
      {
	 return(OPT_AND_IS_FALSE);
      }
   }

   /* If the expression is a logical OR, and the left operand is TRUE,
      then we can substitute the expression with 1 */
   if(type == COMP_LOGICOR)
   {
      if(left->constant && left->num)
      {
	 return(OPT_OR_IS_TRUE);
      }
   }

   /* If the expression is a multiplication, and one operand is 1,
      then we can eliminate the multiplication */
   if(type == COMP_MULTIPLY)
   {
      if((left->constant && left->num == 1) ||
         (right->constant && right->num == 1))
      {
	 return(OPT_MULTIPLY_WITH_1);
      }
   }

   /* If the expression is a division with 1,
      then we can eliminate the division */
   if(type == COMP_DIVISION)
   {
      if(right->constant && right->num == 1)
      {
	 return(OPT_DIVISION_WITH_1);
      }
   }

   return(OPT_IMPOSSIBLE);
}

/**********************************************************************
** FreeBranch	- Frees an entire tree recursively
**
************************/
void FreeBranch(struct PNode *top)
{
   /* First free all nodes in the left branch */
   if(top->left)
   {
      FreeBranch(top->left);
   }
   else
   {
      free(top->left);
   }

   /* Then free all nodes in the right one */
   if(top->right)
   {
      FreeBranch(top->right);
   }
   else
   {
      free(top->right);
   }
}

/*********************************************************************
** Reduce()	- Searches the tree recursively for constant expressions
**		  to combine. All branches with a left and a right node
**		  that can be reduced are combined.
**		  If any changes was made, the 'changes' variable will be
**		  non-zero.
**
***************************/
struct PNode *Reduce(struct PNode *node)
{
   struct PNode *left, *right;
   OptType opt_type;	/* Type of optimization that can be made */

   /* Return if the node is already an operand */
   if (node->data.type == COMP_NOTHING)
   {
      return (node);
   }

   /* Search the tree recursively to the left and the right */
   left = Reduce(node->left);
   right = Reduce(node->right);

   /* Find out if the branch can be combined */
   opt_type = Reducable(node->data.type, &left->data, &right->data);

   /* Perform the proper optimizations */
   switch (opt_type)
   {
      /* If both operands are constants, then just combine them */
      case OPT_TWO_CONSTANTS:
	 left->data.num = Calculate(node->data.type,
				    left->data.num,
				    right->data.num);

	 node->data = left->data;
	 free(left);
	 free(right);
	 node->left = NULL;
	 node->right = NULL;
	 node->data.type = COMP_NOTHING;
	 node->data.data = NULL;
	 node->data.constant = TRUE;
	 changed++;
	 return (node);

      /* If the operator is a logical AND, and the left operand is FALSE,
         then the result is 0 */
      case OPT_AND_IS_FALSE:
	 /* Delete the entire expression tree under this node */
	 FreeBranch(node->left);
	 FreeBranch(node->right);
	 node->left = NULL;
	 node->right = NULL;
	 node->data.type = COMP_NOTHING;
	 node->data.num = 0;
	 node->data.data = NULL;
	 node->data.constant = TRUE;
	 changed++;
	 return(node);
	 
      case OPT_OR_IS_TRUE:
	 FreeBranch(node->left);
	 FreeBranch(node->right);
	 node->left = NULL;
	 node->right = NULL;
	 node->data.type = COMP_NOTHING;
	 node->data.num = 1;
	 node->data.data = NULL;
	 node->data.constant = TRUE;
	 changed++;
	 return(node);

      case OPT_MULTIPLY_WITH_1:
	 if(node->left->data.constant && node->left->data.num == 1)
	 {
	    free(node->left);
	    right = node->right;
	    *node = *right;
	    free(right);
	 }
	 else
	 {
	    FreeBranch(node->right);
	    left = node->left;
	    *node = *left;
	    free(left);
	 }
	 changed++;
	 return(node);

      case OPT_DIVISION_WITH_1:
	 free(node->right);
	 left = node->left;
	 *node = *left;
	 free(left);
	 changed++;
	 return(node);

      /* If no optimization could be made, then just return */	 
      case OPT_IMPOSSIBLE:
	 break;
   }
   return (node);
}

/******************************************************************
** MergeConstants	- Move around constants in the tree to create
**			  reducable expressions.
**			  If any changes was made, the 'changes' variable will be
**			  non-zero.
**
**************************/
void MergeConstants(struct PNode *top)
{
   struct PNode *swap;
   BOOL merged;			/* True if a merge was made */

   while (top->left)
   {
      merged = FALSE;

      /* If the right node is an operator, we go down and try to
         merge that tree. If is is an operand and is constant, we
         swap that one with the one on the left branch, but only if
         the operators are the same. If the left branch is also a constant
         we combine them instead of swapping them. */
      if (top->right->data.type != COMP_NOTHING)
      {
	 MergeConstants(top->right);
      }
      else if (top->right->data.constant)
      {
	 if (top->left->data.type == top->data.type)
	 {
	    if (top->left->right->data.constant)
	    {
	       /* Combine the operands if they have the same operator
	          and are constants */
	       top->right->data.num = Calculate(top->data.type,
						top->left->right->data.num,
						top->right->data.num);
	       free(top->left->right);
	       swap = top->left->left;
	       free(top->left);
	       top->left = swap;
	       changed++;
	       merged = TRUE;	/* Signal that we should not step down
	       			   in the tree */
	    }
	    else
	    {
	       /* If the left operand is variable, then just swap */
	       swap = top->right;
	       top->right = top->left->right;
	       top->left->right = swap;
	       changed++;
	    }
	 }
      }
      /* Step down in the tree if we haven't combined any nodes */
      if (!merged)
	 top = top->left;
   }
}

/*****************************************************************
** OptimizeTree	- Optimize the entire expression tree. Reduce()
**		  and MergeConstants() are called until no changes
**		  are made.
**
***************************/
OptErr OptimizeTree(struct PNode *top)
{
   int pass_number = 1;

   OptError = OPT_OK;	/* Clear the error variable */
   
   do
   {
      changed = FALSE;

      printf("------------------------------------------------------------------\n");
      printf("Pass %d:\t\t", pass_number++);
      OutputTree(top);
      printf("\nReducing:\t");

      Reduce(top);
      if(OptError)	/* Break if an error has occurred */
      {
	 break;
      }
      printf("\nReduced:\t");
      OutputTree(top);
      printf("\nMerging:\t");

      MergeConstants(top);
      if(OptError)	/* Break if an error has occurred */
      {
	 break;
      }
      printf("\nMerged:\t\t");
      OutputTree(top);
      printf("\n");

   } while(changed);
   return(OptError);
}

/*****************************************************************
** ReturnExpression()	- Put back the optimized expression tree.
**
***************************/
int ReturnExpression(void *user, struct PNode *tree, BOOL first)
{
   static int x;

   if(first)
   {
      x = 0;
   }

   if (tree->data.type == COMP_NOTHING)
   {
      PutOper(user, &tree->data, x++);
      return(x);
   }

   ReturnExpression(user, tree->left, FALSE);

   PutOper(user, &tree->data, x++);

   ReturnExpression(user, tree->right, FALSE);
   return(x);
}

/*****************************************************************
** OptimizeExpression()	- Optimize an entire expression tree.
**
***************************/
OptErr OptimizeExpression(void *user)
{
   struct PNode *top;	/* The tree root */
   struct Oper oper;
   OptErr ret;
   
   top = ParseExpression(user);

   printf("Original:\t");
   OutputTree(top);
   printf("\n");

   ret = OptimizeTree(top);

   printf("------------------------------------------------------------------\n");
   printf("Optimized:\t");
   OutputTree(top);
   printf("\n");

   oper.type = COMP_LAST;
   oper.num = 0;
   oper.data = NULL;
   oper.constant = 0;
   PutOper(user, &oper, ReturnExpression(user, top, TRUE));
   return(ret);
}