This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] printf optimization
- From: Mark Dettinger <mdetting at yahoo dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 4 Jun 2002 06:22:33 -0700 (PDT)
- Subject: [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