Merge remote-tracking branch 'upstream/release_34' into merge-20140211

Conflicts:
	lib/Linker/LinkModules.cpp
	lib/Support/Unix/Signals.inc

Change-Id: Ia54f291fa5dc828052d2412736e8495c1282aa64

1 files changed, 105 insertions, 105 deletions

diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
index 307d81e..c355c2c 100644
--- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
+++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
@@ -27,7 +27,7 @@ namespace PBQP {
 
     /// \brief PBQP Heuristic which applies an allocability test based on
     ///        Briggs.
-    /// 
+    ///
     /// This heuristic assumes that the elements of cost vectors in the PBQP
     /// problem represent storage options, with the first being the spill
     /// option and subsequent elements representing legal registers for the
@@ -39,16 +39,16 @@ namespace PBQP {
     /// solver stack. If no nodes can be proven allocable then the node with
     /// the lowest estimated spill cost is selected and push to the solver stack
     /// instead.
-    /// 
-    /// This implementation is built on top of HeuristicBase.       
+    ///
+    /// This implementation is built on top of HeuristicBase.
     class Briggs : public HeuristicBase<Briggs> {
     private:
 
       class LinkDegreeComparator {
       public:
         LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
-        bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
-          if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
+        bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const {
+          if (s->getSolverDegree(n1Id) > s->getSolverDegree(n2Id))
             return true;
           return false;
         }
@@ -60,12 +60,12 @@ namespace PBQP {
       public:
         SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
           : s(&s), g(&s.getGraph()) {}
-        bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
-          const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr);
-          const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr);
+        bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const {
+          const PBQP::Vector &cv1 = g->getNodeCosts(n1Id);
+          const PBQP::Vector &cv2 = g->getNodeCosts(n2Id);
 
-          PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr);
-          PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr);
+          PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Id);
+          PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Id);
 
           if (cost1 < cost2)
             return true;
@@ -77,10 +77,10 @@ namespace PBQP {
         Graph *g;
       };
 
-      typedef std::list<Graph::NodeItr> RNAllocableList;
+      typedef std::list<Graph::NodeId> RNAllocableList;
       typedef RNAllocableList::iterator RNAllocableListItr;
 
-      typedef std::list<Graph::NodeItr> RNUnallocableList;  
+      typedef std::list<Graph::NodeId> RNUnallocableList;
       typedef RNUnallocableList::iterator RNUnallocableListItr;
 
     public:
@@ -114,7 +114,7 @@ namespace PBQP {
 
       /// \brief Determine whether a node should be reduced using optimal
       ///        reduction.
-      /// @param nItr Node iterator to be considered.
+      /// @param nId Node id to be considered.
       /// @return True if the given node should be optimally reduced, false
       ///         otherwise.
       ///
@@ -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::NodeItr nItr) {
-        if (getSolver().getSolverDegree(nItr) < 3) {
+      bool shouldOptimallyReduce(Graph::NodeId nId) {
+        if (getSolver().getSolverDegree(nId) < 3) {
           return true;
         }
         // else
@@ -132,15 +132,15 @@ 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::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
-        initializeNode(nItr);
+      /// @param nId Node id to add to the heuristic reduce list.
+      void addToHeuristicReduceList(Graph::NodeId nId) {
+        NodeData &nd = getHeuristicNodeData(nId);
+        initializeNode(nId);
         nd.isHeuristic = true;
         if (nd.isAllocable) {
-          nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
+          nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId);
         } else {
-          nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
+          nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nId);
         }
       }
 
@@ -159,19 +159,19 @@ namespace PBQP {
           RNAllocableListItr rnaItr =
             min_element(rnAllocableList.begin(), rnAllocableList.end(),
                         LinkDegreeComparator(getSolver()));
-          Graph::NodeItr nItr = *rnaItr;
+          Graph::NodeId nId = *rnaItr;
           rnAllocableList.erase(rnaItr);
-          handleRemoveNode(nItr);
-          getSolver().pushToStack(nItr);
+          handleRemoveNode(nId);
+          getSolver().pushToStack(nId);
           return true;
         } else if (!rnUnallocableList.empty()) {
           RNUnallocableListItr rnuItr =
             min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
                         SpillCostComparator(getSolver()));
-          Graph::NodeItr nItr = *rnuItr;
+          Graph::NodeId nId = *rnuItr;
           rnUnallocableList.erase(rnuItr);
-          handleRemoveNode(nItr);
-          getSolver().pushToStack(nItr);
+          handleRemoveNode(nId);
+          getSolver().pushToStack(nId);
           return true;
         }
         // else
@@ -179,43 +179,43 @@ namespace PBQP {
       }
 
       /// \brief Prepare a change in the costs on the given edge.
-      /// @param eItr Edge iterator.    
-      void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
+      /// @param eId Edge id.
+      void preUpdateEdgeCosts(Graph::EdgeId eId) {
         Graph &g = getGraph();
-        Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
-                       n2Itr = g.getEdgeNode2(eItr);
-        NodeData &n1 = getHeuristicNodeData(n1Itr),
-                 &n2 = getHeuristicNodeData(n2Itr);
+        Graph::NodeId n1Id = g.getEdgeNode1(eId),
+                      n2Id = g.getEdgeNode2(eId);
+        NodeData &n1 = getHeuristicNodeData(n1Id),
+                 &n2 = getHeuristicNodeData(n2Id);
 
         if (n1.isHeuristic)
-          subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
+          subtractEdgeContributions(eId, getGraph().getEdgeNode1(eId));
         if (n2.isHeuristic)
-          subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));
+          subtractEdgeContributions(eId, getGraph().getEdgeNode2(eId));
 
-        EdgeData &ed = getHeuristicEdgeData(eItr);
+        EdgeData &ed = getHeuristicEdgeData(eId);
         ed.isUpToDate = false;
       }
 
       /// \brief Handle the change in the costs on the given edge.
-      /// @param eItr Edge iterator.
-      void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
+      /// @param eId Edge id.
+      void postUpdateEdgeCosts(Graph::EdgeId eId) {
         // This is effectively the same as adding a new edge now, since
         // we've factored out the costs of the old one.
-        handleAddEdge(eItr);
+        handleAddEdge(eId);
       }
 
       /// \brief Handle the addition of a new edge into the PBQP graph.
-      /// @param eItr Edge iterator for the added edge.
+      /// @param eId Edge id for the added edge.
       ///
       /// 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::EdgeItr eItr) {
+      void handleAddEdge(Graph::EdgeId eId) {
         Graph &g = getGraph();
-        Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
-                       n2Itr = g.getEdgeNode2(eItr);
-        NodeData &n1 = getHeuristicNodeData(n1Itr),
-                 &n2 = getHeuristicNodeData(n2Itr);
+        Graph::NodeId n1Id = g.getEdgeNode1(eId),
+                      n2Id = g.getEdgeNode2(eId);
+        NodeData &n1 = getHeuristicNodeData(n1Id),
+                 &n2 = getHeuristicNodeData(n2Id);
 
         // If neither node is managed by the heuristic there's nothing to be
         // done.
@@ -223,60 +223,60 @@ namespace PBQP {
           return;
 
         // Ok - we need to update at least one node.
-        computeEdgeContributions(eItr);
+        computeEdgeContributions(eId);
 
         // Update node 1 if it's managed by the heuristic.
         if (n1.isHeuristic) {
           bool n1WasAllocable = n1.isAllocable;
-          addEdgeContributions(eItr, n1Itr);
-          updateAllocability(n1Itr);
+          addEdgeContributions(eId, n1Id);
+          updateAllocability(n1Id);
           if (n1WasAllocable && !n1.isAllocable) {
             rnAllocableList.erase(n1.rnaItr);
             n1.rnuItr =
-              rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
+              rnUnallocableList.insert(rnUnallocableList.end(), n1Id);
           }
         }
 
         // Likewise for node 2.
         if (n2.isHeuristic) {
           bool n2WasAllocable = n2.isAllocable;
-          addEdgeContributions(eItr, n2Itr);
-          updateAllocability(n2Itr);
+          addEdgeContributions(eId, n2Id);
+          updateAllocability(n2Id);
           if (n2WasAllocable && !n2.isAllocable) {
             rnAllocableList.erase(n2.rnaItr);
             n2.rnuItr =
-              rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
+              rnUnallocableList.insert(rnUnallocableList.end(), n2Id);
           }
         }
       }
 
       /// \brief Handle disconnection of an edge from a node.
-      /// @param eItr Edge iterator for edge being disconnected.
-      /// @param nItr Node iterator for the node being disconnected from.
+      /// @param eId Edge id for edge being disconnected.
+      /// @param nId Node id for the node being disconnected from.
       ///
       /// Updates allocability of the given node and, if appropriate, moves the
       /// node to a new list.
-      void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
+      void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) {
+        NodeData &nd =getHeuristicNodeData(nId);
 
         // If the node is not managed by the heuristic there's nothing to be
         // done.
         if (!nd.isHeuristic)
           return;
 
-        EdgeData &ed = getHeuristicEdgeData(eItr);
+        EdgeData &ed = getHeuristicEdgeData(eId);
         (void)ed;
         assert(ed.isUpToDate && "Edge data is not up to date.");
 
         // Update node.
         bool ndWasAllocable = nd.isAllocable;
-        subtractEdgeContributions(eItr, nItr);
-        updateAllocability(nItr);
+        subtractEdgeContributions(eId, nId);
+        updateAllocability(nId);
 
         // If the node has gone optimal...
-        if (shouldOptimallyReduce(nItr)) {
+        if (shouldOptimallyReduce(nId)) {
           nd.isHeuristic = false;
-          addToOptimalReduceList(nItr);
+          addToOptimalReduceList(nId);
           if (ndWasAllocable) {
             rnAllocableList.erase(nd.rnaItr);
           } else {
@@ -287,36 +287,36 @@ namespace PBQP {
           // from "unallocable" to "allocable".
           if (!ndWasAllocable && nd.isAllocable) {
             rnUnallocableList.erase(nd.rnuItr);
-            nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
+            nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId);
           }
         }
       }
 
     private:
 
-      NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
-        return getSolver().getHeuristicNodeData(nItr);
+      NodeData& getHeuristicNodeData(Graph::NodeId nId) {
+        return getSolver().getHeuristicNodeData(nId);
       }
 
-      EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
-        return getSolver().getHeuristicEdgeData(eItr);
+      EdgeData& getHeuristicEdgeData(Graph::EdgeId eId) {
+        return getSolver().getHeuristicEdgeData(eId);
       }
 
       // Work out what this edge will contribute to the allocability of the
       // nodes connected to it.
-      void computeEdgeContributions(Graph::EdgeItr eItr) {
-        EdgeData &ed = getHeuristicEdgeData(eItr);
+      void computeEdgeContributions(Graph::EdgeId eId) {
+        EdgeData &ed = getHeuristicEdgeData(eId);
 
         if (ed.isUpToDate)
           return; // Edge data is already up to date.
 
-        Matrix &eCosts = getGraph().getEdgeCosts(eItr);
+        Matrix &eCosts = getGraph().getEdgeCosts(eId);
 
         unsigned numRegs = eCosts.getRows() - 1,
                  numReverseRegs = eCosts.getCols() - 1;
 
         std::vector<unsigned> rowInfCounts(numRegs, 0),
-                              colInfCounts(numReverseRegs, 0);        
+                              colInfCounts(numReverseRegs, 0);
 
         ed.worst = 0;
         ed.reverseWorst = 0;
@@ -348,19 +348,19 @@ namespace PBQP {
         ed.isUpToDate = true;
       }
 
-      // Add the contributions of the given edge to the given node's 
+      // Add the contributions of the given edge to the given node's
       // 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::EdgeItr eItr, Graph::NodeItr nItr) {
-        EdgeData &ed = getHeuristicEdgeData(eItr);
+      void addEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) {
+        EdgeData &ed = getHeuristicEdgeData(eId);
 
         assert(ed.isUpToDate && "Using out-of-date edge numbers.");
 
-        NodeData &nd = getHeuristicNodeData(nItr);
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
-        
-        bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
+        NodeData &nd = getHeuristicNodeData(nId);
+        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
+
+        bool nIsNode1 = nId == getGraph().getEdgeNode1(eId);
         EdgeData::UnsafeArray &unsafe =
           nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
         nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;
@@ -375,25 +375,25 @@ namespace PBQP {
         }
       }
 
-      // Subtract the contributions of the given edge to the given node's 
+      // Subtract the contributions of the given edge to the given node's
       // 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::EdgeItr eItr, Graph::NodeItr nItr) {
-        EdgeData &ed = getHeuristicEdgeData(eItr);
+      void subtractEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) {
+        EdgeData &ed = getHeuristicEdgeData(eId);
 
         assert(ed.isUpToDate && "Using out-of-date edge numbers.");
 
-        NodeData &nd = getHeuristicNodeData(nItr);
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
-        
-        bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
+        NodeData &nd = getHeuristicNodeData(nId);
+        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
+
+        bool nIsNode1 = nId == getGraph().getEdgeNode1(eId);
         EdgeData::UnsafeArray &unsafe =
           nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
         nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;
 
         for (unsigned r = 0; r < numRegs; ++r) {
-          if (unsafe[r]) { 
+          if (unsafe[r]) {
             if (nd.unsafeDegrees[r] == 1) {
               ++nd.numSafe;
             }
@@ -402,22 +402,22 @@ namespace PBQP {
         }
       }
 
-      void updateAllocability(Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+      void updateAllocability(Graph::NodeId nId) {
+        NodeData &nd = getHeuristicNodeData(nId);
+        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
         nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0;
       }
 
-      void initializeNode(Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
+      void initializeNode(Graph::NodeId nId) {
+        NodeData &nd = getHeuristicNodeData(nId);
 
         if (nd.isInitialized)
           return; // Node data is already up to date.
 
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
 
         nd.numDenied = 0;
-        const Vector& nCosts = getGraph().getNodeCosts(nItr);
+        const Vector& nCosts = getGraph().getNodeCosts(nId);
         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(nItr),
-                           aeEnd = getSolver().solverEdgesEnd(nItr);
+        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nId),
+                           aeEnd = getSolver().solverEdgesEnd(nId);
              aeItr != aeEnd; ++aeItr) {
-          
-          Graph::EdgeItr eItr = *aeItr;
-          computeEdgeContributions(eItr);
-          addEdgeContributions(eItr, nItr);
+
+          Graph::EdgeId eId = *aeItr;
+          computeEdgeContributions(eId);
+          addEdgeContributions(eId, nId);
         }
 
-        updateAllocability(nItr);
+        updateAllocability(nId);
         nd.isInitialized = true;
       }
 
-      void handleRemoveNode(Graph::NodeItr xnItr) {
+      void handleRemoveNode(Graph::NodeId xnId) {
         typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
-        std::vector<Graph::EdgeItr> edgesToRemove;
-        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
-                           aeEnd = getSolver().solverEdgesEnd(xnItr);
+        std::vector<Graph::EdgeId> edgesToRemove;
+        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnId),
+                           aeEnd = getSolver().solverEdgesEnd(xnId);
              aeItr != aeEnd; ++aeItr) {
-          Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
-          handleRemoveEdge(*aeItr, ynItr);
+          Graph::NodeId ynId = getGraph().getEdgeOtherNode(*aeItr, xnId);
+          handleRemoveEdge(*aeItr, ynId);
           edgesToRemove.push_back(*aeItr);
         }
         while (!edgesToRemove.empty()) {