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 ↗

(On Diff #70894)

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 ↗

(On Diff #70894)

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

[lhames]

Yep - go ahead and kill this off. :)

• Lang.

llvm/trunk/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;

llvm/trunk/include/llvm/CodeGen/PBQP/Math.h

 
 /// \brief PBQP Vector class.
 class Vector {
   friend hash_code hash_value(const Vector &);
 public:
 
   /// \brief Construct a PBQP vector of the given size.
   explicit Vector(unsigned Length)
-    : Length(Length), Data(new PBQPNum[Length]) {
-    // llvm::dbgs() << "Constructing PBQP::Vector "
-    //              << this << " (length " << Length << ")\n";
-  }
+    : Length(Length), Data(new PBQPNum[Length]) {}
 
   /// \brief Construct a PBQP vector with initializer.
   Vector(unsigned Length, PBQPNum InitVal)
     : Length(Length), Data(new PBQPNum[Length]) {
-    // llvm::dbgs() << "Constructing PBQP::Vector "
-    //              << this << " (length " << Length << ", fill "
-    //              << InitVal << ")\n";
     std::fill(Data, Data + Length, InitVal);
   }
 
   /// \brief Copy construct a PBQP vector.
   Vector(const Vector &V)
     : Length(V.Length), Data(new PBQPNum[Length]) {
-    // llvm::dbgs() << "Copy-constructing PBQP::Vector " << this
-    //              << " from PBQP::Vector " << &V << "\n";
     std::copy(V.Data, V.Data + Length, Data);
   }
 
   /// \brief Move construct a PBQP vector.
   Vector(Vector &&V)
     : Length(V.Length), Data(V.Data) {
     V.Length = 0;
     V.Data = nullptr;
   }
 
   /// \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;
-  }
+  ~Vector() { delete[] Data; }
 
   /// \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);

llvm/trunk/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.

llvm/trunk/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;
-  }
+  AllowedRegVector(AllowedRegVector &&) = default;
 
   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;
 };
public:
   NodeMetadata()
     : RS(Unprocessed), NumOpts(0), DeniedOpts(0), OptUnsafeEdges(nullptr),
       VReg(0)
 #ifndef NDEBUG
       , everConservativelyAllocatable(false)
 #endif
       {}
 
-  // FIXME: Re-implementing default behavior to work around MSVC. Remove once
-  // MSVC synthesizes move constructors properly.
   NodeMetadata(const NodeMetadata &Other)
     : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),
       OptUnsafeEdges(new unsigned[NumOpts]), VReg(Other.VReg),
       AllowedRegs(Other.AllowedRegs)
 #ifndef NDEBUG
       , everConservativelyAllocatable(Other.everConservativelyAllocatable)
 #endif
   {
     if (NumOpts > 0) {
       std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],
                 &OptUnsafeEdges[0]);
     }
   }
 
-  // FIXME: Re-implementing default behavior to work around MSVC. Remove once
-  // MSVC synthesizes move constructors properly.
-  NodeMetadata(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
-      , everConservativelyAllocatable(Other.everConservativelyAllocatable)
-#endif
-  {}
+  NodeMetadata(NodeMetadata &&Other) = default;
 
-  // 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
-    everConservativelyAllocatable = Other.everConservativelyAllocatable;
-#endif
-    return *this;
-  }
+  NodeMetadata& operator=(NodeMetadata &&Other) = default;
 
   void setVReg(unsigned VReg) { this->VReg = VReg; }
   unsigned getVReg() const { return VReg; }
 
   void setAllowedRegs(GraphMetadata::AllowedRegVecRef AllowedRegs) {
     this->AllowedRegs = std::move(AllowedRegs);
   }
   const AllowedRegVector& getAllowedRegs() const { return *AllowedRegs; }

 #ifndef NDEBUG
     // Remember this state to assert later that a non-infinite register
     // option was available.
     if (RS == ConservativelyAllocatable)
       everConservativelyAllocatable = true;
 #endif
   }
 
-
   void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
     DeniedOpts += Transpose ? MD.getWorstRow() : MD.getWorstCol();
     const bool* UnsafeOpts =
       Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
     for (unsigned i = 0; i < NumOpts; ++i)
       OptUnsafeEdges[i] += UnsafeOpts[i];
   }
 
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) {