Open64: osprey/be/opt/opt_lclsc.cxx Source File

00001 #include "opt_lclsc.h"
00002 
00003   //calculate the total bits needed for all the local variables and
00004   //initialize the _bp_map between aux_id of local variabls and bit position
00005 void
00006 LOCAL_CLSC::Init_bp_map(OPT_STAB *opt_stab)
00007 {
00008   IDX_32 nbits=0;
00009   AUX_ID i;
00010   AUX_STAB_ITER aux_stab_iter(opt_stab);
00011   FOR_ALL_NODE(i, aux_stab_iter, Init()) {
00012     AUX_STAB_ENTRY *sym = opt_stab->Aux_stab_entry(i);
00013     ST *st=sym->St();
00014     if(st!=NULL && ST_sclass(st)==SCLASS_AUTO) {
00015         if(!_bp_map.count(st))  {
00016           (_bp_map)[st]=nbits;
00017     nbits++;
00018         }
00019     }
00020   }
00021   _bs_size=nbits;
00022 
00023   if(Tracing()) {
00024     fprintf(TFile, "dump bitpos of symbals: \n");
00025     STBP_MAP::iterator mitr=_bp_map.begin();
00026     STBP_MAP::iterator mitrn=_bp_map.end();
00027     while(mitr!=mitrn) {
00028       ST* st=(*mitr).first;
00029       IDX_32 bp=(*mitr).second;
00030       fprintf(TFile, "st: %s,  bp: %d\n", ST_name(st), bp);
00031       mitr++;
00032     }
00033   }
00034 
00035   return;
00036 }
00037 
00038 
00039 BOOL
00040 LOCAL_CLSC::Aux_id_in_bs(AUX_ID aux_id, IDX_32_SET *bs)
00041 {
00042   IDX_32 bitpos=Get_bitpos(aux_id);
00043   if(bitpos!=ILLEGAL_BP) {
00044     if(bs->MemberP(bitpos))
00045       return TRUE;
00046   }
00047   return FALSE;     
00048 }
00049 
00050 BOOL
00051 LOCAL_CLSC:: Add_aux_id_to_bs(AUX_ID aux_id, IDX_32_SET *bs)
00052 {
00053   IDX_32 bitpos=Get_bitpos(aux_id);
00054   if(bitpos!=ILLEGAL_BP) {
00055     bs->Union1D(bitpos);
00056     return TRUE;
00057   }
00058   else
00059     return FALSE;
00060 }
00061 
00062 void
00063 LOCAL_CLSC::Get_aux_id_by_alias(AUX_ID aux_id, AUX_ID_LIST *alist)
00064 {
00065   const BS *alias_set = Opt_stab()->Indirect(); // all scalars + virtuals
00066   for (AUX_ID idx = BS_Choose( alias_set );
00067         idx != (AUX_ID) BS_CHOOSE_FAILURE;
00068         idx = BS_Choose_Next ( alias_set, idx )) {
00069 
00070         if (Opt_stab()->Rule()->Aliased_Memop(Opt_stab()->Aux_stab_entry(aux_id)->Points_to(), 
00071         Opt_stab()->Aux_stab_entry(idx)->Points_to())) 
00072           alist->New_aux_id_node(idx, Pool());
00073   }
00074   return;
00075 }
00076 
00077 void
00078 LOCAL_CLSC::Collect_def_by_chi_list(CHI_LIST *chi_list, IDX_32_SET *appear_set)
00079 {
00080   AUX_ID_LIST *alist=CXX_NEW(AUX_ID_LIST, Pool());
00081   alist->Clear();
00082   CHI_NODE *cnode;
00083   CHI_LIST_ITER chi_iter;
00084   FOR_ALL_NODE(cnode, chi_iter, Init(chi_list)) {
00085     if(cnode->Live()) {
00086       AUX_ID aux_id=cnode->Aux_id();
00087       alist->New_aux_id_node(aux_id, Pool());
00088       //deal with virtual variable
00089       AUX_STAB_ENTRY *sym=Opt_stab()->Aux_stab_entry(aux_id);
00090       if(sym->Is_virtual() && sym->Aux_id_list()!=NULL)
00091           Get_aux_id_by_alias(aux_id, alist);        
00092     }
00093   }
00094 
00095   if(!alist->Is_Empty()) {
00096     AUX_ID_LIST_ITER alist_iter;
00097     AUX_ID_NODE *a_node;
00098     FOR_ALL_ELEM(a_node, alist_iter, Init(alist)) {
00099       AUX_ID aux_id=a_node->Aux_id();
00100       Add_aux_id_to_bs(aux_id, appear_set);
00101     }          
00102   }
00103 
00104   CXX_DELETE(alist, Pool());      
00105   return;
00106 }
00107 
00108 void
00109 LOCAL_CLSC::Collect_def(CODEREP *cr, IDX_32_SET *appear_set, IDX_32_SET *def_set)
00110 {
00111   AUX_ID aux_id=cr->Aux_id();
00112   AUX_STAB_ENTRY *sym=Opt_stab()->Aux_stab_entry(aux_id);
00113   if(sym!=NULL && sym->St()!=NULL) {
00114     TY_IDX ty=ST_type(sym->St());
00115     if(TY_kind(ty)!=KIND_ARRAY && TY_kind(ty)!=KIND_STRUCT) {
00116       Add_aux_id_to_bs(aux_id, def_set);
00117       return;
00118     }
00119   }
00120   Add_aux_id_to_bs(aux_id, appear_set);
00121   return;
00122 }
00123 
00124 AUX_ID_LIST *
00125 LOCAL_CLSC::Get_use_by_mu_node(MU_NODE *mnode)
00126 {
00127   AUX_ID_LIST *alist=CXX_NEW(AUX_ID_LIST, Pool());
00128   alist->Clear();
00129  
00130   AUX_ID aux_id=mnode->Aux_id();
00131   alist->New_aux_id_node(aux_id, Pool());
00132   
00133   AUX_STAB_ENTRY *sym=Opt_stab()->Aux_stab_entry(aux_id);
00134   if(sym->Is_virtual()  && sym->Aux_id_list()!=NULL)
00135       Get_aux_id_by_alias(aux_id, alist);        
00136 
00137   return alist;
00138 }
00139 
00140 
00141 void
00142 LOCAL_CLSC::Collect_use_by_mu_node(MU_NODE *mnode, IDX_32_SET *upwd_set, IDX_32_SET *appear_set, IDX_32_SET *def_set)
00143 {
00144   AUX_ID_LIST *aux_id_list=Get_use_by_mu_node(mnode);
00145   if(!aux_id_list->Is_Empty()) {
00146     AUX_ID_LIST_ITER aux_id_list_iter;
00147     AUX_ID_NODE *aux_id_node;
00148     FOR_ALL_ELEM(aux_id_node, aux_id_list_iter, Init(aux_id_list)) {
00149       AUX_ID aux_id=aux_id_node->Aux_id();
00150       if(!Aux_id_in_bs(aux_id, def_set)) {
00151         Add_aux_id_to_bs(aux_id, upwd_set);
00152       } 
00153       else { 
00154         Add_aux_id_to_bs(aux_id, appear_set);
00155       }
00156     }
00157   }
00158   CXX_DELETE(aux_id_list, Pool());
00159   return;
00160 }
00161 
00162 void
00163 LOCAL_CLSC::Collect_use_rec(CODEREP *cr, IDX_32_SET *upwd_set, IDX_32_SET *appear_set, IDX_32_SET *def_set)
00164 {
00165   if(cr->Kind() == CK_VAR){
00166       AUX_ID aux_id=cr->Aux_id();
00167       if(!Aux_id_in_bs(aux_id, def_set))
00168         Add_aux_id_to_bs(aux_id, upwd_set);
00169       else
00170         Add_aux_id_to_bs(aux_id, appear_set);
00171   }
00172   else if(cr->Kind() == CK_IVAR){
00173     if(cr->Ilod_base())
00174       Collect_use_rec(cr->Ilod_base(), upwd_set, appear_set, def_set);
00175 
00176     MU_NODE *mnode=cr->Ivar_mu_node();    
00177     if(mnode!=NULL)
00178       Collect_use_by_mu_node(mnode, upwd_set, appear_set, def_set); 
00179   } else if(cr->Kind()==CK_OP) {
00180       //if  there is a call in parameter, the algorithm will fail, but in wopt, we assume this will not happen
00181       for (INT i=0; i< cr->Kid_count(); i++) {
00182         Collect_use_rec(cr->Opnd(i), upwd_set, appear_set, def_set);
00183       }
00184   }
00185   return;
00186 }
00187 
00188   //initialize the bs, then collect local info for each bb:  
00189   // 1) must def, saved in _loc_def
00190   // 2) upward exposed use, saved in _loc_upwd
00191   // 3) all the other appears (non-upwd uses, may def, mu, chi...) will be saved in _loc_appear
00192 void
00193 LOCAL_CLSC::Collect_local_refs(CFG *cfg)
00194 {
00195   CFG_ITER cfg_iter(cfg);
00196   BB_NODE *bb;
00197   FOR_ALL_NODE(bb, cfg_iter, Init()){
00198     bb->Set_loc_appear( CXX_NEW(IDX_32_SET(Bs_size(), Pool(), OPTS_FALSE), Pool()));
00199     bb->Set_loc_def( CXX_NEW(IDX_32_SET(Bs_size(), Pool(), OPTS_FALSE), Pool()));
00200     bb->Set_loc_upwd( CXX_NEW(IDX_32_SET(Bs_size(), Pool(), OPTS_FALSE), Pool()));
00201     bb->Set_live_out( CXX_NEW(IDX_32_SET(Bs_size(), Pool(), OPTS_FALSE), Pool()));
00202     bb->Set_live_at_exit( CXX_NEW(IDX_32_SET(Bs_size(), Pool(), OPTS_FALSE), Pool()));     //we use _live_at_exit to save live_in set for bb
00203   
00204     STMT_LIST *stmt_list = bb->Stmtlist();
00205     STMTREP_ITER  stmt_iter(stmt_list);
00206     STMTREP      *stmtrep;
00207     FOR_ALL_NODE(stmtrep, stmt_iter, Init()){
00208 
00209       //calculate upward exposed use and all the uses
00210       if(stmtrep->Rhs())
00211         Collect_use_rec(stmtrep->Rhs(), bb->Loc_upwd(), bb->Loc_appear(),bb->Loc_def()); 
00212 
00213       OPERATOR opr=stmtrep->Opr();
00214       if(opr==OPR_ISTORE || opr==OPR_ISTOREX || opr==OPR_STBITS || opr==OPR_MSTORE)
00215         Collect_use_rec(stmtrep->Lhs()->Istr_base(), bb->Loc_upwd(), bb->Loc_appear(), bb->Loc_def());
00216 
00217       if(stmtrep->Has_mu()) {
00218         MU_LIST *mu_list=stmtrep->Mu_list();
00219         if(mu_list!=NULL)  {
00220           MU_NODE *mnode;
00221           MU_LIST_ITER mu_iter;
00222           FOR_ALL_NODE(mnode, mu_iter, Init(mu_list))  {
00223             Collect_use_by_mu_node(mnode, bb->Loc_upwd(), bb->Loc_appear(), bb->Loc_def());
00224           }
00225         }
00226       }
00227 
00228       if(stmtrep->Opr()==OPR_STID) {
00229          Collect_def(stmtrep->Lhs(), bb->Loc_appear(), bb->Loc_def());
00230       }
00231 
00232       if(stmtrep->Has_chi()) {
00233         CHI_LIST *chi_list=stmtrep->Chi_list(); 
00234         //chi_list may be empty for STID,           
00235         FmtAssert((chi_list!=NULL||stmtrep->Opr()!=OPR_ISTORE), 
00236       ("LOCAL_CLSC::Collect_local_refs: empty chi_list for istore!\n"));
00237         if(chi_list!=NULL) {
00238           Collect_def_by_chi_list(chi_list, bb->Loc_appear());
00239         }
00240       }
00241     }
00242 
00243     bb->Loc_appear()->UnionD(bb->Loc_def());
00244     bb->Loc_appear()->UnionD(bb->Loc_upwd());
00245 
00246     if(Tracing()) {
00247       fprintf(TFile, "dump local references for bb %d: \n", bb->Id());
00248       fprintf( TFile, "kill def: ");
00249       bb->Loc_def()->Print(TFile);
00250       fprintf( TFile, "\n" );
00251       fprintf( TFile, " upwd: ");
00252       bb->Loc_upwd()->Print(TFile);
00253       fprintf( TFile, "\n" );      
00254       fprintf( TFile, "appear: ");
00255       bb->Loc_appear()->Print(TFile);
00256       fprintf( TFile, "\n" );
00257     }
00258   }
00259   return;
00260 }
00261 
00262   //calculate data flow equation, backward
00263   // 1) initialize:  _live_out(exit_bb) = empty
00264   // 2) propagation equation: _live_out(bb) = union of _live_in(succs)
00265   //            _live_in(bb) = live_out(bb) - _loc_def(bb) + _loc_upwd(bb)  
00266   //            In the above equation, the order must be kept.
00267   // 3) live range calculation equation:
00268   //            liveness(var) = union of bbs in which var is in _live_in, _live_out,  _loc_appear
00269 void
00270 LOCAL_CLSC::Calculate_liveness(CFG *cfg)
00271 {
00272   BOOL change=TRUE;
00273   IDX_32_SET save_lo_set(Bs_size(), Pool(), OPTS_FALSE);
00274   IDX_32_SET save_lae_set(Bs_size(), Pool(), OPTS_FALSE);
00275   
00276   while(change) {
00277     change=FALSE;
00278 
00279     BB_NODE *bb;
00280     POBB_ITER cfg_iter(cfg);
00281     FOR_ALL_ELEM(bb, cfg_iter, Init()) {
00282       save_lo_set.CopyD(bb->Live_out());
00283       save_lae_set.CopyD(bb->Live_at_exit());
00284    
00285       BB_NODE *succ;
00286       BB_LIST_ITER bb_succ_iter;
00287       FOR_ALL_ELEM( succ, bb_succ_iter, Init(bb->Succ()) )     
00288         bb->Live_out()->UnionD(succ->Live_at_exit());
00289 
00290       bb->Live_at_exit()->UnionD(bb->Live_out());
00291       bb->Live_at_exit()->DifferenceD(bb->Loc_def());
00292       bb->Live_at_exit()->UnionD(bb->Loc_upwd());
00293 
00294       if((!save_lo_set.EqualP( bb->Live_out() )) || (!save_lae_set.EqualP(bb->Live_at_exit())))
00295         change=TRUE;
00296     }
00297   }
00298 
00299   if(Tracing()) {
00300     fprintf(TFile, "dump liveness:\n");
00301     BB_NODE *bb;
00302     POBB_ITER cfg_iter(cfg);
00303     FOR_ALL_ELEM(bb, cfg_iter, Init()) {
00304       fprintf(TFile, "for bb %d: \n", bb->Id());
00305       fprintf( TFile, "live in: ");
00306       bb->Live_at_exit()->Print(TFile);
00307       fprintf( TFile, "\n" );     
00308       fprintf( TFile, "live out: ");
00309       bb->Live_out()->Print(TFile);
00310       fprintf( TFile, "\n" );     
00311       fprintf(TFile, "appear:");
00312       bb->Loc_appear()->Print(TFile);
00313       fprintf( TFile, "\n" );
00314     }
00315   }
00316 
00317   return;
00318 }
00319 
00320   //calculate live ranges for each local variable
00321   // live_range(var) = union of bbs in which var was included in  _live_in(bb) or live_out(bb) or appear
00322 void
00323 LOCAL_CLSC::Get_lr(CFG *cfg)
00324 {
00325   //create LOCAL CLSC candidate
00326   STBP_MAP::iterator mitr=_bp_map.begin();
00327   STBP_MAP::iterator mitrn=_bp_map.end();
00328   while(mitr!=mitrn) {
00329     ST* st=(*mitr).first;
00330     IDX_32 bp=(*mitr).second;
00331     Add_node(st,cfg);
00332     mitr++;
00333   }
00334   //calculate live range
00335   DFSBB_ITER cfg_iter(cfg);
00336   BB_NODE *bb;
00337   FOR_ALL_ELEM(bb, cfg_iter, Init()){  
00338     if (bb->Kind() != BB_ENTRY) {
00339       IDX_32_SET *bs=CXX_NEW(IDX_32_SET(Bs_size(), Pool(), OPTS_FALSE), Pool());
00340 
00341       bs->UnionD(bb->Loc_appear());
00342       bs->UnionD(bb->Live_at_exit());
00343       bs->UnionD(bb->Live_out());
00344  
00345       LCLSC_NTAB::iterator vitr=_clsc_ntab.begin();
00346       LCLSC_NTAB::iterator vitrn=_clsc_ntab.end();
00347       while(vitr!=vitrn) {
00348         LCLSC_NODE *node=*vitr;
00349         IDX_32 bp=Get_bitpos(node->Get_st());
00350         if(bs->MemberP(bp))
00351           node->Get_lr()->Union1D(bb);
00352         vitr++;
00353       }
00354     }
00355   }
00356 
00357   if(Tracing()) {
00358     fprintf(TFile, "dump live range:\n");
00359     fprintf(TFile, "before remove fake entry live range\n");
00360     LCLSC_NTAB::iterator vitr=_clsc_ntab.begin();
00361     LCLSC_NTAB::iterator vitrn=_clsc_ntab.end();
00362     while(vitr!=vitrn) {
00363       LCLSC_NODE *node=*vitr;
00364       node->Print(TFile);
00365       vitr++;
00366     }    
00367   }
00368 
00369   //shrink to remove the fake live range before the first appearance of st
00370   BOOL change=TRUE;
00371   IDX_32_SET save_appear_set(Bs_size(), Pool(), OPTS_FALSE);
00372   while(change) {
00373     change=FALSE;
00374 
00375     FOR_ALL_ELEM(bb, cfg_iter, Init()) {
00376       if(bb->Kind() == BB_ENTRY) {
00377         bb->Loc_appear()->ClearD();
00378       }
00379 
00380       save_appear_set.CopyD(bb->Loc_appear());
00381 
00382       BB_NODE *pred;
00383       BB_LIST_ITER bb_pred_iter;
00384       FOR_ALL_ELEM( pred, bb_pred_iter, Init(bb->Pred()) )
00385         bb->Loc_appear()->UnionD(pred->Loc_appear());
00386 
00387       if((!save_appear_set.EqualP( bb->Loc_appear() )))
00388         change=TRUE;
00389     }
00390   }
00391 
00392   FOR_ALL_ELEM(bb, cfg_iter, Init()){
00393       LCLSC_NTAB::iterator vitr=_clsc_ntab.begin();
00394       LCLSC_NTAB::iterator vitrn=_clsc_ntab.end();
00395       while(vitr!=vitrn) {
00396         LCLSC_NODE *node=*vitr;
00397         IDX_32 bp=Get_bitpos(node->Get_st());
00398         if(!bb->Loc_appear()->MemberP(bp))
00399           node->Get_lr()->Difference1D(bb);
00400         vitr++;
00401       }
00402   }
00403   
00404 
00405 
00406   //reset bs in bb node of cfg to NULL, they will be freed after mem pool pop
00407 
00408   FOR_ALL_ELEM(bb, cfg_iter, Init()){
00409     bb->Set_loc_def( NULL );
00410     bb->Set_loc_upwd( NULL );
00411     bb->Set_loc_appear(NULL);
00412     bb->Set_live_at_exit(NULL);
00413     bb->Set_live_out(NULL);
00414   }
00415 
00416   if(Tracing()) {
00417     fprintf(TFile, "after remove fake entry live range\n");
00418     LCLSC_NTAB::iterator vitr=_clsc_ntab.begin();
00419     LCLSC_NTAB::iterator vitrn=_clsc_ntab.end();
00420     while(vitr!=vitrn) {
00421       LCLSC_NODE *node=*vitr;
00422       node->Print(TFile);
00423       vitr++;
00424     }    
00425   }
00426   return;
00427 }
00428 
00429 BOOL 
00430 LOCAL_CLSC::LR_overlapped(BB_NODE_SET *lr0, BB_NODE_SET *lr1, CFG *cfg)
00431 {
00432   if(lr0==lr1)
00433     return TRUE;
00434   
00435   BB_NODE_SET *bs0=CXX_NEW(BB_NODE_SET(cfg->Total_bb_count(), cfg, Pool(), BBNS_EMPTY), Pool());
00436   BB_NODE_SET *bs1=CXX_NEW(BB_NODE_SET(cfg->Total_bb_count(), cfg, Pool(), BBNS_EMPTY), Pool());
00437   bs0->CopyD(lr0);
00438   bs1->CopyD(lr1);
00439   if(bs0->IntersectionD(bs1)->EmptyP())
00440     return FALSE;
00441   else 
00442     return TRUE;
00443 }
00444 
00445 void
00446 LOCAL_CLSC::Update_cr_alias(POINTS_TO *pt0, POINTS_TO *pt1, CODEREP *cr, OPT_STAB *opt_stab)
00447 {
00448   CODEKIND ck=cr->Kind();
00449   if(ck==CK_IVAR || ck==CK_VAR) {
00450     POINTS_TO *pt=cr->Points_to(opt_stab);
00451     if(pt!=NULL) {
00452       BOOL aliased=FALSE;
00453       if(opt_stab->Rule()->Aliased_Memop(pt,pt0)) {
00454         pt->Meet(pt1, NULL);
00455       }
00456 
00457       if(opt_stab->Rule()->Aliased_Memop(pt,pt1)) {
00458         pt->Meet(pt0, NULL);
00459       }
00460     }
00461 
00462     if(ck==CK_IVAR) 
00463       if(cr->Ilod_base())
00464         Update_cr_alias(pt0, pt1, cr->Ilod_base(), opt_stab);
00465     
00466   }else if(ck==CK_OP) {
00467       for (INT i=0; i< cr->Kid_count(); i++) 
00468         Update_cr_alias(pt0, pt1, cr->Opnd(i), opt_stab);
00469   }
00470   
00471   return;
00472 }
00473 
00474 void
00475 LOCAL_CLSC::Update_alias(ST *st0, ST *st1, CFG *cfg, OPT_STAB *opt_stab)
00476 {
00477   //update the points_to
00478   //the st_group need not to be updated since the alias info has been updated?
00479   POINTS_TO pt0, pt1;
00480   TY_IDX ty0 = ST_type (st0);
00481   pt0.Analyze_ST(st0, 0, TY_size(ty0), 0, 0, ty0, TRUE/*has equiv*/);
00482   pt0.Set_alias_class(PESSIMISTIC_AC_ID);
00483   
00484   TY_IDX ty1 = ST_type (st1);
00485   pt1.Analyze_ST(st1, 0, TY_size(ty1), 0, 0, ty1, TRUE/*has equiv*/);
00486   pt1.Set_alias_class(PESSIMISTIC_AC_ID);
00487   
00488   AUX_ID i;
00489   AUX_STAB_ITER aux_stab_iter(opt_stab);
00490   FOR_ALL_NODE(i, aux_stab_iter, Init()) {
00491   
00492     AUX_STAB_ENTRY *sym = opt_stab->Aux_stab_entry(i);
00493     ST *st=sym->St();
00494     if(st==st0) {
00495       POINTS_TO *pt=sym->Points_to();
00496       pt->Meet(&pt1, NULL);    
00497     }
00498     else if(st==st1) {
00499       POINTS_TO *pt=sym->Points_to();
00500       pt->Meet(&pt0, NULL);    
00501     }
00502   }
00503 
00504   //update the points_to
00505   CFG_ITER cfg_iter(cfg);
00506   BB_NODE *bb;
00507   FOR_ALL_NODE(bb, cfg_iter, Init()){
00508   
00509     STMT_LIST *stmt_list = bb->Stmtlist();
00510     STMTREP_ITER  stmt_iter(stmt_list);
00511     STMTREP      *stmtrep;
00512     FOR_ALL_NODE(stmtrep, stmt_iter, Init()){
00513 
00514       OPERATOR opr=stmtrep->Opr();
00515       if(opr==OPR_ISTORE || opr==OPR_ISTBITS || opr==OPR_ISTOREX || opr==OPR_MSTORE ) {
00516         Update_cr_alias(&pt0, &pt1, stmtrep->Lhs(), opt_stab);
00517       }
00518           
00519       if(stmtrep->Rhs()) {
00520         Update_cr_alias(&pt0, &pt1, stmtrep->Rhs(), opt_stab);
00521       }
00522           
00523       if(OPERATOR_is_store(opr))  {
00524         POINTS_TO *pt=stmtrep->Lhs()->Points_to(opt_stab);
00525         if(opt_stab->Rule()->Aliased_Memop(pt,&pt0))
00526           pt->Meet(&pt1, NULL);
00527         if(opt_stab->Rule()->Aliased_Memop(pt,&pt1))
00528           pt->Meet(&pt0, NULL);
00529       }
00530     }
00531   }
00532 
00533   return;
00534 }
00535 
00536 void
00537 LOCAL_CLSC::Perform_clsc(CFG *cfg)
00538 {
00539 
00540   typedef map<LCLSC_NODE*, BB_NODE_SET*> LR_MAP;
00541   typedef vector<LCLSC_NODE*> LN_CLASS;
00542   typedef map<LCLSC_NODE*, LN_CLASS*> LS_MAP;
00543 
00544   LR_MAP lr_map;  //the map from local variable to live range
00545   LS_MAP lc_map;  //the map from local variable to the set of variables sharing the same stack location
00546 
00547   //initialize lr_map and lc_map
00548   for(LCLSC_NTAB::iterator vitr0=_clsc_ntab.begin(); vitr0!=_clsc_ntab.end();vitr0++) {
00549     LCLSC_NODE *node=*vitr0;
00550     if(node->Get_lr()->EmptyP()) 
00551       continue;
00552 
00553     BB_NODE_SET *lcr=CXX_NEW(BB_NODE_SET(cfg->Total_bb_count(), cfg, Pool(), BBNS_EMPTY), Pool());
00554     lcr->CopyD(node->Get_lr());
00555     lr_map[node]=lcr;
00556 
00557     LN_CLASS *lnc=new LN_CLASS;
00558     lnc->push_back(node);
00559     lc_map[node]=lnc;
00560   }
00561 
00562   //perform coalescing  
00563   for(LCLSC_NTAB::iterator vitr0=_clsc_ntab.begin(); vitr0!=_clsc_ntab.end();vitr0++)  {
00564     LCLSC_NODE *node0=*vitr0;
00565     BB_NODE_SET *lr0=node0->Get_lr();
00566     if(lr0->EmptyP()) 
00567       continue;
00568 
00569     BB_NODE_SET *lcr0=lr_map[node0];
00570 
00571     for(LCLSC_NTAB::iterator vitr1=vitr0+1; vitr1!=_clsc_ntab.end();vitr1++) {
00572       LCLSC_NODE *node1=*vitr1;
00573       BB_NODE_SET *lr1=node1->Get_lr();
00574       if(lr1->EmptyP()) 
00575         continue;
00576 
00577       BB_NODE_SET *lcr1=lr_map[node1];
00578 
00579       if(!LR_overlapped(lcr0, lcr1,cfg)) {
00580         ST *st0=node0->Get_st();
00581         ST* st1=node1->Get_st();
00582         TY_IDX ty0=ST_type(st0);
00583         TY_IDX ty1=ST_type(st1);
00584 
00585         if(TY_size(ty0)==TY_size(ty1)) {
00586 //        if(ty0==ty1) {
00587 
00588           if(Tracing()) {
00589             fprintf(TFile, "union %s and %s, size reduction: %d\n", ST_name(st0),ST_name(st1), TY_size(ty0));
00590           }
00591 
00592           //create common st base block for st0 and st1
00593           St_Block_Union(st0, st1);
00594 
00595           //merge live range and update lr_map
00596           lcr0->UnionD(lcr1);
00597           lr_map[node1]=lcr0;
00598 
00599           //update alias info for all the symble related, first st0 and st1, then st0 class and st1 class
00600           Update_alias(st0, st1,Cfg(), Opt_stab());
00601           
00602           LN_CLASS *lnc0=lc_map[node0];
00603           LN_CLASS *lnc1=lc_map[node1];
00604           FmtAssert(lnc0!=lnc1, ("LOCAL_CLSC::Perform_clse, merged two node have the same class"));
00605           for(LN_CLASS::iterator lnitr0=lnc0->begin();lnitr0!=lnc0->end();lnitr0++) {
00606             for(LN_CLASS::iterator lnitr1=lnc1->begin();lnitr1!=lnc1->end();lnitr1++) {
00607               LCLSC_NODE *ln0=*lnitr0;
00608               LCLSC_NODE *ln1=*lnitr1;
00609               FmtAssert(ln0!=ln1, ("LOCAL_CLSC::Perform_clsc, merged two set have common member"));
00610               Update_alias(ln0->Get_st(), ln1->Get_st(), cfg, Opt_stab());
00611             }
00612           }
00613 
00614           //update ls_map
00615           lnc0->insert(lnc0->end(), lnc1->begin(), lnc1->end());
00616           lc_map[node1]=lnc0;
00617         } 
00618       }
00619     }
00620   }
00621   return;
00622 }
00623 
00624 void
00625 LOCAL_CLSC:: Do_local_clsc()
00626 {
00627   if(Tracing()) {
00628     fprintf(TFile, "%sBefore LOCAL CLSC\n%s", DBar, DBar);
00629     Cfg()->Print(TFile);
00630   }
00631   OPT_POOL_Initialize(Pool(), "LOCAL CLSC  pool", FALSE, LCLSC_TRACE_FLAG);
00632   OPT_POOL_Push( Pool(), LCLSC_TRACE_FLAG);
00633   //calculate the total bits needed for all the local variables and
00634   //initialize the _bp_map between aux_id of local variabls and bit position
00635   Init_bp_map(Opt_stab());
00636 
00637   //initialize the bs, then collect local info for each bb:  
00638   Collect_local_refs(Cfg());
00639 
00640   //calculate data flow equation, backward
00641   Calculate_liveness(Cfg());
00642 
00643   //calculate live ranges for each local variable
00644   Get_lr(Cfg());
00645 
00646   //union the basic st of two vars whose live ranges are not overlap and fix alias info
00647   Perform_clsc(Cfg());
00648 
00649   OPT_POOL_Pop( Pool(), LCLSC_TRACE_FLAG );
00650   OPT_POOL_Delete( Pool(), LCLSC_TRACE_FLAG);
00651   
00652   if(Tracing()) {
00653     fprintf(TFile, "%sAfter LOCAL CLSC\n%s", DBar, DBar);
00654     Cfg()->Print(TFile);
00655   }
00656 
00657   return;
00658 }