third_party/LLVM/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h - SwiftShader - Git at Google

 //===-- Briggs.h --- Briggs Heuristic for PBQP ------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This class implements the Briggs test for "allocability" of nodes in a
 // PBQP graph representing a register allocation problem. Nodes which can be
 // proven allocable (by a safe and relatively accurate test) are removed from
 // the PBQP graph first. If no provably allocable node is present in the graph
 // then the node with the minimal spill-cost to degree ratio is removed.
 //
 //===----------------------------------------------------------------------===//

 #ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
 #define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H

 #include "../HeuristicSolver.h"
 #include "../HeuristicBase.h"

 #include <limits>

 namespace PBQP {
   namespace Heuristics {

     /// \brief 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.
     class Briggs : public HeuristicBase<Briggs> {
     private:

       class LinkDegreeComparator {
       public:
         LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
         bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
           if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
             return true;
           return false;
         }
       private:
         HeuristicSolverImpl<Briggs> *s;
       };

       class SpillCostComparator {
       public:
         SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
           : s(&s), g(&s.getGraph()) {}
         bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
           const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr);
           const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr);

           PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr);
           PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr);

           if (cost1 < cost2)
             return true;
           return false;
         }

       private:
         HeuristicSolverImpl<Briggs> *s;
         Graph *g;
       };

       typedef std::list<Graph::NodeItr> RNAllocableList;
       typedef RNAllocableList::iterator RNAllocableListItr;

       typedef std::list<Graph::NodeItr> RNUnallocableList;
       typedef RNUnallocableList::iterator RNUnallocableListItr;

     public:

       struct NodeData {
         typedef std::vector<unsigned> UnsafeDegreesArray;
         bool isHeuristic, isAllocable, isInitialized;
         unsigned numDenied, numSafe;
         UnsafeDegreesArray unsafeDegrees;
         RNAllocableListItr rnaItr;
         RNUnallocableListItr rnuItr;

         NodeData()
           : isHeuristic(false), isAllocable(false), isInitialized(false),
             numDenied(0), numSafe(0) { }
       };

       struct EdgeData {
         typedef std::vector<unsigned> UnsafeArray;
         unsigned worst, reverseWorst;
         UnsafeArray unsafe, reverseUnsafe;
         bool isUpToDate;

         EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {}
       };

       /// \brief Construct an instance of the Briggs heuristic.
       /// @param solver A reference to the solver which is using this heuristic.
       Briggs(HeuristicSolverImpl<Briggs> &solver) :
         HeuristicBase<Briggs>(solver) {}

       /// \brief Determine whether a node should be reduced using optimal
       ///        reduction.
       /// @param nItr Node iterator to be considered.
       /// @return 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.
       bool shouldOptimallyReduce(Graph::NodeItr nItr) {
         if (getSolver().getSolverDegree(nItr) < 3) {
           return true;
         }
         // else
         return false;
       }

       /// \brief Add a node to the heuristic reduce list.
       /// @param nItr Node iterator to add to the heuristic reduce list.
       void addToHeuristicReduceList(Graph::NodeItr nItr) {
         NodeData &nd = getHeuristicNodeData(nItr);
         initializeNode(nItr);
         nd.isHeuristic = true;
         if (nd.isAllocable) {
           nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
         } else {
           nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
         }
       }

       /// \brief Heuristically reduce one of the nodes in the heuristic
       ///        reduce list.
       /// @return 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.
       bool heuristicReduce() {
         if (!rnAllocableList.empty()) {
           RNAllocableListItr rnaItr =
             min_element(rnAllocableList.begin(), rnAllocableList.end(),
                         LinkDegreeComparator(getSolver()));
           Graph::NodeItr nItr = *rnaItr;
           rnAllocableList.erase(rnaItr);
           handleRemoveNode(nItr);
           getSolver().pushToStack(nItr);
           return true;
         } else if (!rnUnallocableList.empty()) {
           RNUnallocableListItr rnuItr =
             min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
                         SpillCostComparator(getSolver()));
           Graph::NodeItr nItr = *rnuItr;
           rnUnallocableList.erase(rnuItr);
           handleRemoveNode(nItr);
           getSolver().pushToStack(nItr);
           return true;
         }
         // else
         return false;
       }

       /// \brief Prepare a change in the costs on the given edge.
       /// @param eItr Edge iterator.
       void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
         Graph &g = getGraph();
         Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
                        n2Itr = g.getEdgeNode2(eItr);
         NodeData &n1 = getHeuristicNodeData(n1Itr),
                  &n2 = getHeuristicNodeData(n2Itr);

         if (n1.isHeuristic)
           subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
         if (n2.isHeuristic)
           subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));

         EdgeData &ed = getHeuristicEdgeData(eItr);
         ed.isUpToDate = false;
       }

       /// \brief Handle the change in the costs on the given edge.
       /// @param eItr Edge iterator.
       void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
         // This is effectively the same as adding a new edge now, since
         // we've factored out the costs of the old one.
         handleAddEdge(eItr);
       }

       /// \brief Handle the addition of a new edge into the PBQP graph.
       /// @param eItr Edge iterator 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.
       void handleAddEdge(Graph::EdgeItr eItr) {
         Graph &g = getGraph();
         Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
                        n2Itr = g.getEdgeNode2(eItr);
         NodeData &n1 = getHeuristicNodeData(n1Itr),
                  &n2 = getHeuristicNodeData(n2Itr);

         // If neither node is managed by the heuristic there's nothing to be
         // done.
         if (!n1.isHeuristic && !n2.isHeuristic)
           return;

         // Ok - we need to update at least one node.
         computeEdgeContributions(eItr);

         // Update node 1 if it's managed by the heuristic.
         if (n1.isHeuristic) {
           bool n1WasAllocable = n1.isAllocable;
           addEdgeContributions(eItr, n1Itr);
           updateAllocability(n1Itr);
           if (n1WasAllocable && !n1.isAllocable) {
             rnAllocableList.erase(n1.rnaItr);
             n1.rnuItr =
               rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
           }
         }

         // Likewise for node 2.
         if (n2.isHeuristic) {
           bool n2WasAllocable = n2.isAllocable;
           addEdgeContributions(eItr, n2Itr);
           updateAllocability(n2Itr);
           if (n2WasAllocable && !n2.isAllocable) {
             rnAllocableList.erase(n2.rnaItr);
             n2.rnuItr =
               rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
           }
         }
       }

       /// \brief Handle disconnection of an edge from a node.
       /// @param eItr Edge iterator for edge being disconnected.
       /// @param nItr Node iterator for the node being disconnected from.
       ///
       /// Updates allocability of the given node and, if appropriate, moves the
       /// node to a new list.
       void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
         NodeData &nd = getHeuristicNodeData(nItr);

         // If the node is not managed by the heuristic there's nothing to be
         // done.
         if (!nd.isHeuristic)
           return;

         EdgeData &ed = getHeuristicEdgeData(eItr);
         (void)ed;
         assert(ed.isUpToDate && "Edge data is not up to date.");

         // Update node.
         bool ndWasAllocable = nd.isAllocable;
         subtractEdgeContributions(eItr, nItr);
         updateAllocability(nItr);

         // If the node has gone optimal...
         if (shouldOptimallyReduce(nItr)) {
           nd.isHeuristic = false;
           addToOptimalReduceList(nItr);
           if (ndWasAllocable) {
             rnAllocableList.erase(nd.rnaItr);
           } else {
             rnUnallocableList.erase(nd.rnuItr);
           }
         } else {
           // Node didn't go optimal, but we might have to move it
           // from "unallocable" to "allocable".
           if (!ndWasAllocable && nd.isAllocable) {
             rnUnallocableList.erase(nd.rnuItr);
             nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
           }
         }
       }

     private:

       NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
         return getSolver().getHeuristicNodeData(nItr);
       }

       EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
         return getSolver().getHeuristicEdgeData(eItr);
       }

       // Work out what this edge will contribute to the allocability of the
       // nodes connected to it.
       void computeEdgeContributions(Graph::EdgeItr eItr) {
         EdgeData &ed = getHeuristicEdgeData(eItr);

         if (ed.isUpToDate)
           return; // Edge data is already up to date.

         Matrix &eCosts = getGraph().getEdgeCosts(eItr);

         unsigned numRegs = eCosts.getRows() - 1,
                  numReverseRegs = eCosts.getCols() - 1;

         std::vector<unsigned> rowInfCounts(numRegs, 0),
                               colInfCounts(numReverseRegs, 0);

         ed.worst = 0;
         ed.reverseWorst = 0;
         ed.unsafe.clear();
         ed.unsafe.resize(numRegs, 0);
         ed.reverseUnsafe.clear();
         ed.reverseUnsafe.resize(numReverseRegs, 0);

         for (unsigned i = 0; i < numRegs; ++i) {
           for (unsigned j = 0; j < numReverseRegs; ++j) {
             if (eCosts[i + 1][j + 1] ==
                   std::numeric_limits<PBQPNum>::infinity()) {
               ed.unsafe[i] = 1;
               ed.reverseUnsafe[j] = 1;
               ++rowInfCounts[i];
               ++colInfCounts[j];

               if (colInfCounts[j] > ed.worst) {
                 ed.worst = colInfCounts[j];
               }

               if (rowInfCounts[i] > ed.reverseWorst) {
                 ed.reverseWorst = rowInfCounts[i];
               }
             }
           }
         }

         ed.isUpToDate = true;
       }

       // Add the contributions of the given edge to the given node's
       // numDenied and safe members. No action is taken other than to update
       // these member values. Once updated these numbers can be used by clients
       // to update the node's allocability.
       void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
         EdgeData &ed = getHeuristicEdgeData(eItr);

         assert(ed.isUpToDate && "Using out-of-date edge numbers.");

         NodeData &nd = getHeuristicNodeData(nItr);
         unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;

         bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
         EdgeData::UnsafeArray &unsafe =
           nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
         nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;

         for (unsigned r = 0; r < numRegs; ++r) {
           if (unsafe[r]) {
             if (nd.unsafeDegrees[r]==0) {
               --nd.numSafe;
             }
             ++nd.unsafeDegrees[r];
           }
         }
       }

       // Subtract the contributions of the given edge to the given node's
       // numDenied and safe members. No action is taken other than to update
       // these member values. Once updated these numbers can be used by clients
       // to update the node's allocability.
       void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
         EdgeData &ed = getHeuristicEdgeData(eItr);

         assert(ed.isUpToDate && "Using out-of-date edge numbers.");

         NodeData &nd = getHeuristicNodeData(nItr);
         unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;

         bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
         EdgeData::UnsafeArray &unsafe =
           nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
         nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;

         for (unsigned r = 0; r < numRegs; ++r) {
           if (unsafe[r]) {
             if (nd.unsafeDegrees[r] == 1) {
               ++nd.numSafe;
             }
             --nd.unsafeDegrees[r];
           }
         }
       }

       void updateAllocability(Graph::NodeItr nItr) {
         NodeData &nd = getHeuristicNodeData(nItr);
         unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
         nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0;
       }

       void initializeNode(Graph::NodeItr nItr) {
         NodeData &nd = getHeuristicNodeData(nItr);

         if (nd.isInitialized)
           return; // Node data is already up to date.

         unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;

         nd.numDenied = 0;
         nd.numSafe = numRegs;
         nd.unsafeDegrees.resize(numRegs, 0);

         typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;

         for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
                            aeEnd = getSolver().solverEdgesEnd(nItr);
              aeItr != aeEnd; ++aeItr) {

           Graph::EdgeItr eItr = *aeItr;
           computeEdgeContributions(eItr);
           addEdgeContributions(eItr, nItr);
         }

         updateAllocability(nItr);
         nd.isInitialized = true;
       }

       void handleRemoveNode(Graph::NodeItr xnItr) {
         typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
         std::vector<Graph::EdgeItr> edgesToRemove;
         for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
                            aeEnd = getSolver().solverEdgesEnd(xnItr);
              aeItr != aeEnd; ++aeItr) {
           Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
           handleRemoveEdge(*aeItr, ynItr);
           edgesToRemove.push_back(*aeItr);
         }
         while (!edgesToRemove.empty()) {
           getSolver().removeSolverEdge(edgesToRemove.back());
           edgesToRemove.pop_back();
         }
       }

       RNAllocableList rnAllocableList;
       RNUnallocableList rnUnallocableList;
     };

   }
 }


 #endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
	//===-- Briggs.h --- Briggs Heuristic for PBQP ------------------- C++ --===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// This class implements the Briggs test for "allocability" of nodes in a
	// PBQP graph representing a register allocation problem. Nodes which can be
	// proven allocable (by a safe and relatively accurate test) are removed from
	// the PBQP graph first. If no provably allocable node is present in the graph
	// then the node with the minimal spill-cost to degree ratio is removed.
	//
	//===----------------------------------------------------------------------===//

	#ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
	#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H

	#include "../HeuristicSolver.h"
	#include "../HeuristicBase.h"

	#include <limits>

	namespace PBQP {
	namespace Heuristics {

	/// \brief 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.
	class Briggs : public HeuristicBase<Briggs> {
	private:

	class LinkDegreeComparator {
	public:
	LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
	bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
	if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
	return true;
	return false;
	}
	private:
	HeuristicSolverImpl<Briggs> *s;
	};

	class SpillCostComparator {
	public:
	SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
	: s(&s), g(&s.getGraph()) {}
	bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
	const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr);
	const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr);

	PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr);
	PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr);

	if (cost1 < cost2)
	return true;
	return false;
	}

	private:
	HeuristicSolverImpl<Briggs> *s;
	Graph *g;
	};

	typedef std::list<Graph::NodeItr> RNAllocableList;
	typedef RNAllocableList::iterator RNAllocableListItr;

	typedef std::list<Graph::NodeItr> RNUnallocableList;
	typedef RNUnallocableList::iterator RNUnallocableListItr;

	public:

	struct NodeData {
	typedef std::vector<unsigned> UnsafeDegreesArray;
	bool isHeuristic, isAllocable, isInitialized;
	unsigned numDenied, numSafe;
	UnsafeDegreesArray unsafeDegrees;
	RNAllocableListItr rnaItr;
	RNUnallocableListItr rnuItr;

	NodeData()
	: isHeuristic(false), isAllocable(false), isInitialized(false),
	numDenied(0), numSafe(0) { }
	};

	struct EdgeData {
	typedef std::vector<unsigned> UnsafeArray;
	unsigned worst, reverseWorst;
	UnsafeArray unsafe, reverseUnsafe;
	bool isUpToDate;

	EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {}
	};

	/// \brief Construct an instance of the Briggs heuristic.
	/// @param solver A reference to the solver which is using this heuristic.
	Briggs(HeuristicSolverImpl<Briggs> &solver) :
	HeuristicBase<Briggs>(solver) {}

	/// \brief Determine whether a node should be reduced using optimal
	/// reduction.
	/// @param nItr Node iterator to be considered.
	/// @return 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.
	bool shouldOptimallyReduce(Graph::NodeItr nItr) {
	if (getSolver().getSolverDegree(nItr) < 3) {
	return true;
	}
	// else
	return false;
	}

	/// \brief Add a node to the heuristic reduce list.
	/// @param nItr Node iterator to add to the heuristic reduce list.
	void addToHeuristicReduceList(Graph::NodeItr nItr) {
	NodeData &nd = getHeuristicNodeData(nItr);
	initializeNode(nItr);
	nd.isHeuristic = true;
	if (nd.isAllocable) {
	nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
	} else {
	nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
	}
	}

	/// \brief Heuristically reduce one of the nodes in the heuristic
	/// reduce list.
	/// @return 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.
	bool heuristicReduce() {
	if (!rnAllocableList.empty()) {
	RNAllocableListItr rnaItr =
	min_element(rnAllocableList.begin(), rnAllocableList.end(),
	LinkDegreeComparator(getSolver()));
	Graph::NodeItr nItr = *rnaItr;
	rnAllocableList.erase(rnaItr);
	handleRemoveNode(nItr);
	getSolver().pushToStack(nItr);
	return true;
	} else if (!rnUnallocableList.empty()) {
	RNUnallocableListItr rnuItr =
	min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
	SpillCostComparator(getSolver()));
	Graph::NodeItr nItr = *rnuItr;
	rnUnallocableList.erase(rnuItr);
	handleRemoveNode(nItr);
	getSolver().pushToStack(nItr);
	return true;
	}
	// else
	return false;
	}

	/// \brief Prepare a change in the costs on the given edge.
	/// @param eItr Edge iterator.
	void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
	Graph &g = getGraph();
	Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
	n2Itr = g.getEdgeNode2(eItr);
	NodeData &n1 = getHeuristicNodeData(n1Itr),
	&n2 = getHeuristicNodeData(n2Itr);

	if (n1.isHeuristic)
	subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
	if (n2.isHeuristic)
	subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));

	EdgeData &ed = getHeuristicEdgeData(eItr);
	ed.isUpToDate = false;
	}

	/// \brief Handle the change in the costs on the given edge.
	/// @param eItr Edge iterator.
	void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
	// This is effectively the same as adding a new edge now, since
	// we've factored out the costs of the old one.
	handleAddEdge(eItr);
	}

	/// \brief Handle the addition of a new edge into the PBQP graph.
	/// @param eItr Edge iterator 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.
	void handleAddEdge(Graph::EdgeItr eItr) {
	Graph &g = getGraph();
	Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
	n2Itr = g.getEdgeNode2(eItr);
	NodeData &n1 = getHeuristicNodeData(n1Itr),
	&n2 = getHeuristicNodeData(n2Itr);

	// If neither node is managed by the heuristic there's nothing to be
	// done.
	if (!n1.isHeuristic && !n2.isHeuristic)
	return;

	// Ok - we need to update at least one node.
	computeEdgeContributions(eItr);

	// Update node 1 if it's managed by the heuristic.
	if (n1.isHeuristic) {
	bool n1WasAllocable = n1.isAllocable;
	addEdgeContributions(eItr, n1Itr);
	updateAllocability(n1Itr);
	if (n1WasAllocable && !n1.isAllocable) {
	rnAllocableList.erase(n1.rnaItr);
	n1.rnuItr =
	rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
	}
	}

	// Likewise for node 2.
	if (n2.isHeuristic) {
	bool n2WasAllocable = n2.isAllocable;
	addEdgeContributions(eItr, n2Itr);
	updateAllocability(n2Itr);
	if (n2WasAllocable && !n2.isAllocable) {
	rnAllocableList.erase(n2.rnaItr);
	n2.rnuItr =
	rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
	}
	}
	}

	/// \brief Handle disconnection of an edge from a node.
	/// @param eItr Edge iterator for edge being disconnected.
	/// @param nItr Node iterator for the node being disconnected from.
	///
	/// Updates allocability of the given node and, if appropriate, moves the
	/// node to a new list.
	void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
	NodeData &nd = getHeuristicNodeData(nItr);

	// If the node is not managed by the heuristic there's nothing to be
	// done.
	if (!nd.isHeuristic)
	return;

	EdgeData &ed = getHeuristicEdgeData(eItr);
	(void)ed;
	assert(ed.isUpToDate && "Edge data is not up to date.");

	// Update node.
	bool ndWasAllocable = nd.isAllocable;
	subtractEdgeContributions(eItr, nItr);
	updateAllocability(nItr);

	// If the node has gone optimal...
	if (shouldOptimallyReduce(nItr)) {
	nd.isHeuristic = false;
	addToOptimalReduceList(nItr);
	if (ndWasAllocable) {
	rnAllocableList.erase(nd.rnaItr);
	} else {
	rnUnallocableList.erase(nd.rnuItr);
	}
	} else {
	// Node didn't go optimal, but we might have to move it
	// from "unallocable" to "allocable".
	if (!ndWasAllocable && nd.isAllocable) {
	rnUnallocableList.erase(nd.rnuItr);
	nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
	}
	}
	}

	private:

	NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
	return getSolver().getHeuristicNodeData(nItr);
	}

	EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
	return getSolver().getHeuristicEdgeData(eItr);
	}

	// Work out what this edge will contribute to the allocability of the
	// nodes connected to it.
	void computeEdgeContributions(Graph::EdgeItr eItr) {
	EdgeData &ed = getHeuristicEdgeData(eItr);

	if (ed.isUpToDate)
	return; // Edge data is already up to date.

	Matrix &eCosts = getGraph().getEdgeCosts(eItr);

	unsigned numRegs = eCosts.getRows() - 1,
	numReverseRegs = eCosts.getCols() - 1;

	std::vector<unsigned> rowInfCounts(numRegs, 0),
	colInfCounts(numReverseRegs, 0);

	ed.worst = 0;
	ed.reverseWorst = 0;
	ed.unsafe.clear();
	ed.unsafe.resize(numRegs, 0);
	ed.reverseUnsafe.clear();
	ed.reverseUnsafe.resize(numReverseRegs, 0);

	for (unsigned i = 0; i < numRegs; ++i) {
	for (unsigned j = 0; j < numReverseRegs; ++j) {
	if (eCosts[i + 1][j + 1] ==
	std::numeric_limits<PBQPNum>::infinity()) {
	ed.unsafe[i] = 1;
	ed.reverseUnsafe[j] = 1;
	++rowInfCounts[i];
	++colInfCounts[j];

	if (colInfCounts[j] > ed.worst) {
	ed.worst = colInfCounts[j];
	}

	if (rowInfCounts[i] > ed.reverseWorst) {
	ed.reverseWorst = rowInfCounts[i];
	}
	}
	}
	}

	ed.isUpToDate = true;
	}

	// Add the contributions of the given edge to the given node's
	// numDenied and safe members. No action is taken other than to update
	// these member values. Once updated these numbers can be used by clients
	// to update the node's allocability.
	void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
	EdgeData &ed = getHeuristicEdgeData(eItr);

	assert(ed.isUpToDate && "Using out-of-date edge numbers.");

	NodeData &nd = getHeuristicNodeData(nItr);
	unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;

	bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
	EdgeData::UnsafeArray &unsafe =
	nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
	nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;

	for (unsigned r = 0; r < numRegs; ++r) {
	if (unsafe[r]) {
	if (nd.unsafeDegrees[r]==0) {
	--nd.numSafe;
	}
	++nd.unsafeDegrees[r];
	}
	}
	}

	// Subtract the contributions of the given edge to the given node's
	// numDenied and safe members. No action is taken other than to update
	// these member values. Once updated these numbers can be used by clients
	// to update the node's allocability.
	void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
	EdgeData &ed = getHeuristicEdgeData(eItr);

	assert(ed.isUpToDate && "Using out-of-date edge numbers.");

	NodeData &nd = getHeuristicNodeData(nItr);
	unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;

	bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
	EdgeData::UnsafeArray &unsafe =
	nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
	nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;

	for (unsigned r = 0; r < numRegs; ++r) {
	if (unsafe[r]) {
	if (nd.unsafeDegrees[r] == 1) {
	++nd.numSafe;
	}
	--nd.unsafeDegrees[r];
	}
	}
	}

	void updateAllocability(Graph::NodeItr nItr) {
	NodeData &nd = getHeuristicNodeData(nItr);
	unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
	nd.isAllocable = nd.numDenied < numRegs \|\| nd.numSafe > 0;
	}

	void initializeNode(Graph::NodeItr nItr) {
	NodeData &nd = getHeuristicNodeData(nItr);

	if (nd.isInitialized)
	return; // Node data is already up to date.

	unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;

	nd.numDenied = 0;
	nd.numSafe = numRegs;
	nd.unsafeDegrees.resize(numRegs, 0);

	typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;

	for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
	aeEnd = getSolver().solverEdgesEnd(nItr);
	aeItr != aeEnd; ++aeItr) {

	Graph::EdgeItr eItr = *aeItr;
	computeEdgeContributions(eItr);
	addEdgeContributions(eItr, nItr);
	}

	updateAllocability(nItr);
	nd.isInitialized = true;
	}

	void handleRemoveNode(Graph::NodeItr xnItr) {
	typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
	std::vector<Graph::EdgeItr> edgesToRemove;
	for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
	aeEnd = getSolver().solverEdgesEnd(xnItr);
	aeItr != aeEnd; ++aeItr) {
	Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
	handleRemoveEdge(*aeItr, ynItr);
	edgesToRemove.push_back(*aeItr);
	}
	while (!edgesToRemove.empty()) {
	getSolver().removeSolverEdge(edgesToRemove.back());
	edgesToRemove.pop_back();
	}
	}

	RNAllocableList rnAllocableList;
	RNUnallocableList rnUnallocableList;
	};

	}
	}


	#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H