lib/CodeGen/PBQP/ExhaustiveSolver.h

   1 //===-- ExhaustiveSolver.h - Brute Force PBQP Solver -----------*- C++ --*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Uses a trivial brute force algorithm to solve a PBQP problem.
  11 // PBQP is NP-HARD - This solver should only be used for debugging small
  12 // problems.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
  17 #define LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
  18
  19 #include "Solver.h"
  20
  21 namespace PBQP {
  22
  23 /// A brute force PBQP solver. This solver takes exponential time. It should
  24 /// only be used for debugging purposes.
  25 class ExhaustiveSolverImpl {
  26 private:
  27
  28   const SimpleGraph &g;
  29
  30   PBQPNum getSolutionCost(const Solution &solution) const {
  31     PBQPNum cost = 0.0;
  32
  33     for (SimpleGraph::ConstNodeIterator
  34          nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
  35          nodeItr != nodeEnd; ++nodeItr) {
  36
  37       unsigned nodeId = g.getNodeID(nodeItr);
  38
  39       cost += g.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
  40     }
  41
  42     for (SimpleGraph::ConstEdgeIterator
  43          edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
  44          edgeItr != edgeEnd; ++edgeItr) {
  45
  46       SimpleGraph::ConstNodeIterator n1 = g.getEdgeNode1Itr(edgeItr),
  47                                      n2 = g.getEdgeNode2Itr(edgeItr);
  48       unsigned sol1 = solution.getSelection(g.getNodeID(n1)),
  49                sol2 = solution.getSelection(g.getNodeID(n2));
  50
  51       cost += g.getEdgeCosts(edgeItr)[sol1][sol2];
  52     }
  53
  54     return cost;
  55   }
  56
  57 public:
  58
  59   ExhaustiveSolverImpl(const SimpleGraph &g) : g(g) {}
  60
  61   Solution solve() const {
  62     Solution current(g.getNumNodes(), true), optimal(current);
  63
  64     PBQPNum bestCost = std::numeric_limits<PBQPNum>::infinity();
  65     bool finished = false;
  66
  67     while (!finished) {
  68       PBQPNum currentCost = getSolutionCost(current);
  69
  70       if (currentCost < bestCost) {
  71         optimal = current;
  72         bestCost = currentCost;
  73       }
  74
  75       // assume we're done.
  76       finished = true;
  77
  78       for (unsigned i = 0; i < g.getNumNodes(); ++i) {
  79         if (current.getSelection(i) ==
  80             (g.getNodeCosts(g.getNodeItr(i)).getLength() - 1)) {
  81           current.setSelection(i, 0);
  82         }
  83         else {
  84           current.setSelection(i, current.getSelection(i) + 1);
  85           finished = false;
  86           break;
  87         }
  88       }
  89
  90     }
  91
  92     optimal.setSolutionCost(bestCost);
  93
  94     return optimal;
  95   }
  96
  97 };
  98
  99 class ExhaustiveSolver : public Solver {
 100 public:
 101   ~ExhaustiveSolver() {}
 102   Solution solve(const SimpleGraph &g) const {
 103     ExhaustiveSolverImpl solver(g);
 104     return solver.solve();
 105   }
 106 };
 107
 108 }
 109
 110 #endif // LLVM_CODGEN_PBQP_EXHAUSTIVESOLVER_HPP