osprey/be/lno/snl_utils.h

Go to the documentation of this file.

/*

  Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.

  This program is free software; you can redistribute it and/or modify it
  under the terms of version 2 of the GNU General Public License as
  published by the Free Software Foundation.

  This program is distributed in the hope that it would be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

  Further, this software is distributed without any warranty that it is
  free of the rightful claim of any third person regarding infringement 
  or the like.  Any license provided herein, whether implied or 
  otherwise, applies only to this software file.  Patent licenses, if 
  any, provided herein do not apply to combinations of this program with 
  other software, or any other product whatsoever.  

  You should have received a copy of the GNU General Public License along
  with this program; if not, write the Free Software Foundation, Inc., 59
  Temple Place - Suite 330, Boston MA 02111-1307, USA.

  Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
  Mountain View, CA 94043, or:

  http://www.sgi.com

  For further information regarding this notice, see:

  http://oss.sgi.com/projects/GenInfo/NoticeExplan

*/


// -*-C++-*-

#ifndef snl_utils_INCLUDED
#define snl_utils_INCLUDED "snl_utils.h"

#ifdef _KEEP_RCS_ID
static char *snl_utils_rcs_id = snl_utils_INCLUDED "$Revision$";
#endif /* _KEEP_RCS_ID */

#ifndef mat_INCLUDED
#include "mat.h"
#endif

#ifndef snl_xbounds_INCLUDED
#include "snl_xbounds.h"
#endif

//-----------------------------------------------------------------------
// TODO FIX Compilation hacks
//-----------------------------------------------------------------------

extern BOOL Is_Lexpos(DEPV*, INT dims);
extern BOOL Is_Lexpos(DEPV_ARRAY*);
extern MEM_POOL SNL_local_pool;

//-----------------------------------------------------------------------
// end compilation hacks
//-----------------------------------------------------------------------

//-----------------------------------------------------------------------
// Globals
//-----------------------------------------------------------------------

#define UCTILE_T  0x1
#define UCTILE_I  0x2
#define UCTILE_O  0x4

struct SNL_REGION {
  WN* First;
  WN* Last;
  SNL_REGION(WN* f, WN* l) : First(f), Last(l) {}
  SNL_REGION() : First(NULL), Last(NULL) {}
  BOOL operator == (SNL_REGION r) const
    {return First == r.First && Last == r.Last;}
  BOOL operator != (SNL_REGION r) const
    {return First != r.First || Last != r.Last;}
};

enum SNL_INV_CACHE_BLOCK_REASON {
  SNL_INV_UNDEFINED,
  SNL_INV_TILE_ONLY,
  SNL_INV_SE_ONLY,
  SNL_INV_TILE_SE,
  SNL_INV_LEGO_TILE,
  SNL_INV_MP_TILE,
  SNL_INV_DOACROSS_TILE
};

#define SNL_MAX_LOOPS LNO_MAX_DO_LOOP_DEPTH

class SNL_TILE_INFO {

 public:

  SNL_TILE_INFO(WN** loop, const IMAT& L,
                const INT* striplevel, MEM_POOL* pool);   // unimplemented

  SNL_TILE_INFO(INT nloops, INT strips,
                const INT* iloop, const INT* stripsz, const INT* striplevel,
                SNL_INV_CACHE_BLOCK_REASON reason[], MEM_POOL* pool);

  ~SNL_TILE_INFO() {}

  MEM_POOL*     Pool() const {return _pool;}
  BOOL          Rectangular() const {return _rectangular;}
  void          Print(FILE*) const;
  const IMAT&   L() const {return _l;}
  const IMAT&   KHT() const {return _kht;}
  INT           K() const {return _k;}
  INT           Striplevel(INT i) const {return _striplevel[i];}

  // these are only interesting if Rectangular() is TRUE.

  INT           Iloop(INT i) const {return _iloop[i];}
  INT           Stripsz(INT i) const {return _stripsz[i];}
  INT           Nloops() const {return _l.Rows();}
  INT           Strips() const {return _l.Cols();}
  SNL_INV_CACHE_BLOCK_REASON Reason(INT i) const {return _reason[i];}

 private:

  // these are undefined

  SNL_TILE_INFO();
  SNL_TILE_INFO& operator = (SNL_TILE_INFO&);
  SNL_TILE_INFO(const SNL_TILE_INFO&);

  MEM_POOL*     _pool;
  BOOL          _rectangular;

  IMAT          _l;
  IMAT          _kht;
  INT           _k;
  INT           _striplevel[SNL_MAX_LOOPS];

  // only interesting when _rectangular is true

  INT           _iloop[SNL_MAX_LOOPS];
  INT           _stripsz[SNL_MAX_LOOPS];
  SNL_INV_CACHE_BLOCK_REASON _reason[SNL_MAX_LOOPS];
};


// The SNL_TRANS_INDEX_DATA holds information about the loop index variables
// before and after transformation.  It assumes optional unimodular transf
// followed by optional tiling transf.  It's in a nice simple array format.
// It is meant to augment SNL_BOUNDS_INFO putting the sym_list in a nicer
// format with more data.

class SNL_TRANS_INDEX_DATA {

 public:

  struct TDATA {
    SYMBOL              symbol;         // symbol of the tile loop index
    WN*                 alias_wn;       // NULL initialized but set by
                                        // U_Ctiling before used.
  };
  struct IDATA {
    SYMBOL              pre_symbol;     // symbol of the index, before ut
    WN*                 pre_alias_wn;   // use an ldid of the symbol before
                                        // transformation
    SYMBOL              post_symbol;    // symbol of the index, after ut
    WN*                 post_alias_wn;  // wn with the same alias information
    WN*                 newcode;        // pre_symbol->newcode, unparentized
    INT                 max_used_depth; // depth of deepest index in newcode
    WN*                 lbtest;         // index==lb, in transformed space
    WN*                 ubtest;         // index==ub, in transformed space

  };
  struct ODATA {
    SYMBOL              symbol;         // symbol of the symbolic constant
    WN*                 alias_wn;       // a fake ldid with with correct
                                        // alias and DU information
  };

 public:

  SNL_TRANS_INDEX_DATA(const IMAT* u, const IMAT* uinv,
                       const IMAT* kht, const SNL_BOUNDS_INFO* bi,
                       DOLOOP_STACK* stack, INT first_in_stack,
                       SNL_TILE_INFO* ti, MEM_POOL* p);
  ~SNL_TRANS_INDEX_DATA();

 public:

  INT           t_nloops;       // number of tile loops
  INT           i_nloops;       // original loop nest depth
  INT           o_nloops;       // symbolic variable count

  TDATA*        tdata;          // tile data
  IDATA*        idata;          // index data
  ODATA*        odata;          // other symbolic variable data

  MEM_POOL*     pool;           // from where this data structure was allocated

  void          Print(FILE*) const;
};

extern void SNL_Sanity_Check_Func(WN* wn);

#ifdef Is_True_On
extern void SNL_Sanity_Check_Block(WN* wn);
extern void SNL_Sanity_Check_Loop(WN* wn);
extern void SNL_Sanity_Check_If(WN* wn);
extern void SNL_Sanity_Check_Region(SNL_REGION region);
extern WN*  SNL_Sanity_Check_Exp(WN* wn);
#endif

//-----------------------------------------------------------------------
// SNL-specific stuff
//-----------------------------------------------------------------------
enum SNL_MONO {
  SNL_MONO_INVARIANT,
  SNL_MONO_INC,
  SNL_MONO_DEC,
  SNL_MONO_OTHER
};

extern SNL_MONO Mono(WN* wn, SYMBOL symbol, BOOL neg =FALSE);
void    Print_Do_Stack(FILE* f, const DOLOOP_STACK *);

//------------------------------------------------------------------------
// External Functions
//------------------------------------------------------------------------

class DEF_LIST;

extern void Increase_By(WN* wn, INT c, WN* parent =NULL, INT kid = -1);

extern WN* LWN_Create_Block_From_Stmts_Above(WN* wn);
extern WN* LWN_Create_Block_From_Stmts_Below(WN* wn);
extern INT64  Iterations(WN* loop, MEM_POOL* pool); 
extern WN* Find_Next_Innermost_Do(WN* loop);
extern DOLOOP_STACK* Copy_Dostack(const DOLOOP_STACK& stack, MEM_POOL*);

extern MEM_POOL SNL_local_pool;
extern INT Renumber_Loops(WN* first, WN* last, ARRAY_DIRECTED_GRAPH16* =NULL);

extern void Dump_WN(SNL_REGION, FILE*, INT,
        INT = 2, INT = 2, WN** = NULL, WN* = NULL,
        ARRAY_DIRECTED_GRAPH16* =NULL);

extern void SNL_Add_Du_To_Index_Ldid(WN* loop, WN* ldid, DU_MANAGER*, BOOL);
extern void SNL_Change_Du_To_Index_Ldid(WN* loop, WN* code, DU_MANAGER*, BOOL);
extern void SNL_Change_Du_Pointer(WN* oldptr, WN* ptr, WN* body, DU_MANAGER*);
extern void SNL_Print_Ldid_Pointers(WN* wn);

const DEF_LIST* Find_Def_List_In_Exp(WN* exp, const SYMBOL& sym);
WN* Find_Use_In_Exp(WN* exp, const SYMBOL& sym);
WN* SNL_Copy_Exp(WN*);
void SNL_Fix_Index_Pointers(WN* loop, WN* wn);

extern WN*& SNL_UBexp(WN* snl_end, BOOL* ne = NULL);
extern WN*& SNL_UBvar(WN* snl_end);
extern WN* Good_Do_Next_Innermost(WN* doloop);
extern void SNL_Optimize_Bounds(SNL_REGION region);

extern BOOL SNL_Is_Non_Varying_Access_Array(ACCESS_ARRAY* aa,
                                            INT outer_depth);

extern WN* SNL_Get_Inner_Snl_Loop(WN* outer, INT nloops);

extern BOOL SNL_Is_Invariant(DOLOOP_STACK *stack,
                        INT d,
                        INT dd);

extern INT SNL_Loop_Count(WN* wn_snl); 

extern WN* SNL_Innermost_Do(WN* wn_outer); 

extern INT Is_Inner_SNL(WN* wn_loop);

extern void SNL_Upper_Bound_Standardize(WN* wn_outer, INT nloops);

extern BOOL Valid_SNL_Region(SNL_REGION region); 

extern BOOL Need_Fix_Array_Deps_On_Index_Variable(WN* wn_loop); 

extern BOOL SNL_Fix_Array_Deps_On_Index_Variable(WN* wn_outer, INT nloops); 

extern WN* Next_SNL_Loop(WN* wn_outer); 

extern IMAT* Permutation_To_Unimodular(INT permutation[], INT nloops);

extern INT* Unimodular_To_Permutation(IMAT* unimodular);

extern WN* generate_tree_from_row(const mINT32* m, SNL_TRANS_INDEX_DATA* td,
  INT64 c, TYPE_ID wtype, INT part);

extern WN* generate_tree_from_bounds_info_row(const mINT32* row,
  mINT64 con, BOOL le, const SNL_BOUNDS_SYMBOL_LIST*vi);

extern void Fix_Do_Du_Info(WN* wn, SNL_TRANS_INDEX_DATA* td,
                           BOOL recursive, WN* loops,
                           INT  only_in_nloops);

extern void SNL_Rebuild_Access_Arrays(WN* wn_outerloop);

//-----------------------------------------------------------------------
//-----------------------------------------------------------------------
//-----------------------------------------------------------------------
// Debugging utilities
//-----------------------------------------------------------------------
//-----------------------------------------------------------------------
//-----------------------------------------------------------------------

#define SNL_DEBUG0(level, string)     \
    ((snl_debug < level) ? 0 :      \
   (fprintf(TFile, "SNL DEBUG: "),\
    fprintf(TFile, string),\
    fprintf(TFile, "\n")))

#define SNL_DEBUG1(level, string, v1)     \
    ((snl_debug < level) ? 0 :      \
   (fprintf(TFile, "SNL DEBUG: "),\
    fprintf(TFile, string, v1),\
    fprintf(TFile, "\n")))

#define SNL_DEBUG2(level, string, v1, v2)   \
    ((snl_debug < level) ? 0 :      \
   (fprintf(TFile, "SNL DEBUG: "),\
    fprintf(TFile, string, v1, v2),\
    fprintf(TFile, "\n")))

#define SNL_DEBUG3(level, string, v1, v2, v3)   \
    ((snl_debug < level) ? 0 :      \
   (fprintf(TFile, "SNL DEBUG: "),\
    fprintf(TFile, string, v1, v2, v3),\
    fprintf(TFile, "\n")))

#endif

---