diff options
author | Lang Hames <lhames@gmail.com> | 2010-02-12 09:43:37 +0000 |
---|---|---|
committer | Lang Hames <lhames@gmail.com> | 2010-02-12 09:43:37 +0000 |
commit | 5cef638855c9f2bb23a9c181cc47ddace8551f50 (patch) | |
tree | 929fa605c106ba2d8cc54f5dd262b0fcdae74f48 /lib/CodeGen/PBQP | |
parent | d19925f48fcbad32755c4cf0dca845a6487fe3c8 (diff) | |
download | external_llvm-5cef638855c9f2bb23a9c181cc47ddace8551f50.zip external_llvm-5cef638855c9f2bb23a9c181cc47ddace8551f50.tar.gz external_llvm-5cef638855c9f2bb23a9c181cc47ddace8551f50.tar.bz2 |
* Updated the cost matrix normalization proceedure to better handle infinite costs.
* Enabled R1/R2 application for nodes with infinite spill costs in the Briggs heuristic (made
safe by the changes to the normalization proceedure).
* Removed a redundant header.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@95973 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen/PBQP')
-rw-r--r-- | lib/CodeGen/PBQP/HeuristicSolver.h | 25 | ||||
-rw-r--r-- | lib/CodeGen/PBQP/Heuristics/Briggs.h | 9 |
2 files changed, 21 insertions, 13 deletions
diff --git a/lib/CodeGen/PBQP/HeuristicSolver.h b/lib/CodeGen/PBQP/HeuristicSolver.h index b48f548..c156264 100644 --- a/lib/CodeGen/PBQP/HeuristicSolver.h +++ b/lib/CodeGen/PBQP/HeuristicSolver.h @@ -18,7 +18,6 @@ #include "Graph.h" #include "Solution.h" -#include "llvm/Support/raw_ostream.h" #include <vector> #include <limits> @@ -494,14 +493,23 @@ namespace PBQP { bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) { + const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity(); + Matrix &edgeCosts = g.getEdgeCosts(eItr); Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)), &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr)); for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { - PBQPNum rowMin = edgeCosts.getRowMin(r); + PBQPNum rowMin = infinity; + + for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { + if (vCosts[c] != infinity && edgeCosts[r][c] < rowMin) + rowMin = edgeCosts[r][c]; + } + uCosts[r] += rowMin; - if (rowMin != std::numeric_limits<PBQPNum>::infinity()) { + + if (rowMin != infinity) { edgeCosts.subFromRow(r, rowMin); } else { @@ -510,9 +518,16 @@ namespace PBQP { } for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { - PBQPNum colMin = edgeCosts.getColMin(c); + PBQPNum colMin = infinity; + + for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { + if (uCosts[r] != infinity && edgeCosts[r][c] < colMin) + colMin = edgeCosts[r][c]; + } + vCosts[c] += colMin; - if (colMin != std::numeric_limits<PBQPNum>::infinity()) { + + if (colMin != infinity) { edgeCosts.subFromCol(c, colMin); } else { diff --git a/lib/CodeGen/PBQP/Heuristics/Briggs.h b/lib/CodeGen/PBQP/Heuristics/Briggs.h index c09ad74..30d34d9 100644 --- a/lib/CodeGen/PBQP/Heuristics/Briggs.h +++ b/lib/CodeGen/PBQP/Heuristics/Briggs.h @@ -128,14 +128,7 @@ namespace PBQP { /// selected for heuristic reduction instead. bool shouldOptimallyReduce(Graph::NodeItr nItr) { if (getSolver().getSolverDegree(nItr) < 3) { - if (getGraph().getNodeCosts(nItr)[0] != - std::numeric_limits<PBQPNum>::infinity()) { - return true; - } - // Otherwise we have an infinite spill cost node. - initializeNode(nItr); - NodeData &nd = getHeuristicNodeData(nItr); - return nd.isAllocable; + return true; } // else return false; |