//-*-c++-*-
// ====================================================================
// ====================================================================
//
// Module: opt_ssa.h
// $Revision: 1.2 $
// $Date: 2003/03/04 06:16:04 $
//
// Revision history:
//  4-OCT-94 shin - Original Version
//
// ====================================================================
//
// 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
//
// ====================================================================
//
// Description:
//
// ====================================================================
// ====================================================================


#ifndef opt_ssa_INCLUDED
#define opt_ssa_INCLUDED	"opt_ssa.h"

#include "defs.h"
#include "opt_defs.h"
#include "cxx_memory.h"
#include "opt_sym.h"

//  Forward declaration
class CFG;
class OPT_STAB;
class BB_NODE;
class BB_LIST;
class STMTREP;
class COLOR;
class PHI_LIST;
class COPYPROP;
class EXC;
class EXC_SCOPE;

class SSA {
private:
  MEM_POOL *mem_pool;
  MEM_POOL *loc_pool;  
  CFG      *_cfg;
  CODEMAP  *_htable;
  OPT_STAB *_opt_stab;

            SSA(void);
            SSA(const SSA&);
            SSA& operator = (const SSA&);

  OPT_STAB *Opt_stab(void)    { return _opt_stab; }
  CFG      *Cfg(void)         { return _cfg; }
  CODEMAP  *Htable(void)      { return _htable; }

  void      Collect_defs_bb(MEM_POOL *);
  void      Place_phi_node(MEM_POOL *);
  BB_NODE  *Insert_identity_assignment_4_loopexit(BB_NODE *,AUX_ID,MEM_POOL *);
  void      Insert_identity_assignment_4_entry(CFG *cfg, OPT_STAB *opt_stab);
  void      Rename(CFG *cfg, OPT_STAB *opt_stab, BB_NODE *bb);
  void      Rename_rhs(OPT_STAB *opt_stab, WN *wn);
  void      Gen_name(OPT_STAB *opt_stab, IDTYPE var);
  void      Value_number(CODEMAP *htable, OPT_STAB *opt_stab, BB_NODE *bb, 
			 COPYPROP *copyprop, EXC *exc);
  CODEREP  *Du2cr( CODEMAP *htable, OPT_STAB *opt_stab, VER_ID du, STMTREP *stmt);
  CODEREP  *Revive_phi_chi_opnd(VER_ID du);
  void	    Make_live_phi_chi_opnd(VER_ID du);

public:
            SSA(MEM_POOL *gpool,
		MEM_POOL *lpool){mem_pool=gpool; loc_pool=lpool; }
           ~SSA(void) 	  {};
  MEM_POOL *Mem_pool(void)    { return mem_pool; }

  void      Construct(CODEMAP *htable,
		      CFG *cfg, OPT_STAB *opt_stab);  //  Construct SSA form.
  
  CODEREP  *Get_zero_version_CR(AUX_ID aux_id, OPT_STAB *, VER_ID);
  void      Pointer_Alias_Analysis(void);         
  void      Dead_store_elim(CFG *, OPT_STAB *, EXC *);
  void	    Find_zero_versions();
  void      Create_CODEMAP(void);
  void      Value_number_mu_list(MU_LIST *mu_list);
  void      Value_number_mu_node(MU_NODE *mu_node);
  void	    Resurrect_phi(PHI_NODE *phi);
  void	    Resurrect_chi(CHI_NODE *chi);
};

class CODEREP;


class PHI_KEY {
  IDTYPE _bb_id;
  AUX_ID _aux_id;
public:
  // A constructor is not allowed because 
  // PHI_KEY is a union member in ID_MAP!
  void Init(IDTYPE bb_id, AUX_ID aux_id) {
    _bb_id = bb_id;
    _aux_id = aux_id;
  }
  friend BOOL operator==(const PHI_KEY x, const PHI_KEY y) 
    {
      return (x._bb_id == y._bb_id && x._aux_id == y._aux_id);
    }
  friend BOOL operator!=(const PHI_KEY x, const PHI_KEY y) 
    {
      return (x._bb_id != y._bb_id || x._aux_id != y._aux_id);
    }
};


// Phi functions
class PHI_NODE : public SLIST_NODE {
  DECLARE_SLIST_NODE_CLASS(PHI_NODE)
private:

  enum PHI_NODE_FLAGS {
    PNF_NONE		   = 0x00,
    PNF_LIVE		   = 0x01,
    PNF_DSE_DEAD	   = 0x02,
    PNF_DCE_DEAD	   = 0x04,// phi res is dead after DCE
    PNF_RES_IS_CR	   = 0x08,// phi res is CODEREP, not VER_STAB index
    PNF_OPND_IV_UPDATE	   = 0x10,// an opnd is defined by an IV update
    PNF_OPND_NOT_IV_UPDATE = 0x20,// an opnd is not defined by an IV update
    PNF_VISITED            = 0x40, // vistied bit.
    PNF_NULL_SSU_PROCESSED = 0x80, // prevent infinite loop in setting 
				   // NULL_SSU_VERSION flag in SPRE step 2
    PNF_FIND_DEF_PROCESSED = 0x100, // prevent infinite loop in looking for 
			    	    // real stores in SPRE step 6 
    PNF_INCOMPLETE         = 0x200, // when this bit is set, its dominator
                                    // frontier might not have a phi 
                                    // this bit is set by phi generated by LPRE/EPRE.
    PNF_SIZE_VISITED       = 0x400, // No_trucation_by_value_size visited
    PNF_FIND_CORR_PROCESSED = 0x800 // prevent infinite loop in looking for 
			    	    // corresponding preg in SPRE step 6 
  };

  AUX_ID      _aux_id;
  mUINT32     _flags;
  mINT16      size;
  mINT16      count;
  BB_NODE     *_bb;
  union PHI_ELEM {
  friend class PHI_NODE;
  private:
    AUX_ID    version;
    CODEREP   *cr;
  };

  // vec[0] is the result
  // vec[1..] are the operands
  PHI_ELEM *vec;

  PHI_NODE(void);
  PHI_NODE(const PHI_NODE&);
  PHI_NODE& operator = (const PHI_NODE&);

public:
         PHI_NODE(mINT16 in_degree, MEM_POOL *pool, BB_NODE *bb)
	   { vec = (PHI_ELEM*) CXX_NEW_ARRAY(PHI_ELEM, (in_degree + 1), pool);
	     size = in_degree; count = 0; _bb = bb; 
	     _flags = PNF_NONE; }
        ~PHI_NODE(void)                  { /*CXX_DELETE_ARRAY(vec, Opt_default_pool);*/ }
  
  AUX_ID   Opnd(INT32 i) const           { return vec[i+1].version; }
  AUX_ID   Result(void) const            { return vec[0].version; }
  CODEREP *OPND(INT32 i) const           { return vec[i+1].cr;  }
  CODEREP *RESULT(void) const            { return vec[0].cr; }
  mINT16   Size(void) const              { return size; }
  mINT16   Count(void) const             { return count; }
  IDTYPE   Aux_id(void) const            { return _aux_id; }
  BB_NODE *Bb(void) const                { return _bb; }
  void     Set_bb(BB_NODE *bb)           { _bb = bb; }

  PHI_KEY  Key(void) const               { PHI_KEY key; key.Init(_bb->Id(), _aux_id); return key; }
  
  mUINT8   Flags(void) const             { return _flags; }
  void     Set_flags(mUINT8 i)           { _flags = i; }
  void     Set_opnd(const INT32 i, AUX_ID cr)
                                         { vec[i+1].version = cr;}
  void     Set_result(AUX_ID cr)         { vec[0].version = cr; }
  void     Set_opnd(const INT32 i, CODEREP *c)
                                         { vec[i+1].cr = c; }
  void     Set_result(CODEREP *c)        { vec[0].cr = c; }
  void     Set_count(mINT16 c)           { count = c; }
  void     Set_aux_id(AUX_ID v)          { _aux_id = v; }
  void     Set_invalid(void)             { vec[0].cr = NULL; }
  void     Reset_OPND(INT32 i)           { vec[i+1].cr = NULL; }

  // Remove the i'th operand from the phi-node (0 is first opnd)
  void     Remove_opnd(INT32 i);

  // flags field accessors
  BOOL	   Live(void) const		{ return _flags & PNF_LIVE; }
  void	   Set_live(void)		{ _flags |= PNF_LIVE; }
  void	   Reset_live(void)		{ _flags &= ~PNF_LIVE; }
  BOOL	   Dse_dead(void) const		{ return _flags & PNF_DSE_DEAD; }
  void	   Set_dse_dead(void)		{ _flags |= PNF_DSE_DEAD; }
  void	   Reset_dse_dead(void)		{ _flags &= ~PNF_DSE_DEAD; }
  BOOL	   Dce_dead(void) const         { return _flags & PNF_DCE_DEAD; }
  void	   Reset_dce_dead(void)		{ _flags &= ~PNF_DCE_DEAD; }
  void	   Set_dce_dead(void)		{ _flags |= PNF_DCE_DEAD; }
  BOOL	   Res_is_cr(void) const        { return _flags & PNF_RES_IS_CR; }
  void	   Set_res_is_cr(void)		{ _flags |= PNF_RES_IS_CR; }
  // is one of the operands defined by an IV update statement
  BOOL	   Opnd_iv_update(void) const   { return _flags & PNF_OPND_IV_UPDATE; }
  void	   Set_opnd_iv_update(void)	{ _flags |= PNF_OPND_IV_UPDATE; }
  // none of the operands defined by an IV update statement
  BOOL	   Opnd_not_iv_update(void) const{ return _flags & PNF_OPND_NOT_IV_UPDATE; }
  void	   Set_opnd_not_iv_update(void)	{ _flags |= PNF_OPND_NOT_IV_UPDATE; }
  BOOL	   Visited(void) const		{ return _flags & PNF_VISITED; }
  void	   Set_visited(void)		{ _flags |= PNF_VISITED; }
  void	   Reset_visited(void)		{ _flags &= ~PNF_VISITED; }
  BOOL	   Null_ssu_processed(void) const   { return _flags & PNF_NULL_SSU_PROCESSED; }
  void	   Set_null_ssu_processed(void)	{ _flags |= PNF_NULL_SSU_PROCESSED; }
  BOOL	   Find_def_processed(void) const   { return _flags & PNF_FIND_DEF_PROCESSED; }
  void	   Set_find_def_processed(void)	{ _flags |= PNF_FIND_DEF_PROCESSED; }
  void	   Reset_find_def_processed(void) { _flags &= ~PNF_FIND_DEF_PROCESSED; }
  BOOL	   Find_corr_processed(void) const { return _flags & PNF_FIND_CORR_PROCESSED; }
  void	   Set_find_corr_processed(void)	{ _flags |= PNF_FIND_CORR_PROCESSED; }
  BOOL	   Incomplete(void) const	{ return _flags & PNF_INCOMPLETE; }
  void	   Set_incomplete(void)		{ _flags |= PNF_INCOMPLETE; }
  void	   Reset_incomplete(void)	{ _flags &= ~PNF_INCOMPLETE; }

  BOOL	   Is_size_visited(void) const	{ return _flags & PNF_SIZE_VISITED; }
  void	   Set_size_visited(void)	{ _flags |= PNF_SIZE_VISITED; }
  void	   Reset_size_visited(void)	{ _flags &= ~PNF_SIZE_VISITED; }

  //  Print functions
  void     Print(INT32 in_degree,
		 FILE *fp=stderr) const;
  void     PRINT(INT32 in_degree,
		 FILE *fp=stderr) const;
  void     Print(FILE *fp=stderr) const;
};


class PHI_LIST : public SLIST {
  DECLARE_SLIST_CLASS (PHI_LIST, PHI_NODE)

private:
  INT32   in_degree;          

  PHI_LIST(const PHI_LIST&);
  PHI_LIST& operator = (const PHI_LIST&);

public:
  PHI_LIST(BB_NODE *bb);
  ~PHI_LIST(void)			{}

  PHI_NODE *New_phi_node(IDTYPE var, MEM_POOL *pool, BB_NODE *bb)
    { PHI_NODE *p = (PHI_NODE *) CXX_NEW (PHI_NODE(in_degree, pool, bb), pool); 
      for (INT32 i = 0; i < in_degree; i++)
	p->Set_opnd(i, (AUX_ID)0);
      p->Set_result((AUX_ID)0);
      p->Set_aux_id(var);
      Append(p);
      return p;
    }

  PHI_LIST *Dup_phi_node(MEM_POOL *pool, BB_NODE *bb, INT pos);
  // Remove the i'th operand from the phi-nodes (0 is first opnd)
  void     Remove_opnd(INT32 i);
	
  INT32 In_degree(void) const           { return in_degree; }
  void  Set_in_degree( INT32 n )	{ in_degree = n; }

  void  Print(FILE *fp=stderr);    
  void  PRINT(FILE *fp=stderr);    
};


class PHI_LIST_ITER : public SLIST_ITER {
private:
  DECLARE_SLIST_ITER_CLASS (PHI_LIST_ITER, PHI_NODE, PHI_LIST)

  PHI_LIST_ITER(const PHI_LIST_ITER&);
  PHI_LIST_ITER& operator = (const PHI_LIST_ITER&);

public:
  ~PHI_LIST_ITER(void)		{}

  PHI_NODE *First_elem(void)	{ return First(); }
  PHI_NODE *Next_elem(void)	{ return Next();  }
};

class PHI_OPND_ITER {
private:
  PHI_NODE *_phi;
  INT       _curidx;

  PHI_OPND_ITER(void);
  PHI_OPND_ITER(const PHI_OPND_ITER&);
  PHI_OPND_ITER& operator = (const PHI_OPND_ITER&);

public:
  PHI_OPND_ITER(PHI_NODE *phi)   { _phi = phi; }
  ~PHI_OPND_ITER(void)           {}
  void     Init(PHI_NODE *phi)   { _phi = phi; }
  void     Init(void)            {}
  CODEREP *First_elem(void)      { _curidx = 0; return _phi->OPND(_curidx); }
  CODEREP *Next_elem(void)       { _curidx++;
				   return (Is_Empty())? NULL:_phi->OPND(_curidx); }
  BOOL     Is_Empty(void) const  { return _curidx >= _phi->Size(); }
  INT	   Curidx(void) const	 { return _curidx; }
};

#endif  // opt_ssa_INCLUDED