et-forest.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "alloc-pool.h"
#include "et-forest.h"
#include "selftest.h"

Include dependency graph for et-forest.cc:

Data Structures
struct	et_occ

Functions
static void	set_depth (struct et_occ *occ, int d)
static void	set_depth_add (struct et_occ *occ, int d)
static void	set_prev (struct et_occ *occ, struct et_occ *t)
static void	set_next (struct et_occ *occ, struct et_occ *t)
static void	et_recomp_min (struct et_occ *occ)
static void	et_splay (struct et_occ *occ)
static struct et_occ *	et_new_occ (struct et_node *node)
struct et_node *	et_new_tree (void *data)
void	et_free_tree (struct et_node *t)
void	et_free_tree_force (struct et_node *t)
void	et_free_pools (void)
void	et_set_father (struct et_node *t, struct et_node *father)
void	et_split (struct et_node *t)
struct et_node *	et_nca (struct et_node *n1, struct et_node *n2)
bool	et_below (struct et_node *down, struct et_node *up)
struct et_node *	et_root (struct et_node *node)

Variables
static object_allocator< et_node >	et_nodes ("et_nodes pool")
static object_allocator< et_occ >	et_occurrences ("et_occ pool")

Function Documentation

et_below()

bool et_below	(	struct et_node *	down,
		struct et_node *	up )

Checks whether the node UP is an ancestor of the node DOWN.   

References et_splay(), et_occ::next, NULL, et_occ::parent, et_occ::prev, r, et_node::rightmost_occ, set_next(), and set_prev().

Referenced by dominated_by_p().

et_free_pools()

void et_free_pools

(

void

)

Release the alloc pools, if they are empty.   

References et_nodes, and et_occurrences.

Referenced by free_dominance_info(), and free_dominance_info_for_region().

et_free_tree()

void et_free_tree

(

struct et_node *

t

)

Releases et tree T.   

References et_nodes, et_occurrences, et_split(), et_node::father, et_node::rightmost_occ, and et_node::son.

Referenced by delete_from_dominance_info().

et_free_tree_force()

void et_free_tree_force

(

struct et_node *

t

)

Releases et tree T without maintaining other nodes.   

References et_nodes, et_occurrences, et_node::parent_occ, and et_node::rightmost_occ.

Referenced by free_dominance_info(), and free_dominance_info_for_region().

et_nca()

struct et_node * et_nca	(	struct et_node *	n1,
		struct et_node *	n2 )

Finds the nearest common ancestor of the nodes N1 and N2.   

References et_occ::depth, et_splay(), et_occ::min, et_occ::min_occ, et_occ::next, NULL, et_occ::of, et_occ::parent, et_occ::prev, r, et_node::rightmost_occ, set_next(), and set_prev().

Referenced by nearest_common_dominator().

et_new_occ()

static struct et_occ * et_new_occ ( struct et_node * node )

static

Create a new et tree occurrence of NODE.   

References et_occ::depth, et_occurrences, et_occ::min, et_occ::min_occ, et_occ::next, NULL, et_occ::of, et_occ::parent, and et_occ::prev.

Referenced by et_new_tree(), and et_set_father().

et_new_tree()

struct et_node * et_new_tree

(

void *

data

)

Create a new et tree containing DATA.   

References et_node::data, et_new_occ(), et_nodes, et_node::father, et_node::left, NULL, et_node::parent_occ, et_node::right, et_node::rightmost_occ, and et_node::son.

Referenced by add_to_dominance_info(), calculate_dominance_info(), and calculate_dominance_info_for_region().

et_recomp_min()

static void et_recomp_min ( struct et_occ * occ )

inlinestatic

Recompute minimum for occurrence OCC.   

References et_occ::depth, et_occ::min, et_occ::min_occ, et_occ::next, and et_occ::prev.

Referenced by et_set_father(), et_splay(), and et_split().

et_root()

struct et_node * et_root

(

struct et_node *

node

)

Returns the root of the tree that contains NODE.   

References et_splay(), et_occ::next, r, and et_node::rightmost_occ.

Referenced by root_of_dom_tree().

et_set_father()

void et_set_father	(	struct et_node *	t,
		struct et_node *	father )

Sets father of et tree T to FATHER.   

References et_occ::depth, et_new_occ(), et_recomp_min(), et_splay(), et_node::father, et_node::left, et_occ::min, et_occ::min_occ, et_node::parent_occ, et_occ::prev, et_node::right, et_node::rightmost_occ, set_next(), set_prev(), and et_node::son.

Referenced by calculate_dominance_info(), calculate_dominance_info_for_region(), redirect_immediate_dominators(), and set_immediate_dominator().

et_splay()

static void et_splay ( struct et_occ * occ )

static

Splay the occurrence OCC to the root of the tree.   

References et_occ::depth, et_recomp_min(), et_occ::min, et_occ::min_occ, et_occ::next, NULL, et_occ::parent, et_occ::prev, set_depth(), set_depth_add(), set_next(), and set_prev().

Referenced by et_below(), et_nca(), et_root(), et_set_father(), and et_split().

et_split()

void et_split

(

struct et_node *

t

)

Splits the edge from T to its father.   

References et_occ::depth, et_occurrences, et_recomp_min(), et_splay(), et_node::father, et_node::left, et_occ::min, et_occ::next, NULL, et_occ::parent, et_node::parent_occ, et_occ::prev, r, et_node::right, et_node::rightmost_occ, set_prev(), and et_node::son.

Referenced by et_free_tree(), redirect_immediate_dominators(), and set_immediate_dominator().

set_depth()

static void set_depth ( struct et_occ * occ, int d )

inlinestatic

Changes depth of OCC to D.   

References et_occ::depth, and et_occ::min.

Referenced by et_splay().

set_depth_add()

static void set_depth_add ( struct et_occ * occ, int d )

inlinestatic

Adds D to the depth of OCC.   

References et_occ::depth, and et_occ::min.

Referenced by et_splay().

set_next()

static void set_next ( struct et_occ * occ, struct et_occ * t )

inlinestatic

Sets next field of OCC to P.   

References gcc_assert, et_occ::next, and et_occ::parent.

Referenced by et_below(), et_nca(), et_set_father(), and et_splay().

set_prev()

static void set_prev ( struct et_occ * occ, struct et_occ * t )

inlinestatic

Sets prev field of OCC to P.   

References gcc_assert, et_occ::parent, and et_occ::prev.

Referenced by et_below(), et_nca(), et_set_father(), et_splay(), and et_split().

Variable Documentation

et_nodes

object_allocator< et_node > et_nodes("et_nodes pool") ( "et_nodes pool" )

static

Referenced by et_free_pools(), et_free_tree(), et_free_tree_force(), and et_new_tree().

et_occurrences

object_allocator< et_occ > et_occurrences("et_occ pool") ( "et_occ pool" )

static

Referenced by et_free_pools(), et_free_tree(), et_free_tree_force(), et_new_occ(), and et_split().