C-Breeze C Compiler Infrastructure [ Project home page]

Path Class Reference #include <path.h> Inheritance diagram for Path: List of all members. Public Types enum   LocationKind { Statement, BasicBlock, Procedure }   Kind of location. More... Public Member Functions   Path (PathDB *db, const Path *parent, procNode *callee)   Path (PathDB *db, const Path *parent, procNode *callee, basicblockNode *block)   Path (PathDB *db, const Path *parent, const Location &loc)   Path (const Path &other)   ~Path () const Path *  parent () const int  depth () const bool  dominates_exit () const bool  is_recursive () const bool  is_proc_present (procNode *proc) const bool  is_always () const void  print_shallow (ostream &o) const void  print_deep (ostream &o) const LocationKind  kind () const unsigned int  subtree_id () const Location *  dominator () 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. virtual void  adjust_depth ()=0   Adjust depths. virtual void  print (ostream &o) const =0 virtual void  print_path (ostream &o) const =0 Static Public Member Functions static const Path *  always () 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 procLocation *  procedure (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 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 Member Functions   Path () Private Attributes const Path *  _parent   Parent. int  _depth bool  _dominates_exit PathDB *  _db Static Private Attributes static const Path *  Always Friends class  PathDB ostream &  operator<< (ostream &o, const Path &c) 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 Path::Path (   )  [private] Path::Path (  PathDB *  db, const Path *  parent, procNode *  callee )  Path::Path (  PathDB *  db, const Path *  parent, procNode *  callee, basicblockNode *  block )  Path::Path (  PathDB *  db, const Path *  parent, const Location &  loc )  Path::Path (  const Path &  other  )  Path::~Path (   )  Member Function Documentation virtual void Location::adjust_depth (   )  [pure virtual, inherited]   Adjust depths. These methods are needed to fix the depths of all Location nodes during a context-insensitive reparenting. Implemented in stmtLocation, basicblockLocation, and procLocation. static const Path* Path::always (   )  [inline, static]   Definition at line 166 of file path.h. References Always. void Location::clear_dominator (   )  [inherited] void Location::decrement_children (   )  [inline, inherited]   Definition at line 251 of file location.h. References Location::_num_children. int Path::depth (   )  const [inline]   Definition at line 155 of file path.h. References _depth. static bool Location::dominates (  const Location *  dom, const Location *  cur )  [static, inherited]   Interprocedure dominance test. bool Path::dominates_exit (   )  const [inline]   Definition at line 156 of file path.h. References _dominates_exit. 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. bool Path::is_always (   )  const [inline]   Definition at line 162 of file path.h. References Always. Referenced by print_shallow(). static bool Location::is_prefix (  const Location *  prefix, const Location *  longer )  [static, inherited]   See if one location is a prefix of the other. bool Path::is_proc_present (  procNode *  proc  )  const bool Path::is_recursive (   )  const LocationKind Location::kind (   )  const [inline, inherited]   Definition at line 234 of file location.h. References Location::_kind. 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. const Path* Path::parent (   )  const [inline]   Fields Reimplemented from Location. Definition at line 154 of file path.h. References _parent. Referenced by print_deep(). virtual void Location::print (  ostream &  o  )  const [pure virtual, inherited]   Implemented in stmtLocation, basicblockLocation, and procLocation. Referenced by print_shallow(). void Path::print_deep (  ostream &  o  )  const [inline]   Definition at line 177 of file path.h. References parent(), and print_shallow(). virtual void Location::print_path (  ostream &  o  )  const [pure virtual, inherited]   Implemented in stmtLocation, basicblockLocation, and procLocation. void Path::print_shallow (  ostream &  o  )  const [inline]   Definition at line 170 of file path.h. References is_always(), and Location::print(). Referenced by print_deep(). static procLocation* Location::procedure (  Location *  where  )  [static, inherited]   Find the enclosing procedure. 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] 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. ostream& operator<< (  ostream &  o, const Path &  c )  [friend]   Definition at line 185 of file path.h. friend class PathDB [friend]   Definition at line 113 of file path.h. Member Data Documentation PathDB* Path::_db [private]   Definition at line 121 of file path.h. int Path::_depth [private]   Definition at line 118 of file path.h. Referenced by depth(). bool Path::_dominates_exit [private]   Definition at line 120 of file path.h. Referenced by dominates_exit(). 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(). const Path* Path::_parent [private]   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 from Location. Definition at line 117 of file path.h. Referenced by parent(). 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(). const Path* Path::Always [static, private]   Definition at line 127 of file path.h. Referenced by always(), and is_always(). 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. 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: path.h

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