database.cc

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

						fg[n].add_var_mod(vm);
						lhs_var.push_back(get_assign_lhs_var(id,assign[assign_num]));
						assign_num++;
						assign_ctr--;
					}
					update_lhs_var_aliases(id, lhs_var);
					n = fg.get_new_node(id);
				}
				break;
			case STATE_NUM:
				break;
			case BRAC_OPEN:
break;//KSV
				fg[n].add_action(s,tn);
				brac_stack.push_back(n);
				break;
			case BRAC_CLOSE:
break;//KSV
				fg[n].add_action(s,tn);
				tmp = brac_stack[brac_stack.size() - 1];
				if (tmp != n) {
					for (long i = tmp+1; i <= n; i++) {
						fg.add_edge (i, tmp, Edge(-10000));
					}
				}
				brac_stack.pop_back();
				if (!block_depth) n = fg.get_new_node(id);
				break;
			case FN_START:
//				cout << function_[id].func_call()[fc_num];
				if (!block_depth) n = fg.get_new_node(id);
				fg[n].add_action(s,tn);
				func_node_stack.push_back(n);
				vm = do_func_call(id, fc_num);
				fc_func = func_map(((function_[id].func_call())[fc_num]).name());
				fg[n].add_func(fc_func);
				if (!function_[fc_func].defined()) {
					set<long> vt;
					vt.insert(0);
					function_[fc_func].set_vars_touched(vt);
					fg[n].add_var_mod(0);
					vm.push_back(0);		
				}
				fg[n].add_var_mod(vm);
				fc_num++;
				break;
			case FN_END:
				fg[n].add_action(s,tn);
				tmp = func_node_stack[func_node_stack.size() - 1];
				if (tmp != n) {
					for (long i = tmp+1; i <= n; i++) {
						fg.add_edge (i, tmp, Edge(-10000));
					}
				}
				func_node_stack.pop_back();
				if (!block_depth) n = fg.get_new_node(id);
				break;
		}

		// Post processing for assignments:
		// If an assign end is reached and we aren't inside a
		// loop/cond, draw edges to represent assign data dependencies.
		if (draw_assign_arcs) {
			if (!block_depth) {
				Rassert(assign_target != -1);
				for (long i = assign_target + 1; i < n; i++) {
					fg.add_edge(i, assign_target, Edge(-10000));
				}
				vm = add_alias_data(id, assign[assign_num++]);
				fg[assign_target].add_var_mod(vm);
				assign_ctr--;
//				assign_ctr = 0;
			}
			if (!assign_ctr) {
				assign_target = -1;
			}
		}
	}
	///////////////////////////////////
	// function dependence cleanup
	///////////////////////////////////
	// finish drawing edges in dependence graph
	fg.make_depend_arcs();
	// remove/merge nodes to simplify graph
	fg.compact_graph();

	// Determine which variables would be used/modified during
	// a call to this function.  Currently, assumes that any variable
	// used would be modified as well.
	fg.find_tree_node_starts();
	set<long> vars_touched = fg.determine_vars_touched();
	set<long> new_touched;
//	cout << function_[id].name() << ":  " << vars_touched << endl;
	set_difference(vars_touched.begin(), vars_touched.end(),
						local_vars.begin(), local_vars.end(),
						inserter(new_touched, new_touched.begin()));
	vars_touched = new_touched;

// KSV remove this set difference for stricter analysis
	if (!(ArgPack::ap().strict_dependence())) {
		new_touched.clear();
		set<long> parm_set = function_[id].parameter_set();
		set_difference(vars_touched.begin(), vars_touched.end(),
						parm_set.begin(), parm_set.end(),
						inserter(new_touched, new_touched.begin()));
		vars_touched = new_touched;
	}

//	cout << function_[id].name() << ":  " << vars_touched << endl;
//	if (function_[id].name() == "print_array") {
//		cout << "STUFF: " << vars_touched << endl;
//	}

	// Finally, record variables which are used by this function
	function_[id].set_vars_touched(vars_touched);
	return fg;
}

// Do analysis for a function call by 'id' to whichever function is
// the target of func call number 'fc_num'.  Note: 'fc_num' is NOT
// the number of the callee, rather it is the X'th function call
// invoked by function 'id'!
RVector<long> DB::do_func_call (long id, long fc_num)
{
	// Get callee function index and store in 'func'
	FuncCall fc = function_[id].func_call()[fc_num];
	long func = func_map(fc.name());

	// 2 types of parms: static (in function header)
	//                   call_time (in current function invocation)
	RVector<long> static_parms = function_[func].parameter();
	RVector<pair<long,ArgType> > call_time_parms = fc.parms();

	RVector<long> ret_val;
	set<long> arg_fc_vars;

	// DEBUG STUFF: for when the 2 parms sizes are not equal
//cout << "caller: " << function_[id].name() << "  ";
//cout << fc.name() << "  " << call_time_parms.size() << "  " 
//		<< static_parms.size() << endl;
	if (call_time_parms.size() != static_parms.size()) {
//		if (!(ArgPack::ap().loosest_dependence())) {
			Rassert(!(function_[func].defined()));
//		}
//		Rassert(function_[func].elipses());
	}

	// Analyze function call parameters:
	//    Parameters could be function calls, constants or variables
	MAP(x, call_time_parms.size()) {
		if (call_time_parms[x].second == FUNC) {
			// Handle nested function calls
			// they should return which vars they touch
			// Add those variables to ret_val
			set<long> tset = function_[call_time_parms[x].first].vars_touched();
			set_union(arg_fc_vars.begin(), arg_fc_vars.end(),
							tset.begin(), tset.end(),
							inserter(arg_fc_vars, arg_fc_vars.begin()));

		} else if (call_time_parms[x].second == CONST) {
			// do nothing for consts

		} else if (variable_[call_time_parms[x].first].is_pointer()) {
			// update aliases based on parameters which are variables
			if (x < static_parms.size()) {
				RVector<long> p_alias=function_[func].v_alias_vec(static_parms[x]);
				function_[id].add_aliases (call_time_parms[x].first,p_alias,false);
			}
		}
	}

	///////////////////////////////////////
	// Prepare return value (vars touched)
	///////////////////////////////////////
	// 'parm_set' is indicies of function's static parameters
	set<long> parm_set = function_[func].parameter_set();
   // Returns value encompassing: variables aliased to parms,
   //    and the arguments themselves
	set<long> tmp = function_[id].func_call_cleanup_aliases (
													call_time_parms, static_parms);
	// variables touched inside the function
	set<long> v_touched = function_[func].vars_touched();
	set<long> ret_set;

	// combine the sets to get the set of vars touched
	set_union(arg_fc_vars.begin(), arg_fc_vars.end(),
					tmp.begin(), tmp.end(), inserter(tmp, tmp.begin()));
	set_union(v_touched.begin(), v_touched.end(),
					tmp.begin(), tmp.end(), inserter(tmp, tmp.begin()));

// KSV remove this set difference for stricter analysis
	if (!(ArgPack::ap().strict_dependence())) {
		set_difference(tmp.begin(), tmp.end(),	parm_set.begin(), parm_set.end(),
						inserter(ret_set, ret_set.begin()));
	} else {
		ret_set = tmp;
	}

	// convert set to vector
	set<long>::iterator i;
	for (i = ret_set.begin(); i != ret_set.end(); i++){
		long t = *i;
		ret_val.push_back(t);
	}

	return ret_val;
}

// Determine alias effects for a given assignment.
//       'fn' is the function, 
//       'a_node' gives the boundaries of the assignment
// Note: This function should handle multiple assignments in a
//       single line appropriately.
RVector<long> DB::add_alias_data (long fn, pair<long,long> a_node)
{
	long start = a_node.first;  // first AST node of assignment
	long end = a_node.second;   // last AST node of assignment
	long target = -1, assign_op = -1;
	bool clear_old_alias = false;  // not used
	RVector<long> v;
	string str;

	//-----------------------------------------------------
	// Walk through assignment from first AST node to end.
	// First variable is the target (the first if condition).
	// Next wait to grab an assignment operator. (condition 2 & 3)
	// Finally, all vars on RHS of assign operator are sources (cond 4)
	//-----------------------------------------------------
	for (long i = start; i < end; i++) {
		str = create_var_name (tree_node_[i].name(), fn);
		if (target == -1) {
			// Only grabs first var on left of '=' sign
			// this allows it to only get the 'a' in 'a[i]' statements
			// NOTE: If variable is not in map 'var_map' returns '-1'
			target = get_literal_id (str);
		} else if (tree_node_[i].name() == "assignment_operator") {
			assign_op = i;
// Perhaps one could clear old aliases, but you would have to do 
// control flow checking first so it isn't performed currently...
//KSV				clear_old_alias = true;
		} else if ((tree_node_[i].name() == ">>=") ||
					(tree_node_[i].name() == "<<=") ||
					(tree_node_[i].name() == "+=") ||
					(tree_node_[i].name() == "-=") ||
					(tree_node_[i].name() == "*=") ||
					(tree_node_[i].name() == "/=") ||
					(tree_node_[i].name() == "%=") ||
					(tree_node_[i].name() == "&=") ||
					(tree_node_[i].name() == "^=") ||
					(tree_node_[i].name() == "|=")) {
			assign_op = i;
		} else if (assign_op > -1) {
			long a = get_literal_id(str);
			if (a != -1) {
				v.push_back(a);
			}
		}
	}

	// If it was an assignment, it must have had a target.
	Rassert(target != -1);

	// If the target was a pointer add to it's alias set
	if (variable_[target].is_pointer()) {
		function_[fn].add_aliases (target, v, clear_old_alias);
	}

	// Return the alias vector of the target variable
	return (function_[fn].v_alias_vec(target));
}

// Gets the target of the assignment specified by 'a_node'.
// (The target would be the left most variable.)
long DB::get_assign_lhs_var (long fn, pair<long,long> a_node)
{
	long start = a_node.first, end = a_node.second;
	long target = -1;
	for (long i = start; i < end; i++) {
		string str = create_var_name (tree_node_[i].name(), fn);
		if (target == -1) {
			// Only grabs first var on left of '=' sign
			// this allows it to only get the 'a' in 'a[i]' statements
			// NOTE: If variable is not in map 'var_map' returns '-1'
			target = get_literal_id (str);
		}
		if (target != -1) {	
			return target;
		}
	}
	Rabort();
	return -1;
}

// Give each var in 'lhs_var' the aliases of all the others
void DB::update_lhs_var_aliases (long id, RVector<long> lhs_var)
{
	set<long> s;
	MAP (x, lhs_var.size()) {
		set<long> vs = function_[id].v2v_alias_var(lhs_var[x]);
		set_union(s.begin(), s.end(), vs.begin(), vs.end(),
				inserter(s, s.begin()));
	}
	MAP (x, lhs_var.size()) {
		function_[id].set_v2v_alias_vec(lhs_var[x], s);
	}
}

/*===========================================================================*/
// Output routines
/*===========================================================================*/
// Generates the vcg file to view the call graph
void DB::print_fgraph_vcg ()
{
	ofstream out;
	string file_name = "call_graph.vcg";
	out.open(file_name.c_str());

	if (!out) {
		cout << "Cannot open output file";
		Rabort();
	}

	out << "graph: { label: \"" << file_name << "\"\n";
	out << "display_edge_labels: no\n";

	call_graph_.print_vcg_inside(out);
	

	out << "}\n";
}

// Generates the vcg file to view the task graphs for each function
void DB::print_tgraph_vcg ()
{
	ofstream out;

	// create subdirectory to put vcg files in
	string dir_name = "tmp_vcg";
	string sysstr = "mkdir " + dir_name;
	system(sysstr.c_str());

	// For each function which contains nodes, create a vcg file
	MAP (x, fg_.size()) {
		if (fg_[x].size_vertex()) {
			string s = "tmp_vcg/" + fg_[x].name();
			out.open(s.c_str());
			Rassert(out);

			out << "graph: { label: \"" << s << "\"\n";
			if (ArgPack::ap().display_edge_labels()) {
				out << "display_edge_labels: yes\n";
			} else {
				out << "display_edge_labels: no\n";
			}
			fg_[x].print_vcg_inside(out);
			out << "}\n";
			out.close();
		}
	}
}

// output some database info...(Not used)
ostream &
operator<<(ostream & os, const DB & db_a) {
	os << "Functions:\n";
	MAP (x, db_a.size_function()) {
		os << db_a.function(x) << endl;
	}
	os << "Variables:\n";
	MAP (x, db_a.size_variable()) {
		os << db_a.variable(x) << endl;
	}
	return os;
}

// output method for a set of longs...
ostream &operator <<(ostream &output, set<long> &sa)
{
	set<long>::iterator i;
	for (i = sa.begin(); i != sa.end(); i++) {
		output << *i << " ";
	}
	return output;
}