Open64: osprey/be/lno/cache_model.h 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 
00156 #ifndef cache_model_INCLUDED
00157 #define cache_model_INCLUDED "cache_model.h"
00158 
00159 
00160 #ifdef _KEEP_RCS_ID
00161 static char *cache_model_rcs_id = cache_model_INCLUDED "$Revision: 1.5 $";
00162 #endif /* _KEEP_RCS_ID */
00163 
00164 #ifndef defs_INCLUDED
00165 #include "defs.h"
00166 #endif
00167 
00168 class ARRAY_REF;
00169 // class DOLOOP_STACK;
00170 
00274 enum FORMULA_OP {
00275   FORMULA_BAD = 666,
00276 
00277   FORMULA_ADD = 1001,   // to keep random stuff from working
00278   FORMULA_SUB,
00279   FORMULA_MUL,
00280   FORMULA_DIV,
00281   FORMULA_MAX,
00282   FORMULA_MIN,
00283   FORMULA_GE,
00284   FORMULA_GT,
00285   FORMULA_LE,
00286   FORMULA_LT,
00287   FORMULA_AND,
00288   FORMULA_OR,
00289   FORMULA_COND,         // execute LHS if Cond != 0, RHS otherwise
00290   FORMULA_FCONST,
00291   FORMULA_VAR,          // read from 'vars' parameter
00292   FORMULA_SET,          // set _scratch register
00293   FORMULA_USE,          // use _scratch register
00294   FORMULA_COMMA         // left child probably a set
00295 };
00296 
00297 // Set Fpool, the pool to use.  Call New to get new elements.
00298 // Elements are freed by freeing the pool -- there is no need for a
00299 // destructor.
00300 
00301 // Note that you can preset valued in the array v, but you can also
00302 // have the formula itself set a value with Set.
00303 
00304 class FORMULA {
00305 
00306  public:
00307 
00308   void                  Print(FILE* f, FORMULA_OP parent) const;
00309   enum                  {SCRATCH_REGISTERS = 10*LNO_MAX_DO_LOOP_DEPTH};
00310 
00311 
00312   double                Eval(INT nvars, const double* vars) const;
00313   double                Eval(INT nvars, const mINT64* vars) const;
00314   double                Eval(INT nvars, const mINT32* vars) const;
00315 
00316   FORMULA*              Add_To_Variable(INT var, INT val);
00317 
00318   FORMULA*              Duplicate() const;
00319   void                  Print(FILE* f) const {Print(f, FORMULA_BAD);}
00320 
00321   static MEM_POOL* Fpool;
00322   inline static FORMULA* Var(INT v) {
00323     FmtAssert(Fpool, ("Fpool uninitialized"));
00324     return CXX_NEW(FORMULA(v, FALSE), Fpool);
00325   }
00326   inline static FORMULA* Use(INT v) {
00327     FmtAssert(Fpool, ("Fpool uninitialized"));
00328     return CXX_NEW(FORMULA(v, TRUE), Fpool);
00329   }
00330   inline static FORMULA* Set(INT v, FORMULA* f) {
00331     FmtAssert(Fpool, ("Fpool uninitialized"));
00332     return CXX_NEW(FORMULA(v, f), Fpool);
00333   }
00334   inline static FORMULA* Set0(INT v, FORMULA* f) {
00335     FmtAssert(Fpool, ("Fpool uninitialized"));
00336     return Set(v,f?f:Const(0.0));
00337   }
00338   inline static FORMULA* Const(double v) {
00339     FmtAssert(Fpool, ("Fpool uninitialized"));
00340     return CXX_NEW(FORMULA(v), Fpool);
00341   }
00342   inline static FORMULA* Cond(FORMULA* cond, FORMULA* left, FORMULA* right) {
00343     FmtAssert(Fpool, ("Fpool uninitialized"));
00344     return CXX_NEW(FORMULA(cond, left, right), Fpool);
00345   }
00346   inline static FORMULA* Comma(FORMULA* left, FORMULA* right) {
00347     FmtAssert(Fpool, ("Fpool uninitialized"));
00348     return CXX_NEW(FORMULA(FORMULA_COMMA, left, right), Fpool);
00349   }
00350   inline static FORMULA* Comma3(FORMULA* c1, FORMULA* c2, FORMULA* c3) {
00351     FmtAssert(Fpool, ("Fpool uninitialized"));
00352     return Comma(c1, Comma(c2, c3));
00353   }
00354   inline static FORMULA* Comma4(FORMULA* c1, FORMULA* c2,
00355                                 FORMULA* c3, FORMULA* c4) {
00356     FmtAssert(Fpool, ("Fpool uninitialized"));
00357     return Comma(c1, Comma3(c2, c3, c4));
00358   }
00359   inline static FORMULA* Comma5(FORMULA* c1, FORMULA* c2,
00360                                 FORMULA* c3, FORMULA* c4, FORMULA* c5) {
00361     FmtAssert(Fpool, ("Fpool uninitialized"));
00362     return Comma(c1, Comma4(c2, c3, c4, c5));
00363   }
00364   inline static FORMULA* Add(FORMULA* left, FORMULA* right) {
00365     FmtAssert(Fpool, ("Fpool uninitialized"));
00366     return CXX_NEW(FORMULA(FORMULA_ADD, left, right), Fpool);
00367   }
00368   inline static FORMULA* Sub(FORMULA* left, FORMULA* right) {
00369     FmtAssert(Fpool, ("Fpool uninitialized"));
00370     return CXX_NEW(FORMULA(FORMULA_SUB, left, right), Fpool);
00371   }
00372   inline static FORMULA* Mul(FORMULA* left, FORMULA* right) {
00373     FmtAssert(Fpool, ("Fpool uninitialized"));
00374     return CXX_NEW(FORMULA(FORMULA_MUL, left, right), Fpool);
00375   }
00376   inline static FORMULA* Div(FORMULA* left, FORMULA* right) {
00377     FmtAssert(Fpool, ("Fpool uninitialized"));
00378     return CXX_NEW(FORMULA(FORMULA_DIV, left, right), Fpool);
00379   }
00380   inline static FORMULA* Max(FORMULA* left, FORMULA* right) {
00381     FmtAssert(Fpool, ("Fpool uninitialized"));
00382     return CXX_NEW(FORMULA(FORMULA_MAX, left, right), Fpool);
00383   }
00384   inline static FORMULA* Min(FORMULA* left, FORMULA* right) {
00385     FmtAssert(Fpool, ("Fpool uninitialized"));
00386     return CXX_NEW(FORMULA(FORMULA_MIN, left, right), Fpool);
00387   }
00388   inline static FORMULA* Ge(FORMULA* left, FORMULA* right) {
00389     FmtAssert(Fpool, ("Fpool uninitialized"));
00390     return CXX_NEW(FORMULA(FORMULA_GE, left, right), Fpool);
00391   }
00392   inline static FORMULA* Gt(FORMULA* left, FORMULA* right) {
00393     FmtAssert(Fpool, ("Fpool uninitialized"));
00394     return CXX_NEW(FORMULA(FORMULA_GT, left, right), Fpool);
00395   }
00396   inline static FORMULA* Le(FORMULA* left, FORMULA* right) {
00397     FmtAssert(Fpool, ("Fpool uninitialized"));
00398     return CXX_NEW(FORMULA(FORMULA_LE, left, right), Fpool);
00399   }
00400   inline static FORMULA* Lt(FORMULA* left, FORMULA* right) {
00401     FmtAssert(Fpool, ("Fpool uninitialized"));
00402     return CXX_NEW(FORMULA(FORMULA_LT, left, right), Fpool);
00403   }
00404   inline static FORMULA* And(FORMULA* left, FORMULA* right) {
00405     FmtAssert(Fpool, ("Fpool uninitialized"));
00406     return CXX_NEW(FORMULA(FORMULA_OR, left, right), Fpool);
00407   }
00408   inline static FORMULA* Or(FORMULA* left, FORMULA* right) {
00409     FmtAssert(Fpool, ("Fpool uninitialized"));
00410     return CXX_NEW(FORMULA(FORMULA_OR, left, right), Fpool);
00411   }
00412 
00413   // debugging aid
00414   ~FORMULA() {
00415     _fop = FORMULA_BAD;
00416   }
00417 
00418  private:
00419 
00420   FORMULA(double v) {
00421     _fop = FORMULA_FCONST;
00422     _fconst = v;
00423   }
00424   FORMULA(INT v, BOOL use_reg) {
00425     _fop = use_reg ? FORMULA_USE : FORMULA_VAR;
00426     _var = v;
00427   }
00428   FORMULA(INT v, FORMULA* f) {
00429     _fop = FORMULA_SET;
00430     _var = v;
00431     _kids.Left = f;
00432   }
00433   FORMULA(FORMULA_OP fop, FORMULA* left, FORMULA* right) {
00434     Is_True(left && right, ("Missing child for FORMULA::FORMULA()"));
00435     Is_True(fop == FORMULA_ADD || fop == FORMULA_SUB ||
00436             fop == FORMULA_MUL || fop == FORMULA_DIV ||
00437             fop == FORMULA_MAX || fop == FORMULA_MIN ||
00438             fop == FORMULA_GE || fop == FORMULA_GT ||
00439             fop == FORMULA_LE || fop == FORMULA_LT ||
00440             fop == FORMULA_AND || fop == FORMULA_OR ||
00441             fop == FORMULA_COMMA,
00442             ("Bad call to formula constructor: fop=%d", fop));
00443     _fop = fop;
00444     _kids.Left = left;
00445     _kids.Right = right;
00446   }
00447   FORMULA(FORMULA* cond, FORMULA* left, FORMULA* right) {
00448     Is_True(left && right && cond, ("Missing child for FORMULA::FORMULA()"));
00449     _fop = FORMULA_COND;
00450     _kids.Cond = cond;
00451     _kids.Left = left;
00452     _kids.Right = right;
00453   }
00454 
00455   double                Eval(const double* vars) const;
00456   double                Eval_Inlined(const double* vars) const {
00457     if (_fop == FORMULA_FCONST)
00458       return _fconst;
00459     else if (_fop == FORMULA_VAR)
00460       return vars[_var];
00461     else
00462       return Eval(vars);
00463   }
00464 
00465   FORMULA_OP    _fop;
00466   union {
00467     double      _fconst;
00468     INT         _var;
00469   };   // wasting some space, since Cond and Right could go in here too.
00470   struct {
00471     FORMULA*          Cond;
00472     FORMULA*          Left;
00473     FORMULA*          Right;
00474   }             _kids;
00475 
00476   static double _scratch[SCRATCH_REGISTERS];
00477 };
00478 
00479 class COMPUTE_FOOTPRINT_RVAL {
00480   FORMULA*      _formula;          // sum of Wformula and Rformula
00481  public:
00482   FORMULA*      RFormula;          // formula for reads
00483   FORMULA*      WFormula;          // formula for writes
00484   FORMULA*      AllFormula();      // total ... use only after
00485                                    // RFormula and Wformula are final
00486   INT           D;
00487   COMPUTE_FOOTPRINT_RVAL() :
00488         WFormula(NULL), RFormula(NULL), _formula(NULL), D(0) {}
00489   void          Print(FILE* f) const;
00490 };
00491 
00492 extern void Set_Cache_Model_Statics(INT mhd_level); 
00493 
00494 extern COMPUTE_FOOTPRINT_RVAL Compute_Footprint(
00495                     const ARRAY_REF*  arl,
00496                     INT               nloops,   // to be tiled
00497                     const INT*        loops,    // to be tiled
00498                     const INT*        arl_stripsz,
00499                     const INT64*      est_iters,
00500                     const INT64*      max_iters,
00501                     const INT*        unrolls,
00502                     INT               depth,
00503                     INT               stripdepth,
00504                     const INT*        permute_order,
00505                     INT               v_first,
00506                     INT64             outersz,
00507                     BOOL              using_tlb,
00508                     INT               middle_loop_no);
00509 
00510 void Cache_Model(ARRAY_REF* arl,
00511                  INT depth,
00512                  INT required_inner,
00513                  const INT* legal_inners,
00514                  INT nlegal_inners,
00515                  const INT* legal_tiles,
00516                  INT nlegal_tiles,
00517                  const INT* unrolls,
00518                  const DOLOOP_STACK* stack,
00519      BOOL blocking_disabled,
00520      const INT *required_blocksize,
00521                  double model_cost,
00522      INT num_refs,
00523 
00524                  INT* new_order,                       // array
00525                  INT* nstrips,                         // return val
00526                  INT* stripdepth,                      // return val
00527                  INT* iloop,                           // return array
00528                  INT* stripsz,                         // return array
00529                  INT* striplevel,                      // return array
00530                  double* cycles_per_iter,              // scalar
00531      double* doverhead_best);        // scalar
00532 #endif