Open64: osprey/be/lno/reverse.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 #ifdef USE_PCH
00041 #include "lno_pch.h"
00042 #endif // USE_PCH
00043 #pragma hdrstop
00044 
00045 #ifdef _KEEP_RCS_ID
00046 /*REFERENCED*/
00047 static char *rcs_id = "$Source: /home/bos/bk/kpro64-pending/be/lno/SCCS/s.reverse.cxx $ $Revision: 1.5 $";
00048 #endif /* _KEEP_RCS_ID */
00049 
00050 #include <sys/types.h>
00051 
00052 #include "lnoutils.h"
00053 #include "lnopt_main.h"
00054 #include "stab.h"
00055 #include "targ_const.h"
00056 #include "wn_simp.h"
00057 #include "stdlib.h"
00058 #include "lwn_util.h"
00059 #include "strtab.h"
00060 #include "config.h"
00061 #include "optimizer.h"
00062 #include "opt_du.h"
00063 #include "name.h"
00064 #include "wintrinsic.h"
00065 #include "lno_bv.h"
00066 #include "dep_graph.h"
00067 #include "debug.h"
00068 #include "cxx_memory.h"
00069 #include "snl_utils.h"
00070 #include "reverse.h"
00071 
00072 static ARRAY_DIRECTED_GRAPH16* dg;
00073 static DU_MANAGER* du;
00074 
00075 //-----------------------------------------------------------------------
00076 // NAME: RV_Easy_Bounds 
00077 // FUNCTION: Returns TRUE if the bounds of loop 'wn_loop' are easy enough
00078 //   to do a simple loop reversal, FALSE otherwise. 
00079 // NOTE: Simple, in this case, means of the form: 
00080 //   do i = exp1; i <= exp2; i = i + exp3  
00081 //-----------------------------------------------------------------------
00082 
00083 static BOOL RV_Easy_Bounds(WN* wn_loop) 
00084 {
00085   WN* wn_start = WN_start(wn_loop); 
00086   if (WN_operator(wn_start) != OPR_STID)
00087     return FALSE; 
00088   if (SYMBOL(wn_start) != SYMBOL(WN_index(wn_loop)))
00089     return FALSE;  
00090   WN* wn_end = WN_end(wn_loop);
00091   OPERATOR opr = WN_operator(wn_end); 
00092   if (opr != OPR_GE && opr != OPR_GT && opr != OPR_LE && opr != OPR_LT)
00093     return FALSE;  
00094   WN* wn_index = SNL_UBvar(wn_end);  
00095   if (WN_operator(wn_index) != OPR_LDID) 
00096     return FALSE; 
00097   if (SYMBOL(wn_index) != SYMBOL(WN_index(wn_loop)))
00098     return FALSE;  
00099   WN* wn_step = WN_step(wn_loop); 
00100   if (WN_operator(wn_step) != OPR_STID)
00101     return FALSE; 
00102   if (SYMBOL(wn_step) != SYMBOL(WN_index(wn_loop)))
00103     return FALSE;  
00104   WN* wn_add = WN_kid0(wn_step); 
00105   if (WN_operator(wn_add) != OPR_ADD)
00106     return FALSE; 
00107   WN* wn_left = WN_kid0(wn_add); 
00108   if (WN_operator(wn_left) != OPR_LDID)
00109     return FALSE; 
00110   if (SYMBOL(wn_left) != SYMBOL(WN_index(wn_loop)))
00111     return FALSE;
00112   WN* wn_right = WN_kid1(wn_add); 
00113   if (WN_operator(wn_right) != OPR_INTCONST)
00114     return FALSE; 
00115   if (WN_const_val(wn_right) != 1) 
00116     return FALSE;  
00117   return TRUE; 
00118 }
00119 
00120 //-----------------------------------------------------------------------
00121 // NAME: RV_Scalar_Node_Legal 
00122 // FUNCTION: Returns TRUE if node 'wn' is a STID or LDID and does not 
00123 //   inhibit reversal of loop 'wn_loop' .  Also returns TRUE if the node  
00124 //   is not a STID or LDID.  Returns FALSE, otherwise.  
00125 //-----------------------------------------------------------------------
00126 
00127 static BOOL RV_Scalar_Node_Legal(WN* wn, 
00128                WN* wn_loop) 
00129 {
00130   if (WN_operator(wn) == OPR_STID) {
00131     if (dg->Get_Vertex(wn))
00132       return FALSE;
00133     for (WN* wn_tp = wn_loop; wn_tp != NULL; wn_tp = LWN_Get_Parent(wn_tp)) 
00134       if (WN_opcode(wn) == OPC_DO_LOOP 
00135     && SYMBOL(wn) == SYMBOL(WN_index(wn_tp)))
00136         return TRUE; 
00137     USE_LIST* use_list = du->Du_Get_Use(wn); 
00138     if (use_list == NULL) 
00139       return TRUE; 
00140     if (use_list->Incomplete())
00141       return FALSE; 
00142     USE_LIST_ITER iter(use_list);
00143     DU_NODE* node = NULL;
00144     for (node = iter.First(); !iter.Is_Empty(); node = iter.Next()) {
00145       WN* wn_use = node->Wn();
00146       if (!Wn_Is_Inside(wn_use, wn_loop))
00147   return FALSE; 
00148     }
00149   } else if (WN_operator(wn) == OPR_LDID) {
00150     if (dg->Get_Vertex(wn))
00151       return FALSE; 
00152     for (WN* wn_tp = wn_loop; wn_tp != NULL; wn_tp = LWN_Get_Parent(wn_tp)) 
00153       if (WN_opcode(wn_tp) == OPC_DO_LOOP 
00154     && SYMBOL(wn) == SYMBOL(WN_index(wn_tp)))
00155         return TRUE;
00156     DEF_LIST *def_list = du->Ud_Get_Def(wn);
00157     if (def_list == NULL) 
00158       return TRUE; 
00159     if (def_list->Incomplete()) {
00160       DEF_LIST_ITER iter(def_list); 
00161       DU_NODE* node = NULL;
00162       for (node = iter.First(); !iter.Is_Empty(); node = iter.Next()) {
00163         WN* wn_def = node->Wn();
00164         if (Wn_Is_Inside(wn_def, wn_loop))
00165           return FALSE;
00166       }
00167     } else {
00168       if (def_list->Loop_stmt() != NULL 
00169     && (!Wn_Is_Inside(def_list->Loop_stmt(), wn_loop)
00170     || def_list->Loop_stmt() == wn_loop))
00171   return FALSE;
00172     }
00173   }
00174   return TRUE;    
00175 }   
00176   
00177 //-----------------------------------------------------------------------
00178 // NAME: RV_Scalar_Legal 
00179 // FUNCTION: Returns TRUE if the expression rooted at 'wn' does not contain
00180 //   scalars which inhibit loop reversal.  Returns FALSE, otherwise.  
00181 //-----------------------------------------------------------------------
00182 
00183 static BOOL RV_Scalar_Legal(WN* wn, 
00184                 WN* wn_loop)
00185 {
00186   if (!RV_Scalar_Node_Legal(wn, wn_loop))
00187     return FALSE; 
00188 
00189   if (WN_opcode(wn) == OPC_BLOCK) {
00190     for (WN* wn_tp = WN_first(wn); wn_tp != NULL; wn_tp = WN_next(wn_tp))
00191       if (!RV_Scalar_Legal(wn_tp, wn_loop))
00192         return FALSE; 
00193   } else {
00194     for (INT i = 0; i < WN_kid_count(wn); i++) {
00195       if (!RV_Scalar_Legal(WN_kid(wn, i), wn_loop))
00196   return FALSE; 
00197     }
00198   }
00199   return TRUE; 
00200 }
00201 
00202 //-----------------------------------------------------------------------
00203 // NAME: RV_Depv_Is_Reversable 
00204 // FUNCTION: Returns TRUE if the 'array_index'th dependence vector in 
00205 //   'depv_array' can have its component corresponding to loop 'wn_loop'
00206 //   reversed without becoming lexicographically negative.  Returns 
00207 //   FALSE otherwise.  
00208 //-----------------------------------------------------------------------
00209 
00210 static BOOL RV_Depv_Is_Reversable(DEPV_ARRAY* depv_array,
00211           INT array_index,  
00212           WN* wn_loop) 
00213 {
00214   DO_LOOP_INFO* dli = Get_Do_Loop_Info(wn_loop); 
00215   INT dep_index = dli->Depth - depv_array->Num_Unused_Dim(); 
00216   DEPV* depv = depv_array->Depv(array_index);  
00217   for (INT i = 0; i < dep_index; i++) 
00218     if (DEP_Direction(DEPV_Dep(depv, i)) == DIR_POS)
00219       return TRUE; 
00220   DIRECTION dir = DEP_Direction(DEPV_Dep(depv, dep_index)); 
00221   if (dir == DIR_NEG || dir == DIR_EQ || dir == DIR_NEGEQ) 
00222     return TRUE;
00223   return FALSE; 
00224 } 
00225 
00226 //-----------------------------------------------------------------------
00227 // NAME: RV_Array_Node_Legal 
00228 // FUNCTION: Returns TRUE if no dependence incident on node 'wn' inhibits
00229 //   the loop reversal of loop 'wn_loop'.  Returns FALSE, otherwise.  Use 
00230 //   'edge_table' to keep track of which edges we have already checked.     
00231 //-----------------------------------------------------------------------
00232 
00233 static BOOL RV_Array_Node_Legal(WN* wn, 
00234          WN* wn_loop,
00235          HASH_TABLE<EINDEX16,INT>* edge_table) 
00236 {
00237   OPERATOR opr = WN_operator(wn);
00238   if (opr == OPR_ILOAD || opr == OPR_ISTORE 
00239       || opr == OPR_LDID || opr == OPR_STID) {
00240     VINDEX16 v = dg->Get_Vertex(wn);
00241     if (v == 0)
00242       return (opr == OPR_LDID || opr == OPR_STID); 
00243     EINDEX16 e = 0;
00244     for (e = dg->Get_In_Edge(v); e != 0; e = dg->Get_Next_In_Edge(e)) {
00245       if (edge_table->Find(e))
00246   continue; 
00247       edge_table->Enter(e, 1); 
00248       DEPV_ARRAY* depv_array = dg->Depv_Array(e); 
00249       for (INT i = 0; i < depv_array->Num_Vec(); i++)
00250   if (!RV_Depv_Is_Reversable(depv_array, i, wn_loop))
00251     return FALSE; 
00252     }
00253     for (e = dg->Get_In_Edge(v); e != 0; e = dg->Get_Next_In_Edge(e)) {
00254       if (edge_table->Find(e))
00255   continue; 
00256       edge_table->Enter(e, 1); 
00257       DEPV_ARRAY* depv_array = dg->Depv_Array(e); 
00258       for (INT i = 0; i < depv_array->Num_Vec(); i++)
00259   if (!RV_Depv_Is_Reversable(depv_array, i, wn_loop))
00260     return FALSE; 
00261     }
00262   }
00263   return TRUE; 
00264 }
00265 
00266 //-----------------------------------------------------------------------
00267 // NAME: RV_Array_Legal 
00268 // FUNCTION: Returns TRUE if no dependence incident on a node in the tree
00269 //   rooted at 'wn' inhibits the loop reversal of loop 'wn_loop'.  Returns
00270 //   FALSE, otherwise.  Use 'edge_table' to keep track of which edges 
00271 //   we have already checked.  
00272 //----------------------------------------------------------------------
00273 static BOOL RV_Array_Legal(WN* wn, 
00274                      WN* wn_loop, 
00275                HASH_TABLE<EINDEX16,INT>* edge_table)
00276 {
00277   if (!RV_Array_Node_Legal(wn, wn_loop, edge_table))
00278     return FALSE; 
00279 
00280   if (WN_opcode(wn) == OPC_BLOCK) {
00281     for (WN* wn_tp = WN_first(wn); wn_tp != NULL; wn_tp = WN_next(wn_tp))
00282       if (!RV_Array_Legal(wn_tp, wn_loop, edge_table))
00283         return FALSE; 
00284   } else {
00285     for (INT i = 0; i < WN_kid_count(wn); i++) {
00286       if (!RV_Array_Legal(WN_kid(wn, i), wn_loop, edge_table))
00287   return FALSE; 
00288     }
00289   }
00290   return TRUE; 
00291 }
00292 
00293 //-----------------------------------------------------------------------
00294 // NAME: RV_Is_Legal 
00295 // FUNCTION: Returns TRUE if reversing loop 'wn_loop' is legal, FALSE 
00296 //   otherwise. 
00297 //-----------------------------------------------------------------------
00298 
00299 extern BOOL RV_Is_Legal(WN* wn_loop)
00300 { 
00301   dg = Array_Dependence_Graph; 
00302   du = Du_Mgr; 
00303   if (!Do_Loop_Is_Good(wn_loop))
00304     return FALSE; 
00305   if (!RV_Easy_Bounds(wn_loop))  
00306     return FALSE;
00307   if (!RV_Scalar_Legal(wn_loop, wn_loop)) 
00308     return FALSE;
00309   INT hash_table_size = MIN(dg->Get_Edge_Count(), 512); 
00310   HASH_TABLE<EINDEX16,INT> edge_table(hash_table_size, &LNO_local_pool); 
00311   if (!RV_Array_Legal(wn_loop, wn_loop, &edge_table))
00312     return FALSE; 
00313   return TRUE; 
00314 }
00315 
00316 //-----------------------------------------------------------------------
00317 // NAME: RV_Reverse_Index_Ldid 
00318 // FUNCTION: Replace 'wn_index' with 'lower_bound + upper_bound - wn_index',
00319 //   where 'lower_bound' and 'upper_bound' are the lower and upper bounds 
00320 //   of the index variable of loop 'wn_loop'.   
00321 //-----------------------------------------------------------------------
00322 
00323 static void RV_Reverse_Index_Ldid(WN* wn_index, 
00324           WN* wn_loop) 
00325 {
00326   WN* wn_parent = LWN_Get_Parent(wn_index); 
00327   INT i;
00328   for (i = 0; i < WN_kid_count(wn_parent); i++) 
00329     if (WN_kid(wn_parent, i) == wn_index) 
00330       break;
00331   INT replace_index = i; 
00332   WN* wn_lower_bound = WN_kid0(WN_start(wn_loop)); 
00333   WN* wn_upper_bound = SNL_UBexp(WN_end(wn_loop));
00334   WN* wn_new_lb = LWN_Copy_Tree(wn_lower_bound); 
00335   WN* wn_new_ub = LWN_Copy_Tree(wn_upper_bound); 
00336   WN* wn_new_index = LWN_Copy_Tree(wn_index); 
00337   if (du != NULL) { 
00338     LWN_Copy_Def_Use(wn_lower_bound, wn_new_lb, du);  
00339     LWN_Copy_Def_Use(wn_upper_bound, wn_new_ub, du);  
00340     LWN_Copy_Def_Use(wn_index, wn_new_index, du);  
00341   }
00342   OPERATOR opr = WN_operator(WN_end(wn_loop));
00343   TYPE_ID tid = Do_Wtype(wn_loop); 
00344   if (opr == OPR_GT || opr == OPR_LT) {
00345     OPCODE op = OPCODE_make_op(OPR_INTCONST, tid, MTYPE_V); 
00346     WN* wn_minus_one = WN_CreateIntconst(op, (INT64) -1);
00347     OPCODE op_add = OPCODE_make_op(OPR_ADD, tid, MTYPE_V);
00348     wn_new_ub = LWN_CreateExp2(op_add, wn_new_ub, wn_minus_one); 
00349   } 
00350   OPCODE opc_add = OPCODE_make_op(OPR_ADD, tid, MTYPE_V);  
00351   WN* wn_sum = LWN_CreateExp2(opc_add, wn_new_lb, wn_new_ub);  
00352   OPCODE opc_sub = OPCODE_make_op(OPR_SUB, tid, MTYPE_V);  
00353   WN* wn_result = LWN_CreateExp2(opc_sub, wn_sum, wn_new_index);
00354   WN_kid(wn_parent, replace_index) = wn_result;  
00355   LWN_Set_Parent(wn_result, wn_parent);   
00356   LWN_Delete_Tree(wn_index);
00357 } 
00358 
00359 //-----------------------------------------------------------------------
00360 // NAME: RV_Reverse_Indices 
00361 // FUNCTION: Replace the references to the index variable of loop 'wn_loop' 
00362 //  with their reversed value.  In other words, if 'i' is index variable 
00363 //  of 'wn_loop', replace the references to 'i' in 'wn_tree' with: 
00364 //  'lower_bound + upper_bound - i', where 'lower_bound' and 'upper_bound' 
00365 //  are the lower and upper bounds of 'i' in 'wn_loop'.   
00366 //-----------------------------------------------------------------------
00367 
00368 static void RV_Reverse_Indices(WN* wn_tree, 
00369              WN* wn_loop)
00370 {
00371   if (WN_operator(wn_tree) == OPR_LDID
00372       && SYMBOL(wn_tree) == SYMBOL(WN_index(wn_loop))) {
00373     RV_Reverse_Index_Ldid(wn_tree, wn_loop); 
00374   } else if (WN_opcode(wn_tree) == OPC_BLOCK) {
00375     for (WN* wn = WN_first(wn_tree); wn != NULL; wn = WN_next(wn))
00376       RV_Reverse_Indices(wn, wn_loop); 
00377   } else { 
00378     for (INT i = 0; i < WN_kid_count(wn_tree); i++) 
00379       RV_Reverse_Indices(WN_kid(wn_tree, i), wn_loop); 
00380   }
00381 }
00382 
00383 //-----------------------------------------------------------------------
00384 // NAME: RV_Reverse_Dependence 
00385 // FUNCTION: Reverse the dependence component corresponding to the loop 
00386 //   'wn_loop' in the 'array_index'th element of the 'depv_array'.  
00387 //-----------------------------------------------------------------------
00388 
00389 static void RV_Reverse_Dependence(DEPV_ARRAY* depv_array,
00390           INT array_index,  
00391                 WN* wn_loop) 
00392 { 
00393   DO_LOOP_INFO* dli = Get_Do_Loop_Info(wn_loop); 
00394   INT dep_index = dli->Depth - depv_array->Num_Unused_Dim();
00395   DEPV* depv = depv_array->Depv(array_index); 
00396   DEPV_Dep(depv, dep_index) = DEP_Negate(DEPV_Dep(depv, dep_index));  
00397 }
00398 
00399 //-----------------------------------------------------------------------
00400 // NAME: RV_Reverse_Node_Dependences 
00401 // FUNCTION: Reverse all of the components of the dependence edges corres- 
00402 //   ponding to 'wn_loop' which are incident on node 'wn', if those com-
00403 //   ponents have not already been reversed.  Use the 'edge_table' to 
00404 //   keep track of which edges we have already operated on. 
00405 //-----------------------------------------------------------------------
00406 
00407 static void RV_Reverse_Node_Dependences(WN* wn, 
00408                 WN* wn_loop, 
00409           HASH_TABLE<EINDEX16,INT>* edge_table)
00410 {
00411   if (OPCODE_is_load(WN_opcode(wn)) || OPCODE_is_store(WN_opcode(wn))) {
00412     VINDEX16 v = dg->Get_Vertex(wn);
00413     if (v == 0) 
00414       return; 
00415     EINDEX16 e = 0;
00416     DO_LOOP_INFO* dli = Get_Do_Loop_Info(wn_loop); 
00417     INT loop_depth = dli->Depth;  
00418     for (e = dg->Get_In_Edge(v); e != 0; e = dg->Get_Next_In_Edge(e)) {
00419       if (edge_table->Find(e))
00420   continue; 
00421       edge_table->Enter(e, 1); 
00422       DEPV_ARRAY* depv_array = dg->Depv_Array(e); 
00423       for (INT i = 0; i < depv_array->Num_Vec(); i++)
00424   RV_Reverse_Dependence(depv_array, i, wn_loop); 
00425     }
00426     for (e = dg->Get_In_Edge(v); e != 0; e = dg->Get_Next_In_Edge(e)) {
00427       if (edge_table->Find(e))
00428   continue; 
00429       edge_table->Enter(e, 1); 
00430       DEPV_ARRAY* depv_array = dg->Depv_Array(e); 
00431       for (INT i = 0; i < depv_array->Num_Vec(); i++)
00432   RV_Reverse_Dependence(depv_array, i, wn_loop); 
00433     }
00434   }
00435 }
00436 
00437 //-----------------------------------------------------------------------
00438 // NAME: RV_Reverse_Dependences 
00439 // FUNCTION: Reverse all of the components in the tree rooted at 'wn'
00440 //   corresponding to the loop 'wn_loop'.  Use the 'edge_table' to 
00441 //   keep track of which edges we have already operated on.  
00442 //-----------------------------------------------------------------------
00443 
00444 static void RV_Reverse_Dependences(WN* wn, 
00445                  WN* wn_loop,
00446            HASH_TABLE<EINDEX16,INT>* edge_table) 
00447 {
00448   RV_Reverse_Node_Dependences(wn, wn_loop, edge_table);
00449   if (WN_opcode(wn) == OPC_BLOCK) {
00450     for (WN* wn_tp = WN_first(wn); wn_tp != NULL; wn_tp = WN_next(wn_tp))
00451       RV_Reverse_Dependences(wn_tp, wn_loop, edge_table);
00452   } else {
00453     for (INT i = 0; i < WN_kid_count(wn); i++) 
00454       RV_Reverse_Dependences(WN_kid(wn, i), wn_loop, edge_table);
00455   }
00456 }  
00457 
00458 //-----------------------------------------------------------------------
00459 // NAME: RV_Simplify_Indicies 
00460 // FUNCTION: Simplify the array indicies in the tree rooted at 'wn_tree'.  
00461 //-----------------------------------------------------------------------
00462 
00463 static void RV_Simplify_Indicies(WN* wn_tree) 
00464 {
00465   if (WN_operator(wn_tree) == OPR_ARRAY) {
00466     LWN_Simplify_Tree(wn_tree); 
00467   } else if (WN_opcode(wn_tree) == OPC_BLOCK) {
00468     for (WN* wn = WN_first(wn_tree); wn != NULL; wn = WN_next(wn))
00469       RV_Simplify_Indicies(wn); 
00470   } else {
00471     for (INT i = 0; i < WN_kid_count(wn_tree); i++) 
00472       RV_Simplify_Indicies(WN_kid(wn_tree, i));  
00473   }
00474 }
00475 
00476 //-----------------------------------------------------------------------
00477 // NAME: RV_Reverse_Loop  
00478 // FUNCTION: Reverse the loop 'wn_loop'.  We assume that the loop has 
00479 //   already been determined to be reversible.  
00480 //-----------------------------------------------------------------------
00481 
00482 extern void RV_Reverse_Loop(WN* wn_loop)
00483 {
00484   if (LNO_Verbose) {
00485     fprintf(stdout, "Reversing Loop %s\n", WB_Whirl_Symbol(WN_index(wn_loop))); 
00486     fprintf(TFile, "Reversing Loop %s\n", WB_Whirl_Symbol(WN_index(wn_loop))); 
00487   }
00488   dg = Array_Dependence_Graph; 
00489   du = Du_Mgr;  
00490   RV_Reverse_Indices(WN_do_body(wn_loop), wn_loop);
00491   INT hash_table_size = MIN(dg->Get_Edge_Count(), 512);
00492   HASH_TABLE<EINDEX16,INT> edge_table(hash_table_size, &LNO_local_pool);
00493   RV_Reverse_Dependences(WN_do_body(wn_loop), wn_loop, &edge_table);   
00494   RV_Simplify_Indicies(WN_do_body(wn_loop));  
00495   DOLOOP_STACK loop_stack(&LNO_local_pool); 
00496   Build_Doloop_Stack(LWN_Get_Parent(wn_loop), &loop_stack); 
00497   LNO_Build_Access(wn_loop, &loop_stack, &LNO_default_pool); 
00498   DO_LOOP_INFO *dli = Get_Do_Loop_Info(wn_loop); 
00499   dli->Is_Backward = Do_Loop_Is_Backward(wn_loop); 
00500 }
00501 
00502 //-----------------------------------------------------------------------
00503 // NAME: RV_Traverse
00504 // FUNCTION: Reverse every loop in the tree rooted at 'wn_tree'.
00505 // NOTE: This function is provided only for testing 'RV_Is_Legal()' 
00506 //   and 'RV_Reverse_Loop()'.  
00507 //-----------------------------------------------------------------------
00508 
00509 static void RV_Traverse(WN* wn_tree) 
00510 {
00511   if (WN_opcode(wn_tree) == OPC_DO_LOOP) {
00512     if (RV_Is_Legal(wn_tree))
00513       RV_Reverse_Loop(wn_tree);
00514     if (LNO_Verbose) {
00515       DO_LOOP_INFO* dli = Get_Do_Loop_Info(wn_tree);
00516       if (!dli->Is_Backward) {
00517   fprintf(stdout, "Loop 0x%p is indexed forward\n", wn_tree); 
00518   fprintf(TFile, "Loop 0x%p is indexed forward\n", wn_tree); 
00519       } else {
00520   fprintf(stdout, "Loop 0x%p is indexed backward\n", wn_tree); 
00521   fprintf(TFile, "Loop 0x%p is indexed backward\n", wn_tree); 
00522       }
00523     }
00524   }
00525   if (WN_opcode(wn_tree) == OPC_BLOCK) {
00526     for (WN* wn = WN_first(wn_tree); wn != NULL; wn = WN_next(wn))
00527       RV_Traverse(wn);
00528   } else {
00529     for (INT i = 0; i < WN_kid_count(wn_tree); i++) 
00530       RV_Traverse(WN_kid(wn_tree, i));
00531   }
00532 }
00533 
00534 //-----------------------------------------------------------------------
00535 // NAME: Reverse_Loops  
00536 // FUNCTION: Reverse every loop in the 'func_nd' for which loop reversal 
00537 //   is legal. 
00538 // NOTE: This function is provided only for testing 'RV_Is_Legal()' 
00539 //   and 'RV_Reverse_Loop()'. 
00540 //-----------------------------------------------------------------------
00541 
00542 extern void Reverse_Loops(WN* func_nd) 
00543 {
00544   if (!LNO_Blind_Loop_Reversal)
00545     return;
00546   if (LNO_Verbose) {
00547     fprintf(stdout, "Applying Loop Reversal\n");
00548     fprintf(TFile, "Applying Loop Reversal\n");
00549   }
00550   (void) RV_Traverse(func_nd);
00551   if (LNO_Verbose) {
00552     fprintf(stdout, "Loop Reversal Complete\n");
00553     fprintf(TFile, "Loop Reversal Complete\n");
00554   }
00555 }
00556 
00557 //-----------------------------------------------------------------------
00558 // NAME: RV_Evaluate 
00559 // FUNCTION: Returns the value of the expression rooted at 'wn_tree', 
00560 //   if it is actually an integer expression.  Sets '*valid' to FALSE if 
00561 //   'wn_tree' is not the root of an integer expression.  
00562 //-----------------------------------------------------------------------
00563 
00564 static INT RV_Evaluate(WN* wn_tree, BOOL* valid) 
00565 {
00566   INT numeric1 = 0; 
00567   INT numeric2 = 0;
00568   BOOL valid1 = TRUE; 
00569   BOOL valid2 = TRUE; 
00570   switch (WN_operator(wn_tree)) {
00571   case OPR_INTCONST:  
00572     *valid = TRUE; 
00573     return WN_const_val(wn_tree); 
00574   case OPR_NEG:
00575     numeric1 = RV_Evaluate(WN_kid0(wn_tree), &valid1);  
00576     if (!valid1) { 
00577       *valid = FALSE; 
00578       return 0; 
00579     } else { 
00580       *valid = TRUE; 
00581       return numeric1; 
00582     } 
00583   case OPR_ADD: 
00584     numeric1 = RV_Evaluate(WN_kid0(wn_tree), &valid1); 
00585     numeric2 = RV_Evaluate(WN_kid1(wn_tree), &valid2); 
00586     if (!valid1 || !valid2) {
00587       *valid = FALSE; 
00588       return 0; 
00589     } else {
00590       *valid = TRUE; 
00591       return numeric1 + numeric2; 
00592     }
00593   case OPR_SUB: 
00594     numeric1 = RV_Evaluate(WN_kid0(wn_tree), &valid1); 
00595     numeric2 = RV_Evaluate(WN_kid1(wn_tree), &valid2); 
00596     if (!valid1 || !valid2) {
00597       *valid = FALSE; 
00598       return 0; 
00599     } else {
00600       *valid = TRUE; 
00601       return numeric1 - numeric2; 
00602     }
00603   case OPR_MPY: 
00604     numeric1 = RV_Evaluate(WN_kid0(wn_tree), &valid1); 
00605     numeric2 = RV_Evaluate(WN_kid1(wn_tree), &valid2); 
00606     if (!valid1 || !valid2) {
00607       *valid = FALSE; 
00608       return 0; 
00609     } else {
00610       *valid = TRUE; 
00611       return numeric1 * numeric2; 
00612     }
00613   case OPR_DIV: 
00614     numeric1 = RV_Evaluate(WN_kid0(wn_tree), &valid1); 
00615     numeric2 = RV_Evaluate(WN_kid1(wn_tree), &valid2); 
00616     if (!valid1 || !valid2) {
00617       *valid = FALSE; 
00618       return 0; 
00619     } else {
00620       *valid = TRUE; 
00621       return numeric1 / numeric2; 
00622     }
00623   default:
00624     *valid = FALSE; 
00625     return 0;  
00626   }
00627 }
00628 
00629 //-----------------------------------------------------------------------
00630 // NAME: RV_Sign 
00631 // FUNCTION: Returns 1 if the constant expression rooted at 'wn_tree' is 
00632 //   provably positive or zero, -1 if it is provably negative, and 0 
00633 //   otherwise.  
00634 //-----------------------------------------------------------------------
00635 
00636 static INT RV_Sign(WN* wn_tree)
00637 {
00638   BOOL valid = FALSE; 
00639   INT numeric = RV_Evaluate(wn_tree, &valid); 
00640   if (!valid) 
00641     return 0; 
00642   return numeric < 0 ? -1 : 1; 
00643 }
00644 
00645 //-----------------------------------------------------------------------
00646 // NAME: RV_Index_Sign
00647 // FUNCTION: Returns -1 if the coefficient of 'wn_index' is provably 
00648 //   negative, +1 if the coefficient of 'wn_index' is provably positive, 
00649 //   and 0 otherwise.   
00650 //-----------------------------------------------------------------------
00651 
00652 static INT RV_Index_Sign(WN* wn_index) 
00653 {
00654   INT sign = 1; 
00655   WN* wn = NULL; 
00656   WN* wn_last = wn_index;
00657   BOOL break_loop = FALSE; 
00658   for (wn = LWN_Get_Parent(wn_index); ; wn_last = wn, wn = LWN_Get_Parent(wn)) {
00659     if (break_loop || !OPCODE_is_expression(WN_opcode(wn))) 
00660       break;
00661     switch (WN_operator(wn)) {
00662     case OPR_NEG: 
00663       sign = -sign; 
00664       break;
00665     case OPR_ADD: 
00666     case OPR_CVT: 
00667       break;   
00668     case OPR_SUB: 
00669       sign = (wn_last == WN_kid1(wn)) ? -sign : sign;
00670       break; 
00671     case OPR_MPY: 
00672     case OPR_DIV: 
00673       {
00674         for (INT i = 0; i < WN_kid_count(wn); i++) {
00675     if (WN_kid(wn, i) == wn_last) 
00676         continue; 
00677     INT sibling_sign = RV_Sign(WN_kid(wn, i)); 
00678           if (sibling_sign == 0) 
00679       return 0; 
00680         sign *= sibling_sign;  
00681         }
00682       }
00683       break;
00684     case OPR_ARRAY: 
00685     case OPR_PARM:
00686     case OPR_INTRINSIC_OP:
00687 #ifdef KEY
00688     case OPR_PURE_CALL_OP:
00689 #endif
00690       break_loop = TRUE; 
00691       break; 
00692     default:  
00693       return 0;
00694     }
00695   }  
00696   return (sign < 0 ? -1 : 1); 
00697 }
00698 
00699 //-----------------------------------------------------------------------
00700 // NAME: RV_Find_Backward_Indices 
00701 // FUNCTION: Returns TRUE if all of the indices of 'wn_loop' in 'wn_tree'
00702 //  have provably negative coefficients, FALSE otherwise.  
00703 //-----------------------------------------------------------------------
00704 
00705 static BOOL RV_Tree_Has_All_Backward_Indices(WN* wn_tree, 
00706                      WN* wn_loop, 
00707                BOOL* found_backward)
00708 {
00709   if (WN_operator(wn_tree) == OPR_LDID
00710       && SYMBOL(wn_tree) == SYMBOL(WN_index(wn_loop))) {
00711     if (RV_Index_Sign(wn_tree) >= 0)
00712       return FALSE; 
00713     *found_backward = TRUE; 
00714   } else if (WN_opcode(wn_tree) == OPC_BLOCK) {
00715     for (WN* wn = WN_first(wn_tree); wn != NULL; wn = WN_next(wn))
00716       if (!RV_Tree_Has_All_Backward_Indices(wn, wn_loop, found_backward))
00717   return FALSE;
00718   } else {
00719     for (INT i = 0; i < WN_kid_count(wn_tree); i++)
00720       if (!RV_Tree_Has_All_Backward_Indices(WN_kid(wn_tree, i), wn_loop, 
00721   found_backward))
00722   return FALSE; 
00723   }
00724   return TRUE; 
00725 } 
00726 
00727 
00728 //-----------------------------------------------------------------------
00729 // NAME: RV_Find_Written_Indices
00730 // FUNCTION: Returns TRUE if all of the indices of 'wn_loop' in 'wn_tree'
00731 //  have been written, FALSE otherwise.
00732 //-----------------------------------------------------------------------
00733 
00734 static BOOL RV_Tree_Has_All_Written_Indices(WN* wn_tree,
00735                                              WN* wn_loop)
00736 {
00737   if (WN_operator(wn_tree) == OPR_STID
00738       && SYMBOL(wn_tree) == SYMBOL(WN_index(wn_loop))) {
00739     if (RV_Index_Sign(wn_tree) >= 0)
00740       return TRUE;
00741   } else if (WN_opcode(wn_tree) == OPC_BLOCK) {
00742     for (WN* wn = WN_first(wn_tree); wn != NULL; wn = WN_next(wn))
00743       if (RV_Tree_Has_All_Written_Indices(wn, wn_loop))
00744         return TRUE;
00745   } else {
00746     for (INT i = 0; i < WN_kid_count(wn_tree); i++)
00747       if (RV_Tree_Has_All_Written_Indices(WN_kid(wn_tree, i), wn_loop))
00748         return TRUE;
00749   }
00750   return FALSE;
00751 }
00752 
00753 
00754 //-----------------------------------------------------------------------
00755 // NAME: Do_Loop_Is_Backward
00756 // FUNCTION: Returns TRUE if all of the do loop indices in the body of
00757 //   'wn_loop' have provably negative coefficients.  Otherwise, returns
00758 //   FALSE.  
00759 // NOTE: This is a simple algorithm that only looks at arithmetic expres-
00760 //   sions.  It is inconclusive otherwise. 
00761 //-----------------------------------------------------------------------
00762 
00763 extern BOOL Do_Loop_Is_Backward(WN* wn_loop)
00764 {
00765   BOOL found_backward = FALSE; 
00766   return RV_Tree_Has_All_Backward_Indices(WN_do_body(wn_loop), wn_loop, 
00767     &found_backward) && found_backward; 
00768 }
00769 
00770 
00771 //-----------------------------------------------------------------------
00772 // NAME: Do_Loop_Is_Regular
00773 // FUNCTION: Returns TRUE if all of the do loop indices in the body of
00774 // 'wn_loop' has been written.  Otherwise, returns FALSE.
00775 // NOTE: This is a simple algorithm that only looks at arithmetic expres-
00776 // sions.  It is inconclusive otherwise.
00777 //-----------------------------------------------------------------------
00778 
00779 extern BOOL Do_Loop_Is_Regular(WN* wn_loop)
00780 {
00781   return !RV_Tree_Has_All_Written_Indices(WN_do_body(wn_loop), wn_loop);        
00782 }
00783