elim_graph Class Reference

Collaboration diagram for elim_graph:

Public Member Functions
	elim_graph (var_map map)

Data Fields
int	size
auto_vec< int >	nodes
auto_vec< int >	edge_list
auto_vec< location_t >	edge_locus
auto_sbitmap	visited
auto_vec< int >	stack
var_map	map
edge	e
auto_vec< int >	const_dests
auto_vec< tree >	const_copies
auto_vec< location_t >	copy_locus

Detailed Description

Used to hold all the components required to do SSA PHI elimination.
The node and pred/succ list is a simple linear list of nodes and
edges represented as pairs of nodes.

The predecessor and successor list:  Nodes are entered in pairs, where
[0] ->PRED, [1]->SUCC.  All the even indexes in the array represent
predecessors, all the odd elements are successors.

Rationale:
When implemented as bitmaps, very large programs SSA->Normal times were
being dominated by clearing the interference graph.

Typically this list of edges is extremely small since it only includes
PHI results and uses from a single edge which have not coalesced with
each other.  This means that no virtual PHI nodes are included, and
empirical evidence suggests that the number of edges rarely exceed
3, and in a bootstrap of GCC, the maximum size encountered was 7.
This also limits the number of possible nodes that are involved to
rarely more than 6, and in the bootstrap of gcc, the maximum number
of nodes encountered was 12.   

Constructor & Destructor Documentation

elim_graph()

elim_graph::elim_graph

(

var_map

map

)

Create an elimination graph for map.   

References const_copies, const_dests, copy_locus, edge_list, edge_locus, map, nodes, stack, and visited.

Field Documentation

const_copies

auto_vec<tree> elim_graph::const_copies

Referenced by elim_graph().

const_dests

auto_vec<int> elim_graph::const_dests

Referenced by elim_graph().

copy_locus

auto_vec<location_t> elim_graph::copy_locus

Referenced by elim_graph().

e

edge elim_graph::e

edge_list

auto_vec<int> elim_graph::edge_list

Referenced by elim_graph().

edge_locus

auto_vec<location_t> elim_graph::edge_locus

Referenced by elim_graph().

map

var_map elim_graph::map

Referenced by elim_graph().

nodes

auto_vec<int> elim_graph::nodes

Referenced by elim_graph().

size

int elim_graph::size

stack

auto_vec<int> elim_graph::stack

Referenced by elim_graph().

visited

auto_sbitmap elim_graph::visited

Referenced by elim_graph().

---

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

• tree-outof-ssa.cc