[ConstraintElimination] Change debug output to display variable names.

[zjaffal]

Summary

Previously when constraint system outputs the rows in the system the variables used are x1,2...n making it hard to infer which ones they relate to in the IR

[fhahn]

Thanks for looking into this! Would it make sense to change ConstraintSystem to hold a pointer/reference to the corresponding variable map and then isolate the name generation logic and dumping to ConstraintSystem.cpp only?

[nikic]

We should make sure that no name map is generated when not debugging.

[zjaffal]

Refactored the printing logic to be done in ConstraintSystem

[fhahn]

Would it be possible to add a test to show the additional dbg output, e.g. llvm/test/Transforms/ConstraintElimination/debug.ll?

llvm/include/llvm/Analysis/ConstraintSystem.h

42

capitalize first letter of sentence and period at end of sentence. Newline before comment

46

Please run clang-format and remove the needed ;

47

Pass argument as const reference?

llvm/lib/Analysis/ConstraintSystem.cpp

116

Can use (auto &[V, Index] : Value2Index).

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

646–647

This function isn't needed any longer.

647–648

Change to const reference and adjust name?

[zjaffal]

1. Modify debug.ll test to display variable names.
2. Delete unused functions and rename dumpdumpWithNames to dumpConstraint
3. Address style comments

[fhahn]

llvm/include/llvm/Analysis/ConstraintSystem.h

42

still needs a newline before the comment.

47

not just const, const reference, i.e. const DenseMap<Value *, unsigned> &Value2Index

48

newline before the next function.

48

; here also needs removed and reformatting. Please run clang-format.

109–110

The bit about using Names needs to be removed.

[zjaffal]

fix formatting and update dump() function comment

[fhahn]

LGTM, with a few small nits addressed.

llvm/include/llvm/Analysis/ConstraintSystem.h

42

nit: from *the* Value2Index map.

llvm/lib/Analysis/ConstraintSystem.cpp

126

nit: add newline here.

130

nit: the coding style recommends using auto sparingly and spell out full types unless they are too big. So here it would probably be better to use SmallVector<std::string>

[zjaffal]

Address nit comments

llvm/include/llvm/Analysis/ConstraintSystem.h

class ConstraintSystem {
   DenseMap<Value *, unsigned> Value2Index;
 
   /// Current greatest common divisor for all coefficients in the system.
   uint32_t GCD = 1;
 
   // Eliminate constraints from the system using Fourier–Motzkin elimination.
   bool eliminateUsingFM();
 
-  /// Print the constraints in the system, using x0...xn as variable names.
-  void dump() const;
-
   /// Returns true if there may be a solution for the constraints in the system.
   bool mayHaveSolutionImpl();
 
+  /// Get list of variable names from the Value2Index map.
+  SmallVector<std::string> getVarNamesList() const;
+
 public:
+  ConstraintSystem() {}
+  ConstraintSystem(const DenseMap<Value *, unsigned> &Value2Index)
+      : Value2Index(Value2Index) {}
+
   bool addVariableRow(ArrayRef<int64_t> R) {
     assert(Constraints.empty() || R.size() == Constraints.back().size());
     // If all variable coefficients are 0, the constraint does not provide any
     // usable information.
     if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
       return false;
 
     for (const auto &C : R) {
void popLastNVariables(unsigned N) {
     for (auto &C : Constraints) {
       for (unsigned i = 0; i < N; i++)
         C.pop_back();
     }
   }
 
   /// Returns the number of rows in the constraint system.
   unsigned size() const { return Constraints.size(); }
 
-  /// Print the constraints in the system, using \p Names as variable names.
-  void dump(ArrayRef<std::string> Names) const;
+  /// Print the constraints in the system.
+  void dump() const;
 };
 } // namespace llvm
 
 #endif // LLVM_ANALYSIS_CONSTRAINTSYSTEM_H

llvm/lib/Analysis/ConstraintSystem.cpp

bool ConstraintSystem::mayHaveSolutionImpl() {
   }
 
   if (Constraints.empty() || Constraints[0].size() > 1)
     return true;
 
   return all_of(Constraints, [](auto &R) { return R[0] >= 0; });
 }
 
-void ConstraintSystem::dump(ArrayRef<std::string> Names) const {
+SmallVector<std::string> ConstraintSystem::getVarNamesList() const {
+  SmallVector<std::string> Names(Value2Index.size(), "");
+  for (auto &[V, Index] : Value2Index) {
+    std::string OperandName;
+    if (V->getName().empty())
+      OperandName = V->getNameOrAsOperand();
+    else
+      OperandName = std::string("%") + V->getName().str();
+    Names[Index - 1] = OperandName;
+  }
+  return Names;
+}
+
+void ConstraintSystem::dump() const {
   if (Constraints.empty())
     return;
-
+  SmallVector<std::string> Names = getVarNamesList();
   for (const auto &Row : Constraints) {
     SmallVector<std::string, 16> Parts;
     for (unsigned I = 1, S = Row.size(); I < S; ++I) {
       if (Row[I] == 0)
         continue;
       std::string Coefficient;
       if (Row[I] != 1)
         Coefficient = std::to_string(Row[I]) + " * ";
       Parts.push_back(Coefficient + Names[I - 1]);
     }
     assert(!Parts.empty() && "need to have at least some parts");
     LLVM_DEBUG(dbgs() << join(Parts, std::string(" + "))
                       << " <= " << std::to_string(Row[0]) << "\n");
   }
 }
 
-void ConstraintSystem::dump() const {
-  SmallVector<std::string, 16> Names;
-  for (unsigned i = 1; i < Constraints.back().size(); ++i)
-    Names.push_back("x" + std::to_string(i));
-  LLVM_DEBUG(dbgs() << "---\n");
-  dump(Names);
-}
-
 bool ConstraintSystem::mayHaveSolution() {
   LLVM_DEBUG(dump());
   bool HasSolution = mayHaveSolutionImpl();
   LLVM_DEBUG(dbgs() << (HasSolution ? "sat" : "unsat") << "\n");
   return HasSolution;
 }
 
 bool ConstraintSystem::isConditionImplied(SmallVector<int64_t, 8> R) const {

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

struct State {
   /// block Succ.
   bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {
     return DT.dominates(BasicBlockEdge(&BB, Succ), Succ);
   }
 };
 
 } // namespace
 
 #ifndef NDEBUG
-static void dumpWithNames(const ConstraintSystem &CS,
-                          DenseMap<Value *, unsigned> &Value2Index) {
-  SmallVector<std::string> Names(Value2Index.size(), "");
-  for (auto &KV : Value2Index) {
-    Names[KV.second - 1] = std::string("%") + KV.first->getName().str();
-  }
-  CS.dump(Names);
-}
 
-static void dumpWithNames(ArrayRef<int64_t> C,
-                          DenseMap<Value *, unsigned> &Value2Index) {
-  ConstraintSystem CS;
+static void dumpConstraint(ArrayRef<int64_t> C,
+                           const DenseMap<Value *, unsigned> &Value2Index) {
+  ConstraintSystem CS(Value2Index);
   CS.addVariableRowFill(C);
-  dumpWithNames(CS, Value2Index);
+  CS.dump();
 }
 #endif
 
 void State::addInfoFor(BasicBlock &BB) {
   // True as long as long as the current instruction is guaranteed to execute.
   bool GuaranteedToExecute = true;
   // Queue conditions and assumes.
   for (Instruction &I : BB) {
if (Added) {
     auto &Value2Index = getValue2Index(R.IsSigned);
     for (Value *V : NewVariables) {
       Value2Index.insert({V, Value2Index.size() + 1});
       ValuesToRelease.push_back(V);
     }
 
     LLVM_DEBUG({
       dbgs() << "  constraint: ";
-      dumpWithNames(R.Coefficients, getValue2Index(R.IsSigned));
+      dumpConstraint(R.Coefficients, getValue2Index(R.IsSigned));
       dbgs() << "\n";
     });
 
     DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
                             std::move(ValuesToRelease));
 
     if (R.IsEq) {
       // Also add the inverted constraint for equality constraints.
while (!DFSInStack.empty()) {
       LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
                         << "\n");
       LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
       assert(E.NumIn <= CB.NumIn);
       if (CB.NumOut <= E.NumOut)
         break;
       LLVM_DEBUG({
         dbgs() << "Removing ";
-        dumpWithNames(Info.getCS(E.IsSigned).getLastConstraint(),
+        dumpConstraint(Info.getCS(E.IsSigned).getLastConstraint(),
                        Info.getValue2Index(E.IsSigned));
         dbgs() << "\n";
       });
 
       Info.popLastConstraint(E.IsSigned);
       // Remove variables in the system that went out of scope.
       auto &Mapping = Info.getValue2Index(E.IsSigned);
       for (Value *V : E.ValuesToRelease)
         Mapping.erase(V);