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

00001 /*
00002  * Copyright 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 //-*-c++-*-
00041 //                     Reductions
00042 //                     ----------
00043 //
00044 // Description:
00045 //
00046 //  Mark reductions.  We use an algorithm similar to SUIF's and Polaris's.
00047 //  We look at each store in the program.  It is a reduction if
00048 //  it's of the form a(x) = a(x) op ..., where op is a reducion operation,
00049 //  x is anything or nothing and nothing in 'x' aliases 'a' (although 
00050 //  'a' may be aliased with anything in '...').
00051 //
00052 //  If it is a reduction, we annotation both the load and the store
00053 //  with the type.
00054 //
00055 
00056 /* ====================================================================
00057  * ====================================================================
00058  *
00059  * Module: redic.cxx
00060  * $Revision: 1.5 $
00061  * $Date: 04/12/21 14:57:15-08:00 $
00062  * $Author: bos@eng-25.internal.keyresearch.com $
00063  * $Source: /home/bos/bk/kpro64-pending/be/lno/SCCS/s.reduc.cxx $
00064  *
00065  * Revision history:
00066  *  dd-mmm-94 - Original Version
00067  *
00068  * Description: Model time taken by inner loops
00069  *
00070  * ====================================================================
00071  * ====================================================================
00072  */
00073 
00074 #ifdef USE_PCH
00075 #include "lno_pch.h"
00076 #endif // USE_PCH
00077 #pragma hdrstop
00078 
00079 const static char *source_file = __FILE__;
00080 const static char *rcs_id = "$Source: /home/bos/bk/kpro64-pending/be/lno/SCCS/s.reduc.cxx $ $Revision: 1.5 $";
00081 
00082 #include <sys/types.h>
00083 #include "reduc.h"
00084 #include "stab.h"
00085 #include "lnoutils.h"
00086 #include "lwn_util.h"
00087 #include "lnopt_main.h"
00088 
00089 OPERATOR REDUCTION_TYPE_to_OPERATOR(REDUCTION_TYPE red_type)
00090 {
00091   switch (red_type) {
00092   case RED_ADD:
00093     return OPR_ADD;
00094   case RED_MPY:
00095     return OPR_MPY;
00096   case RED_MIN:
00097     return OPR_MIN;
00098   case RED_MAX:
00099     return OPR_MAX;
00100   case RED_NONE:
00101     break;
00102   default:
00103     Fail_FmtAssertion("REDUCTION_TYPE_to_OPERATOR: bogus red_type %d",
00104                       red_type);
00105   }
00106   return OPERATOR_UNKNOWN;
00107 }
00108 
00109 // Find all the stores
00110 void REDUCTION_MANAGER::Build(WN *wn,BOOL build_scalar, BOOL build_array,
00111       class ARRAY_DIRECTED_GRAPH16 *dep_graph)
00112 {
00113   _build_scalar = build_scalar;
00114   _build_array = build_array;
00115   Is_True((!build_array) || dep_graph,
00116   ("Null dep_graph in REDUCTION_MANAGER::Build"));
00117   _dep_graph = dep_graph;
00118   Build(wn);
00119 }
00120 
00121 void REDUCTION_MANAGER::Build(WN *wn)
00122 {
00123   OPCODE opcode = WN_opcode(wn);
00124 
00125   if (OPCODE_is_store(opcode)) {
00126     OPERATOR oper = OPCODE_operator(opcode);
00127     if ((_build_scalar && (oper == OPR_STID)) ||
00128   (_build_array && (oper != OPR_STID))) {
00129       Check_Store(wn);
00130     }
00131   } else if (opcode == OPC_BLOCK) {
00132     WN *kid = WN_first (wn);
00133     while (kid) {
00134       Build(kid);
00135       kid = WN_next(kid);
00136     }
00137   } else if (OPCODE_is_scf(opcode)) {
00138     for (INT kidno=0; kidno<WN_kid_count(wn); kidno++) {
00139       WN *kid = WN_kid(wn,kidno);
00140       Build(kid);
00141     }
00142   }
00143 }
00144 
00145 // Process a store
00146 void REDUCTION_MANAGER::Check_Store(WN *store)
00147 {
00148   // first check that the operation is a reduction type
00149   REDUCTION_TYPE type = RED_NONE;
00150 
00151   WN *rhs = WN_kid0(store);
00152   OPERATOR oper = WN_operator(rhs);
00153 
00154   switch(oper) {
00155     case OPR_ADD: case OPR_SUB:
00156       type = RED_ADD;
00157       break;
00158     case OPR_MPY: 
00159 #ifdef KEY
00160     case OPR_DIV:
00161 #endif
00162       type = RED_MPY;
00163       break;
00164     case OPR_MAX:
00165       type = RED_MAX;
00166       break;
00167     case OPR_MIN:
00168       type = RED_MIN;
00169       break;
00170     default: return; // not a reduction operator
00171   }
00172 
00173   // next check that the lhs is equivalent to one of the children of the 
00174   // right hand side (if it's a minus, it has to be equivalent to the first
00175   // child of the right hand side)
00176 
00177   WN *match_ld; // the wn of the kid that matches the store
00178 
00179   match_ld = Find_Match(store,WN_opcode(rhs),rhs);
00180   if (match_ld)  {
00181     if (!Self_Dependent_Store(store)) {
00182       WN_MAP32_Set(_map,store,(INT32) type);
00183       WN_MAP32_Set(_map,match_ld,(INT32) type);
00184     }
00185   }
00186 }
00187 
00188 // Find a load to the same location as store, keep looking as deep as
00189 // possible
00190 WN *REDUCTION_MANAGER::Find_Match(WN *store,OPCODE rhs_opcode, WN *rhs) {
00191   WN *kid0 = WN_kid0(rhs);
00192 
00193 #ifndef KEY
00194   if (OPCODE_operator(rhs_opcode) == OPR_SUB) {
00195 #else
00196   if (OPCODE_operator(rhs_opcode) == OPR_SUB || 
00197       OPCODE_operator(rhs_opcode) == OPR_DIV) {
00198 #endif
00199     if (Opcode_Match(WN_opcode(kid0), rhs_opcode)) { // recurse
00200       return Find_Match(store,rhs_opcode,kid0);
00201     } else if (Match(store,kid0)) {
00202       return kid0;
00203     } else {
00204       return NULL;
00205     }
00206   } else {
00207     if (Opcode_Match(WN_opcode(kid0), rhs_opcode)) { // recurse
00208       WN *result = Find_Match(store,rhs_opcode,kid0);
00209       if (result) {  // found a match
00210   return result;
00211       }
00212     }
00213     if (Match(store,kid0)) {
00214       return kid0;
00215     }
00216     WN *kid1 = WN_kid1(rhs);
00217     if (Opcode_Match(WN_opcode(kid1), rhs_opcode)) { // recurse
00218       WN *result = Find_Match(store,rhs_opcode,kid1);
00219       if (result) {  // found a match
00220   return result;
00221       }
00222     }
00223     if (Match(store,kid1)) {
00224       return kid1;
00225     }
00226   }
00227   return NULL;
00228 }
00229 
00230 
00231 // is value a load to the same location we're storing in store
00232 BOOL REDUCTION_MANAGER::Match(WN *store, WN *value) const
00233 {
00234   OPERATOR st_oper = WN_operator(store);
00235   OPERATOR value_oper = WN_operator(value);
00236 
00237   if (st_oper == OPR_STID) {  // value has to be an ldid of the same loc
00238     return((value_oper == OPR_LDID) && 
00239      (WN_offset(store) == WN_offset(value)) &&
00240      (ST_base(WN_st(store)) == ST_base(WN_st(value))) &&
00241      (ST_ofst(WN_st(store)) == ST_ofst(WN_st(value))));
00242   } else if (st_oper == OPR_ISTORE) {
00243     return((value_oper == OPR_ILOAD) && 
00244      (WN_offset(store) == WN_offset(value)) &&
00245      Equiv(WN_kid1(store),WN_kid0(value)));
00246   } else {
00247     return (FALSE); // we don't do the other types of stores for now
00248   }
00249 }
00250 
00251 // are the two expressions subtrees equivalent
00252 BOOL REDUCTION_MANAGER::Equiv(WN *wn1, WN *wn2) const
00253 {
00254   if (!WN_Equiv(wn1,wn2)) return(FALSE);
00255   for (INT kidno=0; kidno<WN_kid_count(wn1); kidno++) {
00256     if (!Equiv(WN_kid(wn1,kidno),WN_kid(wn2,kidno))) {
00257       return(FALSE);
00258     }
00259   }
00260   return(TRUE);
00261 }
00262 
00263 // is the store self dependent
00264 // i.e. is it something like a[a[i]] = ...
00265 BOOL REDUCTION_MANAGER::Self_Dependent_Store(WN *store) const
00266 {
00267   OPERATOR oper = WN_operator(store);
00268   if (oper == OPR_STID) {
00269     return(FALSE);
00270   } else if (oper == OPR_ISTORE) {
00271     if (Unmapped_Vertices(WN_kid1(store))) {
00272       return(TRUE); // possilby self dependent
00273     }
00274     VINDEX16 store_vertex = _dep_graph->Get_Vertex(store);
00275     if (!store_vertex) {
00276       return(TRUE);
00277     }
00278     EINDEX16 e = _dep_graph->Get_In_Edge(store_vertex);
00279     while (e) {
00280       WN *wn = _dep_graph->Get_Wn( _dep_graph->Get_Source(e));
00281       if ((wn != store) && Is_Descendent_Of_Store_Address(store,wn)) {
00282   return(TRUE);
00283       }
00284       e = _dep_graph->Get_Next_In_Edge(e);
00285     }
00286     e = _dep_graph->Get_Out_Edge(store_vertex);
00287     while (e) {
00288       WN *wn = _dep_graph->Get_Wn( _dep_graph->Get_Sink(e));
00289       if ((wn != store) && Is_Descendent_Of_Store_Address(store,wn)) {
00290   return(TRUE);
00291       }
00292       e = _dep_graph->Get_Next_Out_Edge(e);
00293     }
00294   } else {
00295     return(TRUE);
00296   }
00297   return(FALSE);
00298 }
00299 
00300 // are there any loads here that aren't mapped in the dependence graph
00301 BOOL REDUCTION_MANAGER::Unmapped_Vertices(WN *wn) const
00302 {
00303   OPCODE opcode = WN_opcode(wn);
00304   if (OPCODE_is_load(opcode) && (OPCODE_operator(opcode) != OPR_LDID)) {
00305     if (!_dep_graph->Get_Vertex(wn)) {
00306       return(TRUE);
00307     }
00308   } 
00309   for (INT kidno=0; kidno<WN_kid_count(wn); kidno++) {
00310     WN *kid = WN_kid(wn,kidno);
00311     if (Unmapped_Vertices(kid)) {
00312       return(TRUE);
00313     }
00314   }
00315   return(FALSE);
00316 }
00317 
00318 // Is wn a descendant of the store's address
00319 BOOL REDUCTION_MANAGER::Is_Descendent_Of_Store_Address(WN *store,WN *wn) const
00320 {
00321   while (OPCODE_is_expression(WN_opcode(wn))) {
00322     if (wn == WN_kid1(store)) {
00323       return(TRUE);
00324     }
00325     wn = LWN_Get_Parent(wn);
00326   }
00327   return FALSE;
00328 }
00329 
00330 void REDUCTION_MANAGER::Erase_Node(WN* wn)
00331 {
00332   OPCODE opcode = WN_opcode(wn);
00333   if (OPCODE_is_store(opcode) || OPCODE_is_load(opcode)) {
00334     if (Which_Reduction(wn) != RED_NONE) {
00335       WN_MAP32_Set(_map,wn,(INT32) RED_NONE);
00336     }
00337   }
00338 }
00339 
00340 // Erase all the reductions in the tree rooted at wn
00341 void REDUCTION_MANAGER::Erase(WN *wn)
00342 {
00343   OPCODE opcode = WN_opcode(wn);
00344 
00345   if (opcode == OPC_BLOCK) {
00346     WN *kid = WN_first (wn);
00347     while (kid) {
00348       Erase(kid);
00349       kid = WN_next(kid);
00350     }
00351     return;
00352   } else {
00353     Erase_Node(wn);
00354     for (INT kidno=0; kidno<WN_kid_count(wn); kidno++) {
00355       Erase(WN_kid(wn,kidno));
00356     }
00357   }
00358 }
00359 
00360 void REDUCTION_MANAGER::Unroll_Update_Rec(WN **bodies, UINT u)
00361 {
00362   if (bodies[0]) {
00363     OPCODE  opc = WN_opcode(bodies[0]);
00364     OPERATOR  opr = OPCODE_operator(opc);
00365 
00366     if (OPCODE_is_store(opc) || OPCODE_is_load(opc)) {
00367       REDUCTION_TYPE type = Which_Reduction(bodies[0]);
00368       if (type != RED_NONE) {
00369   for (INT i=1; i<u; i++) {
00370     WN_MAP32_Set(_map,bodies[i],(INT32) type);
00371   }
00372       }
00373     }
00374 
00375     if (opr == OPR_BLOCK) {
00376       WN **new_bodies = CXX_NEW_ARRAY(WN *,u,&LNO_local_pool);
00377       for (INT i=0; i<u; i++) {
00378         new_bodies[i] = WN_first(bodies[i]);
00379       }
00380       while (new_bodies[0]) {
00381         Unroll_Update_Rec(new_bodies, u);
00382         for (INT i=0; i<u; i++) {
00383           new_bodies[i] = WN_next(new_bodies[i]);
00384         }
00385       }
00386     } else if (WN_kid_count(bodies[0])) {
00387       WN **new_bodies = CXX_NEW_ARRAY(WN *,u,&LNO_local_pool);
00388       for (INT kidno=0; kidno<WN_kid_count(bodies[0]); kidno++) {
00389         for (INT i=0; i<u; i++) {
00390           new_bodies[i] = WN_kid(bodies[i],kidno);
00391         }
00392         Unroll_Update_Rec(new_bodies, u);
00393       }
00394     }
00395   }
00396 }
00397 
00398 void REDUCTION_MANAGER::Unroll_Update(WN **bodies, UINT u)
00399 {
00400   MEM_POOL_Push(&LNO_local_pool);
00401   Unroll_Update_Rec(bodies,u);
00402   MEM_POOL_Pop(&LNO_local_pool);
00403 }
00404 
00405