diff options
author | rdivacky <rdivacky@FreeBSD.org> | 2009-10-14 17:57:32 +0000 |
---|---|---|
committer | rdivacky <rdivacky@FreeBSD.org> | 2009-10-14 17:57:32 +0000 |
commit | cd749a9c07f1de2fb8affde90537efa4bc3e7c54 (patch) | |
tree | b21f6de4e08b89bb7931806bab798fc2a5e3a686 /lib/CodeGen/PBQP/ExhaustiveSolver.h | |
parent | 72621d11de5b873f1695f391eb95f0b336c3d2d4 (diff) | |
download | FreeBSD-src-cd749a9c07f1de2fb8affde90537efa4bc3e7c54.zip FreeBSD-src-cd749a9c07f1de2fb8affde90537efa4bc3e7c54.tar.gz |
Update llvm to r84119.
Diffstat (limited to 'lib/CodeGen/PBQP/ExhaustiveSolver.h')
-rw-r--r-- | lib/CodeGen/PBQP/ExhaustiveSolver.h | 110 |
1 files changed, 110 insertions, 0 deletions
diff --git a/lib/CodeGen/PBQP/ExhaustiveSolver.h b/lib/CodeGen/PBQP/ExhaustiveSolver.h new file mode 100644 index 0000000..b2f2e6f --- /dev/null +++ b/lib/CodeGen/PBQP/ExhaustiveSolver.h @@ -0,0 +1,110 @@ +//===-- 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 + +#include "Solver.h" + +namespace PBQP { + +/// A brute force PBQP solver. This solver takes exponential time. It should +/// only be used for debugging purposes. +class ExhaustiveSolverImpl { +private: + + const SimpleGraph &g; + + PBQPNum getSolutionCost(const Solution &solution) const { + PBQPNum cost = 0.0; + + for (SimpleGraph::ConstNodeIterator + nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd(); + nodeItr != nodeEnd; ++nodeItr) { + + unsigned nodeId = g.getNodeID(nodeItr); + + cost += g.getNodeCosts(nodeItr)[solution.getSelection(nodeId)]; + } + + for (SimpleGraph::ConstEdgeIterator + edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd(); + edgeItr != edgeEnd; ++edgeItr) { + + SimpleGraph::ConstNodeIterator n1 = g.getEdgeNode1Itr(edgeItr), + n2 = g.getEdgeNode2Itr(edgeItr); + unsigned sol1 = solution.getSelection(g.getNodeID(n1)), + sol2 = solution.getSelection(g.getNodeID(n2)); + + cost += g.getEdgeCosts(edgeItr)[sol1][sol2]; + } + + return cost; + } + +public: + + ExhaustiveSolverImpl(const SimpleGraph &g) : g(g) {} + + Solution solve() const { + Solution current(g.getNumNodes(), true), optimal(current); + + PBQPNum bestCost = std::numeric_limits<PBQPNum>::infinity(); + bool finished = false; + + while (!finished) { + PBQPNum currentCost = getSolutionCost(current); + + if (currentCost < bestCost) { + optimal = current; + bestCost = currentCost; + } + + // assume we're done. + finished = true; + + for (unsigned i = 0; i < g.getNumNodes(); ++i) { + if (current.getSelection(i) == + (g.getNodeCosts(g.getNodeItr(i)).getLength() - 1)) { + current.setSelection(i, 0); + } + else { + current.setSelection(i, current.getSelection(i) + 1); + finished = false; + break; + } + } + + } + + optimal.setSolutionCost(bestCost); + + return optimal; + } + +}; + +class ExhaustiveSolver : public Solver { +public: + ~ExhaustiveSolver() {} + Solution solve(const SimpleGraph &g) const { + ExhaustiveSolverImpl solver(g); + return solver.solve(); + } +}; + +} + +#endif // LLVM_CODGEN_PBQP_EXHAUSTIVESOLVER_HPP |