Open64: osprey/be/cg/sched/dag.h Source File

00001 /*
00002   Copyright (C) 2000-2003, Intel Corporation
00003   All rights reserved.
00004   
00005   Redistribution and use in source and binary forms, with or without modification,
00006   are permitted provided that the following conditions are met:
00007   
00008   Redistributions of source code must retain the above copyright notice, this list
00009   of conditions and the following disclaimer. 
00010   
00011   Redistributions in binary form must reproduce the above copyright notice, this list
00012   of conditions and the following disclaimer in the documentation and/or other materials
00013   provided with the distribution. 
00014 
00015   Neither the name of the owner nor the names of its contributors may be used to endorse or
00016   promote products derived from this software without specific prior written permission. 
00017 
00018   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
00019   IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
00020   FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR
00021   ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00022   NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
00023   BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00024   LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00025   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00026 */
00027 
00028 //-*-c++-*-
00029 
00030 //*********************************************************************
00031 //
00032 // Module: dag.h
00033 // $Date: 2005/12/30 01:50:22 $
00034 // $Author: weitang $
00035 // $Source: /depot/CVSROOT/javi/src/sw/cmplr/be/cg/sched/dag.h,v $
00036 //
00037 // Description:
00038 //
00039 // Interface of DAG (dependence graph) construction related utilities.
00040 //
00041 //*********************************************************************
00042 
00043 #ifndef dag_INCLUDED
00044 #define dag_INCLUDED
00045 
00046 #include <set>
00047 //#if (__GNUC__ == 3)
00048 #include <ext/hash_map>
00049 using __gnu_cxx::hash_map;
00050 using std::vector;
00051 using std::set;
00052 //#endif // __GNUC__ == 3
00053 #include "tn_map.h"
00054 #include "region.h"
00055 #include "bitset.h"
00056 #include "cg_dep_graph.h"
00057 
00058 /* Bitset switch used in DAG construction
00059  */
00060 #define    DAG_BITSET_SWITCH_ON
00061 
00062 
00063 /* Functions defined in cg_dep_graph.cxx.
00064  */
00065 extern BOOL has_assigned_reg(TN *tn);
00066 extern void add_reg_assignment(TN *tn);
00067 extern void add_gtn_use_arc(OP *op, UINT8 opnd);
00068 extern BOOL OP_like_store(OP *op);
00069 extern BOOL get_mem_dep(OP *pred, OP *succ, BOOL *definite, UINT8 *omega);
00070 extern ARC *new_arc_with_latency(CG_DEP_KIND kind, OP *pred, OP *succ,
00071                                  INT16 latency, UINT8 omega,
00072                                  UINT8 opnd, BOOL is_definite);
00073 extern ARC *shorter_succ_arc(ARC *arc1, ARC *arc2);
00074 extern void adjust_for_rw_elim(ARC_LIST *arcs, UINT32 num_definite_arcs,
00075                                ARC *shortest, ARC *shortest_to_from_store);
00076 extern BOOL op_defines_sp(OP *op);
00077 extern BOOL CG_DEP_Alloca_Aliases(OP *mem_op);
00078 extern BOOL is_xfer_depndnce_reqd(const void *op, const void *xfer_op);
00079 extern void maybe_add_exit_sp_adj_arc (OP *mem_op, OP *exit_sp_adj_op);
00080 extern _CG_DEP_OP_INFO *new_op_info(void);
00081 extern void Invoke_Init_Routines();
00082 extern void CG_DEP_Delete_DAG(void);
00083 
00084 extern TN_MAP gtn_use_map;
00085 
00086 inline BOOL ARC_is_memin(ARC *arc)
00087 {
00088     return ARC_kind(arc) == CG_DEP_MEMIN;
00089 }
00090 
00091 inline BOOL ARC_is_postbr(ARC *arc)
00092 {
00093     return ARC_kind(arc) == CG_DEP_POSTBR;
00094 }
00095 
00096 inline BOOL ARC_is_br(ARC *arc)
00097 {
00098     return ARC_kind(arc) == CG_DEP_POSTBR || 
00099            ARC_kind(arc) == CG_DEP_PREBR;
00100 }
00101 
00102 inline BOOL ARC_is_postchk(ARC *arc)
00103 {
00104 #if defined(TARG_IA64)
00105     return ARC_kind(arc) == CG_DEP_POSTCHK;
00106 #else
00107     return FALSE;
00108 #endif
00109 }
00110 
00111 inline BOOL ARC_is_ctlspec(ARC *arc)
00112 {
00113 #if defined(TARG_IA64)
00114     return ARC_kind(arc) == CG_DEP_CTLSPEC;
00115 #else
00116     return FALSE;
00117 #endif
00118 }
00119 
00120 inline BOOL
00121 ARC_is_control_spec(ARC* arc) {
00122     if ( ARC_is_dotted(arc) &&
00123          ( ARC_is_postbr(arc) && OP_br(ARC_pred(arc)) ||
00124            ARC_is_postchk(arc) 
00125 #ifdef TARG_IA64 
00126            && OP_chk(ARC_pred(arc)) 
00127 #endif 
00128            || ARC_is_ctlspec(arc)) ) {
00129         return TRUE;
00130     }
00131 
00132     return FALSE;
00133 }
00134 
00135 
00136 inline BOOL
00137 ARC_is_data_spec(ARC* arc) {
00138     if (ARC_is_dotted(arc) &&
00139         ARC_is_mem(arc) &&
00140         OP_store(ARC_pred(arc))) {
00141         return TRUE;
00142     }
00143 
00144     return FALSE;
00145 }
00146 
00147 inline BOOL
00148 ARC_is_spec(ARC* arc) {
00149     return ARC_is_control_spec(arc) || ARC_is_data_spec(arc);
00150 }
00151 
00152 /* Base class for the use of mempool.
00153  */
00154 class DAG_MEM {
00155 protected:
00156     MEM_POOL _mem_pool;
00157 
00158     DAG_MEM() {
00159         MEM_POOL_Initialize( &_mem_pool, "DAG_MEM", true );
00160         MEM_POOL_Push( &_mem_pool );
00161     }
00162     ~DAG_MEM() {
00163         MEM_POOL_Pop( &_mem_pool );
00164         MEM_POOL_Delete(&_mem_pool );
00165     }
00166 };
00167 
00168 /* ====================================================================
00169  *
00170  * DAG_BUILDER:
00171  *
00172  * This class is intended for building DAG for a SEME region.
00173  *
00174  * ====================================================================
00175  */
00176 class DAG_BUILDER : public DAG_MEM {
00177 
00178 friend class SCHEDULER;
00179 
00180 private:
00181     typedef std::set<OP*> OPs;
00182 
00183     template <class _Ptr_Tp>
00184     struct ptr_hash {
00185         size_t operator()(_Ptr_Tp __x) const { return UINT(__x); }
00186     };
00187 
00188     /* Mapping: TN -> OPs
00189      */
00190     typedef mempool_allocator< std::pair<TN*,OPs> >          TN_OPs_ALLOC;
00191 
00192 //#if (__GNUC__ == 3)  
00193     typedef __gnu_cxx::hash_map<TN*, OPs, ptr_hash<TN*>, 
00194                 std::equal_to<TN*>, TN_OPs_ALLOC>       TN_OPs_MAP;
00195 //#else 
00196 //    typedef hash_map<TN*, OPs, ptr_hash<TN*>, equal_to<TN*>, 
00197 //                    TN_OPs_ALLOC>                       TN_OPs_MAP;
00198 //#endif
00199     typedef TN_OPs_MAP::iterator                        TN_OPs_MAP_ITER;
00200   
00201     /* Mapping: BB -> OPs
00202      */
00203     typedef mempool_allocator< std::pair<BB*,OPs> >     BB_OPs_ALLOC;
00204 //#if (__GNUC__ == 3)  
00205     typedef __gnu_cxx::hash_map<BB*, OPs,
00206                    ptr_hash<BB*>, std::equal_to<BB*>,
00207                    BB_OPs_ALLOC>                        BB_OPs_MAP;
00208 //#else
00209 //    typedef hash_map<BB*, OPs, ptr_hash<BB*>, 
00210 //                   equal_to<BB*>, BB_OPs_ALLOC>         BB_OPs_MAP;
00211 //#endif
00212     typedef BB_OPs_MAP::iterator                        BB_OPs_MAP_ITER;
00213   
00214     /* Mapping: BB -> (TN -> OPs)
00215      */
00216     typedef mempool_allocator< std::pair<BB*,TN_OPs_MAP> >   BB_DEF_USE_ALLOC;
00217 //#if (__GNUC__ == 3)  
00218     typedef __gnu_cxx::hash_map<BB*, TN_OPs_MAP,
00219                    ptr_hash<BB*>, std::equal_to<BB*>,
00220                    BB_DEF_USE_ALLOC>                    BB_DEF_USE_MAP;
00221 //#else
00222 //    typedef hash_map<BB*, TN_OPs_MAP, ptr_hash<BB*>, 
00223 //                equal_to<BB*>, BB_DEF_USE_ALLOC>        BB_DEF_USE_MAP;
00224 //#endif
00225     typedef BB_DEF_USE_MAP::iterator                    BB_DEF_USE_MAP_ITER;
00226 
00227     /* Define the OP vector
00228      */ 
00229     typedef mempool_allocator<OP*>                 OP_TABLE_ALLOC;
00230     typedef vector<OP*,OP_TABLE_ALLOC>                   OP_TABLE;
00231     typedef OP_TABLE::iterator                            OP_TABLE_ITER;
00232 
00233     /* Define the Define OPs 
00234      */ 
00235     typedef mempool_allocator<OP*>                 DEFINE_OPS_ALLOC;
00236     typedef vector<OP*,DEFINE_OPS_ALLOC>                   DEFINE_OPS;
00237     typedef DEFINE_OPS::iterator                            DEFINE_OPS_ITER;
00238 
00239 
00240     /* Define the TN vector
00241      */
00242     typedef mINT32 mTN_INDEX;   
00243     typedef struct {
00244         
00245         BS*      def ;
00246         BS*      use ;
00247 
00248     }TN_BITSET_TABLE_ENTRY;
00249       
00250     typedef mempool_allocator<TN_BITSET_TABLE_ENTRY>   TN_BITSET_TABLE_ALLOC;
00251     typedef vector<TN_BITSET_TABLE_ENTRY,TN_BITSET_TABLE_ALLOC>  TN_BITSET_TABLE;
00252 
00253     typedef mempool_allocator<mTN_INDEX>    TN_BITSET_TABLE_INDEX_ALLOC;
00254     typedef vector<mTN_INDEX,TN_BITSET_TABLE_INDEX_ALLOC> TN_BITSET_TABLE_INDEX;
00255 
00256 
00257     /* Define the BB vector
00258      */
00259     typedef mINT32 mBB_INDEX;   
00260     typedef struct{
00261 
00262             BB*      bb;
00263             BS*      in;
00264             BS*      out;
00265             BS*      kill;
00266             BS*      gen;
00267             BS*      reverse_in;
00268             BS*      reverse_out;
00269 
00270     }BB_BITSET_TABLE_ENTRY;
00271 
00272     typedef mempool_allocator<BB_BITSET_TABLE_ENTRY>  BB_BITSET_TABLE_ALLOC;
00273     typedef vector<BB_BITSET_TABLE_ENTRY,BB_BITSET_TABLE_ALLOC>  BB_BITSET_TABLE;
00274     typedef mempool_allocator<mBB_INDEX>  BB_BITSET_TABLE_INDEX_ALLOC;
00275     typedef vector<mBB_INDEX,BB_BITSET_TABLE_INDEX_ALLOC>  BB_BITSET_TABLE_INDEX;
00276 
00277     
00278 
00279 
00280     BOOL            _cyclic;
00281     BOOL            _include_assigned_registers;
00282     BOOL            _include_memread_arcs;
00283     BOOL            _include_memin_arcs;
00284     BOOL            _include_control_arcs;
00285     BB*             _bb;
00286     REGION*         _region;
00287     UINT            _num_data_spec_arcs;
00288     UINT            _num_cntl_spec_arcs;
00289     BB_OPs_MAP      _bb_ops_map;
00290     BB_DEF_USE_MAP  _bb_def_info_map;
00291     BB_DEF_USE_MAP  _bb_use_info_map;
00292     OPs             _empty_set;
00293 
00294     mINT32       _OP_Count, _BB_Count;
00295     OP_TABLE     _OP_Table;
00296     DEFINE_OPS _Define_OPs;
00297     TN_BITSET_TABLE     _TN_Bitset_Table;
00298     TN_BITSET_TABLE_INDEX   _TN_Bitset_Table_Index;
00299     mINT32      _Max_TN_number;
00300     mINT32      _Max_BB_id;
00301     BB_BITSET_TABLE     _BB_Bitset_Table;
00302     BB_BITSET_TABLE_INDEX _BB_Bitset_Table_Index;
00303     BS* _out;
00304     BS* _reverse_out;
00305     
00306 #ifdef TARG_IA64
00307     /* predicate query system 
00308      */
00309     PRDB_GEN*       _prdb ;
00310 #endif
00311 
00312     /* Internal member functions.
00313      */
00314     BOOL OP_Shadowed_By_Prev_OPs (OP*, OPs&, COMPARE_FUNCTION);
00315     mINT32 Get_Table_Index(OP* op);
00316     mINT32 Get_Table_Index(BB* bb);
00317     mINT32 Get_Table_Index(TN* tn);
00318     BOOL Is_Control_Speculative (OP* pred, OP* succ);
00319     OPs& Get_Def_Use_OPs    (OP *op, UINT8 res, CG_DEP_KIND arc_kind);
00320     void Set_Def_Use_OPs    (OP *op);
00321     mUINT16 OP_To_Gid             (OP* op);
00322     OP* Gid_To_OP       (mINT32 order);
00323     void Set_OP_Order        (OP* op);
00324     void Update_Max_TN_number     (OP* op);
00325     void Init_TN_BB_Bitset_Table(void);
00326     void Set_TN_BB_Bitset_Table(void);
00327     void Update_Max_BB_id(BB* bb);
00328     BS* Union_Of_Preds(BB* bb);
00329     BS* Union_Of_Succs(BB* bb);
00330     void Get_Define_OPs(OP *op, UINT8 res, CG_DEP_KIND arc_kind);
00331     void Compute_Defs_Uses_In (BB* bb);
00332     void Compute_OPs_In     (BB* bb);
00333     void Build_Reg_Arcs     (OP* op);
00334     void Build_Mem_Arcs     (OP *op);
00335     void Build_Branch_Arcs  (OP* op, BOOL include_latency);
00336   
00337     /* misc */
00338     INT16 Find_Ancestor_BB (BB * bb, BB_VECTOR * bbv) ;
00339     INT16 Find_Successor_BB (BB * bb, BB_VECTOR * bbv) ;
00340 
00341 public:
00342 
00343     /* Constructors and Destructors.
00344      */
00345 #ifdef TARG_IA64
00346     DAG_BUILDER (REGION* region, PRDB_GEN * prdb,
00347                      BOOL    assigned_regs, BOOL    memread_arcs,
00348                      BOOL    memin_arcs,    BOOL    control_arcs);
00349     DAG_BUILDER(BB* bb,PRDB_GEN* prdb=NULL);
00350 #else
00351     DAG_BUILDER (REGION* region, 
00352                      BOOL    assigned_regs, BOOL    memread_arcs,
00353                      BOOL    memin_arcs,    BOOL    control_arcs);
00354     DAG_BUILDER(BB* bb);
00355 #endif
00356 
00357     ~DAG_BUILDER(void);
00358 
00359     /* Exported interfaces */
00360     void Build_DAG (void);
00361     void Build_Misc_Arcs    (OP* op);
00362 };
00363 
00364 
00365 INT16 get_opnd_idx (OP *op , TN* tn) ;
00366 void adjust_reganti_latency (ARC *arc) ;
00367 void adjust_reganti_latency (BB *bb) ;
00368 
00369 #endif
00370