aboutsummaryrefslogtreecommitdiffstats
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/llvm/CodeGen/PBQP/Graph.h346
-rw-r--r--include/llvm/CodeGen/PBQP/HeuristicBase.h40
-rw-r--r--include/llvm/CodeGen/PBQP/HeuristicSolver.h248
-rw-r--r--include/llvm/CodeGen/PBQP/Heuristics/Briggs.h176
-rw-r--r--include/llvm/CodeGen/PBQP/Solution.h11
-rw-r--r--include/llvm/CodeGen/RegAllocPBQP.h17
6 files changed, 404 insertions, 434 deletions
diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h
index 9f9a567..b57abca 100644
--- a/include/llvm/CodeGen/PBQP/Graph.h
+++ b/include/llvm/CodeGen/PBQP/Graph.h
@@ -20,63 +20,79 @@
#include "llvm/ADT/ilist_node.h"
#include <list>
#include <map>
-#include <set>
namespace PBQP {
/// PBQP Graph class.
/// Instances of this class describe PBQP problems.
class Graph {
+ private:
+
+ // ----- TYPEDEFS -----
+ class NodeEntry;
+ class EdgeEntry;
+
+ typedef llvm::ilist<NodeEntry> NodeList;
+ typedef llvm::ilist<EdgeEntry> EdgeList;
+
public:
- typedef unsigned NodeId;
- typedef unsigned EdgeId;
+ typedef NodeList::iterator NodeItr;
+ typedef NodeList::const_iterator ConstNodeItr;
- private:
+ typedef EdgeList::iterator EdgeItr;
+ typedef EdgeList::const_iterator ConstEdgeItr;
- typedef std::set<NodeId> AdjEdgeList;
+ private:
+ typedef std::list<EdgeItr> AdjEdgeList;
+
public:
typedef AdjEdgeList::iterator AdjEdgeItr;
private:
- class NodeEntry {
+ class NodeEntry : public llvm::ilist_node<NodeEntry> {
+ friend struct llvm::ilist_sentinel_traits<NodeEntry>;
private:
Vector costs;
AdjEdgeList adjEdges;
+ unsigned degree;
void *data;
NodeEntry() : costs(0, 0) {}
public:
- NodeEntry(const Vector &costs) : costs(costs), data(0) {}
+ NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
Vector& getCosts() { return costs; }
const Vector& getCosts() const { return costs; }
- unsigned getDegree() const { return adjEdges.size(); }
+ unsigned getDegree() const { return degree; }
AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
AdjEdgeItr edgesEnd() { return adjEdges.end(); }
- AdjEdgeItr addEdge(EdgeId e) {
+ AdjEdgeItr addEdge(EdgeItr e) {
+ ++degree;
return adjEdges.insert(adjEdges.end(), e);
}
void removeEdge(AdjEdgeItr ae) {
+ --degree;
adjEdges.erase(ae);
}
void setData(void *data) { this->data = data; }
void* getData() { return data; }
};
- class EdgeEntry {
+ class EdgeEntry : public llvm::ilist_node<EdgeEntry> {
+ friend struct llvm::ilist_sentinel_traits<EdgeEntry>;
private:
- NodeId node1, node2;
+ NodeItr node1, node2;
Matrix costs;
AdjEdgeItr node1AEItr, node2AEItr;
void *data;
- EdgeEntry() : costs(0, 0, 0), data(0) {}
+ EdgeEntry() : costs(0, 0, 0) {}
public:
- EdgeEntry(NodeId node1, NodeId node2, const Matrix &costs)
+ EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
: node1(node1), node2(node2), costs(costs) {}
- NodeId getNode1() const { return node1; }
- NodeId getNode2() const { return node2; }
+ NodeItr getNode1() const { return node1; }
+ NodeItr getNode2() const { return node2; }
Matrix& getCosts() { return costs; }
const Matrix& getCosts() const { return costs; }
void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
@@ -89,126 +105,52 @@ namespace PBQP {
// ----- MEMBERS -----
- typedef std::vector<NodeEntry> NodeVector;
- typedef std::vector<NodeVector::size_type> FreeNodeVector;
- NodeVector nodes;
- FreeNodeVector freeNodes;
+ NodeList nodes;
+ unsigned numNodes;
- typedef std::vector<EdgeEntry> EdgeVector;
- typedef std::vector<EdgeVector::size_type> FreeEdgeVector;
- EdgeVector edges;
- FreeEdgeVector freeEdges;
+ EdgeList edges;
+ unsigned numEdges;
// ----- INTERNAL METHODS -----
- NodeEntry& getNode(NodeId nId) { return nodes[nId]; }
- const NodeEntry& getNode(NodeId nId) const { return nodes[nId]; }
-
- EdgeEntry& getEdge(EdgeId eId) { return edges[eId]; }
- const EdgeEntry& getEdge(EdgeId eId) const { return edges[eId]; }
-
- NodeId addConstructedNode(const NodeEntry &n) {
- NodeId nodeId = 0;
- if (!freeNodes.empty()) {
- nodeId = freeNodes.back();
- freeNodes.pop_back();
- nodes[nodeId] = n;
- } else {
- nodeId = nodes.size();
- nodes.push_back(n);
- }
- return nodeId;
+ NodeEntry& getNode(NodeItr nItr) { return *nItr; }
+ const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; }
+
+ EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
+ const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; }
+
+ NodeItr addConstructedNode(const NodeEntry &n) {
+ ++numNodes;
+ return nodes.insert(nodes.end(), n);
}
- EdgeId addConstructedEdge(const EdgeEntry &e) {
- assert(findEdge(e.getNode1(), e.getNode2()) == invalidEdgeId() &&
+ EdgeItr addConstructedEdge(const EdgeEntry &e) {
+ assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
"Attempt to add duplicate edge.");
- EdgeId edgeId = 0;
- if (!freeEdges.empty()) {
- edgeId = freeEdges.back();
- freeEdges.pop_back();
- edges[edgeId] = e;
- } else {
- edgeId = edges.size();
- edges.push_back(e);
- }
-
- EdgeEntry &ne = getEdge(edgeId);
+ ++numEdges;
+ EdgeItr edgeItr = edges.insert(edges.end(), e);
+ EdgeEntry &ne = getEdge(edgeItr);
NodeEntry &n1 = getNode(ne.getNode1());
NodeEntry &n2 = getNode(ne.getNode2());
-
// Sanity check on matrix dimensions:
assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
(n2.getCosts().getLength() == ne.getCosts().getCols()) &&
"Edge cost dimensions do not match node costs dimensions.");
-
- ne.setNode1AEItr(n1.addEdge(edgeId));
- ne.setNode2AEItr(n2.addEdge(edgeId));
- return edgeId;
+ ne.setNode1AEItr(n1.addEdge(edgeItr));
+ ne.setNode2AEItr(n2.addEdge(edgeItr));
+ return edgeItr;
}
inline void copyFrom(const Graph &other);
public:
- class NodeItr {
- public:
- NodeItr(NodeId nodeId, const Graph &g)
- : nodeId(nodeId), endNodeId(g.nodes.size()), freeNodes(g.freeNodes) {
- this->nodeId = findNextInUse(nodeId); // Move to the first in-use nodeId
- }
-
- bool operator==(const NodeItr& n) const { return nodeId == n.nodeId; }
- bool operator!=(const NodeItr& n) const { return !(*this == n); }
- NodeItr& operator++() { nodeId = findNextInUse(++nodeId); return *this; }
- NodeId operator*() const { return nodeId; }
-
- private:
- NodeId findNextInUse(NodeId n) const {
- while (n < endNodeId &&
- std::find(freeNodes.begin(), freeNodes.end(), n) !=
- freeNodes.end()) {
- ++n;
- }
- return n;
- }
-
- NodeId nodeId, endNodeId;
- const FreeNodeVector& freeNodes;
- };
-
- class EdgeItr {
- public:
- EdgeItr(EdgeId edgeId, const Graph &g)
- : edgeId(edgeId), endEdgeId(g.edges.size()), freeEdges(g.freeEdges) {
- this->edgeId = findNextInUse(edgeId); // Move to the first in-use edgeId
- }
-
- bool operator==(const EdgeItr& n) const { return edgeId == n.edgeId; }
- bool operator!=(const EdgeItr& n) const { return !(*this == n); }
- EdgeItr& operator++() { edgeId = findNextInUse(++edgeId); return *this; }
- EdgeId operator*() const { return edgeId; }
-
- private:
- EdgeId findNextInUse(EdgeId n) const {
- while (n < endEdgeId &&
- std::find(freeEdges.begin(), freeEdges.end(), n) !=
- freeEdges.end()) {
- ++n;
- }
- return n;
- }
-
- EdgeId edgeId, endEdgeId;
- const FreeEdgeVector& freeEdges;
- };
-
/// \brief Construct an empty PBQP graph.
- Graph() {}
+ Graph() : numNodes(0), numEdges(0) {}
/// \brief Copy construct this graph from "other". Note: Does not copy node
/// and edge data, only graph structure and costs.
/// @param other Source graph to copy from.
- Graph(const Graph &other) {
+ Graph(const Graph &other) : numNodes(0), numEdges(0) {
copyFrom(other);
}
@@ -228,7 +170,7 @@ namespace PBQP {
/// \brief Add a node with the given costs.
/// @param costs Cost vector for the new node.
/// @return Node iterator for the added node.
- NodeId addNode(const Vector &costs) {
+ NodeItr addNode(const Vector &costs) {
return addConstructedNode(NodeEntry(costs));
}
@@ -236,31 +178,32 @@ namespace PBQP {
/// @param n1Itr First node.
/// @param n2Itr Second node.
/// @return Edge iterator for the added edge.
- EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs) {
- assert(getNodeCosts(n1Id).getLength() == costs.getRows() &&
- getNodeCosts(n2Id).getLength() == costs.getCols() &&
+ EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
+ const Matrix &costs) {
+ assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
+ getNodeCosts(n2Itr).getLength() == costs.getCols() &&
"Matrix dimensions mismatch.");
- return addConstructedEdge(EdgeEntry(n1Id, n2Id, costs));
+ return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs));
}
/// \brief Get the number of nodes in the graph.
/// @return Number of nodes in the graph.
- unsigned getNumNodes() const { return nodes.size() - freeNodes.size(); }
+ unsigned getNumNodes() const { return numNodes; }
/// \brief Get the number of edges in the graph.
/// @return Number of edges in the graph.
- unsigned getNumEdges() const { return edges.size() - freeEdges.size(); }
+ unsigned getNumEdges() const { return numEdges; }
/// \brief Get a node's cost vector.
/// @param nItr Node iterator.
/// @return Node cost vector.
- Vector& getNodeCosts(NodeId nId) { return getNode(nId).getCosts(); }
+ Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
/// \brief Get a node's cost vector (const version).
/// @param nItr Node iterator.
/// @return Node cost vector.
- const Vector& getNodeCosts(NodeId nId) const {
- return getNode(nId).getCosts();
+ const Vector& getNodeCosts(ConstNodeItr nItr) const {
+ return getNode(nItr).getCosts();
}
/// \brief Set a node's data pointer.
@@ -268,23 +211,23 @@ namespace PBQP {
/// @param data Pointer to node data.
///
/// Typically used by a PBQP solver to attach data to aid in solution.
- void setNodeData(NodeId nId, void *data) { getNode(nId).setData(data); }
+ void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
/// \brief Get the node's data pointer.
/// @param nItr Node iterator.
/// @return Pointer to node data.
- void* getNodeData(NodeId nId) { return getNode(nId).getData(); }
+ void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
/// \brief Get an edge's cost matrix.
/// @param eItr Edge iterator.
/// @return Edge cost matrix.
- Matrix& getEdgeCosts(EdgeId eId) { return getEdge(eId).getCosts(); }
+ Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
/// \brief Get an edge's cost matrix (const version).
/// @param eItr Edge iterator.
/// @return Edge cost matrix.
- const Matrix& getEdgeCosts(EdgeId eId) const {
- return getEdge(eId).getCosts();
+ const Matrix& getEdgeCosts(ConstEdgeItr eItr) const {
+ return getEdge(eItr).getCosts();
}
/// \brief Set an edge's data pointer.
@@ -292,120 +235,124 @@ namespace PBQP {
/// @param data Pointer to edge data.
///
/// Typically used by a PBQP solver to attach data to aid in solution.
- void setEdgeData(EdgeId eId, void *data) { getEdge(eId).setData(data); }
+ void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
/// \brief Get an edge's data pointer.
/// @param eItr Edge iterator.
/// @return Pointer to edge data.
- void* getEdgeData(EdgeId eId) { return getEdge(eId).getData(); }
+ void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
/// \brief Get a node's degree.
/// @param nItr Node iterator.
/// @return The degree of the node.
- unsigned getNodeDegree(NodeId nId) const {
- return getNode(nId).getDegree();
+ unsigned getNodeDegree(NodeItr nItr) const {
+ return getNode(nItr).getDegree();
}
/// \brief Begin iterator for node set.
- NodeItr nodesBegin() const { return NodeItr(0, *this); }
+ NodeItr nodesBegin() { return nodes.begin(); }
+
+ /// \brief Begin const iterator for node set.
+ ConstNodeItr nodesBegin() const { return nodes.begin(); }
/// \brief End iterator for node set.
- NodeItr nodesEnd() const { return NodeItr(nodes.size(), *this); }
+ NodeItr nodesEnd() { return nodes.end(); }
+
+ /// \brief End const iterator for node set.
+ ConstNodeItr nodesEnd() const { return nodes.end(); }
/// \brief Begin iterator for edge set.
- EdgeItr edgesBegin() const { return EdgeItr(0, *this); }
+ EdgeItr edgesBegin() { return edges.begin(); }
/// \brief End iterator for edge set.
- EdgeItr edgesEnd() const { return EdgeItr(edges.size(), *this); }
+ EdgeItr edgesEnd() { return edges.end(); }
/// \brief Get begin iterator for adjacent edge set.
/// @param nItr Node iterator.
/// @return Begin iterator for the set of edges connected to the given node.
- AdjEdgeItr adjEdgesBegin(NodeId nId) {
- return getNode(nId).edgesBegin();
+ AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
+ return getNode(nItr).edgesBegin();
}
/// \brief Get end iterator for adjacent edge set.
/// @param nItr Node iterator.
/// @return End iterator for the set of edges connected to the given node.
- AdjEdgeItr adjEdgesEnd(NodeId nId) {
- return getNode(nId).edgesEnd();
+ AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
+ return getNode(nItr).edgesEnd();
}
/// \brief Get the first node connected to this edge.
/// @param eItr Edge iterator.
/// @return The first node connected to the given edge.
- NodeId getEdgeNode1(EdgeId eId) {
- return getEdge(eId).getNode1();
+ NodeItr getEdgeNode1(EdgeItr eItr) {
+ return getEdge(eItr).getNode1();
}
/// \brief Get the second node connected to this edge.
/// @param eItr Edge iterator.
/// @return The second node connected to the given edge.
- NodeId getEdgeNode2(EdgeId eId) {
- return getEdge(eId).getNode2();
+ NodeItr getEdgeNode2(EdgeItr eItr) {
+ return getEdge(eItr).getNode2();
}
/// \brief Get the "other" node connected to this edge.
/// @param eItr Edge iterator.
/// @param nItr Node iterator for the "given" node.
/// @return The iterator for the "other" node connected to this edge.
- NodeId getEdgeOtherNode(EdgeId eId, NodeId nId) {
- EdgeEntry &e = getEdge(eId);
- if (e.getNode1() == nId) {
+ NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
+ EdgeEntry &e = getEdge(eItr);
+ if (e.getNode1() == nItr) {
return e.getNode2();
} // else
return e.getNode1();
}
- EdgeId invalidEdgeId() const {
- return std::numeric_limits<EdgeVector::size_type>::max();
- }
-
/// \brief Get the edge connecting two nodes.
- /// @param n1Id First node id.
- /// @param n2Id Second node id.
- /// @return An id for edge (n1Id, n2Id) if such an edge exists,
- /// otherwise returns an invalid edge id.
- EdgeId findEdge(NodeId n1Id, NodeId n2Id) {
- for (AdjEdgeItr aeItr = adjEdgesBegin(n1Id), aeEnd = adjEdgesEnd(n1Id);
+ /// @param n1Itr First node iterator.
+ /// @param n2Itr Second node iterator.
+ /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
+ /// otherwise returns edgesEnd().
+ EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
+ for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
aeItr != aeEnd; ++aeItr) {
- if ((getEdgeNode1(*aeItr) == n2Id) ||
- (getEdgeNode2(*aeItr) == n2Id)) {
+ if ((getEdgeNode1(*aeItr) == n2Itr) ||
+ (getEdgeNode2(*aeItr) == n2Itr)) {
return *aeItr;
}
}
- return invalidEdgeId();
+ return edges.end();
}
/// \brief Remove a node from the graph.
- /// @param nItr Node id.
- void removeNode(NodeId nId) {
- NodeEntry &n = getNode(nId);
- for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end; ++itr) {
- EdgeId eId = *itr;
- removeEdge(eId);
+ /// @param nItr Node iterator.
+ void removeNode(NodeItr nItr) {
+ NodeEntry &n = getNode(nItr);
+ for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
+ EdgeItr eItr = *itr;
+ ++itr;
+ removeEdge(eItr);
}
- freeNodes.push_back(nId);
+ nodes.erase(nItr);
+ --numNodes;
}
/// \brief Remove an edge from the graph.
/// @param eItr Edge iterator.
- void removeEdge(EdgeId eId) {
- EdgeEntry &e = getEdge(eId);
+ void removeEdge(EdgeItr eItr) {
+ EdgeEntry &e = getEdge(eItr);
NodeEntry &n1 = getNode(e.getNode1());
NodeEntry &n2 = getNode(e.getNode2());
n1.removeEdge(e.getNode1AEItr());
n2.removeEdge(e.getNode2AEItr());
- freeEdges.push_back(eId);
+ edges.erase(eItr);
+ --numEdges;
}
/// \brief Remove all nodes and edges from the graph.
void clear() {
nodes.clear();
- freeNodes.clear();
edges.clear();
- freeEdges.clear();
+ numNodes = numEdges = 0;
}
/// \brief Dump a graph to an output stream.
@@ -415,7 +362,7 @@ namespace PBQP {
for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
nodeItr != nodeEnd; ++nodeItr) {
- const Vector& v = getNodeCosts(*nodeItr);
+ const Vector& v = getNodeCosts(nodeItr);
os << "\n" << v.getLength() << "\n";
assert(v.getLength() != 0 && "Empty vector in graph.");
os << v[0];
@@ -427,10 +374,10 @@ namespace PBQP {
for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
edgeItr != edgeEnd; ++edgeItr) {
- NodeId n1 = getEdgeNode1(*edgeItr);
- NodeId n2 = getEdgeNode2(*edgeItr);
+ unsigned n1 = std::distance(nodesBegin(), getEdgeNode1(edgeItr));
+ unsigned n2 = std::distance(nodesBegin(), getEdgeNode2(edgeItr));
assert(n1 != n2 && "PBQP graphs shound not have self-edges.");
- const Matrix& m = getEdgeCosts(*edgeItr);
+ const Matrix& m = getEdgeCosts(edgeItr);
os << "\n" << n1 << " " << n2 << "\n"
<< m.getRows() << " " << m.getCols() << "\n";
assert(m.getRows() != 0 && "No rows in matrix.");
@@ -456,7 +403,7 @@ namespace PBQP {
nodeItr != nodeEnd; ++nodeItr) {
os << " node" << nodeItr << " [ label=\""
- << nodeItr << ": " << getNodeCosts(*nodeItr) << "\" ]\n";
+ << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
}
os << " edge [ len=" << getNumNodes() << " ]\n";
@@ -464,11 +411,11 @@ namespace PBQP {
for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
edgeItr != edgeEnd; ++edgeItr) {
- os << " node" << getEdgeNode1(*edgeItr)
- << " -- node" << getEdgeNode2(*edgeItr)
+ os << " node" << getEdgeNode1(edgeItr)
+ << " -- node" << getEdgeNode2(edgeItr)
<< " [ label=\"";
- const Matrix &edgeCosts = getEdgeCosts(*edgeItr);
+ const Matrix &edgeCosts = getEdgeCosts(edgeItr);
for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
os << edgeCosts.getRowAsVector(i) << "\\n";
@@ -480,16 +427,39 @@ namespace PBQP {
};
-// void Graph::copyFrom(const Graph &other) {
-// std::map<Graph::ConstNodeItr, Graph::NodeItr,
-// NodeItrComparator> nodeMap;
+ class NodeItrComparator {
+ public:
+ bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
+ return &*n1 < &*n2;
+ }
+
+ bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const {
+ return &*n1 < &*n2;
+ }
+ };
+
+ class EdgeItrCompartor {
+ public:
+ bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
+ return &*e1 < &*e2;
+ }
+
+ bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const {
+ return &*e1 < &*e2;
+ }
+ };
+
+ void Graph::copyFrom(const Graph &other) {
+ std::map<Graph::ConstNodeItr, Graph::NodeItr,
+ NodeItrComparator> nodeMap;
-// for (Graph::ConstNodeItr nItr = other.nodesBegin(),
-// nEnd = other.nodesEnd();
-// nItr != nEnd; ++nItr) {
-// nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
-// }
-// }
+ for (Graph::ConstNodeItr nItr = other.nodesBegin(),
+ nEnd = other.nodesEnd();
+ nItr != nEnd; ++nItr) {
+ nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
+ }
+
+ }
}
diff --git a/include/llvm/CodeGen/PBQP/HeuristicBase.h b/include/llvm/CodeGen/PBQP/HeuristicBase.h
index 36d94d6..0c1fcb7 100644
--- a/include/llvm/CodeGen/PBQP/HeuristicBase.h
+++ b/include/llvm/CodeGen/PBQP/HeuristicBase.h
@@ -52,7 +52,7 @@ namespace PBQP {
class HeuristicBase {
private:
- typedef std::list<Graph::NodeId> OptimalList;
+ typedef std::list<Graph::NodeItr> OptimalList;
HeuristicSolverImpl<HImpl> &s;
Graph &g;
@@ -63,8 +63,8 @@ namespace PBQP {
// Add the given node to the optimal reductions list. Keep an iterator to
// its location for fast removal.
- void addToOptimalReductionList(Graph::NodeId nId) {
- optimalList.insert(optimalList.end(), nId);
+ void addToOptimalReductionList(Graph::NodeItr nItr) {
+ optimalList.insert(optimalList.end(), nItr);
}
public:
@@ -105,8 +105,8 @@ namespace PBQP {
/// criteria. Note however that your criteria for selecting optimal nodes
/// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or
/// higher should not be selected under any circumstances.
- bool shouldOptimallyReduce(Graph::NodeId nId) {
- if (g.getNodeDegree(nId) < 3)
+ bool shouldOptimallyReduce(Graph::NodeItr nItr) {
+ if (g.getNodeDegree(nItr) < 3)
return true;
// else
return false;
@@ -118,8 +118,8 @@ namespace PBQP {
/// You probably don't want to over-ride this, except perhaps to record
/// statistics before calling this implementation. HeuristicBase relies on
/// its behaviour.
- void addToOptimalReduceList(Graph::NodeId nId) {
- optimalList.push_back(nId);
+ void addToOptimalReduceList(Graph::NodeItr nItr) {
+ optimalList.push_back(nItr);
}
/// \brief Initialise the heuristic.
@@ -132,10 +132,10 @@ namespace PBQP {
void setup() {
for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
nItr != nEnd; ++nItr) {
- if (impl().shouldOptimallyReduce(*nItr)) {
- addToOptimalReduceList(*nItr);
+ if (impl().shouldOptimallyReduce(nItr)) {
+ addToOptimalReduceList(nItr);
} else {
- impl().addToHeuristicReduceList(*nItr);
+ impl().addToHeuristicReduceList(nItr);
}
}
}
@@ -150,13 +150,13 @@ namespace PBQP {
if (optimalList.empty())
return false;
- Graph::NodeId nId = optimalList.front();
+ Graph::NodeItr nItr = optimalList.front();
optimalList.pop_front();
- switch (s.getSolverDegree(nId)) {
- case 0: s.applyR0(nId); break;
- case 1: s.applyR1(nId); break;
- case 2: s.applyR2(nId); break;
+ switch (s.getSolverDegree(nItr)) {
+ case 0: s.applyR0(nItr); break;
+ case 1: s.applyR1(nItr); break;
+ case 2: s.applyR2(nItr); break;
default: llvm_unreachable(
"Optimal reductions of degree > 2 nodes is invalid.");
}
@@ -185,7 +185,7 @@ namespace PBQP {
/// \brief Add a node to the heuristic reduce list.
/// @param nItr Node iterator to add to the heuristic reduce list.
- void addToHeuristicList(Graph::NodeId nId) {
+ void addToHeuristicList(Graph::NodeItr nItr) {
llvm_unreachable("Must be implemented in derived class.");
}
@@ -200,19 +200,19 @@ namespace PBQP {
/// \brief Prepare a change in the costs on the given edge.
/// @param eItr Edge iterator.
- void preUpdateEdgeCosts(Graph::EdgeId eId) {
+ void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
llvm_unreachable("Must be implemented in derived class.");
}
/// \brief Handle the change in the costs on the given edge.
/// @param eItr Edge iterator.
- void postUpdateEdgeCostts(Graph::EdgeId eId) {
+ void postUpdateEdgeCostts(Graph::EdgeItr eItr) {
llvm_unreachable("Must be implemented in derived class.");
}
/// \brief Handle the addition of a new edge into the PBQP graph.
/// @param eItr Edge iterator for the added edge.
- void handleAddEdge(Graph::EdgeId eId) {
+ void handleAddEdge(Graph::EdgeItr eItr) {
llvm_unreachable("Must be implemented in derived class.");
}
@@ -223,7 +223,7 @@ namespace PBQP {
/// Edges are frequently removed due to the removal of a node. This
/// method allows for the effect to be computed only for the remaining
/// node in the graph.
- void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) {
+ void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
llvm_unreachable("Must be implemented in derived class.");
}
diff --git a/include/llvm/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h
index 7fa6386..47e15b2 100644
--- a/include/llvm/CodeGen/PBQP/HeuristicSolver.h
+++ b/include/llvm/CodeGen/PBQP/HeuristicSolver.h
@@ -40,7 +40,7 @@ namespace PBQP {
typedef typename HImpl::NodeData HeuristicNodeData;
typedef typename HImpl::EdgeData HeuristicEdgeData;
- typedef std::list<Graph::EdgeId> SolverEdges;
+ typedef std::list<Graph::EdgeItr> SolverEdges;
public:
@@ -55,9 +55,9 @@ namespace PBQP {
HeuristicNodeData& getHeuristicData() { return hData; }
- SolverEdgeItr addSolverEdge(Graph::EdgeId eId) {
+ SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) {
++solverDegree;
- return solverEdges.insert(solverEdges.end(), eId);
+ return solverEdges.insert(solverEdges.end(), eItr);
}
void removeSolverEdge(SolverEdgeItr seItr) {
@@ -104,7 +104,7 @@ namespace PBQP {
Graph &g;
HImpl h;
Solution s;
- std::vector<Graph::NodeId> stack;
+ std::vector<Graph::NodeItr> stack;
typedef std::list<NodeData> NodeDataList;
NodeDataList nodeDataList;
@@ -127,15 +127,15 @@ namespace PBQP {
/// \brief Get the heuristic data attached to the given node.
/// @param nItr Node iterator.
/// @return The heuristic data attached to the given node.
- HeuristicNodeData& getHeuristicNodeData(Graph::NodeId nId) {
- return getSolverNodeData(nId).getHeuristicData();
+ HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
+ return getSolverNodeData(nItr).getHeuristicData();
}
/// \brief Get the heuristic data attached to the given edge.
/// @param eItr Edge iterator.
/// @return The heuristic data attached to the given node.
- HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeId eId) {
- return getSolverEdgeData(eId).getHeuristicData();
+ HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
+ return getSolverEdgeData(eItr).getHeuristicData();
}
/// \brief Begin iterator for the set of edges adjacent to the given node in
@@ -143,8 +143,8 @@ namespace PBQP {
/// @param nItr Node iterator.
/// @return Begin iterator for the set of edges adjacent to the given node
/// in the solver graph.
- SolverEdgeItr solverEdgesBegin(Graph::NodeId nId) {
- return getSolverNodeData(nId).solverEdgesBegin();
+ SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) {
+ return getSolverNodeData(nItr).solverEdgesBegin();
}
/// \brief End iterator for the set of edges adjacent to the given node in
@@ -152,8 +152,8 @@ namespace PBQP {
/// @param nItr Node iterator.
/// @return End iterator for the set of edges adjacent to the given node in
/// the solver graph.
- SolverEdgeItr solverEdgesEnd(Graph::NodeId nId) {
- return getSolverNodeData(nId).solverEdgesEnd();
+ SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) {
+ return getSolverNodeData(nItr).solverEdgesEnd();
}
/// \brief Remove a node from the solver graph.
@@ -161,10 +161,10 @@ namespace PBQP {
///
/// Does <i>not</i> notify the heuristic of the removal. That should be
/// done manually if necessary.
- void removeSolverEdge(Graph::EdgeId eId) {
- EdgeData &eData = getSolverEdgeData(eId);
- NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)),
- &n2Data = getSolverNodeData(g.getEdgeNode2(eId));
+ void removeSolverEdge(Graph::EdgeItr eItr) {
+ EdgeData &eData = getSolverEdgeData(eItr);
+ NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
+ &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
n1Data.removeSolverEdge(eData.getN1SolverEdgeItr());
n2Data.removeSolverEdge(eData.getN2SolverEdgeItr());
@@ -189,30 +189,30 @@ namespace PBQP {
/// \brief Add to the end of the stack.
/// @param nItr Node iterator to add to the reduction stack.
- void pushToStack(Graph::NodeId nId) {
- getSolverNodeData(nId).clearSolverEdges();
- stack.push_back(nId);
+ void pushToStack(Graph::NodeItr nItr) {
+ getSolverNodeData(nItr).clearSolverEdges();
+ stack.push_back(nItr);
}
/// \brief Returns the solver degree of the given node.
/// @param nItr Node iterator for which degree is requested.
/// @return Node degree in the <i>solver</i> graph (not the original graph).
- unsigned getSolverDegree(Graph::NodeId nId) {
- return getSolverNodeData(nId).getSolverDegree();
+ unsigned getSolverDegree(Graph::NodeItr nItr) {
+ return getSolverNodeData(nItr).getSolverDegree();
}
/// \brief Set the solution of the given node.
/// @param nItr Node iterator to set solution for.
/// @param selection Selection for node.
- void setSolution(const Graph::NodeId &nId, unsigned selection) {
- s.setSelection(nId, selection);
+ void setSolution(const Graph::NodeItr &nItr, unsigned selection) {
+ s.setSelection(nItr, selection);
- for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId),
- aeEnd = g.adjEdgesEnd(nId);
+ for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
+ aeEnd = g.adjEdgesEnd(nItr);
aeItr != aeEnd; ++aeItr) {
- Graph::EdgeId eId(*aeItr);
- Graph::NodeId anId(g.getEdgeOtherNode(eId, nId));
- getSolverNodeData(anId).addSolverEdge(eId);
+ Graph::EdgeItr eItr(*aeItr);
+ Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr));
+ getSolverNodeData(anItr).addSolverEdge(eItr);
}
}
@@ -220,12 +220,12 @@ namespace PBQP {
/// @param nItr Node iterator for node to apply R0 to.
///
/// Node will be automatically pushed to the solver stack.
- void applyR0(Graph::NodeId nId) {
- assert(getSolverNodeData(nId).getSolverDegree() == 0 &&
+ void applyR0(Graph::NodeItr nItr) {
+ assert(getSolverNodeData(nItr).getSolverDegree() == 0 &&
"R0 applied to node with degree != 0.");
// Nothing to do. Just push the node onto the reduction stack.
- pushToStack(nId);
+ pushToStack(nItr);
s.recordR0();
}
@@ -234,20 +234,20 @@ namespace PBQP {
/// @param xnItr Node iterator for node to apply R1 to.
///
/// Node will be automatically pushed to the solver stack.
- void applyR1(Graph::NodeId xnId) {
- NodeData &nd = getSolverNodeData(xnId);
+ void applyR1(Graph::NodeItr xnItr) {
+ NodeData &nd = getSolverNodeData(xnItr);
assert(nd.getSolverDegree() == 1 &&
"R1 applied to node with degree != 1.");
- Graph::EdgeId eId = *nd.solverEdgesBegin();
+ Graph::EdgeItr eItr = *nd.solverEdgesBegin();
- const Matrix &eCosts = g.getEdgeCosts(eId);
- const Vector &xCosts = g.getNodeCosts(xnId);
+ const Matrix &eCosts = g.getEdgeCosts(eItr);
+ const Vector &xCosts = g.getNodeCosts(xnItr);
// Duplicate a little to avoid transposing matrices.
- if (xnId == g.getEdgeNode1(eId)) {
- Graph::NodeId ynId = g.getEdgeNode2(eId);
- Vector &yCosts = g.getNodeCosts(ynId);
+ if (xnItr == g.getEdgeNode1(eItr)) {
+ Graph::NodeItr ynItr = g.getEdgeNode2(eItr);
+ Vector &yCosts = g.getNodeCosts(ynItr);
for (unsigned j = 0; j < yCosts.getLength(); ++j) {
PBQPNum min = eCosts[0][j] + xCosts[0];
for (unsigned i = 1; i < xCosts.getLength(); ++i) {
@@ -257,10 +257,10 @@ namespace PBQP {
}
yCosts[j] += min;
}
- h.handleRemoveEdge(eId, ynId);
+ h.handleRemoveEdge(eItr, ynItr);
} else {
- Graph::NodeId ynId = g.getEdgeNode1(eId);
- Vector &yCosts = g.getNodeCosts(ynId);
+ Graph::NodeItr ynItr = g.getEdgeNode1(eItr);
+ Vector &yCosts = g.getNodeCosts(ynItr);
for (unsigned i = 0; i < yCosts.getLength(); ++i) {
PBQPNum min = eCosts[i][0] + xCosts[0];
for (unsigned j = 1; j < xCosts.getLength(); ++j) {
@@ -270,12 +270,12 @@ namespace PBQP {
}
yCosts[i] += min;
}
- h.handleRemoveEdge(eId, ynId);
+ h.handleRemoveEdge(eItr, ynItr);
}
- removeSolverEdge(eId);
+ removeSolverEdge(eItr);
assert(nd.getSolverDegree() == 0 &&
"Degree 1 with edge removed should be 0.");
- pushToStack(xnId);
+ pushToStack(xnItr);
s.recordR1();
}
@@ -283,30 +283,30 @@ namespace PBQP {
/// @param xnItr Node iterator for node to apply R2 to.
///
/// Node will be automatically pushed to the solver stack.
- void applyR2(Graph::NodeId xnId) {
- assert(getSolverNodeData(xnId).getSolverDegree() == 2 &&
+ void applyR2(Graph::NodeItr xnItr) {
+ assert(getSolverNodeData(xnItr).getSolverDegree() == 2 &&
"R2 applied to node with degree != 2.");
- NodeData &nd = getSolverNodeData(xnId);
- const Vector &xCosts = g.getNodeCosts(xnId);
+ NodeData &nd = getSolverNodeData(xnItr);
+ const Vector &xCosts = g.getNodeCosts(xnItr);
SolverEdgeItr aeItr = nd.solverEdgesBegin();
- Graph::EdgeId yxeId = *aeItr,
- zxeId = *(++aeItr);
+ Graph::EdgeItr yxeItr = *aeItr,
+ zxeItr = *(++aeItr);
- Graph::NodeId ynId = g.getEdgeOtherNode(yxeId, xnId),
- znId = g.getEdgeOtherNode(zxeId, xnId);
+ Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr),
+ znItr = g.getEdgeOtherNode(zxeItr, xnItr);
- bool flipEdge1 = (g.getEdgeNode1(yxeId) == xnId),
- flipEdge2 = (g.getEdgeNode1(zxeId) == xnId);
+ bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr),
+ flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr);
const Matrix *yxeCosts = flipEdge1 ?
- new Matrix(g.getEdgeCosts(yxeId).transpose()) :
- &g.getEdgeCosts(yxeId);
+ new Matrix(g.getEdgeCosts(yxeItr).transpose()) :
+ &g.getEdgeCosts(yxeItr);
const Matrix *zxeCosts = flipEdge2 ?
- new Matrix(g.getEdgeCosts(zxeId).transpose()) :
- &g.getEdgeCosts(zxeId);
+ new Matrix(g.getEdgeCosts(zxeItr).transpose()) :
+ &g.getEdgeCosts(zxeItr);
unsigned xLen = xCosts.getLength(),
yLen = yxeCosts->getRows(),
@@ -333,27 +333,27 @@ namespace PBQP {
if (flipEdge2)
delete zxeCosts;
- Graph::EdgeId yzeId = g.findEdge(ynId, znId);
+ Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr);
bool addedEdge = false;
- if (yzeId == g.invalidEdgeId()) {
- yzeId = g.addEdge(ynId, znId, delta);
+ if (yzeItr == g.edgesEnd()) {
+ yzeItr = g.addEdge(ynItr, znItr, delta);
addedEdge = true;
} else {
- Matrix &yzeCosts = g.getEdgeCosts(yzeId);
- h.preUpdateEdgeCosts(yzeId);
- if (ynId == g.getEdgeNode1(yzeId)) {
+ Matrix &yzeCosts = g.getEdgeCosts(yzeItr);
+ h.preUpdateEdgeCosts(yzeItr);
+ if (ynItr == g.getEdgeNode1(yzeItr)) {
yzeCosts += delta;
} else {
yzeCosts += delta.transpose();
}
}
- bool nullCostEdge = tryNormaliseEdgeMatrix(yzeId);
+ bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr);
if (!addedEdge) {
// If we modified the edge costs let the heuristic know.
- h.postUpdateEdgeCosts(yzeId);
+ h.postUpdateEdgeCosts(yzeItr);
}
if (nullCostEdge) {
@@ -361,26 +361,26 @@ namespace PBQP {
if (!addedEdge) {
// We didn't just add it, so we need to notify the heuristic
// and remove it from the solver.
- h.handleRemoveEdge(yzeId, ynId);
- h.handleRemoveEdge(yzeId, znId);
- removeSolverEdge(yzeId);
+ h.handleRemoveEdge(yzeItr, ynItr);
+ h.handleRemoveEdge(yzeItr, znItr);
+ removeSolverEdge(yzeItr);
}
- g.removeEdge(yzeId);
+ g.removeEdge(yzeItr);
} else if (addedEdge) {
// If the edge was added, and non-null, finish setting it up, add it to
// the solver & notify heuristic.
edgeDataList.push_back(EdgeData());
- g.setEdgeData(yzeId, &edgeDataList.back());
- addSolverEdge(yzeId);
- h.handleAddEdge(yzeId);
+ g.setEdgeData(yzeItr, &edgeDataList.back());
+ addSolverEdge(yzeItr);
+ h.handleAddEdge(yzeItr);
}
- h.handleRemoveEdge(yxeId, ynId);
- removeSolverEdge(yxeId);
- h.handleRemoveEdge(zxeId, znId);
- removeSolverEdge(zxeId);
+ h.handleRemoveEdge(yxeItr, ynItr);
+ removeSolverEdge(yxeItr);
+ h.handleRemoveEdge(zxeItr, znItr);
+ removeSolverEdge(zxeItr);
- pushToStack(xnId);
+ pushToStack(xnItr);
s.recordR2();
}
@@ -391,21 +391,21 @@ namespace PBQP {
private:
- NodeData& getSolverNodeData(Graph::NodeId nId) {
- return *static_cast<NodeData*>(g.getNodeData(nId));
+ NodeData& getSolverNodeData(Graph::NodeItr nItr) {
+ return *static_cast<NodeData*>(g.getNodeData(nItr));
}
- EdgeData& getSolverEdgeData(Graph::EdgeId eId) {
- return *static_cast<EdgeData*>(g.getEdgeData(eId));
+ EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) {
+ return *static_cast<EdgeData*>(g.getEdgeData(eItr));
}
- void addSolverEdge(Graph::EdgeId eId) {
- EdgeData &eData = getSolverEdgeData(eId);
- NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)),
- &n2Data = getSolverNodeData(g.getEdgeNode2(eId));
+ void addSolverEdge(Graph::EdgeItr eItr) {
+ EdgeData &eData = getSolverEdgeData(eItr);
+ NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
+ &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
- eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eId));
- eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eId));
+ eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr));
+ eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr));
}
void setup() {
@@ -417,15 +417,15 @@ namespace PBQP {
for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
nItr != nEnd; ++nItr) {
nodeDataList.push_back(NodeData());
- g.setNodeData(*nItr, &nodeDataList.back());
+ g.setNodeData(nItr, &nodeDataList.back());
}
// Create edge data objects.
for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
eItr != eEnd; ++eItr) {
edgeDataList.push_back(EdgeData());
- g.setEdgeData(*eItr, &edgeDataList.back());
- addSolverEdge(*eItr);
+ g.setEdgeData(eItr, &edgeDataList.back());
+ addSolverEdge(eItr);
}
}
@@ -441,30 +441,28 @@ namespace PBQP {
for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
nItr != nEnd; ++nItr) {
- Graph::NodeId nId = *nItr;
+ if (g.getNodeCosts(nItr).getLength() == 1) {
- if (g.getNodeCosts(nId).getLength() == 1) {
+ std::vector<Graph::EdgeItr> edgesToRemove;
- std::vector<Graph::EdgeId> edgesToRemove;
-
- for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId),
- aeEnd = g.adjEdgesEnd(nId);
+ for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
+ aeEnd = g.adjEdgesEnd(nItr);
aeItr != aeEnd; ++aeItr) {
- Graph::EdgeId eId = *aeItr;
+ Graph::EdgeItr eItr = *aeItr;
- if (g.getEdgeNode1(eId) == nId) {
- Graph::NodeId otherNodeId = g.getEdgeNode2(eId);
- g.getNodeCosts(otherNodeId) +=
- g.getEdgeCosts(eId).getRowAsVector(0);
+ if (g.getEdgeNode1(eItr) == nItr) {
+ Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr);
+ g.getNodeCosts(otherNodeItr) +=
+ g.getEdgeCosts(eItr).getRowAsVector(0);
}
else {
- Graph::NodeId otherNodeId = g.getEdgeNode1(eId);
- g.getNodeCosts(otherNodeId) +=
- g.getEdgeCosts(eId).getColAsVector(0);
+ Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr);
+ g.getNodeCosts(otherNodeItr) +=
+ g.getEdgeCosts(eItr).getColAsVector(0);
}
- edgesToRemove.push_back(eId);
+ edgesToRemove.push_back(eItr);
}
if (!edgesToRemove.empty())
@@ -479,12 +477,12 @@ namespace PBQP {
}
void eliminateIndependentEdges() {
- std::vector<Graph::EdgeId> edgesToProcess;
+ std::vector<Graph::EdgeItr> edgesToProcess;
unsigned numEliminated = 0;
for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
eItr != eEnd; ++eItr) {
- edgesToProcess.push_back(*eItr);
+ edgesToProcess.push_back(eItr);
}
while (!edgesToProcess.empty()) {
@@ -494,21 +492,21 @@ namespace PBQP {
}
}
- bool tryToEliminateEdge(Graph::EdgeId eId) {
- if (tryNormaliseEdgeMatrix(eId)) {
- g.removeEdge(eId);
+ bool tryToEliminateEdge(Graph::EdgeItr eItr) {
+ if (tryNormaliseEdgeMatrix(eItr)) {
+ g.removeEdge(eItr);
return true;
}
return false;
}
- bool tryNormaliseEdgeMatrix(Graph::EdgeId &eId) {
+ bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) {
const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity();
- Matrix &edgeCosts = g.getEdgeCosts(eId);
- Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eId)),
- &vCosts = g.getNodeCosts(g.getEdgeNode2(eId));
+ 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 = infinity;
@@ -556,34 +554,34 @@ namespace PBQP {
}
}
- void computeSolution(Graph::NodeId nId) {
+ void computeSolution(Graph::NodeItr nItr) {
- NodeData &nodeData = getSolverNodeData(nId);
+ NodeData &nodeData = getSolverNodeData(nItr);
- Vector v(g.getNodeCosts(nId));
+ Vector v(g.getNodeCosts(nItr));
// Solve based on existing solved edges.
for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(),
solvedEdgeEnd = nodeData.solverEdgesEnd();
solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) {
- Graph::EdgeId eId(*solvedEdgeItr);
- Matrix &edgeCosts = g.getEdgeCosts(eId);
+ Graph::EdgeItr eItr(*solvedEdgeItr);
+ Matrix &edgeCosts = g.getEdgeCosts(eItr);
- if (nId == g.getEdgeNode1(eId)) {
- Graph::NodeId adjNode(g.getEdgeNode2(eId));
+ if (nItr == g.getEdgeNode1(eItr)) {
+ Graph::NodeItr adjNode(g.getEdgeNode2(eItr));
unsigned adjSolution = s.getSelection(adjNode);
v += edgeCosts.getColAsVector(adjSolution);
}
else {
- Graph::NodeId adjNode(g.getEdgeNode1(eId));
+ Graph::NodeItr adjNode(g.getEdgeNode1(eItr));
unsigned adjSolution = s.getSelection(adjNode);
v += edgeCosts.getRowAsVector(adjSolution);
}
}
- setSolution(nId, v.minIndex());
+ setSolution(nItr, v.minIndex());
}
void cleanup() {
diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
index 9663b26..307d81e 100644
--- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
+++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
@@ -47,8 +47,8 @@ namespace PBQP {
class LinkDegreeComparator {
public:
LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
- bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const {
- if (s->getSolverDegree(n1Id) > s->getSolverDegree(n2Id))
+ bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
+ if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
return true;
return false;
}
@@ -60,12 +60,12 @@ namespace PBQP {
public:
SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
: s(&s), g(&s.getGraph()) {}
- bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const {
- const PBQP::Vector &cv1 = g->getNodeCosts(n1Id);
- const PBQP::Vector &cv2 = g->getNodeCosts(n2Id);
+ bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
+ const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr);
+ const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr);
- PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Id);
- PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Id);
+ PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr);
+ PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr);
if (cost1 < cost2)
return true;
@@ -77,10 +77,10 @@ namespace PBQP {
Graph *g;
};
- typedef std::list<Graph::NodeId> RNAllocableList;
+ typedef std::list<Graph::NodeItr> RNAllocableList;
typedef RNAllocableList::iterator RNAllocableListItr;
- typedef std::list<Graph::NodeId> RNUnallocableList;
+ typedef std::list<Graph::NodeItr> RNUnallocableList;
typedef RNUnallocableList::iterator RNUnallocableListItr;
public:
@@ -123,8 +123,8 @@ namespace PBQP {
/// infinite are checked for allocability first. Allocable nodes may be
/// optimally reduced, but nodes whose allocability cannot be proven are
/// selected for heuristic reduction instead.
- bool shouldOptimallyReduce(Graph::NodeId nId) {
- if (getSolver().getSolverDegree(nId) < 3) {
+ bool shouldOptimallyReduce(Graph::NodeItr nItr) {
+ if (getSolver().getSolverDegree(nItr) < 3) {
return true;
}
// else
@@ -133,14 +133,14 @@ namespace PBQP {
/// \brief Add a node to the heuristic reduce list.
/// @param nItr Node iterator to add to the heuristic reduce list.
- void addToHeuristicReduceList(Graph::NodeId nId) {
- NodeData &nd = getHeuristicNodeData(nId);
- initializeNode(nId);
+ void addToHeuristicReduceList(Graph::NodeItr nItr) {
+ NodeData &nd = getHeuristicNodeData(nItr);
+ initializeNode(nItr);
nd.isHeuristic = true;
if (nd.isAllocable) {
- nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId);
+ nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
} else {
- nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nId);
+ nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
}
}
@@ -159,19 +159,19 @@ namespace PBQP {
RNAllocableListItr rnaItr =
min_element(rnAllocableList.begin(), rnAllocableList.end(),
LinkDegreeComparator(getSolver()));
- Graph::NodeId nId = *rnaItr;
+ Graph::NodeItr nItr = *rnaItr;
rnAllocableList.erase(rnaItr);
- handleRemoveNode(nId);
- getSolver().pushToStack(nId);
+ handleRemoveNode(nItr);
+ getSolver().pushToStack(nItr);
return true;
} else if (!rnUnallocableList.empty()) {
RNUnallocableListItr rnuItr =
min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
SpillCostComparator(getSolver()));
- Graph::NodeId nId = *rnuItr;
+ Graph::NodeItr nItr = *rnuItr;
rnUnallocableList.erase(rnuItr);
- handleRemoveNode(nId);
- getSolver().pushToStack(nId);
+ handleRemoveNode(nItr);
+ getSolver().pushToStack(nItr);
return true;
}
// else
@@ -180,28 +180,28 @@ namespace PBQP {
/// \brief Prepare a change in the costs on the given edge.
/// @param eItr Edge iterator.
- void preUpdateEdgeCosts(Graph::EdgeId eId) {
+ void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
Graph &g = getGraph();
- Graph::NodeId n1Id = g.getEdgeNode1(eId),
- n2Id = g.getEdgeNode2(eId);
- NodeData &n1 = getHeuristicNodeData(n1Id),
- &n2 = getHeuristicNodeData(n2Id);
+ Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
+ n2Itr = g.getEdgeNode2(eItr);
+ NodeData &n1 = getHeuristicNodeData(n1Itr),
+ &n2 = getHeuristicNodeData(n2Itr);
if (n1.isHeuristic)
- subtractEdgeContributions(eId, getGraph().getEdgeNode1(eId));
+ subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
if (n2.isHeuristic)
- subtractEdgeContributions(eId, getGraph().getEdgeNode2(eId));
+ subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));
- EdgeData &ed = getHeuristicEdgeData(eId);
+ EdgeData &ed = getHeuristicEdgeData(eItr);
ed.isUpToDate = false;
}
/// \brief Handle the change in the costs on the given edge.
/// @param eItr Edge iterator.
- void postUpdateEdgeCosts(Graph::EdgeId eId) {
+ void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
// This is effectively the same as adding a new edge now, since
// we've factored out the costs of the old one.
- handleAddEdge(eId);
+ handleAddEdge(eItr);
}
/// \brief Handle the addition of a new edge into the PBQP graph.
@@ -210,12 +210,12 @@ namespace PBQP {
/// Updates allocability of any nodes connected by this edge which are
/// being managed by the heuristic. If allocability changes they are
/// moved to the appropriate list.
- void handleAddEdge(Graph::EdgeId eId) {
+ void handleAddEdge(Graph::EdgeItr eItr) {
Graph &g = getGraph();
- Graph::NodeId n1Id = g.getEdgeNode1(eId),
- n2Id = g.getEdgeNode2(eId);
- NodeData &n1 = getHeuristicNodeData(n1Id),
- &n2 = getHeuristicNodeData(n2Id);
+ Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
+ n2Itr = g.getEdgeNode2(eItr);
+ NodeData &n1 = getHeuristicNodeData(n1Itr),
+ &n2 = getHeuristicNodeData(n2Itr);
// If neither node is managed by the heuristic there's nothing to be
// done.
@@ -223,29 +223,29 @@ namespace PBQP {
return;
// Ok - we need to update at least one node.
- computeEdgeContributions(eId);
+ computeEdgeContributions(eItr);
// Update node 1 if it's managed by the heuristic.
if (n1.isHeuristic) {
bool n1WasAllocable = n1.isAllocable;
- addEdgeContributions(eId, n1Id);
- updateAllocability(n1Id);
+ addEdgeContributions(eItr, n1Itr);
+ updateAllocability(n1Itr);
if (n1WasAllocable && !n1.isAllocable) {
rnAllocableList.erase(n1.rnaItr);
n1.rnuItr =
- rnUnallocableList.insert(rnUnallocableList.end(), n1Id);
+ rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
}
}
// Likewise for node 2.
if (n2.isHeuristic) {
bool n2WasAllocable = n2.isAllocable;
- addEdgeContributions(eId, n2Id);
- updateAllocability(n2Id);
+ addEdgeContributions(eItr, n2Itr);
+ updateAllocability(n2Itr);
if (n2WasAllocable && !n2.isAllocable) {
rnAllocableList.erase(n2.rnaItr);
n2.rnuItr =
- rnUnallocableList.insert(rnUnallocableList.end(), n2Id);
+ rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
}
}
}
@@ -256,27 +256,27 @@ namespace PBQP {
///
/// Updates allocability of the given node and, if appropriate, moves the
/// node to a new list.
- void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) {
- NodeData &nd =getHeuristicNodeData(nId);
+ void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+ NodeData &nd = getHeuristicNodeData(nItr);
// If the node is not managed by the heuristic there's nothing to be
// done.
if (!nd.isHeuristic)
return;
- EdgeData &ed = getHeuristicEdgeData(eId);
+ EdgeData &ed = getHeuristicEdgeData(eItr);
(void)ed;
assert(ed.isUpToDate && "Edge data is not up to date.");
// Update node.
bool ndWasAllocable = nd.isAllocable;
- subtractEdgeContributions(eId, nId);
- updateAllocability(nId);
+ subtractEdgeContributions(eItr, nItr);
+ updateAllocability(nItr);
// If the node has gone optimal...
- if (shouldOptimallyReduce(nId)) {
+ if (shouldOptimallyReduce(nItr)) {
nd.isHeuristic = false;
- addToOptimalReduceList(nId);
+ addToOptimalReduceList(nItr);
if (ndWasAllocable) {
rnAllocableList.erase(nd.rnaItr);
} else {
@@ -287,30 +287,30 @@ namespace PBQP {
// from "unallocable" to "allocable".
if (!ndWasAllocable && nd.isAllocable) {
rnUnallocableList.erase(nd.rnuItr);
- nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId);
+ nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
}
}
}
private:
- NodeData& getHeuristicNodeData(Graph::NodeId nId) {
- return getSolver().getHeuristicNodeData(nId);
+ NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
+ return getSolver().getHeuristicNodeData(nItr);
}
- EdgeData& getHeuristicEdgeData(Graph::EdgeId eId) {
- return getSolver().getHeuristicEdgeData(eId);
+ EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
+ return getSolver().getHeuristicEdgeData(eItr);
}
// Work out what this edge will contribute to the allocability of the
// nodes connected to it.
- void computeEdgeContributions(Graph::EdgeId eId) {
- EdgeData &ed = getHeuristicEdgeData(eId);
+ void computeEdgeContributions(Graph::EdgeItr eItr) {
+ EdgeData &ed = getHeuristicEdgeData(eItr);
if (ed.isUpToDate)
return; // Edge data is already up to date.
- Matrix &eCosts = getGraph().getEdgeCosts(eId);
+ Matrix &eCosts = getGraph().getEdgeCosts(eItr);
unsigned numRegs = eCosts.getRows() - 1,
numReverseRegs = eCosts.getCols() - 1;
@@ -352,15 +352,15 @@ namespace PBQP {
// numDenied and safe members. No action is taken other than to update
// these member values. Once updated these numbers can be used by clients
// to update the node's allocability.
- void addEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) {
- EdgeData &ed = getHeuristicEdgeData(eId);
+ void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+ EdgeData &ed = getHeuristicEdgeData(eItr);
assert(ed.isUpToDate && "Using out-of-date edge numbers.");
- NodeData &nd = getHeuristicNodeData(nId);
- unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
+ NodeData &nd = getHeuristicNodeData(nItr);
+ unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
- bool nIsNode1 = nId == getGraph().getEdgeNode1(eId);
+ bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
EdgeData::UnsafeArray &unsafe =
nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;
@@ -379,15 +379,15 @@ namespace PBQP {
// numDenied and safe members. No action is taken other than to update
// these member values. Once updated these numbers can be used by clients
// to update the node's allocability.
- void subtractEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) {
- EdgeData &ed = getHeuristicEdgeData(eId);
+ void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+ EdgeData &ed = getHeuristicEdgeData(eItr);
assert(ed.isUpToDate && "Using out-of-date edge numbers.");
- NodeData &nd = getHeuristicNodeData(nId);
- unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
+ NodeData &nd = getHeuristicNodeData(nItr);
+ unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
- bool nIsNode1 = nId == getGraph().getEdgeNode1(eId);
+ bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
EdgeData::UnsafeArray &unsafe =
nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;
@@ -402,22 +402,22 @@ namespace PBQP {
}
}
- void updateAllocability(Graph::NodeId nId) {
- NodeData &nd = getHeuristicNodeData(nId);
- unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
+ void updateAllocability(Graph::NodeItr nItr) {
+ NodeData &nd = getHeuristicNodeData(nItr);
+ unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0;
}
- void initializeNode(Graph::NodeId nId) {
- NodeData &nd = getHeuristicNodeData(nId);
+ void initializeNode(Graph::NodeItr nItr) {
+ NodeData &nd = getHeuristicNodeData(nItr);
if (nd.isInitialized)
return; // Node data is already up to date.
- unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
+ unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
nd.numDenied = 0;
- const Vector& nCosts = getGraph().getNodeCosts(nId);
+ const Vector& nCosts = getGraph().getNodeCosts(nItr);
for (unsigned i = 1; i < nCosts.getLength(); ++i) {
if (nCosts[i] == std::numeric_limits<PBQPNum>::infinity())
++nd.numDenied;
@@ -428,27 +428,27 @@ namespace PBQP {
typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
- for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nId),
- aeEnd = getSolver().solverEdgesEnd(nId);
+ for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
+ aeEnd = getSolver().solverEdgesEnd(nItr);
aeItr != aeEnd; ++aeItr) {
- Graph::EdgeId eId = *aeItr;
- computeEdgeContributions(eId);
- addEdgeContributions(eId, nId);
+ Graph::EdgeItr eItr = *aeItr;
+ computeEdgeContributions(eItr);
+ addEdgeContributions(eItr, nItr);
}
- updateAllocability(nId);
+ updateAllocability(nItr);
nd.isInitialized = true;
}
- void handleRemoveNode(Graph::NodeId xnId) {
+ void handleRemoveNode(Graph::NodeItr xnItr) {
typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
- std::vector<Graph::EdgeId> edgesToRemove;
- for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnId),
- aeEnd = getSolver().solverEdgesEnd(xnId);
+ std::vector<Graph::EdgeItr> edgesToRemove;
+ for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
+ aeEnd = getSolver().solverEdgesEnd(xnItr);
aeItr != aeEnd; ++aeItr) {
- Graph::NodeId ynId = getGraph().getEdgeOtherNode(*aeItr, xnId);
- handleRemoveEdge(*aeItr, ynId);
+ Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
+ handleRemoveEdge(*aeItr, ynItr);
edgesToRemove.push_back(*aeItr);
}
while (!edgesToRemove.empty()) {
diff --git a/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h
index 98ba5a1..b9f288b 100644
--- a/include/llvm/CodeGen/PBQP/Solution.h
+++ b/include/llvm/CodeGen/PBQP/Solution.h
@@ -26,7 +26,8 @@ namespace PBQP {
class Solution {
private:
- typedef std::map<Graph::NodeId, unsigned> SelectionsMap;
+ typedef std::map<Graph::ConstNodeItr, unsigned,
+ NodeItrComparator> SelectionsMap;
SelectionsMap selections;
unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions;
@@ -72,15 +73,15 @@ namespace PBQP {
/// \brief Set the selection for a given node.
/// @param nItr Node iterator.
/// @param selection Selection for nItr.
- void setSelection(Graph::NodeId nodeId, unsigned selection) {
- selections[nodeId] = selection;
+ void setSelection(Graph::NodeItr nItr, unsigned selection) {
+ selections[nItr] = selection;
}
/// \brief Get a node's selection.
/// @param nItr Node iterator.
/// @return The selection for nItr;
- unsigned getSelection(Graph::NodeId nodeId) const {
- SelectionsMap::const_iterator sItr = selections.find(nodeId);
+ unsigned getSelection(Graph::ConstNodeItr nItr) const {
+ SelectionsMap::const_iterator sItr = selections.find(nItr);
assert(sItr != selections.end() && "No selection for node.");
return sItr->second;
}
diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h
index 7472e5a..6f2d139 100644
--- a/include/llvm/CodeGen/RegAllocPBQP.h
+++ b/include/llvm/CodeGen/RegAllocPBQP.h
@@ -52,22 +52,22 @@ namespace llvm {
/// PBQPBuilder you are unlikely to need this: Nodes and options for all
/// vregs will already have been set up for you by the base class.
template <typename AllowedRegsItr>
- void recordVReg(unsigned vreg, PBQP::Graph::NodeId nodeId,
+ void recordVReg(unsigned vreg, PBQP::Graph::NodeItr node,
AllowedRegsItr arBegin, AllowedRegsItr arEnd) {
- assert(node2VReg.find(nodeId) == node2VReg.end() && "Re-mapping node.");
+ assert(node2VReg.find(node) == node2VReg.end() && "Re-mapping node.");
assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg.");
assert(allowedSets[vreg].empty() && "vreg already has pregs.");
- node2VReg[nodeId] = vreg;
- vreg2Node[vreg] = nodeId;
+ node2VReg[node] = vreg;
+ vreg2Node[vreg] = node;
std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg]));
}
/// Get the virtual register corresponding to the given PBQP node.
- unsigned getVRegForNode(PBQP::Graph::NodeId nodeId) const;
+ unsigned getVRegForNode(PBQP::Graph::ConstNodeItr node) const;
/// Get the PBQP node corresponding to the given virtual register.
- PBQP::Graph::NodeId getNodeForVReg(unsigned vreg) const;
+ PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const;
/// Returns true if the given PBQP option represents a physical register,
/// false otherwise.
@@ -92,8 +92,9 @@ namespace llvm {
private:
- typedef std::map<PBQP::Graph::NodeId, unsigned> Node2VReg;
- typedef DenseMap<unsigned, PBQP::Graph::NodeId> VReg2Node;
+ typedef std::map<PBQP::Graph::ConstNodeItr, unsigned,
+ PBQP::NodeItrComparator> Node2VReg;
+ typedef DenseMap<unsigned, PBQP::Graph::NodeItr> VReg2Node;
typedef DenseMap<unsigned, AllowedSet> AllowedSetMap;
PBQP::Graph graph;
generated by cgit v1.1 at 2024-12-23 17:27:59 +0000