[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

37

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

41

Please run clang-format and remove the needed ;

42

Pass argument as const reference?

llvm/lib/Analysis/ConstraintSystem.cpp

111

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

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

638–639

This function isn't needed any longer.

639–640

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

37

still needs a newline before the comment.

42

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

43

newline before the next function.

43

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

103–104

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

37

nit: from *the* Value2Index map.

llvm/lib/Analysis/ConstraintSystem.cpp

121

nit: add newline here.

124

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 {
   SmallVector<SmallVector<int64_t, 8>, 4> Constraints;
   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 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;
-
+  auto 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) {
static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info) {
 
   bool Changed = false;
   if (CSToUse.isConditionImplied(R.Coefficients)) {
     if (!DebugCounter::shouldExecute(EliminatedCounter))
       return false;
 
     LLVM_DEBUG({
       dbgs() << "Condition " << *Cmp << " implied by dominating constraints\n";
-      dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned));
+      CSToUse.dump();
     });
     Constant *TrueC =
         ConstantInt::getTrue(CmpInst::makeCmpResultType(Cmp->getType()));
     Cmp->replaceUsesWithIf(TrueC, [](Use &U) {
       // Conditions in an assume trivially simplify to true. Skip uses
       // in assume calls to not destroy the available information.
       auto *II = dyn_cast<IntrinsicInst>(U.getUser());
       return !II || II->getIntrinsicID() != Intrinsic::assume;
     });
     NumCondsRemoved++;
     Changed = true;
   }
   if (CSToUse.isConditionImplied(ConstraintSystem::negate(R.Coefficients))) {
     if (!DebugCounter::shouldExecute(EliminatedCounter))
       return false;
 
     LLVM_DEBUG({
       dbgs() << "Condition !" << *Cmp << " implied by dominating constraints\n";
-      dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned));
+      CSToUse.dump();
     });
     Constant *FalseC =
         ConstantInt::getFalse(CmpInst::makeCmpResultType(Cmp->getType()));
     Cmp->replaceAllUsesWith(FalseC);
     NumCondsRemoved++;
     Changed = true;
   }
   return Changed;
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);

llvm/test/Transforms/ConstraintElimination/debug.ll

 ; RUN: opt -passes=constraint-elimination -S -debug %s 2>&1 | FileCheck %s
 
 ; REQUIRES: asserts
 
 declare void @use(i1)
 
 define i1 @test_and_ule(i4 %x, i4 %y, i4 %z) {
 ; CHECK:      Processing fact to add to the system:  %c.1 = icmp ule i4 %x, %y
 ; CHECK-NEXT: Adding 'ule %x, %y'
 ; CHECK-NEXT:  constraint: %x + -1 * %y <= 0
 
 ; CHECK:      Processing fact to add to the system:  %c.2 = icmp ule i4 %y, %z
 ; CHECK-NEXT: Adding 'ule %y, %z'
 ; CHECK-NEXT:  constraint: %y + -1 * %z <= 0
 
 ; CHECK: Checking   %t.1 = icmp ule i4 %x, %z
+; CHECK: %x + -1 * %y <= 0
+; CHECK: %y + -1 * %z <= 0
+; CHECK: -1 * %x + %z <= -1
+; CHECK: unsat
 ; CHECK: Condition   %t.1 = icmp ule i4 %x, %z implied by dominating constraints
+; CHECK: %x + -1 * %y <= 0
+; CHECK: %y + -1 * %z <= 0
+; CHECK: %x + -1 * %y <= 0
+; CHECK: %y + -1 * %z <= 0
+; CHECK: %x + -1 * %z <= 0
+; CHECK: sat
 
 entry:
   %c.1 = icmp ule i4 %x, %y
   %c.2 = icmp ule i4 %y, %z
   %and = and i1 %c.1, %c.2
   br i1 %and, label %bb1, label %exit
 
 bb1:
   %t.1 = icmp ule i4 %x, %z
   ret i1 %t.1
 
 exit:
   %c.3 = icmp ule i4 %x, %z
   ret i1 %c.3
 }