#include <location.h>
Inheritance diagram for Location:
Kind of location.
Definition at line 93 of file location.h.
Create a new location.
Store the given parent and kind information. Initialize all of the flags and numberings.
[virtual]
[pure virtual]
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.
[inline]
Definition at line 251 of file location.h.
References _num_children.
[static]
Interprocedure dominance test.
Definition at line 245 of file location.h.
References _dominator.
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.
Definition at line 250 of file location.h.
See if one location is a prefix of the other.
Definition at line 234 of file location.h.
References _kind.
[inline, static, protected]
Get the next tree number.
Increment the global counter and return it.
Definition at line 216 of file location.h.
References current_tree_number.
Definition at line 249 of file location.h.
[inline, private]
Definition at line 107 of file location.h.
Fields
Reimplemented in Path.
Definition at line 233 of file location.h.
References _parent.
Implemented in stmtLocation, basicblockLocation, and procLocation.
Referenced by Path::print_shallow().
Find the enclosing procedure.
Definition at line 257 of file location.h.
References _tree_max.
Definition at line 254 of file location.h.
References _tree_min.
Interprocedure strict dominance test.
Definition at line 243 of file location.h.
References _subtree_id.
Definition at line 256 of file location.h.
Definition at line 253 of file location.h.
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.
[friend]
Definition at line 321 of file location.h.
[protected]
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 dominator().
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 kind().
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 decrement_children(), increment_children(), and num_children().
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).
Definition at line 123 of file location.h.
Referenced by stmtLocation::block_location(), parent(), basicblockLocation::proc_location(), and procLocation::stmt_location().
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 subtree_id().
Definition at line 204 of file location.h.
Referenced by set_tree_max(), and tree_max().
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 set_tree_min(), and tree_min().
Definition at line 99 of file location.h.
[static, protected]
Global subtree ID counter.
Definition at line 155 of file location.h.
The current tree number to assign.
Definition at line 210 of file location.h.
Referenced by next_tree_number().
Definition at line 101 of file location.h.
Definition at line 100 of file location.h.
Some global counters.
Definition at line 98 of file location.h.
Generated on February 1, 2006
Back to the C-Breeze home page