C-Breeze C Compiler Infrastructure [ Project home page]

proceduredb.h Go to the documentation of this file. // $Id: proceduredb.h,v 1.41 2003/09/29 14:23:33 toktb Exp $ // ---------------------------------------------------------------------- // // C-Breeze // C Compiler Framework // // Copyright (c) 2000 University of Texas at Austin // // Samuel Z. Guyer // Daniel A. Jimenez // Calvin Lin // // Permission is hereby granted, free of charge, to any person // obtaining a copy of this software and associated documentation // files (the "Software"), to deal in the Software without // restriction, including without limitation the rights to use, copy, // modify, merge, publish, distribute, sublicense, and/or sell copies // of the Software, and to permit persons to whom the Software is // furnished to do so, subject to the following conditions: // // The above copyright notice and this permission notice shall be // included in all copies or substantial portions of the Software. // // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND // NONINFRINGEMENT. IN NO EVENT SHALL THE UNIVERSITY OF TEXAS AT // AUSTIN BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER // IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF // OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN // THE SOFTWARE. // // We acknowledge the C-to-C Translator from MIT Laboratory for // Computer Science for inspiring parts of the C-Breeze design. // // ---------------------------------------------------------------------- #ifndef CBZ_PROCEDUREDB_H #define CBZ_PROCEDUREDB_H class memoryBlock; #include "pointeroptions.h" #include "location.h" #include "dfpreds.h" #include "memoryaccess.h" #include "worklist.h" #include "linker.h" #include "loops.h" #include "callgraph.h" #include "cbztimer.h" class procedureInfo; typedef set< procedureInfo * > procedureinfo_set; typedef procedureinfo_set::iterator procedureinfo_set_p; typedef procedureinfo_set::const_iterator procedureinfo_set_cp; typedef pair< basicblockNode *, basicblockNode *> cfg_edge_pair; typedef set< cfg_edge_pair > cfg_edge_set; typedef cfg_edge_set::iterator cfg_edge_set_p; class procedureInfo { public: typedef map< basicblockNode *, int > worklist_order_map; typedef worklist_order_map::iterator worklist_order_map_p; // -- This is a map from callsites to the caller typedef map< stmtLocation *, procedureInfo *> callsite_map; typedef callsite_map::iterator callsite_map_p; typedef callsite_map::const_iterator callsite_map_cp; typedef map< basicblockLocation *, memoryblock_set > mergepoint_map; typedef mergepoint_map::iterator mergepoint_map_p; // -- Pending changes typedef map< stmtLocation *, memoryblock_set> callsite_changes_map; typedef callsite_changes_map::iterator callsite_changes_map_p; // -- For use in counting contexts: typedef map< procedureInfo *, int > proc_int_map; typedef proc_int_map::iterator proc_int_map_p; private: procNode * _proc; workList _worklist; worklist_order_map _forward_worklist_order; vector< basicblockNode * > _forward_basicblock_order; worklist_order_map _backward_worklist_order; vector< basicblockNode * > _backward_basicblock_order; mergepoint_map _merge_points; DFPreds * _dominance_frontiers; loopTree * _loops; callsite_map _callsites; declNode * _return_variable; memoryBlock * _return_block; // TB returnNode * _return_stmt; bool _never_returns; callsite_changes_map _pending_changes; bool _context_insensitive; bool _prefer_context_sensitive; TREE procLocation * _only_context; memoryblock_set _external_inputs; memoryblock_set _external_outputs; map<memoryBlock*,memoryblock_set> _input_values; // TB typedef pair<memoryBlock*,stmtLocation*> block_loc_pair; // TB map<block_loc_pair,memoryblock_set> _input_site_values; // TB procedureinfo_set _ancestors, /*TB*/ _decestors; procedureInfo * _first_caller; procedureinfo_set _calls; bool _is_recursive; basicblock_set _blocks_to_skip; cfg_edge_set _active_edges; typedef map< basicblockNode *, basicblockNode * > true_branch_map; typedef true_branch_map::iterator true_branch_map_p; true_branch_map _true_branches; int _analysis_count; bool _verbose; cbzTimer _self_timer; cbzTimer _total_timer; int _cg_depth_min, _cg_depth_max; // TB int _cg_height_min, _cg_height_max; // TB public: // EDB: Added! DFPreds * dominance_frontiers() const { return _dominance_frontiers; } procedureInfo(procNode * the_proc); ~procedureInfo(); void add_one_ancestor(procedureInfo *ancestor); void add_ancestor_set(procedureinfo_set & ancestors); void setup_call_at(procedureInfo * caller, stmtLocation * callsite, bool is_recursive_call, bool multiple_target_call); inline procNode * proc() const { return _proc; } inline string & name() { return proc()->decl()->name(); } string qualified_name(); const procedureinfo_set & ancestors() const { return _ancestors; } inline const procedureinfo_set & calls() const { return _calls; } inline const callsite_map & callsites() const { return _callsites; } inline procedureInfo * first_caller() const { return _first_caller; } inline bool is_recursive() const { return _is_recursive; } inline void set_recursive() { _is_recursive = true; } inline declNode * return_variable() const { return _return_variable; } inline memoryBlock * return_block() const { return _return_block; } inline void return_block(memoryBlock *r) { _return_block = r; } inline returnNode * return_stmt() const { return _return_stmt; } inline bool never_returns() const { return _never_returns; } inline void set_never_returns() { _never_returns = true; } void set_pending_changes(stmtLocation * callsite, memoryblock_set & changes); void get_pending_changes(stmtLocation * callsite, memoryblock_set & changes); procedureInfo * caller_at(stmtLocation * callsite); bool is_ancestor(procedureInfo * other); procLocation * procedure_location(stmtLocation * callsite); inline bool is_context_insensitive() const { return _context_insensitive; } inline bool prefer_context_sensitive() const { return _prefer_context_sensitive; } inline void set_prefer_context_sensitive() { _prefer_context_sensitive = true; } procLocation * get_context() const { return _only_context; } void setup_merge_point(memoryBlock * block_to_merge, basicblockLocation * cur); memoryblock_set * lookup_merge_point(basicblockLocation * where); void check_merge_point(memoryBlock * block_to_merge, basicblockLocation * cur); const memoryblock_set & external_inputs() const { return _external_inputs; } const memoryblock_set & external_outputs() const { return _external_outputs; } bool add_external_input(memoryBlock * block); bool add_external_output(memoryBlock * block); // TB void record_input_to_value(memoryBlock *block, stmtLocation *loc, memoryblock_set points_to) { _input_values[block] = points_to; _input_site_values[block_loc_pair(block,loc)] = points_to; } // TB memoryblock_set input_to_value(memoryBlock *block) const { if(_input_values.find(block) == _input_values.end()) return memoryblock_set(); return _input_values.find(block)->second; } // TB memoryblock_set input_to_value(memoryBlock *block, stmtLocation *loc) const { block_loc_pair p(block,loc); if(_input_site_values.find(p) == _input_site_values.end()) return memoryblock_set(); return _input_site_values.find(p)->second; } basicblockNode * get_next_block(Direction dir); void add_block(basicblockNode * block, Direction dir); void add_reachable_blocks(basicblockNode * block, Direction dir); void add_all_blocks(); void add_start_block(Direction dir); bool is_empty() const; void remove_branch_blocks(basicblockNode * cond, basicblockNode * branch_taken, basicblockNode * branch_not_taken); void update_conditional_worklist(basicblockNode * block, bool has_truth_value, bool which_branch); inline cfg_edge_set & active_edges() { return _active_edges; } inline int analysis_count() const { return _analysis_count; } inline void incr_analysis_count() { _analysis_count++; } inline bool is_verbose() const { return _verbose; } bool is_library_routine() { return (proc()->decl()->decl_location() == declNode::UNKNOWN); } void print(ostream & out); void stats(ostream & out); int count_calling_contexts(); int procedure_size(); void start_self_timer() { _self_timer.start(); } void stop_self_timer() { _self_timer.stop(); } double self_timer() { return _self_timer.time(); } void start_total_timer() { _total_timer.start(); } void stop_total_timer() { _total_timer.stop(); } double total_timer() { return _total_timer.time(); } // TB void update_cg_statistics_call(procedureInfo *callee); void update_cg_statistics_return(procedureInfo *callee); void get_cg_statistics(int &cg_depth_min, int &cg_depth_max, int &cg_height_min, int &cg_height_max); private: int count_calling_contexts_rec(proc_int_map & count, stmtNode * callsite); void reverse_post_order(Direction dir, basicblockNode * cur, basicblock_set & visited, basicblock_list & order); void dfs_dominators(Direction dir, basicblockNode * cur, basicblock_set & visited, basicblock_list & order, basicblock_list & rpo_order); int block_position(basicblockNode * block, Direction dir); basicblockNode * block_at(int position, Direction dir); void add_reachable_blocks_rec(Direction dir, basicblockNode * cur, worklist_set & temp, bool first); }; typedef map< procNode *, procedureInfo *> proc_info_map; typedef proc_info_map::iterator proc_info_map_p; typedef list< procedureInfo *> proc_info_list; typedef proc_info_list::iterator proc_info_list_p; typedef pair< stmtLocation *, procedureInfo * > procedurecall_pair; typedef list< procedurecall_pair> procedurecall_stack; typedef procedurecall_stack::iterator procedurecall_stack_p; typedef procedurecall_stack::const_iterator procedurecall_stack_cp; typedef procedurecall_stack::reverse_iterator procedurecall_stack_rp; typedef procedurecall_stack::const_reverse_iterator procedurecall_stack_crp; class procedureDB : public Walker { private: proc_info_map _procedures; callGraph * _callgraph; procedureinfo_set _need_reanalysis; procedureInfo * _root; procedurecall_stack _callstack; proc_info_list _worklist; public: procedureDB(); ~procedureDB(); void build(procNode * root, Linker & linker); void clear(); void add_procedure(procNode * proc); procedureInfo * lookup(procNode * proc); inline const procedurecall_stack & callstack() const { return _callstack; } bool is_recursive_call(procedureInfo * callee, int & num_instances); void setup_analysis(); procedureInfo * next_procedure_on_worklist(); bool is_procedure_on_worklist(procedureInfo * info); void add_procedure_to_worklist(procedureInfo * info); void call_to(stmtLocation * callsite, procedureInfo * callee); void return_from(); bool is_visible_to_caller(procedureInfo * info, memoryBlock * block); bool is_visible_to(procedureInfo * info, memoryBlock * block); inline stmtLocation * current_callsite() { return _callstack.back().first; } procedureInfo * current_caller(); void clear_call_stack(); void print_call_stack(ostream & out); void progress_meter(ostream & out); void mark_for_reanalysis(procedureInfo * info, stmtLocation * callsite, bool include_self); void mark_one_for_reanalysis(procedureInfo * info); bool is_reanalysis_required(procedureInfo * info); void print_leftovers(); int times_called(procedureInfo * info); void stats(ostream & out); int size() const { return _procedures.size(); } void number_of_procedures(int & total, int & analyzed, int & context_insensitive, int & recursive, int & unanalyzed, int & program_size); inline proc_info_map procedures() const { return _procedures; } }; #endif // CBZ_PROCEDUREDB_H

Generated on February 1, 2006
Back to the C-Breeze home page