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

00001 //-*-c++-*-
00002 
00003 /*
00004  * Copyright 2004, 2005, 2006 PathScale, Inc.  All Rights Reserved.
00005  */
00006 
00007 // ====================================================================
00008 // ====================================================================
00009 //
00010 // Module: opt_speculate.h
00011 // $Revision: 1.1.1.1 $
00012 // $Date: 2005/10/21 19:00:00 $
00013 // $Author: marcel $
00014 // $Source: /proj/osprey/CVS/open64/osprey1.0/be/opt/opt_speculate.cxx,v $
00015 //
00016 // ====================================================================
00017 //
00018 // Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.
00019 //
00020 // This program is free software; you can redistribute it and/or modify
00021 // it under the terms of version 2 of the GNU General Public License as
00022 // published by the Free Software Foundation.
00023 //
00024 // This program is distributed in the hope that it would be useful, but
00025 // WITHOUT ANY WARRANTY; without even the implied warranty of
00026 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00027 //
00028 // Further, this software is distributed without any warranty that it
00029 // is free of the rightful claim of any third person regarding
00030 // infringement  or the like.  Any license provided herein, whether
00031 // implied or otherwise, applies only to this software file.  Patent
00032 // licenses, if any, provided herein do not apply to combinations of
00033 // this program with other software, or any other product whatsoever.
00034 //
00035 // You should have received a copy of the GNU General Public License
00036 // along with this program; if not, write the Free Software Foundation,
00037 // Inc., 59 Temple Place - Suite 330, Boston MA 02111-1307, USA.
00038 //
00039 // Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
00040 // Mountain View, CA 94043, or:
00041 //
00042 // http://www.sgi.com
00043 //
00044 // For further information regarding this notice, see:
00045 //
00046 // http://oss.sgi.com/projects/GenInfo/NoticeExplan
00047 //
00048 // ====================================================================
00049 // ====================================================================
00050 
00051 
00052 #define USE_STANDARD_TYPES
00053 
00054 #include "defs.h"
00055 #include "config_wopt.h"
00056 #include "opt_etable.h"
00057 #include <algorithm>
00058 #include <vector>
00059 #include "connected_components.h"
00060 
00061 using SGI::find_representative_and_compress_path;
00062 using SGI::connect_components;
00063 using SGI::extend_components_and_ranks;
00064 
00065 void
00066 EXP_WORKLST::Save_flags()
00067 {
00068   EXP_OCCURS_ITER phi_occ_iter(Phi_occurs().Head());
00069   EXP_OCCURS *occur;
00070   FOR_ALL_NODE(occur, phi_occ_iter, Init()) {
00071     occur->Exp_phi()->Save_flags();
00072     occur->Save_flags();
00073   }
00074   EXP_OCCURS_ITER real_occ_iter(Real_occurs().Head());
00075   FOR_ALL_NODE(occur, real_occ_iter, Init()) {
00076     occur->Save_flags();
00077   }
00078   EXP_OCCURS_ITER phi_pred_occ_iter(Phi_pred_occurs().Head());
00079   FOR_ALL_NODE(occur, phi_pred_occ_iter, Init()) {
00080     occur->Save_flags();
00081   }
00082 }
00083 
00084 
00085 void
00086 EXP_WORKLST::Estimate_cost(ETABLE *etable, PRE_KIND pre_kind)
00087 {
00088   const char *note = pre_kind_name(pre_kind);
00089 
00090   EXP_OCCURS_ITER phi_occ_iter(Phi_occurs().Head());
00091   EXP_OCCURS_ITER real_occ_iter(Real_occurs().Head());
00092   EXP_OCCURS *occur;
00093 
00094   // Assign a unique ID to each phi node.
00095   // Keep a mapping from e_version to EXP_OCCURS of phi.
00096   // Ignore phi nodes that are not partial avail.
00097   // All phi node are assumed to be partial anticipated.
00098   //
00099   INT32 phi_count = 0;
00100   vector<EXP_OCCURS *> e_version_table;
00101   e_version_table.insert(e_version_table.end(), Cur_e_version(), (EXP_OCCURS*)NULL);
00102   FOR_ALL_NODE(occur, phi_occ_iter, Init()) {
00103     occur->Exp_phi()->id = phi_count++;
00104     if (occur->Exp_phi()->Partial_avail())
00105       e_version_table[occur->E_version()] = occur;
00106   }
00107 
00108   // Put connected phi's into the same component.
00109   // component is indexed by phi-id
00110   vector<int> component;
00111   {
00112     vector<unsigned char> rank;
00113     extend_components_and_ranks(component, rank, phi_count - 1);
00114     FOR_ALL_NODE(occur, phi_occ_iter, Init()) {
00115       EXP_PHI *phi = occur->Exp_phi();
00116       if (e_version_table[occur->E_version()] == NULL) continue;
00117       Is_True(phi->Partial_avail(), ("Estimate_cost: phi is not partial avail."));
00118       for (int i = 0; i < phi->Opnd_count(); ++i) {
00119   if (phi->Opnd(i) == NULL) continue;
00120   EXP_OCCURS *opnd_occ = e_version_table[phi->Opnd(i)->E_version()];
00121   if (opnd_occ == NULL) continue;
00122   Is_True(opnd_occ->Exp_phi()->Partial_avail(), 
00123     ("Estimate_cost: phi is not partial avail."));
00124   connect_components(component.begin(),
00125          rank,
00126          phi->id,
00127          opnd_occ->Exp_phi()->id);
00128       }
00129     }
00130     for (int i = 0; i < component.size(); ++i)
00131       find_representative_and_compress_path(component.begin(), i);
00132   }
00133 
00134 #ifdef Is_True_On
00135   // Verify that every non-empty component has at least one real occ.
00136   {
00137     vector<bool> component_has_real_occ;
00138     component_has_real_occ.insert(component_has_real_occ.end(), component.size(), 0);
00139     
00140     FOR_ALL_NODE(occur, real_occ_iter, Init()) {
00141       EXP_OCCURS *phi_occ = e_version_table[occur->E_version()];
00142       if (phi_occ != NULL) {
00143   int equiv_class = component[phi_occ->Exp_phi()->id];
00144   component_has_real_occ[equiv_class] = 1;
00145       }
00146     }
00147 
00148     FOR_ALL_NODE(occur, phi_occ_iter, Init()) {
00149       EXP_PHI *phi = occur->Exp_phi();
00150       if (e_version_table[occur->E_version()] == NULL) continue;
00151       int equiv_class = component[phi->id];
00152       FmtAssert(component_has_real_occ[equiv_class], 
00153     ("Estimate_cost: equiv class %d has no real occ.", equiv_class));
00154     }
00155   }
00156 #endif
00157 
00158   // Count the number of real occurrence for each connect components
00159   // Note: real occurrence not defined by any phi are ignored.
00160   vector<int> original_count;
00161   original_count.insert(original_count.end(), component.size(), 0);
00162 
00163   FOR_ALL_NODE(occur, real_occ_iter, Init()) {
00164     if (occur->Occurs_as_lvalue()) continue;
00165     EXP_OCCURS *phi_occ = e_version_table[occur->E_version()];
00166     if (phi_occ == NULL) continue;
00167     int freq = occur->Stmt()->Bb()->Freq();  
00168     int equiv_class = component[phi_occ->Exp_phi()->id];
00169     original_count[equiv_class] += freq;
00170   }
00171   
00172   // Count the number of computation after PRE, i.e.,
00173   //  the number of real occurrence not deleted +
00174   //  the number of inserted occurrence
00175   // Note: real occurrence not connect with any phi are ignored.
00176   vector<int> PRE_count;
00177   PRE_count.insert(PRE_count.end(), component.size(), 0);
00178 
00179   FOR_ALL_NODE(occur, real_occ_iter, Init()) {
00180     if (occur->Occurs_as_lvalue()) continue;
00181     if (occur->Delete_comp()) continue;
00182     EXP_OCCURS *phi_occ = e_version_table[occur->E_version()];
00183     if (phi_occ == NULL) continue;
00184     int freq = occur->Stmt()->Bb()->Freq();  
00185     int equiv_class = component[phi_occ->Exp_phi()->id];
00186     PRE_count[equiv_class] += freq;
00187   }
00188 
00189   FOR_ALL_NODE(occur, phi_occ_iter, Init()) {
00190     if (e_version_table[occur->E_version()] == NULL) continue;
00191     EXP_PHI *phi = occur->Exp_phi();
00192     int equiv_class = component[phi->id];
00193 
00194     if (phi->Will_b_avail()) {
00195       for (int i = 0; i < phi->Opnd_count(); ++i) {
00196   if (phi->Need_insertion(i)) {
00197     int freq = occur->Exp_phi()->Bb()->Nth_pred(i)->Freq();
00198     PRE_count[equiv_class] += freq;
00199   }
00200       }
00201     }
00202   }
00203 
00204   // Count the number of computation after speculative PRE, i.e.,
00205   //  the number of real occurrence not deleted by spec-PRE,
00206   //  the number of inserted occurrence by spec-PRE
00207   // Note: real occurrence not connect with any phi are ignored.
00208   vector<int> FB_PRE_count;
00209   FB_PRE_count.insert(FB_PRE_count.end(), component.size(), 0);
00210 
00211   FOR_ALL_NODE(occur, phi_occ_iter, Init()) {
00212     if (e_version_table[occur->E_version()] == NULL) continue;
00213     EXP_PHI *phi = occur->Exp_phi();
00214     int equiv_class = component[phi->id];
00215 
00216     for (int i = 0; i < phi->Opnd_count(); ++i) {
00217       if (phi->Has_real_occ(i)) continue;
00218       if (phi->Opnd(i) == NULL ||
00219     (phi->Will_b_avail() && phi->Need_insertion(i)) ||
00220     (phi->Opnd(i)->Occ_kind() == EXP_OCCURS::OCC_PHI_OCCUR &&
00221      e_version_table[phi->Opnd(i)->E_version()] == NULL)) {
00222   int freq = occur->Exp_phi()->Bb()->Nth_pred(i)->Freq();
00223   FB_PRE_count[equiv_class] += freq;
00224       }
00225     }
00226   }
00227 
00228   
00229   // restore flags
00230   FOR_ALL_NODE(occur, phi_occ_iter, Init()) {
00231     EXP_PHI *phi = occur->Exp_phi();
00232     phi->Set_uses(NULL);
00233     for (int i = 0; i < phi->Opnd_count(); ++i) {
00234       if (phi->Opnd(i) != NULL &&
00235     phi->Opnd(i)->Inserted_computation()) {
00236   fprintf(TFile, "%s: reset phi (ver=%d) opnd %d\n",
00237     note,
00238     occur->E_version(), i);
00239   phi->Set_opnd(i, e_version_table[phi->Opnd(i)->E_version()]);
00240       }
00241     }
00242   }
00243 
00244   // Update DownSafety
00245   FOR_ALL_NODE(occur, phi_occ_iter, Init()) {
00246     occur->Exp_phi()->Restore_flags();
00247     int equiv_class = component[occur->Exp_phi()->id]; 
00248     if (FB_PRE_count[equiv_class] < PRE_count[equiv_class]) 
00249       occur->Exp_phi()->Reset_not_down_safe();
00250   }
00251 
00252   FOR_ALL_NODE(occur, real_occ_iter, Init()) {
00253     occur->Restore_flags();
00254   }
00255   
00256   EXP_OCCURS_ITER phi_pred_occ_iter(Phi_pred_occurs().Head());
00257   FOR_ALL_NODE(occur, phi_pred_occ_iter, Init()) {
00258     occur->Restore_flags();
00259   }
00260 
00261   if (Get_Trace(TP_WOPT2, FB_PRE_FLAG)) {
00262     fprintf(TFile, "==== Estimate cost ====\n");
00263 #ifdef KEY /* Mac port */
00264     fprintf(TFile, " num components=%ld\n", (long) component.size());
00265 #else /* KEY Mac port */
00266     fprintf(TFile, " num components=%d\n", (INT)component.size());
00267 #endif /* KEY Mac port */
00268     for (int i = 0; i < component.size(); ++i) {
00269       if (original_count[i] > 0) {
00270   fprintf(TFile, "%s: enum=%d %s=%lld no_opt=%d pre=%d fb_pre=%d\n",
00271     note,
00272     E_num(),
00273     (Exp()->Kind() == CK_CONST) ? "const" : 
00274     ((Exp()->Kind() == CK_VAR) ? "sym" : "symconst"),
00275     (Exp()->Kind() == CK_CONST) ? Exp()->Const_val() :
00276     (INT64)((Exp()->Kind() == CK_VAR) ? Exp()->Aux_id() : 0),
00277     original_count[i],
00278     PRE_count[i],
00279     FB_PRE_count[i]);
00280       }
00281     }
00282   }
00283 }
00284