regalloc::Color Class Reference

Just color the graph itself. More...

#include <color.hh>

Collaboration diagram for regalloc::Color:

Public Types
typedef liveness::InterferenceGraph	InterferenceGraph
typedef liveness::interferencegraph_vertex_iter_type	hnodes_iterator
typedef InterferenceGraph::vertex_descriptor	node_type
typedef misc::set< node_type >	node_set_type
typedef std::list< node_type >	node_list_type
typedef InterferenceGraph::move_type	move_type
typedef InterferenceGraph::move_set_type	move_set_type
typedef std::vector < move_set_type >	move_list_map_type
	Mapping a node to the moves it is involved in. The name "list" is due to Appel, but it appears to be a set.
typedef std::vector< temp::Temp >	color_map_type
	Mapping a node to a color.
typedef std::vector< node_type >	alias_map_type
	Mapping a coalesced node onto its representant.

Public Member Functions
bool	operator() ()
	Perform the coloration: try to assign registers to temporaries. Return true iff colored with success (no spill).
Ctor & dtor.
	Color (assem::ProcFrag &frag, const target::Cpu &cpu, const temp::TempMap &tempmap, bool coalesce_p=false, bool trace_p=false)
	Initialize the register allocation.
Time.
const misc::timer &	timer_get () const
Accessors.
const temp::temp_set_type	spilled_get () const
	Return the list of temporaries that had not been colored.
temp::TempMap	tempmap_get () const
	Return the register allocation for this fragment, i.e., the combination of precolored registers and the temps we just colored.

Protected Member Functions
void	add_edge (const node_type u, const node_type v)
	Add an edge between u and v, making sure to update their degree ("AddEdge").
void	make_work_list (const node_type n)
	Put node n in the appropriate work list.
void	make_work_list ()
	Initialize the work lists ("MakeWorklist").
node_set_type	adjacent (const node_type n) const
	Return the neighbors of n ("Adjacent").
bool	adjacent (const node_type a, const node_type b) const
	Return whether a and b are adjacent. This is performing the job of "adjSet" in Appel's.
move_set_type	node_moves (const node_type n) const
	The (active) moves involing n ("NodeMoves").
bool	move_related (const node_type n) const
	node n is involved in a move ("MoveRelated").
void	coalesce ()
	Perform one round of coalescence ("Coalesce").
void	add_work_list (const node_type u)
	Node u is involved in a move which status just changed: check whether it became simplifiable ("AddWorkList").
node_type	get_alias (const node_type a) const
	Return the active node with whom a has been coalesed ("GetAlias").
void	combine (const node_type u, const node_type v)
	Merge the nodes u and v. Keep u as representative of both nodes, and move v in the appropriate side list ("Combine").
void	freeze_moves (const node_type u)
	Freeze the moves involving u ("FreezeMoves").
void	freeze ()
	Perform one round of freezing nodes ("Freeze").
void	select_spill ()
	Perform one round of spilling ("SelectSpill").
void	simplify ()
	Simplify one low (< nb_regs_) degree node.
void	decrement_degree (node_type n)
	Decrement the degree of n ("DecrementDegree").
void	enable_moves (node_type n)
	Enable the moves related to node n ("EnableMoves").
void	enable_moves (const node_set_type &nodes)
	Enable the moves related to nodes ("EnableMoves").
void	assign_color (node_type n)
void	assign_colors ()
	Pop the entire stack, assigning colors (coloration phase).
Pre-treatments.
Used by the constructor.
void	import_nodes ()
	Import the nodes from the InterferenceGraph ig_.
void	import_moves ()
	Import the moves from the InterferenceGraph ig_.
void	precolor ()
	Precolor the hard registers.
void	priorities_compute ()
	Compute the number of defs and uses of each temporaries.
void	degrees_compute ()
	Compute the initial degree of each node. Don't forget hard registers have an infinite degree.
Coalescing criteria.
bool	coalesce_briggs_p (const node_type a, const node_type b) const
	Check if coalescing a and b is conservative according to Briggs' criterion ("Conservative").
bool	coalesce_george_p (const node_type a, const node_type b) const
	Check if coalescing a and b is safe according to the George criterion. a is a hard register.
Debugging.
void	trace (const std::string &what, const node_type &n) const
	The action what is performed about node n.
void	trace (const std::string &what, const move_type &m) const
	The action what is performed about move m.
void	dump (std::ostream &ostr, const node_type &n) const
	Print node n under a human readable form: the corresponding Temp.
void	dump (std::ostream &ostr, const node_set_type &s) const
	Human readable output of the set of nodes s.
void	dump (std::ostream &ostr, const node_list_type &s) const
	Human readable output of the list of nodes s.
void	dump (std::ostream &ostr, const move_type &s) const
	Print move m under a human readable form: with the corresponding Temp's.
void	dump (std::ostream &ostr, const move_set_type &s) const
	Human readable output of the set of moves s.
void	dump (std::ostream &ostr) const
	Human readable output of this Color object.

Protected Attributes
InterferenceGraph	ig_
	The interference graph.
const target::Cpu &	cpu_
	Target architecture's cpu description.
size_t	nb_regs_
	The number of registers (number of colors).
assem::ProcFrag &	asm_proc_frag_
	The instructions' fragments.
bool	trace_p_
	trace flag.
bool	coalesce_p_
	A flag to know if try to coalesce when we can.
std::map< temp::Temp, int >	temps_priority_
	Number of uses/defs of each temporaries.
Node work-lists, sets, an stacks.
The following lists and sets are mutually disjoint and every node is always in exactly one of the sets or lists. The names used by Appel are provided in paratheses.
node_set_type	precolored_
	Machine registers, preassigned a color ("precolored").
node_set_type	initial_
	Temporary registers, not precolored and not yet processed ("initial").
node_set_type	simplify_work_list_
	List of low-degree non-move-related nodes ("simplifyWorkList"). Actually a set.
node_set_type	freeze_work_list_
	List of low-degree move-related nodes ("freezeWorkList"). Actually a set.
node_set_type	spill_work_list_
	List of high-degree nodes ("spillWorkList"). Actually a set.
node_set_type	spilled_nodes_
	Nodes marked for spilling during this round; initially empty ("spilledNodes").
node_set_type	coalesced_nodes_
	Registers that have been coalesced; when u := v is coalesced, "v" is added to this set, and "u" put back on some work-list (or vice versa) ("coalescedNodes").
node_set_type	colored_nodes_
	Nodes successfully colored ("coloredNodes").
node_list_type	select_stack_
	Stack containing temporaries removed from the graph ("selectStack"). ATTENTION: Use by the front (push_front, pop_front etc.).
Moves sets.
There are five sets of move instructions, and every move is in exactly one of these sets (after "Build" through the end of "Main").
move_set_type	coalesced_moves_
	Moves that have been coalesced ("coalescedMoves").
move_set_type	constrained_moves_
	Moves whose source and target intefere ("constrainedMoves").
move_set_type	frozen_moves_
	Moves that will no longer be considered for coalescing ("frozenMoves").
move_set_type	work_list_moves_
	Moves enabled for possible coalescing ("workListMoves").
move_set_type	active_moves_
	Moves not yet ready for coalescing ("activeMoves").
Other data structures.
std::vector< size_t >	degree_
	The current degree of each node ("degree").
move_list_map_type	move_list_
	A mapping from a node to the list of moves it is associated with ("moveList").
alias_map_type	alias_
	When a "move (u, v)" has been coalesced, and "v" put in coalesced_nodes_, then "alias (v) = u" ("alias").
color_map_type	color_
	The color chosen by the algorithm for a node; for precolored nodes, this is initialized to the given color ("color").

Private Attributes
Timer member.
misc::timer	timer_
	Color timer.

Detailed Description

Just color the graph itself.

Member Typedef Documentation

typedef std::vector<node_type> regalloc::Color::alias_map_type

Mapping a coalesced node onto its representant.

typedef std::vector<temp::Temp> regalloc::Color::color_map_type

Mapping a node to a color.

typedef liveness::interferencegraph_vertex_iter_type regalloc::Color::hnodes_iterator

typedef liveness::InterferenceGraph regalloc::Color::InterferenceGraph

typedef std::vector<move_set_type> regalloc::Color::move_list_map_type

Mapping a node to the moves it is involved in. The name "list" is due to Appel, but it appears to be a set.

typedef InterferenceGraph::move_set_type regalloc::Color::move_set_type

typedef InterferenceGraph::move_type regalloc::Color::move_type

typedef std::list<node_type> regalloc::Color::node_list_type

typedef misc::set<node_type> regalloc::Color::node_set_type

typedef InterferenceGraph::vertex_descriptor regalloc::Color::node_type

Constructor & Destructor Documentation

regalloc::Color::Color	(	assem::ProcFrag &	frag,
		const target::Cpu &	cpu,
		const temp::TempMap &	tempmap,
		bool	coalesce_p = false,
		bool	trace_p = false
	)

Initialize the register allocation.

This is basically the "Build" routine in Appel.

References degrees_compute(), DO, ig_, import_moves(), import_nodes(), make_work_list(), precolor(), priorities_compute(), timer_, and liveness::InterferenceGraph::timer_get().

Member Function Documentation

void regalloc::Color::add_edge ( const node_type  u, const node_type  v  )

protected

Add an edge between u and v, making sure to update their degree ("AddEdge").

void regalloc::Color::add_work_list ( const node_type  u )

protected

Node u is involved in a move which status just changed: check whether it became simplifiable ("AddWorkList").

node_set_type regalloc::Color::adjacent ( const node_type  n ) const

protected

Return the neighbors of n ("Adjacent").

Compared to using directly neighbors_of, pay special attention to nodes that were simplified.

bool regalloc::Color::adjacent ( const node_type  a, const node_type  b  ) const

protected

Return whether a and b are adjacent. This is performing the job of "adjSet" in Appel's.

Compared to using directly edge_exists, pay special attention to nodes that were simplified.

void regalloc::Color::assign_color ( node_type  n )

protected

void regalloc::Color::assign_colors ( )

protected

Pop the entire stack, assigning colors (coloration phase).

Get successively the last node of the stack and try to color it, rebuilding the original graph, step by step.

Look for the precoloration of some nodes, the interferences between two nodes (these nodes must not occupy the same register), and the coalesced nodes that occupy the same register. ("AssignColors").

Referenced by operator()().

void regalloc::Color::coalesce ( )

protected

Perform one round of coalescence ("Coalesce").

Referenced by operator()().

bool regalloc::Color::coalesce_briggs_p ( const node_type  a, const node_type  b  ) const

protected

Check if coalescing a and b is conservative according to Briggs' criterion ("Conservative").

Briggs: less than k neighbors of significant degree.

bool regalloc::Color::coalesce_george_p ( const node_type  a, const node_type  b  ) const

protected

Check if coalescing a and b is safe according to the George criterion. a is a hard register.

George: Nodes a and b can safely coalesce if, for every neighbor t of b, either t already interfers with a, or t is of insignificant degree.

void regalloc::Color::combine ( const node_type  u, const node_type  v  )

protected

Merge the nodes u and v. Keep u as representative of both nodes, and move v in the appropriate side list ("Combine").

Attention

Be sure to read the correction published by Appel on his site, since there are mistakes in the algorithm of this function.

void regalloc::Color::decrement_degree ( node_type  n )

protected

Decrement the degree of n ("DecrementDegree").

Removing a node from the graph involves decrementing the degree of its current neighbors. If the degree of a neighbor is already less than K - 1 then the neighbor must be move-related, and is not added to the simplify_work_list_. When the degree of a neighbor transitions from K to K - 1, moves associated with its neighbors may be enabled.

The algorithm as specified by Appel may have a small period during which the invariants are not preserved. When one successfully coalesce two different nodes a and b, they are combined (see combine). As part of this merge, nodes adjacent to b become adjacent to a: there is a call to add_edge, which increases the degree. But this degree ought is decrement immediatly afterwards. Now, it is possible under some conditions that the "add_edge" had increased the degree of a node from k - 1 to kwithout moving the node from work list. And then decrement_degree will see that the degree was k, and therefore that the status of the node is to be changed. The problem is that its status was not updated by add_edge, so a strict invariant check will see that we try to remove a node from spill_work_list_, where it is not.

That's not a problem: just don't be too strict on the invariant check here.

void regalloc::Color::degrees_compute ( )

protected

Compute the initial degree of each node. Don't forget hard registers have an infinite degree.

Referenced by Color().

void regalloc::Color::dump ( std::ostream &  ostr, const node_type &  n  ) const

protected

Print node n under a human readable form: the corresponding Temp.

References color_, colored_nodes_, and ig_.

Referenced by dump(), operator()(), and trace().

void regalloc::Color::dump ( std::ostream &  ostr, const node_set_type &  s  ) const

protected

Human readable output of the set of nodes s.

References dump().

void regalloc::Color::dump ( std::ostream &  ostr, const node_list_type &  s  ) const

protected

Human readable output of the list of nodes s.

References dump().

void regalloc::Color::dump ( std::ostream &  ostr, const move_type &  s  ) const

protected

Print move m under a human readable form: with the corresponding Temp's.

References dump().

void regalloc::Color::dump ( std::ostream &  ostr, const move_set_type &  s  ) const

protected

Human readable output of the set of moves s.

References dump().

void regalloc::Color::dump ( std::ostream &  ostr ) const

protected

Human readable output of this Color object.

References active_moves_, coalesce_p_, coalesced_moves_, coalesced_nodes_, colored_nodes_, constrained_moves_, freeze_work_list_, frozen_moves_, ig_, initial_, misc::graph< Orientation, VertexLabel, EdgeLabel >::name_get(), precolored_, REPORT, select_stack_, simplify_work_list_, spill_work_list_, spilled_nodes_, and work_list_moves_.

void regalloc::Color::enable_moves ( node_type  n )

protected

Enable the moves related to node n ("EnableMoves").

Removing a node from the graph involves decrementing the degree of its /current/ neighbors. If the degree of a neighbor is already less than K - 1 then the neighbor must be move-related, and is not added to the simplify_work_list_. When the degree of a neighbor transitions from K to K - 1, moves associated with /its/ neighbors may be enabled.

void regalloc::Color::enable_moves ( const node_set_type &  nodes )

protected

Enable the moves related to nodes ("EnableMoves").

void regalloc::Color::freeze ( )

protected

Perform one round of freezing nodes ("Freeze").

Referenced by operator()().

void regalloc::Color::freeze_moves ( const node_type  u )

protected

Freeze the moves involving u ("FreezeMoves").

node_type regalloc::Color::get_alias ( const node_type  a ) const

protected

Return the active node with whom a has been coalesed ("GetAlias").

void regalloc::Color::import_moves ( )

protected

Import the moves from the InterferenceGraph ig_.

References ig_, move_list_, liveness::InterferenceGraph::moves_get(), and work_list_moves_.

Referenced by Color().

void regalloc::Color::import_nodes ( )

protected

Import the nodes from the InterferenceGraph ig_.

References ig_, initial_, and precolored_.

Referenced by Color().

void regalloc::Color::make_work_list ( const node_type  n )

protected

Put node n in the appropriate work list.

See Also

make_work_list.

void regalloc::Color::make_work_list ( )

protected

Initialize the work lists ("MakeWorklist").

Referenced by Color().

bool regalloc::Color::move_related ( const node_type  n ) const

protected

node n is involved in a move ("MoveRelated").

move_set_type regalloc::Color::node_moves ( const node_type  n ) const

protected

The (active) moves involing n ("NodeMoves").

bool regalloc::Color::operator()

(

)

Perform the coloration: try to assign registers to temporaries. Return true iff colored with success (no spill).

References assign_colors(), coalesce(), DO, dump(), freeze(), freeze_work_list_, select_spill(), simplify(), simplify_work_list_, spill_work_list_, spilled_nodes_, trace_p_, and work_list_moves_.

void regalloc::Color::precolor ( )

protected

Precolor the hard registers.

Referenced by Color().

void regalloc::Color::priorities_compute ( )

protected

Compute the number of defs and uses of each temporaries.

These values are needed when searching a node to spill, with the lowest priority.

See Also

spill ()

Referenced by Color().

void regalloc::Color::select_spill ( )

protected

Perform one round of spilling ("SelectSpill").

Referenced by operator()().

void regalloc::Color::simplify ( )

protected

Simplify one low (< nb_regs_) degree node.

Referenced by operator()().

const temp::temp_set_type regalloc::Color::spilled_get

(

)

const

Return the list of temporaries that had not been colored.

References ig_, and spilled_nodes_.

temp::TempMap regalloc::Color::tempmap_get

(

)

const

Return the register allocation for this fragment, i.e., the combination of precolored registers and the temps we just colored.

const misc::timer & regalloc::Color::timer_get

(

)

const

References timer_.

void regalloc::Color::trace ( const std::string &  what, const node_type &  n  ) const

protected

The action what is performed about node n.

References dump(), and trace_p_.

void regalloc::Color::trace ( const std::string &  what, const move_type &  m  ) const

protected

The action what is performed about move m.

References dump(), and trace_p_.

Member Data Documentation

move_set_type regalloc::Color::active_moves_

protected

Moves not yet ready for coalescing ("activeMoves").

Referenced by dump().

alias_map_type regalloc::Color::alias_

protected

When a "move (u, v)" has been coalesced, and "v" put in coalesced_nodes_, then "alias (v) = u" ("alias").

assem::ProcFrag& regalloc::Color::asm_proc_frag_

protected

The instructions' fragments.

bool regalloc::Color::coalesce_p_

protected

A flag to know if try to coalesce when we can.

Referenced by dump().

move_set_type regalloc::Color::coalesced_moves_

protected

Moves that have been coalesced ("coalescedMoves").

Referenced by dump().

node_set_type regalloc::Color::coalesced_nodes_

protected

Registers that have been coalesced; when u := v is coalesced, "v" is added to this set, and "u" put back on some work-list (or vice versa) ("coalescedNodes").

Referenced by dump().

color_map_type regalloc::Color::color_

protected

The color chosen by the algorithm for a node; for precolored nodes, this is initialized to the given color ("color").

Referenced by dump().

node_set_type regalloc::Color::colored_nodes_

protected

Nodes successfully colored ("coloredNodes").

Referenced by dump().

move_set_type regalloc::Color::constrained_moves_

protected

Moves whose source and target intefere ("constrainedMoves").

Referenced by dump().

const target::Cpu& regalloc::Color::cpu_

protected

Target architecture's cpu description.

std::vector<size_t> regalloc::Color::degree_

protected

The current degree of each node ("degree").

node_set_type regalloc::Color::freeze_work_list_

protected

List of low-degree move-related nodes ("freezeWorkList"). Actually a set.

Referenced by dump(), and operator()().

move_set_type regalloc::Color::frozen_moves_

protected

Moves that will no longer be considered for coalescing ("frozenMoves").

Referenced by dump().

InterferenceGraph regalloc::Color::ig_

protected

The interference graph.

Referenced by Color(), dump(), import_moves(), import_nodes(), and spilled_get().

node_set_type regalloc::Color::initial_

protected

Temporary registers, not precolored and not yet processed ("initial").

Referenced by dump(), and import_nodes().

move_list_map_type regalloc::Color::move_list_

protected

A mapping from a node to the list of moves it is associated with ("moveList").

Referenced by import_moves().

size_t regalloc::Color::nb_regs_

protected

The number of registers (number of colors).

node_set_type regalloc::Color::precolored_

protected

Machine registers, preassigned a color ("precolored").

Referenced by dump(), and import_nodes().

node_list_type regalloc::Color::select_stack_

protected

Stack containing temporaries removed from the graph ("selectStack"). ATTENTION: Use by the front (push_front, pop_front etc.).

Referenced by dump().

node_set_type regalloc::Color::simplify_work_list_

protected

List of low-degree non-move-related nodes ("simplifyWorkList"). Actually a set.

Referenced by dump(), and operator()().

node_set_type regalloc::Color::spill_work_list_

protected

List of high-degree nodes ("spillWorkList"). Actually a set.

Referenced by dump(), and operator()().

node_set_type regalloc::Color::spilled_nodes_

protected

Nodes marked for spilling during this round; initially empty ("spilledNodes").

Referenced by dump(), operator()(), and spilled_get().

std::map<temp::Temp, int> regalloc::Color::temps_priority_

protected

Number of uses/defs of each temporaries.

misc::timer regalloc::Color::timer_

private

Color timer.

Referenced by Color(), and timer_get().

bool regalloc::Color::trace_p_

protected

trace flag.

Referenced by operator()(), and trace().

move_set_type regalloc::Color::work_list_moves_

protected

Moves enabled for possible coalescing ("workListMoves").

Referenced by dump(), import_moves(), and operator()().

---

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

• regalloc/color.hh
• regalloc/color.cc