//-*-c++-*- // ==================================================================== // ==================================================================== // // Module: opt_cfg.h // $Revision: 1.3 $ // $Date: 2003/06/12 22:19:34 $ // // ==================================================================== // // Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. // // This program is free software; you can redistribute it and/or modify // it under the terms of version 2 of the GNU General Public License as // published by the Free Software Foundation. // // This program is distributed in the hope that it would be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. // // Further, this software is distributed without any warranty that it // is free of the rightful claim of any third person regarding // infringement or the like. Any license provided herein, whether // implied or otherwise, applies only to this software file. Patent // licenses, if any, provided herein do not apply to combinations of // this program with other software, or any other product whatsoever. // // You should have received a copy of the GNU General Public License // along with this program; if not, write the Free Software Foundation, // Inc., 59 Temple Place - Suite 330, Boston MA 02111-1307, USA. // // Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, // Mountain View, CA 94043, or: // // http://www.sgi.com // // For further information regarding this notice, see: // // http://oss.sgi.com/projects/GenInfo/NoticeExplan // // ==================================================================== // // Description: // // Control Flow Graph // ------------------ // // In preopt phase, the cfg construction performs some form of // lowering for the following opcodes. As result: // Do loop: comprise 4 nodes, INIT, END, BODY, STEP. // The INIT block contains the init statement in the // original WHIRL tree. The END block contains a // OPR_TRUEBR statement which uses the ending condition // in the original WHIRL tree. The STEP block contains // the step increment statement in the original tree. // +-------+ // | INIT | // +-------+ // | // v // ^ // +---- < END > ----> loop exit // | v // | | // | v // | +-------+ // | | BODY | // | +-------+ // | | // | v // | +-------+ // | | STEP | // | +-------+ // | | // +--------+ // // While_do loop: comprise 2 nodes, END, BODY. // | // v // ^ // +---- < END > ----> loop exit // | v // | | // | v // | +-------+ // | | BODY | // | +-------+ // | | // +--------+ // // Do_While loop: comprise 2 nodes, BODY, END. // | // +-----+ | // | | | // | v v // | +-------+ // | | BODY | // | +-------+ // | | // | v // | ^ // + < END > ----> loop exit // | v // | | // +--------+ // // If statement: creates a new bb that contains a OPR_TRUEBR // statement which uses the if condition in the // original tree. The rest of if statement is // connected from this bb. // // Conditional Branch: The ST label is replaced with the pointer // to the branch target BB. // // ==================================================================== // ==================================================================== #ifndef opt_cfg_INCLUDED #define opt_cfg_INCLUDED "opt_cfg.h" #ifndef opt_bb_INCLUDED #include "opt_bb.h" #endif #ifndef opt_fb_INCLUDED #include "opt_fb.h" #endif #ifndef opt_base_INCLUDED #include "opt_base.h" #endif #ifndef CXX_MEMORY_INCLUDED #include "cxx_memory.h" #endif #ifndef ERRORS_INCLUDED #include "errors.h" #endif #ifndef region_util_INCLUDED #include "region_util.h" #endif // forward declarations typedef struct region_id RID; class EXC; class MOD_PHI_BB_CONTAINER; class OPT_STAB; class OPT_TAIL; class CFG { friend class EXITBB_ITER; friend class OPT_TAIL; private: BOOL _trace; // -ttOPT:0x0008 or 0x0004 DYN_ARRAY _bb_vec; // handle to bb table DYN_ARRAY _entry_vec; // hold all entry points DYN_ARRAY _exit_vec; // hold early exit DYN_ARRAY _notreach_vec;// bbs not reached from an entry DYN_ARRAY _agoto_pred_vec; // bbs containing AGOTO statements DYN_ARRAY _agoto_succ_vec; // bbs possibly reached from AGOTO BB_NODE **_dfs_vec; // all bb's pointer in DFS order INT32 _dfs_vec_sz; // the number of entries in it BB_NODE **_po_vec; // all bb's pointer in CFG post-order INT32 _po_vec_sz; // the number of entries in it BB_NODE **_dpo_vec; // dominator tree preorder BB vector INT32 _dpo_vec_sz; // the number of entries in it BB_NODE **_pdo_vec; // post-dominator tree preorder BB vector INT32 _pdo_vec_sz; // the number of entries in it MEM_POOL *_mem_pool; // permenant memory pool MEM_POOL *_loc_pool; // local memory pool BB_NODE *_entry_bb; // assume _entry_bb dominate all bbs. BB_NODE *_exit_bb; // assume exit_bb post dominate all bbs. BB_NODE *_first_bb; // in source order, excluding the fake entry/exit BB_NODE *_last_bb; // in source order, excluding the fake entry/exit BB_NODE *_fake_entry_bb; // the fake entry BB BB_NODE *_fake_exit_bb; // the fake exit BB BB_LOOP *_loops; // the loop structure used in mainopt BOOL _loops_valid; // the loop structure are valid EXC *_exc; // handle to the exception handling INT32 _last_stmt_id; // stmt_id // The following members and methods are for CFG construction use. BB_NODE *_current_bb; // point to bb currently constucting IDTYPE _first_bb_id; // the first bb id in the comp unit IDTYPE _last_bb_id; // to assign bb_id, maintain source order! MAP *_label_map; // map from label to bb IDTYPE _orig_last_label;// the original last label number for this PU IDTYPE _last_label_num; // the last label number for this PU INT32 _cur_loop_depth; // nesting depth of loops BOOL _lower_fully; // to lower hi-scf statements with all // the label/goto inserted OPT_STAB *_opt_stab; // opt_stab pointer CODEMAP *_htable; BOOL _calls_break; // do calls break basic blocks? BOOL _rvi_break_stmt; // break at every stmt for rvi? OPT_FEEDBACK *_feedback; // Pointer to feedback data -- NULL if no data STACK _mp_type; // the mp region type STACK _mp_rid; // the rid of the region STACK _bb_region;// the BB_REGION of the parent (not just mp) RID *_rid; // RID pointer REGION_LEVEL _rgn_level; // context for cfg: preopt/mainopt/rvi BOOL _has_regions; // does the cfg have region nodes? INT32 _dohead_cnt; // number of DOHEAD block, for PRE BB_NODE_SET *_bb_set; // A scratch bb set for temporary use BB_NODE_SET *_non_true_body_set; // scratch bb set for use in Compute_true_loop_body_set CFG(const CFG&); CFG(void); CFG& operator = (const CFG&); void Connect_predsucc (BB_NODE *p, BB_NODE *s) { if (!p->Succ()->Contains(s)) { p->Append_succ(s,_mem_pool); s->Append_pred(p,_mem_pool); } else { Is_True(s->Pred()->Contains(p), ("Bad CFG preds and succs")); } } void DisConnect_predsucc (BB_NODE *p, BB_NODE *s) { p->Remove_succ(s,_mem_pool); s->Remove_pred(p,_mem_pool); } void Connect_after(BB_NODE *p, BB_NODE *s) { p->Insert_After(s); Connect_predsucc(p, s); } void Init_stmtlist(BB_NODE *b, WN *stmt) { b->Set_firststmt(stmt); b->Set_laststmt(stmt); } IDTYPE Alloc_bb_id(void) { return _last_bb_id = _bb_vec.Newidx(); } BB_NODE *New_bb( BOOL connect, BB_KIND k = BB_GOTO ); // create a new block, but do not add it to the cfg BB_NODE *Create_bb( BB_KIND k = BB_GOTO ) { BB_NODE *tmp= CXX_NEW(BB_NODE(), _mem_pool); tmp->Set_kind(k); return tmp; } // attach the block to the cfg, and make it the current block void Append_bb( BB_NODE *bb ) { bb->Set_id(Alloc_bb_id()); _bb_vec[bb->Id()] = bb; if ( _last_bb != NULL ) { _last_bb->Insert_After(bb); } _last_bb = bb; _current_bb = bb; } void Set_current_bb(BB_NODE *b) { _current_bb = b; } // Find out which blocks are not reached from an entrypoint // (see also public version Find_not_reached()) // "can_disconnect" means there are no phi-nodes in the cfg yet, so // we can simply disconnect unreached blocks from their preds/succs void Process_not_reached( BOOL can_disconnect ); void Prop_entry(BB_NODE*) const; // Find all of the blocks that exit from the region, and fill in // the _exit_vec[] array. 'is_whirl' says that block still contains // whirl statements rather than stmtreps. void Find_exit_blocks( void ); // Find blocks that do not exit void Find_no_exit_blocks( BB_NODE *bb, BB_NODE_SET *instack ); void Process_no_exit(void); void Bkwd_prop_exit(BB_NODE*) const; // add a true entrypoint into the region void Add_altentry(BB_NODE *bb) { _entry_vec[_entry_vec.Newidx()] = bb;} // add a block that exits the region or does not reach an exit void Add_earlyexit(BB_NODE *bb) { _exit_vec[_exit_vec.Newidx()] = bb; } // add a block that is not reachable from one of the entrypoints void Add_notreach(BB_NODE *bb) { _notreach_vec[_notreach_vec.Newidx()] = bb; bb->Init_stmt(NULL); // sets first and last WN pointers } void Init_last_label (const IDTYPE lab) { _last_label_num = _orig_last_label = lab; } BOOL Verify_wn(WN *wn, WN *parent, WN_MAP wn_map); void Fill_DFS_vec(BB_NODE *bb); // fill up _dfs_vec and _po_vec // Internal routines for initialization of _dpo_vec and _pdo_vec void Init_dpo_vec(BB_NODE*, INT *id); void Init_pdo_vec(BB_NODE*, INT *id); enum END_BLOCK { END_UNKNOWN, // bad value END_NOT, // does not end block END_FALLTHRU, // ends block, and falls-through to next block END_BREAK // ends block, does not fall-through }; // lower various high-level construct statements to CFG so they are // valid (just as if lowerer had handled them) void Lower_do_loop(WN *wn, END_BLOCK *ends_bb ); void Lower_do_while(WN *wn, END_BLOCK *ends_bb ); void Lower_while_do(WN *wn, END_BLOCK *ends_bb ); void Lower_if_stmt(WN *wn, END_BLOCK *ends_bb ); // add various high-level construct statements to CFG so they can // later be raised back up (mostly preopt phase) void Add_one_io_stmt(WN *wn, END_BLOCK *ends_bb); void Add_one_do_loop_stmt(WN *wn, END_BLOCK *ends_bb ); void Add_one_do_while_stmt(WN *wn, END_BLOCK *ends_bb ); void Add_one_while_do_stmt(WN *wn, END_BLOCK *ends_bb ); void Add_one_if_stmt(WN *wn, END_BLOCK *ends_bb ); void Add_one_compgoto_stmt(WN *wn, END_BLOCK *ends_bb ); void Add_one_region(WN *wn, END_BLOCK *ends_bb ); void Add_one_stmt(WN *func_nd, END_BLOCK *ends_bb ); BB_NODE *Process_entry( WN *wn, END_BLOCK *ends_bb ); void Create_label_stmt(BB_NODE *bb); // in the bb // copy the block of pragma statements into bb void Copy_xpragmas_into(BB_NODE *bb, WN *pragmas); // Create a BB with label BB_NODE *Create_labelled_bb(BB_KIND k=BB_GOTO); // Add loop entry test to current block BB_NODE *Create_entrytest(WN *cond, BB_NODE *target); BB_NODE *Create_loopbody(WN *); // Create loop exit test bb BB_NODE *Create_exittest(WN *, BB_NODE*, BB_KIND); // Create conditional test BB_NODE *Create_conditional(WN *, BB_NODE *, BB_NODE *, BOOL, WN **); // generate the opc_loop_info and attach to the body_bb void Create_loop_info( BB_NODE *body_bb, WN *loop_wn ); void Create_blank_loop_info( BB_NODE *body_bb ); // locate all of the blocks in a given region, filling in the // sets of blocks in each loop FOR PREOPT BB_LOOP *Ident_loop( BB_NODE *first_bb, BB_NODE *last_bb, INT32 loopnest, BB_LOOP *cur_loop ); void Set_loop_bb_set(BB_LOOP *loop); BOOL Check_if_it_can_reach_body_first_bb(BB_NODE *bb, BB_LOOP *loop); void Compute_true_loop_body_set(BB_LOOP *loop); BOOL Loop_itself_is_empty(BB_LOOP *loop); BB_LOOP *Get_last_loop(BB_LOOP *loop); // screen out those BBs originally assigned to the 'loop' but // actually does not belong to the 'loop'. void Screen_out_false_loopnest(BB_LOOP *loop, BB_LOOP *sibling); void Ident_mp_regions(void); // From here on, all are public access functions public: CFG(MEM_POOL *pool, MEM_POOL *lpool); ~CFG(void); BOOL Trace(void) const { return _trace; } void Print(FILE *fp=stderr, BOOL dfs_order = TRUE, IDTYPE bb_id = (IDTYPE) -1); void Validate(FILE *fp=stderr); // create the control-flow graph void Create(WN *func_nd, // the top-level whirl BOOL lower_scf, // lower structured cntl-flow BOOL calls_break, // calls break blocks REGION_LEVEL rgn_level, // caller level: // preopt/mainopt/rvi OPT_STAB *opt_stab,// optimizer symbol table BOOL do_tail); // do tail recursion? void Compute_dom_tree // compute dominator tree or (BOOL build_dom); // post-dominator tree void Compute_dom_frontier(void); void Compute_bbs_reached(void); void Compute_control_dependence (void); MEM_POOL *Mem_pool(void) const{ return _mem_pool; } MEM_POOL *Loc_pool(void) const{ return _loc_pool; } CODEMAP *Htable(void) const{ return _htable; } void Set_htable(CODEMAP *h) { _htable = h; } IDTYPE First_bb_id(void) const{ return _first_bb_id; } IDTYPE Last_bb_id(void) const{ return _last_bb_id; } mUINT32 Total_bb_count(void) const{ return _last_bb_id+1; } BOOL Removable_bb( const BB_NODE *bb ) const; void Remove_bb(BB_NODE *bb); void Remove_path(BB_NODE *pred, BB_NODE *succ); // completely eliminate bb from cfg, loopinfo, phi, usecnt etc. // Only use AFTER SSA is done void Delete_bb(BB_NODE *bb, MOD_PHI_BB_CONTAINER *); BB_NODE *Entry_bb(void) const{ return _entry_bb; } BB_NODE *Exit_bb(void) const{ return _exit_bb; } BB_NODE *Fake_entry_bb(void) const{ return _fake_entry_bb; } BB_NODE *Fake_exit_bb(void) const{ return _fake_exit_bb; } BB_NODE *First_bb(void) const{ return _first_bb; } BB_NODE *Last_bb(void) const{ return _last_bb; } void Set_last_bb( BB_NODE *bb) { _last_bb = bb; } BB_NODE *Get_bb(mINT32 idx) const{ return _bb_vec[idx]; } BB_NODE *Func_entry_bb(void) const; // Split one BB into two consecutive ones. The new BB is returned // to the caller. Assumes only whirl statements. // The given wn becomes the last statement in the old block. BB_NODE *Split_bb_with_wns(BB_NODE *, WN *); // Change_block_kind is used by DCE and CFG to fix up loop-info and // other data structures when part of it is not reachable. void Change_block_kind(BB_NODE *, BB_KIND) const; BB_LOOP *Loops(void) const{ return _loops; } BOOL Loops_valid() const{ return _loops_valid; } void Set_loops(BB_LOOP *l) { _loops = l; } void Set_loops_valid(BOOL b) { _loops_valid = b; } void Set_exc(EXC *exc) { _exc = exc; } EXC *Exc(void) const{ return _exc; } void Reset_stmt_id(void) { _last_stmt_id = INVALID_STMT_ID; } INT32 Get_stmt_id(void) { return ++_last_stmt_id; } void Invalidate_loops(void); LABEL_IDX Alloc_label(void) const { LABEL_IDX idx; New_LABEL(CURRENT_SYMTAB, idx); return idx; } INT32 Cur_loop_depth(void) const{ return _cur_loop_depth; } void Set_cur_loop_depth(INT32 newdepth) { _cur_loop_depth = newdepth; } // Prepend wn at the beginning of bb void Prepend_wn_in(BB_NODE *bb, WN *wn); // Append wn at the end of bb void Append_wn_in(BB_NODE *bb, WN *wn); // is high-level structured control being lowered fully? BOOL Lower_fully(void) const { return _lower_fully; } // do calls end basic blocks? BOOL Calls_break(void) const { return _calls_break; } // do we need to break each stmt into a block for RVI? BOOL Rvi_break_stmt(void) const{ return _rvi_break_stmt; } void Set_rvi_break_stmt(BOOL b){ _rvi_break_stmt = b; } // profile feedback info for this PU OPT_FEEDBACK *Feedback(void) const { return _feedback; } void Set_feedback(OPT_FEEDBACK *fb) { _feedback = fb; } BOOL Has_feedback(void) const { return _feedback != NULL; } // stack for BB_REGION when processing inside a region // (all regions, not just mp) void Push_bb_region(BB_REGION *bbr) { _bb_region.Push(bbr); } BB_REGION *Pop_bb_region(void) { return _bb_region.Pop(); } BB_REGION *Top_bb_region(void) const { return _bb_region.Top(); } void Clear_bb_region(void) { _bb_region.Clear(); } BOOL Null_bb_region(void) const { return _bb_region.Is_Empty(); } // Assuming the MP region has only one entry one exit void Push_mp_type(MP_TY t) { _mp_type.Push(t);} void Push_mp_rid(RID *rid) { _mp_rid.Push(rid); } MP_TY Pop_mp_type(void) { return _mp_type.Pop(); } RID *Pop_mp_rid(void) { return _mp_rid.Pop(); } MP_TY Top_mp_type(void) const { return _mp_type.Top(); } RID *Top_mp_rid(void) const { return _mp_rid.Top(); } BOOL NULL_mp_type(void) const { return _mp_type.Is_Empty(); } void Clear_mp_type(void) { _mp_type.Clear(); } void Clear_mp_rid(void) { _mp_rid.Clear(); } BOOL Inside_mp_do(void) { return !NULL_mp_type() && Top_mp_type() != MP_REGION; } // return the RID tree for this PU or RID for just the region RID *Rid(void) const { return _rid; } // which phase is building a cfg (preopt/mainopt/rvi) REGION_LEVEL Rgn_level(void) const { return _rgn_level; } // were there any region nodes seen in the program void Set_has_regions(void) { _has_regions = TRUE; } BOOL Has_regions(void) const { return _has_regions; } // total number of DOHEAD block in the PU void Inc_dohead_cnt(void) { _dohead_cnt++; } INT32 Dohead_cnt(void) const { return _dohead_cnt; } // return the block associated with the given label number (which // comes either from a WN or is generated internally BB_NODE *Get_bb_from_label(INT32 l) const { return (BB_NODE*) _label_map->Get_val((POINTER) CAST(l)); } void Append_label_map (INT32 labnum, BB_NODE *bb) { _label_map->Add_map((POINTER) CAST(labnum), (POINTER)bb); bb->Set_labnam(labnum); } BB_NODE *Add_bb_to_edge(BB_NODE *, BB_NODE *); // Function name is self-explanatory const BB_LOOP *Find_innermost_loop_contains(BB_NODE *bb); // Find a region with the given pragma, that encloses the given BB // Note that the region encloses "bb" and does not start with it BB_NODE *Find_enclosing_region_bb( BB_NODE *, WN_PRAGMA_ID ); // Determine if this loop is the outermost one in a parallel region // (any sort of parallel loop or region for which we probably do not // wish to perform IVR on...) BOOL Is_outermost_loop_in_parallel_region( BB_LOOP *loop, WN_PRAGMA_ID pragma_id ); // Find blocks in the cfg that are not reached from an entrypoint // (sets Reached() flag for them) void Find_not_reached(); // Connect all agoto blocks to all labels that could be targets void Connect_agotos(); // Remove bb from the list of blocks containing AGOTOs (used during DCE) void Remove_agoto_pred( BB_NODE *bb ); // Return the number of blocks containing potential agoto target labels INT32 Agoto_succ_entries(); // Return the idx'th block containing a potential agoto target labels BB_NODE *Agoto_succ_bb(INT32 idx); // process multiple entry or exit blocks. 'is_whirl' means that // the blocks contain whirl statements rather than stmtreps void Process_multi_entryexit( BOOL is_whirl ); // update pred/succ arcs of fake entry/exit blocks so they are not // reachable from normal blocks void Remove_fake_entryexit_arcs( void ); // Rebuild or mark for rebuilding all auxilliary data structures: // dom/pdom trees, _dpo_vec, _po_vec... void Invalidate_and_update_aux_info(void); // Remove critical edge: add a BB_NODE to each CFG edge where the // source BB has more than one successors and the sink BB has more // than one predecessors. Return the number of edges coverted. INT Remove_critical_edge(); // fill in provided array of BB_NODE *'s so they are ordered in // pred-first order. (i.e., all of a block's predecessors come // before it in the array) // Also return the number of entries in the array. // Uses the Dforder() flag. void Get_pred_first_vec( BB_NODE *bbvec[], INT32 *numbbs ); BB_NODE **Dfs_vec(void); INT32 Dfs_vec_sz(void) const { return _dfs_vec_sz; } BB_NODE **Po_vec(void); INT32 Po_vec_sz(void) const { return _po_vec_sz; } BB_NODE *Po_Bb(INT32 n) const { return _po_vec[n]; } // Dpo_vec() must be invoked before Dpo_Bb(n) can be accessed BB_NODE **Dpo_vec(void); INT32 Dpo_vec_sz(void) const { return _dpo_vec_sz; } BB_NODE *Dpo_Bb(INT32 n) const { return _dpo_vec[n]; } // Pdo_vec() must be invoked before Pdo_Bb(n) can be accessed BB_NODE **Pdo_vec(void); INT32 Pdo_vec_sz(void) const { return _pdo_vec_sz; } BB_NODE *Pdo_Bb(INT32 n) const { return _pdo_vec[n]; } BOOL Verify_tree(WN *); BOOL Verify_cfg(void); // find cyclic regions in the cfg, and attempt to convert them to // higher-level loops by changing their block kinds and setting the // appropriate information. void Find_loop_cycles( void ); BB_LOOP *Analyze_loops(void); // Analyze the loop structure BB_NODE *Find_entry_bb(void); // used by emitters to find code block BOOL Fall_through(BB_NODE *bb1, BB_NODE *bb2); // bb1 falls through to bb2 void Delete_empty_BB(); void Clone_bb(IDTYPE source, IDTYPE dest); // Create a new block and allocate it. BB_NODE *Create_and_allocate_bb( BB_KIND k ) { BB_NODE *bb = Create_bb(k); bb->Set_id(Alloc_bb_id()); _bb_vec[bb->Id()] = bb; return bb; } }; // CFG_ITER iterates forward through the bb next chain in the cfg // class CFG_ITER { private: const CFG *cfg; BB_NODE *cur; CFG_ITER(const CFG_ITER&); CFG_ITER& operator = (const CFG_ITER&); public: CFG_ITER(void) { cfg = NULL; cur = NULL; } CFG_ITER(CFG *g) { cfg = g; cur = NULL; } CFG_ITER(const CFG *g) { cfg = g; cur = NULL; } ~CFG_ITER(void) {} void Init(CFG *g) { cfg = g; } void Init(void) {} BB_NODE *First(void) { return cur = cfg->First_bb(); } BB_NODE *Last(void) { return cur = cfg->Last_bb(); } BB_NODE *Next(void) { return cur = ((cur)? cur->Next() : NULL); } BB_NODE *Prev(void) { return cur = ((cur)? cur->Prev() : NULL); } BB_NODE *Cur(void) { return cur; } BOOL Is_Empty(void) { return cur == NULL; } BOOL Is_Empty_Reverse(void){ return cur == NULL; } BB_NODE *First_elem(void) { return cur = cfg->First_bb(); } BB_NODE *Next_elem(void) { return cur = ((cur)? cur->Next() : NULL); } BB_NODE *Prev_elem(void) { return cur = ((cur)? cur->Prev() : NULL); } }; // Iterator to access the depth-first BB array class DFSBB_ITER { BB_NODE **_dfs_bbs; // depth-first ordering of bb_nodes INT32 _bbs_count; // how many entries in dfs_bbs INT32 _cur; // private constructor so it cannot be used DFSBB_ITER(void); DFSBB_ITER(const DFSBB_ITER&); DFSBB_ITER& operator = (const DFSBB_ITER&); BB_NODE *Dfs_Bb(INT32 n) const{ return _dfs_bbs[n]; } INT32 Bbs_count(void) const{ return _bbs_count; } public: DFSBB_ITER(CFG *cfg) { _dfs_bbs = cfg->Dfs_vec(); _bbs_count = cfg->Dfs_vec_sz(); } ~DFSBB_ITER(void) {} void Init(void) {} INT32 First(void) { return _cur = 0; } INT32 Last(void) { return _cur = Bbs_count() - 1; } INT32 Next(void) { return _cur = _cur + 1; } INT32 Prev(void) { return _cur = _cur - 1; } INT32 Cur(void) { return _cur; } BOOL Is_Empty(void) { return _cur >= Bbs_count(); } BOOL Is_Empty_Reverse(void){ return _cur < 0; } BB_NODE *First_elem(void) { First(); return Dfs_Bb(_cur); } BB_NODE *Last_elem(void) { Last(); return Dfs_Bb(_cur); } BB_NODE *Next_elem(void) { Next(); return Dfs_Bb(_cur); } BB_NODE *Prev_elem(void) { Prev(); return Dfs_Bb(_cur); } }; // Iterator to access the postorder BB array // class POBB_ITER { BB_NODE **_po_bbs; // post ordering of bb_nodes INT32 _bbs_count; // how many entries in po_bbs INT32 _cur; // current PO number // private constructor so it cannot be used POBB_ITER(void); POBB_ITER(const POBB_ITER&); POBB_ITER& operator = (const POBB_ITER&); BB_NODE *Po_Bb(INT32 n) const{ return _po_bbs[n]; } INT32 Bbs_count(void) const{ return _bbs_count; } public: POBB_ITER(CFG *cfg) { _po_bbs = cfg->Po_vec(); _bbs_count = cfg->Po_vec_sz(); } ~POBB_ITER(void) {} void Init(void) {} INT32 First(void) { return _cur = 0; } INT32 Last(void) { return _cur = Bbs_count() - 1; } INT32 Next(void) { return _cur = _cur + 1; } INT32 Prev(void) { return _cur = _cur - 1; } INT32 Cur(void) { return _cur; } BOOL Is_Empty(void) { return _cur >= Bbs_count(); } BOOL Is_Empty_Reverse(void){ return _cur < 0; } BB_NODE *First_elem(void) { First(); return Po_Bb(_cur); } BB_NODE *Last_elem(void) { Last(); return Po_Bb(_cur); } BB_NODE *Next_elem(void) { Next(); return Po_Bb(_cur); } BB_NODE *Prev_elem(void) { Prev(); return Po_Bb(_cur); } }; // Iterator to access the postorder BB array in reverse order // (i.e. a reverse postorder traversal) // class RPOBB_ITER { POBB_ITER _po_iter; // post-order iterator, which we traverse backwards // private constructor so it cannot be used RPOBB_ITER(void); RPOBB_ITER(const RPOBB_ITER&); RPOBB_ITER& operator = (const RPOBB_ITER&); public: RPOBB_ITER(CFG *cfg) : _po_iter(cfg) {} ~RPOBB_ITER(void) {} void Init(void) {} INT32 First(void) { return _po_iter.Last(); } INT32 Last(void) { return _po_iter.First(); } INT32 Next(void) { return _po_iter.Prev(); } INT32 Prev(void) { return _po_iter.Next(); } INT32 Cur(void) { return Last() + First() - _po_iter.Cur(); } BOOL Is_Empty(void) { return _po_iter.Is_Empty_Reverse(); } BOOL Is_Empty_Reverse(void){ return _po_iter.Is_Empty(); } BB_NODE *First_elem(void) { return _po_iter.Last_elem(); } BB_NODE *Last_elem(void) { return _po_iter.First_elem(); } BB_NODE *Next_elem(void) { return _po_iter.Prev_elem(); } BB_NODE *Prev_elem(void) { return _po_iter.Next_elem(); } }; // Iterator to access the dominator/post-dominator tree preorder BB array class DPOBB_ITER { BB_NODE **_dpo_bbs; // dominator/post-dominator tree preorder vector INT32 _bbs_count; // how many entries in dpo_bbs INT32 _cur; // current DPO number // private constructor so it cannot be used DPOBB_ITER(void); DPOBB_ITER(const DPOBB_ITER&); DPOBB_ITER& operator = (const DPOBB_ITER&); BB_NODE *Dpo_Bb(INT32 n) const{ return _dpo_bbs[n]; } INT32 Bbs_count(void) const{ return _bbs_count; } public: DPOBB_ITER(CFG *cfg, BOOL dom = TRUE) { if (dom) { _dpo_bbs = cfg->Dpo_vec(); _bbs_count = cfg->Dpo_vec_sz(); } else { _dpo_bbs = cfg->Pdo_vec(); _bbs_count = cfg->Pdo_vec_sz(); } } ~DPOBB_ITER(void) {} void Init(void) {} INT32 First(void) { return _cur = 0; } INT32 Last(void) { return _cur = Bbs_count() - 1; } INT32 Next(void) { return _cur = _cur + 1; } INT32 Prev(void) { return _cur = _cur - 1; } INT32 Cur(void) { return _cur; } BOOL Is_Empty(void) { return _cur >= Bbs_count(); } BOOL Is_Empty_Reverse(void){ return _cur < 0; } BB_NODE *First_elem(void) { First(); return Dpo_Bb(_cur); } BB_NODE *Last_elem(void) { Last(); return Dpo_Bb(_cur); } BB_NODE *Next_elem(void) { Next(); return Dpo_Bb(_cur); } BB_NODE *Prev_elem(void) { Prev(); return Dpo_Bb(_cur); } }; // Iterator to access the exit_vec dynamic array class EXITBB_ITER { CFG *_cfg; INT32 _cur; // private constructor so it cannot be used EXITBB_ITER(void); EXITBB_ITER(const EXITBB_ITER&); EXITBB_ITER& operator = (const EXITBB_ITER&); public: EXITBB_ITER(CFG *cfg) { _cfg = cfg; } ~EXITBB_ITER(void) {} BB_NODE *Cur_exit_bb() const { return _cfg->_exit_vec[_cur]; } void Init(void) {} void First(void) { _cur = 0; } void Next(void) { _cur++; } BOOL Is_Empty(void) { return _cur > _cfg->_exit_vec.Lastidx(); } }; class MOD_PHI_BB : public SLIST_NODE { BB_NODE *_bb; // the basic that has its phi_list modified PHI_LIST *_old_lst; // old list that got removed from the bb->Phi_list PHI_LIST *_new_lst; // new list that got attached to the bb->Phi_list // unwanted member functions MOD_PHI_BB(const MOD_PHI_BB&); MOD_PHI_BB& operator = (const MOD_PHI_BB&); MOD_PHI_BB(void); public: MOD_PHI_BB(BB_NODE *bb, PHI_LIST *old_lst, PHI_LIST *new_lst): _bb(bb), _old_lst(old_lst), _new_lst(new_lst) {} ~MOD_PHI_BB(void) {} BB_NODE *Bb(void) const { return _bb; } PHI_LIST *Old_lst(void) const { return _old_lst; } PHI_LIST *New_lst(void) const { return _new_lst; } void Set_new_lst(PHI_LIST *lst) { _new_lst = lst; } }; class MOD_PHI_BB_CONTAINER : public SLIST { private: MEM_POOL *_mem_pool; MOD_PHI_BB_CONTAINER(const MOD_PHI_BB_CONTAINER&); MOD_PHI_BB_CONTAINER& operator = (const MOD_PHI_BB_CONTAINER&); DECLARE_SLIST_CLASS( MOD_PHI_BB_CONTAINER, MOD_PHI_BB ) public: MOD_PHI_BB_CONTAINER(MEM_POOL *pool):_mem_pool(pool) {} ~MOD_PHI_BB_CONTAINER(void) {} void Add_entry(BB_NODE *bb, // add entry to this container PHI_LIST *old_lst, PHI_LIST *new_lst); }; class MOD_PHI_BB_ITER : public SLIST_ITER { DECLARE_SLIST_ITER_CLASS( MOD_PHI_BB_ITER, MOD_PHI_BB, MOD_PHI_BB_CONTAINER ) public: void Init() {} }; extern BOOL Remove_region_exit(BB_NODE *, BOOL); extern void Remove_region_entry(BB_NODE *); inline BOOL Is_backedge(BB_NODE *tail, BB_NODE *head) { return head->Dominates(tail); } extern void Add_new_auxid_to_entry_chis(AUX_ID, CFG *, CODEMAP *, OPT_STAB *); #endif // opt_cfg_INCLUDED