This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] printf optimization


This is a patch for GCC 3.1 that introduces a printf optimization:

If possible, then constant arguments are integrated into the format string
at compile-time.

Example:  printf("%d+%d=%d",1,2,x)  
	    turns into  
	  printf("1+2=%d",x)

The optimization works on the abstract syntax tree and runs directly before RTL
generation.


-Mark Dettinger


2002-06-03	Mark Dettinger (mdetting@yahoo.com)

	2 Modified Files:

	* toplev.c: add new switches
	* c-decl.c: insert call to printf optimizer

	5 New Files:

	* md-optimize-printf.h
	* md-optimize-printf.c  printf optimizer
	* md-print-tree.h       
	* md-print-tree.c       outputs trees (for debugging)
	* md-utilities.c        useful functions 

	The functions contained in the 5 new files are included from c-decl.c.
	They could also be put directly into c-decl.c, of course. 


diff -ruN gcc31/gcc/gcc/c-decl.c gcc31md/gcc/gcc/c-decl.c
--- gcc31/gcc/gcc/c-decl.c	Fri May  3 14:07:04 2002
+++ gcc31md/gcc/gcc/c-decl.c	Mon Jun  3 14:50:31 2002
@@ -48,6 +48,8 @@
 #include "c-common.h"
 #include "c-pragma.h"
 
+#include "md-optimize-printf.c"
+
 /* In grokdeclarator, distinguish syntactic contexts of declarators.  */
 enum decl_context
 { NORMAL,			/* Ordinary declaration */
@@ -7078,6 +7080,8 @@
       && MAIN_NAME_P (DECL_NAME (fndecl))
       && DECL_CONTEXT (fndecl) == NULL_TREE)
     expand_main_function ();
+
+  if (optimize_tree) optimize_function(fndecl);
 
   /* Generate the RTL for this function.  */
   expand_stmt (DECL_SAVED_TREE (fndecl));
diff -ruN gcc31/gcc/gcc/md-optimize-printf.c
gcc31md/gcc/gcc/md-optimize-printf.c
--- gcc31/gcc/gcc/md-optimize-printf.c	Mon Jun  3 15:19:49 2002
+++ gcc31md/gcc/gcc/md-optimize-printf.c	Mon Jun  3 14:50:11 2002
@@ -0,0 +1,286 @@
+/* Module: Printf Optimizations
+   Author: Mark Dettinger (mdetting@yahoo.com)
+*/
+
+#include "md-optimize-printf.h"
+
+#include "md-utilities.c"
+#include "md-print-tree.c"
+
+extern int optimize_tree;
+extern int print_tree_before;
+extern int print_tree_after;
+
+/* ---------------------------------------------------------------------- */
+/* Generic Optimization Algorithm                                         */
+/* ---------------------------------------------------------------------- */
+
+static void
+optimize_function (tree fn)
+{
+  if (print_tree_before)
+    print_function_body(fn);
+
+  optimize_stmt (DECL_SAVED_TREE(fn));
+
+  if (print_tree_after) {
+    if (print_tree_before)
+      P("------------------------------------------------------------\n");
+    print_function_body(fn);
+  }
+}
+
+
+static void
+optimize_stmt (tree stmt)
+{
+  /* Recursively optimize the sub-statements until an expression is reached.
+     Then call optimize_expr. */
+
+  if (stmt==NULL) return;
+  switch (TREE_CODE(stmt)) {
+  case COMPOUND_STMT:
+    optimize_stmt_chain(COMPOUND_BODY(stmt));
+    break;
+  case EXPR_STMT:
+    optimize_expr(EXPR_STMT_EXPR(stmt));
+    break;
+  case RETURN_STMT:
+    optimize_expr(RETURN_EXPR(stmt));
+    break;
+  case IF_STMT:
+    optimize_expr(IF_COND(stmt));
+    optimize_stmt(THEN_CLAUSE(stmt));
+    optimize_stmt(ELSE_CLAUSE(stmt));
+    break;
+  case WHILE_STMT:
+    optimize_expr(WHILE_COND(stmt));
+    optimize_stmt(WHILE_BODY(stmt));
+    break;
+  case FOR_STMT:
+    optimize_stmt(FOR_INIT_STMT(stmt));
+    optimize_expr(FOR_COND(stmt));
+    optimize_expr(FOR_EXPR(stmt));
+    optimize_stmt(FOR_BODY(stmt));
+    break;
+  default:
+    /* Do nothing. */
+    break;
+  }
+}
+
+
+static void 
+optimize_stmt_chain (tree stmt)
+{
+  while (stmt) {
+    optimize_stmt(stmt);
+    stmt = TREE_CHAIN(stmt);
+  }
+}
+
+
+static tree
+optimize_expr (tree expr)
+{
+  if (expr==NULL) return NULL;
+
+  switch (TREE_CODE(expr)) {
+  case CALL_EXPR:
+    return optimize_call(expr);
+  default:
+    return expr;
+  }
+}
+
+
+static tree
+optimize_call (tree expr)
+{
+  assert_str (expr!=0, "expr is NULL");
+  assert_str (TREE_CODE(expr)==CALL_EXPR, "expected a CALL_EXPR");
+
+  if (is_printf_call_p(expr)) {
+    return optimize_printf_call(expr);
+  }
+  return expr;
+}
+
+
+/* ---------------------------------------------------------------------- */
+/* Printf Optimization                                                    */
+/* ---------------------------------------------------------------------- */
+
+static int
+is_printf_call_p (tree expr)
+{
+  tree f;
+
+  if (expr==0) return 0;
+  if (TREE_CODE(expr)!=CALL_EXPR) return 0;
+  f = LEFT(expr);
+  return TREE_CODE(f)==ADDR_EXPR && is_printf_function_p(LEFT(f));
+}
+
+static int
+is_printf_function_p (tree expr)
+{
+  if (expr==0) return 0;
+  if (TREE_CODE(expr)!=FUNCTION_DECL) return 0;
+  return strcmp(IDENTIFIER_POINTER(DECL_NAME(expr)),"printf")==0;
+}
+
+static int
+format_string_contains_positional_args (const char* format_string) 
+{
+  char* p;
+  int state = 0;
+
+  for (p=format_string; *p; p++) {
+    switch (state) {
+    case 0:
+      if (*p=='%') {
+	state = 1;
+      }
+      break;
+    case 1:
+      if (isdigit(*p))
+	state = 2;
+      else 
+	state = 0;
+      break;
+    case 2:
+      if (*p=='$') {
+	/* Positional argument found. */
+	return 1;
+      } else if (isdigit(*p)) {
+	state = 2;
+      } else {
+	state = 0;
+      }
+    }
+  }
+  return 0;
+}
+
+static tree
+optimize_printf_call (tree expr)
+{
+  tree arg_list, arg, arg0, format_node;
+  char *p;
+
+  arg_list = RIGHT(expr);
+  arg0 = skip_nop(TREE_VALUE(arg_list));
+  if (TREE_CODE(arg0)!=ADDR_EXPR) 
+    return expr;
+  format_node = LEFT(arg0);
+  if (TREE_CODE(format_node)!=STRING_CST)
+    return expr;
+  arg_list = TREE_CHAIN(arg_list);
+
+  if (format_string_contains_positional_args
(TREE_STRING_POINTER(format_node)))
+    return expr;
+
+  /* Pre-conditions are met. The situation looks like this:
+	 
+            expr
+	   /    \
+	printf  RIGHT(expr)---arg_list---TREE_CHAIN(arg_list)--->...
+                 |               |           |
+                 &              arg         arg2
+                /
+          format_node         
+	       |
+	 format_string 
+  */
+
+  while (arg_list) {
+    arg = skip_nop(TREE_VALUE(arg_list));
+    p = optimize_format_string (TREE_STRING_POINTER(format_node), arg);
+    if (!p) break;
+    TREE_STRING_POINTER(format_node) = p;
+    TREE_CHAIN(RIGHT(expr)) = TREE_CHAIN(arg_list);
+    arg_list = TREE_CHAIN(arg_list);
+  }
+  return expr;
+}
+
+
+static tree
+skip_nop (tree expr)
+{
+  if (expr==0) return 0;
+  if (TREE_CODE(expr)==NOP_EXPR) return skip_nop(LEFT(expr));
+  return expr;
+}
+
+
+/* Takes a format string and a constant node, and returns an optimized format
string
+   where the first conversion specifier is replaced by the constant.
+   Returns NULL, if unsuccessful.
+   Example:  optimize_format_string ("%d + %d", 1, 2) = "1 + %d"
+*/
+static char*
+optimize_format_string (char* format, tree expr)
+{
+  char* result;
+  char* p;
+  int cnt;
+  
+  assert_str (expr!=0, "optimize_format_string: expr is NULL");
+
+  /* If the format string contains more than one conversion specifier,
+     temporarily overwrite the second percent sign with a 0. */
+  cnt = 0;
+  for (p=format; *p; p++) {
+    if (*p=='%') {
+      if (*(p+1)=='%')
+	p++;
+      else
+	cnt++;
+    }
+    if (cnt==2) {
+      *p = 0;
+      break;
+    }
+  }
+
+  /* Example: 
+     If the original format string was "%d + %d = %d",
+     we now have changed it to "%d + ". p points to the remaining string,
+     with the first character overwritten with a 0,
+     i.e. *p = 0 and p+1 = "d = %d".
+  */ 
+
+  switch (TREE_CODE(expr)) {
+  case INTEGER_CST:
+    if ((int)TREE_INT_CST_HIGH(expr)==0) {
+      result = ggc_alloc_string ("", strlen(format)+20);
+      sprintf(result,format,(int)TREE_INT_CST_LOW(expr));
+    } else {
+      /* Integer constant is too big. This can happen in cross-compilers. */
+      result = 0;
+    }
+    break;
+  case ADDR_EXPR:
+    switch (TREE_CODE(LEFT(expr))) {
+    case STRING_CST:
+      result = ggc_alloc_string ("",
strlen(format)+strlen(TREE_STRING_POINTER(LEFT(expr))));
+      sprintf(result,format,TREE_STRING_POINTER(LEFT(expr)));
+      break;
+    default:
+      result = 0;
+    }
+    break;
+  default:
+    result = 0;
+    break;
+  }
+
+  /* Append the remaining unprocessed format string. */
+  if (cnt==2) {
+    *p = '%';
+    if (result) strcat(result,p);
+  }
+  return result;
+}
diff -ruN gcc31/gcc/gcc/md-optimize-printf.h
gcc31md/gcc/gcc/md-optimize-printf.h
--- gcc31/gcc/gcc/md-optimize-printf.h	Mon Jun  3 15:20:50 2002
+++ gcc31md/gcc/gcc/md-optimize-printf.h	Tue May 28 17:31:07 2002
@@ -0,0 +1,20 @@
+
+/* Predicates */
+
+static int is_printf_call_p     (tree expr);
+static int is_printf_function_p (tree expr);
+
+/* Auxiliary Functions */
+
+static tree skip_nop (tree expr);
+
+/* Optimization Algorithms */
+
+static void optimize_function (tree fn);
+static void optimize_stmt (tree stmt);
+static void optimize_stmt_chain (tree stmt);
+
+static tree  optimize_expr (tree expr);
+static tree  optimize_call (tree expr);
+static tree  optimize_printf_call (tree expr);
+static char* optimize_format_string (char* format, tree expr);
diff -ruN gcc31/gcc/gcc/md-print-tree.c gcc31md/gcc/gcc/md-print-tree.c
--- gcc31/gcc/gcc/md-print-tree.c	Mon Jun  3 15:21:04 2002
+++ gcc31md/gcc/gcc/md-print-tree.c	Mon Jun  3 13:50:36 2002
@@ -0,0 +1,238 @@
+#include "md-print-tree.h"
+
+ 
+void println_expr (tree expr) {
+  print_expr(expr);
+  fprintf(stderr,"\n");
+}
+
+void pe (tree expr) { 
+  println_expr(expr); 
+}
+
+void print_string_constant (char* s) {
+  char* p;
+  fprintf (stderr, "\"");
+  for (p=s; *p; p++) {
+    if (*p=='\n')
+      fprintf (stderr, "\\n");
+    else {
+      fputc (*p, stderr);
+    }
+  }
+  fprintf (stderr, "\"");
+}
+
+void print_expr_operator (int code) {
+  switch (code) {
+  case MODIFY_EXPR:
+    fprintf(stderr,"=");
+    break;
+  case PLUS_EXPR:
+    fprintf(stderr,"+");
+    break;
+  case MINUS_EXPR:
+    fprintf(stderr,"-");
+    break;
+  case MULT_EXPR:
+    fprintf(stderr,"*");
+    break;
+  case LSHIFT_EXPR:
+    fprintf(stderr,"<<");
+    break;
+  case RSHIFT_EXPR:
+    fprintf(stderr,">>");
+    break;
+  case EQ_EXPR:
+    fprintf(stderr,"==");
+    break;
+  case LT_EXPR:
+    fprintf(stderr,"<");
+    break;
+  case GT_EXPR:
+    fprintf(stderr,">");
+    break;
+  case LE_EXPR:
+    fprintf(stderr,"<=");
+    break;
+  case GE_EXPR:
+    fprintf(stderr,">=");
+    break;
+  case CALL_EXPR:
+    fprintf(stderr,"call");
+    break;
+  case ADDR_EXPR:
+    fprintf(stderr,"&");
+    break;
+  case NOP_EXPR:
+    fprintf(stderr,"nop");
+    break;
+  case POSTINCREMENT_EXPR:
+    fprintf(stderr,"post++");
+    break;
+  case POSTDECREMENT_EXPR:
+    fprintf(stderr,"post--");
+    break;
+  case PREINCREMENT_EXPR:
+    fprintf(stderr,"pre++");
+    break;
+  case PREDECREMENT_EXPR:
+    fprintf(stderr,"pre--");
+    break;
+  default:
+    fprintf(stderr,"%s", tree_code_name[code]);
+  }
+}
+
+void print_expr (tree expr) {
+  int code;
+
+  if (expr==NULL) return;
+  code = TREE_CODE(expr);
+  if (code>NUM_TREE_CODES) {
+    fprintf(stderr,"(unknown expression of kind %d)",code);
+    return;
+  }
+  switch (code) {
+  case INTEGER_CST:
+    fprintf(stderr,"%d",(int)TREE_INT_CST_LOW(expr));
+    break;
+  case REAL_CST:
+    fprintf(stderr,"<value>");
+    break;
+  case STRING_CST:
+    print_string_constant(TREE_STRING_POINTER(expr));
+    break;
+  case VAR_DECL:
+  case PARM_DECL:
+  case FUNCTION_DECL:
+    print_expr(DECL_NAME(expr));
+    break;
+  case IDENTIFIER_NODE:
+    if (expr!=NULL)
+      fprintf(stderr,"%s",IDENTIFIER_POINTER(expr));
+    break;
+  case TREE_LIST:
+    fprintf(stderr,"(list");
+    print_expr_list(expr);
+    fprintf(stderr,")");
+    break;
+  default:
+    fprintf(stderr,"(");
+    print_expr_operator(code);
+    print_expr_operands(expr);
+    fprintf(stderr,")");
+  }
+}
+
+void print_expr_operands (tree expr) {
+  int i;
+
+  assert_str(tree_code_length[TREE_CODE(expr)]>=0,"negative tree_code
length");
+
+  for (i=0; i<tree_code_length[TREE_CODE(expr)]; i++) {
+    fprintf(stderr," ");
+    print_expr(TREE_OPERAND(expr,i));
+  }
+}
+
+void print_expr_list (tree expr) {
+  tree exp;
+  for (exp = expr; exp != 0; exp = TREE_CHAIN (exp)) {
+    fprintf(stderr," ");
+    print_expr(TREE_VALUE(exp));
+  }
+}
+
+void print_simple_stmt (tree stmt, int indent) 
+{
+  switch (TREE_CODE(stmt)) {
+  case DECL_STMT:
+    fprintf(stderr,"(decl ");
+    print_expr(DECL_STMT_DECL(stmt));
+    fprintf(stderr,")");
+    break;
+  case RETURN_STMT:
+    fprintf(stderr,"(return ");
+    print_expr(RETURN_EXPR(stmt));
+    fprintf(stderr,")");
+    break;
+  case EXPR_STMT:
+    fprintf(stderr,"(expr ");
+    print_expr(EXPR_STMT_EXPR(stmt));
+    fprintf(stderr,")");
+    break;
+  case SCOPE_STMT:
+    fprintf(stderr,"(scope)");
+    break;
+  case IF_STMT:
+    fprintf(stderr,"(if ");
+    print_expr(IF_COND(stmt));
+    fprintf(stderr,"\n");
+    print_stmt(THEN_CLAUSE(stmt),indent+1);
+    if (ELSE_CLAUSE(stmt)) {
+      print_spaces(indent);
+      fprintf(stderr,"else\n");
+      print_stmt(ELSE_CLAUSE(stmt),indent+1);
+    }
+    print_spaces(indent);
+    fprintf(stderr,")");
+    break;
+  case WHILE_STMT:
+    fprintf(stderr,"(while)");
+    break;
+  case FOR_STMT:
+    fprintf(stderr,"(for ");
+    print_simple_stmt(FOR_INIT_STMT(stmt),0);
+    fprintf(stderr," ");
+    print_expr(FOR_COND(stmt));
+    fprintf(stderr," ");
+    print_expr(FOR_EXPR(stmt));
+    fprintf(stderr,"\n");
+    print_stmt(FOR_BODY(stmt),indent+1);
+    print_spaces(indent);
+    fprintf(stderr,")");
+    break;
+  default:
+    fprintf(stderr,"(statement of kind %d)",TREE_CODE(stmt));
+  }
+}
+
+void print_spaces (int n) 
+{
+  int i;
+  for (i=0; i<n; i++)
+    fprintf(stderr,"  ");
+}
+
+void print_stmt (tree stmt, int indent) 
+{
+  if (stmt!=0) {
+    print_spaces(indent);
+    switch (TREE_CODE(stmt)) {
+    case COMPOUND_STMT:
+      fprintf(stderr,"(compound\n");
+      print_stmt_chain(COMPOUND_BODY(stmt),indent+1);
+      fprintf(stderr,")");
+      break;
+    default:
+      print_simple_stmt(stmt,indent);
+    }
+    fprintf(stderr,"\n");
+  }
+}
+
+
+void print_stmt_chain (tree stmt, int indent) 
+{
+  while (stmt && stmt != error_mark_node) {
+    print_stmt(stmt,indent);
+    stmt = TREE_CHAIN(stmt);
+  }
+}
+
+
+void print_function_body (tree fndecl)
+{
+  print_stmt (DECL_SAVED_TREE (fndecl),0);
+}
diff -ruN gcc31/gcc/gcc/md-print-tree.h gcc31md/gcc/gcc/md-print-tree.h
--- gcc31/gcc/gcc/md-print-tree.h	Mon Jun  3 15:21:07 2002
+++ gcc31md/gcc/gcc/md-print-tree.h	Mon Jun  3 14:12:10 2002
@@ -0,0 +1,14 @@
+void print_string_constant (char* s);
+void print_expr_operator (int code);
+void print_expr_operands (tree expr);
+void print_expr_list (tree expr);
+void println_expr (tree expr);
+void print_expr (tree expr);
+void pe (tree expr);
+
+void print_simple_stmt (tree stmt, int indent);
+void print_stmt (tree stmt, int indent);
+void print_stmt_chain (tree stmt, int indent);
+void print_function_body (tree fndecl);
+
+void print_spaces (int n);
diff -ruN gcc31/gcc/gcc/md-utilities.c gcc31md/gcc/gcc/md-utilities.c
--- gcc31/gcc/gcc/md-utilities.c	Mon Jun  3 15:20:58 2002
+++ gcc31md/gcc/gcc/md-utilities.c	Tue May 28 17:13:27 2002
@@ -0,0 +1,30 @@
+/* Print Macro for Debugging Purposes */
+
+#define P(s) fprintf (stderr, s)
+
+/* Shortcuts to access operands of expressions. */
+
+#define LEFT(expr)  TREE_OPERAND(expr,0)
+#define RIGHT(expr) TREE_OPERAND(expr,1)
+
+/* Same shortcuts as functions, so you can use them in gdb. */
+
+static tree left  (tree expr);
+static tree right (tree expr);
+
+static tree left (tree expr) { return LEFT(expr); }
+static tree right (tree expr) { return RIGHT(expr); }
+
+/* Assertion Function */
+
+void assert_str (int cond, const char* errmsg);
+
+void assert_str (int cond, const char* errmsg)
+{
+  if (cond) return;
+  /* If we got here, then the assertion failed.
+     Output error message and exit program. */
+  fprintf(stderr, errmsg);
+  fprintf(stderr,"\n");
+  exit(1);
+}
diff -ruN gcc31/gcc/gcc/toplev.c gcc31md/gcc/gcc/toplev.c
--- gcc31/gcc/gcc/toplev.c	Wed May  1 01:04:51 2002
+++ gcc31md/gcc/gcc/toplev.c	Mon Jun  3 14:54:25 2002
@@ -332,6 +332,10 @@
    based on this variable.  */
 
 int optimize = 0;
+int optimize_tree = 0;
+int print_tree_before = 0;
+int print_tree_after = 0;
+
 
 /* Nonzero means optimize for size.  -Os.
    The only valid values are zero and non-zero. When optimize_size is
@@ -1150,6 +1154,12 @@
    N_("Report on permanent memory allocation at end of run") },
   { "trapv", &flag_trapv, 1,
    N_("Trap for signed overflow in addition / subtraction / multiplication")
},
+  { "optimize-printf", &optimize_tree, 1,
+   N_("Run the Tree Optimizer.") },
+  { "print-tree-before", &print_tree_before, 1,
+   N_("Print the tree before optimizing it.") },
+  { "print-tree-after", &print_tree_after, 1,
+   N_("Print the tree after optimizing it.") },
 };
 
 /* Table of language-specific options.  */


__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]