---

memoryaccess.h

Go to the documentation of this file.

// ----------------------------------------------------------------------
//
//  C-Breeze
//  C Compiler Framework
// 
//  Copyright (c) 2000 University of Texas at Austin
// 
//  Samuel Z. Guyer
//  Daniel A. Jimenez
//  Calvin Lin
// 
//  Permission is hereby granted, free of charge, to any person
//  obtaining a copy of this software and associated documentation
//  files (the "Software"), to deal in the Software without
//  restriction, including without limitation the rights to use, copy,
//  modify, merge, publish, distribute, sublicense, and/or sell copies
//  of the Software, and to permit persons to whom the Software is
//  furnished to do so, subject to the following conditions:
//  
//  The above copyright notice and this permission notice shall be
//  included in all copies or substantial portions of the Software.
//  
//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
//  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
//  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
//  NONINFRINGEMENT.  IN NO EVENT SHALL THE UNIVERSITY OF TEXAS AT
//  AUSTIN BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
//  IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
//  OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//  THE SOFTWARE.
//
//  We acknowledge the C-to-C Translator from MIT Laboratory for
//  Computer Science for inspiring parts of the C-Breeze design.
//
// ----------------------------------------------------------------------

#ifndef CBZ_MEMORYACCESS_H
#define CBZ_MEMORYACCESS_H

#include <set>
#include "location.h"

class memoryBlock;

typedef set< memoryBlock *,
             less< memoryBlock * >, memoryblock_alloc > memoryblock_set;
typedef memoryblock_set::iterator memoryblock_set_p;
typedef memoryblock_set::const_iterator memoryblock_set_cp;

class memoryDef;

typedef list< memoryDef *, memorydef_alloc > memorydef_list;
typedef memorydef_list::iterator memorydef_list_p;
typedef memorydef_list::const_iterator memorydef_list_cp;

typedef set< memoryDef *, less< memoryDef *>, memorydef_alloc > memorydef_set;
typedef memorydef_set::iterator memorydef_set_p;
typedef memorydef_set::const_iterator memorydef_set_cp;

class memoryUse;

typedef list< memoryUse *, memoryuse_alloc > memoryuse_list;
typedef memoryuse_list::iterator memoryuse_list_p;
typedef memoryuse_list::const_iterator memoryuse_list_cp;

typedef set< memoryUse *, less< memoryUse *>, memoryuse_alloc > memoryuse_set;
typedef memoryuse_set::iterator memoryuse_set_p;

// ------------------------------------------------------------
// memoryAccess
// ------------------------------------------------------------

// Common base class for both defs and uses

class memoryAccess : public PerClassHeap< PointersHeap >
{
public:

  static bool Verbose;
  static unsigned int def_count;
  static unsigned int use_count;
  static unsigned int merge_use_count;

  static void stats();

private:

  Location * _where;
  bool _is_weak;
  bool _is_additive;

public:

  // --- Constructor

  memoryAccess(Location * where);

  // --- Fields

  inline Location * where() const { return _where; }

  inline bool is_weak() const { return _is_weak; }
  inline void set_weak(bool is) { _is_weak = is; }

  inline bool is_additive() const { return _is_additive; }
  inline void set_additive() { _is_additive = true; }
};

typedef set< memoryAccess * > memoryaccess_set;
typedef memoryaccess_set::iterator memoryaccess_set_p;
typedef memoryaccess_set::const_iterator memoryaccess_set_cp;

// ------------------------------------------------------------
// memoryDef
// ------------------------------------------------------------

// A memoryDef represents a single definition of (assignment to) a
// particular memoryBlock. It records the place where the def occured,
// and the object deing modified. In addition, it is used to record
// the points-to values of any pointer objects.

class memoryDef : public memoryAccess
{
private:

  memoryuse_list _uses;
  memoryblock_set _points_to;
  memoryBlock * const _owner;

  memoryDef * _previous;

public:

  // --- Constructor

  memoryDef(Location * where, memoryBlock * owner);

  // --- Destructor

  ~memoryDef();

  // --- Fields

  inline memoryuse_list & uses() { return _uses; }
  inline const memoryblock_set & points_to() const { return _points_to; }
  inline memoryBlock * owner() const { return _owner; }

  inline memoryDef * previous() const { return _previous; }
  inline void previous(memoryDef * previous_def) { _previous = previous_def; }

  // --- Manipulate the points-to function

  void add_pointers(const memoryblock_set & mbs);
  void clear_points_to();

  // --- Output

  void print(ostream & o) const;
};

// ------------------------------------------------------------
// orderedDefs
// ------------------------------------------------------------

// An orderedDef object holds a sequence of memoryDefs in dominating
// order (a particular def always comes before the defs that dominate
// it).

class orderedUses;

class orderedDefs
{
private:

  memorydef_list _defs;

public:

  orderedDefs()
    : _defs()
  {}

  // --- Find the memoryDef for a given program location

  memoryDef * find_def(Location * where) const;

  // --- Find the nearest strictly dominating memoryDef (use this to
  // find the reaching definition for a regular use.

  memoryDef * find_strictly_dominating_def(Location * where) const;

  // --- Find the nearest dominating memoryDef (use this to find the
  // reaching definition for a merge-point use.

  memoryDef * find_dominating_def(Location * where) const;

  // --- Add a new memoryDef in the proper place, and return a
  // reference to it. If there is already an entry for the given path,
  // just return that memoryDef.

  memoryDef * make_def_at(Location * where, memoryBlock * owner, bool & is_new);

  // --- Prune out unnecessary defs

  void prune(orderedUses & Uses);

  // --- Output

  void print(ostream & o) const;

  // --- Clear

  void clear();

  // --- Size

  int size() const { return _defs.size(); }
};

// ------------------------------------------------------------
// memoryUse
// ------------------------------------------------------------

// A memoryUse represents a single use of the memoryBlock. It points
// to the reaching definition (from the orderedDefs list). For merges
// (phi functions) we create one for each of the control-flow
// predecessors.

class memoryUse : public memoryAccess
{
private:

  memoryDef * _reaching_def;
  bool _search_for_def;

public:

  // --- Constructor

  memoryUse(Location * where);

  // --- Destructor

  ~memoryUse();

  // --- Fields

  memoryDef * reaching_def() const { return _reaching_def; }
  void reaching_def(memoryDef * def);

  inline bool search_for_def() const { return _search_for_def; }
  inline void search_for_def(bool val) { _search_for_def = val; }

  // --- Output

  void print(ostream & o) const;
};


typedef map< Location *, memoryUse *,
             less< Location * >, location_alloc > memoryuse_map;
typedef memoryuse_map::iterator memoryuse_map_p;
typedef memoryuse_map::const_iterator memoryuse_map_cp;
typedef memoryuse_map::value_type memoryuse_map_pair;

typedef map< basicblockNode *, memoryUse *,
             less< basicblockNode * >, basicblock_alloc> pred_use_map;
typedef pred_use_map::iterator pred_use_map_p;
typedef pred_use_map::const_iterator pred_use_map_cp;

typedef map< Location *, pred_use_map,
             less< Location * >, location_alloc > merge_use_map;
typedef merge_use_map::iterator merge_use_map_p;
typedef merge_use_map::const_iterator merge_use_map_cp;

// ------------------------------------------------------------
// orderedUses
// ------------------------------------------------------------

class orderedUses
{
private:

  memoryuse_map _uses;
  merge_use_map _merge_uses;
  
public:

  orderedUses()
    : _uses(),
      _merge_uses()
  {}

  // --- Find an existing use for the given location (doesn't work for
  // merge/phi functions).

  memoryUse * find_use(Location * where) const;

  // --- Add a new use for the given location, or return the existing
  // one.

  memoryUse * make_use_at(Location * where);

  // --- Add a new set of uses for a particular merge point: one use
  // for each control-flow predecessor, with the reaching definitions
  // set appropriately.

  const pred_use_map & make_merge_uses_at(basicblockLocation * where);

  // --- Update the def-use chains (only performed once at the end of
  // analysis by the memoryModel).

  void update_def_use_chains();

  // --- Prune uses for a particular location

  void prune(Location * where);

  // --- Output

  void print(ostream & o) const;

  // --- Clear

  void clear();
};

#endif // CBZ_MEMORYACCESS_H

---