Open64: osprey/be/com/fb_whirl.h Source File

00001 /* -*- c++ -*-
00002  *
00003  * Copyright 2003, 2004, 2005, 2006 PathScale, Inc.  All Rights Reserved.
00004  */
00005 
00006 /*
00007 
00008   Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.
00009 
00010   This program is free software; you can redistribute it and/or modify it
00011   under the terms of version 2 of the GNU General Public License as
00012   published by the Free Software Foundation.
00013 
00014   This program is distributed in the hope that it would be useful, but
00015   WITHOUT ANY WARRANTY; without even the implied warranty of
00016   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
00017 
00018   Further, this software is distributed without any warranty that it is
00019   free of the rightful claim of any third person regarding infringement 
00020   or the like.  Any license provided herein, whether implied or 
00021   otherwise, applies only to this software file.  Patent licenses, if 
00022   any, provided herein do not apply to combinations of this program with 
00023   other software, or any other product whatsoever.  
00024 
00025   You should have received a copy of the GNU General Public License along
00026   with this program; if not, write the Free Software Foundation, Inc., 59
00027   Temple Place - Suite 330, Boston MA 02111-1307, USA.
00028 
00029   Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
00030   Mountain View, CA 94043, or:
00031 
00032   http://www.sgi.com
00033 
00034   For further information regarding this notice, see:
00035 
00036   http://oss.sgi.com/projects/GenInfo/NoticeExplan
00037 
00038 */
00039 
00040 
00041 //-*-c++-*-
00042 // ====================================================================
00043 // ====================================================================
00044 //
00045 // Module: fb_whirl.h
00046 // $Source: /scratch/mee/2.4-65/kpro64-pending/be/com/SCCS/s.fb_whirl.h $
00047 //
00048 // Description:
00049 //
00050 // During instrumentation, certain events associated with program
00051 // control flow (such as the number of times a particular branch is
00052 // taken, or not taken) are counted.  During subsequent compilations,
00053 // this data may be retrieved and used to guide optimization decisions.
00054 //
00055 // fb_whirl.h and fb_whirl.cxx define data structures and functions to
00056 // manipulate this feedback information.
00057 //
00058 // When initially retrieved from the file of instrumentation data,
00059 // frequencies count the number of times that certain events occurred
00060 // during execution.
00061 //
00062 // Some whirl transformations require frequency values to be scaled
00063 // or estimated.  Consequently, these values may not always be exact
00064 // or even compatible.
00065 //
00066 // ====================================================================
00067 // ====================================================================
00068 
00069 #ifndef fb_whirl_INCLUDED
00070 #define fb_whirl_INCLUDED
00071 
00072 #include "fb_info.h"
00073 #include "mempool_allocator.h"
00074 #ifndef wn_INCLUDED
00075 #include "wn.h"
00076 #endif
00077 #include <vector>             // STL vector.
00078 
00079 #ifndef instr_reader_INCLUDED
00080 #include "instr_reader.h"
00081 #endif
00082 
00083 
00084 // ====================================================================
00085 // Tracing masks for TP_FEEDBACK tracing phase
00086 // ====================================================================
00087 
00088 #define TP_FEEDBACK_WN         0x0001
00089 #define TP_FEEDBACK_WN_DRAW    0x0002
00090 #define TP_FEEDBACK_CFG        0x0010
00091 #define TP_FEEDBACK_CFG_DRAW   0x0020
00092 #define TP_FEEDBACK_CFG_BEFORE 0x0040
00093 #define TP_FEEDBACK_CFG_PROP   0x0080
00094 #define TP_OPT_FEEDBACK        0x0100
00095 #define TP_OPT_FEEDBACK_DRAW   0x0200
00096 #define TP_OPT_FEEDBACK_BEFORE 0x0400
00097 #define TP_OPT_FEEDBACK_PROP   0x0800
00098 #define TP_CG_FEEDBACK         0x1000
00099 #define TP_CG_FEEDBACK_DRAW    0x2000
00100 
00101 
00102 // ==================================================================
00103 // Map to record <pu_runtime_address, pu_name> pair.
00104 // 
00105 
00106 template <class _Key> struct fbhash { };
00107 template <> struct fbhash<UINT64> {
00108   size_t operator()(const UINT64 x)const{return (size_t)x;}
00109 };
00110 
00111 typedef hash_map<UINT64, char*, fbhash<UINT64> > ADDRESS_NAME_MAP;
00112 typedef hash_map<UINT64, INT32, fbhash<UINT64> > ADDRESS_PUSIZE_MAP;
00113 
00114 
00115 // ====================================================================
00116 
00117 // FEEDBACK::Verify(...) and OPT_FEEDBACK::Verify(...) return one of
00118 // the following values.  "UNBALANCED" means that some of the frequency
00119 // values are UNKNOWN or do not add up, and "INVALID" indicates the
00120 // presence of UNINITialized or ERROR frequencies.
00121 
00122 enum FB_VERIFY_STATUS {
00123   FB_VERIFY_CONSISTENT,
00124   FB_VERIFY_UNBALANCED,
00125   FB_VERIFY_INVALID
00126 };
00127 
00128 // ====================================================================
00129 
00130 class FEEDBACK {
00131 #ifdef KEY
00132   friend class ARA_LOOP_INFO;
00133 #endif
00134 private:
00135 
00136   MEM_POOL   *_m;
00137   WN_MAP_TAB *_maptab;
00138   WN         *_root_wn;
00139   bool        _trace;      // Get_Trace(TP_FEEDBACK, TP_FEEDBACK_WN)
00140   bool        _trace_draw; // Get_Trace(TP_FEEDBACK, TP_FEEDBACK_WN_DRAW)
00141 
00142 #ifdef KEY
00143   UINT64     _runtime_func_addr;  // run time function address
00144 #endif
00145 
00146   // For Whirl nodes, the map WN_MAP_FEEDBACK holds an index into
00147   // one of the following vectors:
00148 
00149   vector< FB_Info_Invoke,  mempool_allocator<FB_Info_Invoke>  >  _invokes;
00150   vector< FB_Info_Branch,  mempool_allocator<FB_Info_Branch>  >  _branches;
00151   vector< FB_Info_Loop,    mempool_allocator<FB_Info_Loop>    >  _loops;
00152   vector< FB_Info_Circuit, mempool_allocator<FB_Info_Circuit> >  _circuits;
00153   vector< FB_Info_Call,    mempool_allocator<FB_Info_Call>    >  _calls;
00154   vector< FB_Info_Icall,   mempool_allocator<FB_Info_Icall>   >  _icalls;
00155   vector< FB_Info_Switch,  mempool_allocator<FB_Info_Switch>  >  _switches;
00156 #ifdef KEY
00157   vector< FB_Info_Value,   mempool_allocator<FB_Info_Value>    >  _values;
00158   vector< FB_Info_Value_FP_Bin,mempool_allocator<FB_Info_Value_FP_Bin> > _values_fp_bin;
00159 #endif
00160 
00161   INT32 Get_index_invoke  ( const WN *wn ) const;
00162   INT32 Get_index_branch  ( const WN *wn ) const;
00163   INT32 Get_index_loop    ( const WN *wn ) const;
00164   INT32 Get_index_circuit ( const WN *wn ) const;
00165   INT32 Get_index_call    ( const WN *wn ) const;
00166   INT32 Get_index_icall   ( const WN *wn ) const;
00167   INT32 Get_index_switch  ( const WN *wn ) const;
00168 #ifdef KEY
00169   INT32 Get_index_value   ( const WN *wn ) const;
00170   INT32 Get_index_value_fp_bin( const WN *wn ) const;
00171 #endif
00172 
00173   INT32 Add_index_invoke  ( WN *wn );
00174   INT32 Add_index_branch  ( WN *wn );
00175   INT32 Add_index_loop    ( WN *wn );
00176   INT32 Add_index_circuit ( WN *wn );
00177   INT32 Add_index_call    ( WN *wn );
00178   INT32 Add_index_icall   ( WN *wn );
00179   INT32 Add_index_switch  ( WN *wn );
00180 #ifdef KEY
00181   INT32 Add_index_value   ( WN *wn );
00182   INT32 Add_index_value_fp_bin( WN *wn );
00183 #endif
00184 
00185 public:
00186 
00187   FEEDBACK( WN *wn, MEM_POOL *m,
00188       INT32 invoke_size = 1,
00189       INT32 branch_size = 1,
00190       INT32 loop_size = 1,
00191       INT32 circuit_size = 1,
00192       INT32 call_size = 1,
00193       INT32 icall_size = 1,
00194       INT32 switch_size = 1,
00195 #ifdef KEY
00196       INT32 value_size = 1,
00197       INT32 value_fp_bin_size = 1,
00198       UINT64 runtime_fun_address = 0x0,
00199 #endif
00200       WN_MAP_TAB *maptab = Current_Map_Tab );
00201 
00202   void  Reset_Root_WN( WN *root_wn ) { _root_wn = root_wn; }
00203 
00204 #ifdef KEY
00205   void Set_Runtime_Func_Addr( UINT64 addr ) { _runtime_func_addr = addr; }
00206   UINT64 Get_Runtime_Func_Addr() { return _runtime_func_addr; }
00207 #endif
00208 
00209   bool  Same_in_out( const WN *wn );
00210   void  FB_set_in_out_same_node( WN *wn );
00211   void  FB_set_in_out_same( WN *wn );
00212 
00213 #if defined(TARG_SL) && defined(TARG_SL2)
00214   void FB_reset_in_out_same_node( WN *wn );
00215 #endif
00216 
00217   void  Print         ( FILE *fp, const WN *wn ) const;
00218   void  Print_with_wn ( FILE *fp, WN *wn ) const;
00219 
00220   const FB_Info_Invoke&  Query_invoke  ( const WN *wn ) const;
00221   const FB_Info_Branch&  Query_branch  ( const WN *wn ) const;
00222   const FB_Info_Loop&    Query_loop    ( const WN *wn ) const;
00223   const FB_Info_Circuit& Query_circuit ( const WN *wn ) const;
00224   const FB_Info_Call&    Query_call    ( const WN *wn ) const;
00225   const FB_Info_Icall&   Query_icall   ( const WN *wn ) const;
00226   const FB_Info_Switch&  Query_switch  ( const WN *wn ) const;
00227 #ifdef KEY
00228   const FB_Info_Value&    Query_value   ( const WN *wn ) const;
00229   const FB_Info_Value_FP_Bin& Query_value_fp_bin( const WN *wn ) const;
00230 #endif
00231 
00232   FB_FREQ Query      ( const WN *wn, const FB_EDGE_TYPE type ) const;
00233   FB_FREQ Query_prob ( const WN *wn, const FB_EDGE_TYPE type ) const;
00234   FB_FREQ Query_total_out ( const WN *wn ) const;
00235 
00236   void Annot_invoke  ( WN *wn, const FB_Info_Invoke & fb_info );
00237   void Annot_branch  ( WN *wn, const FB_Info_Branch & fb_info );
00238   void Annot_loop    ( WN *wn, const FB_Info_Loop   & fb_info );
00239   void Annot_circuit ( WN *wn, const FB_Info_Circuit& fb_info );
00240   void Annot_call    ( WN *wn, const FB_Info_Call   & fb_info );
00241   void Annot_icall   ( WN *wn, const FB_Info_Icall  & fb_info );
00242   void Annot_switch  ( WN *wn, const FB_Info_Switch & fb_info );
00243 #ifdef KEY
00244   void Annot_value   ( WN *wn, const FB_Info_Value  & fb_info );
00245   void Annot_value_fp_bin( WN *wn, const FB_Info_Value_FP_Bin  & fb_info );
00246 #endif
00247 
00248   void Annot         ( WN *wn, const FB_EDGE_TYPE type, FB_FREQ freq );
00249 
00250   // Resets feedback info to FB_FREQ_UNINIT; use when wn is deleted
00251   void Delete(WN *wn) {
00252     IPA_WN_MAP32_Set ( _maptab, WN_MAP_FEEDBACK, wn, 0 );
00253   }
00254 
00255   FB_VERIFY_STATUS Verify( const char *caller         = NULL,
00256          bool        abort_if_error = TRUE ) const;
00257 
00258   FB_VERIFY_STATUS Verify_and_guess( const char *caller         = NULL,
00259              bool        abort_if_error = TRUE ) const;
00260 
00261   // Feedback info in CG is carried by code-gen internal structures.
00262   // Verification for CG feedback info done apart from FEEDBACK class.
00263 
00264   // Lower feedback info
00265 
00266   void FB_lower_branch  ( WN *wn_br,   WN *wn_branch );
00267   void FB_lower_circuit ( WN *wn_cand, WN *wn_left_br, WN *wn_right_br );
00268   void FB_factor_circuit( WN *wn_left, WN *wn_right,
00269         WN *wn_outer, WN *wn_inner );
00270 
00271   void FB_lower_loop     ( WN *wn_loop, WN *wn_top_br, WN *wn_back_br );
00272   void FB_lower_loop_alt ( WN *wn_loop, WN *wn_top_br );
00273   void FB_lower_while_do_to_do_while ( WN *wn_loop, WN *wn_top_br );
00274 
00275   void FB_lower_compgoto ( WN *wn_compgoto, WN *wn_xgoto, WN *wn_branch );
00276 
00277   void FB_lower_call ( WN *wn_call, WN *wn_new_call );
00278   void FB_lower_icall( WN *wn_icall, WN *wn_new_icall, WN * wn_new_call, WN * wn_new_if );
00279   void FB_lower_return_val ( WN *wn_return_val, WN *wn_return );
00280 
00281   void FB_lower_mstore_to_loop ( WN *wn_mstore, WN *wn_loop, INT64 nMoves );
00282   void FB_hoist_case( WN *wn_switch, vector<FB_FREQ>::size_type wcase);
00283 
00284   // Goto conversion
00285 
00286   void FB_move_goto_out( WN *wn_branch, WN *wn_inner_br, WN *wn_outer_br );
00287   void FB_convert_goto_to_if(   WN *wn_branch, WN *wn_if );
00288   void FB_convert_goto_to_loop( WN *wn_branch, WN *wn_loop );
00289 
00290   void FB_simplify_branch_to_goto( WN *wn_branch );
00291 
00292   // Cloning (clone freq = original freq * scale; original reduced by same)
00293   void FB_set_zero_node(    WN *wn );
00294   void FB_set_zero(         WN *wn );
00295   void FB_set_unknown_node( WN *wn );
00296   void FB_set_unknown(      WN *wn );
00297   void FB_scale_node(       WN *wn, FB_FREQ freq_scale );
00298   void FB_scale(            WN *wn, FB_FREQ freq_scale );
00299   void FB_duplicate_node(   WN *wn_origl, WN *wn_clone );
00300   void FB_duplicate(        WN *wn_origl, WN *wn_clone );
00301   void FB_recombine_node(   WN *wn_origl, WN *wn_clone );
00302   void FB_recombine(        WN *wn_origl, WN *wn_clone );
00303   void FB_clone_node(       WN *wn_origl, WN *wn_clone, FB_FREQ freq_scale );
00304   void FB_clone(            WN *wn_origl, WN *wn_clone, FB_FREQ freq_scale );
00305 
00306 private:
00307   void FB_clone_test( WN *wn_origl, WN *wn_clone,
00308           FB_FREQ freq_origl_taken, FB_FREQ freq_origl_not,
00309           FB_FREQ freq_clone_taken, FB_FREQ freq_clone_not );
00310 public:
00311   void FB_clone_loop_test( WN *wn_origl, WN *wn_clone, WN *wn_loop );
00312 
00313   void Display_FB_CFG_From_Whirl(const char *caller = NULL);
00314 
00315   // IPA interface
00316 
00317   friend void FB_IPA_Clone_node(
00318           FEEDBACK *feedback_origl, FEEDBACK *feedback_clone,
00319           WN             *wn_origl, WN             *wn_clone,
00320           FB_FREQ freq_scale );
00321 
00322   friend void FB_IPA_Clone( FEEDBACK *feedback_origl, FEEDBACK *feedback_clone,
00323           WN             *wn_origl, WN             *wn_clone,
00324           FB_FREQ freq_scale );
00325 
00326   friend void FB_IPA_Clone( FEEDBACK *feedback_origl, FEEDBACK *feedback_clone,
00327           WN             *wn_origl, WN             *wn_clone,
00328           float scale ) {
00329     FB_IPA_Clone( feedback_origl, feedback_clone, wn_origl, wn_clone,
00330       FB_FREQ( scale, false ) );
00331   }
00332 
00333   friend void FB_IPA_Inline(FEEDBACK *feedback_origl, FEEDBACK *feedback_clone,
00334           WN             *wn_origl, WN             *wn_clone,
00335           FB_FREQ freq_scale );
00336 
00337   // Transfer FB from one PU to another, for MP lowerer
00338 
00339   friend void FB_Transfer_node(
00340                           FEEDBACK *feedback_origl, FEEDBACK *feedback_new,
00341                           WN                   *wn);
00342 
00343   friend void FB_Transfer(FEEDBACK *feedback_origl, FEEDBACK *feedback_new,
00344                           WN                   *wn);
00345 
00346 };
00347 
00348 extern "C" void dump_fb ( const FEEDBACK *feedback, const WN *wn );
00349 
00350 extern FEEDBACK *Cur_PU_Feedback;
00351  
00352 extern ADDRESS_NAME_MAP PU_Addr_Name_Map;
00353 extern ADDRESS_PUSIZE_MAP PU_Addr_Pusize_Map;
00354 
00355 extern INT
00356 Convert_Feedback_Info (const FEEDBACK* fb, const WN* tree,
00357            PU_Profile_Handle& pu_handle);
00358 
00359 extern void
00360 Read_Feedback_Info (FEEDBACK* fb, WN* tree, const Pu_Hdr& pu_hdr);
00361 
00362 // scale is portion of freq transfered to clone; original gets (1 - scale)
00363 
00364 #ifdef __cplusplus
00365 extern "C" {
00366 #endif
00367 
00368 void FB_old_Annotate_whirl(WN *);  // remove when new scheme ready ..
00369 
00370 #ifdef __cplusplus
00371 }
00372 #endif
00373 
00374 #define FB_DEVWARN_LIMIT  5
00375 
00376 #endif