Index: tree-match.h =================================================================== --- tree-match.h (revision 122842) +++ tree-match.h (working copy) @@ -57,8 +57,9 @@ bb_1st_cfg_node (basic_block bb) */ typedef struct patt_info_s { const char *format_spec; + int sign; va_list *args_ptr; /* only used for anomymous holes */ - struct patt_info_s *next; + struct patt_info_s *next; /* next disjunct in the pattern */ } patt_info; typedef patt_info *pattern; @@ -96,14 +97,16 @@ rmpat (pattern p) static inline void pat_print (pattern p) { + const char *sign; if (!p) return; + sign = (p->sign > 0)? "+" : (p->sign < 0)? "-" : ""; if (!p->next) - fprintf (stderr, "\"%s\"", p->format_spec); + fprintf (stderr, "%s\"%s\"", sign, p->format_spec); else { - fprintf (stderr, "\"%s\" or ", p->format_spec); + fprintf (stderr, "%s\"%s\" or ", sign, p->format_spec); pat_print (p->next); } } @@ -162,9 +165,10 @@ typedef struct condate_s { char *name; /* Used to identify the condate in warning messages. */ pattern from; /* Paths start at nodes matching this pattern. */ pattern to; /* Paths end at nodes matching this pattern. */ - pattern avoid; /* Paths must avoid nodes matching: this pattern, */ + pattern avoid; /* Paths must avoid nodes matching this pattern, */ pattern avoid_then; /* ... successful conditions matching this pattern, */ pattern avoid_else; /* ... and unsuccessful conditions mathing this one. */ + const char *msg; /* message to print if the condate is matched */ } *condate; /* Condate constructor */ @@ -182,6 +186,7 @@ mkcond (const char *name, pattern from, cond->avoid = avoid; cond->avoid_then = avoid_then; cond->avoid_else = avoid_else; + cond->msg = NULL; return cond; } @@ -201,6 +206,17 @@ rmcond (condate cond) extern void print_cond (condate cond); +#define CONDMAX 100 +extern condate conds[CONDMAX]; /* list of condated to check */ +extern int n_conds; /* number of condates to check */ + +extern void normalize_condate(condate cond); +extern void name_condate(condate cond); +extern void add_condate(condate cond); + +extern FILE *checkfile; +extern int condate_parse (void); + /* Tracing levels & macros */ enum trace_level { TRACE_ALWAYS = 0, Index: Makefile.in =================================================================== --- Makefile.in (revision 122842) +++ Makefile.in (working copy) @@ -936,7 +936,7 @@ C_OBJS = c-lang.o stub-objc.o $(C_AND_OB OBJS-common = \ double-int.o tree-chrec.o tree-scalar-evolution.o tree-data-ref.o \ tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o \ - tree-check.o tree-match.o graphite.o \ + tree-check.o tree-match.o condate.tab.o graphite.o \ gimplify.o tree-pretty-print.o tree-into-ssa.o tree-ssa-ter.o \ tree-outof-ssa.o tree-ssa-ccp.o tree-vn.o tree-ssa-uncprop.o \ tree-ssa-dce.o tree-ssa-copy.o tree-nrv.o tree-ssa-copyrename.o \ @@ -1882,6 +1882,14 @@ tree-match.o : tree-match.c $(TREE_FLOW_ $(TREE_DUMP_H) except.h langhooks.h $(CFGLOOP_H) tree-pass.h \ $(CFGLAYOUT_H) $(BASIC_BLOCK_H) hard-reg-set.h $(HASHTAB_H) toplev.h \ tree-ssa-propagate.h tree-match.h +condate.tab.o : condate.tab.c +condate.tab.c : condate.y $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ + $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) $(FLAGS_H) output.h \ + $(DIAGNOSTIC_H) $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \ + $(TREE_DUMP_H) except.h langhooks.h $(CFGLOOP_H) tree-pass.h \ + $(CFGLAYOUT_H) $(BASIC_BLOCK_H) hard-reg-set.h $(HASHTAB_H) toplev.h \ + tree-ssa-propagate.h tree-match.h + $(BISON) $(BISONFLAGS) $< tree-cfgcleanup.o : tree-cfgcleanup.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) $(FLAGS_H) output.h \ $(DIAGNOSTIC_H) errors.h $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \ Index: condate.y =================================================================== --- condate.y (revision 0) +++ condate.y (revision 0) @@ -0,0 +1,307 @@ +/* Condate language for tree/CFG checks. + Copyright (C) 2006 Free Software Foundation, Inc. + Contributed by Nic Volanschi + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +/* The Condate language for expressing user-defined properties + of a program. These properties, called "condates" + blend control-flow, data-flow, syntactic and semantic information. +*/ + +%{ + #define YYSTYPE void * + #include "config.h" + #include "system.h" + #include "coretypes.h" + #include "tm.h" + #include "tree.h" + #include "rtl.h" + #include "tm_p.h" + #include "hard-reg-set.h" + #include "basic-block.h" + #include "output.h" + #include "errors.h" + #include "flags.h" + #include "function.h" + #include "expr.h" + #include "diagnostic.h" + #include "tree-flow.h" + #include "timevar.h" + #include "tree-dump.h" + #include "tree-pass.h" + #include "toplev.h" + #include "tree-match.h" + int yylex (void); + void yyerror (char const *); + +%} + +/* Bison declarations. */ +%name-prefix="condate_" +%token CONDATE +%token FROM +%token TO +%token AVOID +%token IDENT +%right OR +%token STR +%token CCODE +%token WARNING + +%% /* The grammar follows. */ +start: /* empty */ +| start condate {/* print_cond($2); */ + normalize_condate($2); + name_condate($2); + add_condate($2);}; + +condate: CONDATE IDENT '{' crq '}' + WARNING '(' STR ')' ';' {$$ = $4; + ((condate)$$)->name = $2; ((condate)$$)->msg = $8;} +| crq ';' {$$ = $1;}; + +/* Constraint Reachability Queries */ +crq: patexp {$$ = mkcond(NULL, $1, NULL, NULL, NULL, NULL);} +| FROM patexp TO patexp {$$ = mkcond(NULL, $2, $4, NULL, NULL, NULL);} +| FROM patexp TO patexp AVOID patexp {$$ = mkcond(NULL, $2, $4, $6, NULL, NULL);}; + +patexp: edgepat {$$ = $1;} +| patexp OR patexp {$$ = pat_or($1, $3);} +| '(' patexp ')' {$$ = $2;}; + +edgepat: pat {$$ = $1; ((pattern)$$)->sign = 0;} +| '+' pat {$$ = $2; ((pattern)$$)->sign = +1;} +| '-' pat {$$ = $2; ((pattern)$$)->sign = -1;}; + +pat: STR sempat {$$ = mkpat($1); free($1);}; + +sempat: /* empty */ +| '|' CCODE {fprintf(stderr, "%s: warning: semantic patterns NYI: {%s}\n", + tree_check_file, (char *)$2);}; + +%% + +/* The lexical analyzer returns a double floating point + number on the stack and the token NUM, or the numeric code + of the character read if not a number. It skips all blanks + and tabs, and returns 0 for end-of-input. */ + +#include + +/* The folowing should be bigger than all of the folowing: + - the maximal keyword length + - the maximal pattern length + - the maximal length of a CCODE block. + Note: this ugly limit should be eliminated by writing the lexer in Flex. +*/ +#define MAX_KEYWORD_LEN 1024 + +int +yylex (void) +{ + int c; + static char buf[MAX_KEYWORD_LEN + 1]; + int len; + static int afterbar = 0; + + c = getc (checkfile); + /* Skip white space and comments. */ + do + { + while (c == ' ' || c == '\t' || c == '\n') + c = getc (checkfile); + if(c == '#') + { + while ((c = getc (checkfile)) != '\n' && c != EOF) + ; + if (c == '\n') + c = getc (checkfile); + } + } while(c == ' ' || c == '\t' || c == '#' || c == '\n'); + + /* Return end-of-input. */ + if (c == EOF) + return 0; + + /* recognize one-character keywords */ + if (c == '+' || c == '-' || c == ';' + || c == '}' || c == '(' || c == ')') + return c; + if (c == '|') + { + afterbar = 1; + return c; + } + + /* Process strings. */ + if (c == '"') + { + len = 0; + while ((c = getc (checkfile)) != '"' && c != EOF && len < MAX_KEYWORD_LEN) + { + buf[len++] = c; + } + buf[len] = 0; + if (c == EOF || len == MAX_KEYWORD_LEN) + return 0; + yylval = xstrdup(buf); + return STR; + } + + /* Meaning of '{' is context-dependent: */ + if (c == '{') + { + if (!afterbar) + return c; + else + { /* Process C code. */ + len = 0; + while ((c = getc (checkfile)) != '}' && c != EOF && len < MAX_KEYWORD_LEN) + { + buf[len++] = c; + } + if (c == EOF || len == MAX_KEYWORD_LEN) + return 0; + buf[len] = 0; + afterbar = 0; + yylval = xstrdup(buf); + return CCODE; + } + } + /* Recognize keywords & identifiers */ + if (isalpha(c)) + { + len = 0; + buf[len++] = c; + while ((isalnum((c = getc (checkfile))) || c == '_') && len < MAX_KEYWORD_LEN) + { + buf[len++] = c; + } + if (c == EOF || len == MAX_KEYWORD_LEN) + return 0; + buf[len] = 0; + ungetc (c, checkfile); + + /* try keywords */ + if (!strcmp (buf, "condate")) + return CONDATE; + else if (!strcmp (buf, "from")) + return FROM; + else if (!strcmp (buf, "to")) + return TO; + else if (!strcmp (buf, "avoid")) + return AVOID; + else if (!strcmp (buf, "or")) + return OR; + else if (!strcmp (buf, "warning")) + return WARNING; + /* identifier */ + yylval = xstrdup (buf); + return IDENT; + } + + /* Return a single char. */ + fprintf (stderr, "Illegal character: '%c'\n", c); + return 0; +} + +/* Called by yyparse on error. */ +void +yyerror (char const *s) +{ + char buf[32]; + fprintf (stderr, "%s: %s\n", tree_check_file, s); + fgets (buf, 32, checkfile); + fprintf (stderr, "%s: before or near: \"%s\"\n", + tree_check_file, buf); +} + +struct split_pattern_s split_pattern(pattern p); + +/* Structure to return a pattern splitted in: unsigned, positive, and negative + edge patterns. */ +struct split_pattern_s {pattern p1, p2, p3;}; + +struct split_pattern_s +split_pattern (pattern p) +{ + struct split_pattern_s sp; + if (!p) + sp.p1 = sp.p2 = sp.p3 = NULL; + else + { + sp = split_pattern(p->next); + if (p->sign == 0) + { + p->next = sp.p1; + sp.p1 = p; + } + else if (p->sign > 0) + { + p->next = sp.p2; + sp.p2 = p; + } + else + { + p->next = sp.p3; + sp.p3 = p; + } + } + return sp; +} + +/* Normalize a condate by separating the avoid patterns into: + - avoid (unsigned edge patterns), + - avoid_then (positive edge patterns), and + - avoid_else (negative edge patterns). + Normalization conserves the meaning of a condate, but optimizes its matching. + Note: we assume that the initial condate contains only 'avoid' patterns. +*/ +void +normalize_condate (condate cond) +{ + struct split_pattern_s sp = split_pattern (cond->avoid); + cond->avoid = sp.p1; + cond->avoid_then = sp.p2; + cond->avoid_else = sp.p3; +} + +void +name_condate (condate cond) +{ + if(!cond->name) + { + cond->name = xmalloc (strlen (tree_check_file) + 6); + strcpy (cond->name, tree_check_file); + sprintf (cond->name + strlen (tree_check_file), "[%d]", n_conds + 1); + } +} + +void +add_condate (condate cond) +{ + static int warned = 0; + if (n_conds == CONDMAX && !warned) + { + fprintf (stderr, "Warning: ignoring checks beyond %d", CONDMAX); + warned = 1; + return; + } + conds[n_conds++] = cond; +} Index: ChangeLog.graphite =================================================================== --- ChangeLog.graphite (revision 122842) +++ ChangeLog.graphite (working copy) @@ -1,3 +1,20 @@ +2007-03-20 Nic Volanschi + * condate.y: New file. + * tree-match.h (struct patt_info_s): New field sign. + (struct condate_s): New field msg. + (normalize_condate, name_condate, add_condate): New. + (conds[], condate_parse): Made extern. + * tree-check.c (tree_check_warning): First arg changed to cond; warning reformatted. + (tree_check_init): Reset the TREE_VISITED bit on every CFG node. + (tree_scan): New. + (tree_check): Process trivial condates. + (read_delimited_string): Removed. + (print_cond): Print name and msg. + (conds[]): Made extern. + (parse_tree_check_file_once): Rewritten to use the parser in condate.y. + Processing of option --tree_check_string moved to tree_scan(). + * Makefile.in: Added condate.y + 2007-03-12 Sebastian Pop * tree-pretty-print.c (dump_generic_bb_buff, lazy_dump_generic_node): Index: tree-check.c =================================================================== --- tree-check.c (revision 122842) +++ tree-check.c (working copy) @@ -47,21 +47,21 @@ Software Foundation, 51 Franklin Street, tree-match.h. */ static void -tree_check_warning (const char *condname, tree stmt, int check_option) +tree_check_warning (condate cond, tree stmt, int check_option) { location_t saved_location = input_location; if (EXPR_HAS_LOCATION (stmt)) input_location = EXPR_LOCATION (stmt); - warning (check_option, "user-defined check failed:"); - fprintf (stderr, "%s:%d: check = %s,\n", - input_filename, input_line, condname); - fprintf (stderr, "%s:%d: instance = ", input_filename, input_line); + warning (check_option, "user-defined warning %s:", cond->name); + if (cond->msg) + fprintf (stderr, "%s:%d: %s\n", input_location.file, input_location.line, cond->msg); + fprintf (stderr, "%s:%d: instance = ", input_location.file, input_location.line); /* print_local_holes (); */ print_global_holes (); fprintf (stderr, ",\n"); - fprintf (stderr, "%s:%d: reached: ", input_filename, input_line); + fprintf (stderr, "%s:%d: reached: ", input_location.file, input_location.line); print_generic_expr (stderr, stmt, 0); fprintf (stderr, ".\n"); input_location = saved_location; @@ -72,7 +72,18 @@ tree_check_warning (const char *condname static void tree_check_init (void) { + basic_block bb; reset_global_holes (); + FOR_EACH_BB (bb) + { + block_stmt_iterator bsi; + tree stmt; + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + stmt = bsi_stmt (bsi); + TREE_VISITED (stmt) = 0; + } + } } /* Visit a CFG node. Used in tree_check_instance. */ @@ -95,7 +106,7 @@ check_node (cfg_node node, condate cond) if (tree_match_disj (stmt, cond->to, node)) { - tree_check_warning (cond->name, stmt, OPT_ftree_checks_); + tree_check_warning (cond, stmt, OPT_ftree_checks_); return 0; /* follow_none */ } @@ -135,8 +146,9 @@ tree_check_instance (condate cond) for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) { + pattern patt; stmt = bsi_stmt (bsi); - pattern patt = cond->from; + patt = cond->from; PP_TRACE (TRACE_MATCH, { lazy_print_generic_expr (stderr, stmt, 0); @@ -249,15 +261,60 @@ push_global_holes_if_new (VEC (hole_p, h reset_global_holes (); } +/* Check a trivial condate consisting only in a (FROM) pattern. + This comes to reporting every match of the pattern in a function. */ + +static void +tree_scan (condate cond) +{ + basic_block bb; + + FOR_EACH_BB (bb) + { + block_stmt_iterator bsi; + tree stmt; + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + stmt = bsi_stmt (bsi); + + PP_TRACE (TRACE_MATCH, { + lazy_print_generic_expr (stderr, stmt, 0); + fprintf (stderr, "= "); + print_generic_expr (stderr, stmt, 0); + fprintf (stderr, "\n"); + }); + + if (!cond->from || tree_match_disj (stmt, cond->from, bsi_cfg_node (bsi))) + { + tree_check_warning (cond, + cfg_node_stmt (bsi_cfg_node (bsi)), + OPT_ftree_check_); + reset_global_holes (); + } + } + } +} + /* Check a condate on a function. */ static void tree_check (condate cond) { - /* Allocate stack for collecting condate instances. */ - VEC (hole_p, heap) *stack = VEC_alloc (hole_p, heap, 10); + VEC (hole_p, heap) *stack; pattern patt = cond->from; basic_block bb; + + /* Check for trivial condates */ + if (!cond->to) + { + tree_scan (cond); + return; + } + + /* Allocate stack for collecting condate instances. */ + stack = VEC_alloc (hole_p, heap, 10); + patt = cond->from; PP_TRACE (TRACE_CHECK, fprintf (stderr, "searching src pat %s\n", @@ -300,48 +357,13 @@ tree_check (condate cond) VEC_free (hole_p, heap, stack); } -/* Read from a file a string delimted by double quotes. */ - -static char * -read_delimited_string (FILE *infile) -{ - static char buf[256]; - int c, buf_sp; - - /* lookahead(1), to skip comment lines */ - while ((c = getc (infile)) == '#') - { - /* skip to \n */ - while ((c = getc (infile)) != '\n' && c != EOF); - } - - ungetc (c, infile); - - /* skip to opening \" */ - while ((c = getc (infile)) != '"' && c != '\n' && c != EOF); - - if (c == '\n' || c == EOF) - return NULL; /* no string found */ - - /* fill in string contents */ - buf_sp = 0; - while ((c = getc (infile)) != '"' && c != '\n' && c != EOF) - buf[buf_sp++] = c; - - if (c == '\n' || c == EOF) - return NULL; /* unclosed string */ - - /* end string */ - buf[buf_sp] = '\0'; - return buf; -} /* Print a condate. */ void print_cond (condate cond) { - fprintf (stderr, "check("); + fprintf (stderr, "condate %s {", cond->name); pat_print (cond->from); fprintf (stderr, ", "); pat_print (cond->to); @@ -351,7 +373,7 @@ print_cond (condate cond) pat_print (cond->avoid_then); fprintf (stderr, ", "); pat_print (cond->avoid_else); - fprintf (stderr, ")\n"); + fprintf (stderr, "} warning(%s);\n", cond->msg? cond->msg : ""); } /* Check a list of condates on the current function. */ @@ -373,9 +395,8 @@ execute_conds (condate conds[], int n) } } -#define CONDMAX 100 -static condate conds[CONDMAX]; /* list of condated to check */ -static int n_conds = 0; /* number of condates to check */ +condate conds[CONDMAX]; /* list of condated to check */ +int n_conds = 0; /* number of condates to check */ /* Flush the list of condates. */ @@ -393,16 +414,15 @@ delete_conds (condate conds[], int n) n_conds = 0; } +/* Open file containing the checks. Used by the parser condate.y */ +FILE *checkfile; + /* Parse the file containing condates definitions, and cache the result. */ static int parse_tree_check_file_once (void) { static const char *current_check_file = NULL; - static char *str; - static pattern from, to, avoid, avoid_then, avoid_else; - static char *name; - FILE *checkfile; if (current_check_file) { @@ -417,44 +437,19 @@ parse_tree_check_file_once (void) current_check_file = tree_check_file; checkfile = fopen (tree_check_file, "r"); - if (!checkfile) - return -1; - - while (1) + if (!checkfile) { - from = to = avoid = avoid_then = avoid_else = NULL; - - while ((str = read_delimited_string (checkfile)) != NULL) - from = pat_or (mkpat (str), from); - - if (!from) - break; - - while ((str = read_delimited_string (checkfile)) != NULL) - to = pat_or (mkpat (str), to); - - while ((str = read_delimited_string (checkfile)) != NULL) - avoid = pat_or (mkpat (str), avoid); - - while ((str = read_delimited_string (checkfile)) != NULL) - avoid_then = pat_or (mkpat (str), avoid_then); - - while ((str = read_delimited_string (checkfile)) != NULL) - avoid_else = pat_or (mkpat (str), avoid_else); - - name = xmalloc (strlen (tree_check_file) + 6); - strcpy (name, tree_check_file); - sprintf (name + strlen (tree_check_file), "[%03d]", n_conds); - conds[n_conds++] = mkcond (name, from, to, avoid, - avoid_then, avoid_else); - free (name); - if (n_conds == CONDMAX) - { - fprintf (stderr, "Warning: ignoring checks beyond %d", CONDMAX); - break; - } + fprintf (stderr, "tree-check-file %s not found\n", tree_check_file); + return -1; + } + + if (condate_parse () != 0) + { + fclose (checkfile); + return -2; } + fclose (checkfile); return 0; } @@ -477,48 +472,21 @@ execute_tree_check (void) if (tree_check_file) { if (parse_tree_check_file_once () < 0) - { - fprintf (stderr, "tree-check-file %s not found\n", tree_check_file); - return 0; - } - execute_conds (conds, n_conds); + return 0; } else { /* tree_check_string != NULL */ - basic_block bb; - pattern patt = mkpat (tree_check_string); - - reset_global_holes (); - - FOR_EACH_BB (bb) + static const char *current_check_string = NULL; + if (!current_check_string) { - block_stmt_iterator bsi; - tree stmt; - - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - stmt = bsi_stmt (bsi); - - PP_TRACE (TRACE_MATCH, { - lazy_print_generic_expr (stderr, stmt, 0); - fprintf (stderr, "= "); - print_generic_expr (stderr, stmt, 0); - fprintf (stderr, "\n"); - }); - - if (!patt || tree_match_disj (stmt, patt, bsi_cfg_node (bsi))) - { - tree_check_warning (tree_check_string, - cfg_node_stmt (bsi_cfg_node (bsi)), - OPT_ftree_check_); - reset_global_holes (); - } - } + condate cond = mkcond (tree_check_string, mkpat (tree_check_string), + NULL, NULL, NULL, NULL); + add_condate (cond); + current_check_string = tree_check_string; } - - rmpat (patt); } + execute_conds (conds, n_conds); PP_TRACE (TRACE_CHECK, fprintf (stderr, "}\n")); return 0;