Open64: osprey/be/lno/lno_split.cxx Source File

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 //                     Statement Splitting
00041 //                     -------------------
00042 //
00043 // Description:
00044 //
00045 //  Split large statements.  This allows phase 3 to do more
00046 //  fission.
00047 //
00048 //
00049 /* ====================================================================
00050  * ====================================================================
00051  *
00052  * Module: lno_split.cxx
00053  * $Revision: 1.6 $
00054  * $Date: 04/12/21 14:57:13-08:00 $
00055  * $Author: bos@eng-25.internal.keyresearch.com $
00056  * $Source: /home/bos/bk/kpro64-pending/be/lno/SCCS/s.lno_split.cxx $
00057  *
00058  * Revision history:
00059  *  dd-mmm-94 - Original Version
00060  *
00061  * Description: Split statements
00062  * ====================================================================
00063  * ====================================================================
00064  */
00065 
00066 #define __STDC_LIMIT_MACROS
00067 #include <stdint.h>
00068 #ifdef USE_PCH
00069 #include "lno_pch.h"
00070 #endif // USE_PCH
00071 #pragma hdrstop
00072 
00073 const static char *source_file = __FILE__;
00074 const static char *rcs_id = "$Source: /home/bos/bk/kpro64-pending/be/lno/SCCS/s.lno_split.cxx $ $Revision: 1.6 $";
00075 
00076 #include <sys/types.h>
00077 #include "lnopt_main.h"
00078 #include "dep_graph.h"
00079 #include "model.h"
00080 #include "lnoutils.h"
00081 #include "lwn_util.h"
00082 #include "config_targ_opt.h"
00083 #include "config_targ.h"
00084 #include "config_opt.h"
00085 #include "opt_du.h"
00086 #include "opt_alias_interface.h"
00087 #include "reduc.h"
00088 
00089 static INT Split_Statement(WN *statement, ARRAY_DIRECTED_GRAPH16 *dep_graph);
00090 static BOOL Scalar_Interferes(WN *store, WN *expr, WN *split_point,
00091         ARRAY_DIRECTED_GRAPH16 *dep_graph);
00092 static WN *Find_Inner(WN *wn);
00093 static WN *Find_Split_Point(WN *store);
00094 static INT Num_Leaves_Or_Arrays(WN *wn);
00095 static WN *Find_Enough_Subtree(WN *wn, INT enough, INT *num_leaves);
00096 static BOOL Need_To_Split(WN *region);
00097 extern BOOL Variant_Array(WN *store, WN *split_point, 
00098         ARRAY_DIRECTED_GRAPH16 *dep_graph);
00099 extern WN *Split_Using_Preg(WN *statement, WN *split_point,
00100         ARRAY_DIRECTED_GRAPH16 *dep_graph,
00101         BOOL recursive=TRUE);
00102 extern INT Split_Array(WN *statement, WN *split_point,
00103         ARRAY_DIRECTED_GRAPH16 *dep_graph);
00104 
00105 static BOOL is_ok_to_reassociate(OPCODE opc)
00106 {
00107   // based on common/com/wn_simp_code.h
00108   // TODO: unify these predicates in a single, shared location.
00109 
00110    switch (OPCODE_operator(opc)) {
00111     case OPR_MAX:
00112     case OPR_MIN:
00113     case OPR_BAND:
00114     case OPR_BIOR:
00115     case OPR_BXOR:
00116     case OPR_LAND:
00117     case OPR_LIOR:
00118       return (TRUE);
00119 
00120     case OPR_ADD:
00121     case OPR_MPY:
00122       if ( MTYPE_is_integral(OPCODE_rtype(opc)) ) {
00123    return TRUE;
00124       } else if ( MTYPE_is_float(OPCODE_rtype(opc)) ) {
00125    return ( Enable_Cfold_Reassociate );
00126       } else {
00127    /* Don't know what to do */
00128    return FALSE;
00129       }
00130       
00131     default:
00132       return FALSE;
00133    }
00134 }
00135 
00136 static WN *reassoc_expr(WN *wn)
00137 {
00138   if ( ! is_ok_to_reassociate( WN_opcode(wn) ) ) {
00139     for (INT i = 0; i < WN_kid_count(wn); ++i) {
00140       WN_kid(wn, i) = reassoc_expr(WN_kid(wn,i));
00141     }
00142     return wn;
00143   }
00144   OPERATOR opr   = WN_operator(wn);
00145   TYPE_ID  rtype = WN_rtype(wn);
00146   WN      *lhs   = reassoc_expr(WN_kid0(wn));
00147   WN      *rhs   = reassoc_expr(WN_kid1(wn));
00148   WN      *e     = rhs;
00149   WN      *e2    = e;
00150 
00151   WN_kid0(wn) = lhs;  // make sure childen connected properly.
00152   WN_kid1(wn) = rhs;
00153 
00154   //           wn                   rhs
00155   //          / |                  / |
00156   //         L  rhs               ~  f
00157   //           / |     ===>       e
00158   //          ~  f               / \ 
00159   //          e                 wn  b
00160   //         / \               /  \ 
00161   //        e2  b             L   e2
00162 
00163   while ( WN_operator(e2) == opr && WN_rtype(e2) == rtype ) {
00164     e  = e2;
00165     e2 = WN_kid0(e2);
00166   }
00167   if ( e2 != e ) {
00168     WN_kid1(wn) = e2;
00169     WN_kid0(e)  = wn;
00170     return rhs;
00171   }
00172   return wn;
00173 }
00174 
00175 // split all the statements that use too many register in a region 
00176 // (where region is defined loosely).  
00177 // Too many is at least Target_FPRs -2
00178 // All stores in the region must be descendents of a do loop
00179 //
00180 // Do nothing if we have less than 32 registers (in that case model will
00181 // always think we need too many registers regardless)
00182 //
00183 // Return 0 on error
00184 INT Split_Region(WN *region, ARRAY_DIRECTED_GRAPH16 *dep_graph)
00185 {
00186   if (Target_FPRs < 32) return 1;
00187 
00188   OPCODE opcode = WN_opcode(region);
00189   if (opcode == OPC_BLOCK) {
00190     WN *kid = WN_first(region);
00191     while (kid) {
00192       WN *next = WN_next(kid);
00193       if (!Split_Region(kid,dep_graph)) return 0;
00194       kid = next;
00195     }
00196   } else if (OPCODE_is_store(opcode) &&         // The following test ensures
00197                                                 // that we don't try to split 
00198                                                 // large initialization stids
00199                                                 // under DO_LOOPS
00200              WN_opcode(LWN_Get_Parent(region)) == OPC_BLOCK) {
00201     if (Need_To_Split(region)) {
00202       if ( Enable_Cfold_Reassociate ) {
00203   OPERATOR opr = WN_operator(region);
00204   if ( opr == OPR_STID || opr == OPR_ISTORE ) {
00205     // pv 593337: ensure canonical form, which may be
00206     // destroyed by forward substitution.  Canonical
00207     // form is well suited to spliting in a way that
00208     // leads to benificial loop fission.
00209     WN_kid0(region) = reassoc_expr(WN_kid0(region));
00210     LWN_Parentize(region);
00211   }
00212       }
00213       if (!Split_Statement(region,dep_graph)) return 0;
00214     }
00215   } else if (!OPCODE_is_expression(opcode)) {
00216     for (INT kidno=0; kidno<WN_kid_count(region); kidno++) {
00217       if (!Split_Region(WN_kid(region,kidno),dep_graph)) return 0;
00218     }
00219   }
00220   return 1;
00221 }
00222 
00223 static BOOL Need_To_Split(WN *region)
00224 {
00225   MEM_POOL_Push(&LNO_local_pool);
00226   REGISTER_MODEL *reg_model = CXX_NEW(REGISTER_MODEL(&LNO_local_pool), 
00227               &LNO_local_pool);
00228   reg_model->Add_Statement(region);
00229   INT fpr,intr,tlb;
00230   reg_model->Calculate_Register_Usage(Find_Inner(region),&fpr,&intr,&tlb);
00231   if (fpr >= (Target_FPRs-2) || intr >= Target_INTRs-2 ||
00232       tlb >= Mhd.L[0].TLB_Entries-2) {
00233     MEM_POOL_Pop(&LNO_local_pool);
00234     return TRUE;
00235   } 
00236   MEM_POOL_Pop(&LNO_local_pool);
00237   return FALSE;
00238 }
00239 
00240 // Given that statement needs to be split, split it in half
00241 // Given a = b(...) + c(...), (where b and c are subtrees),
00242 // we'd usually split this into
00243 // preg = c(...)
00244 // a = b(...) + preg
00245 //
00246 // if 'a' is a variant array references, i.e. 
00247 // a[i] = b(...) + c(...)
00248 // we instead split this into
00249 // a[i] = c(...)
00250 // a[i] = b(...) + a[i]
00251 // this allows us to fission between the two statements without doing
00252 // scalar expansion
00253 // it's only legal if there is no all equals dependence to a[i] from 
00254 // anything in b(...)
00255 //
00256 // return 0 on error
00257 static INT Split_Statement(WN *statement, ARRAY_DIRECTED_GRAPH16 *dep_graph)
00258 {
00259   WN *split_point = Find_Split_Point(statement);
00260   if (!WN_kid_count(split_point)) {
00261     return 1;  // don't split leaves
00262   }
00263 
00264   if ((WN_operator(statement)==OPR_STID || WN_operator(statement)==OPR_ISTORE)
00265       && split_point == WN_kid0(statement)) {
00266 
00267     // we're splitting around the entire RHS, so don't bother
00268     return 1;
00269   }
00270 
00271   if (Variant_Array(statement,split_point,dep_graph) &&
00272       (WN_rtype(split_point)  == WN_desc(statement))) {
00273     if (!Split_Array(statement,split_point,dep_graph)) {
00274       return 0;
00275     }
00276   } else {
00277     Split_Using_Preg(statement,split_point,dep_graph);
00278   }
00279   return 1;
00280 }
00281 
00282 
00283 extern INT Split_Array(WN *store, WN *split_point, 
00284     ARRAY_DIRECTED_GRAPH16 *dep_graph) 
00285 {
00286   // make two copies of the array statement
00287   WN *array1 = LWN_Copy_Tree(WN_kid1(store),TRUE,LNO_Info_Map);
00288   LWN_Copy_Def_Use(WN_kid1(store),array1,Du_Mgr);
00289   WN *array2 = LWN_Copy_Tree(WN_kid1(store),TRUE,LNO_Info_Map);
00290   LWN_Copy_Def_Use(WN_kid1(store),array2,Du_Mgr);
00291 
00292   // load the array at the split point
00293   WN *split_point_parent = LWN_Get_Parent(split_point);
00294   TY_IDX addr_type = WN_ty(store);
00295   TY_IDX el_type = TY_pointed(addr_type);
00296   TYPE_ID mtype = WN_desc(store);
00297   OPCODE l_opcode = OPCODE_make_op(OPR_ILOAD,Promote_Type(mtype),mtype);
00298 #ifndef KEY
00299   WN *load = 
00300     LWN_CreateIload(l_opcode,WN_offset(store),el_type,addr_type,array1);
00301 #else
00302   WN *load = 
00303     LWN_CreateIload(l_opcode,WN_offset(store),el_type,addr_type,array1, 
00304         WN_field_id(store));
00305 #endif /* KEY */
00306   Copy_alias_info(Alias_Mgr,store,load);
00307   LWN_Set_Parent(load,split_point_parent);
00308   INT i=0;
00309   while (WN_kid(split_point_parent,i) != split_point) i++;
00310   WN_kid(split_point_parent,i) = load;
00311   if (dep_graph->Add_Deps_To_Copy_Block(WN_kid1(store),array1,FALSE)==0) {
00312      LNO_Erase_Dg_From_Here_In(load,dep_graph);
00313      if (red_manager) 
00314        red_manager->Erase(store);
00315      return 0;
00316   }
00317 
00318   // store the code below split_point into the array
00319 #ifndef KEY
00320   WN *new_store = LWN_CreateIstore(WN_opcode(store),WN_offset(store),
00321   WN_ty(store),split_point,array2);
00322 #else
00323   WN *new_store = LWN_CreateIstore(WN_opcode(store),WN_offset(store),
00324   WN_ty(store),split_point,array2, WN_field_id(store));
00325 #endif /* KEY */
00326   Copy_alias_info(Alias_Mgr,store,new_store);
00327   LWN_Copy_Linenumber(store,new_store);
00328   LWN_Insert_Block_Before(LWN_Get_Parent(store),store,new_store);
00329   if (dep_graph->Add_Deps_To_Copy_Block(WN_kid1(store),array2,FALSE)==0) {
00330      LNO_Erase_Dg_From_Here_In(new_store,dep_graph);
00331      if (red_manager) { 
00332        red_manager->Erase(store);
00333        red_manager->Erase(new_store);
00334      } 
00335      return 0;
00336   }
00337 
00338   // fix the array dependence graph
00339   BOOL not_overflow;
00340   VINDEX16 new_sv = dep_graph->Add_Vertex(new_store);
00341   // Is_True(new_sv,("Graph overflow in Split_Array \n"));
00342   if (!new_sv) {
00343      LNO_Erase_Dg_From_Here_In(new_store,dep_graph);
00344      if (red_manager) { 
00345        red_manager->Erase(store);
00346        red_manager->Erase(new_store);
00347      } 
00348      return 0;
00349   }
00350   VINDEX16 new_lv = dep_graph->Add_Vertex(load);
00351   // Is_True(new_lv,("Graph overflow in Split_Array \n"));
00352   if (!new_lv) {
00353      LNO_Erase_Dg_From_Here_In(load,dep_graph);
00354      if (red_manager) { 
00355        red_manager->Erase(store);
00356        red_manager->Erase(new_store);
00357      } 
00358      return 0;
00359   }
00360 
00361   // new store gets all the dependences from old store
00362   // load gets the same dependences except not the load-load
00363 
00364   VINDEX16 store_v = dep_graph->Get_Vertex(store);
00365   EINDEX16 e = dep_graph->Get_Out_Edge(store_v);
00366   while (e) {
00367     VINDEX16 sink = dep_graph->Get_Sink(e);
00368     if (sink != store_v) {
00369       not_overflow = dep_graph->Add_Edge(new_sv,sink,
00370     Create_DEPV_ARRAY(dep_graph->Depv_Array(e),&LNO_default_pool));
00371       // Is_True(not_overflow,("Graph overflow in Split_Array \n"));
00372       if (!not_overflow) {
00373          LNO_Erase_Dg_From_Here_In(store,dep_graph);
00374          if (red_manager) { 
00375      red_manager->Erase(store);
00376      red_manager->Erase(new_store);
00377          } 
00378          return 0;
00379       }
00380       if (!OPCODE_is_load(WN_opcode(dep_graph->Get_Wn(sink)))) {
00381         not_overflow = dep_graph->Add_Edge(new_lv,sink,
00382     Create_DEPV_ARRAY(dep_graph->Depv_Array(e),&LNO_default_pool));
00383         // Is_True(not_overflow,("Graph overflow in Split_Array \n"));
00384         if (!not_overflow) {
00385            LNO_Erase_Dg_From_Here_In(store,dep_graph);
00386            if (red_manager) { 
00387        red_manager->Erase(store);
00388        red_manager->Erase(new_store);
00389            } 
00390            return 0;
00391         }
00392       }
00393     }
00394     e = dep_graph->Get_Next_Out_Edge(e);
00395   }
00396 
00397   e = dep_graph->Get_In_Edge(store_v);
00398   while (e) {
00399     VINDEX16 source = dep_graph->Get_Source(e);
00400     if (source != store_v) {
00401       not_overflow = dep_graph->Add_Edge(source, new_sv,
00402     Create_DEPV_ARRAY(dep_graph->Depv_Array(e),&LNO_default_pool));
00403       // Is_True(not_overflow,("Graph overflow in Split_Array \n"));
00404       if (!not_overflow) {
00405         LNO_Erase_Dg_From_Here_In(store,dep_graph);
00406         if (red_manager) { 
00407     red_manager->Erase(store);
00408     red_manager->Erase(new_store);
00409   } 
00410         return 0;
00411       }
00412       if (!OPCODE_is_load(WN_opcode(dep_graph->Get_Wn(source)))) {
00413         not_overflow = dep_graph->Add_Edge(source, new_lv,
00414     Create_DEPV_ARRAY(dep_graph->Depv_Array(e),&LNO_default_pool));
00415         // Is_True(not_overflow,("Graph overflow in Split_Array \n"));
00416         if (!not_overflow) {
00417           LNO_Erase_Dg_From_Here_In(store,dep_graph);
00418           if (red_manager) { 
00419       red_manager->Erase(store);
00420       red_manager->Erase(new_store);
00421           } 
00422           return 0;
00423         }
00424       }
00425     }
00426     e = dep_graph->Get_Next_In_Edge(e);
00427   }
00428 
00429 
00430   // get all the cross dependences
00431   WN *inner = Find_Inner(store);
00432   INT depth = Do_Loop_Depth(inner);
00433   INT good_depth = Good_Do_Depth(store);
00434   INT num_bad = depth - good_depth;
00435 
00436   EINDEX16 self_e = dep_graph->Get_Edge(store_v,store_v);
00437   if (!self_e) {
00438     DEPV_ARRAY *zero = Create_DEPV_ARRAY(1,good_depth+1,num_bad,
00439             &LNO_default_pool);
00440     for (INT ii=0; ii<=good_depth; ii++) {
00441       DEPV_Dep(zero->Depv(0),ii) = DEP_SetDirection(DIR_EQ);
00442     }
00443     DEPV_ARRAY *zero2 = Create_DEPV_ARRAY(zero,&LNO_default_pool);
00444     DEPV_ARRAY *zero3 = Create_DEPV_ARRAY(zero,&LNO_default_pool);
00445 
00446     not_overflow = dep_graph->Add_Edge(new_sv,store_v,zero);
00447     not_overflow = not_overflow && dep_graph->Add_Edge(new_sv,new_lv,zero2);
00448     not_overflow = not_overflow && dep_graph->Add_Edge(new_lv,store_v,zero3);
00449   } else {
00450     DEPV_ARRAY *self_dep = dep_graph->Depv_Array(self_e);
00451     DEPV *tmp_dep = DEPV_Create(&LNO_local_pool,good_depth+1);
00452     for (INT ii=0; ii<=good_depth; ii++) {
00453       DEPV_Dep(tmp_dep,ii) = DEP_SetDirection(DIR_EQ);
00454     }
00455     DEPV_LIST *tmp = CXX_NEW(DEPV_LIST(self_dep,&LNO_local_pool),
00456   &LNO_local_pool);
00457     tmp->Append(CXX_NEW(DEPV_NODE(tmp_dep),&LNO_local_pool));
00458 
00459     not_overflow = dep_graph->Add_Edge(new_sv,new_sv,
00460   Create_DEPV_ARRAY(self_dep,&LNO_default_pool));
00461     not_overflow = not_overflow && dep_graph->Add_Edge(store_v,new_sv,
00462   Create_DEPV_ARRAY(self_dep,&LNO_default_pool));
00463     not_overflow = not_overflow && dep_graph->Add_Edge(new_sv,store_v,
00464   Create_DEPV_ARRAY(tmp,&LNO_default_pool));
00465     not_overflow = not_overflow && dep_graph->Add_Edge(new_lv,new_sv,
00466   Create_DEPV_ARRAY(self_dep,&LNO_default_pool));
00467     not_overflow = not_overflow && dep_graph->Add_Edge(new_sv,new_lv,
00468   Create_DEPV_ARRAY(tmp,&LNO_default_pool));
00469     not_overflow = not_overflow && dep_graph->Add_Edge(store_v,new_lv,
00470   Create_DEPV_ARRAY(self_dep,&LNO_default_pool));
00471     not_overflow = not_overflow && dep_graph->Add_Edge(new_lv,store_v,
00472   Create_DEPV_ARRAY(tmp,&LNO_default_pool));
00473   }
00474 
00475   // Is_True(not_overflow,("Graph overflow in Split_Array \n"));
00476   if (!not_overflow) {
00477     LNO_Erase_Dg_From_Here_In(store,dep_graph);
00478     if (red_manager) { 
00479       red_manager->Erase(store);
00480       red_manager->Erase(new_store);
00481     } 
00482     return 0;
00483   }
00484 
00485 
00486   // recalculate reductions
00487   if (red_manager && (red_manager->Which_Reduction(store) != RED_NONE)) {
00488     red_manager->Erase(store);
00489     red_manager->Erase(new_store);
00490     red_manager->Build(store,TRUE,TRUE,dep_graph);
00491     red_manager->Build(new_store,TRUE,TRUE,dep_graph);
00492   }
00493 
00494 
00495   // recurse on two split statements if we need to
00496   if (Need_To_Split(new_store)) {
00497     Split_Statement(new_store,dep_graph);
00498   }
00499 
00500 #if 0
00501   // this is basically gratuitous recursion
00502   if (Need_To_Split(store)) {
00503     Split_Statement(store,dep_graph);
00504   }
00505 #endif
00506 
00507   return 1;
00508 
00509 }
00510 
00511 
00512 // Split by creating a new preg for the temp value
00513 // this is always safe
00514 //
00515 // return the new statment created
00516 extern WN *Split_Using_Preg(WN *statement, WN *split_point,
00517         ARRAY_DIRECTED_GRAPH16 *dep_graph,
00518                                 BOOL recursive)
00519 {
00520   // create a new preg
00521   OPCODE store_opcode = WN_opcode(statement);
00522   OPCODE split_opcode = WN_opcode(split_point);
00523   TYPE_ID type = OPCODE_rtype(split_opcode);
00524   ST *preg_st = MTYPE_To_PREG(type);
00525   const char *orig_name;
00526   if (OPCODE_operator(store_opcode) == OPR_STID) {
00527     orig_name = ST_name(WN_st(statement));
00528   } else if ((WN_operator(WN_kid1(statement)) == OPR_ARRAY) &&
00529        (OPCODE_has_sym(WN_opcode(WN_array_base(WN_kid1(statement)))))) {
00530     orig_name = ST_name(WN_st(WN_array_base(WN_kid1(statement))));
00531   } else {
00532     orig_name = "blank";
00533   }
00534   char new_name[20]; 
00535   INT length = strlen(orig_name);
00536   WN_OFFSET preg_num;
00537   if (length < 18) {
00538     strcpy(new_name,orig_name);
00539     new_name[length] = '_';
00540     new_name[length+1] = '1';
00541     new_name[length+2] = 0;
00542 #ifdef _NEW_SYMTAB
00543     preg_num = Create_Preg(type,new_name);
00544   } else {
00545     preg_num = Create_Preg(type,NULL);
00546   }
00547 #else
00548     preg_num = Create_Preg(type,new_name, NULL);
00549   } else {
00550     preg_num = Create_Preg(type,NULL,NULL);
00551   }
00552 #endif
00553 
00554   // load the preg at split point
00555   WN *split_point_parent = LWN_Get_Parent(split_point);
00556   OPCODE preg_l_opcode = OPCODE_make_op(OPR_LDID,Promote_Type(type),type);
00557   WN *preg_load = WN_CreateLdid(preg_l_opcode,preg_num,preg_st,
00558             Be_Type_Tbl(type));
00559   LWN_Set_Parent(preg_load,split_point_parent);
00560   INT i=0;
00561   while (WN_kid(split_point_parent,i) != split_point) i++;
00562   WN_kid(split_point_parent,i) = preg_load;
00563 
00564   // store the preg before the store
00565   OPCODE preg_s_opcode = OPCODE_make_op(OPR_STID,MTYPE_V,type);
00566   WN *preg_store = LWN_CreateStid(preg_s_opcode,
00567                                   preg_num,preg_st,
00568                                   Be_Type_Tbl(type),split_point);
00569   LWN_Copy_Linenumber(statement,preg_store);
00570   LWN_Insert_Block_Before(LWN_Get_Parent(statement),statement,preg_store);
00571   // in case the expression that we stored is an address...
00572   WN_set_st_addr_saved(split_point);
00573 
00574   // Fix up the du
00575   Du_Mgr->Add_Def_Use(preg_store,preg_load);
00576 
00577 
00578   // recalculate reductions
00579   if (red_manager && (red_manager->Which_Reduction(statement) != RED_NONE)) {
00580     red_manager->Erase(statement);
00581     red_manager->Erase(preg_store);
00582     red_manager->Build(statement,TRUE,TRUE,dep_graph);
00583     // preg_store can't be a reduction
00584   }
00585 
00586   // recurse on two split statements if we need to
00587   if (recursive &&
00588       WN_kid_count(split_point_parent) > 1 &&   // only if we created
00589                                                 // something simpler
00590       Need_To_Split(preg_store)) {
00591     Split_Statement(preg_store,dep_graph);
00592   }
00593 
00594   if (recursive && Need_To_Split(statement)) {
00595     Split_Statement(statement,dep_graph);
00596   }
00597   return preg_store;
00598 }
00599 
00600 // Return true if
00601 // 1. The store is a cleanly variant array reference
00602 // 2. Other than underneath the split point there is no all equals dependent
00603 //    load to the store 
00604 // it's always conservative to return FALSE
00605 extern BOOL Variant_Array(WN *store, WN *split_point, 
00606         ARRAY_DIRECTED_GRAPH16 *dep_graph)
00607 {
00608   if (WN_operator(store) != OPR_ISTORE) return FALSE;
00609 
00610   // check the array
00611   if (WN_kid_count(store) != 2) return FALSE;
00612   WN *array = WN_kid1(store);
00613   if (WN_operator(array) != OPR_ARRAY) return FALSE;
00614 
00615   ACCESS_ARRAY *aa = (ACCESS_ARRAY *) WN_MAP_Get(LNO_Info_Map,array);
00616   if (aa->Too_Messy) return FALSE;
00617 
00618   WN *inner = Find_Inner(store);
00619   if (!Do_Loop_Is_Good(inner) || Do_Loop_Has_Gotos(inner)) return FALSE;
00620   INT depth = Do_Loop_Depth(inner);
00621 
00622   BOOL seen_var = FALSE;
00623   for (INT i=0; i<aa->Num_Vec(); i++) {
00624     ACCESS_VECTOR *av = aa->Dim(i);
00625     if (av->Too_Messy || (av->Non_Const_Loops() == (depth+1))) return FALSE;
00626     if (av->Delinearized_Symbol)
00627       return FALSE; 
00628     if (av->Loop_Coeff(depth)) seen_var=TRUE;
00629   }
00630   if (!seen_var) return FALSE;
00631 
00632   // now the array is the right form, check for dependences from any 
00633   // load under store but not under split_point to the store
00634   VINDEX16 v = dep_graph->Get_Vertex(store);
00635   if (!v) return FALSE;
00636   EINDEX16 e;
00637   for (e=dep_graph->Get_In_Edge(v); e; e=dep_graph->Get_Next_In_Edge(e)) {
00638     if (dep_graph->Depv_Array(e)->Max_Level() > depth) {
00639       WN *source_wn = dep_graph->Get_Wn(dep_graph->Get_Source(e));
00640       if (Is_Descendent(source_wn,store) && 
00641     !Is_Descendent(source_wn,split_point)) {
00642         return FALSE;
00643       }
00644     }
00645   }
00646 
00647   // now make sure none of the scalars are aliased to the store
00648   // this is extremely unlikely but we have to be sure
00649   if (Scalar_Interferes(store,WN_kid0(store),split_point,dep_graph)) {
00650     return FALSE;
00651   }
00652   return TRUE;
00653 }
00654 
00655 
00656 
00657 // do any of the scalars under expr alias with store (ignore things under
00658 // the split point), we need to check these explicitly since they're not
00659 // in the array dependence graph
00660 static BOOL Scalar_Interferes(WN *store, WN *expr, WN *split_point,
00661         ARRAY_DIRECTED_GRAPH16 *dep_graph) 
00662 {
00663   if (expr == split_point) {
00664     return FALSE;
00665   }
00666 
00667   if (OPCODE_is_load(WN_opcode(expr))) {
00668     VINDEX16 v = dep_graph->Get_Vertex(expr);
00669     if (v) return FALSE; // we've already checked this one
00670     return (Aliased(Alias_Mgr,store,expr) != NOT_ALIASED);
00671   } else {
00672     for (INT kidno=0; kidno < WN_kid_count(expr); kidno++) {
00673       if (Scalar_Interferes(store,WN_kid(expr,kidno),split_point,dep_graph)) {
00674   return TRUE;
00675       }
00676     }
00677     return FALSE;
00678   }
00679 }
00680 
00681 
00682 
00683 // find the innermost do loop surrounding this statement
00684 // assumes there is one
00685 static WN *Find_Inner(WN *wn)
00686 {
00687   while (WN_opcode(wn) != OPC_DO_LOOP) wn = LWN_Get_Parent(wn);
00688   return wn;
00689 }
00690   
00691 
00692 
00693 // Given a statement, find a reasonable point to split it
00694 // Return the root of the subtree that should be split
00695 //
00696 // Our goal is that both sides of the split be about the same size
00697 // we accomplish this by searching bottom up until we hit a subtree with 
00698 // about half the leaves
00699 static WN *Find_Split_Point(WN *store)
00700 {
00701   WN *rhs = WN_kid0(store);
00702   INT enough_leaves = (Num_Leaves_Or_Arrays(rhs) >> 1) ;
00703   INT tmp;
00704   WN *result = Find_Enough_Subtree(rhs,enough_leaves,&tmp);
00705   if (WN_operator(result) == OPR_PARM) {
00706     result = WN_kid0(result); // don't split a parm
00707   }
00708   if (WN_operator(result) == OPR_ARRAY &&
00709       WN_operator(LWN_Get_Parent(result)) == OPR_ILOAD) {
00710     // don't split underneath an ILOAD either; causes unnecessary address-save
00711     result = LWN_Get_Parent(result);
00712   }
00713   return result;
00714 }
00715 
00716 // how many leaves or arrays in this expression node (can't be an hcf node)
00717 static INT Num_Leaves_Or_Arrays(WN *wn)
00718 {
00719   if ((WN_kid_count(wn) == 0) ||
00720       (WN_operator(wn) == OPR_ARRAY)) {
00721     return 1;
00722   } 
00723   INT result = 0;
00724   for (INT kidno=0; kidno<WN_kid_count(wn); kidno++) {
00725     result += Num_Leaves_Or_Arrays(WN_kid(wn,kidno));
00726   }
00727   return result;
00728 }
00729 
00730 // Searching bottom up, find the first subtree that contains at least
00731 // "enough" leaves or arrays
00732 // on exit, set *num_leaves to the number of leaves/arrays under this tree
00733 static WN *Find_Enough_Subtree(WN *wn, INT enough, INT *num_leaves)
00734 {
00735   *num_leaves = 0;
00736   if ((WN_kid_count(wn) == 0) ||
00737       (WN_operator(wn) == OPR_ARRAY)) {
00738     *num_leaves = 1;
00739     return wn;
00740   } 
00741 
00742   INT temp = 0;
00743   WN *result;
00744   for (INT kidno=0; kidno<WN_kid_count(wn); kidno++) {
00745     result = Find_Enough_Subtree(WN_kid(wn,kidno),enough, &temp);
00746     if (temp >= enough) {
00747       *num_leaves = temp;
00748       return result;
00749     } else {
00750       *num_leaves += temp;
00751     }
00752   }
00753   return wn;
00754 }
00755