Open64: osprey/be/com/standardize.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 
00041 #ifdef USE_PCH
00042 #include "be_com_pch.h"
00043 #endif /* USE_PCH */
00044 #pragma hdrstop
00045 #include "defs.h"
00046 #include "stab.h"
00047 #include "wn.h"
00048 #include "config_targ.h"
00049 #include "wn_simp.h"
00050 #include "wio.h"
00051 #include "targ_const.h"
00052 #include "const.h"
00053 #include "strtab.h"
00054 #include "config.h"
00055 #include "wn_util.h"
00056 #include "fb_whirl.h"
00057 
00058 /*-----------------------------------------------------------------------
00059 // NAME: WN_Symbol_Count 
00060 // FUNCTION: For the tree rooted at 'wn', return the number of nodes with 
00061 //   the given 'symbol' and 'offset'.  
00062 //---------------------------------------------------------------------*/
00063 
00064 static INT WN_Symbol_Count(WN *wn,              
00065                            ST_IDX symbol, 
00066          WN_OFFSET offset)
00067 {
00068   INT k = 0; 
00069   INT rval = 0; 
00070   rval = (WN_operator(wn) == OPR_LDID &&
00071     symbol == WN_st_idx(wn) && offset == WN_offset(wn)) 
00072     ? 1 : 0;
00073   for (k = 0; k < WN_kid_count(wn); k++)
00074     rval += WN_Symbol_Count(WN_kid(wn,k), symbol, offset);
00075   return rval;
00076 }
00077 
00078 /*-----------------------------------------------------------------------
00079 // NAME: WN_Flip_Le_And_Ge 
00080 // FUNCTION: Flip the left and right hand sides of an expression with 
00081 //   OPR_GE, OPR_LE, OPR_GT, or OPR_LT as the operator of the expression 
00082 //   root 'wn'.  
00083 //---------------------------------------------------------------------*/
00084 
00085 static void WN_Flip_Le_And_Ge(WN *wn)
00086 {
00087   OPCODE    opc;
00088   OPERATOR  opr; 
00089 
00090   opc = WN_opcode(wn);
00091   opr = OPCODE_operator(opc);
00092   switch (opr) {
00093    case OPR_GE: opr = OPR_LE; break;
00094    case OPR_LE: opr = OPR_GE; break;
00095    case OPR_GT: opr = OPR_LT; break;
00096    case OPR_LT: opr = OPR_GT; break;
00097    default: FmtAssert(0, ("Bad call to Flip_Le_And_Ge")); break;
00098   }
00099 
00100   WN_set_opcode(wn, OPCODE_make_op(opr, OPCODE_rtype(opc), OPCODE_desc(opc)));
00101 }
00102 
00103 /*-----------------------------------------------------------------------
00104 // NAME: WN_Solve_For 
00105 // FUNCTION: For the expression 'wn_top', solve this in terms of the 
00106 //   variable given by 'symbol' and 'offset'.  Return TRUE if we knew 
00107 //   how to solve, FALSE otherwise. 
00108 //---------------------------------------------------------------------*/
00109 
00110 static BOOL WN_Solve_For(WN *wn_top, 
00111                ST_IDX symbol,
00112              WN_OFFSET offset)
00113 {
00114   BOOL ok = FALSE;
00115   BOOL use_ceil = FALSE;
00116   INT lcount = 0; 
00117   INT rcount = 0;
00118   INT v = 0; 
00119   INTRINSIC intrnceil = INTRINSIC_NONE;
00120   INTRINSIC intrnfloor = INTRINSIC_NONE;
00121   WN *l = NULL; 
00122   WN *r = NULL; 
00123   WN *wn0 = NULL; 
00124   WN *ll = NULL;  
00125   WN *lr = NULL;  
00126   OPCODE lopc; 
00127   OPCODE negop;
00128   OPCODE newopc; 
00129   OPCODE lropc;
00130   OPERATOR lopr; 
00131   TYPE_ID  type;
00132   OPERATOR opr_base; 
00133    
00134   opr_base = WN_operator(wn_top);
00135   FmtAssert(opr_base == OPR_GT || opr_base == OPR_LT || opr_base == OPR_LE
00136     || opr_base == OPR_GE, ("Solve_For() called with bad RELOP"));
00137  
00138   lcount = WN_Symbol_Count(WN_kid0(wn_top), symbol, offset);
00139   rcount = WN_Symbol_Count(WN_kid1(wn_top), symbol, offset);
00140   if (!(lcount == 1 && rcount == 0) && !(lcount == 0 && rcount == 1)) {
00141     return FALSE;
00142   }
00143 
00144   /* put variable on lhs for the moment */
00145   if (rcount) {
00146     WN_Flip_Le_And_Ge(wn_top);
00147     wn0 = WN_kid0(wn_top);
00148     WN_kid0(wn_top) = WN_kid1(wn_top);
00149     WN_kid1(wn_top) = wn0;
00150   }
00151 
00152   l = WN_kid0(wn_top);
00153   r = WN_kid1(wn_top);
00154   while (1) {
00155     /* 
00156      * invariant at this location: the index is somewhere on the left (l))
00157      * invariant at this location: l and r will be wn_top's kids
00158      */
00159   
00160     lopc = WN_opcode(l);
00161     lopr = OPCODE_operator(lopc);
00162 
00163     /* have we successfully solved for the index variable? */
00164     if (OPCODE_is_load(lopc)) {
00165       ok = TRUE;
00166       break;
00167     }
00168 
00169     if (lopr == OPR_NEG) {
00170       WN_Flip_Le_And_Ge(wn_top);
00171       type = WN_rtype(r);
00172       negop = OPCODE_make_op(OPR_NEG, type, MTYPE_V);
00173       r = WN_CreateExp1(negop, r);
00174       l = WN_kid0(l);
00175       continue;
00176     }
00177 
00178     /* A CVT of an expression containing the index varible
00179      * or any other single kid node is bad news at this point.
00180      */
00181     if (lopr == OPR_CVT || WN_kid_count(l) == 1)
00182       return FALSE;
00183 
00184     lcount = WN_Symbol_Count(WN_kid0(l), symbol, offset);
00185     rcount = WN_Symbol_Count(WN_kid1(l), symbol, offset);
00186 
00187     Is_True((lcount == 1 && rcount == 0) ||
00188             (lcount == 0 && rcount == 1),
00189             ("Impossible: Counts messed up %d %d", lcount, rcount));
00190 
00191     if (rcount) {
00192       if (lopr == OPR_SUB) {
00193         /* 
00194          * in order to commute below, must change sign and mul right size
00195          * through by -1.
00196    */ 
00197         WN_Flip_Le_And_Ge(wn_top);
00198         type = WN_rtype(r);
00199         negop = OPCODE_make_op(OPR_NEG, type, MTYPE_V);
00200         r = WN_CreateExp1(negop, r);
00201       }
00202       else if (lopr != OPR_ADD && lopr != OPR_MPY) /* commutative */
00203         break;
00204       wn0 = WN_kid0(l);
00205       WN_kid0(l) = WN_kid1(l);
00206       WN_kid1(l) = wn0;
00207     }
00208 
00209     ll = WN_kid0(l);
00210     lr = WN_kid1(l);
00211 
00212     if (lopr == OPR_MPY) {
00213       type = OPCODE_rtype(lopc);
00214 
00215       /* the intrinsics */ 
00216       switch (type) {
00217        case MTYPE_I4:
00218         intrnceil = INTRN_I4DIVCEIL; intrnfloor = INTRN_I4DIVFLOOR; break;
00219        case MTYPE_I8:
00220         intrnceil = INTRN_I8DIVCEIL; intrnfloor = INTRN_I8DIVFLOOR; break;
00221        case MTYPE_U4:
00222         intrnceil = INTRN_U4DIVCEIL; intrnfloor = INTRN_U4DIVFLOOR; break;
00223        case MTYPE_U8:
00224         intrnceil = INTRN_U8DIVCEIL; intrnfloor = INTRN_U8DIVFLOOR; break;
00225        default:
00226         goto out;        /* escape before we change any code. */
00227       }
00228 
00229       /* 
00230        * rhs of mul must be a const so we know if we are dividing
00231        * through by a positive or negative.  Besides, it fits the
00232        * expected normalized pattern.
00233        */ 
00234 
00235       lropc = WN_opcode(lr);
00236       if (OPCODE_operator(lropc) != OPR_INTCONST)
00237         break;
00238 
00239       v = WN_const_val(lr);
00240       if (v < 0) {
00241         WN_Flip_Le_And_Ge(wn_top);
00242         WN_const_val(lr) = -v;
00243         negop = OPCODE_make_op(OPR_NEG, OPCODE_rtype(lropc), MTYPE_V);
00244         r = WN_CreateExp1(negop, r);
00245       }
00246 
00247       use_ceil = WN_operator(wn_top) == OPR_GE 
00248         || WN_operator(wn_top) == OPR_LT;
00249       newopc = OPCODE_make_op(OPR_INTRINSIC_OP, type, MTYPE_V);
00250 
00251       r = WN_CreateExp2(newopc, r, lr);
00252       WN_intrinsic(r) = use_ceil ? intrnceil : intrnfloor;
00253       WN_Delete(l);
00254       l = ll;
00255     }
00256     else if (lopr == OPR_ADD || lopr == OPR_SUB) {
00257       WN_kid0(l) = r;
00258       WN_kid1(l) = lr;
00259       r = l;
00260       l = ll;
00261       WN_set_opcode(r, OPCODE_make_op(lopr == OPR_ADD ? OPR_SUB : OPR_ADD,
00262                                       OPCODE_rtype(lopc), OPCODE_desc(lopc)));
00263     }
00264     else
00265       return FALSE;
00266   }
00267 
00268  out:
00269 
00270   WN_kid0(wn_top) = l;
00271   WN_kid1(wn_top) = r;
00272 
00273   return ok;
00274 }
00275 
00276 /*-----------------------------------------------------------------------
00277 // NAME: WN_Copy_Frequency_Tree 
00278 // FUNCTION: Copy the frequency information from 'wn_from' to 'wn'.
00279 //
00280 // Hmm... This function looks like it puts feedback frequencies on
00281 // expression nodes, which isn't useful and really isn't allowed
00282 // (although it isn't known to cause problems at present). Why does
00283 // this function need to be written this way? -- rkennedy
00284 //---------------------------------------------------------------------*/
00285 
00286 static void WN_Copy_Frequency_Tree(const WN *wn, const WN *wn_from)
00287 {
00288   WN_ITER *wniter; 
00289   INT32 count = 0; 
00290 
00291   if (Cur_PU_Feedback) {
00292     count = WN_MAP32_Get(WN_MAP_FEEDBACK, wn_from);
00293     wniter = WN_WALK_TreeIter((WN *) wn );
00294     while (wniter) {
00295       WN *cur = wniter->wn;
00296       wniter = WN_WALK_TreeNext(wniter);
00297       WN_MAP32_Set(WN_MAP_FEEDBACK, cur, count);
00298     }
00299   }
00300 }
00301 
00302 /*-----------------------------------------------------------------------
00303 // NAME: WN_Upper_Bound_Standardize 
00304 // FUNCTION: For the do loop 'doloop' with upper bound 'ub', put that 
00305 //   bound in standard form, if possible.  If 'ok_to_fail', return 
00306 //   FALSE if we can't standardize the upper bound, otherwise assert. 
00307 //   Return TRUE if we can standardize. 
00308 //---------------------------------------------------------------------*/
00309 
00310 extern "C" BOOL
00311 WN_Upper_Bound_Standardize(WN   *doloop, 
00312          WN   *ub, 
00313          BOOL  ok_to_fail)
00314 {
00315   OPCODE opc; 
00316   OPERATOR opr; 
00317   TYPE_ID desc; 
00318   OPCODE subop; 
00319   OPCODE intconst_opc; 
00320   WN *ub1 = NULL; 
00321   WN *wn_const = NULL;
00322   BOOL ok = FALSE; 
00323   WN *wn_tmp = NULL;  
00324 
00325   FmtAssert(WN_opcode(doloop) == OPC_DO_LOOP, ("Bad ub passed"));
00326   if (WN_operator(WN_end(doloop)) == OPR_GT) {
00327     WN_Flip_Le_And_Ge(ub); 
00328     wn_tmp = WN_kid0(ub); 
00329     WN_kid0(ub) = WN_kid1(ub); 
00330     WN_kid1(ub) = wn_tmp; 
00331   }
00332   if (WN_operator(WN_end(doloop)) == OPR_LT) {
00333     /* change i < b to i <= b-1 */
00334     desc = WN_desc(WN_end(doloop));
00335     WN_set_opcode(ub, OPCODE_make_op(OPR_LE, 
00336       WN_rtype(WN_end(doloop)), desc));
00337     subop = OPCODE_make_op(OPR_SUB, desc, MTYPE_V);
00338     intconst_opc = OPCODE_make_op(OPR_INTCONST, desc, MTYPE_V);
00339     wn_const = WN_CreateIntconst(intconst_opc, 1);
00340     ub1 = WN_CreateExp2(subop, WN_kid1(ub), wn_const); 
00341     ub1 = WN_Simplify_Tree(ub1); 
00342     WN_kid1(ub) = ub1;
00343     WN_Copy_Frequency_Tree(ub1, ub);
00344   }
00345   WN_kid1(WN_end(doloop)) = WN_Simplify_Tree(WN_kid1(WN_end(doloop))); 
00346   ok = WN_Solve_For(WN_end(doloop), WN_st_idx(WN_index(doloop)),
00347     WN_offset(WN_index(doloop)));
00348   opc = WN_opcode(ub = WN_end(doloop));
00349   opr = OPCODE_operator(opc);
00350 #ifndef KEY
00351   FmtAssert(opr == OPR_LT || opr == OPR_LE,
00352             ("surprise operator %s returned from WN_Solve_For()",
00353              OPCODE_name(opc)));
00354 #else
00355   FmtAssert(opr == OPR_GE || opr == OPR_LE,
00356             ("surprise operator %s returned from WN_Solve_For()",
00357              OPCODE_name(opc)));
00358 #endif
00359   if (ok == FALSE) {
00360     FmtAssert(ok_to_fail, 
00361       ("Upper_Bound_Standardize() could not solve for induction variable")); 
00362     return FALSE;
00363   }
00364   WN_kid1(WN_end(doloop)) = WN_Simplify_Tree(WN_kid1(WN_end(doloop))); 
00365   return ok;
00366 }
00367