Open64: osprey/be/cg/bb.h Source File

00001 /*
00002  * Copyright 2003, 2004, 2005, 2006 PathScale, Inc.  All Rights Reserved.
00003  */
00004 
00005 /*
00006 
00007   Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.
00008 
00009   This program is free software; you can redistribute it and/or modify it
00010   under the terms of version 2 of the GNU General Public License as
00011   published by the Free Software Foundation.
00012 
00013   This program is distributed in the hope that it would be useful, but
00014   WITHOUT ANY WARRANTY; without even the implied warranty of
00015   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
00016 
00017   Further, this software is distributed without any warranty that it is
00018   free of the rightful claim of any third person regarding infringement 
00019   or the like.  Any license provided herein, whether implied or 
00020   otherwise, applies only to this software file.  Patent licenses, if 
00021   any, provided herein do not apply to combinations of this program with 
00022   other software, or any other product whatsoever.  
00023 
00024   You should have received a copy of the GNU General Public License along
00025   with this program; if not, write the Free Software Foundation, Inc., 59
00026   Temple Place - Suite 330, Boston MA 02111-1307, USA.
00027 
00028   Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
00029   Mountain View, CA 94043, or:
00030 
00031   http://www.sgi.com
00032 
00033   For further information regarding this notice, see:
00034 
00035   http://oss.sgi.com/projects/GenInfo/NoticeExplan
00036 
00037 */
00038 
00039 
00040 /* ====================================================================
00041  * ====================================================================
00042  *
00043  * Module: bb.h
00044  * $Revision: 1.7 $
00045  * $Date: 05/12/05 08:59:02-08:00 $
00046  * $Author: bos@eng-24.pathscale.com $
00047  * $Source: /scratch/mee/2.4-65/kpro64-pending/be/cg/SCCS/s.bb.h $
00048  *
00049  * Description:
00050  *
00051  * Definitions for the principal CGIR basic block (BB) structure, with
00052  * related global variable declarations and utility routine prototypes.
00053  *
00054  * Constants:
00055  *
00056  * Utilities:
00057  *
00058  *   BB *Gen_BB(void)
00059  *     Return a new empty BB, not attached to anything else.
00060  *
00061  *   BB *Gen_BB_N(INT n)
00062  *     Create vector of <n> new empty BBs, not attached to anything else.
00063  *     Return pointer to first element in vector.
00064  *
00065  *   BB *Gen_BB_Like (BB *model)
00066  *     Return a new empty BB, with rid like the model bb. If <model>
00067  *     is NULL, then REGION_First_BB is used at a model. If that is NULL,
00068  *     then the behavior is exactly like Gen_BB.
00069  *
00070  *   BB *Gen_And_Append_BB(BB *prev_bb)
00071  *     Requires: BB_next(prev_bb) == NULL
00072  *     Create a new empty BB, append it after <prev_bb>, and return it.
00073  *     The RID is determined by using <prev_bb> as a model for Gen_BB_Like.
00074  *
00075  *   BB *Gen_And_Insert_BB_After(BB *point)
00076  *   BB *Gen_And_Insert_BB_Before(BB *point)
00077  *     Create a new empty BB, append it beofore or after <point>. 
00078  *     The RID is determined by using <point> as a model for Gen_BB_Like.
00079  *
00080  *   void Chain_BBs(BB* bb1, BB* bb2)
00081  *     Chain <bb1> and <bb2> together through their _next and _prev
00082  *     fields.
00083  *
00084  *   void Target_Simple_Fall_Through_BB(BB* bb, BB* target_bb)
00085  *     Make <bb> be a simple fall-through to <target_bb>.  <bb> must
00086  *     a GOTO BB.
00087  *
00088  *   void Target_Logif_BB(BB* bb, BB* br_targ_bb, float br_targ_prob,
00089  *          BB* fall_through_bb)
00090  *     <bb> is a LOGIF BB.  Make it branch to <br_targ_bb> with probability
00091  *     <br_targ_prob> and fall through to <fall_through_bb>.  Handles the 
00092  *     _succs, _preds fields of the 3 blocks and makes the fall through 
00093  *     directly follow <bb> (by adjusting the _next,_prev fields.)  It is 
00094  *     the responsibility of the caller to make sure that the _succ, _preds 
00095  *     fields do not contain any (no invalid) vestiges of previous flow.  
00096  *     This means that the _succs of <bb> should be initialized but empty 
00097  *     and that the _preds should only contain the other BBs that branch 
00098  *     to them.
00099  *
00100  *   void Target_Cond_Branch(BB* bb, BB* br_targ_bb, float br_targ_prob)
00101  *  Same as above, but does nothing with fall thru, nor does it set
00102  *  probabilities.
00103  *
00104  *   void Negate_Logif_BB(BB *bb)
00105  *  Negate the sense of the final branch in the given LOGIF <bb>.
00106  *
00107  *   void Add_Goto(BB *bb, BB *target_bb)
00108  *     Make <bb> goto <target_bb>.  <bb> may not already have a branch
00109  *     instruction. Properly maintains _succs of <bb> and _preds of
00110  *     <target_bb>.
00111  *
00112  *   BB* Create_Dummy_BB( BB *dest_bb )
00113  *     Allocate, initialize, and return a new empty fall through BB that
00114  *     falls through to <dest_bb>.
00115  *
00116  *   UINT16 BB_New_Op_Map_Idx(BB *bb)
00117  *     Return an index that is distinct from the map_idx fields of
00118  *     all other OPs in <bb>.
00119  *
00120  *   UINT16 BB_length(BB *bb)
00121  *     Return the number of OPs in <bb>.
00122  *
00123  *   BB *BB_loop_head_bb(BB *bb)
00124  *     Returns nil if <bb> is not part of any loop.  Otherwise, returns
00125  *     the head of the closest containing natural loop.
00126  *
00127  *   void Set_BB_loop_head_bb(BB *bb, BB *head)
00128  *     Used by the loop finder (see "findloops.h") to indicate <bb> is
00129  *     part of the natural loop headed by <head>.
00130  *
00131  *   UINT16 BB_unrollings(BB *bb)
00132  *     Returns the number of times <bb> has been unrolled.
00133  *
00134  *   BOOL BB_unrolled_fully(BB *bb)
00135  *     Returns TRUE iff <bb> is part of a fully-unrolled loop.
00136  *
00137  *   void Set_BB_unrollings(BB *bb, UINT16 u)
00138  *     Used by loop unroller (see "cg_loop.c") to indicate <bb> has
00139  *     been unrolled <u> times.
00140  *
00141  *   void Set_BB_unrolled_fully(BB *bb)
00142  *   void Reset_BB_unrolled_fully(BB *bb)
00143  *     Used by loop unroller (see "cg_loop.c") to indicate <bb> is
00144  *     part of a fully unrolled loop.  (Reset provided in case it's
00145  *     needed someday.)
00146  *
00147  *   void BB_Insert_Op(BB *bb, OP *point, OP *op, BOOL before)
00148  *     Requires: OP_bb(point) == bb.
00149  *     Insert <op> in <bb>.  If <point> isn't NULL, insert before
00150  *     <point> if <before> or after it otherwise.  If <point> is NULL
00151  *     insert at start of <bb> if <before>, or end of <bb> otherwise.
00152  *     Sets OP_bb(op) to <bb> and OP_map_idx(op) to a value unique in
00153  *     <bb>.  Implemented in "oputil.c".
00154  *
00155  *   void BB_Insert_Ops(BB *bb, OP *point, OPS *ops, BOOL before)
00156  *     Requires: OP_bb(point) == bb.
00157  *     Insert <ops> in <bb>.  If <point> isn't NULL, insert before
00158  *     <point> if <before> or after it otherwise.  If <point> is NULL
00159  *     insert at start of <bb> if <before>, or end of <bb> otherwise.
00160  *     For each OP <op> in <ops>, sets OP_bb(op) to <bb> and
00161  *     OP_map_idx(op) to a value unique in <bb>.  Implemented in
00162  *     "oputil.c".
00163  *
00164  *   void BB_Insert_Op_Before(BB *bb, OP *point, OP *op)
00165  *   void BB_Insert_Op_After(BB *bb, OP *point, OP *op)
00166  *   void BB_Append_Op(BB *bb, OP *op)
00167  *   void BB_Prepend_Op(BB *bb, OP *op)
00168  *   void BB_Insert_Ops_Before(BB *bb, OP *point, OPS *insert_ops)
00169  *   void BB_Insert_Ops_After(BB *bb, OP *point, OPS *insert_ops)
00170  *   void BB_Append_Ops(BB *bb, OPS *insert_ops)
00171  *   void BB_Prepend_Ops(BB *bb, OPS *insert_ops)
00172  *     More-specific names for the general Insert routines.  These do
00173  *     what you think they should do.  Implemented in "oputil.c".
00174  *
00175  *   void BB_Insert_Noops(OP *op, INT num, BOOL before)
00176  *     Insert <num> number of noops either before or after the <op>.
00177  *
00178  *   OP *BB_Remove_Branch(BB *bb)
00179  *     If <bb> has a branch, remove it (and delay slot nop if present).
00180  *     Return the branch OP or NULL (if no branch).
00181  *
00182  *   void BB_Remove_Op(BB *bb, OP *op)
00183  *     Requires: OP_bb(op) == bb.
00184  *     Remove <op> from <bb> and set OP_bb(op) to NULL.
00185  *     Implemented in "oputil.c".
00186  *
00187  *   void BB_Remove_Ops(BB *bb, OPS *ops)
00188  *     Requires: <ops> are in <bb>
00189  *     Remove <ops> from <bb> and set each OP_bb to NULL.
00190  *     Implemented in "oputil.c".
00191  *
00192  *   void BB_Remove_All(BB *bb)
00193  *     Remove all OPs from <bb> and set each OP_bb to NULL.
00194  *     Implemented in "oputil.c".
00195  *
00196  *   void BB_Append_All(BB *to_bb, BB *from_bb)
00197  *     Append all OPs from <from_bb> to <to_bb>.
00198  *     Implemented in "oputil.c".
00199  *
00200  *   void BB_Prepend_All(BB *to_bb, BB *from_bb)
00201  *     Prepend all OPs from <from_bb> to <to_bb>.
00202  *     Implemented in "oputil.c".
00203  *
00204  *   void BB_Move_Op(BB *to_bb, OP *point, BB *from_bb, OP *op, BOOL before)
00205  *   void BB_Move_Op_Before(BB *to_bb, OP *point, BB *from_bb, OP *op)
00206  *   void BB_Move_Op_After(BB *to_bb, OP *point, BB *from_bb, OP *op)
00207  *   void BB_Move_Op_To_Start(BB *to_bb, BB *from_bb, OP *op)
00208  *   void BB_Move_Op_To_End(BB *to_bb, BB *from_bb, OP *op)
00209  *     Requires: OP_bb(point) == to_bb && OP_bb(op) == from_bb
00210  *     Move <op> from <from_bb> to <to_bb>.  If <before> is TRUE, <op>
00211  *     is placed before <point> (or at start of <to_bb> if <point> is
00212  *     NULL); otherwise <op> is placed after <point> (or at end of
00213  *     <to_bb> if <point> is NULL).  The _Before, _After, _To_Start,
00214  *     and _To_End versions are simply abbreviations for the general
00215  *     form (but should be preferred when applicable since they're
00216  *     a little faster).  If <to_bb> and <from_bb> are the same, any
00217  *     local OP_MAP values are retained.  Implemented in "oputil.c".
00218  *
00219  *   void BB_Sink_Op_Before(BB *bb, OP *op, OP *point);
00220  *     Sink an OP before point.   The movement is within a BB,
00221  *     therefore data structure such as CG_DEP_GRAPH, and CG_LOOP
00222  *     are not destroyed.
00223  *
00224  *   BBLIST *BBlist_Find_BB(BBLIST *lst, BB *bb);
00225  *     Returns the BBLIST node in <lst> whose BBLIST_item is <bb>, or NULL
00226  *     if there is none.
00227  *
00228  *   BBLIST *BBlist_Fall_Thru_Succ(BB *bb);
00229  *     Returns a pointer to the BBLIST <node> in BB_succs(list) such that
00230  *     BBLIST_item(node) is the fall through control flow successor of <bb>,
00231  *     or NULL if there is none.    
00232  *
00233  *   BBLIST *BBlist_Fall_Thru_Pred(BB *bb);
00234  *     Returns a pointer to the BBLIST <node> in BB_preds(list) such that
00235  *     BBLIST_item(node) is the fall through control flow predecessor of <bb>,
00236  *     or NULL if there is none.    
00237  *
00238  *   BBLIST *BB_Find_Succ(BB *bb, BB *succ)
00239  *   BBLIST *BB_Find_Pred(BB *bb, BB *pred)
00240  *     Returns the BBLIST node in the successor/predecessor list of <bb>
00241  *  whose BBLIST_item is <succ>/<pred>, or NULL if there is none.
00242  *
00243  *   BOOL BB_in_succ(BB *bb, BB *b)
00244  *     Returns true is b is in BB succ list
00245  *
00246  *   BOOL BB_in_pred(BB *bb, BB *b)
00247  *     Returns true is b is in BB pred list
00248  *
00249  *   INT32 BB_succs_len(BB *bb)
00250  *   INT32 BB_preds_len(BB *bb)
00251  *     return the number of elements in the succs/preds list
00252  *
00253  *   BB *BB_Other_Successor(BB *bb, BB *succ)
00254  *   BB *BB_Other_Predecessor(BB *bb, BB *pred)
00255  *  <bb> has two different successors/predecessors. Return the 
00256  *  successor/predecessor that is not <succ>/<pred>.
00257  * 
00258  *   BB *BB_Unique_Successor( BB *bb );
00259  *   BB *BB_Unique_Predecessor( BB *bb );
00260  *   BB *BB_Unique_Source( BB *bb );
00261  *     If <bb> has a unique successor/predecessor/source, and it IS NOT <bb>,
00262  *     return it.  Otherwise return NULL.
00263  *
00264  *   BB *BB_Fall_Thru_Successor( BB *bb );
00265  *   BB *BB_Fall_Thru_Predecessor( BB *bb );
00266  *     Return the fall through control flow successor/predecessor of <bb>, 
00267  *     or NULL if there is none.
00268  *
00269  *   BOOL BB_Retarget_Branch(BB *bb, BB *from, BB *to)
00270  *     If <bb> branches to <from>, make it branch to <to> instead, updating
00271  *     pred/succ lists, frequency info and returning TRUE. Otherwise, return
00272  *     FALSE;
00273  *
00274  *   BOOL BB_Can_Retarget_Branch(BB *bb, BB *from)
00275  *     Predicate if BB_Retarget_Branch would succeed.
00276  *
00277  *   BOOL BB_Is_Unique_Successor( BB *bb, BB *succ );
00278  *   BOOL BB_Is_Unique_Predecessor( BB *bb, BB *pred );
00279  *     If succ/pred is the unique successor/predecessor, return TRUE
00280  *
00281  *   INT32 BBlist_Len(BBLIST *bblist)
00282  *     return the number of elements in the list
00283  *
00284  *   BOOL BBlist_Has_One_Element(BBLIST *bblist)
00285  *     Return a boolean that indicates iff 'bblist' contains one
00286  *     element. Less overhead than BBlist_Len.
00287  *
00288  *   BOOL BB_Has_One_Succ(BB *bb)
00289  *   BOOL BB_Has_One_Pred(BB *bb)
00290  *     Return a boolean that indicates if 'bb' has one succ/pred.
00291  *     Less overhead than BB_{succs,preds}_len.
00292  *
00293  *   BOOL BB_Move_Delay_Slot_Op (BB *bb)
00294  *     Check if the <bb> is terminated by an OP in the delay slot of an
00295  *     'xfer_op'. If yes, move the delay slot OP above the xfer_op. If
00296  *     the delay slot OP defines one of the operands of the xfer_op, copy
00297  *     that value into a temp before the delay slot OP and rename the 
00298  *     operand in the xfer_op.
00299  *
00300  *   void BB_Delete_Successors(BB *bb)
00301  *     Delete all of the successor from 'bb's _succ list, leaving an
00302  *     initialized empty list of successors.
00303  *
00304  *   void BB_Delete_Predecessors(BB *bb)
00305  *     Delete all of the predecessor from 'bb's _pred list, leaving an
00306  *     initialized empty list of predecessors
00307  *
00308  *   void BB_Mark_Unreachable_Blocks (void)
00309  *     Set the BB_unreachable(bb) attribute for all basic blocks that
00310  *     are unreachable in the current region. If some unreachable blocks
00311  *     are added later, this routine must be invoked again.
00312  *
00313  *   BOOL BB_Add_Ancestors(BB_SET **set, BB *bb, BB *start_bb, MEM_POOL *pool)
00314  *     Requires: <*set> is allocated from <pool>
00315  *     Def'n: The control-flow ancestors of <bb> are <bb> itself and all
00316  *        BBs that precede <bb> on some path from an entry to <bb>.
00317  *     Find the control-flow ancestors of <bb> that aren't ancestors of
00318  *     BBs already in <*set> and add them to <*set>.  Returns TRUE if
00319  *     <start_bb> is visited.
00320  *
00321  *   LABEL_IDX Gen_Label_For_BB(BB *bb)
00322  *     Create a label for <bb>. If one already exists, don't create another.
00323  *
00324  *   BOOL Is_Label_For_BB(ST *label, BB *bb)
00325  *     Returns TRUE iff <label> is a label for <bb>.
00326  *
00327  *   BOOL BB_Has_Exc_Label(BB *bb)
00328  *     Returns TRUE iff <bb> has a label used to mark the beginning or
00329  *     end of an exception-handling region or exception handler.
00330  *
00331  *   BOOL BB_Has_Addr_Taken_Label(BB *bb)
00332  *     Returns TRUE if <bb> has a label whose address is taken, i.e. is
00333  *     flagged with LABEL_addr_saved().
00334  *
00335  *   BOOL BB_Has_Outer_Block_Label(BB *bb)
00336  *     Returns TRUE if <bb> has a label that is the target of a
00337  *     goto-outer-block, i.e. is flagged with LABEL_target_of_goto_outer_block()
00338  *
00339  *   BOOL Change_Switchtable_Entries(ST *tbl, BB *old_tgt, BB *new_tgt)
00340  *     Changes all references to <old_tgt> in switch table <tbl> to
00341  *     refer to <new_tgt> instead.  Returns TRUE iff any changes made.
00342  *
00343  *   BBKIND BB_kind(BB *bb)
00344  *     Return a BB's kind.
00345  *
00346  *   BOOL VALID_BBKIND(BBKIND k)
00347  *     Check a BBKIND for validity.
00348  *
00349  *   const char *BBKIND_Name(BBKIND k)
00350  *     Return a BBKIND as a string for printing.
00351  *
00352  *   void Print_LOOPINFO(LOOPINFO *info)
00353  *     Print out information associated with LOOPINFO annotations.
00354  *
00355  *   BB_MAP BB_Depth_First_Map(BB_SET *region, BB *entry)
00356  *     Requires: If (region != NULL), <entry> dominates all BBs in <region>
00357  *     and there exists a subset of <region> such that all control
00358  *     flow paths from <entry> to members of this subset include
00359  *     exactly the BBs in <region>
00360  *     Return a BB_MAP representing a depth-first partial ordering
00361  *     of the CFG for the BBs in <region> starting with <entry>.
00362  *     <map> will contain zero for BBs unreachable from <entry>.
00363  *     Otherwise, <map> will contain contiguous numbers starting with
00364  *     1 (for <entry>).  If <region> is NULL, the current region or PU
00365  *     is used.  If <entry> is NULL, the current region entry (or PU
00366  *     entries) is used.
00367  *
00368  *   BB_MAP BB_Topological_Map(BB_SET *region, BB *entry)
00369  *     Requires: If (region != NULL), <entry> dominates all BBs in <region>
00370  *     and there exists a subset of <region> such that all control
00371  *     flow paths from <entry> to members of this subset include
00372  *     exactly the BBs in <region>
00373  *     Return a BB_MAP representing a topological partial ordering
00374  *     of the CFG for the BBs in <region> starting with <entry>.
00375  *     <map> will contain zero for BBs whose predecessors can't be
00376  *     visited before the BB itself is visited.  Otherwise, <map> will
00377  *     contain contiguous numbers starting with 1 (for <entry>).  If
00378  *     <region> is NULL, the current region or PU is used.  If <entry>
00379  *     is NULL, the current region entry (or PU entries) is used.
00380  *
00381  *   SRCPOS BB_Loop_Srcpos(BB *bb);
00382  *   INT32 BB_Loop_Lineno(BB *bb);
00383  *     <bb> is the head of a loop; return the starting SRCPOS/line number
00384  *     for the loop if possible; return 0 otherwise.
00385  *
00386  *   void Change_Succ(BB *pred, BB *old_succ, BB *new_succ)
00387  *     Requires: <old_succ> in BB_succs(pred) && <pred> in BB_preds(old_succ)
00388  *     Change the pred/succ lists and frequency info (if present) to
00389  *     indicate that <pred> is now succeeded by <new_succ> instead of
00390  *     <old_succ>.
00391  *
00392  *   void Change_Succ_Prob(BB *pred, BB *succ, float prob)
00393  *     Requires: <succ> in BB_succs(pred) && <pred> in BB_preds(succ)
00394  *     Change the successor probability of the edge from <pred> to <succ>
00395  *     to <prob>, then update BB_freq(succ) accordingly.
00396  *
00397  *   void BB_Add_Annotation(BB *bb, ANNOTATION_KIND kind, void *info)
00398  *  Add an annotation of the given type 'kind' to the 'bb.
00399  *  'info' points to type-specific data for the annotation.
00400  *
00401  *   INT BB_Copy_Annotations(BB *to_bb, BB *from_bb, ANNOTATION_KIND kind)
00402  *  Copy the annotations of type 'kind' of 'from_bb' to 'to_bb'.
00403  *  NOTE: this only copies the pointer to the type-specific data
00404  *  (ANNOT_info); not its contents. The return value is the
00405  *  count of the annotations copied.
00406  *
00407  *   BOOL BB_Is_Cold(BB *bb)
00408  *  Return a boolean to indicate if a BB is part of a cold region
00409  *  or not.
00410  *
00411  *   ST *Gen_ST_For_BB(BB *bb)
00412  *  Generate a symbol (ST) to mark the start of the BB. Used in the
00413  *  rare cases when a label won't suffice (e.g. you need to generate
00414  *  code to take it's address).
00415  *
00416  *   ST *BB_st(BB *bb)
00417  *  Return the symbol associated with the start of the BB, returning
00418  *  NULL if there is none.
00419  *
00420  * TODO: Complete this interface description.
00421  *
00422  * ====================================================================
00423  * ====================================================================
00424  */
00425 
00426 
00427 #ifndef bb_INCLUDED
00428 #define bb_INCLUDED
00429 
00430 #include <vector>
00431 #include "mempool_allocator.h"  /* to get mempool allocator */
00432 
00433 #include "region_util.h"  /* to get the definition of RID. */
00434 #include "symtab.h"     /* to get ST */
00435 
00436 #include "srcpos.h"     /* to get the definition of SRCPOS. */
00437 #include "annotations.h"  /* to get definition of ANNOTATION. */
00438 #include "op.h"     /* to get definition of OPS */
00439 #include "bbregs.h"     /* to get the definition of BBREGS */
00440 
00441 /* Dummy definition to keep ANSI prototypes quiet: */
00442 struct tn;
00443 struct bblist;
00444 class  WN;
00445 
00446 /* ====================================================================
00447  *
00448  * The Basic Block (BB)
00449  *
00450  * ====================================================================
00451  */
00452 
00453 /* Define the BB number type: */
00454 typedef INT32 BB_NUM; /* Individual objects */
00455 typedef mINT32 mBB_NUM; /* Table components */
00456 #define BB_NUM_MAX  INT32_MAX
00457 
00458 typedef struct bb {
00459   struct bb *next;    /* next (sequential) bb     */
00460   struct bb   *prev;    /* previous (sequential) bb   */
00461   struct bblist *preds;   /* list of predecessor BBs    */
00462   struct bblist *succs;   /* list of successor BBs    */
00463   OPS   ops;    /* list of OPs        */
00464   mBB_NUM id;   /* trace identification number    */
00465 #if defined(TARG_IA64)
00466   UINT64  flags;          /* flags        */
00467 #else
00468   UINT32  flags;          /* flags        */
00469 #endif
00470   UINT16  nest_level; /* loop nesting level     */
00471   mUINT16 next_op_map_idx; /* next OP_map_idx to be assigned in BB  */
00472   mUINT16 unrollings; /* (cached) number of unrollings */
00473   float   freq;   /* profile or estimated frequency */
00474   struct bb    *loop_head_bb; /* BB of enclosing loop head (if known) */
00475   RID          *rid;            /* nearest enclosing region_id    */
00476   WN           *branch_wn;  /* terminating branch whirl node  */
00477   struct bbregs *bbregs;  /* auxiliary register info (bbregs.h) */
00478   struct annotation *annotations; /* annotations attached to bb   */
00479 #ifdef KEY
00480   struct bb     *aux;
00481 #endif 
00482 #if defined(TARG_IA64) || defined(TARG_SL) || defined(TARG_MIPS)
00483   INT   bb_cycle; 
00484 #if !defined(TARG_SL)
00485   mBB_NUM       id_before_profile;  /* old trace number before any profile process*/
00486 #endif
00487 #endif
00488 } BB;
00489 
00490 #ifndef CAN_USE_BB
00491 #define CAN_USE_BB(a) (a)
00492 #endif
00493 
00494 /* Define the field access macros: b is a *BB, y is an integer */
00495 
00496 #define BB_next(b)  (CAN_USE_BB(b)->next)
00497 #define BB_prev(x)   (CAN_USE_BB(x)->prev)
00498 #define BB_preds(x)  (CAN_USE_BB(x)->preds)
00499 #define BB_succs(x)  (CAN_USE_BB(x)->succs)
00500 #define BB_cycle(x)  (CAN_USE_BB(x)->bb_cycle)
00501 #if 0
00502 /* Don't define BB_ops! OPs must only be manipulated with the provided
00503  * utility routines in order to keep automatically maintained data structures
00504  * correct.
00505  */
00506 #define BB_ops(x)        (CAN_USE_BB(x)->ops)
00507 #endif
00508 #define BB_flag(b)  (CAN_USE_BB(b)->flags)
00509 #define BB_nest_level(b) (CAN_USE_BB(b)->nest_level)
00510 #define BB_rid(b) (CAN_USE_BB(b)->rid)
00511 #define BB_next_op_map_idx(b) (CAN_USE_BB(b)->next_op_map_idx)
00512 #define BB_freq(x)   (CAN_USE_BB(x)->freq)
00513 #define BB_branch_wn(x)  (CAN_USE_BB(x)->branch_wn)
00514 #define BB_bbregs(x)   (CAN_USE_BB(x)->bbregs)
00515 #define BB_annotations(x) (CAN_USE_BB(x)->annotations)
00516 
00517 /* rvalue field accessors */
00518 #define BB_id(b)  (CAN_USE_BB(b)->id+0)
00519 #if defined(TARG_IA64)
00520 #define BB_id_before_profile(b) (CAN_USE_BB(b)->id_before_profile+0)
00521 #endif
00522 #define BB_first_op(b)  (CAN_USE_BB(b)->ops.first+0)
00523 #define BB_last_op(b) (CAN_USE_BB(b)->ops.last+0)
00524 #define BB_unrollings(b) (CAN_USE_BB(b)->unrollings+0)
00525 #define BB_loop_head_bb(b) (CAN_USE_BB(b)->loop_head_bb+0)
00526 #define BB_loophead(bb) (BB_loop_head_bb(bb) == (bb))
00527 #ifdef KEY
00528 #define BB_aux(b)       (CAN_USE_BB(b)->aux)
00529 #endif
00530 /* mutators */
00531 inline void Set_BB_unrollings(BB *bb, UINT16 u) {
00532   bb->unrollings = u;
00533 }
00534 
00535 inline void Set_BB_loop_head_bb(BB *bb, BB *head) {
00536   bb->loop_head_bb = head;
00537 }
00538 
00539 #define BBM_ENTRY 0x0001 /* BB is subprogram entry point */
00540 #define BBM_HANDLER 0x0002 /* BB is handler entry point */
00541 #define BBM_EXIT  0x0004 /* BBKIND_RETURN, or call STOP (unmaintained) */
00542 #define BBM_CALL  0x0008 /* BB terminates with a call */
00543 #define BBM_LABEL 0x0010 /* BB has labels */
00544 #define BBM_PRAGMA  0x0020 /* BB has pragmas */
00545 #define BBM_NOTE  0x0040 /* BB has one or more notes. */
00546 #define BBM_UNREACHABLE 0x0080 /* BB is unreachable (valid only right after a 
00547                call to BB_Mark_Unreachable_Blocks) */
00548 #define BBM_UNROLLED_FULLY 0x0100 /* BB is fully unrolled */
00549 #define BBM_INNERMOST 0x0200 /* in an innermost loop */
00550 #define BBM_SCHEDULED 0x0400 /* BB has been scheduled by SWP/CFLOW/LOCS */
00551 #define BBM_REG_ALLOC   0x0800 /* BB has been register allocated by SWP/LRA */
00552 #define BBM_LOCAL_FLAG1 0x1000 /* local use flag */
00553 #define BBM_FREQ_FB 0x2000 /* BB_freq is based on feedback */
00554 #define BBM_GRA_SPILL 0x4000 /* BB used to aid GRA spill placement */
00555 #define BBM_SCHEDULED_HBS 0x8000 /* BB (or HB) has been scheduled by HBS */
00556 #define BBM_ROTATING_KERNEL 0x10000 /* BB uses rotating registers */
00557 #define BBM_MOD_ROTATING_REGISTERS 0x20000 /* BB modifies all rotating registers */
00558 #define BBM_MOD_PRED_ROTATING_REGISTERS 0x40000 /* BB modifies predicate rotating registers */
00559 #define BBM_ASM     0x00080000 /* BB has asm */
00560 #define BBM_PREDICATE_PROMOTE 0x00100000 /* Predicate promotion phase has been
00561               invoked for the BB. */
00562 #define BBM_POST_LABEL          0x00200000 /* BB has a post-label, i.e. a 
00563               label at the end of the BB, rather
00564               than at the beginning */
00565 #ifdef KEY
00566 #define BBM_NON_LOCAL_LABEL     0x00400000 /* BB has a non-local label */
00567 #endif
00568 
00569 #if defined(TARG_IA64) || defined(TARG_SL) || defined(TARG_MIPS)
00570 #define BBM_EDGE_SPLITTING      0x00800000 /* BB is used for edge splitting */
00571 
00572 #ifdef TARG_IA64
00573 #define BBM_RECOVERY            0x01000000 /* BB is a recovery block */
00574 #define BBM_CHK_SPLIT           0x02000000 /* BB splitted from another because of chk insertion */
00575 #define BBM_EMITTED             0x04000000 /* BB has been emitted */
00576 #define BBM_PROFILE_SPLITTED    0x08000000 /* BB is bb splitted from old bb by profile */
00577 #define BBM_PROFILE_CHANGED     0x10000000 /* BB is changed by profile*/
00578 #define BBM_PROFILE_ADDED       0x20000000 /* BB is new bb added by profile*/
00579 #define BBM_CHK_SPLIT_HEAD      0x40000000 /* BB splitted from another because of chk insertion */
00580 #define BBM_PARTIAL_BUNDLE      0x80000000 /* BB partial bundle for across boundary*/
00581 #define BBM_CHK_SPLIT_TAIL     0x200000000 /* BB is splited tail *///bug fix for OSP_212
00582 #elif defined(TARG_SL)
00583 #define BBM_ZDL_PROLOG          0x01000000 
00584 #define BBM_ZDL_BODY            0x02000000        
00585 #define BBM_HAS_TAG          0x04000000        
00586 #define BBM_SCHEDULED_SIZE      0x08000000          
00587 #define BBM_FREQ_UNBALANCED 0x10000000
00588 #endif // TARG_SL
00589 
00590 #define BB_edge_splitting(x)          (BB_flag(x) & BBM_EDGE_SPLITTING)
00591 #define Set_BB_edge_splitting(x)      (BB_flag(x) |= BBM_EDGE_SPLITTING)
00592 #define Reset_BB_edge_splitting(x)    (BB_flag(x) &= ~BBM_EDGE_SPLITTING)
00593 #endif // TARG_IA64 || TARG_SL
00594 
00595 
00596 #if defined (TARG_SL)
00597 /* BB is the prolog of  zero-delay-loop, so it  only contains 
00598  * add.i/mvtc/loop three instructios, LIS may add nops.
00599  */
00600 #define BB_zdl_prolog(x)        (BB_flag(x) & BBM_ZDL_PROLOG)
00601 #define Set_BB_zdl_prolog(x)    (BB_flag(x) |= BBM_ZDL_PROLOG)
00602 #define Reset_BB_zdl_prolog(x)  (BB_flag(x) &= ~BBM_ZDL_PROLOG)
00603 
00604 /* BB is the body of zero-delay-loop, so if it has branch inside,
00605  * it should be deleted ( i delay this to keep cfg not complain)
00606  */
00607 #define BB_zdl_body(x)          (BB_flag(x) & BBM_ZDL_BODY)
00608 #define Set_BB_zdl_body(x)      (BB_flag(x) |= BBM_ZDL_BODY)
00609 #define Reset_BB_zdl_body(x)    (BB_flag(x) &= ~BBM_ZDL_BODY)
00610 
00611 #define BB_has_tag(x)           (BB_flag(x) & BBM_HAS_TAG)
00612 #define Set_BB_has_tag(x)       (BB_flag(x) |= BBM_HAS_TAG)
00613 #define Reset_BB_has_tag(x)     (BB_flag(x) &=~ BBM_HAS_TAG)
00614 
00615 #define BB_SCHED_SIZE(x)        (BB_flag(x) & BBM_SCHEDULED_SIZE)
00616 #define Set_BB_sched_size(x)    (BB_flag(x) |= BBM_SCHEDULED_SIZE)
00617 #define Reset_BB_sched_size(x)  (BB_flag(x) &= ~BBM_SCHEDULED_SIZE)
00618 
00619 #define BB_freq_unbalanced(x)     (BB_flag(x) & BBM_FREQ_UNBALANCED)
00620 #define Set_BB_freq_unbalanced(x)   (BB_flag(x) |= BBM_FREQ_UNBALANCED)
00621 #define Reset_BB_freq_unbalanced(x)   (BB_flag(x) &= ~BBM_FREQ_UNBALANCED)
00622 #endif // TARG_SL
00623 
00624 #define BB_entry(x)   (BB_flag(x) & BBM_ENTRY)
00625 #define BB_handler(bb)    (BB_flag(bb) & BBM_HANDLER)
00626 #define BB_exit(x)    (BB_flag(x) & BBM_EXIT)
00627 #define BB_call(x)    (BB_flag(x) & BBM_CALL)
00628 #define BB_has_label(x)   (BB_flag(x) & BBM_LABEL)
00629 #define BB_has_pragma(x)  (BB_flag(x) & BBM_PRAGMA)
00630 #define BB_has_note(x)    (BB_flag(x) & BBM_NOTE)
00631 #define BB_unreachable(x) (BB_flag(x) & BBM_UNREACHABLE)
00632 #define BB_unrolled_fully(x)  (BB_flag(x) & BBM_UNROLLED_FULLY)
00633 #define BB_innermost(x)   (BB_flag(x) & BBM_INNERMOST)
00634 #define BB_scheduled(bb)  (BB_flag(bb) & BBM_SCHEDULED)
00635 #define BB_reg_alloc(bb)  (BB_flag(bb) & BBM_REG_ALLOC)
00636 #define BB_local_flag1(bb)  (BB_flag(bb) & BBM_LOCAL_FLAG1)
00637 #define BB_freq_fb_based(bb)  (BB_flag(bb) & BBM_FREQ_FB)
00638 #define BB_gra_spill(bb)  (BB_flag(bb) & BBM_GRA_SPILL)
00639 #define BB_scheduled_hbs(bb)  (BB_flag(bb) & BBM_SCHEDULED_HBS)
00640 #define BB_rotating_kernel(bb)  (BB_flag(bb) & BBM_ROTATING_KERNEL)
00641 #define BB_mod_rotating_registers(bb) (BB_flag(bb) & BBM_MOD_ROTATING_REGISTERS)
00642 #define BB_mod_pred_rotating_registers(bb) (BB_flag(bb) & BBM_MOD_PRED_ROTATING_REGISTERS)
00643 #define BB_asm(bb)    (BB_flag(bb) & BBM_ASM)
00644 #define BB_predicate_promote(bb) (BB_flag(bb) & BBM_PREDICATE_PROMOTE)
00645 #define BB_has_post_label(x)    (BB_flag(x) & BBM_POST_LABEL)
00646 #ifdef KEY
00647 #define BB_has_non_local_label(x) (BB_flag(x) & BBM_NON_LOCAL_LABEL)
00648 #endif
00649 #ifdef TARG_IA64
00650 #define BB_recovery(x)          (BB_flag(x) & BBM_RECOVERY)
00651 #define BB_chk_split(x)         (BB_flag(x) & BBM_CHK_SPLIT)
00652 #define BB_chk_split_head(x)    (BB_flag(x) & BBM_CHK_SPLIT_HEAD)
00653 #define BB_emitted(x)           (BB_flag(x) & BBM_EMITTED)
00654 #define BB_profile_splitted(x)    (BB_flag(x) & BBM_PROFILE_SPLITTED)
00655 #define BB_profile_changed(x)    (BB_flag(x) & BBM_PROFILE_CHANGED)
00656 #define BB_profile_added(x)    (BB_flag(x) & BBM_PROFILE_ADDED)
00657 #define BB_partial_bundle(x)  (BB_flag(x) & BBM_PARTIAL_BUNDLE)
00658 #define BB_chk_split_tail(x)    (BB_flag(x) & BBM_CHK_SPLIT_TAIL)//bug fix for OSP_212
00659 #endif
00660 
00661 #define Set_BB_entry(x)   (BB_flag(x) |= BBM_ENTRY)
00662 #define Set_BB_handler(bb)  (BB_flag(bb) |= BBM_HANDLER)
00663 #define Set_BB_exit(x)    (BB_flag(x) |= BBM_EXIT)
00664 #define Set_BB_call(x)    (BB_flag(x) |= BBM_CALL)
00665 #define Set_BB_has_label(x) (BB_flag(x) |= BBM_LABEL)
00666 #define Set_BB_has_pragma(x)  (BB_flag(x) |= BBM_PRAGMA)
00667 #define Set_BB_has_note(x)  (BB_flag(x) |= BBM_NOTE)
00668 #define Set_BB_unreachable(x) (BB_flag(x) |= BBM_UNREACHABLE)
00669 #define Set_BB_unrolled_fully(x)(BB_flag(x) |= BBM_UNROLLED_FULLY)
00670 #define Set_BB_innermost(x) (BB_flag(x) |= BBM_INNERMOST)
00671 #define Set_BB_scheduled(bb)  (BB_flag(bb) |= BBM_SCHEDULED)
00672 #define Set_BB_reg_alloc(bb)  (BB_flag(bb) |= BBM_REG_ALLOC)
00673 #define Set_BB_local_flag1(bb)  (BB_flag(bb) |= BBM_LOCAL_FLAG1)
00674 #define Set_BB_freq_fb_based(bb)(BB_flag(bb) |= BBM_FREQ_FB)
00675 #define Set_BB_gra_spill(bb)  (BB_flag(bb) |= BBM_GRA_SPILL)
00676 #define Set_BB_scheduled_hbs(bb)(BB_flag(bb) |= BBM_SCHEDULED_HBS)
00677 #define Set_BB_rotating_kernel(bb) (BB_flag(bb) |= BBM_ROTATING_KERNEL)
00678 #define Set_BB_mod_rotating_registers(bb) (BB_flag(bb) |= BBM_MOD_ROTATING_REGISTERS)
00679 #define Set_BB_mod_pred_rotating_registers(bb) (BB_flag(bb) |= BBM_MOD_PRED_ROTATING_REGISTERS)
00680 #define Set_BB_asm(bb)    (BB_flag(bb) |= BBM_ASM)
00681 #define Set_BB_predicate_promote(bb)  (BB_flag(bb) |= BBM_PREDICATE_PROMOTE)
00682 #define Set_BB_has_post_label(x)  (BB_flag(x) |= BBM_POST_LABEL)
00683 #ifdef KEY
00684 #define Set_BB_has_non_local_label(x) (BB_flag(x) |= BBM_NON_LOCAL_LABEL)
00685 #endif
00686 
00687 #ifdef TARG_IA64
00688 #define Set_BB_recovery(x)          (BB_flag(x) |= BBM_RECOVERY)
00689 #define Set_BB_chk_split(x)         (BB_flag(x) |= BBM_CHK_SPLIT)
00690 #define Set_BB_chk_split_head(x)    (BB_flag(x) |= BBM_CHK_SPLIT_HEAD)
00691 #define Set_BB_emitted(x)           (BB_flag(x) |= BBM_EMITTED)
00692 #define Set_BB_profile_splitted(x)    (BB_flag(x) |= BBM_PROFILE_SPLITTED)
00693 #define Set_BB_profile_changed(x)    (BB_flag(x) |= BBM_PROFILE_CHANGED)
00694 #define Set_BB_profile_added(x)    (BB_flag(x) |= BBM_PROFILE_ADDED)
00695 #define Set_BB_partial_bundle(x)    (BB_flag(x) |= BBM_PARTIAL_BUNDLE)
00696 #define Set_BB_chk_split_tail(x)    (BB_flag(x) |= BBM_CHK_SPLIT_TAIL)//bug fix for OSP_212
00697 #endif
00698 #define Reset_BB_entry(x) (BB_flag(x) &= ~BBM_ENTRY)
00699 #define Reset_BB_handler(bb)  (BB_flag(bb) &= ~BBM_HANDLER)
00700 #define Reset_BB_exit(x)  (BB_flag(x) &= ~BBM_EXIT)
00701 #define Reset_BB_call(x)  (BB_flag(x) &= ~BBM_CALL)
00702 #define Reset_BB_has_label(x) (BB_flag(x) &= ~BBM_LABEL)
00703 #define Reset_BB_has_pragma(x)  (BB_flag(x) &= ~BBM_PRAGMA)
00704 #define Reset_BB_has_note(x)  (BB_flag(x) &= ~BBM_NOTE)
00705 #define Reset_BB_unreachable(x) (BB_flag(x) &=  ~BBM_UNREACHABLE)
00706 #define Reset_BB_unrolled_fully(x) (BB_flag(x) &= ~BBM_UNROLLED_FULLY)
00707 #define Reset_BB_innermost(x) (BB_flag(x) &= ~BBM_INNERMOST)
00708 #define Reset_BB_scheduled(bb)  (BB_flag(bb) &= ~BBM_SCHEDULED)
00709 #define Reset_BB_reg_alloc(bb)  (BB_flag(bb) &= ~BBM_REG_ALLOC)
00710 #define Reset_BB_local_flag1(bb) (BB_flag(bb) &= ~BBM_LOCAL_FLAG1)
00711 #define Reset_BB_freq_fb_based(bb) (BB_flag(bb) &= ~BBM_FREQ_FB)
00712 #define Reset_BB_gra_spill(bb)  (BB_flag(bb) &= ~BBM_GRA_SPILL)
00713 #define Reset_BB_scheduled_hbs(bb) (BB_flag(bb) &= ~BBM_SCHEDULED_HBS)
00714 #define Reset_BB_rotating_kernel(bb) (BB_flag(bb) &= ~BBM_ROTATING_KERNEL)
00715 #define Reset_BB_mod_rotating_registers(bb) (BB_flag(bb) &= ~BBM_MOD_ROTATING_REGISTERS)
00716 #define Reset_BB_mod_pred_rotating_registers(bb) (BB_flag(bb) &= ~BBM_MOD_PRED_ROTATING_REGISTERS)
00717 #define Reset_BB_asm(bb)  (BB_flag(bb) &= ~BBM_ASM)
00718 #define Reset_BB_predicate_promote(bb)  (BB_flag(bb) &= ~BBM_PREDICATE_PROMOTE)
00719 #define Reset_BB_has_post_label(x)  (BB_flag(x) &= ~BBM_POST_LABEL)
00720 
00721 #ifdef TARG_IA64
00722 #define Reset_BB_recovery(x)          (BB_flag(x) &= ~BBM_RECOVERY)
00723 #define Reset_BB_chk_split(x)         (BB_flag(x) &= ~BBM_CHK_SPLIT)
00724 #define Reset_BB_chk_split_head(x)    (BB_flag(x) &= ~BBM_CHK_SPLIT_HEAD)
00725 #define Reset_BB_emitted(x)           (BB_flag(x) &= ~BBM_EMITTED)
00726 #define Reset_BB_profile_splitted(x)    (BB_flag(x) &= ~BBM_PROFILE_SPLITTED)
00727 #define Reset_BB_profile_changed(x)    (BB_flag(x) &= ~BBM_PROFILE_CHANGED)
00728 #define Resset_BB_profile_added(x)    (BB_flag(x) &= ~BBM_PROFILE_ADDED)
00729 #define Reset_BB_partial_bundle(x)    (BB_flag(x) &= ~BBM_PARTIAL_BUNDLE)
00730 #define Reset_BB_chk_split_tail(x)    (BB_flag(x) &= ~BBM_CHK_SPLIT_TAIL)//bug fix for OSP_212
00731 #endif
00732 #ifdef KEY
00733 #define Reset_BB_has_non_local_label(x) (BB_flag(x) &= ~BBM_NON_LOCAL_LABEL)
00734 #endif
00735 #define BB_tail_call(bb)  (   (BB_flag(bb) & (BBM_CALL | BBM_EXIT)) \
00736          == (BBM_CALL | BBM_EXIT))
00737 
00738 /* ====================================================================
00739  *
00740  * BBKIND -- Basic Block kinds.
00741  *
00742  * ====================================================================
00743  */
00744 
00745 /* WARNING: the order of this type must match array in bbutil.c. */
00746 typedef enum {
00747   BBKIND_UNKNOWN, /* Unknown BB kind */
00748   BBKIND_GOTO,    /* GOTO block -- single target BB */
00749   BBKIND_LOGIF,   /* Logical IF -- two target BBs */
00750   BBKIND_VARGOTO, /* Variable GOTO -- targets explicit, i.e. switch */
00751   BBKIND_INDGOTO, /* Indirect GOTO -- targets NOT explicit */
00752   BBKIND_RETURN,  /* Return from subprogram */
00753   BBKIND_CALL,    /* Function call */
00754   BBKIND_REGION_EXIT, /* Region exit */
00755   BBKIND_TAIL_CALL, /* Tail call */
00756 #ifdef TARG_IA64
00757   BBKIND_CHK,       /* end with check */
00758 #endif
00759 #if defined(TARG_SL)
00760   BBKIND_ZDL_BODY, 
00761   BBKIND_FORK,
00762 #endif
00763   BBKIND_LAST   /* > last legal value */
00764 } BBKIND;
00765 
00766 #define VALID_BBKIND(k) (k>=BBKIND_UNKNOWN && k<BBKIND_LAST)
00767 
00768 extern const char *BBKIND_Name (BBKIND k);
00769 extern BBKIND BB_kind (BB *bb);
00770 
00771 /* ====================================================================
00772  *
00773  * Basic Block lists.
00774  *
00775  * For a generic list of basic blocks, BB_LIST should be used. 
00776  *
00777  * The successor and predecessor basic block lists need an additional
00778  * attribute, the probability of the edge. For these lists, BBLIST is 
00779  * used. It should not be used for any other purpose.
00780  *
00781  * NOTE: Currently the predecessor edge probability is not calculated 
00782  * and is set to NaN.
00783  *
00784  * ====================================================================
00785  */
00786 
00787 /* to get definition of BB_LIST */
00788 #include "bb_list.h"
00789 
00790 typedef struct bblist {
00791     BB      *item;  /* The BB list element       */
00792     struct bblist *next;  /* The next list component   */
00793     float    prob;  /* probability for this edge */
00794 #if defined(TARG_IA64) || defined(TARG_SL) || defined(TARG_MIPS)
00795     float    freq;  /* frequency for this edge */    
00796 #endif
00797     mUINT16        flags;       /* flags                     */
00798 } BBLIST;
00799 
00800 #define BBLIST_item(b)  ((b)->item)
00801 #define BBLIST_next(b)  ((b)->next)
00802 #define BBLIST_prob(b)  ((b)->prob) /*** Only valid for succ edges ***/
00803 #define BBLIST_flags(b) ((b)->flags)
00804 #if defined(TARG_IA64) || defined(TARG_SL) || defined(TARG_MIPS)
00805 #define BBLIST_freq(b)  ((b)->freq) /*** Only valid for succ edges ***/
00806 #endif
00807 
00808 #define BLM_PROB_FB     0x0001 /* bblist::prob based on Feedback. */
00809 #define BLM_ON_TREE     0x0002 /* bblist::edge on the spanning tree */
00810 #define BLM_PROB_HINT   0x0004 /* bblist::prob based on user hint. */
00811 
00812 #define BBLIST_prob_hint_based(b)       (BBLIST_flags(b) & BLM_PROB_HINT)
00813 #define Set_BBLIST_prob_hint_based(b)   (BBLIST_flags(b) |= BLM_PROB_HINT)
00814 #define Reset_BBLIST_prob_hint_based(b) (BBLIST_flags(b) &= ~BLM_PROB_HINT)
00815 
00816 #define BBLIST_prob_fb_based(b)       (BBLIST_flags(b) & BLM_PROB_FB)
00817 #define Set_BBLIST_prob_fb_based(b)   (BBLIST_flags(b) |= BLM_PROB_FB)
00818 #define Reset_BBLIST_prob_fb_based(b) (BBLIST_flags(b) &= ~BLM_PROB_FB)
00819 
00820 #define BBLIST_on_tree(b)       (BBLIST_flags(b) & BLM_ON_TREE)
00821 #define Set_BBLIST_on_tree(b)   (BBLIST_flags(b) |= BLM_ON_TREE)
00822 #define Reset_BBLIST_on_tree(b) (BBLIST_flags(b) &= ~BLM_ON_TREE)
00823 
00824 /* Macros for stepping through BBlists. */
00825 #define FOR_ALL_BBLIST_ITEMS(list,item) \
00826   for (item = list; item != NULL; item = BBLIST_next(item))
00827 
00828 /* Macros for stepping through BB STL lists. */
00829 #define FOR_ALL_BB_STLLIST_ITEMS_FWD(list,item) \
00830         for (item = list.begin(); item != list.end(); item++)
00831 
00832 /* Macros for stepping through BB STL lists. */
00833 #define FOR_ALL_BB_STLLIST_ITEMS_BKWD(list,item) \
00834         for (item = list.rbegin(); item != list.rend(); item++)
00835 
00836 #define FOR_ALL_BB_SUCCS(bb,succ) FOR_ALL_BBLIST_ITEMS(BB_succs(bb),succ)
00837 #define FOR_ALL_BB_PREDS(bb,pred) FOR_ALL_BBLIST_ITEMS(BB_preds(bb),pred)
00838 #define BB_First_Succ(bb) \
00839     ((BB_succs(bb) != NULL) ? BBLIST_item(BB_succs(bb)) : NULL)
00840 #define BB_First_Pred(bb) \
00841     ((BB_preds(bb) != NULL) ? BBLIST_item(BB_preds(bb)) : NULL)
00842 
00843 extern void BBlist_Free (BBLIST **lst);
00844 extern INT  BBlist_Len (BBLIST *lst);
00845 extern BBLIST *BBlist_Find_BB(BBLIST *lst, BB *bb);
00846 extern BBLIST* BBlist_Fall_Thru_Succ(BB *bb);
00847 extern BBLIST* BBlist_Fall_Thru_Pred(BB *bb);
00848 
00849 inline BBLIST *BB_Find_Succ(BB *bb, BB *succ)
00850 {
00851   return BBlist_Find_BB(BB_succs(bb), succ);
00852 }
00853 
00854 inline BBLIST *BB_Find_Pred(BB *bb, BB *pred)
00855 {
00856   return BBlist_Find_BB(BB_preds(bb), pred);
00857 }
00858 
00859 inline BOOL BB_in_succs(BB *bb, BB *b)
00860 {
00861   return BBlist_Find_BB(BB_succs(bb), b) != NULL;
00862 }
00863 
00864 inline BOOL BB_in_preds(BB *bb, BB *b)
00865 {
00866   return BBlist_Find_BB(BB_preds(bb), b) != NULL;
00867 }
00868 
00869 inline INT32 BB_succs_len(BB *bb)
00870 {
00871   return BBlist_Len(BB_succs(bb));
00872 }
00873 
00874 inline INT32 BB_preds_len(BB *bb)
00875 {
00876   return BBlist_Len(BB_preds(bb));
00877 }
00878 
00879 inline BOOL BBlist_Has_One_Element(BBLIST *bblist)
00880 {
00881   return bblist && BBLIST_next(bblist) == NULL;
00882 }
00883 
00884 inline BOOL BB_Has_One_Succ(BB *bb)
00885 {
00886   return BBlist_Has_One_Element(BB_succs(bb));
00887 }
00888 
00889 inline BOOL BB_Has_One_Pred(BB *bb)
00890 {
00891   return BBlist_Has_One_Element(BB_preds(bb));
00892 }
00893 
00894 /* ====================================================================
00895  *
00896  * Global variables.
00897  *
00898  * ====================================================================
00899  */
00900 
00901 /* The following global variables describe BBs for the current PU: */
00902 
00903 extern BB *REGION_First_BB; /* First BB in current REGION (or PU) */
00904         /* Note that each region has own list of BB's,
00905          * and these lists are merged when a nested
00906          * region is processed; so may not see all
00907          * BB's until come to PU level. */
00908 extern BB_NUM PU_BB_Count;       /* Number of BBs in the current
00909               * PU, indexed 1..PU_BB_Count in
00910               * BB_idx.
00911               */
00912 
00913 extern BB_LIST *Entry_BB_Head;    /* chain of entry point BBs  */
00914 extern BB_LIST *Exit_BB_Head;   /* chain of exit BBs */
00915 
00916 extern BB **BB_Vec;   /* mapping from bb idx to BB in each PU */
00917 #define BBvec(i) BB_Vec[i] 
00918 
00919 /* to get the definition of BB_MAP, must come after the definition of BB */
00920 #include "bb_map.h"
00921 
00922 #include "bb_set.h"  /* to get BB_SET, must come after definition of BB_vec */
00923 
00924 
00925 /* ====================================================================
00926  *
00927  *  BB_REGION represents a region of BBs in the CFG, analogous to
00928  *  other BB data structure such as BBLIST and BB_SET.
00929  *
00930  *  Any region of the CFG can be uniquely identified by
00931  *   1) a set of entry blocks and;
00932  *   2) a set of exit blocks.
00933  *
00934  *  The region is defined to contain all basic blocks in any path 
00935  *  starting from an entry block, and not containing any exit block.
00936  *
00937  *  The has_omega field specifies whether the OPs in the region has
00938  *  CG_LOOP_INFO.  Currently either all OPs in the region have omega
00939  *  or none of them have omega.
00940  *
00941  *  INVARIANTS (or properties of a valid region):
00942  *    entries must contain at least one basic block.
00943  *    exits might bbe empty, e.g. the REGION represents an infinite loop.
00944  *    exit blocks are not considered part of the REGION.
00945  *    no basic block can be in both entries and exits of the same region.
00946  *    a basic block can be appear more than once in entries or in exits.
00947  *    If has_omega is TRUE, all OPs in the region must have CG_LOOP_INFO.
00948  *
00949  *  template <class Container>
00950  *  void BB_REGION_to_Container(Container& c, const BB_REGION& r)
00951  *    Convert a BB_REGION representation into a Container.
00952  *
00953  *  BB_SET *BB_REGION_to_BB_SET(BB_SET *bbs, const BB_REGION& r, MEM_POOL *pool);
00954  *    Convert a BB_REGION representation into a BB_SET representation.
00955  *    The usage convention follows BB_SET_UnionD() where the pool is the
00956  *    MEM_POOL of bbs.
00957  *
00958  * ====================================================================
00959  */
00960 
00961 struct BB_REGION {
00962   typedef mempool_allocator<BB*> allocator_type;
00963   typedef vector<BB*, allocator_type> bb_vector;
00964   allocator_type data_allocator;
00965   bb_vector entries;   
00966   bb_vector exits;  
00967   bool      has_omega;
00968 
00969   // Assert if any the invariants becomes false.
00970   void Verify() const; 
00971 
00972   bool Has_omega() const { return has_omega; }
00973   void Set_has_omega() { has_omega = true; }
00974   
00975   //  Construct an empty BB_REGION.
00976   //
00977   BB_REGION(MEM_POOL *pool)
00978     :data_allocator(pool),
00979      entries(0, (BB*)NULL, data_allocator),
00980      exits(0, (BB*)NULL, data_allocator),
00981      has_omega(false)
00982   {}
00983   
00984   //  Construct a BB_REGION from a BB_SET.
00985   //
00986   BB_REGION(BB_SET *bbs, MEM_POOL *pool);
00987   void Print(void) const;
00988 };
00989 
00990 extern BB_SET *BB_REGION_to_BB_SET(BB_SET *bbs, const BB_REGION& r,
00991            MEM_POOL *pool);
00992 extern void BB_REGION_to_Vector (vector<BB*>& c, const BB_REGION& r);
00993 
00994 /* =======================================================================
00995  *
00996  *  BB_VISITED_COUNTER
00997  *    Use a version counter to keep track of visited BBs, so that the
00998  *    same data structure can be used several times without the need
00999  *    of resetting every element.
01000  *
01001  *    A BB is visited if its counter equals the current version counter.
01002  *   
01003  *
01004  *    BB_VISITED_COUNTER(MEM_POOL *m)
01005  *      -- constructor
01006  *
01007  *    Visited(BB *bb)
01008  *      -- returns TRUE if BB is visited
01009  *
01010  *    Set_visited(BB *bb)
01011  *      -- mark BB visited
01012  *
01013  *    Init()
01014  *      -- initialization before use
01015  *
01016  *  This struct can be generalized using templates
01017  *  for any index-able data structure.
01018  * 
01019  * =======================================================================
01020  */
01021 class BB_VISITED_COUNTER {
01022   MEM_POOL *pool;
01023   INT  current_version;
01024   INT  size;
01025   INT  *counter;
01026 
01027 public:
01028   //  Set BB visited
01029   void Set_visited(BB *bb) const { counter[BB_id(bb)] = current_version; }
01030 
01031   //  Test if BB has been visited
01032   BOOL Visited(BB *bb) const { return counter[BB_id(bb)] == current_version; }
01033   
01034   //  Initialize:  
01035   //   by incrementing the version counter, all BB visited are reset
01036   //
01037   void Init() {
01038     INT required_size = PU_BB_Count + 2;      // use the magic +2
01039     if (required_size > size) {
01040 #pragma mips_frequency_hint NEVER
01041       if (size == 0) 
01042   counter = (INT *) MEM_POOL_Alloc(pool, required_size * sizeof(INT));
01043       else
01044   counter = (INT *) MEM_POOL_Realloc(pool, counter, size * sizeof(INT), required_size * sizeof(INT));
01045       for (INT i = size; i < required_size; i++)
01046   counter[i] = 0;
01047       size = required_size;
01048     }
01049     if (++current_version == 0) {  // overflowed ==> reset all counters
01050 #pragma mips_frequency_hint NEVER
01051       for (INT i = 0; i < size; i++)
01052   counter[i] = 0;
01053     }
01054   }
01055 
01056   BB_VISITED_COUNTER(MEM_POOL *m)
01057     :current_version(0),counter(NULL), size(0), pool(m) 
01058   {}
01059 };
01060 
01061 
01062 
01063 /* ====================================================================
01064  *
01065  * BB manipulation routines (implemented in bbutil.c).
01066  *
01067  * ====================================================================
01068  */
01069 
01070 /* =====  Creation and Initialization  ====== */
01071 
01072 /* Described in comment at top */
01073 extern BB *Gen_BB(void);
01074 extern BB *Gen_BB_N(INT n);
01075 extern BB *Gen_BB_Like (BB *model);
01076 extern BB *Gen_And_Append_BB(BB *prev_bb);
01077 extern BB *Gen_And_Insert_BB_Before(BB *point);
01078 extern BB *Gen_And_Insert_BB_After(BB *point);
01079 extern void Chain_BBs(BB* bb1, BB* bb2);
01080 extern void Target_Simple_Fall_Through_BB(BB* bb, BB* target_bb);
01081 extern void Target_Logif_BB(BB* bb, BB* br_targ_bb, float br_targ_prob,
01082             BB* fall_through);
01083 extern void Target_Cond_Branch(BB* bb, BB* br_targ_bb, float br_targ_prob);
01084 extern void Negate_Logif_BB(BB *bb);
01085 extern void Add_Goto_Op(BB *bb, BB *target_bb);
01086 extern void Add_Goto(BB *bb, BB *target_bb);
01087 extern BB* Create_Dummy_BB( BB *dest_bb );
01088 extern LABEL_IDX Gen_Label_For_BB (BB *bb);
01089 extern BOOL Is_Label_For_BB(LABEL_IDX label, BB *bb);
01090 extern BOOL Change_Switchtable_Entries(ST *tbl, BB *old_tgt, BB *new_tgt);
01091 extern void Change_Succ(BB *pred, BB *old_succ, BB *new_succ);
01092 extern void Change_Succ_Prob(BB *pred, BB *succ, float prob);
01093 
01094 /* Add/copy an annotation to a BB */
01095 extern void BB_Add_Annotation(BB *bb, ANNOTATION_KIND kind, void *info);
01096 extern INT BB_Copy_Annotations(BB *to_bb, BB *from_bb, ANNOTATION_KIND kind);
01097 extern INT BB_Copy_All_Annotations(BB *to_bb, BB *from_bb);
01098 
01099 /* Free the memory associated with the live BBs and clear pointers: */
01100 extern  void  Free_BB_Memory ( void );
01101 
01102 /* =====  Predecessor/Successor Handling  ====== */
01103 
01104 /* Link up the pred and succ basic blocks. */
01105 extern void Link_Pred_Succ (BB *pred, BB *succ);
01106 #if defined (KEY)
01107 extern void Link_Pred_Succ_with_Prob(BB *pred, BB *succ, float prob, 
01108              BOOL via_feedback = FALSE,
01109              BOOL set_prob = FALSE,
01110              BOOL via_hint =FALSE, 
01111              BOOL incr_prob=TRUE);
01112 #else
01113 extern void Link_Pred_Succ_with_Prob(BB *pred, BB *succ, float prob, 
01114              BOOL via_feedback = FALSE,
01115              BOOL set_prob = FALSE);
01116 #endif
01117 extern BBLIST *BBlist_Add_BB(BBLIST **lst, BB *bb);
01118 extern void BBlist_Delete_BB(BBLIST **lst, BB *bb);
01119 #if defined(KEY)
01120 extern BBLIST *BBlist_Add_BB_with_Prob(BBLIST **lst, BB *bb, float prob,
01121                BOOL via_feedback = FALSE,
01122                BOOL set_prob     = FALSE,
01123                BOOL via_hint = FALSE,
01124                BOOL incr_prob = TRUE);
01125 
01126 #else
01127 extern BBLIST *BBlist_Add_BB_with_Prob(BBLIST **lst, BB *bb, float prob,
01128                BOOL via_feedback = FALSE,
01129                BOOL set_prob     = FALSE,
01130                BOOL incr_prob = TRUE);
01131 #endif
01132 
01133 /* Unlink the pred and succ basic blocks. */
01134 extern void Unlink_Pred_Succ (BB *pred, BB *succ);
01135 
01136 
01137 /*  If bb has a unique successor not included in the set described by */
01138 /*  the BB_MAP32 map, return it.  Otherwise return NULL. */
01139 extern BB *BB_Unique_Successor_Not_In_Set( BB *bb, BB_MAP map );
01140 
01141 /*
01142  *  If bb has a unique successor/predecessor, return it.  
01143  *  Otherwise return NULL. 
01144  */
01145 extern BB *BB_Unique_Successor( BB *bb );
01146 extern BB *BB_Unique_Predecessor( BB *bb );
01147 extern BB *BB_Unique_Source( BB *bb );
01148 extern void Remove_Explicit_Branch (BB *bb);
01149 extern BB *BB_Fall_Thru_Successor( BB *bb );
01150 extern BB *BB_Fall_Thru_Predecessor( BB *bb );
01151 extern BOOL BB_Retarget_Branch(BB *bb, BB *from, BB *to);
01152 extern BOOL BB_Can_Retarget_Branch(BB *bb, BB *from);
01153 
01154 extern BB *BB_Other_Successor(BB *bb, BB *succ);
01155 extern BB *BB_Other_Predecessor(BB *bb, BB *pred);
01156 
01157 inline BOOL BB_Is_Unique_Successor( BB *bb, BB *succ )
01158 {
01159   return BB_Unique_Successor(bb) == succ;
01160 }
01161 
01162 inline BOOL BB_Is_Unique_Predecessor( BB *bb, BB *pred)
01163 {
01164   return BB_Unique_Predecessor(bb) == pred;
01165 }
01166 
01167 #define BB_Delete_Successors(bb) BBlist_Free(&BB_succs(bb))
01168 #define BB_Delete_Predecessors(bb) BBlist_Free(&BB_preds(bb))
01169 
01170 
01171 /* =====  Miscellaneous  ====== */
01172 
01173 /* Initialize for a new PU */
01174 extern void BB_PU_Initialize(void);
01175 /* Initialize for a new REGION */
01176 extern void BB_REGION_Initialize(void);
01177 
01178 /* Return the op for the terminating branch of a given BB */
01179 extern struct op *BB_branch_op (BB *);
01180 
01181 #ifdef TARG_IA64
01182 /* Return the last non nop op of a branch bb */
01183 extern OP* Last_Non_Nop_op (BB *); 
01184 extern OP* BB_Last_chk_op(BB *);
01185 #endif 
01186 
01187 /* Return the terminating xfer OP in a given BB */
01188 extern struct op* BB_xfer_op( BB *bb );
01189 
01190 /* Return the last OP which isn't a copy/xfer OP in a given BB */
01191 extern struct op* BB_copy_xfer_op( BB *bb );
01192 
01193 /* Return the call op in a given BB */
01194 extern struct op* BB_call_op(BB* bb);
01195 
01196 /* Return the op that that does the entry/exit SP adjustment in BB */
01197 extern struct op *BB_entry_sp_adj_op (BB *bb);
01198 extern struct op *BB_exit_sp_adj_op (BB *bb);
01199 
01200 /* Set the op that does the entry/exit SP adjustment in BB */
01201 extern void Set_BB_entry_sp_adj_op (BB *bb, struct op *);
01202 extern void Set_BB_exit_sp_adj_op (BB *bb, struct op *);
01203 
01204 /* Remove a BB from the list: */
01205 extern void  Remove_BB (BB *);
01206 
01207 /* Insert a BB into the list after a given BB (NULL for beginning): */
01208 extern void  Insert_BB ( BB *bb, BB *after );
01209 
01210 /* Move a BB from its current position to be after a given BB
01211  * (NULL for beginning):
01212  */
01213 extern void  Move_BB ( BB *bb, BB *after );
01214 
01215 /* Append the BBs from a previously compiled REGION to the
01216  * list of BBs for the current REGION.
01217  */
01218 extern BB *Append_Region_BBs( BB *prev, RID *rid );
01219 
01220 /* set BB_unreachable(bb) flag for all unreachable bbs in current region */
01221 extern void BB_Mark_Unreachable_Blocks (void);
01222 
01223 /* transfer annotations for entry/exit blocks for PU */
01224 extern void BB_Transfer_Exitinfo(BB* from, BB* to);
01225 extern void BB_Transfer_Entryinfo(BB* from, BB* to);
01226 extern void BB_Transfer_Callinfo(BB* from, BB* to);
01227 extern void BB_Transfer_Asminfo (BB *from, BB *to);
01228 
01229 /* Print the given BB or BBLIST: */
01230 extern void Print_BB_Header ( BB *bp,
01231             BOOL flow_info_only, BOOL print_tn_info );
01232 #pragma mips_frequency_hint NEVER Print_BB_Header
01233 extern void Trace_BB ( BB *bp, char *msg );
01234 #pragma mips_frequency_hint NEVER Trace_BB
01235 extern void Print_BB ( BB *bp );
01236 #pragma mips_frequency_hint NEVER Print_BB
01237 extern void Print_BB_No_Srclines ( BB *bp );
01238 #pragma mips_frequency_hint NEVER Print_BB_No_Srclines
01239 extern void Print_BB_Pragmas( BB *bp );
01240 #pragma mips_frequency_hint NEVER Print_BB_Pragmas
01241 extern void Print_All_BBs ( void );
01242 #pragma mips_frequency_hint NEVER Print_All_BBs
01243 extern void Print_All_BB_Headers ( void );
01244 #pragma mips_frequency_hint NEVER Print_All_BB_Headers
01245 extern void Print_Entry_Chain ( char *banner );
01246 #pragma mips_frequency_hint NEVER Print_Entry_Chain
01247 extern void Print_Flow_Graph  ( char *banner, BOOL verbose );
01248 #pragma mips_frequency_hint NEVER Print_Flow_Graph
01249 extern void Print_LOOPINFO( LOOPINFO *info );
01250 #pragma mips_frequency_hint NEVER Print_LOOPINFO
01251 
01252 #define BB_length(bb) OPS_length(&(bb)->ops)
01253 
01254 
01255 UINT16 BB_New_Op_Map_Idx(BB *bb);
01256 
01257 void BB_Insert_Op_Before(BB *bb, OP *point, OP *op);
01258 void BB_Insert_Op_After(BB *bb, OP *point, OP *op);
01259 void BB_Append_Op(BB *bb, OP *op);
01260 void BB_Prepend_Op(BB *bb, OP *op);
01261 void BB_Insert_Ops_Before(BB *bb, OP *point, OPS *ops);
01262 void BB_Insert_Ops_After(BB *bb, OP *point, OPS *ops);
01263 void BB_Append_Ops(BB *bb, OPS *ops);
01264 void BB_Prepend_Ops(BB *bb, OPS *ops);
01265 void BB_Insert_Op(BB *bb, OP *point, OP *op, BOOL before);
01266 void BB_Insert_Ops(BB *bb, OP *point, OPS *ops, BOOL before);
01267 
01268 void BB_Insert_Noops(OP *op, INT num, BOOL before);
01269 
01270 void BB_Move_Op(BB *to_bb, OP *point, BB *from_bb, OP *op, BOOL before);
01271 void BB_Move_Op_Before(BB *to_bb, OP *point, BB *from_bb, OP *op);
01272 void BB_Move_Op_After(BB *to_bb, OP *point, BB *from_bb, OP *op);
01273 void BB_Move_Op_To_Start(BB *to_bb, BB *from_bb, OP *op);
01274 void BB_Move_Op_To_End(BB *to_bb, BB *from_bb, OP *op);
01275 
01276 void BB_Sink_Op_Before(BB *bb, OP *op, OP *point);
01277 void BB_Update_OP_Order(BB *bb);
01278 void BB_Verify_OP_Order(BB *bb);
01279 
01280 BOOL BB_Move_Delay_Slot_Op (BB *bb);
01281 
01282 void BB_Append_All(BB *to_bb, BB *from_bb);
01283 void BB_Prepend_All(BB *to_bb, BB *from_bb);
01284 
01285 OP *BB_Remove_Branch(BB *bb);
01286 void BB_Remove_Ops(BB *bb, OPS *ops);
01287 void BB_Remove_Op(BB *bb, OP *op);
01288 void BB_Remove_All(BB *bb);
01289 
01290 extern SRCPOS BB_Loop_Srcpos(BB *bb);
01291 inline INT32 BB_Loop_Lineno(BB *bb)
01292 {
01293   return Srcpos_To_Line(BB_Loop_Srcpos(bb));
01294 }
01295 
01296 BOOL BB_Add_Ancestors(struct bs **set, BB *bb, BB *start_bb, MEM_POOL *pool);
01297 
01298 BOOL BB_Has_Exc_Label(BB *bb);
01299 BOOL BB_Has_Addr_Taken_Label(BB *bb);
01300 BOOL BB_Has_Outer_Block_Label(BB *bb);
01301 
01302 struct bb_map *BB_Depth_First_Map(struct bs *region, BB *entry);
01303 struct bb_map *BB_Topological_Map(struct bs *region, BB *entry);
01304 
01305 BOOL BB_Is_Cold(BB *bb);
01306 #if defined(TARG_SL)
01307 BOOL BB_Is_Hot(BB* bb);
01308 #endif
01309 ST *Gen_ST_For_BB(BB *bb);
01310 ST *BB_st(BB *bb);
01311 
01312 void Split_BBs();
01313 
01314 extern BB_SET* Find_BB_Parents(BB* bb);
01315 
01316 #ifdef Is_True_On
01317 extern void Verify_BB(BB *);
01318 #else
01319 #define Verify_BB(bb)
01320 #endif
01321 
01322 /*
01323 **  return true  if BB needs to be processed (compile)
01324 **  return false if BB is already compiled
01325 */
01326 inline BOOL BB_compile(BB *bb)
01327 {
01328   return (BB_rid(bb) == NULL || RID_level(BB_rid(bb)) < RL_CGSCHED);
01329 }
01330 
01331 /* Routine for displaying the flow graph using DaVinci */
01332 void draw_flow_graph(void);
01333 void verify_flow_graph(void);
01334 
01335 #endif /* bb_INCLUDED */