00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043 #ifndef dag_INCLUDED
00044 #define dag_INCLUDED
00045
00046 #include <set>
00047 #include "tn_map.h"
00048 #include "region.h"
00049 #include "recovery.h"
00050 #include "prdb.h"
00051 #include "bitset.h"
00052
00053
00054
00055
00056 #define DAG_BITSET_SWITCH_ON
00057
00058
00059
00060
00061 extern BOOL has_assigned_reg(TN *tn);
00062 extern void add_reg_assignment(TN *tn);
00063 extern void add_gtn_use_arc(OP *op, UINT8 opnd);
00064 extern BOOL OP_like_store(OP *op);
00065 extern BOOL get_mem_dep(OP *pred, OP *succ, BOOL *definite, UINT8 *omega);
00066 extern ARC *new_arc_with_latency(CG_DEP_KIND kind, OP *pred, OP *succ,
00067 INT16 latency, UINT8 omega,
00068 UINT8 opnd, BOOL is_definite);
00069 extern ARC *shorter_succ_arc(ARC *arc1, ARC *arc2);
00070 extern void adjust_for_rw_elim(ARC_LIST *arcs, UINT32 num_definite_arcs,
00071 ARC *shortest, ARC *shortest_to_from_store);
00072 extern BOOL op_defines_sp(OP *op);
00073 extern BOOL CG_DEP_Alloca_Aliases(OP *mem_op);
00074 extern BOOL is_xfer_depndnce_reqd(const void *op, const void *xfer_op);
00075 extern void maybe_add_exit_sp_adj_arc (OP *mem_op, OP *exit_sp_adj_op);
00076 extern _CG_DEP_OP_INFO *new_op_info(void);
00077 extern void Invoke_Init_Routines();
00078 extern void CG_DEP_Delete_DAG(void);
00079
00080 extern TN_MAP gtn_use_map;
00081
00082 inline BOOL ARC_is_memin(ARC *arc)
00083 {
00084 return ARC_kind(arc) == CG_DEP_MEMIN;
00085 }
00086
00087 inline BOOL ARC_is_postbr(ARC *arc)
00088 {
00089 return ARC_kind(arc) == CG_DEP_POSTBR;
00090 }
00091
00092 inline BOOL ARC_is_br(ARC *arc)
00093 {
00094 return ARC_kind(arc) == CG_DEP_POSTBR ||
00095 ARC_kind(arc) == CG_DEP_PREBR;
00096 }
00097
00098 inline BOOL ARC_is_postchk(ARC *arc)
00099 {
00100 return ARC_kind(arc) == CG_DEP_POSTCHK;
00101 }
00102
00103 inline BOOL ARC_is_ctlspec(ARC *arc)
00104 {
00105 return ARC_kind(arc) == CG_DEP_CTLSPEC;
00106 }
00107
00108 inline BOOL
00109 ARC_is_control_spec(ARC* arc) {
00110 if ( ARC_is_dotted(arc) &&
00111 ( ARC_is_postbr(arc) && OP_br(ARC_pred(arc)) ||
00112 ARC_is_postchk(arc) && OP_chk(ARC_pred(arc)) ||
00113 ARC_is_ctlspec(arc)) ) {
00114 return TRUE;
00115 }
00116
00117 return FALSE;
00118 }
00119
00120
00121 inline BOOL
00122 ARC_is_data_spec(ARC* arc) {
00123 if (ARC_is_dotted(arc) &&
00124 ARC_is_mem(arc) &&
00125 OP_store(ARC_pred(arc))) {
00126 return TRUE;
00127 }
00128
00129 return FALSE;
00130 }
00131
00132 inline BOOL
00133 ARC_is_spec(ARC* arc) {
00134 return ARC_is_control_spec(arc) || ARC_is_data_spec(arc);
00135 }
00136
00137
00138
00139 class DAG_MEM {
00140 protected:
00141 MEM_POOL _mem_pool;
00142
00143 DAG_MEM() {
00144 MEM_POOL_Initialize( &_mem_pool, "DAG_MEM", true );
00145 MEM_POOL_Push( &_mem_pool );
00146 }
00147 ~DAG_MEM() {
00148 MEM_POOL_Pop( &_mem_pool );
00149 MEM_POOL_Delete(&_mem_pool );
00150 }
00151 };
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161 class DAG_BUILDER : public DAG_MEM {
00162
00163 friend class SCHEDULER;
00164
00165 private:
00166 typedef std::set<OP*> OPs;
00167
00168 template <class _Ptr_Tp>
00169 struct ptr_hash {
00170 size_t operator()(_Ptr_Tp __x) const { return (UINT)(INTPTR)(__x); }
00171 };
00172
00173
00174
00175 typedef mempool_allocator< std::pair<TN*,OPs> > TN_OPs_ALLOC;
00176 typedef __gnu_cxx::hash_map<TN*, OPs,
00177 ptr_hash<TN*>, std::equal_to<TN*>,
00178 TN_OPs_ALLOC> TN_OPs_MAP;
00179 typedef TN_OPs_MAP::iterator TN_OPs_MAP_ITER;
00180
00181
00182
00183 typedef mempool_allocator< std::pair<BB*,OPs> > BB_OPs_ALLOC;
00184 typedef __gnu_cxx::hash_map<BB*, OPs,
00185 ptr_hash<BB*>, std::equal_to<BB*>,
00186 BB_OPs_ALLOC> BB_OPs_MAP;
00187 typedef BB_OPs_MAP::iterator BB_OPs_MAP_ITER;
00188
00189
00190
00191 typedef mempool_allocator< std::pair<BB*,TN_OPs_MAP> > BB_DEF_USE_ALLOC;
00192 typedef __gnu_cxx::hash_map<BB*, TN_OPs_MAP,
00193 ptr_hash<BB*>, std::equal_to<BB*>,
00194 BB_DEF_USE_ALLOC> BB_DEF_USE_MAP;
00195 typedef BB_DEF_USE_MAP::iterator BB_DEF_USE_MAP_ITER;
00196
00197
00198
00199 typedef mempool_allocator<OP*> OP_TABLE_ALLOC;
00200 typedef std::vector<OP*,OP_TABLE_ALLOC> OP_TABLE;
00201 typedef OP_TABLE::iterator OP_TABLE_ITER;
00202
00203
00204
00205 typedef mempool_allocator<OP*> DEFINE_OPS_ALLOC;
00206 typedef std::vector<OP*,DEFINE_OPS_ALLOC> DEFINE_OPS;
00207 typedef DEFINE_OPS::iterator DEFINE_OPS_ITER;
00208
00209
00210
00211
00212 typedef mINT32 mTN_INDEX;
00213 typedef struct {
00214
00215 BS* def ;
00216 BS* use ;
00217
00218 }TN_BITSET_TABLE_ENTRY;
00219
00220 typedef mempool_allocator<TN_BITSET_TABLE_ENTRY> TN_BITSET_TABLE_ALLOC;
00221 typedef std::vector<TN_BITSET_TABLE_ENTRY,TN_BITSET_TABLE_ALLOC> TN_BITSET_TABLE;
00222
00223 typedef mempool_allocator<mTN_INDEX> TN_BITSET_TABLE_INDEX_ALLOC;
00224 typedef std::vector<mTN_INDEX,TN_BITSET_TABLE_INDEX_ALLOC> TN_BITSET_TABLE_INDEX;
00225
00226
00227
00228
00229 typedef mINT32 mBB_INDEX;
00230 typedef struct{
00231
00232 BB* bb;
00233 BS* in;
00234 BS* out;
00235 BS* kill;
00236 BS* gen;
00237 BS* reverse_in;
00238 BS* reverse_out;
00239
00240 }BB_BITSET_TABLE_ENTRY;
00241
00242 typedef mempool_allocator<BB_BITSET_TABLE_ENTRY> BB_BITSET_TABLE_ALLOC;
00243 typedef std::vector<BB_BITSET_TABLE_ENTRY,BB_BITSET_TABLE_ALLOC> BB_BITSET_TABLE;
00244 typedef mempool_allocator<mBB_INDEX> BB_BITSET_TABLE_INDEX_ALLOC;
00245 typedef std::vector<mBB_INDEX,BB_BITSET_TABLE_INDEX_ALLOC> BB_BITSET_TABLE_INDEX;
00246
00247
00248
00249
00250 BOOL _cyclic;
00251 BOOL _include_assigned_registers;
00252 BOOL _include_memread_arcs;
00253 BOOL _include_memin_arcs;
00254 BOOL _include_control_arcs;
00255 BB* _bb;
00256 REGION* _region;
00257 UINT _num_data_spec_arcs;
00258 UINT _num_cntl_spec_arcs;
00259 BB_OPs_MAP _bb_ops_map;
00260 BB_DEF_USE_MAP _bb_def_info_map;
00261 BB_DEF_USE_MAP _bb_use_info_map;
00262 OPs _empty_set;
00263
00264 mINT32 _OP_Count, _BB_Count;
00265 OP_TABLE _OP_Table;
00266 DEFINE_OPS _Define_OPs;
00267 TN_BITSET_TABLE _TN_Bitset_Table;
00268 TN_BITSET_TABLE_INDEX _TN_Bitset_Table_Index;
00269 mINT32 _Max_TN_number;
00270 mINT32 _Max_BB_id;
00271 BB_BITSET_TABLE _BB_Bitset_Table;
00272 BB_BITSET_TABLE_INDEX _BB_Bitset_Table_Index;
00273 BS* _out;
00274 BS* _reverse_out;
00275
00276
00277
00278
00279
00280 PRDB_GEN* _prdb ;
00281
00282
00283
00284 BOOL OP_Shadowed_By_Prev_OPs (OP*, OPs&, COMPARE_FUNCTION);
00285 mINT32 Get_Table_Index(OP* op);
00286 mINT32 Get_Table_Index(BB* bb);
00287 mINT32 Get_Table_Index(TN* tn);
00288 BOOL Is_Control_Speculative (OP* pred, OP* succ);
00289 OPs& Get_Def_Use_OPs (OP *op, UINT8 res, CG_DEP_KIND arc_kind);
00290 void Set_Def_Use_OPs (OP *op);
00291 mUINT16 OP_To_Gid (OP* op);
00292 OP* Gid_To_OP (mINT32 order);
00293 void Set_OP_Order (OP* op);
00294 void Update_Max_TN_number (OP* op);
00295 void Init_TN_BB_Bitset_Table(void);
00296 void Set_TN_BB_Bitset_Table(void);
00297 void Update_Max_BB_id(BB* bb);
00298 BS* Union_Of_Preds(BB* bb);
00299 BS* Union_Of_Succs(BB* bb);
00300 void Get_Define_OPs(OP *op, UINT8 res, CG_DEP_KIND arc_kind);
00301 void Compute_Defs_Uses_In (BB* bb);
00302 void Compute_OPs_In (BB* bb);
00303 void Build_Reg_Arcs (OP* op);
00304 void Build_Mem_Arcs (OP *op);
00305 void Build_Misc_Arcs (OP* op);
00306 void Build_Branch_Arcs (OP* op, BOOL include_latency);
00307
00308
00309 INT16 Find_Ancestor_BB (BB * bb, BB_VECTOR * bbv) ;
00310 INT16 Find_Successor_BB (BB * bb, BB_VECTOR * bbv) ;
00311
00312 public:
00313
00314
00315
00316 DAG_BUILDER (REGION* region, PRDB_GEN * prdb,
00317 BOOL assigned_regs, BOOL memread_arcs,
00318 BOOL memin_arcs, BOOL control_arcs);
00319
00320 DAG_BUILDER(BB* bb,PRDB_GEN* prdb=NULL);
00321
00322 ~DAG_BUILDER(void);
00323
00324
00325
00326 void Build_DAG (void);
00327 };
00328
00329
00330 INT16 get_opnd_idx (OP *op , TN* tn) ;
00331 void adjust_reganti_latency (ARC *arc) ;
00332 void adjust_reganti_latency (BB *bb) ;
00333
00334 #endif
00335
