1218885Sdim//===-- Briggs.h --- Briggs Heuristic for PBQP ------------------*- C++ -*-===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This class implements the Briggs test for "allocability" of nodes in a 11218885Sdim// PBQP graph representing a register allocation problem. Nodes which can be 12218885Sdim// proven allocable (by a safe and relatively accurate test) are removed from 13218885Sdim// the PBQP graph first. If no provably allocable node is present in the graph 14218885Sdim// then the node with the minimal spill-cost to degree ratio is removed. 15218885Sdim// 16218885Sdim//===----------------------------------------------------------------------===// 17218885Sdim 18218885Sdim#ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H 19218885Sdim#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H 20218885Sdim 21249423Sdim#include "../HeuristicBase.h" 22218885Sdim#include "../HeuristicSolver.h" 23218885Sdim#include <limits> 24218885Sdim 25218885Sdimnamespace PBQP { 26218885Sdim namespace Heuristics { 27218885Sdim 28218885Sdim /// \brief PBQP Heuristic which applies an allocability test based on 29218885Sdim /// Briggs. 30218885Sdim /// 31218885Sdim /// This heuristic assumes that the elements of cost vectors in the PBQP 32218885Sdim /// problem represent storage options, with the first being the spill 33218885Sdim /// option and subsequent elements representing legal registers for the 34218885Sdim /// corresponding node. Edge cost matrices are likewise assumed to represent 35218885Sdim /// register constraints. 36218885Sdim /// If one or more nodes can be proven allocable by this heuristic (by 37218885Sdim /// inspection of their constraint matrices) then the allocable node of 38218885Sdim /// highest degree is selected for the next reduction and pushed to the 39218885Sdim /// solver stack. If no nodes can be proven allocable then the node with 40218885Sdim /// the lowest estimated spill cost is selected and push to the solver stack 41218885Sdim /// instead. 42218885Sdim /// 43218885Sdim /// This implementation is built on top of HeuristicBase. 44218885Sdim class Briggs : public HeuristicBase<Briggs> { 45218885Sdim private: 46218885Sdim 47218885Sdim class LinkDegreeComparator { 48218885Sdim public: 49218885Sdim LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {} 50218885Sdim bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { 51218885Sdim if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr)) 52218885Sdim return true; 53218885Sdim return false; 54218885Sdim } 55218885Sdim private: 56218885Sdim HeuristicSolverImpl<Briggs> *s; 57218885Sdim }; 58218885Sdim 59218885Sdim class SpillCostComparator { 60218885Sdim public: 61218885Sdim SpillCostComparator(HeuristicSolverImpl<Briggs> &s) 62218885Sdim : s(&s), g(&s.getGraph()) {} 63218885Sdim bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { 64218885Sdim const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr); 65218885Sdim const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr); 66218885Sdim 67218885Sdim PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr); 68218885Sdim PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr); 69218885Sdim 70218885Sdim if (cost1 < cost2) 71218885Sdim return true; 72218885Sdim return false; 73218885Sdim } 74218885Sdim 75218885Sdim private: 76218885Sdim HeuristicSolverImpl<Briggs> *s; 77218885Sdim Graph *g; 78218885Sdim }; 79218885Sdim 80218885Sdim typedef std::list<Graph::NodeItr> RNAllocableList; 81218885Sdim typedef RNAllocableList::iterator RNAllocableListItr; 82218885Sdim 83218885Sdim typedef std::list<Graph::NodeItr> RNUnallocableList; 84218885Sdim typedef RNUnallocableList::iterator RNUnallocableListItr; 85218885Sdim 86218885Sdim public: 87218885Sdim 88218885Sdim struct NodeData { 89218885Sdim typedef std::vector<unsigned> UnsafeDegreesArray; 90218885Sdim bool isHeuristic, isAllocable, isInitialized; 91218885Sdim unsigned numDenied, numSafe; 92218885Sdim UnsafeDegreesArray unsafeDegrees; 93218885Sdim RNAllocableListItr rnaItr; 94218885Sdim RNUnallocableListItr rnuItr; 95218885Sdim 96218885Sdim NodeData() 97218885Sdim : isHeuristic(false), isAllocable(false), isInitialized(false), 98218885Sdim numDenied(0), numSafe(0) { } 99218885Sdim }; 100218885Sdim 101218885Sdim struct EdgeData { 102218885Sdim typedef std::vector<unsigned> UnsafeArray; 103218885Sdim unsigned worst, reverseWorst; 104218885Sdim UnsafeArray unsafe, reverseUnsafe; 105218885Sdim bool isUpToDate; 106218885Sdim 107218885Sdim EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {} 108218885Sdim }; 109218885Sdim 110218885Sdim /// \brief Construct an instance of the Briggs heuristic. 111218885Sdim /// @param solver A reference to the solver which is using this heuristic. 112218885Sdim Briggs(HeuristicSolverImpl<Briggs> &solver) : 113218885Sdim HeuristicBase<Briggs>(solver) {} 114218885Sdim 115218885Sdim /// \brief Determine whether a node should be reduced using optimal 116218885Sdim /// reduction. 117218885Sdim /// @param nItr Node iterator to be considered. 118218885Sdim /// @return True if the given node should be optimally reduced, false 119218885Sdim /// otherwise. 120218885Sdim /// 121218885Sdim /// Selects nodes of degree 0, 1 or 2 for optimal reduction, with one 122218885Sdim /// exception. Nodes whose spill cost (element 0 of their cost vector) is 123218885Sdim /// infinite are checked for allocability first. Allocable nodes may be 124218885Sdim /// optimally reduced, but nodes whose allocability cannot be proven are 125218885Sdim /// selected for heuristic reduction instead. 126218885Sdim bool shouldOptimallyReduce(Graph::NodeItr nItr) { 127218885Sdim if (getSolver().getSolverDegree(nItr) < 3) { 128218885Sdim return true; 129218885Sdim } 130218885Sdim // else 131218885Sdim return false; 132218885Sdim } 133218885Sdim 134218885Sdim /// \brief Add a node to the heuristic reduce list. 135218885Sdim /// @param nItr Node iterator to add to the heuristic reduce list. 136218885Sdim void addToHeuristicReduceList(Graph::NodeItr nItr) { 137218885Sdim NodeData &nd = getHeuristicNodeData(nItr); 138218885Sdim initializeNode(nItr); 139218885Sdim nd.isHeuristic = true; 140218885Sdim if (nd.isAllocable) { 141218885Sdim nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); 142218885Sdim } else { 143218885Sdim nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr); 144218885Sdim } 145218885Sdim } 146218885Sdim 147218885Sdim /// \brief Heuristically reduce one of the nodes in the heuristic 148218885Sdim /// reduce list. 149218885Sdim /// @return True if a reduction takes place, false if the heuristic reduce 150218885Sdim /// list is empty. 151218885Sdim /// 152218885Sdim /// If the list of allocable nodes is non-empty a node is selected 153218885Sdim /// from it and pushed to the stack. Otherwise if the non-allocable list 154218885Sdim /// is non-empty a node is selected from it and pushed to the stack. 155218885Sdim /// If both lists are empty the method simply returns false with no action 156218885Sdim /// taken. 157218885Sdim bool heuristicReduce() { 158218885Sdim if (!rnAllocableList.empty()) { 159218885Sdim RNAllocableListItr rnaItr = 160218885Sdim min_element(rnAllocableList.begin(), rnAllocableList.end(), 161218885Sdim LinkDegreeComparator(getSolver())); 162218885Sdim Graph::NodeItr nItr = *rnaItr; 163218885Sdim rnAllocableList.erase(rnaItr); 164218885Sdim handleRemoveNode(nItr); 165218885Sdim getSolver().pushToStack(nItr); 166218885Sdim return true; 167218885Sdim } else if (!rnUnallocableList.empty()) { 168218885Sdim RNUnallocableListItr rnuItr = 169218885Sdim min_element(rnUnallocableList.begin(), rnUnallocableList.end(), 170218885Sdim SpillCostComparator(getSolver())); 171218885Sdim Graph::NodeItr nItr = *rnuItr; 172218885Sdim rnUnallocableList.erase(rnuItr); 173218885Sdim handleRemoveNode(nItr); 174218885Sdim getSolver().pushToStack(nItr); 175218885Sdim return true; 176218885Sdim } 177218885Sdim // else 178218885Sdim return false; 179218885Sdim } 180218885Sdim 181218885Sdim /// \brief Prepare a change in the costs on the given edge. 182218885Sdim /// @param eItr Edge iterator. 183218885Sdim void preUpdateEdgeCosts(Graph::EdgeItr eItr) { 184218885Sdim Graph &g = getGraph(); 185218885Sdim Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), 186218885Sdim n2Itr = g.getEdgeNode2(eItr); 187218885Sdim NodeData &n1 = getHeuristicNodeData(n1Itr), 188218885Sdim &n2 = getHeuristicNodeData(n2Itr); 189218885Sdim 190218885Sdim if (n1.isHeuristic) 191218885Sdim subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr)); 192218885Sdim if (n2.isHeuristic) 193218885Sdim subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr)); 194218885Sdim 195218885Sdim EdgeData &ed = getHeuristicEdgeData(eItr); 196218885Sdim ed.isUpToDate = false; 197218885Sdim } 198218885Sdim 199218885Sdim /// \brief Handle the change in the costs on the given edge. 200218885Sdim /// @param eItr Edge iterator. 201218885Sdim void postUpdateEdgeCosts(Graph::EdgeItr eItr) { 202218885Sdim // This is effectively the same as adding a new edge now, since 203218885Sdim // we've factored out the costs of the old one. 204218885Sdim handleAddEdge(eItr); 205218885Sdim } 206218885Sdim 207218885Sdim /// \brief Handle the addition of a new edge into the PBQP graph. 208218885Sdim /// @param eItr Edge iterator for the added edge. 209218885Sdim /// 210218885Sdim /// Updates allocability of any nodes connected by this edge which are 211218885Sdim /// being managed by the heuristic. If allocability changes they are 212218885Sdim /// moved to the appropriate list. 213218885Sdim void handleAddEdge(Graph::EdgeItr eItr) { 214218885Sdim Graph &g = getGraph(); 215218885Sdim Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), 216218885Sdim n2Itr = g.getEdgeNode2(eItr); 217218885Sdim NodeData &n1 = getHeuristicNodeData(n1Itr), 218218885Sdim &n2 = getHeuristicNodeData(n2Itr); 219218885Sdim 220218885Sdim // If neither node is managed by the heuristic there's nothing to be 221218885Sdim // done. 222218885Sdim if (!n1.isHeuristic && !n2.isHeuristic) 223218885Sdim return; 224218885Sdim 225218885Sdim // Ok - we need to update at least one node. 226218885Sdim computeEdgeContributions(eItr); 227218885Sdim 228218885Sdim // Update node 1 if it's managed by the heuristic. 229218885Sdim if (n1.isHeuristic) { 230218885Sdim bool n1WasAllocable = n1.isAllocable; 231218885Sdim addEdgeContributions(eItr, n1Itr); 232218885Sdim updateAllocability(n1Itr); 233218885Sdim if (n1WasAllocable && !n1.isAllocable) { 234218885Sdim rnAllocableList.erase(n1.rnaItr); 235218885Sdim n1.rnuItr = 236218885Sdim rnUnallocableList.insert(rnUnallocableList.end(), n1Itr); 237218885Sdim } 238218885Sdim } 239218885Sdim 240218885Sdim // Likewise for node 2. 241218885Sdim if (n2.isHeuristic) { 242218885Sdim bool n2WasAllocable = n2.isAllocable; 243218885Sdim addEdgeContributions(eItr, n2Itr); 244218885Sdim updateAllocability(n2Itr); 245218885Sdim if (n2WasAllocable && !n2.isAllocable) { 246218885Sdim rnAllocableList.erase(n2.rnaItr); 247218885Sdim n2.rnuItr = 248218885Sdim rnUnallocableList.insert(rnUnallocableList.end(), n2Itr); 249218885Sdim } 250218885Sdim } 251218885Sdim } 252218885Sdim 253218885Sdim /// \brief Handle disconnection of an edge from a node. 254218885Sdim /// @param eItr Edge iterator for edge being disconnected. 255218885Sdim /// @param nItr Node iterator for the node being disconnected from. 256218885Sdim /// 257218885Sdim /// Updates allocability of the given node and, if appropriate, moves the 258218885Sdim /// node to a new list. 259218885Sdim void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) { 260218885Sdim NodeData &nd = getHeuristicNodeData(nItr); 261218885Sdim 262218885Sdim // If the node is not managed by the heuristic there's nothing to be 263218885Sdim // done. 264218885Sdim if (!nd.isHeuristic) 265218885Sdim return; 266218885Sdim 267218885Sdim EdgeData &ed = getHeuristicEdgeData(eItr); 268218885Sdim (void)ed; 269218885Sdim assert(ed.isUpToDate && "Edge data is not up to date."); 270218885Sdim 271218885Sdim // Update node. 272218885Sdim bool ndWasAllocable = nd.isAllocable; 273218885Sdim subtractEdgeContributions(eItr, nItr); 274218885Sdim updateAllocability(nItr); 275218885Sdim 276218885Sdim // If the node has gone optimal... 277218885Sdim if (shouldOptimallyReduce(nItr)) { 278218885Sdim nd.isHeuristic = false; 279218885Sdim addToOptimalReduceList(nItr); 280218885Sdim if (ndWasAllocable) { 281218885Sdim rnAllocableList.erase(nd.rnaItr); 282218885Sdim } else { 283218885Sdim rnUnallocableList.erase(nd.rnuItr); 284218885Sdim } 285218885Sdim } else { 286218885Sdim // Node didn't go optimal, but we might have to move it 287218885Sdim // from "unallocable" to "allocable". 288218885Sdim if (!ndWasAllocable && nd.isAllocable) { 289218885Sdim rnUnallocableList.erase(nd.rnuItr); 290218885Sdim nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); 291218885Sdim } 292218885Sdim } 293218885Sdim } 294218885Sdim 295218885Sdim private: 296218885Sdim 297218885Sdim NodeData& getHeuristicNodeData(Graph::NodeItr nItr) { 298218885Sdim return getSolver().getHeuristicNodeData(nItr); 299218885Sdim } 300218885Sdim 301218885Sdim EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { 302218885Sdim return getSolver().getHeuristicEdgeData(eItr); 303218885Sdim } 304218885Sdim 305218885Sdim // Work out what this edge will contribute to the allocability of the 306218885Sdim // nodes connected to it. 307218885Sdim void computeEdgeContributions(Graph::EdgeItr eItr) { 308218885Sdim EdgeData &ed = getHeuristicEdgeData(eItr); 309218885Sdim 310218885Sdim if (ed.isUpToDate) 311218885Sdim return; // Edge data is already up to date. 312218885Sdim 313218885Sdim Matrix &eCosts = getGraph().getEdgeCosts(eItr); 314218885Sdim 315218885Sdim unsigned numRegs = eCosts.getRows() - 1, 316218885Sdim numReverseRegs = eCosts.getCols() - 1; 317218885Sdim 318218885Sdim std::vector<unsigned> rowInfCounts(numRegs, 0), 319218885Sdim colInfCounts(numReverseRegs, 0); 320218885Sdim 321218885Sdim ed.worst = 0; 322218885Sdim ed.reverseWorst = 0; 323218885Sdim ed.unsafe.clear(); 324218885Sdim ed.unsafe.resize(numRegs, 0); 325218885Sdim ed.reverseUnsafe.clear(); 326218885Sdim ed.reverseUnsafe.resize(numReverseRegs, 0); 327218885Sdim 328218885Sdim for (unsigned i = 0; i < numRegs; ++i) { 329218885Sdim for (unsigned j = 0; j < numReverseRegs; ++j) { 330218885Sdim if (eCosts[i + 1][j + 1] == 331218885Sdim std::numeric_limits<PBQPNum>::infinity()) { 332218885Sdim ed.unsafe[i] = 1; 333218885Sdim ed.reverseUnsafe[j] = 1; 334218885Sdim ++rowInfCounts[i]; 335218885Sdim ++colInfCounts[j]; 336218885Sdim 337218885Sdim if (colInfCounts[j] > ed.worst) { 338218885Sdim ed.worst = colInfCounts[j]; 339218885Sdim } 340218885Sdim 341218885Sdim if (rowInfCounts[i] > ed.reverseWorst) { 342218885Sdim ed.reverseWorst = rowInfCounts[i]; 343218885Sdim } 344218885Sdim } 345218885Sdim } 346218885Sdim } 347218885Sdim 348218885Sdim ed.isUpToDate = true; 349218885Sdim } 350218885Sdim 351218885Sdim // Add the contributions of the given edge to the given node's 352218885Sdim // numDenied and safe members. No action is taken other than to update 353218885Sdim // these member values. Once updated these numbers can be used by clients 354218885Sdim // to update the node's allocability. 355218885Sdim void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) { 356218885Sdim EdgeData &ed = getHeuristicEdgeData(eItr); 357218885Sdim 358218885Sdim assert(ed.isUpToDate && "Using out-of-date edge numbers."); 359218885Sdim 360218885Sdim NodeData &nd = getHeuristicNodeData(nItr); 361218885Sdim unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; 362218885Sdim 363218885Sdim bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr); 364218885Sdim EdgeData::UnsafeArray &unsafe = 365218885Sdim nIsNode1 ? ed.unsafe : ed.reverseUnsafe; 366218885Sdim nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst; 367218885Sdim 368218885Sdim for (unsigned r = 0; r < numRegs; ++r) { 369218885Sdim if (unsafe[r]) { 370218885Sdim if (nd.unsafeDegrees[r]==0) { 371218885Sdim --nd.numSafe; 372218885Sdim } 373218885Sdim ++nd.unsafeDegrees[r]; 374218885Sdim } 375218885Sdim } 376218885Sdim } 377218885Sdim 378218885Sdim // Subtract the contributions of the given edge to the given node's 379218885Sdim // numDenied and safe members. No action is taken other than to update 380218885Sdim // these member values. Once updated these numbers can be used by clients 381218885Sdim // to update the node's allocability. 382218885Sdim void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) { 383218885Sdim EdgeData &ed = getHeuristicEdgeData(eItr); 384218885Sdim 385218885Sdim assert(ed.isUpToDate && "Using out-of-date edge numbers."); 386218885Sdim 387218885Sdim NodeData &nd = getHeuristicNodeData(nItr); 388218885Sdim unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; 389218885Sdim 390218885Sdim bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr); 391218885Sdim EdgeData::UnsafeArray &unsafe = 392218885Sdim nIsNode1 ? ed.unsafe : ed.reverseUnsafe; 393218885Sdim nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst; 394218885Sdim 395218885Sdim for (unsigned r = 0; r < numRegs; ++r) { 396218885Sdim if (unsafe[r]) { 397218885Sdim if (nd.unsafeDegrees[r] == 1) { 398218885Sdim ++nd.numSafe; 399218885Sdim } 400218885Sdim --nd.unsafeDegrees[r]; 401218885Sdim } 402218885Sdim } 403218885Sdim } 404218885Sdim 405218885Sdim void updateAllocability(Graph::NodeItr nItr) { 406218885Sdim NodeData &nd = getHeuristicNodeData(nItr); 407218885Sdim unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; 408218885Sdim nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0; 409218885Sdim } 410218885Sdim 411218885Sdim void initializeNode(Graph::NodeItr nItr) { 412218885Sdim NodeData &nd = getHeuristicNodeData(nItr); 413218885Sdim 414218885Sdim if (nd.isInitialized) 415218885Sdim return; // Node data is already up to date. 416218885Sdim 417218885Sdim unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; 418218885Sdim 419218885Sdim nd.numDenied = 0; 420234353Sdim const Vector& nCosts = getGraph().getNodeCosts(nItr); 421234353Sdim for (unsigned i = 1; i < nCosts.getLength(); ++i) { 422234353Sdim if (nCosts[i] == std::numeric_limits<PBQPNum>::infinity()) 423234353Sdim ++nd.numDenied; 424234353Sdim } 425234353Sdim 426218885Sdim nd.numSafe = numRegs; 427218885Sdim nd.unsafeDegrees.resize(numRegs, 0); 428218885Sdim 429218885Sdim typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; 430218885Sdim 431218885Sdim for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr), 432218885Sdim aeEnd = getSolver().solverEdgesEnd(nItr); 433218885Sdim aeItr != aeEnd; ++aeItr) { 434218885Sdim 435218885Sdim Graph::EdgeItr eItr = *aeItr; 436218885Sdim computeEdgeContributions(eItr); 437218885Sdim addEdgeContributions(eItr, nItr); 438218885Sdim } 439218885Sdim 440218885Sdim updateAllocability(nItr); 441218885Sdim nd.isInitialized = true; 442218885Sdim } 443218885Sdim 444218885Sdim void handleRemoveNode(Graph::NodeItr xnItr) { 445218885Sdim typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; 446218885Sdim std::vector<Graph::EdgeItr> edgesToRemove; 447218885Sdim for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr), 448218885Sdim aeEnd = getSolver().solverEdgesEnd(xnItr); 449218885Sdim aeItr != aeEnd; ++aeItr) { 450218885Sdim Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr); 451218885Sdim handleRemoveEdge(*aeItr, ynItr); 452218885Sdim edgesToRemove.push_back(*aeItr); 453218885Sdim } 454218885Sdim while (!edgesToRemove.empty()) { 455218885Sdim getSolver().removeSolverEdge(edgesToRemove.back()); 456218885Sdim edgesToRemove.pop_back(); 457218885Sdim } 458218885Sdim } 459218885Sdim 460218885Sdim RNAllocableList rnAllocableList; 461218885Sdim RNUnallocableList rnUnallocableList; 462218885Sdim }; 463218885Sdim 464218885Sdim } 465218885Sdim} 466218885Sdim 467218885Sdim 468218885Sdim#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H 469