Open64: osprey/ipa/main/optimize/ipo

00001 /*
00002  * Copyright 2003, 2004, 2005, 2006 PathScale, Inc.  All Rights Reserved.
00003  */
00004 
00005 /*
00006 
00007   Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.
00008 
00009   This program is free software; you can redistribute it and/or modify it
00010   under the terms of version 2 of the GNU General Public License as
00011   published by the Free Software Foundation.
00012 
00013   This program is distributed in the hope that it would be useful, but
00014   WITHOUT ANY WARRANTY; without even the implied warranty of
00015   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
00016 
00017   Further, this software is distributed without any warranty that it is
00018   free of the rightful claim of any third person regarding infringement 
00019   or the like.  Any license provided herein, whether implied or 
00020   otherwise, applies only to this software file.  Patent licenses, if 
00021   any, provided herein do not apply to combinations of this program with 
00022   other software, or any other product whatsoever.  
00023 
00024   You should have received a copy of the GNU General Public License along
00025   with this program; if not, write the Free Software Foundation, Inc., 59
00026   Temple Place - Suite 330, Boston MA 02111-1307, USA.
00027 
00028   Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
00029   Mountain View, CA 94043, or:
00030 
00031   http://www.sgi.com
00032 
00033   For further information regarding this notice, see:
00034 
00035   http://oss.sgi.com/projects/GenInfo/NoticeExplan
00036 
00037 */
00038 
00039 
00040 /* -*-Mode: c++;-*- (Tell emacs to use c++ mode) */
00041 // ====================================================================
00042 // ====================================================================
00043 //
00044 // $Revision: 1.1.1.1 $
00045 // $Date: 2005/10/21 19:00:00 $
00046 // $Author: marcel $
00047 // $Source: /proj/osprey/CVS/open64/osprey1.0/ipa/main/optimize/ipo_pad.cxx,v $
00048 //
00049 // Revision history:
00050 //  2-May-98 - Original Version
00051 //
00052 // Description:
00053 //
00054 // Implementation of the utilities necessary to pad array
00055 // columns to avoid cash-thrashing whenever possible.
00056 //
00057 // ====================================================================
00058 // ====================================================================
00059 
00060 #define __STDC_LIMIT_MACROS
00061 #include <stdint.h>
00062 #if defined(BUILD_OS_DARWIN)
00063 #include <darwin_elf.h>
00064 #else /* defined(BUILD_OS_DARWIN) */
00065 #include <elf.h>
00066 #endif /* defined(BUILD_OS_DARWIN) */
00067 #include <assert.h>   // for assert()
00068 #include <cmplrs/host.h>        // for ipc_ld.h
00069 #define USE_STANDARD_TYPES      /* override unwanted defines in defs.h */
00070 
00071 #include "defs.h"
00072 #include "stab.h"   // symtab stuff
00073 #include "mempool.h"    // for MEM_POOL
00074 #include "cxx_template.h" // DYN_ARRAY<T>
00075 #include "tracing.h"    // for TFile
00076 #include "dwarf_DST_mem.h"  // for ipc_file.h
00077 #include "mtypes.h"   // for ipc_file.h
00078 #include "const.h"
00079 #include "irbdata.h"
00080 #include "ipc_file.h"   // for ipa_inline.h
00081 #include "ipa_option.h"   // for Trace_IPA
00082 #include "ipa_pad.h"      // for COMMON_SNODE
00083 #include "ipo_main.h"   // for IPO_Gprel_Sym_Count
00084 #include "ipa_cg.h"             // call graph
00085 #include "ir_reader.h"          // dump tree
00086 #define MAX_ALIGN 16
00087 
00088 static
00089 BOOL trace_split_common = FALSE;
00090 //=================================================================
00091 // DESCR: Add_Element
00092 //        Enter and element into the array
00093 //=================================================================
00094 void 
00095 Add_Element_ST_TO_FLD_MAP(FLD_HANDLE fld, ST* s, 
00096         ST_TO_FLD_MAP_ARRAY& st_to_fld_map)
00097 {
00098   INT idx = st_to_fld_map.Newidx();
00099   ST_TO_FLD_MAP *entry = &(st_to_fld_map)[idx];
00100   entry->Init(fld, s);
00101 }
00102 
00103 //=================================================================
00104 // DESCR: Create
00105 // For each ST in the symbol-table, based at the given base,
00106 // match it up with the corresponding field in the base.
00107 //=================================================================
00108 void
00109 Create_ST_TO_FLD_MAP(COMMON_SNODE_TBL* common_snode_tbl)
00110 {
00111   ST* st;
00112   INT i;
00113   FOREACH_SYMBOL(GLOBAL_SYMTAB, st, i) {
00114 
00115     if (Is_Common_Based_Symbol(st)) {
00116 
00117       ST* common_st = ST_base(st);
00118       COMMON_SNODE_LIST* common_snode_list = 
00119         common_snode_tbl->Find(ST_name_idx(common_st));
00120       Is_True(common_snode_list, ("NULL common list in Create_ST_TO_FLD_MAP"));
00121 
00122       if (!common_snode_list->No_Pad()) {
00123 
00124         ST_TO_FLD_MAP_ARRAY* st_to_fld_map = common_snode_list->Get_Map();
00125         Is_True(st_to_fld_map, ("NULL fld map list in Create_ST_TO_FLD_MAP"));
00126       
00127         BOOL done = FALSE;
00128         FLD_ITER fld_iter= Make_fld_iter(TY_fld(Ty_Table[ST_type(common_st)]));
00129         do {
00130           FLD_HANDLE fld (fld_iter);
00131           if (FLD_ofst(fld) == ST_ofst(st) && FLD_type(fld) == ST_type(st)) {
00132             INT idx = st_to_fld_map->Newidx();
00133             ST_TO_FLD_MAP  *item = &(*st_to_fld_map)[idx];
00134             item->Init(fld,st);
00135             done = TRUE;
00136           }
00137         } while (!FLD_last_field(fld_iter++) && !done);
00138 
00139         Is_True(done, 
00140                 ("Missing FLD for ST %s in Create_ST_TO_FLD_MAP",ST_name(st)));
00141       }
00142     }
00143   }
00144 }
00145 
00146 //=================================================================
00147 // DESCR: Get_FLD
00148 //        Return the FLD given the ST
00149 //=================================================================
00150 /*ARGSUSED*/
00151 FLD_HANDLE
00152 Get_FLD(ST* s, ST* common_st, ST_TO_FLD_MAP_ARRAY& st_to_fld_map)
00153 {
00154 #if 0
00155     FLD_ITER fld_iter = 
00156   Make_fld_iter(TY_fld(Ty_Table[ST_type(common_st)]));
00157     do {
00158   FLD_HANDLE current_fld (fld_iter);
00159   TY& fld_type = Ty_Table[FLD_type(current_fld)];
00160   if (FLD_ofst(current_fld) == ST_ofst(s) && 
00161       (FLD_type(current_fld) == ST_type(s)))
00162       {
00163     return current_fld;
00164       }
00165     } while (!FLD_last_field(fld_iter++));
00166     
00167     Is_True(0, ("FLD not found in Get_FLD \n"));
00168     return;
00169 }
00170 #endif       
00171 
00172   ST* st = NULL;
00173   FLD_HANDLE fld;
00174   for (UINT32 idx = 0; idx < st_to_fld_map.Elements(); idx++)
00175     {
00176       ST_TO_FLD_MAP *entry = &(st_to_fld_map)[idx];
00177       if (s == entry->Get_ST())
00178   return entry->Get_FLD();
00179     } 
00180   return fld;
00181 }
00182 
00183 //=================================================================
00184 // DESCR: Get_ST
00185 //        Return the ST given the field
00186 //=================================================================
00187 /*ARGSUSED*/
00188 ST *
00189 Get_ST(FLD_HANDLE fld, ST_TO_FLD_MAP_ARRAY& st_to_fld_map)
00190 {
00191   ST  * st = NULL;
00192 #if 0
00193   ST_IDX idx = FLD_st(fld);
00194   return &St_Table[idx];
00195 #endif
00196   for (mUINT32 idx = 0; idx < st_to_fld_map.Elements(); idx++)
00197     {
00198       ST_TO_FLD_MAP *entry = &(st_to_fld_map)[idx];
00199       if (fld == entry->Get_FLD())
00200   return entry->Get_ST();
00201     }
00202   return st;
00203 
00204 } // Get_ST
00205 
00206 // ==================================================================
00207 // DESCR: Is_Const_Bounds
00208 // ==================================================================
00209 inline INT64
00210 Is_Const_Bounds(ARB_HANDLE arb)
00211 {
00212   return (ARB_const_ubnd(arb) && ARB_const_lbnd(arb) && 
00213            ARB_const_stride(arb));
00214 }
00215 
00216 // ==================================================================
00217 // DESCR: Num_Elements
00218 //        return the number of elements in a particular dimension
00219 // ==================================================================
00220 static INT64
00221 Num_Elements(ARB_HANDLE arb)
00222 {
00223 #ifdef KEY
00224 // bug 2132: for dimensions -n1:n1, # of elements is n1 - (-n1) + 1
00225    return abs(ARB_ubnd_val(arb) - ARB_lbnd_val(arb)) + 1;
00226 #else
00227  INT64 count = 0;
00228    return abs(abs(ARB_ubnd_val(arb)) - abs((ARB_lbnd_val(arb)))) + 1;
00229 #endif
00230 }
00231 // ===========================================================
00232 // DESCR: Create_New_Array_Type
00233 //        Create a new array type
00234 // ===========================================================
00235 static TY_IDX 
00236 Create_New_Array_Type(TY_IDX old_array_ty)
00237 {
00238   INT num_dims = TY_AR_ndims(old_array_ty);
00239   TY_IDX etype_idx = TY_etype(old_array_ty);
00240   const TY& etype = Ty_Table[etype_idx];
00241 
00242   TY_IDX new_array_ty = 
00243     Make_Array_Type(TY_mtype(etype), num_dims, 1);
00244 
00245   Set_TY_name_idx(Ty_Table[new_array_ty], TY_name_idx(Ty_Table[old_array_ty]));
00246   Set_TY_size(Ty_Table[new_array_ty],TY_size(Ty_Table[old_array_ty]));
00247 
00248   num_dims = TY_AR_ndims(new_array_ty);
00249   ARB_HANDLE arb_base = TY_arb(new_array_ty);
00250   ARB_HANDLE old_arb_base = TY_arb(old_array_ty);
00251   for (UINT i = 0; i < num_dims ; ++i)
00252     {
00253       ARB_HANDLE  arb = arb_base[i];
00254       ARB_HANDLE  old_arb = old_arb_base[i];
00255       ARB_Init(arb, ARB_lbnd_val(old_arb), 
00256          ARB_ubnd_val(old_arb), 
00257          ARB_stride_val(old_arb));
00258       Set_ARB_dimension(arb, num_dims-i);
00259       if (i==0)
00260    Set_ARB_first_dimen(arb_base[0]);
00261       if (i == num_dims-1)
00262    Set_ARB_last_dimen(arb_base[i]); 
00263     }
00264   
00265   return new_array_ty;
00266 }
00267 
00268 // ===========================================================
00269 // DESCR: Create_New_Array_Type
00270 //        Create a new array type
00271 // ===========================================================
00272 static TY_IDX 
00273 Create_Multi_Dim_Array_Type(TY_IDX old_array_ty, BOUNDS_ARRAY *bounds)
00274 {
00275   TY_IDX ty_index = Create_New_Array_Type(old_array_ty);
00276 
00277   TY&  new_array_ty = Ty_Table[ty_index];
00278 
00279   INT num_dims = TY_AR_ndims(new_array_ty);
00280   ARB_HANDLE arb_base = TY_arb(new_array_ty);
00281   INT64 element_size = ARB_stride_val(arb_base[num_dims-1]);
00282   INT64 new_stride = element_size;
00283   
00284   for (UINT i = 0; i < num_dims ; ++i)
00285      {
00286   // get to the array bounds information in column major order
00287   ARB_HANDLE  arb = arb_base[num_dims-i-1];
00288   BOUNDS *belement = &(*bounds)[i];
00289   INT64 upper = belement->Get_Upper(); 
00290   Set_ARB_ubnd_val(arb,upper);
00291   Set_ARB_stride_val(arb,new_stride);
00292   new_stride = new_stride*Num_Elements(arb);
00293      }
00294   return ty_index;
00295 }
00296 
00297 
00298 
00299 // ===========================================================
00300 // DESCR: Get_New_Size_Padding
00301 //        return the padding for dimensions starting at 
00302 //        start dim
00303 //        if start_dim =0, returns total padding
00304 //        if start_dim =1, returns padding for all dims except 
00305 //           last dimension
00306 // ===========================================================
00307 INT64
00308 Get_New_Size_Padding(TY_IDX new_array_ty_idx, TY_IDX old_array_ty_idx,
00309          INT32 start_dim)
00310 {
00311  TY&  new_array_ty = Ty_Table[new_array_ty_idx];
00312  TY& old_array_ty = Ty_Table[old_array_ty_idx];
00313 
00314   INT64 old_size = 1;
00315   INT64 new_size = 1;
00316   INT num_dims = TY_AR_ndims(new_array_ty);
00317   ARB_HANDLE old_arb = TY_arb(old_array_ty);
00318   ARB_HANDLE new_arb = TY_arb(new_array_ty);
00319 
00320   for (INT i=start_dim; i<num_dims; ++i)
00321     {
00322       old_size = old_size*Num_Elements(old_arb[i]);
00323       new_size = new_size*Num_Elements(new_arb[i]);
00324     }
00325   new_size = new_size - old_size;
00326   return new_size;
00327 }
00328 
00329 //=================================================================
00330 // DESCR: Update_Split_Array
00331 //        update the entries of the split array after padding
00332 //=====================================================================
00333 static void
00334 Update_Split_Array(SPLIT_COMMON_DYN_ARRAY *split_array, ST* s)
00335 {
00336   INT id = 0;
00337 
00338   FLD_ITER fld_iter = Make_fld_iter (TY_fld (Ty_Table[ST_type (s)]));
00339   do {
00340     FLD_HANDLE fld (fld_iter);
00341     if (!FLD_equivalence (fld)) {
00342       INT64 element_size = 0;
00343       const TY& fld_type = Ty_Table[FLD_type (fld)];
00344       if (TY_kind(fld_type) == KIND_ARRAY)
00345         element_size = TY_size(TY_etype(fld_type));
00346       else
00347         element_size = TY_size(fld_type);
00348 
00349       SPLIT_COMMON *node = &(*split_array)[id++];
00350       node->Set_Vals(FLD_ofst(fld), TY_size(fld_type)/element_size, element_size, node->Get_split_position(), node->Get_group_position());
00351     }
00352   }  while (!FLD_last_field (fld_iter++));
00353 
00354 }
00355 
00356 // ===========================================================
00357 // DESCR: Pad_Multi_Dim_Common_ST
00358 //        Pad multiple dimensions of a common array
00359 // ===========================================================
00360 static void
00361 Pad_Multi_Dim_Common_ST(ST_TO_FLD_MAP_ARRAY &st_map, ST* st,
00362       ST* common_st, BOUNDS_ARRAY *bounds,
00363                         COMMON_SNODE_LIST *snode_list)
00364 {
00365 
00366   FLD_HANDLE fld = Get_FLD(st, common_st, st_map);
00367   Is_True(!fld.Is_Null(), ("NULL field in Pad_Multi_Dim_Common_ST \n"));
00368   const TY& fld_type = Ty_Table[FLD_type(fld)];
00369 
00370   // Only pad arrays with scalar element types
00371   TY_IDX etype_idx = TY_etype(fld_type);
00372   const TY& etype = Ty_Table[etype_idx];
00373 
00374   if (TY_kind(etype) == KIND_SCALAR) {
00375     // Duplicate the array, such that 
00376     // we are guaranteed not modify some
00377     // shared array type (e.g. a TY_pointed() array).
00378 
00379     TY_IDX old_array_ty_idx = FLD_type(fld);
00380     UINT old_size = Ty_tab.Size();
00381     TY_IDX new_array_ty_idx = 
00382       Create_Multi_Dim_Array_Type(FLD_type(fld), bounds);
00383     TY&  new_array_ty = Ty_Table[new_array_ty_idx];
00384     TY& old_array_ty = Ty_Table[old_array_ty_idx];
00385     TY& common_ty = Ty_Table[ST_type(common_st)];
00386     ARB_HANDLE old_arb_base = TY_arb(old_array_ty);
00387     ARB_HANDLE new_arb_base = TY_arb(new_array_ty);
00388 
00389     // Update the type attributes of the field and the 
00390     // corresponding split out ST.
00391     Set_FLD_type(fld, new_array_ty_idx);
00392     ST *s = Get_ST(fld, st_map);
00393     Is_True(s != NULL, ("NULL st to Pad_Multi_Dim_Common_ST \n"));
00394     Set_ST_type(*s, new_array_ty_idx);
00395 
00396     // Get the array type attributes
00397     INT64 fld_start = FLD_ofst(fld);
00398     INT64 fld_old_end = fld_start + TY_size(new_array_ty);
00399     INT num_dims = TY_AR_ndims(new_array_ty);
00400     INT64 add_size  = Get_New_Size_Padding(new_array_ty_idx,
00401           old_array_ty_idx,0);
00402     add_size = add_size*TY_size(etype_idx);
00403     
00404     if (trace_split_common)
00405       fprintf(TFile, "size added is %lld \n", add_size);
00406 
00407     Set_TY_size(common_ty, TY_size(common_ty) + add_size);
00408     Set_TY_size(new_array_ty, TY_size(old_array_ty) + add_size);
00409     
00410     // compute these for the first dimension
00411     INT64 padding = Get_New_Size_Padding(new_array_ty_idx, 
00412            old_array_ty_idx,1)*
00413              TY_size(etype_idx);
00414     INT64 stride1 = ARB_stride_val(TY_arb(old_array_ty));
00415 
00416     FLD_ITER fld_iter = 
00417       Make_fld_iter(TY_fld(Ty_Table[ST_type(common_st)]));
00418     do {
00419       FLD_HANDLE current_fld (fld_iter);
00420       TY& fld_type = Ty_Table[FLD_type(current_fld)];
00421       if (FLD_ofst(current_fld) >= fld_old_end)
00422   {
00423     s = Get_ST(current_fld, st_map);
00424     if (s != NULL) { 
00425       Set_ST_ofst(*s, ST_ofst(*s) + add_size);
00426       Set_FLD_ofst(current_fld, FLD_ofst(current_fld) + add_size);
00427     } 
00428   }
00429 
00430       else if (FLD_ofst(current_fld) >=  (fld_start + stride1))
00431   {
00432     s = Get_ST(current_fld, st_map);
00433     if (s != NULL) { 
00434       INT64 incr = 
00435         ((FLD_ofst(current_fld) - fld_start)/stride1)*padding;
00436       Set_ST_ofst(*s, (ST_ofst(*s) + incr));
00437       Set_FLD_ofst(current_fld, FLD_ofst(current_fld) + incr);
00438     } 
00439   }
00440     } while (!FLD_last_field(fld_iter++));
00441 
00442     if (!snode_list->No_Split()) {
00443       Update_Split_Array(snode_list->Get_Split_Array(), common_st);
00444     }
00445 
00446   } // if scalar type
00447 }
00448 
00449 
00450 // ===========================================================
00451 // DESCR: Pad an element of a common
00452 // =========================================================== 
00453 static void 
00454 Pad_Common_ST (ST_TO_FLD_MAP_ARRAY &st_map, ST *st, 
00455           ST* common_st, INT padding, COMMON_SNODE_LIST *snode_list)
00456 {
00457   FLD_HANDLE fld = Get_FLD(st,common_st, st_map);
00458   Is_True(!fld.Is_Null(), ("NULL field in Pad_Common_ST \n"));
00459   const TY& fld_type = Ty_Table[FLD_type(fld)];
00460   // Only pad arrays with scalar element types
00461   TY_IDX etype_idx = TY_etype(fld_type);
00462   const TY& etype = Ty_Table[etype_idx];
00463   if (TY_kind(etype) == KIND_SCALAR) {
00464  
00465     // Duplicate the array, such that 
00466     // we are guaranteed not modify some
00467     // shared array type (e.g. a TY_pointed() array).
00468     //
00469     TY_IDX old_array_ty_idx = FLD_type(fld);
00470     UINT old_size = Ty_tab.Size();
00471     TY_IDX new_array_ty_idx = Create_New_Array_Type(FLD_type(fld));
00472 
00473     Is_True(Ty_tab.Size() == old_size+1, ("TY is not entered in Pad_Common_ST \n"));
00474 
00475     TY&  new_array_ty = Ty_Table[new_array_ty_idx];
00476     TY& old_array_ty = Ty_Table[old_array_ty_idx];
00477     TY& common_ty = Ty_Table[ST_type(common_st)];
00478 
00479     ARB_HANDLE old_arb_base = TY_arb(old_array_ty);
00480     ARB_HANDLE new_arb_base = TY_arb(new_array_ty);
00481 
00482     // Update the type attributes of the field and the 
00483     // corresponding split out ST.
00484     Set_FLD_type(fld, new_array_ty_idx);
00485     ST *s = Get_ST(fld, st_map);
00486     Is_True(s != NULL, ("NULL st to Pad_Common_ST \n"));
00487     Set_ST_type(*s, new_array_ty_idx);
00488 
00489     // Get the array type attributes
00490     INT64 fld_start = FLD_ofst(fld);
00491     INT64 fld_old_end = fld_start + TY_size(new_array_ty);
00492     INT num_dims = TY_AR_ndims(new_array_ty);
00493     INT64 stride1 = ARB_stride_val(TY_arb(old_array_ty));
00494 
00495     // Modify the array-type and estimate the increase in size.
00496     INT64 num_cols = TY_size(old_array_ty)/stride1;
00497     INT64 add_size = num_cols*padding;
00498 
00499     if (trace_split_common)
00500       fprintf(TFile, "size added is %lld \n", add_size);
00501     Set_TY_size(common_ty, TY_size(common_ty) + add_size);
00502     Set_TY_size(new_array_ty, TY_size(old_array_ty) + add_size);
00503 
00504     ARB_HANDLE old_arb = old_arb_base[num_dims-1];
00505     ARB_HANDLE new_arb = new_arb_base[num_dims-1];
00506     
00507     Is_True((ARB_stride_val(old_arb) != 0),("Zero stride value found in Pad_Common_St\n"));
00508 
00509     Set_ARB_ubnd_val(new_arb, 
00510          ARB_ubnd_val(old_arb)+
00511          padding/ARB_stride_val(old_arb));
00512     // Update the arb fields for the array
00513     for (INT dim = 1; dim < TY_AR_ndims(old_array_ty); dim++) {
00514       // Update the stride for each dimension by adding:
00515       //
00516       //    (num_cols_per_stride * padding_per_col)
00517       //
00518       //  add_stride = (TY_AR_stride_val(array_ty, dim)/stride1) * padding;
00519       //    TY_AR_stride_val(array_ty, dim) += add_stride;
00520       INT numdims = TY_AR_ndims(old_array_ty);
00521       ARB_HANDLE new_arb = old_arb_base[num_dims-1-dim];      
00522       ARB_HANDLE old_arb = new_arb_base[num_dims-1-dim];
00523 
00524       INT add_stride = (ARB_stride_val(old_arb)/stride1) * padding;
00525       Set_ARB_stride_val(new_arb, ARB_stride_val(new_arb)+add_stride);
00526     }
00527 
00528     // Increase the offsets for fields that overlap or follow
00529     // this one (no field should straddle a column).
00530     //
00531     FLD_ITER fld_iter = 
00532       Make_fld_iter(TY_fld(Ty_Table[ST_type(common_st)]));
00533     do {
00534       FLD_HANDLE current_fld (fld_iter);
00535       TY& fld_type = Ty_Table[FLD_type(current_fld)];
00536       if (FLD_ofst(current_fld) >= fld_old_end)
00537   {
00538     s = Get_ST(current_fld, st_map);
00539     if (s != NULL) { 
00540       Set_ST_ofst(*s, ST_ofst(*s) + add_size);
00541       Set_FLD_ofst(current_fld, FLD_ofst(current_fld) + add_size);
00542     } 
00543   }
00544       else if (FLD_ofst(current_fld) >=  (fld_start + stride1))
00545   {
00546     s = Get_ST(current_fld, st_map);
00547     if (s != NULL) { 
00548       INT64 incr = 
00549         ((FLD_ofst(current_fld) - fld_start)/stride1)*padding;
00550       Set_ST_ofst(*s, (ST_ofst(*s) + incr));
00551       Set_FLD_ofst(current_fld, FLD_ofst(current_fld) + incr);
00552     } 
00553   }
00554 
00555     } while (!FLD_last_field(fld_iter++));
00556     if (IPA_Enable_Split_Common)
00557       Update_Split_Array(snode_list->Get_Split_Array(), common_st);
00558    }
00559 } // Pad_Common_ST
00560 
00561 
00562 // =========================================================== 
00563 // DESCR: Padding_Size
00564 //        return the pad size
00565 // =========================================================== 
00566 static INT64
00567 Padding_Size(const ST* s)
00568 {
00569   Is_True((TY_kind(ST_type(s)) == KIND_ARRAY), ("Expecting an ST of KIND_ARRAY \n"));
00570   INT lower, upper, stride;
00571   INT64 pad_size = 0;
00572   INT64 padding = 0;
00573 
00574   INT num_dims = ARB_dimension(TY_arb(ST_type(s)));
00575   if (num_dims > 1) 
00576     {
00577       ARB_HANDLE arb = TY_arb(ST_type(s))[num_dims - 1];
00578       if (ARB_const_lbnd(arb) && ARB_const_ubnd(arb) &&
00579     ARB_const_stride(arb))
00580   {
00581     lower = ARB_lbnd_val(arb);
00582     upper = ARB_ubnd_val(arb);
00583     stride = ARB_stride_val(arb);
00584     pad_size = abs(upper - lower + 1);
00585     padding = Common_Array_Pad_Size(pad_size*stride);
00586     return padding;
00587   }
00588       else
00589   Fail_FmtAssertion("Non constant bounds in Padding_Size \n");
00590     }
00591   Fail_FmtAssertion("Expecting num dims > 1 in Padding_Size \n");
00592   return 0;
00593 }
00594 
00595 // =========================================================== 
00596 // DESCR: Pad_Multi_Dim_Global_ST
00597 //        Pad a global ST
00598 // =========================================================== 
00599 static void   
00600 Pad_Multi_Dim_Global_ST(ST *s, BOUNDS_ARRAY* bounds)
00601 {
00602   const TY& fld_type = Ty_Table[ST_type(s)];
00603 
00604   Is_True(TY_kind(fld_type) == KIND_ARRAY, ("Expecting KIND_ARRAY in Pad_Multi_Dim_Global_ST \n"));
00605 
00606   // Only pad arrays with scalar element types
00607   TY_IDX etype_idx = TY_etype(fld_type);
00608   const TY& etype = Ty_Table[etype_idx];
00609 
00610   if (TY_kind(etype) == KIND_SCALAR) {
00611     // Duplicate the array, such that 
00612     // we are guaranteed not modify some
00613     // shared array type (e.g. a TY_pointed() array).
00614     TY_IDX old_array_ty_idx = ST_type(s);
00615     TY_IDX new_array_ty_idx = 
00616       Create_Multi_Dim_Array_Type(ST_type(s), bounds);
00617     TY&  new_array_ty = Ty_Table[new_array_ty_idx];
00618     TY& old_array_ty = Ty_Table[old_array_ty_idx];
00619     Set_ST_type(*s, new_array_ty_idx);
00620     INT num_dims = TY_AR_ndims(new_array_ty);
00621     INT64 add_size  = Get_New_Size_Padding(new_array_ty_idx,
00622              old_array_ty_idx,0);
00623     add_size = add_size*TY_size(etype_idx);
00624     if (trace_split_common)
00625       fprintf(TFile, "size added is %lld \n", add_size);
00626     Set_TY_size(new_array_ty, TY_size(old_array_ty) + add_size);
00627   }
00628 } 
00629 
00630 
00631 // =========================================================== 
00632 // DESCR: Pad_Multi_Dim_Common
00633 //        pad multiple dimensions of arrays
00634 // =========================================================== 
00635 static void
00636 Pad_Multi_Dim_Common(COMMON_SNODE_LIST* common_snode_list)
00637 {
00638   COMMON_SNODE_LIST_ITER  common_snode_list_iter(common_snode_list);
00639   // walk the commons in this list and see if any of them
00640   // need to be padded
00641   for (common_snode_list_iter.First();
00642        !common_snode_list_iter.Is_Empty();
00643        common_snode_list_iter.Next()) 
00644     {
00645       COMMON_SNODE *common_snode = common_snode_list_iter.Cur();
00646       ST *s  = common_snode->Get_ST();
00647       
00648       if (ST_sclass(s) == SCLASS_COMMON) {
00649   ST *common_st = ST_base(s);
00650   ST_TO_FLD_MAP_ARRAY *st_map = common_snode_list->Get_Map();
00651   INT64 padding = 0;
00652   if (common_snode->Pad())
00653     {
00654       Pad_Multi_Dim_Common_ST(*st_map, s, common_st,
00655             common_snode->Get_Bounds_Array(),
00656             common_snode_list);
00657     }
00658       }
00659       else 
00660   if ((ST_sclass(s) == SCLASS_UGLOBAL) && common_snode->Pad())
00661     {
00662       Pad_Multi_Dim_Global_ST(s,
00663             common_snode->Get_Bounds_Array());
00664 
00665     }
00666     }
00667 }
00668 
00669 // =========================================================== 
00670 // DESCR: Pad_Common
00671 //        Pad elements of a common
00672 // =========================================================== 
00673 static void
00674 Pad_Common (COMMON_SNODE_LIST *common_snode_list)
00675 {
00676   if (common_snode_list->No_Pad())
00677     return;
00678 
00679   COMMON_SNODE_LIST_ITER  common_snode_list_iter(common_snode_list);
00680   // walk the commons in this list and see if any of them
00681   // need to be padded
00682 
00683   for (common_snode_list_iter.First();
00684        !common_snode_list_iter.Is_Empty();
00685        common_snode_list_iter.Next()) 
00686     {
00687       COMMON_SNODE *common_snode = common_snode_list_iter.Cur();
00688       ST *s  = common_snode->Get_ST();
00689       ST *common_st = ST_base(s);
00690 
00691       ST_TO_FLD_MAP_ARRAY *st_map = common_snode_list->Get_Map();
00692 
00693       INT64 padding = 0;
00694       if (common_snode->Pad())
00695   {
00696     padding = Padding_Size(s);
00697     if (trace_split_common) 
00698       fprintf (TFile, "st = %s, pad size = %lli \n", ST_name(s),padding);
00699       
00700     // Make the padding both a multiple of stride0 and
00701     // the largest possible alignment constrain (16).
00702     // NOTE: The largest stride we
00703     //
00704     INT64 div_padding;
00705     INT64 stride0;
00706 
00707     INT num_dims = ARB_dimension(TY_arb(ST_type(s)));
00708     ARB_HANDLE arb = TY_arb(ST_type(s))[num_dims-1];
00709     stride0 = ARB_stride_val(arb);
00710     
00711     if (stride0 > MAX_ALIGN)
00712       div_padding = stride0;
00713     else
00714       div_padding = MAX_ALIGN;
00715     
00716     if (div_padding > padding)
00717       padding = div_padding;
00718     else
00719       padding = (div_padding - (padding % div_padding)) + padding;
00720 
00721     Pad_Common_ST (*st_map,s,common_st,padding,common_snode_list);
00722   } // if paddable array
00723     }
00724 }
00725 
00726 
00727 // =========================================================== 
00728 // DESCR: IPO_Pad_Symtab
00729 //        update the symbol table
00730 // =========================================================== 
00731 extern void
00732 IPO_Pad_Symtab(COMMON_SNODE_TBL *common_snode_tbl)
00733 {
00734   trace_split_common =  Get_Trace(TP_IPA, IPA_TRACE_SPLIT_COMMON);
00735 
00736   COMMON_SNODE_LIST *snode_list;
00737   COMMON_SNODE_TBL_ITER common_snode_tbl_iter(common_snode_tbl);
00738   
00739   Create_ST_TO_FLD_MAP(common_snode_tbl);
00740 
00741   STR_IDX common_name;
00742   while (common_snode_tbl_iter.Step (&common_name, &snode_list)) {
00743     if (!ST_is_not_used(snode_list->Get_ST()) && !snode_list->No_Pad()) {
00744       Pad_Multi_Dim_Common(snode_list);
00745     }
00746   }
00747 }
00748 
00749 // =========================================================== 
00750 // DESCR: IPO_Pad_Arrays
00751 //        update the whirl to reflect the new size
00752 // =========================================================== 
00753 
00754 static void 
00755 IPO_Pad_Arrays(WN* func_nd)
00756 {
00757    // pad the arrays after the symtab has been fixed.
00758    OPCODE opc = WN_opcode(func_nd);
00759    if (OPCODE_operator(opc) == OPR_ARRAY && (WN_num_dim(func_nd) > 1)) {
00760       WN *base = WN_array_base(func_nd);
00761       if ((OPCODE_operator(WN_opcode(base)) == OPR_LDA) && 
00762     (TY_kind(ST_type(WN_st(base))) == KIND_ARRAY)) {
00763    ARB_HANDLE arb_base = TY_arb(ST_type(WN_st(base)));
00764    BOOL set_base = FALSE;
00765    for (INT i=0; i<WN_num_dim(func_nd); ++i) {
00766       WN *dim = WN_array_dim(func_nd,i);
00767       if (OPCODE_operator(WN_opcode(dim)) == OPR_INTCONST) {
00768          ST *st = WN_st(base);
00769          INT num_dim = WN_num_dim(func_nd);
00770          ARB_HANDLE arb = arb_base[i];
00771          if (Is_Const_Bounds(arb)) {
00772       INT64 st_size = Num_Elements(arb);
00773       if (WN_const_val(dim) != st_size) {
00774          WN_const_val(dim) = st_size;
00775          if (TY_pointed(WN_ty(base)) != ST_type(st) &&
00776        TY_kind(TY_pointed(WN_ty(base))) == KIND_ARRAY)
00777       {
00778          if (!set_base) {
00779             TY_IDX idx = Make_Pointer_Type(ST_type(st));
00780             WN_set_ty(base, idx);
00781          }
00782       }
00783       }
00784          }
00785       }
00786    }
00787       }
00788    }
00789    if (opc == OPC_BLOCK) {
00790       for (WN* wn = WN_first(func_nd); wn; wn = WN_next(wn)) {
00791    IPO_Pad_Arrays(wn);
00792       }
00793    } else {
00794       for (INT kid=0; kid<WN_kid_count(func_nd); kid++) {
00795    IPO_Pad_Arrays(WN_kid(func_nd,kid));
00796       }
00797    }
00798 } // IPO_Pad_Arrays
00799 
00800 
00801 // =========================================================== 
00802 // DESCR: IPO_Pad_Whirl
00803 //        update the whirl to reflect the new size
00804 // =========================================================== 
00805 extern void
00806 IPO_Pad_Whirl(IPA_NODE* node)
00807 {
00808   WN *w = node->Whirl_Tree();
00809   Is_True(w != NULL, (" NULL whirl encountered \n"));
00810   IPO_Pad_Arrays(w);
00811 #ifdef Is_True  
00812   WN_verifier(w);
00813   Verify_GLOBAL_SYMTAB();
00814 #endif
00815 }
00816 
00817
osprey/ipa/main/optimize/ipo_pad.cxx
