PBQP Heuristic which applies an allocability test based on Briggs. More...

#include <Briggs.h>

Inheritance diagram for PBQP::Heuristics::Briggs:

Collaboration diagram for PBQP::Heuristics::Briggs:

Classes
struct	EdgeData

struct	NodeData

Public Member Functions
	Briggs (HeuristicSolverImpl< Briggs > &solver)
	Construct an instance of the Briggs heuristic. More...

bool	shouldOptimallyReduce (Graph::NodeId nId)
	Determine whether a node should be reduced using optimal reduction. More...

void	addToHeuristicReduceList (Graph::NodeId nId)
	Add a node to the heuristic reduce list. More...

bool	heuristicReduce ()
	Heuristically reduce one of the nodes in the heuristic reduce list. More...

void	preUpdateEdgeCosts (Graph::EdgeId eId)
	Prepare a change in the costs on the given edge. More...

void	postUpdateEdgeCosts (Graph::EdgeId eId)
	Handle the change in the costs on the given edge. More...

void	handleAddEdge (Graph::EdgeId eId)
	Handle the addition of a new edge into the PBQP graph. More...

void	handleRemoveEdge (Graph::EdgeId eId, Graph::NodeId nId)
	Handle disconnection of an edge from a node. More...

Public Member Functions inherited from PBQP::HeuristicBase< Briggs >
	HeuristicBase (HeuristicSolverImpl< Briggs > &solver)
	Construct an instance with a reference to the given solver. More...

HeuristicSolverImpl< Briggs > &	getSolver ()
	Get the solver which is using this heuristic instance. More...

Graph &	getGraph ()
	Get the graph representing the problem to be solved. More...

bool	solverRunSimplify () const
	Tell the solver to simplify the graph before the reduction phase. More...

bool	shouldOptimallyReduce (Graph::NodeId nId)
	Decide whether a node should be optimally or heuristically reduced. More...

void	addToOptimalReduceList (Graph::NodeId nId)
	Add the given node to the list of nodes to be optimally reduced. More...

void	setup ()
	Initialise the heuristic. More...

bool	optimalReduce ()
	Optimally reduce one of the nodes in the optimal reduce list. More...

void	reduce ()
	Perform the PBQP reduction process. More...

void	addToHeuristicList (Graph::NodeId nId)
	Add a node to the heuristic reduce list. More...

bool	heuristicReduce ()
	Heuristically reduce one of the nodes in the heuristic reduce list. More...

void	preUpdateEdgeCosts (Graph::EdgeId eId)
	Prepare a change in the costs on the given edge. More...

void	postUpdateEdgeCostts (Graph::EdgeId eId)
	Handle the change in the costs on the given edge. More...

void	handleAddEdge (Graph::EdgeId eId)
	Handle the addition of a new edge into the PBQP graph. More...

void	handleRemoveEdge (Graph::EdgeId eId, Graph::NodeId nId)
	Handle disconnection of an edge from a node. More...

void	cleanup ()
	Clean up any structures used by HeuristicBase. More...

Detailed Description

PBQP Heuristic which applies an allocability test based on Briggs.

This heuristic assumes that the elements of cost vectors in the PBQP problem represent storage options, with the first being the spill option and subsequent elements representing legal registers for the corresponding node. Edge cost matrices are likewise assumed to represent register constraints. If one or more nodes can be proven allocable by this heuristic (by inspection of their constraint matrices) then the allocable node of highest degree is selected for the next reduction and pushed to the solver stack. If no nodes can be proven allocable then the node with the lowest estimated spill cost is selected and push to the solver stack instead.

This implementation is built on top of HeuristicBase.

Definition at line 44 of file Briggs.h.

Constructor & Destructor Documentation

PBQP::Heuristics::Briggs::Briggs ( HeuristicSolverImpl< Briggs > & solver )

inline

Construct an instance of the Briggs heuristic.

Parameters

solver A reference to the solver which is using this heuristic.

Definition at line 112 of file Briggs.h.

Member Function Documentation

void PBQP::Heuristics::Briggs::addToHeuristicReduceList ( Graph::NodeId nId )

inline

Add a node to the heuristic reduce list.

Parameters

nId	Node id to add to the heuristic reduce list.

Definition at line 136 of file Briggs.h.

References PBQP::Heuristics::Briggs::NodeData::isAllocable, PBQP::Heuristics::Briggs::NodeData::isHeuristic, PBQP::Heuristics::Briggs::NodeData::rnaItr, and PBQP::Heuristics::Briggs::NodeData::rnuItr.

void PBQP::Heuristics::Briggs::handleAddEdge ( Graph::EdgeId eId )

inline

Handle the addition of a new edge into the PBQP graph.

Parameters

eId	Edge id for the added edge.

Updates allocability of any nodes connected by this edge which are being managed by the heuristic. If allocability changes they are moved to the appropriate list.

Definition at line 213 of file Briggs.h.

References PBQP::Graph::getEdgeNode1(), PBQP::Graph::getEdgeNode2(), PBQP::HeuristicBase< Briggs >::getGraph(), PBQP::Heuristics::Briggs::NodeData::isAllocable, PBQP::Heuristics::Briggs::NodeData::isHeuristic, PBQP::Heuristics::Briggs::NodeData::rnaItr, and PBQP::Heuristics::Briggs::NodeData::rnuItr.

Referenced by postUpdateEdgeCosts().

void PBQP::Heuristics::Briggs::handleRemoveEdge	(	Graph::EdgeId	eId,
		Graph::NodeId	nId
	)

inline

Handle disconnection of an edge from a node.

Parameters

eId	Edge id for edge being disconnected.
nId	Node id for the node being disconnected from.

Updates allocability of the given node and, if appropriate, moves the node to a new list.

Definition at line 259 of file Briggs.h.

References PBQP::HeuristicBase< Briggs >::addToOptimalReduceList(), PBQP::Heuristics::Briggs::NodeData::isAllocable, PBQP::Heuristics::Briggs::NodeData::isHeuristic, PBQP::Heuristics::Briggs::EdgeData::isUpToDate, PBQP::Heuristics::Briggs::NodeData::rnaItr, PBQP::Heuristics::Briggs::NodeData::rnuItr, and shouldOptimallyReduce().

bool PBQP::Heuristics::Briggs::heuristicReduce ( )

inline

Heuristically reduce one of the nodes in the heuristic reduce list.

Returns: True if a reduction takes place, false if the heuristic reduce list is empty.

If the list of allocable nodes is non-empty a node is selected from it and pushed to the stack. Otherwise if the non-allocable list is non-empty a node is selected from it and pushed to the stack. If both lists are empty the method simply returns false with no action taken.

Definition at line 157 of file Briggs.h.

References PBQP::HeuristicBase< Briggs >::getSolver(), and PBQP::HeuristicSolverImpl< HImpl >::pushToStack().

void PBQP::Heuristics::Briggs::postUpdateEdgeCosts ( Graph::EdgeId eId )

inline

Handle the change in the costs on the given edge.

Parameters

eId Edge id.

Definition at line 201 of file Briggs.h.

References handleAddEdge().

void PBQP::Heuristics::Briggs::preUpdateEdgeCosts ( Graph::EdgeId eId )

inline

Prepare a change in the costs on the given edge.

Parameters

eId Edge id.

Definition at line 183 of file Briggs.h.

References PBQP::Graph::getEdgeNode1(), PBQP::Graph::getEdgeNode2(), PBQP::HeuristicBase< Briggs >::getGraph(), PBQP::Heuristics::Briggs::NodeData::isHeuristic, and PBQP::Heuristics::Briggs::EdgeData::isUpToDate.

bool PBQP::Heuristics::Briggs::shouldOptimallyReduce ( Graph::NodeId nId )

inline

Determine whether a node should be reduced using optimal reduction.

Parameters

nId	Node id to be considered.

Returns: True if the given node should be optimally reduced, false otherwise.

Selects nodes of degree 0, 1 or 2 for optimal reduction, with one exception. Nodes whose spill cost (element 0 of their cost vector) is infinite are checked for allocability first. Allocable nodes may be optimally reduced, but nodes whose allocability cannot be proven are selected for heuristic reduction instead.

Definition at line 126 of file Briggs.h.

References PBQP::HeuristicBase< Briggs >::getSolver().

Referenced by handleRemoveEdge().

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

Briggs.h

Classes

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation