/* Copyright (C) 1992 by Brian Marick */ /* This file is part of GCT. GCT 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 1, or (at your option) any later version. GCT 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. */ #include #include "c-decl.h" #include "gct-tutil.h" #include "gct-contro.h" #include "gct-assert.h" #include #ifdef TEST #define xmalloc malloc #endif /* Look up comparison-compatible variables. */ /* * SUMMARY: * * When preparing to instrument a function: * Call gct_lookup_init. * When entering a compound statement: * Call gct_lookup_compound_init. * When processing a variable declaration: * Call gct_lookup_decl_init. * When finished processing a variable: * Call gct_lookup_decl_finish. * When finished with a compound statement: * Call gct_lookup_compound_finish. * When finished with a function: * Call gct_lookup_finish * * To find all comparison-compatible variables: * Call name_iterate */ /* Variables global to these routines. More fully explained later. */ /* * This variable is an vector, whose length is the maximum depth of the stack. * Each entry points at a let statement. */ tree *Contour_record; /* This index is the size of the vector pointed to by Contour_record. */ int Contour_record_size; /* * This index represents the entry in the contour record which is the * current top of stack. */ int Contour_index = 0; /* The name of a variable we are currently initializing. */ static char *Init_name = (char *) 0; /* The variable itself. */ static tree Init_var; /* * Tells us if we're in the midst of lookup iteration (successive calls * to name_iterate). */ static int Iterating = 0; /* General explanation */ /* You need to understand c-decl.h and gct-decl.c to understand this. */ /* * The structure of a binding tree is as follows: * * Global contour (struct binding_level) Global variables. * Function contour (struct binding_level) Parameters. * function-body contour (let statement) top level declarations. * nested contour (let statement) nested declarations. * ... * nested contour (let statement) * ... * ... * * * At any particular time, one contour is the current contour. * This forms the top of a stack whose bottom is the global contour. The * stack is linked together by the level_chain field in the LET * statement, but the global and function contour must be special-cased. */ /* * These two variables are used in the following way: * * Contour structure Names * { -- 0 * { -- 0.0 * { -- 0.0.0 * } * } * * { -- 0.1 * { -- 0.1.0 * } * } * } * { -- 1 * } * * Initially, the contour record is initialized such that * Contour_record[0]==0. Contour_record[1] == 0.0. Contour_index == 0. * Invariant: The context_record to be entered is always set up before * entry. * * When we enter a compound statement, Contour_index is incremented. * Contour_record[Contour_index+1] is set to the first LET statement * under this contour (which may be NULL). * * When we exit a contour statement, Contour_index is decremented, and then * Contour_record[Contour_index+1] is set to the next let statement of * the enclosing contour (the just-exited contour's sibling). */ /* * From the contour stack, we make an iterator that returns * "comparison-compatible" variables. Important issues: * * 1. Some callers don't want to know about globals. * 2. Shadowed variables should not be returned. Example: * * { * int a; * { * struct foo a; * <<>> * } * } * * 3. However, shadowing must take place appropriately during declarations: * * { * int a; * { * int c = 2*a; * int b = (c + 1); * <<>> * struct foo a; * } * } * * 4. C's scoping rules are peculiar; therefore, when a variable is * being initialized, it shadows other variables with the same name. * * { * int a; * { * struct foo *a = Array[a]; -- Illegal: A refers to variable * -- being defined. * } * } * * 5. A typedef shadows a variable of the same name. The following code * is illegal and should not be generated by operand instrumentation: * * main() * { * int i, j; * * { * typedef int j; * int *k = j; * } * } * * Structure, enum, and union definitions are NOT illegal. * * * We accomplish this as follows: * * 1. Global variables are distinguished by being on the * global_binding_level, which is ignored if appropriate. * * 2. When a new context is entered, nothing special is done -- initially, * declarations in the block do not shadow. * * 3. As each variable is processed, variables it shadows are marked. * (This happens before the initializer is instrumented.) * * 4. When the block is left, all shadowed variables are unshadowed. * * 5. During lookup, variables in the innermost context are ignored until after * they've been processed. * * 6. The variable currently being initialized is not returned. (It is * legal C to say "int a = a", but it's pretty pointless for our purposes.) */ /* Shadowing Utility Functions. */ /* * This routine tells us whether the item under consideration is a * variable or parameter. The lists we traverse also contain types, tags, * etc. */ #define TALKING_VARIABLE_HERE(possible)\ (TREE_CODE(possible) == VAR_DECL || TREE_CODE(possible) == PARM_DECL) /* * Mark as shadowed/unshadowed the first name in the LIST that matches * NAME. There can be only one. (No duplicate declarations in a correct * C program.) * * The routine returns 1 if something was touched, 0 otherwise. * The return value is important -- it is used to stop processing after * the first variable has been shadowed. Any previous variables have * already been shadowed by it. Similarly, when we unshadow a variable, * this allows us to "pop" the most-recently-shadowed variable, leaving * still shadowed any variables shadowed by it. */ static int mark_name_in_list(name, list, value) char *name; tree list; int value; { assert(name); assert(1 == value || 0 == value); for(; list; list=TREE_CHAIN(list)) { if ( TALKING_VARIABLE_HERE(list) && !strcmp(name, DECL_PRINT_NAME(list))) { DECL_GCT_SHADOWED(list) = value; return 1; } } return 0; } /* Mark a name in any contour above this one. */ static int mark_one_name(name, starting_above, value) char *name; int starting_above; int value; { int index; assert(starting_above >= 0); /* Zero is fine. */ for (index = starting_above-1; index>=0; index--) { if (mark_name_in_list(name, STMT_VARS(Contour_record[index]), value)) return 1; } if (mark_name_in_list(name, current_binding_level->names, value)) return 1; return mark_name_in_list(name, global_binding_level->names, value); } /* * For each name in LIST, unshadow anything shadowed by it. Note that we * unshadow for list elements that didn't in fact shadow anything. This * does no harm: it may unshadow something already unshadowed, but it * cannot incorrectly unshadow a shadowed variable. */ static void unshadow_list(list, starting_above) tree list; int starting_above; { for (; list; list=TREE_CHAIN(list)) { (void) mark_one_name(DECL_PRINT_NAME(list), starting_above, 0); } } /* This routine returns 1 iff no variable in the list is shadowed. */ static int list_unshadowed(list) tree list; { for (; list; list=TREE_CHAIN(list)) { if (TALKING_VARIABLE_HERE(list) && DECL_GCT_SHADOWED(list)) return 0; } return 1; } /* Functions */ /* * This returns the nesting depth of a compound statement. BLOCK_CHAIN * is a list of nested blocks. The nesting depth is 1 if there are no * compound statements. */ gct_block_depth(block_chain) tree block_chain; { int max_child_depth = 0; for(; block_chain; block_chain = TREE_CHAIN(block_chain)) { int retval = gct_block_depth(STMT_SUBBLOCKS(block_chain)); if (retval > max_child_depth) max_child_depth = retval; } return max_child_depth + 1; } /* This routine must be called before processing a particular function. */ void gct_lookup_init() { tree rover; /* To run down the levels. */ /* There has to be an outermost compound statement. */ assert(current_binding_level->blocks); assert(Contour_index == 0); /* Last function popped it to 0. */ assert(!Init_name); /* Can't still be initializing a variable. */ assert(!Iterating); /* Not still matching variables. */ if (Contour_record) /* Get rid of previous run's debris. */ free(Contour_record); Contour_record_size = gct_block_depth(current_binding_level->blocks); assert(Contour_record_size > 0); /* * The array is made one larger than necessary. This simplifies * enter_contour, which would otherwise have to check if it were * entering a bottommost contour. Ditto for code below. */ Contour_record_size++; Contour_record = (tree *) xcalloc(Contour_record_size, sizeof(tree)); Contour_record[0] = current_binding_level->blocks; Contour_index = 0; Contour_record[Contour_index+1] = STMT_SUBBLOCKS(Contour_record[Contour_index]); /* Shadow globals with the parameters. */ for (rover = current_binding_level->names; rover; rover=TREE_CHAIN(rover)) (void) mark_name_in_list(DECL_PRINT_NAME(rover), global_binding_level->names, 1); } /* * A vector of say_nesting_depth elements will not overflow if one entry * per nested compound statement is put into it. gct_lookup_init() must * be called before this. */ int say_nesting_depth() { assert(Contour_record_size > 0); return Contour_record_size; } /* * At end of function's body: unshadow the parameters and globals. * Nothing but variables should be shadowed -- we check this. */ void gct_lookup_finish() { tree rover; assert(Contour_index == 0); assert(!Iterating); /* Unshadow globals and parameters that contour 0 shadows. */ unshadow_list(STMT_VARS(Contour_record[Contour_index]), Contour_index); /* Unshadow any globals that the parameters shadow. */ for (rover = global_binding_level->names; rover; rover=TREE_CHAIN(rover)) { if (TALKING_VARIABLE_HERE(rover)) { DECL_GCT_SHADOWED(rover) = 0; } assert(0 == DECL_GCT_SHADOWED(rover)); } assert(list_unshadowed(current_binding_level->names)); assert(list_unshadowed(global_binding_level->names)); } /* Compound statements */ /* * Call this when entering a new compound statement. After this call, * the compound statement's first nested compound statement is itself ready to * be entered. */ void gct_lookup_compound_init() { assert(Contour_record); assert(!Iterating); /* Not still matching variables. */ Contour_index++; Contour_record[Contour_index+1] = STMT_SUBBLOCKS(Contour_record[Contour_index]); assert(list_unshadowed(STMT_VARS(Contour_record[Contour_index]))); } /* Leave the contour, first clearing all variables shadowed by these vars. */ void gct_lookup_compound_finish() { assert(Contour_record); assert(Contour_index >= 0); assert(!Iterating); /* Not still matching variables. */ assert(list_unshadowed(STMT_VARS(Contour_record[Contour_index]))); unshadow_list(STMT_VARS(Contour_record[Contour_index]), Contour_index); Contour_record[Contour_index] = TREE_CHAIN(Contour_record[Contour_index]); Contour_index--; } /* Declarations */ /* * This routine is called when we are instrumenting the initializer for a * variable. That variable and all later variables must be ignored when * looking for matching variables. Note that the variable being * initialized shadows during the process of declaration. * * This routine assumes it may be called on many different kinds of * tokens. It will only shadow variables, parameters, and typedef names. * If it shadows, Init_var points to what caused the shadowing and * Init_name is its name. If no shadowing is done, Init_var is null, but * Init_name still points at the name. * * (Note: in the current implementation, only variables and typedefs are * passed to this function -- no structure names, for example. We check, * just in case.) */ void gct_lookup_decl_init(name) char *name; { assert(!Init_name); Init_name = name; Init_var = STMT_VARS(Contour_record[Contour_index]); /* This is rather inefficient. */ for(; Init_var; Init_var=TREE_CHAIN(Init_var)) { if ( ( TALKING_VARIABLE_HERE(Init_var) || TREE_CODE(Init_var) == TYPE_DECL) && !strcmp(name, DECL_PRINT_NAME(Init_var))) { break; } } if (Init_var) (void) mark_one_name(name, Contour_index, 1); } /* * This routine is called when instrumentation has moved beyond a * variable. Hereafter, the variable shadows any higher-level variables * with the same name. This routine returns 1 if any variable was touched, * 0 otherwise. * * Note: the NAME passed in is presumably the same as the name just * passed to gct_initializing_variable. We use it for a sanity check. */ void gct_lookup_decl_finish(name) char *name; { assert(name); assert(Init_name); /* Must have been initializing something. */ assert(!strcmp(name, Init_name)); /* Caller error? */ assert(!Iterating); /* Not still matching variables. */ Init_name = (char *)0; Init_var = NULL_TREE; } /* * This returns the variable currently being declared. Note that the * variable may actually be a typedef; the caller must be prepared for this. */ tree gct_lookup_decl_var() { assert(Init_var); return Init_var; } /* * This routine initializes uninitialized variables. Currently, it only * initializes pointers to zero. This is done because operand * instrumentation will cause a core dump if a pointer with a random * non-zero value is presented. The initialization is not done if * operand instrumentation is not turned on; we don't want * instrumentation to make uninitialized-variable bugs less likely to be * found. * * Initializing other types, such as integers is not done. The only * effect such uninitialized pointers can have is to make a test condition * "var might be " hard to satisfy. * Initialization might help -- though zero would be a bad choice -- but * it might be best to let the variables have random values, making the * test condition more likely to be ruled out. * * IDENTIFIER is the gct node to be initialized. * The identifier is a child of a DECLARATION list. * * Notice that the identifier might be in the middle of a declaration: * * int (*identifier)[]; * * The initializer is added as an annotation to the last DECLARATION list * node before the terminating semicolon or comma. */ maybe_initialize(identifier, declaration) gct_node identifier; gct_node declaration; { # define DECLARATION_TERMINATOR(node) \ ((node)->text[0] == ',' || (node)->text[0] == ';') /* First of all, the identifier might not be a variable. It might be a function, for example. If it IS a variable, it's in Init_var. */ if (!operand_on()) return; if (!Init_var) return; /* However, Init_var also includes shadowing typedefs. */ if (!TALKING_VARIABLE_HERE(Init_var)) return; if ( POINTER_TYPE == TREE_CODE(TREE_TYPE(Init_var)) && !TREE_EXTERNAL(Init_var)) { gct_node rover; for (rover=identifier->next; ! DECLARATION_TERMINATOR(rover); rover=rover->next) { assert(rover != declaration->children);/* Wraparound is impossible */ } gct_make_current_note(gct_misc_annotation(permanent_string("=0 /*GCT*/")), rover->prev); } } /* Lookup */ /* * Return the next unreturned comparison-compatible variable, or NULL. * (Comparison-compatibility is defined, along with other compatibility * routines, in gct-tcompat.c.) * * A match to Init_name at the bottommost level is a match to a variable * not-yet-defined (we're instrumenting that name's initializer). Don't * return such a match. * * USE_GLOBAL=DONT_USE_GLOBAL tells the lookup routines to lookup only * local-to-this-function variables. * * WARNING: Iteration continues until NULL is returned. Use end_iteration * to stop before then. The caller MUST either accept all the variables * or use end_iteration. */ tree name_iterate(type, use_global) tree type; int use_global; { static level; /* -1 is function level, -2 is global level. */ static tree next; tree retval; assert(GLOBAL_IN_RANGE(use_global)); if (!Iterating) { Iterating = 1; level = Contour_index; next = STMT_VARS(Contour_record[level]); } while (next) { if ( !TALKING_VARIABLE_HERE(next) || !DECL_PRINT_NAME(next) /* anonymous (gcc-internal?) var */ || DECL_GCT_SHADOWED(next)) { /* Not a useful variable. */ next = TREE_CHAIN(next); } else if ( level == Contour_index /* At lowest level */ && Init_name /* defining a variable */ && !strcmp(Init_name, DECL_PRINT_NAME(next))) { next = NULL_TREE; break; /* No match at this level. */ } else if (comparison_compatible(TREE_TYPE(next), type)) { /* We've found a suitable name. */ break; } else { /* Not the right type */ next = TREE_CHAIN(next); } } /* * At this point, the following is true: * 1. NEXT is null if there's nothing at this level. We must look up * a level. * 2. NEXT is non-null if we have a suitable variable to return: * comparison compatible, not after this variable in the decl-list. */ while (!next) { level--; if (-1 == level) { next = current_binding_level->names; } else if (-2 == level && USE_GLOBAL == use_global) { next = global_binding_level->names; } else if (level <= -2) /* bottomed out or globals not to be used. */ { Iterating = 0; return NULL_TREE; } else { next = STMT_VARS(Contour_record[level]); } /* Note: since we've moved up a level, we're guaranteed not to run into later variables in the argument list. */ while ( next && ( !TALKING_VARIABLE_HERE(next) || !DECL_PRINT_NAME(next) /* anonymous (internal)? var */ || DECL_GCT_SHADOWED(next) || !comparison_compatible(TREE_TYPE(next), type))) { next = TREE_CHAIN(next); } } retval=next; next = TREE_CHAIN(next); return retval; } void end_iteration() { Iterating = 0; } /* Debugging */ void show_visible_variables(type, tag1, tag2) tree type; char *tag1, *tag2; { tree var_to_use; if (!tag1) tag1 = ""; if (!tag2) tag2 = ""; fprintf(stderr, "Visible variables at %s (%s)\n", tag1, tag2); while (var_to_use = name_iterate(type, USE_GLOBAL)) { fprintf(stderr, "=%s\n", DECL_PRINT_NAME(var_to_use)); fflush(stderr); } }