[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

38

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

39

Please run clang-format and remove the needed ;

40

Pass argument as const reference?

llvm/lib/Analysis/ConstraintSystem.cpp

111

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

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

660

This function isn't needed any longer.

663

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

38

still needs a newline before the comment.

40

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

41

newline before the next function.

41

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

95

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

38

nit: from *the* Value2Index map.

llvm/lib/Analysis/ConstraintSystem.cpp

112

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>

121

nit: add newline here.

[zjaffal]

Address nit comments

llvm/include/llvm/Analysis/ConstraintSystem.h

class ConstraintSystem {
   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();
 
 public:
   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) {
       auto A = std::abs(C);
       GCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)A}, {32, GCD})
                 .getZExtValue();
bool addVariableRowFill(ArrayRef<int64_t> R) {
     for (auto &CR : Constraints) {
       while (CR.size() != R.size())
         CR.push_back(0);
     }
     return addVariableRow(R);
   }
 
   /// Returns true if there may be a solution for the constraints in the system.
-  bool mayHaveSolution();
+  bool mayHaveSolution(SmallVector<std::string> *Names = nullptr);
 
   static SmallVector<int64_t, 8> negate(SmallVector<int64_t, 8> R) {
     // The negated constraint R is obtained by multiplying by -1 and adding 1 to
     // the constant.
     R[0] += 1;
     for (auto &C : R)
       C *= -1;
     return R;
   }
 
-  bool isConditionImplied(SmallVector<int64_t, 8> R) const;
+  bool isConditionImplied(SmallVector<int64_t, 8> R,
+                          SmallVector<std::string> *Names = nullptr) const;
 
   ArrayRef<int64_t> getLastConstraint() { return Constraints[0]; }
   void popLastConstraint() { Constraints.pop_back(); }
   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;
 };
 } // 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 {
   if (Constraints.empty())
     return;
 
   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() {
+bool ConstraintSystem::mayHaveSolution(SmallVector<std::string> *Names) {
+  if (!Names)
     LLVM_DEBUG(dump());
+  else
+    LLVM_DEBUG(dump(ArrayRef<std::string>(Names->begin(), Names->end())));
   bool HasSolution = mayHaveSolutionImpl();
   LLVM_DEBUG(dbgs() << (HasSolution ? "sat" : "unsat") << "\n");
   return HasSolution;
 }
 
-bool ConstraintSystem::isConditionImplied(SmallVector<int64_t, 8> R) const {
+bool ConstraintSystem::isConditionImplied(
+    SmallVector<int64_t, 8> R, SmallVector<std::string> *Names) const {
   // If all variable coefficients are 0, we have 'C >= 0'. If the constant is >=
   // 0, R is always true, regardless of the system.
   if (all_of(ArrayRef(R).drop_front(1), [](int64_t C) { return C == 0; }))
     return R[0] >= 0;
 
   // If there is no solution with the negation of R added to the system, the
   // condition must hold based on the existing constraints.
   R = ConstraintSystem::negate(R);
 
   auto NewSystem = *this;
   NewSystem.addVariableRow(R);
-  return !NewSystem.mayHaveSolution();
+  return !NewSystem.mayHaveSolution(Names);
 }

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

 
 // A helper to add 2 signed integers where overflowing is allowed.
 static int64_t addWithOverflow(int64_t A, int64_t B) {
   int64_t Result;
   AddOverflow(A, B, Result);
   return Result;
 }
 
+static SmallVector<std::string> getVarNamesList(DenseMap<Value *, unsigned> &Value2Index){
+  SmallVector<std::string> Names(Value2Index.size(), "");
+  for (auto &KV : Value2Index) {
+    std::string OperandName;
+    if(KV.first->getName().empty())
+      OperandName = KV.first->getNameOrAsOperand();
+    else
+      OperandName = std::string("%") + KV.first->getName().str();
+    Names[KV.second - 1] = OperandName;
+  }
+  return Names;
+}
+
 namespace {
 
 class ConstraintInfo;
 
 struct StackEntry {
   unsigned NumIn;
   unsigned NumOut;
   bool IsSigned = false;
return Coefficients.size() > 0 &&
          all_of(Preconditions, [&Info](const PreconditionTy &C) {
            return Info.doesHold(C.Pred, C.Op0, C.Op1);
          });
 }
 
 bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A,
                               Value *B) const {
   auto R = getConstraintForSolving(Pred, A, B);
+  auto Value2Index = getValue2Index(R.IsSigned);
+  auto Names = getVarNamesList(Value2Index);
   return R.Preconditions.empty() && !R.empty() &&
-         getCS(R.IsSigned).isConditionImplied(R.Coefficients);
+         getCS(R.IsSigned).isConditionImplied(R.Coefficients, &Names);
 }
 
 void ConstraintInfo::transferToOtherSystem(
     CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
     unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {
   // Check if we can combine facts from the signed and unsigned systems to
   // derive additional facts.
   if (!A->getType()->isIntegerTy())
struct State {
   }
 };
 
 } // 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();
-  }
+  SmallVector<std::string> Names = getVarNamesList(Value2Index);
   CS.dump(Names);
 }
 
 static void dumpWithNames(ArrayRef<int64_t> C,
                           DenseMap<Value *, unsigned> &Value2Index) {
   ConstraintSystem CS;
   CS.addVariableRowFill(C);
   dumpWithNames(CS, Value2Index);
 }
 #endif
 
 void State::addInfoFor(BasicBlock &BB) {
   // True as long as long as the current instruction is guaranteed to execute.

 static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info) {
   LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n");
 
   CmpInst::Predicate Pred = Cmp->getPredicate();
   Value *A = Cmp->getOperand(0);
   Value *B = Cmp->getOperand(1);
 
   auto R = Info.getConstraintForSolving(Pred, A, B);
+  SmallVector<std::string> Names = getVarNamesList(Info.getValue2Index(R.IsSigned));
   if (R.empty() || !R.isValid(Info)){
     LLVM_DEBUG(dbgs() << "   failed to decompose condition\n");
     return false;
   }
 
   auto &CSToUse = Info.getCS(R.IsSigned);
 
   // If there was extra information collected during decomposition, apply
   // it now and remove it immediately once we are done with reasoning
   // about the constraint.
   for (auto &Row : R.ExtraInfo)
     CSToUse.addVariableRow(Row);
   auto InfoRestorer = make_scope_exit([&]() {
     for (unsigned I = 0; I < R.ExtraInfo.size(); ++I)
       CSToUse.popLastConstraint();
   });
 
   bool Changed = false;
-  if (CSToUse.isConditionImplied(R.Coefficients)) {
+  if (CSToUse.isConditionImplied(R.Coefficients, &Names)) {
     if (!DebugCounter::shouldExecute(EliminatedCounter))
       return false;
 
     LLVM_DEBUG({
       dbgs() << "Condition " << *Cmp << " implied by dominating constraints\n";
       dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned));
     });
     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 (CSToUse.isConditionImplied(ConstraintSystem::negate(R.Coefficients), &Names)) {
     if (!DebugCounter::shouldExecute(EliminatedCounter))
       return false;
 
     LLVM_DEBUG({
       dbgs() << "Condition !" << *Cmp << " implied by dominating constraints\n";
       dumpWithNames(CSToUse, Info.getValue2Index(R.IsSigned));
     });
     Constant *FalseC =
tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info,
                           SmallVectorImpl<Instruction *> &ToRemove) {
   auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,
                               ConstraintInfo &Info) {
     auto R = Info.getConstraintForSolving(Pred, A, B);
     if (R.size() < 2 || !R.isValid(Info))
       return false;
 
     auto &CSToUse = Info.getCS(R.IsSigned);
-    return CSToUse.isConditionImplied(R.Coefficients);
+    auto Value2Index = Info.getValue2Index(R.IsSigned);
+    auto Names = getVarNamesList(Value2Index);
+    return CSToUse.isConditionImplied(R.Coefficients, &Names);
   };
 
   bool Changed = false;
   if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
     // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and
     // can be simplified to a regular sub.
     Value *A = II->getArgOperand(0);
     Value *B = II->getArgOperand(1);