C-Breeze
C Compiler Infrastructure

[ Project home page]

procLocation Class Reference

#include <location.h>

Inheritance diagram for procLocation:

Location PerClassHeap< PointersHeap > List of all members.

Public Types

enum  LocationKind { Statement, BasicBlock, Procedure }
 Kind of location. More...

Public Member Functions

 procLocation (stmtLocation *parent, procNode *proc, bool context_insensitive=false)
stmtLocationstmt_location () const
procNodeproc () const
basicblockLocationlookup_block (basicblockNode *block) const
procLocationparent_proc () const
stmtLocationlast ()
void remove_from_tree ()
 Remove from tree.
virtual void adjust_depth ()
 Adjust tree depths.
virtual void print (ostream &o) const
virtual void print_path (ostream &o) const
virtual ~procLocation ()
Locationparent () const
LocationKind kind () const
unsigned int subtree_id () const
Locationdominator () const
void set_dominator (Location *d)
void clear_dominator ()
int num_children () const
void increment_children ()
void decrement_children ()
unsigned int tree_min () const
void set_tree_min (unsigned int m)
unsigned int tree_max () const
void set_tree_max (unsigned int m)
void visit ()
 Visit.
void finish ()
 Finish.

Static Public Member Functions

static procLocationmain ()
static bool dominates (const Location *dom, const Location *cur)
 Interprocedure dominance test.
static bool strictly_dominates (const Location *dom, const Location *cur)
 Interprocedure strict dominance test.
static procLocationprocedure (Location *where)
 Find the enclosing procedure.
static bool is_prefix (const Location *prefix, const Location *longer)
 See if one location is a prefix of the other.
static void stats ()

Static Public Attributes

static unsigned int stmt_count
static unsigned int block_count
static unsigned int proc_count
static unsigned int dom_calls

Static Protected Member Functions

static unsigned int next_tree_number ()
 Get the next tree number.

Protected Attributes

Location_parent
 Parent.
unsigned int _kind:2
 The kind of location.
unsigned int _subtree_id:16
 Subtree ID.
unsigned int _num_children:8
 Number of dominator children.
Location_dominator
 Immediate dominator.
unsigned int _tree_min
unsigned int _tree_max

Static Protected Attributes

static unsigned int current_subtree_id
 Global subtree ID counter.
static unsigned int current_tree_number
 The current tree number to assign.

Private Attributes

procNode *const _proc
basicblock_location_map _basicblocks

Static Private Attributes

static procLocationMain

Friends

ostream & operator<< (ostream &o, const Location &loc)

Member Enumeration Documentation

enum Location::LocationKind [inherited]
 

Kind of location.

Enumeration values:
Statement 
BasicBlock 
Procedure 

Definition at line 93 of file location.h.


Constructor & Destructor Documentation

procLocation::procLocation stmtLocation parent,
procNode proc,
bool  context_insensitive = false
 

virtual procLocation::~procLocation  )  [virtual]
 


Member Function Documentation

virtual void procLocation::adjust_depth  )  [virtual]
 

Adjust tree depths.

Implements Location.

void Location::clear_dominator  )  [inherited]
 

void Location::decrement_children  )  [inline, inherited]
 

Definition at line 251 of file location.h.

References Location::_num_children.

static bool Location::dominates const Location dom,
const Location cur
[static, inherited]
 

Interprocedure dominance test.

Location* Location::dominator  )  const [inline, inherited]
 

Definition at line 245 of file location.h.

References Location::_dominator.

void Location::finish  )  [inherited]
 

Finish.

Assign the post-order "tree max" (up the tree) number for a location. We call this method only when we find a location that doesn't dominate anything, and is therefore a leaf in the dominator tree. We move up the tree assigning tree max values until we find a sibling that has not been numbered yet. This siutation is indicated by a parent with num_children != 0.

void Location::increment_children  )  [inline, inherited]
 

Definition at line 250 of file location.h.

References Location::_num_children.

static bool Location::is_prefix const Location prefix,
const Location longer
[static, inherited]
 

See if one location is a prefix of the other.

LocationKind Location::kind  )  const [inline, inherited]
 

Definition at line 234 of file location.h.

References Location::_kind.

stmtLocation* procLocation::last  ) 
 

basicblockLocation* procLocation::lookup_block basicblockNode block  )  const
 

static procLocation* procLocation::main  )  [inline, static]
 

Definition at line 501 of file location.h.

References Main.

static unsigned int Location::next_tree_number  )  [inline, static, protected, inherited]
 

Get the next tree number.

Increment the global counter and return it.

Definition at line 216 of file location.h.

References Location::current_tree_number.

int Location::num_children  )  const [inline, inherited]
 

Definition at line 249 of file location.h.

References Location::_num_children.

Location* Location::parent  )  const [inline, inherited]
 

Fields

Reimplemented in Path.

Definition at line 233 of file location.h.

References Location::_parent.

procLocation* procLocation::parent_proc  )  const
 

virtual void procLocation::print ostream &  o  )  const [virtual]
 

Implements Location.

virtual void procLocation::print_path ostream &  o  )  const [virtual]
 

Implements Location.

procNode* procLocation::proc  )  const [inline]
 

Definition at line 497 of file location.h.

References _proc.

static procLocation* Location::procedure Location where  )  [static, inherited]
 

Find the enclosing procedure.

void procLocation::remove_from_tree  ) 
 

Remove from tree.

Used to remove an existing branch and adjust the depths appropriately. (use with stmtLocation::remove_call().

void Location::set_dominator Location d  )  [inherited]
 

void Location::set_tree_max unsigned int  m  )  [inline, inherited]
 

Definition at line 257 of file location.h.

References Location::_tree_max.

void Location::set_tree_min unsigned int  m  )  [inline, inherited]
 

Definition at line 254 of file location.h.

References Location::_tree_min.

static void Location::stats  )  [static, inherited]
 

stmtLocation* procLocation::stmt_location  )  const [inline]
 

Definition at line 496 of file location.h.

References Location::_parent.

static bool Location::strictly_dominates const Location dom,
const Location cur
[static, inherited]
 

Interprocedure strict dominance test.

unsigned int Location::subtree_id  )  const [inline, inherited]
 

Definition at line 243 of file location.h.

References Location::_subtree_id.

unsigned int Location::tree_max  )  const [inline, inherited]
 

Definition at line 256 of file location.h.

References Location::_tree_max.

unsigned int Location::tree_min  )  const [inline, inherited]
 

Definition at line 253 of file location.h.

References Location::_tree_min.

void Location::visit  )  [inherited]
 

Visit.

Assign the pre-order "tree min" (down the tree) number for a location. We call this method as we encounter each location during analysis.


Friends And Related Function Documentation

ostream& operator<< ostream &  o,
const Location loc
[friend, inherited]
 

Definition at line 321 of file location.h.


Member Data Documentation

basicblock_location_map procLocation::_basicblocks [private]
 

Definition at line 484 of file location.h.

Location* Location::_dominator [protected, inherited]
 

Immediate dominator.

This points to the immediate dominator of this node. It is set up during the construction of the location tree. It embodies the dominance rules discussed above.

Definition at line 178 of file location.h.

Referenced by Location::dominator().

unsigned int Location::_kind [protected, inherited]
 

The kind of location.

There are only three kinds, so we only need two bits.

Definition at line 129 of file location.h.

Referenced by Location::kind().

unsigned int Location::_num_children [protected, inherited]
 

Number of dominator children.

This is the number of locations immediately dominated by this one. We use this number to control the depth-first tree numbering algorithm. When the number is greater than one, we know that we still have dominator subtrees to number. Each time we finish a subtree, we decrement this number on the immediate dominator. When it reaches zero, the whole subtree is numbered.

We limit this field to 8 bits, which only allows a node to immediately dominate 256 other nodes. This is probably way higher than it needs to be, but we'll play it safe.

Definition at line 170 of file location.h.

Referenced by Location::decrement_children(), Location::increment_children(), and Location::num_children().

Location* Location::_parent [protected, inherited]
 

Parent.

A pointer to the containing location (strictly in terms of program structure). For stmtLocations, this points to the containing basic block. For basicblockLocations, it points to the procLocation. For procLocations, it points to the callsite stmtLocation (if there is one).

Reimplemented in Path.

Definition at line 123 of file location.h.

Referenced by stmtLocation::block_location(), Location::parent(), basicblockLocation::proc_location(), and stmt_location().

procNode* const procLocation::_proc [private]
 

Definition at line 483 of file location.h.

Referenced by proc().

unsigned int Location::_subtree_id [protected, inherited]
 

Subtree ID.

This number is used for context-insensitive analysis to quickly determine whether two locations can have a dominance relationship. Each context-sensitive program region has a unique subtree ID. If two locations have difference subtree IDs, then they are incomparable, and therefore cannot have a dominance relationship.

We arbitrarily choose 16 bits for this field, which would effectively limit the analyzer to 32K procedures (but that seems reasonable).

Definition at line 151 of file location.h.

Referenced by Location::subtree_id().

unsigned int Location::_tree_max [protected, inherited]
 

Definition at line 204 of file location.h.

Referenced by Location::set_tree_max(), and Location::tree_max().

unsigned int Location::_tree_min [protected, inherited]
 

Tree numbering

These two numbers implement the tree numbering scheme (from communication from Mark Wegman) that allows a constant time interprocedural dominance test. The scheme works as follows: we perform a depth-first traversal of the dominator tree, both pre-order and post-order, assigning consecutive numbers to "tree min" value on the way down, and the "tree max" value on the way up.

This numbering results in the following invariant: the min-max range of each node contains the min-max ranges of all nodes that it dominates.

Since we compute this numbering on-line, we need to test dominance for nodes on the way down the tree. This means we have to do without a tree max value in some cases. Therefore, we have a special case: the tree max defaults to MAX_INT until it is given a specific value.

These number can get large, so we use full 32-bit ints (limits us to 4 billion program locations).

Definition at line 203 of file location.h.

Referenced by Location::set_tree_min(), and Location::tree_min().

unsigned int Location::block_count [static, inherited]
 

Definition at line 99 of file location.h.

unsigned int Location::current_subtree_id [static, protected, inherited]
 

Global subtree ID counter.

Definition at line 155 of file location.h.

unsigned int Location::current_tree_number [static, protected, inherited]
 

The current tree number to assign.

Definition at line 210 of file location.h.

Referenced by Location::next_tree_number().

unsigned int Location::dom_calls [static, inherited]
 

Definition at line 101 of file location.h.

procLocation* procLocation::Main [static, private]
 

Definition at line 486 of file location.h.

Referenced by main().

unsigned int Location::proc_count [static, inherited]
 

Definition at line 100 of file location.h.

unsigned int Location::stmt_count [static, inherited]
 

Some global counters.

Definition at line 98 of file location.h.


The documentation for this class was generated from the following file:

Generated on February 1, 2006
Back to the C-Breeze home page