database.cc

C语言前端编译器,yacc/lex编写,可自行修改代码.

// Copyright 2002 by Keith Vallerio.
// All rights reserved.

/************************************************************
  database.cc

  This is the main analysis file.  It handles the database class
which contains most of the other classes and directs their
interface.  It works in tandem with 'dbio.cc'.

NOTE: LHS -> left hand side
      RHS -> right hand side
************************************************************/

#include "database.h"
#include "ArgPack.h"
#include <algorithm>

#define PARAMETER_DATA_SIZE 0
#define DATA_TYPE_SIZE_UNKNOWN -1

/*###########################################################################*/
DB * DB::def_db_ = 0;
/*===========================================================================*/

DB::DB () :
	function_(), variable_(),
	tree_node_(), tree_start_(),  type_map_(), func_map_(), 
	var_map_(), fn_redeclaration_(false), tg_("task_graph"), fg_(), 
	call_graph_(),	annote_data_(), func_def_name_list_(), undefined_structs_()
{
	Rassert(!def_db_);
	def_db_ = this;
	RVector<string> s;

	add_function("global_defs", "void", s);
	add_variable(0, "global_alias_var", "void", s, 1);

	type_map_insert("void", 0);
	type_map_insert("char", 0);
	type_map_insert("short", 0);
	type_map_insert("int", 0);
	type_map_insert("long", 0);
	type_map_insert("register", 0);
	type_map_insert("float", 0);
	type_map_insert("double", 0);
	undefined_structs_.insert("struct unknown");
	undefined_structs_.insert("register");
}

/*===========================================================================*/
// Two major sections of the program: interpret and profile
/*===========================================================================*/
// Build dependence graph for each function in input code.  First
// analyze the abstract syntax tree, build the call graph, determine
// dependences.  End by outputting 2 new C files.
void DB::interpret()
{
	interpret_tree ();
	build_call_graph();
	do_dependence ();
	print_annotated_c();
	print_task_graph_c();
}

// Profile by recompiling annotated C generated by 'interpret'.
// Rerun the new executable.  Read it's output and determine
// task graph edge and node weights based on these values.
void DB::profile()
{
	prof_recompile();
	prof_rerun();
	prof_read_data();
	prof_get_arc_lengths();
}

/*===========================================================================*/
// Support functions for dependence graph generation from AST 
/*===========================================================================*/
// Adds a new function to the list of functions in DB.  If that
// function already exists, it just returns that functions id
// number.  The redeclaration flag is used to prevent duplication
// of the parameter list.
long DB::add_function (string n, string t, RVector<string> s)
{
	if (func_map_.find(n) == func_map_.end()) {
		fn_redeclaration_ = false;
		function_.push_back(Function(n, t, s));
		func_map_[n] = function_.size() - 1;
		return (function_.size() - 1);
	} else {
		fn_redeclaration_ = true;
		return func_map_[n];
	}
}

// Adds a function call to the current function (f).
// 'c' is the callee name, 'r' is the root of the callee subtree in the
// AST, and 'node' is the node number in the AST
long DB::add_func_call (long f, string c, long r, long node)
{
	return function_[f].add_func_call(c, r, node);
}

// Adds a variable to the current function 'f'.
// 'n' is the name of the variable, 't' is the type, 's' is a vector
// of modifying words like 'extern' and 'pointer'.  'size' is equal
// to one for scalars, or indicates array size.
void DB::add_variable (long f, string n, string t, RVector<string> s,
								long size)
{
	// Check if we've seen this variable name before in this scope.
	if (var_map_.find(n) != var_map_.end()) {
		// We don't support nested scopes for variables.
		// Halt unless using VERY loose dependence (allows reading K&R C)
		if (!ArgPack::ap().loosest_dependence()) {
			Rabort();
		} else {
			long var = var_map(n);
			variable_[var] = Var(n, t, s, size);
		}
	// Add the new variable to the variable list and current function
	} else {
		function_[f].add_variable(variable_.size());
		variable_.push_back(Var(n, t, s, size));
		var_map_[n] = variable_.size() - 1;
	}
}

// Add a parameter declaration for the current function 'f'.
// 'n', 't', and 's' have the same meaning as they did in add_variable.
void DB::add_parameter (long f, string n, string t, RVector<string> s)
{
	if (!fn_redeclaration_) {
		if (var_map_.find(n) == var_map_.end()) {
			function_[f].add_variable(variable_.size());
			function_[f].add_parameter(variable_.size());
			variable_.push_back(Var(n, t, s, PARAMETER_DATA_SIZE));
			var_map_[n] = variable_.size() - 1;
		} else {
			cerr << "Parm name (" << n << ") exists already! Probably part of";
			cerr << " standard library." <<  endl;
		}
	}
	// We don't support nested scopes, but needed to 
	// remove assert to understand code with function pointers
//	Rassert (var_map_.find(n) == var_map_.end());
}

// Add an argument to a function call 'c'.
// 'f' is the caller function, 'a' is the arg, 'atype' is the type.
void DB::add_func_call_arg (long f, long c, long a, ArgType atype)
{
	function_[f].add_func_call_arg(c, a, atype);
}

// Lookup map for string -> function index value.
long DB::func_map (string s)
{
	if (func_map_.find(s) != func_map_.end()) {
		return func_map_[s];
	} else {
		return -1;
	}
}

// Lookup map for string -> variable index value.
long DB::var_map (string s)
{
	if (var_map_.find(s) != var_map_.end()) {
		return var_map_[s]; 
	} else {
		return -1;
	}
}

// Lookup map to set data type size
bool DB::type_map_insert(string s, long length)
{
	if (type_map_.find(s) != type_map_.end()) {
		return false;
	} else {
		type_map_[s] = length;
		return true;
	}
}

// Lookup map to get data type size
long DB::type_map_lookup(string s)
{
	if (type_map_.find(s) != type_map_.end()) {
		return type_map_[s];
	} else {
		return DATA_TYPE_SIZE_UNKNOWN;
	}
}

// Same as var_map(s)
long DB::get_literal_id (string s)
{
	long a = var_map(s);
	return a;
}

//**************************************************
// Analysis routines
//------------------
// These functions determine the dependence relationships for the 
// dependence graphs and task graphs for each function.
//**************************************************

// Generates a static-time call graph to indicate which functions
// can be called from which other functions.  Currently, it insists
// that the function calls cannot be cyclic (or recursive).
// NOTE:  Call graph must contain 'main' currently.
void DB::build_call_graph()
{
	// Create one vertex in the call graph for each function
	MAP (x, function_.size()) {
		call_graph_.add_vertex (FNode (function_[x].name(), x));
	}

	// For each function, draw an outgoing edge to each function it calls
	MAP (x, function_.size()) {
		RVector<string> call_list = function_[x].func_call_names();

		MAP (y, call_list.size()) {
			long called_fn = func_map (call_list[y]);
			Rassert(called_fn != -1);
			if (!call_graph_.nodes_linked (x, called_fn)) {
				call_graph_.add_edge (x, called_fn, FEdge(1));
			}
		}
	}

	// Make sure graph isn't cyclic and that it contains a 'main'.
	Rassert (!call_graph_.cyclic());
	Rassert (func_map ("main") != -1);
	call_graph_.setup_subtrees(func_map ("main"));

	// Output call graph in vcg format.
	print_fgraph_vcg();
}

// Determine dependencies for each function.  Topologically sort 
// call graph.  Start at callees and analyze 'main' last.
void DB::do_dependence ()
{
	Rassert (func_map ("main") != -1);
	RVector<long> fn_list = call_graph_.top_sort (func_map ("main"));
	fn_list.push_back(0);

	// Generate a TG for each function.
	MAP (x, function_.size()) {
		fg_.push_back(TGraph (function_[x].name()));
	}

	// Perform dependence analysis in reverse topological order.
	for (long i = fn_list.size() - 1; i >= 0; i--) {
		fg_[fn_list[i]] = fn_dep (fn_list[i]);
	}
}

/////////////////////////////////////////////////////////////////
// One of the main dependence analysis functions.  Walk through the
// actions list and add nodes to the dependence graph accordingly.
TGraph DB::fn_dep (long id)
{
	TGraph fg(function_[id].name());
	// block depth indicates level of nesting for loops and conditionals
	long block_depth = 0;
	// stores nesting information for functions
	RVector<long> func_node_stack, brac_stack;
	// n is the index value of the current node being modified
	long n = fg.get_new_node(id);

	// actions and types are keywords (the type is used for the switch)
	RVector<string> action = function_[id].action();
	RVector<ActionType> action_type = function_[id].action_type();
	RVector<long> action_tree_node = function_[id].action_tree_node();

	RVector<pair<long,long> > assign = function_[id].assign_node();
	RVector<long> vm;
	long fc_num = 0, tmp;
	long last_state_end = 0;
	long assign_target = -1;
	long assign_num = 0, assign_ctr = 0;
	set<long> local_vars;

	function_[id].init_alias_vectors(variable_.size());

	// CLUDGE fix (sorry about that)
	// KSV: Add and extra action_type to take care of out of bounds case
	action_type.push_back(STATE_NUM);

	/////////////////////////////////////
	// For each action in the function...
	/////////////////////////////////////
	MAP (x, action.size()) {
		// get information about the action:  type, name, AST node location
		ActionType atype = action_type[x];
		string s = action[x];
		long tn = action_tree_node[x];
		bool draw_assign_arcs = false;
		long fc_func;		// function callee function index

		/*
		 * Switch handles actions: (modifies current node appropriately)
		 * ------------------------------------------------------------
		 *   Var use: add to node's var use list
		 *   Var mod: add to node's var use and modify lists
		 *   short assign: add to node's var use and modify lists
		 *   assign: set assign target for later
		 *   assign end: draw assignment arcs to assign target
		 *   state end: end of a statement gets its own block (why?)
		 *   loop/cond start: increase block depth, wait for end
		 *   loop/cond end: decrease block depth, assign all possible
		 *       aliases to every variable on the LHS of an assignment
		 *       inside the node
       *   brack open/close: do nothing anymore
		 *   func start: put func call on fc stack, get variables
		 *       modified by func and store in 'vm', if func not
		 *       defined then set a global var '0' as touched
		 *   func end: draw edges to current node from all edges
		 *       between current node and the node with the func start,
		 *			pop fc stack, start new node
		 */
		switch (atype) {
			case VAR_USE:
				fg[n].add_action(s,tn);
				fg[n].add_var_use(function_[id].v_alias_vec(var_map(s)));
				break;
			case VAR_DECL:
				local_vars.insert(var_map(s));
				fg[n].add_action(s,tn);
				fg[n].add_var_mod(function_[id].v_alias_vec(var_map(s)));
				if ((!block_depth) && (action_type[x+1] != VAR_DECL)) {
//KSV
					if (action_type[x+1] != BRAC_OPEN) {
						n = fg.get_new_node(id);
					}
				}
				break;
			case SHORT_ASSIGN_VAR:
				fg[n].add_action(s,tn);
				fg[n].add_var_mod(function_[id].v_alias_vec(var_map(s)));
				break;
			case ASSIGN:
//KSV2				if (!block_depth) n = fg.get_new_node(id);
				fg[n].add_action(s,tn);
				assign_target = n;
//KSV2				if (!block_depth) n = fg.get_new_node(id);
				assign_ctr++;
				break;
			case ASSIGN_END:
//KSV				fg[n].add_action(s,tn);
				draw_assign_arcs = true;
				if (!block_depth) n = fg.get_new_node(id);
				break;
			case STATE_END:
				// gets it's own node
				if (!block_depth) n = fg.get_new_node(id);
				for (long i = last_state_end + 1; i < n; i++) {
					// These edges will be removed and are of size 0
// KSV:  Adds false dependence...but is needed for some reason
					fg.add_edge(i, n, Edge(0));
				}
				last_state_end = n;
				fg[n].add_action(s,tn);
				if (!block_depth) n = fg.get_new_node(id);
				break;
			case LOOP_START:
			case SELECT_START:
				if (!block_depth) n = fg.get_new_node(id);
				block_depth++;
				fg[n].add_action(s,tn);
				break;
			case LOOP_END:
			case SELECT_END:
				block_depth--;
				fg[n].add_action(s,tn);
				if (!block_depth) {
					RVector<long> lhs_var;
					while (assign_ctr) {
						vm = add_alias_data(id, assign[assign_num]);