[ConstraintElim] Add reproducer remarks.

[fhahn]

Summary

This patch adds an optimization remark for each performed optimization
containing a module that can be used to reproduce the transformation.

The reproducer function contains a series of @llvm.assume calls, one for
each condition currently in scope. For each condition, the operand
instruction are cloned until we reach operands that have an entry in the
constraint system. Those will then be added as function arguments.

The reproducer functions are minimal, that is, they only contain the
conditions required for a given simplification. The resulting IR is very
compact and can be used to verify each transformation individually.

It also provides a python script to extract the IR from the remarks and
create LLVM IR files from it.

[paquette]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

757–912

doxygen comments for this?

770

Can you document this parameter?

782

This lambda is long enough that I feel like it ought to just be a function (if possible)

825

These loops can be merged into one loop

[tschuett]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

757–912

You can, may, or should wrap the struct with an anonymous namespace. You are very careful with static.

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

757–912

Added comment and moved to anon namespace, thanks!

770

Documented the missing arguments, thanks!

782

Hmm, it would be possible but would mean passing a bunch of extra parameters that can conveniently be captured here. Happy to move it out if you think it is strictly better, but IMO having the lambda keeps it a bit simpler and limits the scope to the function here.

825

Done, thanks!

[fhahn]

Address comments, thanks!

[fhahn]

ping :)

[paquette]

Only things I can think of that would be nice to add are

• Some debug output, if possible
• Comments for the lambdas + some of the loops

Other than that, this LGTM.

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

786

Could this have a comment that outlines which part it plays in the overall algorithm?

828

A comment here would be useful for future readers as well.

838

This can use a comment too (even though the name is pretty descriptive, it does some other stuff such as sorting the instructions)

865

Comment on this loop too?

[fhahn]

Thanks Jessica! The committed version should include additional comments, a bit of extra debug output + a test for the output.

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

 
 #include "llvm/Transforms/Scalar/ConstraintElimination.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstraintSystem.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/Verifier.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/DebugCounter.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
 
 #include <cmath>
 #include <string>
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "constraint-elimination"
 
 STATISTIC(NumCondsRemoved, "Number of instructions removed");
 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
               "Controls which conditions are eliminated");
 
 static cl::opt<unsigned>
     MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden,
             cl::desc("Maximum number of rows to keep in constraint system"));
 
+static cl::opt<bool> DumpReproducers(
+    "constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden,
+    cl::desc("Dump IR to reproduce successful transformations."));
+
 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();
 static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min();
 
 // A helper to multiply 2 signed integers where overflowing is allowed.
 static int64_t multiplyWithOverflow(int64_t A, int64_t B) {
   int64_t Result;
   MulOverflow(A, B, Result);
   return Result;
void State::addInfoFor(BasicBlock &BB) {
   if (canAddSuccessor(BB, Br->getSuccessor(0)))
     WorkList.emplace_back(
         FactOrCheck::getFact(DT.getNode(Br->getSuccessor(0)), CmpI));
   if (canAddSuccessor(BB, Br->getSuccessor(1)))
     WorkList.emplace_back(
         FactOrCheck::getFact(DT.getNode(Br->getSuccessor(1)), CmpI, true));
 }
 
-static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info) {
+namespace {
+/// Helper to keep track of a condition and if it should be treated as negated
+/// for reproducer construction.
+struct ReproducerEntry {
+  CmpInst *Cond;
+  bool IsNot;
+
+  ReproducerEntry(CmpInst *Cond, bool IsNot) : Cond(Cond), IsNot(IsNot) {}
+};
+} // namespace
+
+/// Helper function to generate a reproducer function for simplifying \p Cond.
+/// The reproducer function contains a series of @llvm.assume calls, one for
+/// each condition in \p Stack. For each condition, the operand instruction are
+/// cloned until we reach operands that have an entry in \p Value2Index. Those
+/// will then be added as function arguments. \p DT is used to order cloned
+/// instructions. The reproducer function will get added to \p M, if it is
+/// non-null. Otherwise no reproducer function is generated.
+static void generateReproducer(CmpInst *Cond, Module *M,
+                               ArrayRef<ReproducerEntry> Stack,
+                               ConstraintInfo &Info, DominatorTree &DT) {
+  if (!M)
+    return;
+
+  LLVMContext &Ctx = Cond->getContext();
+
+  LLVM_DEBUG(dbgs() << "Creating reproducer for " << *Cond << "\n");
+
+  ValueToValueMapTy Old2New;
+  SmallVector<Value *> Args;
+  SmallPtrSet<Value *, 8> Seen;
+  // Traverse Cond and its operands recursively until we reach a value that's in
+  // Value2Index or not an instruction, or not a operation that
+  // ConstraintElimination can decompose. Such values will be considered as
+  // external inputs to the reproducer, they are collected and added as function
+  // arguments later.
+  auto CollectArguments = [&](CmpInst *Cond) {
+    if (!Cond)
+      return;
+    auto &Value2Index =
+        Info.getValue2Index(CmpInst::isSigned(Cond->getPredicate()));
+    SmallVector<Value *, 4> WorkList;
+    WorkList.push_back(Cond);
+    while (!WorkList.empty()) {
+      Value *V = WorkList.pop_back_val();
+      if (!Seen.insert(V).second)
+        continue;
+      if (Old2New.find(V) != Old2New.end())
+        continue;
+      if (isa<Constant>(V))
+        continue;
+
+      auto *I = dyn_cast<Instruction>(V);
+      if (Value2Index.find(V) != Value2Index.end() || !I ||
+          !isa<CmpInst, BinaryOperator, GetElementPtrInst, CastInst>(V)) {
+        Old2New[V] = V;
+        Args.push_back(V);
+        LLVM_DEBUG(dbgs() << "  found external input " << *V << "\n");
+      } else {
+        append_range(WorkList, I->operands());
+      }
+    }
+  };
+
+  for (auto &Entry : Stack)
+    CollectArguments(Entry.Cond);
+  CollectArguments(Cond);
+
+  SmallVector<Type *> ParamTys;
+  for (auto *P : Args)
+    ParamTys.push_back(P->getType());
+
+  FunctionType *FTy = FunctionType::get(Cond->getType(), ParamTys,
+                                        /*isVarArg=*/false);
+  Function *F = Function::Create(FTy, Function::ExternalLinkage,
+                                 Cond->getModule()->getName() +
+                                     Cond->getFunction()->getName() + "repro",
+                                 M);
+  // Add arguments to the reproducer function for each external value collected.
+  for (unsigned I = 0; I < Args.size(); ++I) {
+    F->getArg(I)->setName(Args[I]->getName());
+    Old2New[Args[I]] = F->getArg(I);
+  }
+
+  BasicBlock *Entry = BasicBlock::Create(Ctx, "entry", F);
+  IRBuilder<> Builder(Entry);
+  Builder.CreateRet(Builder.getTrue());
+  Builder.SetInsertPoint(Entry->getTerminator());
+
+  // Clone instructions in \p Ops and their operands recursively until reaching
+  // an value in Value2Index (external input to the reproducer). Update Old2New
+  // mapping for the original and cloned instructions. Sort instructions to
+  // clone by dominance, then insert the cloned instructions in the function.
+  auto CloneInstructions = [&](ArrayRef<Value *> Ops, bool IsSigned) {
+    SmallVector<Value *, 4> WorkList(Ops);
+    SmallVector<Instruction *> ToClone;
+    auto &Value2Index = Info.getValue2Index(IsSigned);
+    while (!WorkList.empty()) {
+      Value *V = WorkList.pop_back_val();
+      if (Old2New.find(V) != Old2New.end())
+        continue;
+
+      auto *I = dyn_cast<Instruction>(V);
+      if (Value2Index.find(V) == Value2Index.end() && I) {
+        Old2New[V] = nullptr;
+        ToClone.push_back(I);
+        append_range(WorkList, I->operands());
+      }
+    }
+
+    sort(ToClone,
+         [&DT](Instruction *A, Instruction *B) { return DT.dominates(A, B); });
+    for (Instruction *I : ToClone) {
+      Instruction *Cloned = I->clone();
+      Old2New[I] = Cloned;
+      Old2New[I]->setName(I->getName());
+      Cloned->insertBefore(&*Builder.GetInsertPoint());
+      Cloned->dropUnknownNonDebugMetadata();
+      Cloned->setDebugLoc({});
+    }
+  };
+
+  // Materialize the assumptions for the reproducer using the entries in Stack.
+  // That is, first clone the operands of the condition recursively until we
+  // reach an external input to the reproducer and add them to the reproducer
+  // function. Then add an ICmp for the condition (with the inverse predicate if
+  // the entry is negated) and an assert using the ICmp.
+  for (auto &Entry : Stack) {
+    if (!Entry.Cond)
+      continue;
+
+    LLVM_DEBUG(dbgs() << "  Materializing assumption " << *Entry.Cond << "\n");
+    CmpInst::Predicate Pred = Entry.Cond->getPredicate();
+    if (Entry.IsNot)
+      Pred = CmpInst::getInversePredicate(Pred);
+
+    CloneInstructions({Entry.Cond->getOperand(0), Entry.Cond->getOperand(1)},
+                      CmpInst::isSigned(Entry.Cond->getPredicate()));
+
+    auto *Cmp = Builder.CreateICmp(Pred, Entry.Cond->getOperand(0),
+                                   Entry.Cond->getOperand(1));
+    Builder.CreateAssumption(Cmp);
+  }
+
+  // Finally, clone the condition to reproduce and remap instruction operands in
+  // the reproducer using Old2New.
+  CloneInstructions(Cond, CmpInst::isSigned(Cond->getPredicate()));
+  Entry->getTerminator()->setOperand(0, Cond);
+  remapInstructionsInBlocks({Entry}, Old2New);
+
+  assert(!verifyFunction(*F, &dbgs()));
+}
+
+static bool checkAndReplaceCondition(
+    CmpInst *Cmp, ConstraintInfo &Info, Module *ReproducerModule,
+    ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT) {
   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);
   if (R.empty() || !R.isValid(Info)){
static bool checkAndReplaceCondition(
   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));
     });
+    generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);
     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));
     });
+    generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);
     Constant *FalseC =
         ConstantInt::getFalse(CmpInst::makeCmpResultType(Cmp->getType()));
     Cmp->replaceAllUsesWith(FalseC);
     NumCondsRemoved++;
     Changed = true;
   }
   return Changed;
 }
if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||
         !DoesConditionHold(CmpInst::ICMP_SGE, B,
                            ConstantInt::get(A->getType(), 0), Info))
       return false;
     Changed = replaceSubOverflowUses(II, A, B, ToRemove);
   }
   return Changed;
 }
 
-static bool eliminateConstraints(Function &F, DominatorTree &DT) {
+static bool eliminateConstraints(Function &F, DominatorTree &DT,
+                                 OptimizationRemarkEmitter &ORE) {
   bool Changed = false;
   DT.updateDFSNumbers();
 
   ConstraintInfo Info(F.getParent()->getDataLayout());
   State S(DT);
+  std::unique_ptr<Module> ReproducerModule(
+      DumpReproducers ? new Module(F.getName(), F.getContext()) : nullptr);
 
   // First, collect conditions implied by branches and blocks with their
   // Dominator DFS in and out numbers.
   for (BasicBlock &BB : F) {
     if (!DT.getNode(&BB))
       continue;
     S.addInfoFor(BB);
   }
stable_sort(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) {
     }
     return A.NumIn < B.NumIn;
   });
 
   SmallVector<Instruction *> ToRemove;
 
   // Finally, process ordered worklist and eliminate implied conditions.
   SmallVector<StackEntry, 16> DFSInStack;
+  SmallVector<ReproducerEntry> ReproducerCondStack;
   for (FactOrCheck &CB : S.WorkList) {
     // First, pop entries from the stack that are out-of-scope for CB. Remove
     // the corresponding entry from the constraint system.
     while (!DFSInStack.empty()) {
       auto &E = DFSInStack.back();
       LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
                         << "\n");
       LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
while (!DFSInStack.empty()) {
 
       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);
       Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
       DFSInStack.pop_back();
+      if (ReproducerModule)
+        ReproducerCondStack.pop_back();
     }
 
     LLVM_DEBUG({
       dbgs() << "Processing ";
       if (CB.IsCheck)
         dbgs() << "condition to simplify: " << *CB.Inst;
       else
         dbgs() << "fact to add to the system: " << *CB.Inst;
       dbgs() << "\n";
     });
 
     // For a block, check if any CmpInsts become known based on the current set
     // of constraints.
     if (CB.IsCheck) {
       if (auto *II = dyn_cast<WithOverflowInst>(CB.Inst)) {
         Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
       } else if (auto *Cmp = dyn_cast<ICmpInst>(CB.Inst)) {
-        Changed |= checkAndReplaceCondition(Cmp, Info);
+        Changed |= checkAndReplaceCondition(Cmp, Info, ReproducerModule.get(),
+                                            ReproducerCondStack, S.DT);
       }
       continue;
     }
 
     ICmpInst::Predicate Pred;
     Value *A, *B;
     Value *Cmp = CB.Inst;
     match(Cmp, m_Intrinsic<Intrinsic::assume>(m_Value(Cmp)));
     if (match(Cmp, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
       if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) {
         LLVM_DEBUG(
             dbgs()
             << "Skip adding constraint because system has too many rows.\n");
         continue;
       }
 
       // Use the inverse predicate if required.
       if (CB.Not)
         Pred = CmpInst::getInversePredicate(Pred);
 
       Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
+      if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())
+        ReproducerCondStack.emplace_back(cast<CmpInst>(Cmp), CB.Not);
+
       Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
+      if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) {
+        // Add dummy entries to ReproducerCondStack to keep it in sync with
+        // DFSInStack.
+        for (unsigned I = 0,
+                      E = (DFSInStack.size() - ReproducerCondStack.size());
+             I < E; ++I) {
+          ReproducerCondStack.emplace_back(nullptr, false);
+        }
+      }
     }
   }
 
+  if (ReproducerModule && !ReproducerModule->functions().empty()) {
+    std::string S;
+    raw_string_ostream StringS(S);
+    ReproducerModule->print(StringS, nullptr);
+    StringS.flush();
+    OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F);
+    Rem << ore::NV("module") << S;
+    ORE.emit(Rem);
+  }
+
 #ifndef NDEBUG
   unsigned SignedEntries =
       count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
   assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries &&
          "updates to CS and DFSInStack are out of sync");
   assert(Info.getCS(true).size() == SignedEntries &&
          "updates to CS and DFSInStack are out of sync");
 #endif
 
   for (Instruction *I : ToRemove)
     I->eraseFromParent();
   return Changed;
 }
 
 PreservedAnalyses ConstraintEliminationPass::run(Function &F,
                                                  FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
-  if (!eliminateConstraints(F, DT))
+  auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
+  if (!eliminateConstraints(F, DT, ORE))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserveSet<CFGAnalyses>();
   return PA;
 }

llvm/test/Transforms/ConstraintElimination/analysis-invalidation.ll

 ; RUN: opt -passes='require<demanded-bits>,constraint-elimination,require<demanded-bits>' -disable-verify -verify-cfg-preserved=false -debug-pass-manager -disable-output %s 2>&1 | FileCheck %s
 
 ; Check that constraint-elimination properly invalidates anlyses.
 
 ; FIXME: ssub simplification currently doesn't properly set the change status
 ;        after modifying the IR, which causes DemandedBits to be preserved.
 
 ; CHECK:      Running pass: RequireAnalysisPass
 ; CHECK-NEXT: Running analysis: DemandedBitsAnalysis on ssub_no_overflow_due_to_or_conds
 ; CHECK-NEXT: Running analysis: AssumptionAnalysis on ssub_no_overflow_due_to_or_conds
 ; CHECK-NEXT: Running analysis: TargetIRAnalysis on ssub_no_overflow_due_to_or_conds
 ; CHECK-NEXT: Running analysis: DominatorTreeAnalysis on ssub_no_overflow_due_to_or_conds
 ; CHECK-NEXT: Running pass: ConstraintEliminationPass on ssub_no_overflow_due_to_or_conds
+; CHECK-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis on ssub_no_overflow_due_to_or_conds
 ; CHECK-NEXT: Invalidating analysis: DemandedBitsAnalysis on ssub_no_overflow_due_to_or_conds
 ; CHECK-NEXT: Running pass: RequireAnalysisPass
 ; CHECK-NEXT: Running analysis: DemandedBitsAnalysis on ssub_no_overflow_due_to_or_conds
 
 ; CHECK-NEXT: Running pass: RequireAnalysisPass
 ; CHECK-NEXT: Running analysis: DemandedBitsAnalysis on uge_zext
 ; CHECK-NEXT: Running analysis: AssumptionAnalysis on uge_zext
 ; CHECK-NEXT: Running analysis: TargetIRAnalysis on uge_zext
 ; CHECK-NEXT: Running analysis: DominatorTreeAnalysis on uge_zext
 ; CHECK-NEXT: Running pass: ConstraintEliminationPass on uge_zext
+; CHECK-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis on uge_zext
 ; CHECK-NEXT: Invalidating analysis: DemandedBitsAnalysis on uge_zext
 ; CHECK-NEXT: Running pass: RequireAnalysisPass
 ; CHECK-NEXT: Running analysis: DemandedBitsAnalysis on uge_zext
 
 declare { i8, i1 } @llvm.ssub.with.overflow.i8(i8, i8)
 
 define i8 @ssub_no_overflow_due_to_or_conds(i8 %a, i8 %b) {
 entry:

llvm/test/Transforms/ConstraintElimination/reproducer-remarks-debug.ll

+; RUN: opt -passes=constraint-elimination -constraint-elimination-dump-reproducers -pass-remarks=constraint-elimination -debug %s 2>&1 | FileCheck %s
+
+; REQUIRES: asserts
+
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+; CHECK:      Condition   %c.2 = icmp eq ptr %a, null implied by dominating constraints
+; CHECK-NEXT: %a + -1 * % <= 0
+; CHECK-NEXT: Creating reproducer for   %c.2 = icmp eq ptr %a, null
+; CHECK-NEXT:   found external input ptr %a
+; CHECK-NEXT:   Materializing assumption   %c.1 = icmp eq ptr %a, null
+; CHECK-NEXT: ---
+
+define i1 @test_ptr_null_constant(ptr %a) {
+; CHECK-LABEL: define i1 @"{{.+}}test_ptr_null_constantrepro"(ptr %a) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %0 = icmp eq ptr %a, null
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %c.2 = icmp eq ptr %a, null
+; CHECK-NEXT:   ret i1 %c.2
+; CHECK-NEXT: }
+;
+entry:
+  %c.1 = icmp eq ptr %a, null
+  br i1 %c.1, label %then, label %else
+
+then:
+  %c.2 = icmp eq ptr %a, null
+  ret i1 %c.2
+
+else:
+  ret i1 false
+}

llvm/test/Transforms/ConstraintElimination/reproducer-remarks.ll

+; RUN: opt -passes=constraint-elimination -constraint-elimination-dump-reproducers -pass-remarks=constraint-elimination %s 2>&1 | FileCheck %s
+
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+declare void @use(i1)
+
+declare void @llvm.assume(i1)
+
+define i1 @test_no_known_facts(ptr %dst) {
+; CHECK: remark: <unknown>:0:0: module; ModuleID = 'test_no_known_facts'
+; CHECK-LABEL: define i1 @"{{.+}}test_no_known_factsrepro"(ptr %dst)
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    %dst.0 = getelementptr inbounds ptr, ptr %dst, i64 0
+; CHECK-NEXT:    %upper = getelementptr inbounds ptr, ptr %dst, i64 2
+; CHECK-NEXT:    %c = icmp ult ptr %dst.0, %upper
+; CHECK-NEXT:    ret i1 %c
+; CHECK-NEXT:  }
+;
+entry:
+  %dst.0 = getelementptr inbounds ptr, ptr %dst, i64 0
+  %upper = getelementptr inbounds ptr, ptr %dst, i64 2
+  %c = icmp ult i32* %dst.0, %upper
+  ret i1 %c
+}
+
+define void @test_one_known_fact_true_branch(i8 %start, i8 %high) {
+; CHECK: remark: <unknown>:0:0: module; ModuleID = 'test_one_known_fact_true_branch'
+
+; CHECK-LABEL: define i1 @"{{.*}}test_one_known_fact_true_branchrepro"(i8 %high, i8 %start) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %add.ptr.i = add nuw i8 %start, 3
+; CHECK-NEXT:   %0 = icmp ult i8 %add.ptr.i, %high
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %t.0 = icmp ult i8 %start, %high
+; CHECK-NEXT:   ret i1 %t.0
+; CHECK-NEXT: }
+;
+entry:
+  %add.ptr.i = add nuw i8 %start, 3
+  %c.1 = icmp ult i8 %add.ptr.i, %high
+  br i1 %c.1, label %if.then, label %if.end
+
+if.then:
+  %t.0 = icmp ult i8 %start, %high
+  call void @use(i1 %t.0)
+  ret void
+
+if.end:
+  ret void
+}
+
+define void @test_one_known_fact_false_branch(i8 %start, i8 %high) {
+; CHECK: remark: <unknown>:0:0: module; ModuleID = 'test_one_known_fact_false_branch'
+;
+; CHECK-LABEL:define i1 @"{{.*}}test_one_known_fact_false_branchrepro"(i8 %high, i8 %start) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %add.ptr.i = add nuw i8 %start, 3
+; CHECK-NEXT:   %0 = icmp ult i8 %add.ptr.i, %high
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %t.0 = icmp ult i8 %start, %high
+; CHECK-NEXT:   ret i1 %t.0
+; CHECK-NEXT: }
+;
+entry:
+  %add.ptr.i = add nuw i8 %start, 3
+  %c.1 = icmp uge i8 %add.ptr.i, %high
+  br i1 %c.1, label %if.then, label %if.end
+
+if.then:
+  ret void
+
+if.end:
+  %t.0 = icmp ult i8 %start, %high
+  call void @use(i1 %t.0)
+  ret void
+}
+
+define void @test_multiple_known_facts_branches_1(i8 %a, i8 %b) {
+; CHECK: remark: <unknown>:0:0: module; ModuleID = 'test_multiple_known_facts_branches_1'
+
+; CHECK-LABEL: define i1 @"{{.*}}test_multiple_known_facts_branches_1repro"(i8 %a, i8 %b) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %0 = icmp ugt i8 %a, 10
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %1 = icmp ugt i8 %b, 10
+; CHECK-NEXT:   call void @llvm.assume(i1 %1)
+; CHECK-NEXT:   %add = add nuw i8 %a, %b
+; CHECK-NEXT:   %t.0 = icmp ugt i8 %add, 20
+; CHECK-NEXT:   ret i1 %t.0
+; CHECK-NEXT: }
+;
+entry:
+  %c.1 = icmp ugt i8 %a, 10
+  br i1 %c.1, label %then.1, label %else.1
+
+then.1:
+  %c.2 = icmp ugt i8 %b, 10
+  br i1 %c.2, label %then.2, label %else.1
+
+then.2:
+  %add = add nuw i8 %a, %b
+  %t.0 = icmp ugt i8 %add, 20
+  call void @use(i1 %t.0)
+  ret void
+
+else.1:
+  ret void
+}
+
+define void @test_multiple_known_facts_branches_2(i8 %a, i8 %b) {
+; CHECK: remark: <unknown>:0:0: module; ModuleID = 'test_multiple_known_facts_branches_2'
+;
+; CHECK-LABEL: define i1 @"{{.*}}test_multiple_known_facts_branches_2repro"(i8 %a, i8 %b) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %0 = icmp ugt i8 %a, 10
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %1 = icmp ugt i8 %b, 10
+; CHECK-NEXT:   call void @llvm.assume(i1 %1)
+; CHECK-NEXT:   %add = add nuw i8 %a, %b
+; CHECK-NEXT:   %t.0 = icmp ugt i8 %add, 20
+; CHECK-NEXT:   ret i1 %t.0
+; CHECK-NEXT: }
+;
+entry:
+  %c.1 = icmp ugt i8 %a, 10
+  br i1 %c.1, label %then.1, label %exit
+
+then.1:
+  %c.2 = icmp ule i8 %b, 10
+  br i1 %c.2, label %exit, label %else.2
+
+else.2:
+  %add = add nuw i8 %a, %b
+  %t.0 = icmp ugt i8 %add, 20
+  call void @use(i1 %t.0)
+  ret void
+
+exit:
+  ret void
+}
+
+define void @test_assumes(i8 %a, i8 %b) {
+; CHECK-LABEL: define i1 @"{{.*}}test_assumesrepro.2"(i8 %a, i8 %b) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %0 = icmp ugt i8 %a, 10
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %1 = icmp ugt i8 %b, 10
+; CHECK-NEXT:   call void @llvm.assume(i1 %1)
+; CHECK-NEXT:   %add = add nuw i8 %a, %b
+; CHECK-NEXT:   %t.0 = icmp ult i8 %add, 20
+; CHECK-NEXT:   ret i1 %t.0
+; CHECK-NEXT: }
+;
+entry:
+  %c.1 = icmp ugt i8 %a, 10
+  call void @llvm.assume(i1 %c.1)
+  %c.2 = icmp ugt i8 %b, 10
+  call void @llvm.assume(i1 %c.2)
+  %add = add nuw i8 %a, %b
+  %t.0 = icmp ult i8 %add, 20
+  call void @use(i1 %t.0)
+  ret void
+}
+
+declare void @noundef(ptr noundef)
+
+; Currently this fails decomposition. No reproducer should be generated.
+define i1 @test_inbounds_precondition(ptr %src, i32 %n, i32 %idx) {
+; CHECK-NOT: test_inbounds_precondition
+entry:
+  %upper = getelementptr inbounds i32, ptr %src, i64 5
+  %src.idx.4 = getelementptr i32, ptr %src, i64 4
+  %cmp.upper.4 = icmp ule ptr %src.idx.4, %upper
+  br i1 %cmp.upper.4, label %then, label %else
+
+then:
+  ret i1 true
+
+else:
+  ret i1 false
+}
+
+define i32 @test_branch(i32 %a) {
+; CHECK-LABEL: define i1 @"{{.+}}test_branchrepro"(i32 %a) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %0 = icmp ult i32 %a, 0
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %c.2 = icmp ugt i32 0, 0
+; CHECK-NEXT:   ret i1 %c.2
+; CHECK-NEXT: }
+;
+entry:
+  %c.1 = icmp ult i32 %a, 0
+  br i1 %c.1, label %then, label %exit
+
+then:
+  %c.2 = icmp ugt i32 0, 0
+  br label %exit
+
+exit:
+  ret i32 0
+}
+
+define i32 @test_invoke(i32 %a) personality ptr null {
+; CHECK-LABEL: define i1 @"{{.+}}test_invokerepro"(i32 %l, i32 %a) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:  %0 = icmp slt i32 %a, %l
+; CHECK-NEXT:  call void @llvm.assume(i1 %0)
+; CHECK-NEXT:  %c.2 = icmp eq i32 0, 0
+; CHECK-NEXT:  ret i1 %c.2
+; CHECK-NEXT:}
+;
+entry:
+  %call = invoke ptr null(i64 0)
+          to label %cont unwind label %lpad
+
+cont:
+  %l = load i32, ptr %call, align 4
+  %c.1 = icmp slt i32 %a, %l
+  br i1 %c.1, label %then, label %exit
+
+lpad:
+  %lp = landingpad { ptr, i32 }
+          catch ptr null
+          catch ptr null
+  ret i32 0
+
+then:
+  %c.2 = icmp eq i32 0, 0
+  br label %exit
+
+exit:
+  ret i32 0
+}
+
+define <2 x i1> @vector_cmp(<2 x ptr> %vec) {
+; CHECK-LABEL: define <2 x i1> @"{{.+}}vector_cmprepro"(<2 x ptr> %vec) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %gep.1 = getelementptr inbounds i32, <2 x ptr> %vec, i64 1
+; CHECK-NEXT:   %t.1 = icmp ult <2 x ptr> %vec, %gep.1
+; CHECK-NEXT:   ret <2 x i1> %t.1
+; CHECK-NEXT: }
+;
+  %gep.1 = getelementptr inbounds i32, <2 x ptr> %vec, i64 1
+  %t.1 = icmp ult <2 x ptr> %vec, %gep.1
+  ret <2 x i1> %t.1
+}
+
+define i1 @shared_operand() {
+; CHECK-LABEL: define i1 @"{{.+}}shared_operandrepro"() {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %sub = sub i8 0, 0
+; CHECK-NEXT:   %sub.2 = sub nuw i8 %sub, 0
+; CHECK-NEXT:   %c.5 = icmp ult i8 %sub.2, %sub
+; CHECK-NEXT:   ret i1 %c.5
+; CHECK-NEXT: }
+;
+entry:
+  %sub = sub i8 0, 0
+  %sub.2 = sub nuw i8 %sub, 0
+  %c.5 = icmp ult i8 %sub.2, %sub
+  ret i1 %c.5
+}
+
+@glob = external global i32
+
+define i1 @load_global() {
+; CHECK-LABEL: define i1 @"{{.*}}load_globalrepro"(i32 %l) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:  %c = icmp ugt i32 %l, %l
+; CHECK-NEXT:  ret i1 %c
+; CHECK-NEXT:}
+;
+entry:
+  %l = load i32, ptr @glob, align 8
+  %c = icmp ugt i32 %l, %l
+  ret i1 %c
+}
+
+define i1 @test_ptr_null_constant(ptr %a) {
+; CHECK-LABEL: define i1 @"{{.+}}test_ptr_null_constantrepro"(ptr %a) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %0 = icmp eq ptr %a, null
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %c.2 = icmp eq ptr %a, null
+; CHECK-NEXT:   ret i1 %c.2
+; CHECK-NEXT: }
+;
+entry:
+  %c.1 = icmp eq ptr %a, null
+  br i1 %c.1, label %then, label %else
+
+then:
+  %c.2 = icmp eq ptr %a, null
+  ret i1 %c.2
+
+else:
+  ret i1 false
+}
+
+define i1 @test_both_signed_and_unsigned_conds_needed_in_reproducer(ptr %src, ptr %lower, ptr %upper, i16 %N) {
+; CHECK-LABEL: define i1 @"{{.+}}test_both_signed_and_unsigned_conds_needed_in_reproducerrepro"(i16 %N, ptr %src) {
+; CHECK-NEXT: entry:
+; CHECK-NEXT:   %0 = icmp sge i16 %N, 0
+; CHECK-NEXT:   call void @llvm.assume(i1 %0)
+; CHECK-NEXT:   %src.end = getelementptr inbounds i8, ptr %src, i16 %N
+; CHECK-NEXT:   %cmp.src.start = icmp ule ptr %src, %src.end
+; CHECK-NEXT:   ret i1 %cmp.src.start
+; CHECK-NEXT: }
+;
+entry:
+  %N.pos = icmp sge i16 %N, 0
+  br i1 %N.pos, label %then, label %else
+
+then:
+  %src.end = getelementptr inbounds i8, ptr %src, i16 %N
+  %cmp.src.start = icmp ule ptr %src, %src.end
+  ret i1 %cmp.src.start
+
+else:
+  ret i1 false
+}

llvm/tools/opt-viewer/extract-reproducers.py

+#!/usr/bin/env python
+
+desc = '''
+A script to extract ConstraintElimination's reproducer remarks. The extracted
+modules are written as textual LLVM IR to files named reproducerXXXX.ll in the
+current directory.
+'''
+
+import optrecord
+import argparse
+
+if __name__ == '__main__':
+    parser = argparse.ArgumentParser(description=desc)
+    parser.add_argument(
+        'yaml_dirs_or_files',
+        nargs='+',
+        help='List of optimization record files or directories searched '
+             'for optimization record files.')
+
+    args = parser.parse_args()
+
+    print_progress = False
+    jobs = 1
+
+    files = optrecord.find_opt_files(*args.yaml_dirs_or_files)
+    if not files:
+        parser.error("No *.opt.yaml files found")
+        sys.exit(1)
+
+    all_remarks, file_remarks, _ = optrecord.gather_results(
+        files, jobs, True)
+
+    i = 0
+    for r in all_remarks:
+        if r[1] != 'constraint-elimination' or r[2] != 'Reproducer':
+            continue
+        with open('reproducer{}.ll'.format(i), 'wt') as f:
+            f.write(r[7][1][0][1])
+        i += 1