opt_points_to.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

*/


#ifndef opt_points_to_INCLUDED
#define opt_points_to_INCLUDED  "opt_points_to.h"

#include "defs.h"
#include "config.h"
#include "cxx_base.h"
#include "cxx_memory.h"         // for CXX_NEW
#include "opcode.h"
#include "wn.h"
#include "config_wopt.h"        // for WOPT_Alias_Class_Limit,
                                //     WOPT_Ip_Alias_Class_Limit


typedef struct bs BS;

// interface to Mongoose symbol table
struct STAB_ADAPTER {
    ST *St_ptr (WN *wn) const { return WN_st (wn); }
};

class OPT_STAB;

//  ALIAS ANALYSIS and POINTS TO ANALYSIS
//
//  The Mongoose optimizer distinguishes points-to analysis from alias
//  analysis. The former analyzes the lvalue of an expression and
//  summarizes the information into a POINTS_TO instance.
//
//  The latter uses the POINTS_TO information to perform alias analysis.
//
//  The POINTS_TO information is gathered in two methods:
//   1) Flow free
//        such as determining the symbol, the type, the qualifiers, ...
//   2) Flow sensitive
//        such as determining the value of a pointer, ...
// 
//  The alias analysis is performed in 3 domains:
//   1)  symbol to symbol
//         This happens in FORTRAN common blocks, C unions ...
//   2)  memop to symbol
//         This is used by SSA
//   3)  memop to memop
//         This is not used by SSA, but required by the OPT/CG ...
//   4)  call to symbol
//         This is used by SSA.
//   5)  call to memop
//         This is used by SSA.
//


//  EXPR_KIND keeps track of the kind of the pointer expression
//  It is used only during FSA.
//
//     INVALID         -- the compiler should assert when this value is used.
//     BEING_PROCESSED -- this pointer expression is being processed.
//                        assume the most optimistic value in FSA.
//     INT             -- the expression contains an integer expression.
//     ADDR            -- the expression is based on some variable.
//     UNKNOWN         -- the most conservative assumption should be made.
//     ANY             -- the most optimistic assumption should be made.
//
enum EXPR_KIND {
  EXPR_IS_INVALID,
  EXPR_IS_BEING_PROCESSED,
  EXPR_IS_INT,
  EXPR_IS_ADDR, 
  EXPR_IS_UNKNOWN,   // expr is unknown, take it conservatively
  EXPR_IS_ANY        // expr is unknown, but can be combined with anything
  };

//  BASE_KIND qualifies what type of information *base contains.
//
//    INVALID        -- should cause assertion.
//    FIXED          -- the memop is based on a global or local variable.
//    DYNAMIC        -- the base is determined at runtime.
//    UNKNOWN        -- no information  
//
//  The base field in the POINTS_TO data structure can be
//     1) a static address (represented by a ST *)
//     2) a dynamic computed value
//        2a) a WHIRL expression  (represented by a WN *)
//        2b) a CHI node          (represented by a CHI_NODE *)
//        2c) a PHI node          (represented by a PHI_NODE *)
//        2d) it is not defined in this PU (i.e, parameter or global 
//             or even undefined locals).
//             (Represented by the aux_id.)
//
enum BASE_KIND {
  BASE_IS_INVALID,     
  BASE_IS_FIXED,            //  base() is ST*
  BASE_IS_DYNAMIC,          //  base() is some definition
  BASE_IS_UNKNOWN,          //  base() is NULL
  // *** Do not add new base_kind after this line ***
  MAX_BASE_KIND             //  For creating array indexed by BASE_KIND
  };


//  OFTS_KIND qualifies what type of information the ofst and size field contains
//
//   INVALID     -- should assert
//   FIXED       -- the ofst field denotes the lower range of access
//                  and the ofst+size denotes the upper range of access
//   UNKNOWN     -- the ofst field contains no useful information
//
enum OFST_KIND {
  OFST_IS_INVALID,        // invalid ofst kind 
  OFST_IS_FIXED,          // offset is fixed (available in the ofst field)
  OFST_IS_UNKNOWN         // offset is unknown
  };


//  Contains single-bit attributes.
//    
//    Notice the 0 is the default (conservative) values for every attribute.
//    Example: the default attribute for a variable is address taken.
//
//    If a variable is not address taken and we assume it is,
//    alias analysis is not accurate but still produces a correct answer.
//    However, it the variable is address taken and we assume it is not,
//    then alias analysis will produce an incorrect answer.
//
//    NOT_ADDR_SAVED  --  The address of this variable is not saved into a variable.
//    NOT_ADDR_PASSED --  The address of this variable is not passed to some routine.
//    LOCAL           --  The variable determined to be local variable.
//                        This bit does not necessarily set for all locals.
//    NAMED           --  This memory operation accesses a named variable.
//    CONST           --  This memory operation accesses read-only
//                        data (i.e., data that we can assume is not
//                        written by anything in the program [except
//                        possibly runtime initializer/constructor?]).
//    RESTRICTED      --  This memory operation is based on a restricted pointer.
//    UNIQUE_PT       --  This memory operation is based on a unique pointer.
//    F_PARAM         --  This memory operation is based on a Fortran parameter.
//    NO_ALIAS        --  This memory operation is accessed a variable
//                        that has no alias except itself.
//    WEAK            --  This memory operation writes to a weak symbol.
//    WEAK_BASE       --  This symbol is the base(target) of a weak symbol.
//    IS_POINTER      --  Represents a range of address of a pointer.
//    SAFE_TO_SPECULATE -- safe to speculate.
//    NOT_AUTO        --  It is known that if this variable has an
//                        initializer, it is initialized at compile/link
//                        time (not run time). C/C++ "automatic"
//                        locals do not have this bit set. C/C++
//                        globals and "static" do. Currently, this is
//                        used only when the CONST attribute is also
//                        set; it indicates that we can safely say
//                        this item does not alias. With CONST and
//                        without NOT_AUTO, we must at least say the
//                        item's initialization aliases with its uses,
//                        so the uses don't get scheduled first.
//    FORMAL          --  it is a formal parameter passed to this routine.
//                        Needs this bit because after data layout, formal parameters
//                        and local variables are layout w.r.t. to $SP.
//
enum PT_ATTR {
  PT_ATTR_NONE = 0,
  PT_ATTR_NOT_ADDR_SAVED  = 0x1,      // address is not saved
  PT_ATTR_NOT_ADDR_PASSED = 0x2,      // address is not passed
  PT_ATTR_LOCAL           = 0x4,      // local variable
  PT_ATTR_GLOBAL          = 0x8,      // global variable
  PT_ATTR_NAMED           = 0x10,     // reference a named variable
  PT_ATTR_CONST           = 0x20,     // the variable is read-only
  PT_ATTR_RESTRICTED      = 0x40,     // pointer gives restricted access
  PT_ATTR_UNIQUE_PT       = 0x80,     // pointer gives exclusive access
  PT_ATTR_F_PARAM         = 0x100,    // fortran call-by-ref parameter
  PT_ATTR_DEDICATED       = 0x200,    // dedicated register or memory
                                      // location
  PT_ATTR_NO_ALIAS        = 0x400,    // this object has no alias

  //  Weak is different from the other attr.
  //  When two POINTS_TO are combined, it either one is weak, then
  //  the combined one is weak
  PT_ATTR_WEAK            = 0x800,    // weak symbol
  PT_ATTR_WEAK_BASE       = 0x1000,   // base of a weak symbol
  PT_ATTR_IS_POINTER      = 0x2000,   // is a pointer content (not memory ref)
  PT_ATTR_SAFE_TO_SPECULATE = 0x4000, // safe to speculate
  PT_ATTR_NOT_AUTO        = 0x8000,   // static init is not at run time
  PT_ATTR_FORMAL          = 0x10000,  // is a formal parameter
  PT_ATTR_DEFAULT_VSYM    = 0x20000,  // is the default vsym, alias to
                                      // everything
  PT_ATTR_F90_POINTER     = 0x40000,  // access is known to be through
                                      // an f90 pointer
  PT_ATTR_NOT_F90_POINTER = 0x80000,  // access is known not to be
                                      // through an f90 pointer
  PT_ATTR_NOT_F90_TARGET  = 0x100000, // access is to memory that may
                                      // be pointed to by f90 pointer
  PT_ATTR_NOT_ALLOCA_MEM  = 0x200000, // this access can safely be
                                      // moved past stack pointer updates
  PT_ATTR_EXTENDED        = 0x400000  // used by alias manager to represent
                                      // a consecutive array of POINTS_TO
  // 23 of 32 bits used
};


//  ALIAS_INFO is the subset of POINTS_TO that will be passed in .B file.
//
class ALIAS_INFO {

friend class POINTS_TO;
  mUINT32       _expr_kind :3;     // one of EXPR_KIND
  mUINT32       _base_kind :3;     // one of BASE_KIND
  mUINT32       _ofst_kind :2;     // one of OFST_KIND
  mUINT32       _based_sym_depth:3;// used for disjoint
  mUINT32       _unused : 5;       // unused bits for future expansion
  mUINT32       _bit_ofst : 8;     // bit offset (for bit fields)
  mUINT32       _bit_size : 8;     // bit size (for bit fields)
                                   // _bit_size should be zero when this is 
                                   // not a bit field.  When it is
                                   // non-zero, _byte_ofst/_byte_size
                                   // gives the ofst/size of the container
                                   // of the bit field, and _bit_ofst/_bit_size
                                   // gives the bit ofst/size within the
                                   // container 
  PT_ATTR       _attr;             // PT_ATTR attributes
  INT64         _byte_ofst;        // offset from base    -- controlled by _ofst_kind
  UINT64        _byte_size;        // size of access      -- controlled by _ofst_kind
  ST           *_base;             // base symbol         -- controlled by _base_kind
  ST           *_based_sym;        // for restricted pointer, Fortran ref-param ...
  IDTYPE        _alias_class;      // which equivalence class this
                                   // memop is in, according to per-PU
                                   // analysis
  IDTYPE        _ip_alias_class;   // which equivalence class this
                                   // memop is in, according to
                                   // whole-program analysis
};


// for alias classification
const IDTYPE OPTIMISTIC_AC_ID  = 0;
const IDTYPE PESSIMISTIC_AC_ID = 1;


//  POINTS_TO is a structure to contain Points-to analysis results.
//   
//     Points-to analysis determines for the memop
//         1. base pointer 
//         2. types of memory access (e.g. to local variable, global variable, ...)
//         3. access range (ofst, size)
// 
//  !!! the fields make sense only if EXPR_IS_ADDR !!!
//
class POINTS_TO {
private:
  ALIAS_INFO    ai;
  TY_IDX        _ty;              // user-declared type for this memop
  INT32         _id;              // only used by the emitter.

  // Force everyone to use Copy_non_sticky_info or Copy_fully by
  // declaring an private assignment operator and an undefined copy
  // constructor.
  POINTS_TO &operator= (const POINTS_TO &p)
    { ai = p.ai; _ty = p._ty; _id = p._id; return *this; }

  POINTS_TO(const POINTS_TO &);

public:
  //  Member access functions
  //
  EXPR_KIND   Expr_kind(void)        const { return (EXPR_KIND) ai._expr_kind; }
  BASE_KIND   Base_kind(void)        const { return (BASE_KIND) ai._base_kind; }
  OFST_KIND   Ofst_kind(void)        const { return (OFST_KIND) ai._ofst_kind; }
  ST          *Base(void)            const { return ai._base; }
#if _NO_BIT_FIELDS
  mINT64      Ofst(void)             const { return ai._ofst; }
  mINT64      Size(void)             const { return ai._size; }
#else
  mINT64      Byte_Ofst(void)        const { return ai._byte_ofst; }
  mINT64      Byte_Size(void)        const { return ai._byte_size; }
  mUINT8      Bit_Ofst(void)         const { return ai._bit_ofst; }
  mUINT8      Bit_Size(void)         const { return ai._bit_size; }
#endif
  ST          *Based_sym(void)       const { return ai._based_sym; }
  UINT32      Based_sym_depth(void)  const { return ai._based_sym_depth; }
  TY_IDX      Ty(void)               const { return _ty; }
  INT32       Id(void)               const { return _id; }
  PT_ATTR     Attr(void)             const { return ai._attr; }
  BOOL        Not_addr_saved(void)   const { return ai._attr & PT_ATTR_NOT_ADDR_SAVED; }
  BOOL        Not_addr_passed(void)  const { return ai._attr & PT_ATTR_NOT_ADDR_PASSED; }
  BOOL        Local(void)            const { return ai._attr & PT_ATTR_LOCAL; }
  BOOL        Global(void)           const { return ai._attr & PT_ATTR_GLOBAL; }
  BOOL        Named(void)            const { return ai._attr & PT_ATTR_NAMED; }
  BOOL        Unnamed(void)          const { return !Named(); }
  BOOL        Const(void)            const { return ai._attr & PT_ATTR_CONST; }
  BOOL        Restricted(void)       const { return ai._attr & PT_ATTR_RESTRICTED; }
  BOOL        Unique_pt(void)        const { return ai._attr & PT_ATTR_UNIQUE_PT; }
  BOOL        F_param(void)          const { return ai._attr & PT_ATTR_F_PARAM; }
  BOOL        Dedicated(void)        const { return ai._attr & PT_ATTR_DEDICATED; }
  BOOL        No_alias(void)         const { return ai._attr & PT_ATTR_NO_ALIAS; }
  BOOL        Weak(void)             const { return ai._attr & PT_ATTR_WEAK; }
  BOOL        Weak_base(void)        const { return ai._attr & PT_ATTR_WEAK_BASE; }
  BOOL        Is_pointer(void)       const { return ai._attr & PT_ATTR_IS_POINTER; }
  BOOL        Safe_to_speculate(void)        const { return ai._attr & PT_ATTR_SAFE_TO_SPECULATE; }
  BOOL        Not_auto(void)         const { return ai._attr & PT_ATTR_NOT_AUTO; }
  BOOL        Formal(void)           const { return ai._attr & PT_ATTR_FORMAL; }
  BOOL        Default_vsym(void)     const { return ai._attr & PT_ATTR_DEFAULT_VSYM; }
  BOOL        Known_f90_pointer(void) const
    { return ai._attr & PT_ATTR_F90_POINTER; }
  BOOL        Known_not_f90_pointer(void) const
    { return ai._attr & PT_ATTR_NOT_F90_POINTER; }
  BOOL        Not_f90_target(void)   const { return ai._attr & PT_ATTR_NOT_F90_TARGET; }
  BOOL        Not_alloca_mem(void)   const { return ai._attr & PT_ATTR_NOT_ALLOCA_MEM; }
  BOOL        Extended(void)         const { return ai._attr & PT_ATTR_EXTENDED; }

  //  Set members
  //
  void Set_expr_kind(EXPR_KIND expr_kind) { ai._expr_kind = expr_kind; }
  void Set_base_kind(BASE_KIND base_kind) { ai._base_kind = base_kind; }
  void Set_ofst_kind(OFST_KIND ofst_kind) { ai._ofst_kind = ofst_kind; }
  void Set_unused()                       { ai._unused = 0; }
  void Set_base(ST *base)                 { ai._base = base; }
  void Set_byte_ofst(mINT64 ofst)         { ai._byte_ofst = ofst; }
  void Set_byte_size(mINT64 size)         { ai._byte_size = size; }
  void Set_bit_ofst_size(mUINT8 ofst, mUINT8 size) {
      ai._bit_ofst = ofst;
      ai._bit_size = size;
  }
  void Set_based_sym(ST *sym)             { ai._based_sym = sym; }
  void Set_based_sym_depth(UINT32 d)      { ai._based_sym_depth = (d > 7) ? 7 : d; }
  void Set_alias_class(const IDTYPE alias_class)
    {
      if (alias_class <= WOPT_Alias_Class_Limit) {
        ai._alias_class = alias_class;
      }
      else {
        ai._alias_class = PESSIMISTIC_AC_ID;
      }
    }
  void Set_ip_alias_class(const IDTYPE iac)
    {
      if (iac <= WOPT_Ip_Alias_Class_Limit) {
        ai._ip_alias_class = iac;
      }
      else {
        ai._ip_alias_class = PESSIMISTIC_AC_ID;
      }
    }
  void Set_ty(TY_IDX ty)                  { _ty = ty; }
  void Set_id(INT32 id)                   { _id = id; }
  void Set_attr(PT_ATTR attr)             { ai._attr = attr; }
  void Set_not_addr_saved(void)           { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_NOT_ADDR_SAVED); }
  void Set_not_addr_passed(void)          { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_NOT_ADDR_PASSED); }
  void Set_local(void)                    { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_LOCAL); }
  void Set_global(void)                   { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_GLOBAL); }
  void Set_named(void)                    { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_NAMED); }
  void Set_const(void)                    { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_CONST); }
  void Set_restricted(void)               { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_RESTRICTED); }
  void Set_unique_pt(void)                { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_UNIQUE_PT); }
  void Set_F_param(void)                  { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_F_PARAM); }
  void Set_dedicated(void)                { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_DEDICATED); }
  void Set_no_alias(void)                 { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_NO_ALIAS); }
  void Set_weak(void)                     { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_WEAK); }
  void Set_weak_base(void)                { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_WEAK_BASE); }
  void Set_is_pointer(void)               { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_IS_POINTER); }
  void Set_safe_to_speculate(void)                { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_SAFE_TO_SPECULATE); }
  void Set_not_auto(void)                 { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_NOT_AUTO); }
  void Set_formal(void)                   { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_FORMAL); }
  void Set_default_vsym(void)             { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_DEFAULT_VSYM); }
  void Set_known_f90_pointer(void)
    {
      Is_True(!Known_not_f90_pointer(),
              ("POINTS_TO: f90_pointer attributes inconsistent"));
      ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_F90_POINTER);
    }
  void Set_known_not_f90_pointer(void)
    {
      Is_True(!Known_f90_pointer(),
              ("POINTS_TO: f90_pointer attributes inconsistent"));
      ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_NOT_F90_POINTER);
    }
  void Set_not_f90_target(void)           { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_NOT_F90_TARGET); }
  void Set_not_alloca_mem(void)           { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_NOT_ALLOCA_MEM); }
  void Set_extended(void)                 { ai._attr = (PT_ATTR) (ai._attr | PT_ATTR_EXTENDED); }

  void Reset_attr(void)                   { ai._attr = PT_ATTR_NONE; }
  void Reset_not_addr_saved(void)         { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_NOT_ADDR_SAVED); }
  void Reset_not_addr_passed(void)        { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_NOT_ADDR_PASSED); }
  void Reset_local(void)                  { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_LOCAL); }
  void Reset_global(void)                 { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_GLOBAL); }
  void Reset_named(void)                  { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_NAMED); }
  void Reset_const(void)                  { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_CONST); }
  void Reset_restricted(void)             { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_RESTRICTED); }
  void Reset_unique_pt(void)              { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_UNIQUE_PT); }
  void Reset_F_param(void)                { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_F_PARAM); }
  void Reset_dedicated(void)              { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_DEDICATED); }
  void Reset_no_alias(void)               { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_NO_ALIAS); }
  void Reset_weak(void)                   { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_WEAK); }
  void Reset_weak_base(void)              { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_WEAK_BASE); }
  void Reset_is_pointer(void)             { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_IS_POINTER); }
  void Reset_safe_to_speculate(void)              { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_SAFE_TO_SPECULATE); }
  void Reset_not_auto(void)               { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_NOT_AUTO); }
  void Reset_formal(void)                 { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_FORMAL); }
  void Reset_default_vsym(void)           { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_DEFAULT_VSYM); }
  void Reset_known_f90_pointer(void)      { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_F90_POINTER); }
  void Reset_known_not_f90_pointer(void)  { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_NOT_F90_POINTER); }
  void Reset_not_f90_target(void)         { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_NOT_F90_TARGET); }
  void Reset_not_alloca_mem(void)         { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_NOT_ALLOCA_MEM); }
  void Reset_extended(void)               { ai._attr = (PT_ATTR) (ai._attr & ~PT_ATTR_EXTENDED); }

  void Init(void) {
    //  Set fields in POINTS_TO to invalid for error detection.
    Set_expr_kind(EXPR_IS_INVALID);
    Set_base_kind(BASE_IS_INVALID);
    Set_ofst_kind(OFST_IS_INVALID);
    Set_unused();
    Set_based_sym_depth(0);
    Set_base((ST*)NULL);
    Set_byte_ofst(0);
    Set_byte_size(0);
    Set_bit_ofst_size(0,0);
    Set_based_sym((ST*)NULL);
    Set_ty(0);
    Set_id(0);
    Set_alias_class(OPTIMISTIC_AC_ID);
    Set_ip_alias_class(OPTIMISTIC_AC_ID);

    // The default attributes: 
    Set_attr(PT_ATTR_NONE);
  }

  //  Return TRUE if bases are the same.   Return FALSE if don't know.
  BOOL Same_base(const POINTS_TO *) const;

  //  Return TRUE if bases are different.  Return FALSE if don't know.
  BOOL Different_base(const POINTS_TO *) const;

  //  Check whether offset overlaps.  Their bases must be the same.
  BOOL Overlap(const POINTS_TO *) const;

  // Check if PTs are similar, used in creating region bounds and rejecting
  // duplicates
  BOOL Similar(const POINTS_TO *pt) const {
    if (Expr_kind() == pt->Expr_kind() &&
        Base_kind() == pt->Base_kind() &&
        Ofst_kind() == pt->Ofst_kind() &&
        Base_kind() == BASE_IS_FIXED && 
        Ofst_kind() == OFST_IS_FIXED &&
        Base() == pt->Base() &&
        Byte_Ofst() == pt->Byte_Ofst() &&
        Byte_Size() == pt->Byte_Size())
      return TRUE;

    if ((F_param() && pt->F_param()) &&
        (Based_sym() == pt->Based_sym()))
      return TRUE;
  
    return FALSE;
  }

  IDTYPE Alias_class(void) const { return ai._alias_class; }

  IDTYPE Ip_alias_class(void) const { return ai._ip_alias_class; }

  void Shift_ofst(mINT64 shift)   // shift offset by that amount
    { Set_byte_ofst( Byte_Ofst() + shift ); }

  //  Return TRUE if base is fixed.
  BOOL Base_is_fixed(void) const 
    { return Base_kind() == BASE_IS_FIXED; }

  BOOL Int_is_constant(void) const 
    { return (Ofst_kind() == OFST_IS_FIXED); }  // overloaded ofst_kind
  
  mINT64 Int_const_val(void) const
    { return Byte_Ofst(); }

  void Set_const_val(mINT64 val) 
    { Set_byte_ofst(val); Set_ofst_kind(OFST_IS_FIXED); }

  // Merge the information from alias classification for two POINTS_TO's
  void Meet_info_from_alias_class(const POINTS_TO *);

  // Merge two points to information
  void Meet(const POINTS_TO *, ST *);

  // Copy a POINTS_TO structure
  void Copy_fully(const POINTS_TO *p)
    { *this = *p; }

  void Copy_fully(const POINTS_TO &p)
    { *this = p; }

  // Copy a POINTS_TO structure except for its sticky parts (i.e., the
  // parts related to unique_pt and restrict.
  void Copy_non_sticky_info(const POINTS_TO *p)  
    {
      BOOL  is_unique_pt  = Unique_pt();
      BOOL  is_restricted = Restricted();
      ST   *based_sym     = Based_sym();
      *this = *p;
      if (is_unique_pt) {
        Set_unique_pt();
        Set_based_sym(based_sym);
      }
      if (is_restricted) {
        Set_restricted();
        Set_based_sym(based_sym);
      }
    }

  // Copy a POINTS_TO structure except for its sticky parts (i.e., the
  // parts related to unique_pt and restrict.
  void Copy_non_sticky_info(const POINTS_TO &p)
    {
      BOOL  is_unique_pt  = Unique_pt();
      BOOL  is_restricted = Restricted();
      ST   *based_sym     = Based_sym();
      *this = p;
      if (is_unique_pt) {
        Set_unique_pt();
        Set_based_sym(based_sym);
      }
      if (is_restricted) {
        Set_restricted();
        Set_based_sym(based_sym);
      }
    }

  // Compute the POINTS_TO info for an ST
  void Analyze_ST(ST *st, INT64 byte_ofst, INT64 byte_size, UINT8 bit_ofst, 
                  UINT8 bit_size, TY_IDX ty, BOOL has_equiv);

  void Analyze_ST_as_base(ST *, INT64, TY_IDX);

  void Analyze_WN_expr(WN *);
  
#ifdef __cplusplus
  template <class SYMTAB> void Analyze_Ldid_Base(WN *wn, const SYMTAB &symtab);
  template <class SYMTAB> void Analyze_Parameter_Base(WN *wn, const SYMTAB &symtab);
  template <class SYMTAB> void Analyze_WN_expr(WN *wn, const SYMTAB &symtab);
#endif

  void Analyze_Lda_Base(WN *, const OPT_STAB &);
  void Analyze_Lda_Base(WN *, const STAB_ADAPTER &);
  void Lower_to_base(WN *);

  POINTS_TO() {}
  POINTS_TO(ST *st, BOOL indirect = FALSE) { 
    Init(); 
    if (indirect) 
      Analyze_ST_as_base(st, 0, 0);
    else
      Analyze_ST(st, 0, ST_size(st), 0, 0, 0,  TRUE); 
    if (Byte_Size() == 0)
      Set_ofst_kind(OFST_IS_UNKNOWN);
  }
  POINTS_TO(ST *st, INT64 ofst, INT64 size, BOOL indirect = FALSE) {
    Init(); 
    if (indirect) 
      Analyze_ST_as_base(st, ofst, 0);
    else
      Analyze_ST(st, ofst, size, 0, 0, 0,  TRUE); 
    if (Byte_Size() == 0)
      Set_ofst_kind(OFST_IS_UNKNOWN);
  }
  POINTS_TO(ST* st, INT64 byte_ofst, INT64 byte_size, UINT8 bit_ofst,
            UINT8 bit_size, BOOL indirect = FALSE) {
    Init();
    if (indirect) 
      Analyze_ST_as_base(st, byte_ofst, 0);
    else
      Analyze_ST(st, byte_ofst, byte_size, bit_ofst, bit_size, 0,  TRUE); 
    if (Byte_Size() == 0)
      Set_ofst_kind(OFST_IS_UNKNOWN);
  }

  // Print (for debugging)
  void Print(FILE *fp=stderr) const;
};


//  POINTS_TO_NODE:  contains the points_to item
//
class POINTS_TO_NODE : public SLIST_NODE {
  DECLARE_SLIST_NODE_CLASS(POINTS_TO_NODE)
private:
  POINTS_TO *_pt;
  POINTS_TO_NODE(void);
  POINTS_TO_NODE(const POINTS_TO_NODE&);
  POINTS_TO_NODE& operator = (const POINTS_TO_NODE&);
public:
  POINTS_TO_NODE(POINTS_TO *pt)         { _pt = pt; }
  ~POINTS_TO_NODE(void)                 {}
  POINTS_TO *Pt(void) const             { return _pt; }
};


//  POINTS_TO_LIST is a internal linked list
//
class POINTS_TO_LIST : public SLIST {
  DECLARE_SLIST_CLASS (POINTS_TO_LIST, POINTS_TO_NODE)
private:
  POINTS_TO_LIST(const POINTS_TO_LIST&);
  POINTS_TO_LIST& operator = (const POINTS_TO_LIST&);
public:
  void Prepend( POINTS_TO *pt, MEM_POOL *pool );
};


class POINTS_TO_ITER : public SLIST_ITER {
private:
  DECLARE_SLIST_ITER_CLASS (POINTS_TO_ITER, POINTS_TO_NODE, POINTS_TO_LIST)
  POINTS_TO_ITER(const POINTS_TO_ITER&);
  POINTS_TO_ITER& operator = (const POINTS_TO_ITER&);
public:
  ~POINTS_TO_ITER(void)         {}
  POINTS_TO_NODE *First_elem(void)      { return First(); }
  POINTS_TO_NODE *Next_elem(void)       { return Next();  }
};


#ifdef Is_True_On
extern void CHECK_POINTS_TO(POINTS_TO *);
#else
#define CHECK_POINTS_TO(pt)
#endif

//  Lower ST into the <base,ofst> form
void Expand_ST_into_base_and_ofst(ST *st, INT64 st_ofst, ST ** base, INT64 *ofst);

template <class SYMTAB> WN *Find_addr_recur(WN *, const SYMTAB &);

inline static BOOL Is_FORTRAN()
{
    const PU& pu = Get_Current_PU ();
    return (PU_f77_lang (pu) || PU_f90_lang (pu));
}

template <class SYMTAB>
ST *Is_nested_call(const WN *wn, const SYMTAB &symtab);

extern ST *Is_nested_call(const WN *wn);

// Implementation stuff originally from opt_points_to.cxx, since g++ (rightly)
// doesn't do implicit inclusion of .cxx files.


template <class SYMTAB>
void POINTS_TO::Analyze_Ldid_Base(WN *wn_ldid, const SYMTAB &stab)
{
  ST *st = stab.St_ptr(wn_ldid);
  INT64 ofst = WN_offset(wn_ldid);
  TY_IDX ty = WN_ty(wn_ldid);
  Analyze_ST_as_base(st, ofst, ty);
  Set_ofst_kind(OFST_IS_UNKNOWN);
}

// Look for a LDA/LDID node recursively 
template <class SYMTAB>
WN *Find_addr_recur(WN *wn, const SYMTAB &stab)
{
  if (wn == NULL) return NULL;
  switch (WN_operator(wn)) {
  case OPR_PARM:
    // if it is called by reference, LDID is a addr expr
    if (WN_Parm_By_Reference(wn) && WN_kid_count(wn))
      return Find_addr_recur(WN_kid0(wn), stab);
    // otherwise, there is no address expression
    return NULL;
  case OPR_LDA:
    return wn;
  case OPR_LDID:
    { 
      ST *st = stab.St_ptr(wn);
      if (Is_FORTRAN() && ST_sclass(st) == SCLASS_FORMAL &&
          ! ST_is_value_parm(st))
        return wn;
      if (ST_pt_to_unique_mem(st)) {
        TY_IDX ty = WN_ty(wn);
        if (TY_kind(Ty_Table[ty]) != KIND_POINTER) {
          TY_IDX new_ty = Make_Pointer_Type(ty);
          WN_set_ty(wn, new_ty);
          // Detect problem shown up in PV 652586.
          DevWarn("Fixing TY %s of LDID <%s> to a pointer type because the ST has PT_TO_UNIQUE_MEM set",  
                  TY_name(ty) ? TY_name(ty) : "noname",
                  ST_name(st) ? ST_name(st) : "noname");
        }
        return wn;
      }
      TY_IDX ty = WN_ty(wn);
      if (TY_kind(Ty_Table[ty]) == KIND_POINTER)
        return wn;
      Is_True(!TY_is_restrict(ty),
              ("__restrict object must be KIND_POINTER"));
      return NULL;
    }
  case OPR_ARRAY:
    return Find_addr_recur(WN_kid0(wn), stab);
  case OPR_ADD:
    { 
      WN *ret_wn;
      for (INT32 i = 0; i < WN_kid_count(wn); i++)
        if ((ret_wn = Find_addr_recur(WN_kid(wn,i), stab)) != NULL)
          return ret_wn;
      return NULL;
    }
  case OPR_SUB:
    return Find_addr_recur(WN_kid(wn,0), stab);
  default:
    return NULL;
  }
}


template <class SYMTAB>
void POINTS_TO::Analyze_Parameter_Base(WN *wn, const SYMTAB &stab)
{
  Set_expr_kind(EXPR_IS_ADDR);
  Set_base_kind(BASE_IS_UNKNOWN);
  Set_ofst_kind(OFST_IS_UNKNOWN);
  WN *wn_lda;
  switch (WN_operator(wn)) {
  case OPR_LDA:
    Analyze_Lda_Base(wn, stab);
    Lower_to_base(NULL);
    break;
  case OPR_LDID:
    Analyze_Ldid_Base(wn, stab);
    Set_ofst_kind(OFST_IS_UNKNOWN);
    break;
    
  case OPR_ARRAY:
  default:  // no information
    wn_lda = Find_addr_recur(wn, stab);
    if (wn_lda != NULL) {
      if (WN_operator(wn_lda) == OPR_LDA)  {
        Analyze_Lda_Base(wn_lda, stab);
        Lower_to_base(NULL);
      } else if (WN_operator(wn_lda) == OPR_LDID) {
        Analyze_Ldid_Base(wn_lda, stab);
        Lower_to_base(NULL);
        // ignore the range.  Passing A[i] does not mean only passing one element.
      }
    }
    break;
  } // switch
}

//  Templatize symbol table
template <class SYMTAB>
void POINTS_TO::Analyze_WN_expr(WN *wn, const SYMTAB &stab)
{
  OPERATOR opr = WN_operator(wn);
  switch ( opr ) {
  case OPR_LDID:
  case OPR_STID:
  case OPR_LDBITS:
  case OPR_STBITS:
    {
      ST *st = stab.St_ptr(wn);
      if (ST_sclass(st) != SCLASS_UNKNOWN) {
        TY_IDX ty = ST_type(st);
        INT64 ofst = WN_offset(wn);
        INT64 size = MTYPE_size_min(WN_desc(wn)) >> 3;
        if (opr == OPR_LDBITS || opr == OPR_STBITS)
            Analyze_ST (st, ofst, size, WN_bit_offset (wn), WN_bit_size
                        (wn), ty, TRUE /* has equiv */);
        else
            Analyze_ST(st, ofst, size, 0, 0, ty, TRUE /* assume has equiv */);
        return;
      }
    }
    break;
  case OPR_ILDBITS:
  case OPR_ISTBITS:
  case OPR_ILOAD:
  case OPR_MLOAD:
  case OPR_PARM:
  case OPR_ISTORE:
  case OPR_MSTORE:
    { 
      WN *wn_lda = Find_addr_recur(
        OPERATOR_is_store(opr) ? WN_kid1(wn) : WN_kid0(wn), stab);
      if (wn_lda != NULL) {
        if (WN_operator(wn_lda) == OPR_LDA)  {
          ST *st = stab.St_ptr(wn_lda);
          if (ST_sclass(st) != SCLASS_UNKNOWN) {
            Analyze_Lda_Base(wn_lda, stab);
            Lower_to_base(NULL);
            return;
          }
        } else if (WN_operator(wn_lda) == OPR_LDID) {
          Analyze_Ldid_Base(wn_lda, stab);
          Lower_to_base(NULL);
          return;
        }
      }
    }
    break;
  default:
    break;
  } // switch
  Init();   
}

// returns NULL if not a nested call
// global function, can be called with symtab or aux_stab
// used by OPT_STAB::Add_nested_call_mu_chi and REGION_BOUNDS:grb
template <class SYMTAB>
ST *Is_nested_call(const WN *wn, const SYMTAB &symtab)
{
  ST *call_st = NULL;
  INT32 num_parms = WN_kid_count(wn);
  OPERATOR opr = WN_operator(wn);
  if (opr == OPR_CALL) {
    call_st = WN_st(wn);
  } else if (opr == OPR_ICALL)
    num_parms--;

  // nested procedure?
  // SPECIAL CASE:  Check if any of the parameters is an LDA of
  // a nested function.  If so, we consider this to also be a call
  // to that function.  Only do this for fortran because that's the
  // only language so far that supports nested functions.
  ST *nested_func = NULL;

  for ( INT parmkid = 0; parmkid < num_parms; parmkid++ ) {
    WN *parm = WN_kid(wn, parmkid);
    if ( WN_operator(parm) == OPR_PARM ) {
      WN *actual_parm = WN_kid0(parm);
      if ( WN_operator(actual_parm) == OPR_LDA ) {
        // tricky:
        // for stab == OPT_STAB it is
        //      OPT_STAB::St_idx --> aux_stab[WN_aux(wn)].St()
        // for stab == STAB_ADAPTER, it is
        //      STAB_ADAPTER::St_idx --> WN_st(wn)
        ST *lda_st = symtab.St_ptr(actual_parm);
        if ( ST_class(lda_st) == CLASS_FUNC &&
            PU_is_nested_func (Pu_Table[ST_pu (lda_st)])
            )
          nested_func = lda_st;
      }
    }
  }

  if ( nested_func == NULL && call_st != NULL &&
      PU_is_nested_func (Pu_Table[ST_pu (call_st)])
      )
    nested_func = call_st;

  return nested_func;
}

#endif // opt_points_to_INCLUDED