From: Lang Hames Date: Fri, 7 Aug 2009 00:25:12 +0000 (+0000) Subject: Added legal stuff, fixed some formatting issues. Removed the graph generator stuff... X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=caaf120a676f493b1535c9facd188539bfad3f80 Added legal stuff, fixed some formatting issues. Removed the graph generator stuff as it was only meant for debugging the solver. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@78359 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/CodeGen/PBQP/AnnotatedGraph.h b/lib/CodeGen/PBQP/AnnotatedGraph.h index 801b01e3337..904061ca4fb 100644 --- a/lib/CodeGen/PBQP/AnnotatedGraph.h +++ b/lib/CodeGen/PBQP/AnnotatedGraph.h @@ -1,3 +1,17 @@ +//===-- AnnotatedGraph.h - Annotated PBQP Graph ----------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Annotated PBQP Graph class. This class is used internally by the PBQP solver +// to cache information to speed up reduction. +// +//===----------------------------------------------------------------------===// + #ifndef LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H #define LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H diff --git a/lib/CodeGen/PBQP/ExhaustiveSolver.h b/lib/CodeGen/PBQP/ExhaustiveSolver.h index 98f7140ff09..b2f2e6f620f 100644 --- a/lib/CodeGen/PBQP/ExhaustiveSolver.h +++ b/lib/CodeGen/PBQP/ExhaustiveSolver.h @@ -1,3 +1,18 @@ +//===-- ExhaustiveSolver.h - Brute Force PBQP Solver -----------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Uses a trivial brute force algorithm to solve a PBQP problem. +// PBQP is NP-HARD - This solver should only be used for debugging small +// problems. +// +//===----------------------------------------------------------------------===// + #ifndef LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H #define LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H @@ -5,6 +20,8 @@ namespace PBQP { +/// A brute force PBQP solver. This solver takes exponential time. It should +/// only be used for debugging purposes. class ExhaustiveSolverImpl { private: diff --git a/lib/CodeGen/PBQP/GraphBase.h b/lib/CodeGen/PBQP/GraphBase.h index bda5952e22a..f04a1639f64 100644 --- a/lib/CodeGen/PBQP/GraphBase.h +++ b/lib/CodeGen/PBQP/GraphBase.h @@ -1,3 +1,17 @@ +//===-- GraphBase.h - Abstract Base PBQP Graph -----------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Base class for PBQP Graphs. +// +//===----------------------------------------------------------------------===// + + #ifndef LLVM_CODEGEN_PBQP_GRAPHBASE_H #define LLVM_CODEGEN_PBQP_GRAPHBASE_H diff --git a/lib/CodeGen/PBQP/GraphGenerator.h b/lib/CodeGen/PBQP/GraphGenerator.h deleted file mode 100644 index 620e21e2762..00000000000 --- a/lib/CodeGen/PBQP/GraphGenerator.h +++ /dev/null @@ -1,195 +0,0 @@ -#ifndef LLVM_CODEGEN_PBQP_GRAPHGENERATOR_H -#define LLVM_CODEGEN_PBQP_GRAPHGENERATOR_H - -#include "PBQPMath.h" - -namespace PBQP { - -unsigned randRange(unsigned min, unsigned max) { - return min + (rand() % (max - min + 1)); -} - -class BasicNodeCostsGenerator { -private: - - unsigned maxDegree, minCost, maxCost; - - -public: - - BasicNodeCostsGenerator(unsigned maxDegree, unsigned minCost, - unsigned maxCost) : - maxDegree(maxDegree), minCost(minCost), maxCost(maxCost) { } - - Vector operator()() const { - Vector v(randRange(1, maxDegree)); - for (unsigned i = 0; i < v.getLength(); ++i) { - v[i] = randRange(minCost, maxCost); - } - return v; - }; - -}; - -class FixedDegreeSpillCostGenerator { -private: - - unsigned degree, spillCostMin, spillCostMax; - -public: - - FixedDegreeSpillCostGenerator(unsigned degree, unsigned spillCostMin, - unsigned spillCostMax) : - degree(degree), spillCostMin(spillCostMin), spillCostMax(spillCostMax) { } - - Vector operator()() const { - Vector v(degree, 0); - v[0] = randRange(spillCostMin, spillCostMax); - return v; - } - -}; - -class BasicEdgeCostsGenerator { -private: - - unsigned minCost, maxCost; - -public: - - BasicEdgeCostsGenerator(unsigned minCost, unsigned maxCost) : - minCost(minCost), maxCost(maxCost) {} - - Matrix operator()(const SimpleGraph &g, - const SimpleGraph::ConstNodeIterator &n1, - const SimpleGraph::ConstNodeIterator &n2) const { - - Matrix m(g.getNodeCosts(n1).getLength(), - g.getNodeCosts(n2).getLength()); - - for (unsigned i = 0; i < m.getRows(); ++i) { - for (unsigned j = 0; j < m.getCols(); ++j) { - m[i][j] = randRange(minCost, maxCost); - } - } - - return m; - } - -}; - -class InterferenceCostsGenerator { -public: - - Matrix operator()(const SimpleGraph &g, - const SimpleGraph::ConstNodeIterator &n1, - const SimpleGraph::ConstNodeIterator &n2) const { - - unsigned len = g.getNodeCosts(n1).getLength(); - - assert(len == g.getNodeCosts(n2).getLength()); - - Matrix m(len, len); - - m[0][0] = 0; - for (unsigned i = 1; i < len; ++i) { - m[i][i] = std::numeric_limits::infinity(); - } - - return m; - } -}; - -class RingEdgeGenerator { -public: - - template - void operator()(SimpleGraph &g, EdgeCostsGenerator &edgeCostsGen) { - - assert(g.areNodeIDsValid() && "Graph must have valid node IDs."); - - if (g.getNumNodes() < 2) - return; - - if (g.getNumNodes() == 2) { - SimpleGraph::NodeIterator n1 = g.getNodeItr(0), - n2 = g.getNodeItr(1); - g.addEdge(n1, n2, edgeCostsGen(g, n1, n2)); - return; - } - - // Else |V| > 2: - for (unsigned i = 0; i < g.getNumNodes(); ++i) { - SimpleGraph::NodeIterator - n1 = g.getNodeItr(i), - n2 = g.getNodeItr((i + 1) % g.getNumNodes()); - g.addEdge(n1, n2, edgeCostsGen(g, n1, n2)); - } - } - -}; - -class FullyConnectedEdgeGenerator { -public: - - template - void operator()(SimpleGraph &g, EdgeCostsGenerator &edgeCostsGen) { - assert(g.areNodeIDsValid() && "Graph must have valid node IDs."); - - for (unsigned i = 0; i < g.getNumNodes(); ++i) { - for (unsigned j = i + 1; j < g.getNumNodes(); ++j) { - SimpleGraph::NodeIterator - n1 = g.getNodeItr(i), - n2 = g.getNodeItr(j); - g.addEdge(n1, n2, edgeCostsGen(g, n1, n2)); - } - } - } - -}; - -class RandomEdgeGenerator { -public: - - template - void operator()(SimpleGraph &g, EdgeCostsGenerator &edgeCostsGen) { - - assert(g.areNodeIDsValid() && "Graph must have valid node IDs."); - - for (unsigned i = 0; i < g.getNumNodes(); ++i) { - for (unsigned j = i + 1; j < g.getNumNodes(); ++j) { - if (rand() % 2 == 0) { - SimpleGraph::NodeIterator - n1 = g.getNodeItr(i), - n2 = g.getNodeItr(j); - g.addEdge(n1, n2, edgeCostsGen(g, n1, n2)); - } - } - } - } - -}; - -template -SimpleGraph createRandomGraph(unsigned numNodes, - NodeCostsGenerator nodeCostsGen, - EdgesGenerator edgeGen, - EdgeCostsGenerator edgeCostsGen) { - - SimpleGraph g; - for (unsigned n = 0; n < numNodes; ++n) { - g.addNode(nodeCostsGen()); - } - - g.assignNodeIDs(); - - edgeGen(g, edgeCostsGen); - - return g; -} - -} - -#endif // LLVM_CODEGEN_PBQP_GRAPHGENERATOR_H diff --git a/lib/CodeGen/PBQP/HeuristicSolver.h b/lib/CodeGen/PBQP/HeuristicSolver.h index 7088f364568..a36ca78e2f3 100644 --- a/lib/CodeGen/PBQP/HeuristicSolver.h +++ b/lib/CodeGen/PBQP/HeuristicSolver.h @@ -1,3 +1,18 @@ +//===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Heuristic PBQP solver. This solver is able to perform optimal reductions for +// nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is +// used to to select a node for reduction. +// +//===----------------------------------------------------------------------===// + #ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H #define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H @@ -153,9 +168,7 @@ public: typedef std::vector NodeStack; typedef typename NodeStack::iterator NodeStackIterator; - /*! - * \brief Constructor, which performs all the actual solver work. - */ + /// \brief Constructor, which performs all the actual solver work. HeuristicSolverImpl(const SimpleGraph &orig) : solution(orig.getNumNodes(), true) { @@ -166,22 +179,16 @@ public: computeSolutionCost(orig); } - /*! - * \brief Returns the graph for this solver. - */ + /// \brief Returns the graph for this solver. SolverGraph& getGraph() { return g; } - /*! - * \brief Return the solution found by this solver. - */ + /// \brief Return the solution found by this solver. const Solution& getSolution() const { return solution; } private: - /*! - * \brief Add the given node to the appropriate bucket for its link - * degree. - */ + /// \brief Add the given node to the appropriate bucket for its link + /// degree. void addToBucket(const GraphNodeIterator &nodeItr) { NodeData &nodeData = g.getNodeData(nodeItr); @@ -200,10 +207,8 @@ private: } } - /*! - * \brief Remove the given node from the appropriate bucket for its link - * degree. - */ + /// \brief Remove the given node from the appropriate bucket for its link + /// degree. void removeFromBucket(const GraphNodeIterator &nodeItr) { NodeData &nodeData = g.getNodeData(nodeItr); @@ -217,9 +222,7 @@ private: public: - /*! - * \brief Add a link. - */ + /// \brief Add a link. void addLink(const GraphEdgeIterator &edgeItr) { g.getEdgeData(edgeItr).setup(edgeItr); @@ -229,12 +232,10 @@ public: } } - /*! - * \brief Remove link, update info for node. - * - * Only updates information for the given node, since usually the other - * is about to be removed. - */ + /// \brief Remove link, update info for node. + /// + /// Only updates information for the given node, since usually the other + /// is about to be removed. void removeLink(const GraphEdgeIterator &edgeItr, const GraphNodeIterator &nodeItr) { @@ -244,9 +245,7 @@ public: g.getEdgeData(edgeItr).unlink(); } - /*! - * \brief Remove link, update info for both nodes. Useful for R2 only. - */ + /// \brief Remove link, update info for both nodes. Useful for R2 only. void removeLinkR2(const GraphEdgeIterator &edgeItr) { GraphNodeIterator node1Itr = g.getEdgeNode1Itr(edgeItr); @@ -256,9 +255,7 @@ public: removeLink(edgeItr, g.getEdgeNode2Itr(edgeItr)); } - /*! - * \brief Removes all links connected to the given node. - */ + /// \brief Removes all links connected to the given node. void unlinkNode(const GraphNodeIterator &nodeItr) { NodeData &nodeData = g.getNodeData(nodeItr); @@ -284,17 +281,13 @@ public: } } - /*! - * \brief Push the given node onto the stack to be solved with - * backpropagation. - */ + /// \brief Push the given node onto the stack to be solved with + /// backpropagation. void pushStack(const GraphNodeIterator &nodeItr) { stack.push_back(nodeItr); } - /*! - * \brief Set the solution of the given node. - */ + /// \brief Set the solution of the given node. void setSolution(const GraphNodeIterator &nodeItr, unsigned solIndex) { solution.setSelection(g.getNodeID(nodeItr), solIndex); diff --git a/lib/CodeGen/PBQP/Heuristics/Briggs.h b/lib/CodeGen/PBQP/Heuristics/Briggs.h index fd37f5cbb32..255ffef529d 100644 --- a/lib/CodeGen/PBQP/Heuristics/Briggs.h +++ b/lib/CodeGen/PBQP/Heuristics/Briggs.h @@ -1,3 +1,20 @@ +//===-- 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 @@ -327,26 +344,7 @@ class Briggs { } void processRN() { - - /* - std::cerr << "processRN():\n" - << " rNAllocable = [ "; - for (RNAllocableNodeListIterator nItr = rNAllocableBucket.begin(), - nEnd = rNAllocableBucket.end(); - nItr != nEnd; ++nItr) { - std::cerr << g->getNodeID(*nItr) << " (" << g->getNodeData(*nItr).getLinkDegree() << ") "; - } - std::cerr << "]\n" - << " rNUnallocable = [ "; - for (RNUnallocableNodeListIterator nItr = rNUnallocableBucket.begin(), - nEnd = rNUnallocableBucket.end(); - nItr != nEnd; ++nItr) { - float bCost = g->getNodeCosts(*nItr)[0] / g->getNodeData(*nItr).getLinkDegree(); - std::cerr << g->getNodeID(*nItr) << " (" << bCost << ") "; - } - std::cerr << "]\n"; - */ - + if (!rNAllocableBucket.empty()) { GraphNodeIterator selectedNodeItr = *rNAllocableBucket.begin(); //std::cerr << "RN safely pushing " << g->getNodeID(selectedNodeItr) << "\n"; diff --git a/lib/CodeGen/PBQP/PBQPMath.h b/lib/CodeGen/PBQP/PBQPMath.h index dc184fed144..9bcaf4d545a 100644 --- a/lib/CodeGen/PBQP/PBQPMath.h +++ b/lib/CodeGen/PBQP/PBQPMath.h @@ -1,3 +1,12 @@ +//===-- PBQPMath.h - PBQP Vector and Matrix classes ------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + #ifndef LLVM_CODEGEN_PBQP_PBQPMATH_H #define LLVM_CODEGEN_PBQP_PBQPMATH_H diff --git a/lib/CodeGen/PBQP/SimpleGraph.h b/lib/CodeGen/PBQP/SimpleGraph.h index 595269c327e..1ca9caee346 100644 --- a/lib/CodeGen/PBQP/SimpleGraph.h +++ b/lib/CodeGen/PBQP/SimpleGraph.h @@ -1,3 +1,17 @@ +//===-- SimpleGraph.h - Simple PBQP Graph ----------------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Simple PBQP graph class representing a PBQP problem. Graphs of this type +// can be passed to a PBQPSolver instance to solve the PBQP problem. +// +//===----------------------------------------------------------------------===// + #ifndef LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H #define LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H diff --git a/lib/CodeGen/PBQP/Solution.h b/lib/CodeGen/PBQP/Solution.h index 316c9de5bd1..c91e2fa560a 100644 --- a/lib/CodeGen/PBQP/Solution.h +++ b/lib/CodeGen/PBQP/Solution.h @@ -1,3 +1,17 @@ +//===-- Solution.h ------- PBQP Solution -----------------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Annotated PBQP Graph class. This class is used internally by the PBQP solver +// to cache information to speed up reduction. +// +//===----------------------------------------------------------------------===// + #ifndef LLVM_CODEGEN_PBQP_SOLUTION_H #define LLVM_CODEGEN_PBQP_SOLUTION_H diff --git a/lib/CodeGen/PBQP/Solver.h b/lib/CodeGen/PBQP/Solver.h index 5b6a2849579..a9c5f837c45 100644 --- a/lib/CodeGen/PBQP/Solver.h +++ b/lib/CodeGen/PBQP/Solver.h @@ -1,3 +1,13 @@ +//===-- Solver.h ------- PBQP solver interface -----------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + + #ifndef LLVM_CODEGEN_PBQP_SOLVER_H #define LLVM_CODEGEN_PBQP_SOLVER_H