Open64: osprey/be/opt/opt_canon.cxx Source File

00001 //-*-c++-*-
00002 
00003 /*
00004  * Copyright 2003, 2004, 2005, 2006 PathScale, Inc.  All Rights Reserved.
00005  */
00006 
00007 // ====================================================================
00008 //
00009 // Module: opt_canon.cxx
00010 // $Revision: 1.1.1.1 $
00011 // $Date: 2005/10/21 19:00:00 $
00012 // $Author: marcel $
00013 // $Source: /proj/osprey/CVS/open64/osprey1.0/be/opt/opt_canon.cxx,v $
00014 //
00015 // Revision history:
00016 //  3-MAY-95 dahl - Original Version
00017 //
00018 // ====================================================================
00019 //
00020 // Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.
00021 //
00022 // This program is free software; you can redistribute it and/or modify
00023 // it under the terms of version 2 of the GNU General Public License as
00024 // published by the Free Software Foundation.
00025 //
00026 // This program is distributed in the hope that it would be useful, but
00027 // WITHOUT ANY WARRANTY; without even the implied warranty of
00028 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00029 //
00030 // Further, this software is distributed without any warranty that it
00031 // is free of the rightful claim of any third person regarding
00032 // infringement  or the like.  Any license provided herein, whether
00033 // implied or otherwise, applies only to this software file.  Patent
00034 // licenses, if any, provided herein do not apply to combinations of
00035 // this program with other software, or any other product whatsoever.
00036 //
00037 // You should have received a copy of the GNU General Public License
00038 // along with this program; if not, write the Free Software Foundation,
00039 // Inc., 59 Temple Place - Suite 330, Boston MA 02111-1307, USA.
00040 //
00041 // Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
00042 // Mountain View, CA 94043, or:
00043 //
00044 // http://www.sgi.com
00045 //
00046 // For further information regarding this notice, see:
00047 //
00048 // http://oss.sgi.com/projects/GenInfo/NoticeExplan
00049 //
00050 // ====================================================================
00051 //
00052 // Description:
00053 //
00054 //  1) Canonicalize and simplify arithmetic expression
00055 //
00056 // ====================================================================
00057 
00058 
00059 #ifdef USE_PCH
00060 #include "opt_pch.h"
00061 #endif // USE_PCH
00062 #pragma hdrstop
00063 
00064 
00065 #ifdef _KEEP_RCS_ID
00066 #define opt_canon_CXX "opt_canon.cxx"
00067 static char *rcs_id =   opt_canon_CXX"$Revision: 1.8 $";
00068 #endif /* _KEEP_RCS_ID */
00069 
00070 #include "defs.h"
00071 #include "erglob.h"
00072 #include "opcode.h"
00073 #include "errors.h"
00074 #include "tracing.h"    // for TFile
00075 #include "mtypes.h"
00076 #include "config_targ.h"
00077 #include "cxx_memory.h"
00078 #include "wn_util.h"
00079 
00080 #include "opt_config.h"
00081 #include "opt_wn.h"
00082 #include "opt_util.h"
00083 #include "opt_cfg.h"
00084 #include "opt_sym.h"
00085 #include "opt_htable.h"
00086 #include "opt_fold.h"
00087 #include "opt_ssa.h"
00088 #include "opt_main.h"
00089 
00090 CODEREP*
00091 CANON_CR::Convert2cr(WN *wn, CODEMAP *htable, BOOL foldit) const
00092 {
00093   const OPERATOR opr = WN_operator(wn);
00094   MTYPE typ = WN_rtype(wn);
00095   if (typ == MTYPE_V) 
00096     typ = WN_desc(wn);
00097 #ifdef TARG_X8664
00098   else if (WN_opcode(wn) == OPC_U8U4CVT ||
00099            WN_opcode(wn) == OPC_U8U4LDID || // bug 13382
00100      WN_opcode(wn) == OPC_U8U4ILOAD)
00101     typ = MTYPE_U4; // U8U4CVT is deleted in Canon_cvt; otherwise will 
00102                // generate U8ADD instead of U4ADD which is wrong
00103 #endif
00104 
00105   if (Tree() && Scale() != 0) {
00106     return htable->Add_bin_node_and_fold
00107       (OPCODE_make_op(OPR_ADD, typ, MTYPE_V),
00108 #if defined(TARG_SL) || defined(TARG_NVISA)
00109        Tree(), htable->Add_const(typ, Scale()));
00110 #else
00111        Tree(), htable->Add_const(MTYPE_I8, Scale()));
00112 #endif
00113   }
00114   if (Tree()) 
00115     return Tree();
00116 
00117   // return a CK_CONST node
00118   // PathScale forced a I8 type here,
00119   // but we want smaller type when don't have native I8,
00120   // and this is what original code had.
00121 #if defined(TARG_SL) || defined(TARG_NVISA)
00122   CODEREP *cr =  htable->Add_const(typ, Scale());
00123 #else
00124   CODEREP *cr =  htable->Add_const(MTYPE_I8, Scale());
00125 #endif
00126   return cr;
00127 }
00128 
00129 void
00130 CANON_CR::Trim_to_16bits(WN *wn, CODEMAP *htable)
00131 {
00132   const OPCODE op = WN_opcode(wn);
00133   MTYPE typ;
00134   INT64 multiple32K;
00135 
00136   if (Scale() >= (- 0x8000) && Scale() <= 0x7fff)
00137     return;
00138 
00139   typ = OPCODE_desc(op);
00140   if (typ == MTYPE_V) 
00141     typ = OPCODE_rtype(op);
00142   if (MTYPE_size_min(typ) < 32)
00143     typ = OPCODE_rtype(op);
00144 
00145   if (Tree() == NULL) {
00146     // iload of a constant cannot be canonicalized. Very likely
00147     // doing some memory mapped I/O.
00148     multiple32K = ((Scale() + 0x8000) >> 16) << 16;
00149     Set_tree(htable->Add_const(typ, multiple32K));
00150     Set_scale(Scale()-multiple32K);
00151     return;
00152   }
00153   
00154   // make multiple32K one of the values: -96K, -32K, 32K, 96K, 160K, etc
00155   multiple32K = ((Scale() + 0x8000) >> 16) << 16;
00156   Set_scale(Scale() - multiple32K);
00157 
00158   Set_tree(htable->Add_bin_node(OPCODE_make_op(OPR_ADD, typ, MTYPE_V),
00159         Tree(), htable->Add_const(typ, multiple32K)));
00160 }
00161 
00162 void
00163 CANON_CR::Print(FILE *fp) const
00164 {
00165   if (Tree()) {
00166     fprintf(fp,"Tree:\n");
00167     Tree()->Print(0,fp);
00168   } else
00169     fprintf(fp,"Tree: NULL\n");
00170   fprintf(fp,"scale=%lld\n",Scale());
00171 }
00172 
00173 
00174 
00175 
00176 //  Canonicalization after the copy propagation phase.
00177 //
00178 //   The canonical form is  _sign * _nonconst + constval
00179 //   It can canonicalize expressions with +,-,* operators.
00180 //   
00181 //   It should be called for all the kids of iload/istore/operators
00182 //   not equal to +,-,*, and the rhs of all statements,
00183 //   after copy propagation changed them.
00184 //
00185 class CANON_EXPR {
00186 private:
00187   CODEREP  *_expr;     // original expression tree
00188 
00189   //  the canonicalized representation:
00190   //     expr ==  _sign * _nonconst + constval
00191   //
00192   INT32    _sign;       // either +1 or -1
00193   CODEREP  *_nonconst;  // the nonconst part of the expression
00194   INT64    _constval;  // constant
00195 
00196   void Set_expr(CODEREP *cr)     { _expr = cr; }
00197   void Set_nonconst(CODEREP *cr) { _nonconst = cr; }
00198   void Set_constval(INT64 value) { _constval = value; }
00199   void Set_sign(INT32 sign)      { _sign = sign; }
00200 
00201 public:
00202   CANON_EXPR(void)          { _expr = NULL; _nonconst = NULL; _constval = 0; _sign = 1; }
00203   CANON_EXPR(CODEREP *cr)   { _expr = cr;   _nonconst = NULL; _constval = 0; _sign = 1; }
00204   ~CANON_EXPR(void)         { }
00205 
00206   CODEREP *Expr(void) const      { return _expr; }
00207   CODEREP *Nonconst(void) const  { return _nonconst; }
00208   INT64    Constval(void) const  { return _constval; }
00209   INT32    Sign(void) const      { Is_True( _sign == 1 || _sign == -1, ("invalid value."));
00210                                    return _sign; }
00211 
00212   BOOL Canonicalized(void) const { return (_expr != _nonconst) || (_sign != 1) || _constval != 0; }
00213   BOOL Is_const(void) const      { return (_nonconst == NULL && _sign == 1); }
00214   BOOL Trivial(void) const;
00215   BOOL Type_safe(CODEREP *) const;
00216 
00217   void Canon_expr(CODEREP *cr, CODEMAP *htable);
00218 };
00219 
00220 
00221 
00222 // Returns TRUE if the canonicalization is a trivial canonicalization,
00223 // i.e., the CODEREP constructed from the canonical form is the same as
00224 // the original one.
00225 BOOL
00226 CANON_EXPR::Trivial(void) const
00227 {
00228   if (Expr()->Kind() == CK_CONST)
00229     return TRUE;
00230   if (Expr()->Kind() == CK_OP) {
00231     OPERATOR opr = OPCODE_operator(Expr()->Op());
00232     if (opr == OPR_ADD) {
00233       if (Expr()->Opnd(0) == Nonconst() && Sign() > 0 &&
00234     Expr()->Opnd(1)->Kind() == CK_CONST &&
00235     Expr()->Opnd(1)->Const_val() == Constval())
00236   return TRUE;
00237       if (Expr()->Opnd(1) == Nonconst() && Sign() > 0 &&
00238     Expr()->Opnd(0)->Kind() == CK_CONST && 
00239     Expr()->Opnd(0)->Const_val() == Constval())
00240   return TRUE;
00241     } else if (opr == OPR_SUB) {
00242       if (Expr()->Opnd(0) == Nonconst() && Sign() > 0 &&
00243     Expr()->Opnd(1)->Kind() == CK_CONST &&
00244     Expr()->Opnd(1)->Const_val() == - Constval())
00245   return TRUE;
00246       if (Expr()->Opnd(1) == Nonconst() && Sign() < 0 &&
00247     Expr()->Opnd(0)->Kind() == CK_CONST &&
00248     Expr()->Opnd(0)->Const_val() == Constval())
00249   return TRUE;
00250     } else if (opr == OPR_NEG) {
00251       if (Expr()->Opnd(0) == Nonconst() && Sign() < 0 &&
00252     Constval() == 0)
00253   return TRUE;
00254     }
00255   }
00256   return FALSE;
00257 }
00258 
00259 
00260 //  Return TRUE if there will be no need to insert CVT
00261 //  after canonicalization
00262 BOOL
00263 CANON_EXPR::Type_safe(CODEREP *parent) const
00264 {
00265   if (Nonconst() != NULL && 
00266       Nonconst()->Kind() == CK_VAR &&
00267       Expr()->Kind() == CK_OP) {
00268     MTYPE type1 = OPCODE_rtype(parent->Op());
00269     MTYPE type2 = OPCODE_rtype(Expr()->Op());
00270     if (MTYPE_size_min(type1) == MTYPE_size_min(type2))
00271       return TRUE;
00272     else
00273       return FALSE;
00274   } else 
00275     return TRUE;
00276 }
00277 
00278 
00279 
00280 //  Convert a linear expression into canonical form.
00281 //   
00282 //    Linear expression is of the from:
00283 //        expr -->  expr + expr
00284 //        expr -->  expr - expr
00285 //        expr -->  expr * expr
00286 //        expr -->  - expr
00287 //        expr -->  CK_CONST
00288 //        expr -->  terminal
00289 //        terminal -->  CK_RCONST | CK_LDA | CK_VAR | CK_IVAR
00290 //
00291 void 
00292 CANON_EXPR::Canon_expr(CODEREP *cr, CODEMAP *htable)
00293 {
00294   Set_expr(cr);
00295   switch (cr->Kind()) {
00296   case CK_RCONST:
00297   case CK_LDA:
00298   case CK_VAR:
00299   case CK_IVAR:
00300     // no need to canonicalize
00301     goto no_canon;
00302 
00303   case CK_CONST:
00304     // the type of the constant is maintained in the opcode.
00305     Set_nonconst(NULL);
00306     Set_constval(cr->Const_val());
00307     Set_sign(1);
00308     return;
00309 
00310   case CK_OP:
00311     {
00312       if (cr->Is_isop_flag_set(ISOP_CANON_VISITED)) // save compile time
00313   goto no_canon;
00314 
00315       OPCODE opc = cr->Op();
00316       OPERATOR opr = OPCODE_operator(opc);
00317       CANON_EXPR opnd0, opnd1;
00318       switch (opr) {
00319 
00320       case OPR_NEG:
00321   opnd0.Canon_expr(cr->Opnd(0), htable);
00322   if (!opnd0.Type_safe(cr))
00323     goto no_canon;
00324   Set_constval( -opnd0.Constval());
00325   Set_nonconst( opnd0.Nonconst() );
00326   Set_sign( opnd0.Sign() * -1 );
00327   return;
00328 
00329       case OPR_CVT:
00330   if (opc == OPC_U8I4CVT) {
00331     opnd0.Canon_expr(cr->Opnd(0), htable);
00332     if (!opnd0.Canonicalized())
00333       goto no_canon;
00334     if (opnd0.Nonconst() == NULL) {
00335       Set_nonconst( NULL );
00336       Set_constval( opnd0.Constval() );
00337       Set_sign( opnd0.Sign() );
00338     }
00339     else {
00340       Set_nonconst( htable->Add_unary_node(opc, opnd0.Nonconst()));
00341       Set_constval ( opnd0.Constval());
00342       Set_sign( opnd0.Sign ());
00343     }
00344     return;
00345   }
00346   goto no_canon;
00347 
00348       case OPR_ADD:
00349   opnd0.Canon_expr(cr->Opnd(0), htable);
00350   opnd1.Canon_expr(cr->Opnd(1), htable);
00351   if (!opnd0.Canonicalized() && !opnd1.Canonicalized()) 
00352     goto no_canon;
00353   if (!opnd0.Type_safe(cr) || !opnd1.Type_safe(cr))
00354     goto no_canon;
00355 
00356   Set_constval( opnd0.Constval() + opnd1.Constval() );
00357   if (opnd0.Nonconst() == NULL) {
00358     Set_sign( opnd1.Sign() );
00359     Set_nonconst( opnd1.Nonconst() );
00360   } else if (opnd1.Nonconst() == NULL) {
00361     Set_sign( opnd0.Sign() );
00362     Set_nonconst( opnd0.Nonconst() );
00363   } else {
00364     //  a + b    ==>   1 * (a + b)
00365           //  a + -b   ==>   1 * (a - b)
00366           // -a + b    ==>  -1 * (a - b)
00367     // -a + -b   ==>  -1 * (a + b)
00368     Set_sign( opnd0.Sign() );
00369     if (opnd0.Sign() > 0) {
00370       if (opnd1.Sign() > 0) 
00371         Set_nonconst( htable->Add_bin_node(opc, opnd0.Nonconst(), opnd1.Nonconst()));
00372       else {
00373         OPCODE subop = OPCODE_make_op(OPR_SUB, OPCODE_rtype(opc), MTYPE_V);
00374         Set_nonconst( htable->Add_bin_node(subop, opnd0.Nonconst(), opnd1.Nonconst()));
00375       }
00376     } else {
00377       if (opnd1.Sign() > 0) {
00378         OPCODE subop = OPCODE_make_op(OPR_SUB, OPCODE_rtype(opc), MTYPE_V);
00379         Set_nonconst( htable->Add_bin_node(subop, opnd0.Nonconst(), opnd1.Nonconst()));
00380       } else 
00381         Set_nonconst( htable->Add_bin_node(opc, opnd0.Nonconst(), opnd1.Nonconst()));
00382     }
00383   }
00384   return;
00385 
00386       case OPR_SUB:
00387   opnd0.Canon_expr(cr->Opnd(0), htable);
00388   opnd1.Canon_expr(cr->Opnd(1), htable);
00389   if (!opnd0.Canonicalized() && !opnd1.Canonicalized()) 
00390     goto no_canon;
00391   if (!opnd0.Type_safe(cr) || !opnd1.Type_safe(cr))
00392     goto no_canon;
00393 
00394   Set_constval( opnd0.Constval() - opnd1.Constval() );
00395   if (opnd0.Nonconst() == NULL) {
00396     Set_sign( opnd1.Sign() * -1);
00397     Set_nonconst( opnd1.Nonconst() );
00398   } else if (opnd1.Nonconst() == NULL) {
00399     Set_sign( opnd0.Sign() );
00400     Set_nonconst( opnd0.Nonconst() );
00401   } else {
00402     Set_sign( opnd0.Sign() );
00403     //  a - b   ==>  1 * (a - b)
00404           //  a - -b    ==>  1 * (a + b)
00405           // -a - b     ==> -1 * (a + b)
00406     // -a - -b    ==> -1 * (a - b)
00407     if (opnd0.Sign() > 0) {
00408       if (opnd1.Sign() > 0) 
00409         Set_nonconst( htable->Add_bin_node(opc, opnd0.Nonconst(), opnd1.Nonconst()));
00410       else {
00411         OPCODE addop = OPCODE_make_op(OPR_ADD, OPCODE_rtype(opc), MTYPE_V);
00412         Set_nonconst( htable->Add_bin_node(addop, opnd0.Nonconst(), opnd1.Nonconst()));
00413       }
00414     } else {
00415       if (opnd1.Sign() > 0) {
00416         OPCODE addop = OPCODE_make_op(OPR_ADD, OPCODE_rtype(opc), MTYPE_V);
00417         Set_nonconst( htable->Add_bin_node(addop, opnd0.Nonconst(), opnd1.Nonconst()));
00418       } else
00419         Set_nonconst( htable->Add_bin_node(opc, opnd0.Nonconst(), opnd1.Nonconst()));
00420     }
00421   }
00422   return;
00423 
00424       case OPR_MPY:
00425   opnd0.Canon_expr(cr->Opnd(0), htable);
00426   opnd1.Canon_expr(cr->Opnd(1), htable);
00427   if (!opnd0.Canonicalized() && !opnd1.Canonicalized()) 
00428     goto no_canon;
00429   if (!opnd0.Type_safe(cr) || !opnd1.Type_safe(cr))
00430     goto no_canon;
00431 
00432   {
00433     CANON_EXPR *c = NULL;
00434     CANON_EXPR *x = NULL;
00435     if (opnd0.Is_const() && opnd1.Canonicalized()) {
00436       c = &opnd0;
00437       x = &opnd1;
00438     } else if (opnd1.Is_const() && opnd0.Canonicalized()) {
00439       c = &opnd1;
00440       x = &opnd0;
00441     } else
00442       goto no_canon;
00443 
00444     if (x->Nonconst() == NULL) {
00445       // both x and c are constants
00446       Set_sign(1);
00447       Set_constval( c->Constval() * x->Constval());
00448       Set_nonconst(NULL);
00449     } else {
00450       // c is a constant coderep  
00451       // x is a canonicalized expr (x == sign * expr + c1)
00452       //
00453       // c * (sign * expr + c1) ==> (sign * (c * expr)) + (c * c1)     if (c > 0)
00454       //                        ==> (-sign * (-c * expr)) + (c * c1)   if (c < 0)
00455       //                        ==> 0                                  if (c == 0)
00456       //
00457       if (c->Constval() == 0) {
00458         Set_constval(0);
00459         Set_nonconst(NULL);
00460         Set_sign(1);
00461       } else if (c->Constval() > 0) {
00462         CODEREP *cr = htable->Add_const(OPCODE_rtype(opc), c->Constval());
00463         Set_nonconst( htable->Add_bin_node( opc, x->Nonconst(), cr));
00464         Set_constval( c->Constval() * x->Constval());
00465         Set_sign(x->Sign());
00466       } else {
00467         CODEREP *cr = htable->Add_const(OPCODE_rtype(opc), - c->Constval());
00468         Set_nonconst( htable->Add_bin_node( opc, x->Nonconst(), cr));
00469         Set_constval( c->Constval() * x->Constval());
00470         Set_sign(x->Sign() * -1);
00471       }
00472     }
00473   }
00474   return;
00475 
00476       default:
00477   goto no_canon;
00478       } // switch (opr)
00479     } // CK_OP
00480     
00481   default:
00482     Is_True(FALSE, ("unknown CK_KIND."));
00483   } // switch (cr->Kind())
00484   
00485 no_canon:
00486   if (cr->Kind() == CK_OP)
00487     cr->Set_isop_flag(ISOP_CANON_VISITED);
00488   Set_nonconst(cr);
00489   Set_sign(1);
00490   Set_constval(0);
00491   return;
00492 }
00493 
00494 
00495 // Return non-null CODEREP 
00496 //
00497 CODEREP *
00498 CODEMAP::Canon_base(CODEREP *base, INT64 *ofst)
00499 {
00500   if (WOPT_Enable_Canon_Expr) {
00501     CANON_EXPR expr;
00502     expr.Canon_expr(base, this);
00503     if (expr.Canonicalized() && expr.Constval() != 0) {
00504       INT64 constval = *ofst + expr.Constval();
00505       CODEREP *newbase = expr.Nonconst();
00506       if (expr.Nonconst() == NULL) 
00507   newbase = Add_const(Pointer_type, 0);
00508       if (expr.Sign() < 0) {
00509   if (newbase->Kind() == CK_OP && OPCODE_operator(newbase->Op()) == OPR_SUB)
00510     newbase = Add_bin_node(newbase->Op(), newbase->Opnd(1), newbase->Opnd(0));
00511   else {
00512     OPCODE opc = OPCODE_make_op(OPR_NEG, Pointer_type, MTYPE_V);
00513     newbase = Add_unary_node(opc, newbase);
00514   }
00515       }
00516       // Trim to 16 bit for wopt
00517       if (_phase == MAINOPT_PHASE && (constval < -0x8000 || constval > 0x7fff)
00518     || (((constval >> 31) + 1) >> 1) != 0 /* not fits in 32 bits */ ) {
00519   // make multiple32K one of the values: -96K, -32K, 32K, 96K, 160K, etc
00520   INT64 multiple32K = ((constval + 0x8000) >> 16) << 16;
00521   if (multiple32K > 0) {
00522     OPCODE opc = OPCODE_make_op(OPR_ADD, Pointer_type, MTYPE_V);
00523     newbase = Add_bin_node(opc, newbase, Add_const(Pointer_type, multiple32K));
00524   } else {
00525     OPCODE opc = OPCODE_make_op(OPR_SUB, Pointer_type, MTYPE_V);
00526     newbase = Add_bin_node(opc, newbase, Add_const(Pointer_type, -multiple32K));
00527   }
00528   constval =  constval - multiple32K;
00529       }
00530       if (Get_Trace(TP_GLOBOPT, PROP_DUMP_FLAG)) {
00531   fprintf(TFile, "Before Canon_base:\n");
00532   base->Print(0,TFile);
00533   fprintf(TFile, "After Canon_base:\n");
00534   newbase->Print(0,TFile);
00535   fprintf(TFile, "\n");
00536       }
00537       *ofst = constval;  // update offset
00538       return newbase;
00539     }
00540   }
00541   return NULL;
00542 }
00543 
00544 
00545 CODEREP *
00546 CODEMAP::Canon_rhs(CODEREP *rhs)
00547 {
00548   if (WOPT_Enable_Canon_Expr) {
00549     CANON_EXPR expr;
00550     expr.Canon_expr(rhs, this);
00551     if (expr.Canonicalized() && !expr.Trivial()) {
00552       CODEREP *newrhs = expr.Nonconst();
00553       MTYPE rtype = rhs->Kind() == CK_OP ? OPCODE_rtype(rhs->Op()) : rhs->Dtyp();
00554       if (expr.Nonconst() == NULL) 
00555   newrhs = Add_const(rtype, expr.Constval());
00556       else {
00557   if (expr.Sign() < 0) {
00558     if (newrhs->Kind() == CK_OP && OPCODE_operator(newrhs->Op()) == OPR_SUB) 
00559       newrhs = Add_bin_node(newrhs->Op(), newrhs->Opnd(1), newrhs->Opnd(0));
00560     else {
00561       OPCODE opc = OPCODE_make_op(OPR_NEG, rtype, MTYPE_V);
00562       newrhs = Add_unary_node(opc, newrhs);
00563     }
00564   } 
00565   if (expr.Constval() != 0) {
00566     if (expr.Constval() > 0) {
00567       OPCODE opc = OPCODE_make_op(OPR_ADD, rtype, MTYPE_V);
00568       newrhs = Add_bin_node(opc, newrhs, Add_const(rtype, expr.Constval()));
00569     } else {
00570       OPCODE opc = OPCODE_make_op(OPR_SUB, rtype, MTYPE_V);
00571       newrhs = Add_bin_node(opc, newrhs, Add_const(rtype, -expr.Constval()));
00572     }
00573   }
00574       }
00575       if (Get_Trace(TP_GLOBOPT, PROP_DUMP_FLAG)) {
00576   fprintf(TFile, "Before Canon_rhs:\n");
00577   rhs->Print(0,TFile);
00578   fprintf(TFile, "After Canon_rhs:\n");
00579   newrhs->Print(0,TFile);
00580   fprintf(TFile, "\n");
00581       }
00582       return newrhs;
00583     } 
00584   }
00585   return NULL;
00586 }
00587 
00588 
00589 // Canonicalize comparison into the form into
00590 //  1)   iv compare_op invar
00591 //  2)   iv * invar compare_op invar
00592 //  3)   invar * iv compare_op invar
00593 //  4)   invar compare_op iv
00594 //  5)   invar compare_op iv * invar
00595 //  6)   invar compare_op invar * iv
00596 //
00597 // It is nice to have just form 1 and 2.  However, the simplifier is
00598 // free to rearrange the comparion into forms 3-6.
00599 //
00600 //  If the final form is 2, 3, 5 or 6.  Undo the canonicalization
00601 //  because strength reduction may introduce extra variable.
00602 //
00603 CODEREP *
00604 CODEMAP::Separate_iv_invar(CODEREP *cr, BB_NODE *curbb)
00605 {
00606   if (WOPT_Enable_Compare_Simp && 
00607       OPCODE_is_compare(cr->Op()) &&
00608       MTYPE_is_integral(OPCODE_desc(cr->Op())) &&
00609       (OPCODE_operator(cr->Op()) == OPR_NE ||
00610        OPCODE_operator(cr->Op()) == OPR_EQ)) {
00611     CODEREP *iv = NULL;
00612     CODEREP *invar = NULL;
00613     BOOL swapped = FALSE;
00614     if (curbb->Innermost()->Invariant_cr(cr->Opnd(1))) {
00615       iv = cr->Opnd(0);
00616       invar = cr->Opnd(1);
00617     } else if (curbb->Innermost()->Invariant_cr(cr->Opnd(0))) {
00618       iv = cr->Opnd(1);
00619       invar = cr->Opnd(0);
00620       swapped = TRUE;
00621     }
00622     if (invar != NULL && !curbb->Innermost()->Invariant_cr(iv)) {
00623       BOOL cont = TRUE;
00624       while (iv->Kind() == CK_OP && cont) {
00625   switch (OPCODE_operator(iv->Op())) {
00626   case OPR_NEG:
00627     invar = Add_unary_node(iv->Op(), invar);
00628     iv = iv->Opnd(0);
00629     swapped = !swapped;  // toggle
00630     break;
00631   case OPR_ADD:
00632     {
00633       OPCODE subop = OPCODE_make_op(OPR_SUB, OPCODE_rtype(iv->Op()), MTYPE_V);
00634       if (curbb->Innermost()->Invariant_cr(iv->Opnd(0))) {
00635 #ifdef KEY // bug 4959 wraparound will cause problem
00636         if (OPCODE_rtype(subop) == MTYPE_U4 &&
00637       invar->Kind() == CK_CONST && iv->Opnd(0)->Kind() ==CK_CONST &&
00638       invar->Const_val() < iv->Opnd(0)->Const_val()) {
00639           cont = FALSE;
00640     break;
00641         }
00642 #endif
00643         invar = Add_bin_node_and_fold(subop, invar, iv->Opnd(0));
00644         iv = iv->Opnd(1);
00645       } else {
00646 #ifdef KEY // bug 4959 wraparound will cause problem
00647         if (OPCODE_rtype(subop) == MTYPE_U4 &&
00648       invar->Kind() == CK_CONST && iv->Opnd(1)->Kind() ==CK_CONST &&
00649       invar->Const_val() < iv->Opnd(1)->Const_val()) {
00650           cont = FALSE;
00651     break;
00652         }
00653 #endif
00654         invar = Add_bin_node_and_fold(subop, invar, iv->Opnd(1));
00655         iv = iv->Opnd(0);
00656       }
00657     }
00658     break;
00659   case OPR_SUB:
00660     if (curbb->Innermost()->Invariant_cr(iv->Opnd(0))) {
00661       invar = Add_bin_node_and_fold(iv->Op(), iv->Opnd(0), invar);
00662       iv = iv->Opnd(1);
00663       swapped = !swapped; // toggle
00664     } else {
00665       OPCODE addop = OPCODE_make_op(OPR_ADD, OPCODE_rtype(iv->Op()), MTYPE_V);
00666       invar = Add_bin_node_and_fold(addop, invar, iv->Opnd(1));
00667       iv = iv->Opnd(0);
00668     }
00669     break;
00670   default:
00671     cont = FALSE;
00672     break;
00673   }
00674       }
00675       if (iv->Kind() != CK_VAR)
00676   return NULL;
00677 
00678       // Do not apply canon_cmp to any var other primary IV.
00679       CODEREP *primary_iv = curbb->Innermost()->Iv();
00680       if (primary_iv == NULL ||
00681     primary_iv->Kind() != CK_VAR ||
00682     iv->Aux_id() != primary_iv->Aux_id())
00683   return NULL;
00684 
00685       if (!swapped) {
00686   if (cr->Opnd(0) != iv) {
00687     cr->Set_opnd(0, iv);
00688     cr->Set_opnd(1, invar);
00689     return cr;
00690   }
00691       } else {
00692   if (cr->Opnd(1) != iv) {
00693     cr->Set_opnd(0, invar);
00694     cr->Set_opnd(1, iv);
00695     return cr;
00696   }
00697       }
00698     }
00699   }
00700   return NULL;
00701 }
00702 
00703 // This routine perform canonicalization on comparison expressions 'cr',
00704 // and returns TRUE if this expression is canonicalized.
00705 BOOL
00706 CODEMAP::Canonicalize_compare(CODEREP *cr, BB_NODE *curbb, BOOL *modified)
00707 {
00708   OPCODE op = cr->Op();
00709   if (!OPCODE_is_compare(op)) return FALSE;
00710 
00711   // Separate invariant and variant to either side of the operator
00712   *modified = Separate_iv_invar(cr, curbb) != NULL;
00713     
00714   // Swap the kids of the compare opcode
00715   //   if curbb inside loop,
00716   //      the LHS is a loop variant and RHS is a loop invariant
00717   //   otherwise
00718   //      move constant to the RHS
00719   const BB_LOOP *loop = Cfg()->Find_innermost_loop_contains( curbb );
00720   CODEREP *lhs = cr->Get_opnd(0), *rhs = cr->Get_opnd(1);
00721   BOOL swapped = FALSE;
00722   if (loop) { // the comparison is inside a loop
00723     if (!loop->Invariant_cr(lhs)) return TRUE; // canonicalized already
00724     else if (loop->Invariant_cr(rhs)) return FALSE; // nothing can be
00725                                                      // done
00726     else {
00727       cr->Set_opnd(0, rhs);
00728       cr->Set_opnd(1, lhs);
00729       swapped = TRUE;
00730       *modified = TRUE;
00731     }
00732   }
00733   else {
00734     if (lhs->Kind() == CK_VAR) {
00735       if (rhs->Kind() == CK_VAR)
00736         return FALSE; // cannot not do better, leave it as default
00737       else
00738         return TRUE;  // make sure the CK_VAR stay on the left
00739     }
00740     else {
00741       // might need swapping
00742       if (rhs->Kind() == CK_VAR){
00743         cr->Set_opnd(0, rhs);
00744         cr->Set_opnd(1, lhs);
00745         swapped = TRUE;
00746         *modified = TRUE;
00747       }
00748       else
00749         return FALSE;
00750     }
00751   }
00752 
00753   if (swapped)
00754     switch (OPCODE_operator(op)) {
00755     case OPR_LT:
00756       cr->Set_opr(OPR_GT);
00757       break;
00758     case OPR_LE:
00759       cr->Set_opr(OPR_GE);
00760       break;
00761     case OPR_GT:
00762       cr->Set_opr(OPR_LT);
00763       break;
00764     case OPR_GE:
00765       cr->Set_opr(OPR_LE);
00766       break;
00767     }
00768   return TRUE;
00769 }