Delete dead code in PBQP (NFC)

[vsk]

Summary

I tested this with "ninja llc check-llvm-codegen" on a Debug (x86, aarch64, arm) build.

Found with llvm-cov.

[dblaikie]

include/llvm/CodeGen/PBQP/Math.h

65–85

Looks like this (& other parts of this class) could be simplified by making it use unique_ptr<PBQPNum[]> for Data. There's still be some explicit code for the assignment operator (I'd suggest the copy-and-swap idiom) and while this code might not be used right now, it's probably generically useful enough (& once the change is made, simple enough) to keep around, but might deserve a unit test or two if it doesn't have any.

(same goes for similar Matrix changes - and probably for the various operator overloads too (eg: they're probably of sufficient general utility, but should have unit tests))

But I leave the final decisions up to Lang.

[vsk]

@lhames ping?

include/llvm/CodeGen/PBQP/Math.h

65–85

Thanks for the note, using a unique_ptr for Data sounds like a good idea.

[lhames]

Yep - go ahead and kill this off. :)

• Lang.

include/llvm/CodeGen/PBQP/CostAllocator.h

public:
     static unsigned getHashValue(const ValueKeyT &C) {
       return hash_value(C);
     }
 
     static unsigned getHashValue(PoolEntry *P) {
       return getHashValue(P->getValue());
     }
 
-    static unsigned getHashValue(const PoolEntry *P) {
-      return getHashValue(P->getValue());
-    }
-
     template <typename ValueKeyT1, typename ValueKeyT2>
     static
     bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
       return C1 == C2;
     }
 
     template <typename ValueKeyT>
     static bool isEqual(const ValueKeyT &C, PoolEntry *P) {

include/llvm/CodeGen/PBQP/Graph.h

public:
       EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
           : Costs(std::move(Costs)) {
         NIds[0] = N1Id;
         NIds[1] = N2Id;
         ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
         ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
       }
 
-      void invalidate() {
-        NIds[0] = NIds[1] = Graph::invalidNodeId();
-        ThisEdgeAdjIdxs[0] = ThisEdgeAdjIdxs[1] =
-          NodeEntry::getInvalidAdjEdgeIdx();
-        Costs = nullptr;
-      }
-
       void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) {
         assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
                "Edge already connected to NIds[NIdx].");
         NodeEntry &N = G.getNode(NIds[NIdx]);
         ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId);
       }
 
-      void connectTo(Graph &G, EdgeId ThisEdgeId, NodeId NId) {
-        if (NId == NIds[0])
-          connectToN(G, ThisEdgeId, 0);
-        else {
-          assert(NId == NIds[1] && "Edge does not connect NId.");
-          connectToN(G, ThisEdgeId, 1);
-        }
-      }
-
       void connect(Graph &G, EdgeId ThisEdgeId) {
         connectToN(G, ThisEdgeId, 0);
         connectToN(G, ThisEdgeId, 1);
       }
 
       void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
         if (NId == NIds[0])
           ThisEdgeAdjIdxs[0] = NewIdx;

include/llvm/CodeGen/PBQP/Math.h

public:
   }
 
   /// \brief Destroy this vector, return its memory.
   ~Vector() {
     // llvm::dbgs() << "Deleting PBQP::Vector " << this << "\n";
     delete[] Data;
   }
 
-  /// \brief Copy-assignment operator.
-  Vector& operator=(const Vector &V) {
-    // llvm::dbgs() << "Assigning to PBQP::Vector " << this
-    //              << " from PBQP::Vector " << &V << "\n";
-    delete[] Data;
-    Length = V.Length;
-    Data = new PBQPNum[Length];
-    std::copy(V.Data, V.Data + Length, Data);
-    return *this;
-  }
-
-  /// \brief Move-assignment operator.
-  Vector& operator=(Vector &&V) {
-    delete[] Data;
-    Length = V.Length;
-    Data = V.Data;
-    V.Length = 0;
-    V.Data = nullptr;
-    return *this;
-  }
-
   /// \brief Comparison operator.
   bool operator==(const Vector &V) const {
     assert(Length != 0 && Data != nullptr && "Invalid vector");
     if (Length != V.Length)
       return false;
     return std::equal(Data, Data + Length, V.Data);
   }
 
public:
   /// \brief Add another vector to this one.
   Vector& operator+=(const Vector &V) {
     assert(Length != 0 && Data != nullptr && "Invalid vector");
     assert(Length == V.Length && "Vector length mismatch.");
     std::transform(Data, Data + Length, V.Data, Data, std::plus<PBQPNum>());
     return *this;
   }
 
-  /// \brief Subtract another vector from this one.
-  Vector& operator-=(const Vector &V) {
-    assert(Length != 0 && Data != nullptr && "Invalid vector");
-    assert(Length == V.Length && "Vector length mismatch.");
-    std::transform(Data, Data + Length, V.Data, Data, std::minus<PBQPNum>());
-    return *this;
-  }
-
   /// \brief Returns the index of the minimum value in this vector
   unsigned minIndex() const {
     assert(Length != 0 && Data != nullptr && "Invalid vector");
     return std::min_element(Data, Data + Length) - Data;
   }
 
 private:
   unsigned Length;
Matrix(Matrix &&M)
     : Rows(M.Rows), Cols(M.Cols), Data(M.Data) {
     M.Rows = M.Cols = 0;
     M.Data = nullptr;
   }
 
   /// \brief Destroy this matrix, return its memory.
   ~Matrix() { delete[] Data; }
 
-  /// \brief Copy-assignment operator.
-  Matrix& operator=(const Matrix &M) {
-    delete[] Data;
-    Rows = M.Rows; Cols = M.Cols;
-    Data = new PBQPNum[Rows * Cols];
-    std::copy(M.Data, M.Data + (Rows * Cols), Data);
-    return *this;
-  }
-
-  /// \brief Move-assignment operator.
-  Matrix& operator=(Matrix &&M) {
-    delete[] Data;
-    Rows = M.Rows;
-    Cols = M.Cols;
-    Data = M.Data;
-    M.Rows = M.Cols = 0;
-    M.Data = nullptr;
-    return *this;
-  }
-
   /// \brief Comparison operator.
   bool operator==(const Matrix &M) const {
     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
     if (Rows != M.Rows || Cols != M.Cols)
       return false;
     return std::equal(Data, Data + (Rows * Cols), M.Data);
   }
 
public:
   Vector getColAsVector(unsigned C) const {
     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
     Vector V(Rows);
     for (unsigned R = 0; R < Rows; ++R)
       V[R] = (*this)[R][C];
     return V;
   }
 
-  /// \brief Reset the matrix to the given value.
-  Matrix& reset(PBQPNum Val = 0) {
-    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
-    std::fill(Data, Data + (Rows * Cols), Val);
-    return *this;
-  }
-
-  /// \brief Set a single row of this matrix to the given value.
-  Matrix& setRow(unsigned R, PBQPNum Val) {
-    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
-    assert(R < Rows && "Row out of bounds.");
-    std::fill(Data + (R * Cols), Data + ((R + 1) * Cols), Val);
-    return *this;
-  }
-
-  /// \brief Set a single column of this matrix to the given value.
-  Matrix& setCol(unsigned C, PBQPNum Val) {
-    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
-    assert(C < Cols && "Column out of bounds.");
-    for (unsigned R = 0; R < Rows; ++R)
-      (*this)[R][C] = Val;
-    return *this;
-  }
-
   /// \brief Matrix transpose.
   Matrix transpose() const {
     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
     Matrix M(Cols, Rows);
     for (unsigned r = 0; r < Rows; ++r)
       for (unsigned c = 0; c < Cols; ++c)
         M[c][r] = (*this)[r][c];
     return M;
   }
 
-  /// \brief Returns the diagonal of the matrix as a vector.
-  ///
-  /// Matrix must be square.
-  Vector diagonalize() const {
-    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
-    assert(Rows == Cols && "Attempt to diagonalize non-square matrix.");
-    Vector V(Rows);
-    for (unsigned r = 0; r < Rows; ++r)
-      V[r] = (*this)[r][r];
-    return V;
-  }
-
   /// \brief Add the given matrix to this one.
   Matrix& operator+=(const Matrix &M) {
     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
     assert(Rows == M.Rows && Cols == M.Cols &&
            "Matrix dimensions mismatch.");
     std::transform(Data, Data + (Rows * Cols), M.Data, Data,
                    std::plus<PBQPNum>());
     return *this;
   }
 
   Matrix operator+(const Matrix &M) {
     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
     Matrix Tmp(*this);
     Tmp += M;
     return Tmp;
   }
 
-  /// \brief Returns the minimum of the given row
-  PBQPNum getRowMin(unsigned R) const {
-    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
-    assert(R < Rows && "Row out of bounds");
-    return *std::min_element(Data + (R * Cols), Data + ((R + 1) * Cols));
-  }
-
-  /// \brief Returns the minimum of the given column
-  PBQPNum getColMin(unsigned C) const {
-    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
-    PBQPNum MinElem = (*this)[0][C];
-    for (unsigned R = 1; R < Rows; ++R)
-      if ((*this)[R][C] < MinElem)
-        MinElem = (*this)[R][C];
-    return MinElem;
-  }
-
-  /// \brief Subtracts the given scalar from the elements of the given row.
-  Matrix& subFromRow(unsigned R, PBQPNum Val) {
-    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
-    assert(R < Rows && "Row out of bounds");
-    std::transform(Data + (R * Cols), Data + ((R + 1) * Cols),
-                   Data + (R * Cols),
-                   std::bind2nd(std::minus<PBQPNum>(), Val));
-    return *this;
-  }
-
-  /// \brief Subtracts the given scalar from the elements of the given column.
-  Matrix& subFromCol(unsigned C, PBQPNum Val) {
-    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
-    for (unsigned R = 0; R < Rows; ++R)
-      (*this)[R][C] -= Val;
-    return *this;
-  }
-
-  /// \brief Returns true if this is a zero matrix.
-  bool isZero() const {
-    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
-    return find_if(Data, Data + (Rows * Cols),
-                   std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
-      Data + (Rows * Cols);
-  }
-
 private:
   unsigned Rows, Cols;
   PBQPNum *Data;
 };
 
 /// \brief Return a hash_code for the given matrix.
 inline hash_code hash_value(const Matrix &M) {
   unsigned *MBegin = reinterpret_cast<unsigned*>(M.Data);

include/llvm/CodeGen/PBQP/Solution.h

private:
     unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions;
 
   public:
 
     /// \brief Initialise an empty solution.
     Solution()
       : r0Reductions(0), r1Reductions(0), r2Reductions(0), rNReductions(0) {}
 
-    /// \brief Number of nodes for which selections have been made.
-    /// @return Number of nodes for which selections have been made.
-    unsigned numNodes() const { return selections.size(); }
-
-    /// \brief Records a reduction via the R0 rule. Should be called from the
-    ///        solver only.
-    void recordR0() { ++r0Reductions; }
-
-    /// \brief Returns the number of R0 reductions applied to solve the problem.
-    unsigned numR0Reductions() const { return r0Reductions; }
-
-    /// \brief Records a reduction via the R1 rule. Should be called from the
-    ///        solver only.
-    void recordR1() { ++r1Reductions; }
-
-    /// \brief Returns the number of R1 reductions applied to solve the problem.
-    unsigned numR1Reductions() const { return r1Reductions; }
-
-    /// \brief Records a reduction via the R2 rule. Should be called from the
-    ///        solver only.
-    void recordR2() { ++r2Reductions; }
-
-    /// \brief Returns the number of R2 reductions applied to solve the problem.
-    unsigned numR2Reductions() const { return r2Reductions; }
-
-    /// \brief Records a reduction via the RN rule. Should be called from the
-    ///        solver only.
-    void recordRN() { ++ rNReductions; }
-
-    /// \brief Returns the number of RN reductions applied to solve the problem.
-    unsigned numRNReductions() const { return rNReductions; }
-
     /// \brief Set the selection for a given node.
     /// @param nodeId Node id.
     /// @param selection Selection for nodeId.
     void setSelection(GraphBase::NodeId nodeId, unsigned selection) {
       selections[nodeId] = selection;
     }
 
     /// \brief Get a node's selection.

include/llvm/CodeGen/RegAllocPBQP.h

public:
 
   AllowedRegVector() : NumOpts(0), Opts(nullptr) {}
 
   AllowedRegVector(const std::vector<unsigned> &OptVec)
     : NumOpts(OptVec.size()), Opts(new unsigned[NumOpts]) {
     std::copy(OptVec.begin(), OptVec.end(), Opts.get());
   }
 
-  AllowedRegVector(const AllowedRegVector &Other)
-    : NumOpts(Other.NumOpts), Opts(new unsigned[NumOpts]) {
-    std::copy(Other.Opts.get(), Other.Opts.get() + NumOpts, Opts.get());
-  }
-
   AllowedRegVector(AllowedRegVector &&Other)
     : NumOpts(std::move(Other.NumOpts)), Opts(std::move(Other.Opts)) {}
 
-  AllowedRegVector& operator=(const AllowedRegVector &Other) {
-    NumOpts = Other.NumOpts;
-    Opts.reset(new unsigned[NumOpts]);
-    std::copy(Other.Opts.get(), Other.Opts.get() + NumOpts, Opts.get());
-    return *this;
-  }
-
-  AllowedRegVector& operator=(AllowedRegVector &&Other) {
-    NumOpts = std::move(Other.NumOpts);
-    Opts = std::move(Other.Opts);
-    return *this;
-  }
-
   unsigned size() const { return NumOpts; }
   unsigned operator[](size_t I) const { return Opts[I]; }
 
   bool operator==(const AllowedRegVector &Other) const {
     if (NumOpts != Other.NumOpts)
       return false;
     return std::equal(Opts.get(), Opts.get() + NumOpts, Other.Opts.get());
   }
public:
 
   GraphBase::NodeId getNodeIdForVReg(unsigned VReg) const {
     auto VRegItr = VRegToNodeId.find(VReg);
     if (VRegItr == VRegToNodeId.end())
       return GraphBase::invalidNodeId();
     return VRegItr->second;
   }
 
-  void eraseNodeIdForVReg(unsigned VReg) {
-    VRegToNodeId.erase(VReg);
-  }
-
   AllowedRegVecRef getAllowedRegs(AllowedRegVector Allowed) {
     return AllowedRegVecs.getValue(std::move(Allowed));
   }
 
 private:
   DenseMap<unsigned, GraphBase::NodeId> VRegToNodeId;
   AllowedRegVecPool AllowedRegVecs;
 };
: RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
       AllowedRegs(std::move(Other.AllowedRegs))
 #ifndef NDEBUG
       , everConservativelyAllocatable(Other.everConservativelyAllocatable)
 #endif
   {}
 
   // FIXME: Re-implementing default behavior to work around MSVC. Remove once
   // MSVC synthesizes move constructors properly.
-  NodeMetadata& operator=(const NodeMetadata &Other) {
-    RS = Other.RS;
-    NumOpts = Other.NumOpts;
-    DeniedOpts = Other.DeniedOpts;
-    OptUnsafeEdges.reset(new unsigned[NumOpts]);
-    std::copy(Other.OptUnsafeEdges.get(), Other.OptUnsafeEdges.get() + NumOpts,
-              OptUnsafeEdges.get());
-    VReg = Other.VReg;
-    AllowedRegs = Other.AllowedRegs;
-#ifndef NDEBUG
-    everConservativelyAllocatable = Other.everConservativelyAllocatable;
-#endif
-    return *this;
-  }
-
-  // FIXME: Re-implementing default behavior to work around MSVC. Remove once
-  // MSVC synthesizes move constructors properly.
   NodeMetadata& operator=(NodeMetadata &&Other) {
     RS = Other.RS;
     NumOpts = Other.NumOpts;
     DeniedOpts = Other.DeniedOpts;
     OptUnsafeEdges = std::move(Other.OptUnsafeEdges);
     VReg = Other.VReg;
     AllowedRegs = std::move(Other.AllowedRegs);
 #ifndef NDEBUG
public:
   void handleRemoveNode(NodeId NId) {}
   void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
 
   void handleAddEdge(EdgeId EId) {
     handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
     handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
   }
 
-  void handleRemoveEdge(EdgeId EId) {
-    handleDisconnectEdge(EId, G.getEdgeNode1Id(EId));
-    handleDisconnectEdge(EId, G.getEdgeNode2Id(EId));
-  }
-
   void handleDisconnectEdge(EdgeId EId, NodeId NId) {
     NodeMetadata& NMd = G.getNodeMetadata(NId);
     const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
     NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
     promote(NId, NMd);
   }
 
   void handleReconnectEdge(EdgeId EId, NodeId NId) {