[llvm-reduce] Add option to reduce values to zero instead of undef

[aeubanks]

Summary

When creating minimal reproducers, having many undefs everywhere is not
ideal. Using zero produces cleaner minimal reproducers.

[nikic]

This looks pretty reasonable to me, but I'm not particularly familiar with llvm-reduce.

[Meinersbur]

I was working on such a change myself.

One remark here: Replacing a pointer by a NULL value can have a similar destructive effects like undef. When replacing an LoadInst or StoreInst address with NULL, it is introducing undefined behaviour where there was none before and make test cases reduced this way useless. Could we also optionally not replace pointers with null values? Similar though might also apply to the divisor of a divide/remainder operation.

I made a delta pass that converts these to function arguments instead and could upstream it.

[aeubanks]

In D110274#3023542, @Meinersbur wrote:

I was working on such a change myself.

One remark here: Replacing a pointer by a NULL value can have a similar destructive effects like undef. When replacing an LoadInst or StoreInst address with NULL, it is introducing undefined behaviour where there was none before and make test cases reduced this way useless. Could we also optionally not replace pointers with null values? Similar though might also apply to the divisor of a divide/remainder operation.

We can change the reduce operands pass to not reduce those specific operands, although that's orthogonal to this change since this change makes things more defined as null is more defined than undef.

I made a delta pass that converts these to function arguments instead and could upstream it.

Yeah that sounds good. I'm worried that we'll end up creating functions with a ton of arguments, but we can land it and see if anybody complains.
Or do you mean specifically convert load/store pointer operands and div/rem divisor operands to arguments?

[fhahn]

In D110274#3025013, @aeubanks wrote:

In D110274#3023542, @Meinersbur wrote:

I was working on such a change myself.

One remark here: Replacing a pointer by a NULL value can have a similar destructive effects like undef. When replacing an LoadInst or StoreInst address with NULL, it is introducing undefined behaviour where there was none before and make test cases reduced this way useless. Could we also optionally not replace pointers with null values? Similar though might also apply to the divisor of a divide/remainder operation.

We can change the reduce operands pass to not reduce those specific operands, although that's orthogonal to this change since this change makes things more defined as null is more defined than undef.

I made a delta pass that converts these to function arguments instead and could upstream it.

Yeah that sounds good. I'm worried that we'll end up creating functions with a ton of arguments, but we can land it and see if anybody complains.
Or do you mean specifically convert load/store pointer operands and div/rem divisor operands to arguments?

@Meinersbur I think it would be great if you could share that patch. I don't think adding arguments is a problem per-se, especially if it is limited to a small set of functions required in the final reproducer. One of the main benefits of replacing undef is reducing new sources of UB, which adding arguments would achieve. There also should be a couple of things we could do to try to keep the number of extra arguments in check, e.g. trying to re-use arguments.

[aeubanks]

ping

[Meinersbur]

In D110274#3041959, @fhahn wrote:

@Meinersbur I think it would be great if you could share that patch. I don't think adding arguments is a problem per-se, especially if it is limited to a small set of functions required in the final reproducer. One of the main benefits of replacing undef is reducing new sources of UB, which adding arguments would achieve. There also should be a couple of things we could do to try to keep the number of extra arguments in check, e.g. trying to re-use arguments.

D111503

I have another pass that "compresses" arguments by reusing other values of the same type s.t. that some become unused and are removed by the argument reduction pass.

[Meinersbur]

@aeubanks Can I have enabled Undef values but reduce to zero constants too, in case Zero still triggers the bug, but not Undef? In my experience, constant one (for integers) also helped reducing further.

What I have been using is a "reduce-to-one", "reduce-to-zero" and "reduce-to-undef" pass. reduce-to-one would not reduce anything that is already one, zero, or undef (to ensure we can reach a fixpoint). reduce-to-zero does not change anything that is already zero or undef. reduce-to-undef can reduce what is not already undef. To not have undef appear in the reduction output, I would just not run the reduce-to-undef pass.

Thoughts?

[aeubanks]

In D110274#3061561, @Meinersbur wrote:

@aeubanks Can I have enabled Undef values but reduce to zero constants too, in case Zero still triggers the bug, but not Undef? In my experience, constant one (for integers) also helped reducing further.

What I have been using is a "reduce-to-one", "reduce-to-zero" and "reduce-to-undef" pass. reduce-to-one would not reduce anything that is already one, zero, or undef (to ensure we can reach a fixpoint). reduce-to-zero does not change anything that is already zero or undef. reduce-to-undef can reduce what is not already undef. To not have undef appear in the reduction output, I would just not run the reduce-to-undef pass.

Thoughts?

Specifically for the reduce-operands pass I agree it would be much nicer to attempt to reduce to undef/1/0, probably in that order (so we get as many 0s as possible and as few undefs as possible).

This patch touches more than just reduce-operands though, and now I think in the other passes it probably doesn't matter as much exactly what we reduce things to since we'll clean things up in the reduce-operands pass. So I guess I've talked myself out of this patch.

[aeubanks]

In D110274#3062642, @aeubanks wrote:

In D110274#3061561, @Meinersbur wrote:

@aeubanks Can I have enabled Undef values but reduce to zero constants too, in case Zero still triggers the bug, but not Undef? In my experience, constant one (for integers) also helped reducing further.

What I have been using is a "reduce-to-one", "reduce-to-zero" and "reduce-to-undef" pass. reduce-to-one would not reduce anything that is already one, zero, or undef (to ensure we can reach a fixpoint). reduce-to-zero does not change anything that is already zero or undef. reduce-to-undef can reduce what is not already undef. To not have undef appear in the reduction output, I would just not run the reduce-to-undef pass.

Thoughts?

Specifically for the reduce-operands pass I agree it would be much nicer to attempt to reduce to undef/1/0, probably in that order (so we get as many 0s as possible and as few undefs as possible).

This patch touches more than just reduce-operands though, and now I think in the other passes it probably doesn't matter as much exactly what we reduce things to since we'll clean things up in the reduce-operands pass. So I guess I've talked myself out of this patch.

https://reviews.llvm.org/D111765

llvm/test/tools/llvm-reduce/remove-operands.ll

 ; Test that llvm-reduce can reduce operands to their default values.
 ;
 ; RUN: llvm-reduce --delta-passes=operands --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
-; RUN: cat %t | FileCheck %s
+; RUN: cat %t | FileCheck %s --check-prefixes=CHECK-FINAL,CHECK-FINAL-UNDEF
+; RUN: llvm-reduce --delta-passes=operands --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t --default-reduced-value=zero
+; RUN: cat %t | FileCheck %s --check-prefixes=CHECK-FINAL,CHECK-FINAL-ZERO
 
 ; CHECK-INTERESTINGNESS: ret i32
 
-; CHECK-LABEL: define i32 @main() {
+; CHECK-FINAL-LABEL: define i32 @main() {
 define i32 @main() {
 
-; CHECK-LABEL: lb1:
-; CHECK-NEXT: br label %lb2
+; CHECK-FINAL-LABEL: lb1:
+; CHECK-FINAL-NEXT: br label %lb2
 lb1:
   br label %lb2
 
-; CHECK-LABEL: lb2:
-; CHECK-NEXT: ret i32 undef
+; CHECK-FINAL-LABEL: lb2:
+; CHECK-FINAL-UNDEF: ret i32 undef
+; CHECK-FINAL-ZERO: ret i32 0
 lb2:
   ret i32 10
 }

llvm/tools/llvm-reduce/deltas/Delta.h

 #include "TestRunner.h"
 #include "llvm/ADT/ScopeExit.h"
 #include <functional>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
+Constant *defaultValueForType(Type *Ty);
+
 struct Chunk {
   int Begin;
   int End;
 
   /// Helper function to verify if a given Target-index is inside the Chunk
   bool contains(int Index) const { return Index >= Begin && Index <= End; }
 
   void print() const {

llvm/tools/llvm-reduce/deltas/Delta.cpp

 //===- Delta.cpp - Delta Debugging Algorithm Implementation ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains the implementation for the Delta Debugging Algorithm:
 // it splits a given set of Targets (i.e. Functions, Instructions, BBs, etc.)
 // into chunks and tries to reduce the number chunks that are interesting.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Delta.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include <fstream>
 #include <set>
 
 using namespace llvm;
 
 static cl::opt<bool> AbortOnInvalidReduction(
     "abort-on-invalid-reduction",
     cl::desc("Abort if any reduction results in invalid IR"));
 
+enum class DefaultReducedValueType { Zero, Undef };
+
+static cl::opt<DefaultReducedValueType> DefaultReducedValue(
+    "default-reduced-value",
+    cl::desc("The type of constant to reduce values to"),
+    cl::init(DefaultReducedValueType::Undef),
+    cl::values(clEnumValN(DefaultReducedValueType::Zero, "zero",
+                          "Reduce values to 0/null/zeroinitializer"),
+               clEnumValN(DefaultReducedValueType::Undef, "undef",
+                          "Reduce values to undef")));
+
+Constant *llvm::defaultValueForType(Type *Ty) {
+  if (Ty->isLabelTy())
+    return nullptr;
+  if (Ty->isVoidTy())
+    return UndefValue::get(Ty);
+  switch (DefaultReducedValue) {
+  case DefaultReducedValueType::Zero:
+    return Constant::getNullValue(Ty);
+  case DefaultReducedValueType::Undef:
+    return UndefValue::get(Ty);
+  }
+}
+
 void writeOutput(llvm::Module *M, llvm::StringRef Message);
 
 bool isReduced(Module &M, TestRunner &Test, SmallString<128> &CurrentFilepath) {
   // Write Module to tmp file
   int FD;
   std::error_code EC =
       sys::fs::createTemporaryFile("llvm-reduce", "ll", FD, CurrentFilepath);
   if (EC) {

llvm/tools/llvm-reduce/deltas/ReduceArguments.cpp

static void extractArgumentsFromModule(std::vector<Chunk> ChunksToKeep,
 
   for (auto *F : Funcs) {
     ValueToValueMapTy VMap;
     std::vector<WeakVH> InstToDelete;
     for (auto &A : F->args())
       if (!ArgsToKeep.count(&A)) {
         // By adding undesired arguments to the VMap, CloneFunction will remove
         // them from the resulting Function
-        VMap[&A] = UndefValue::get(A.getType());
+        VMap[&A] = defaultValueForType(A.getType());
         for (auto *U : A.users())
           if (auto *I = dyn_cast<Instruction>(*&U))
             InstToDelete.push_back(I);
       }
     // Delete any (unique) instruction that uses the argument
     for (Value *V : InstToDelete) {
       if (!V)
         continue;
       auto *I = cast<Instruction>(V);
-      I->replaceAllUsesWith(UndefValue::get(I->getType()));
+      I->replaceAllUsesWith(defaultValueForType(I->getType()));
       if (!I->isTerminator())
         I->eraseFromParent();
     }
 
     // No arguments to reduce
     if (VMap.empty())
       continue;
 

llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp

 //===- ReduceArguments.cpp - Specialized Delta Pass -----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a function which calls the Generic Delta pass in order
 // to reduce uninteresting Arguments from defined functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ReduceBasicBlocks.h"
+#include "deltas/Delta.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/raw_ostream.h"
 #include <vector>
static void replaceBranchTerminator(BasicBlock &BB,
   if (ChunkSucessors.size() == Term->getNumSuccessors())
     return;
 
   bool IsBranch = isa<BranchInst>(Term) || isa<InvokeInst>(Term);
   Value *Address = nullptr;
   if (auto *IndBI = dyn_cast<IndirectBrInst>(Term))
     Address = IndBI->getAddress();
 
-  Term->replaceAllUsesWith(UndefValue::get(Term->getType()));
+  Term->replaceAllUsesWith(defaultValueForType(Term->getType()));
   Term->eraseFromParent();
 
   if (ChunkSucessors.empty()) {
     auto *FnRetTy = BB.getParent()->getReturnType();
-    ReturnInst::Create(BB.getContext(),
-                       FnRetTy->isVoidTy() ? nullptr : UndefValue::get(FnRetTy),
-                       &BB);
+    ReturnInst::Create(
+        BB.getContext(),
+        FnRetTy->isVoidTy() ? nullptr : defaultValueForType(FnRetTy), &BB);
     return;
   }
 
   if (IsBranch)
     BranchInst::Create(ChunkSucessors[0], &BB);
 
   if (Address) {
     auto *NewIndBI =
         IndirectBrInst::Create(Address, ChunkSucessors.size(), &BB);
     for (auto *Dest : ChunkSucessors)
       NewIndBI->addDestination(Dest);
   }
 }
 
 /// Removes uninteresting BBs from switch, if the default case ends up being
 /// uninteresting, the switch is replaced with a void return (since it has to be
 /// replace with something)
 static void removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
                                              std::set<BasicBlock *> BBsToKeep) {
   if (!BBsToKeep.count(SwInst.getDefaultDest())) {
     auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
     ReturnInst::Create(SwInst.getContext(),
-                       FnRetTy->isVoidTy() ? nullptr : UndefValue::get(FnRetTy),
+                       FnRetTy->isVoidTy() ? nullptr
+                                           : defaultValueForType(FnRetTy),
                        SwInst.getParent());
     SwInst.eraseFromParent();
   } else
     for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
       auto Case = SwInst.case_begin() + I;
       if (!BBsToKeep.count(Case->getCaseSuccessor())) {
         SwInst.removeCase(Case);
         --I;
for (auto &BB : F) {
       else
         replaceBranchTerminator(BB, BBsToKeep);
     }
 
   // Replace out-of-chunk switch uses
   for (auto &BB : BBsToDelete) {
     // Instructions might be referenced in other BBs
     for (auto &I : *BB)
-      I.replaceAllUsesWith(UndefValue::get(I.getType()));
+      I.replaceAllUsesWith(defaultValueForType(I.getType()));
     BB->eraseFromParent();
   }
 }
 
 /// Counts the amount of basic blocks and prints their name & respective index
 static int countBasicBlocks(Module *Program) {
   // TODO: Silence index with --quiet flag
   outs() << "----------------------------\n";

llvm/tools/llvm-reduce/deltas/ReduceFunctions.cpp

static void extractFunctionsFromModule(const std::vector<Chunk> &ChunksToKeep,
 
   // Then, drop body of each of them. We want to batch this and do nothing else
   // here so that minimal number of remaining exteranal uses will remain.
   for (Function &F : FuncsToRemove)
     F.dropAllReferences();
 
   // And finally, we can actually delete them.
   for (Function &F : FuncsToRemove) {
-    // Replace all *still* remaining uses with undef.
-    F.replaceAllUsesWith(UndefValue::get(F.getType()));
+    // Replace all *still* remaining uses.
+    F.replaceAllUsesWith(defaultValueForType(F.getType()));
     // And finally, fully drop it.
     F.eraseFromParent();
   }
 }
 
 /// Counts the amount of functions and prints their
 /// respective name & index
 static int countFunctions(Module *Program) {

llvm/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp

 //===- ReduceGlobalVars.cpp - Specialized Delta Pass ----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a function which calls the Generic Delta pass in order
 // to reduce Global Variables in the provided Module.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ReduceGlobalVars.h"
+#include "deltas/Delta.h"
 #include "llvm/IR/Constants.h"
 #include <set>
 
 using namespace llvm;
 
 /// Removes all the GVs that aren't inside the desired Chunks.
 static void extractGVsFromModule(std::vector<Chunk> ChunksToKeep,
                                  Module *Program) {
static void extractGVsFromModule(std::vector<Chunk> ChunksToKeep,
   std::vector<GlobalVariable *> ToRemove;
   std::vector<WeakVH> InstToRemove;
   for (auto &GV : Program->globals())
     if (!GVsToKeep.count(&GV)) {
       for (auto *U : GV.users())
         if (auto *Inst = dyn_cast<Instruction>(U))
           InstToRemove.push_back(Inst);
 
-      GV.replaceAllUsesWith(UndefValue::get(GV.getType()));
+      GV.replaceAllUsesWith(defaultValueForType(GV.getType()));
       ToRemove.push_back(&GV);
     }
 
   // Delete (unique) Instruction uses of unwanted GVs
   for (Value *V : InstToRemove) {
     if (!V)
       continue;
     auto *Inst = cast<Instruction>(V);
-    Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
+    Inst->replaceAllUsesWith(defaultValueForType(Inst->getType()));
     Inst->eraseFromParent();
   }
 
   for (auto *GV : ToRemove)
     GV->eraseFromParent();
 }
 
 /// Counts the amount of GVs and displays their

llvm/tools/llvm-reduce/deltas/ReduceInstructions.cpp

 //===- ReduceArguments.cpp - Specialized Delta Pass -----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a function which calls the Generic Delta pass in order
 // to reduce uninteresting Arguments from defined functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ReduceInstructions.h"
+#include "deltas/Delta.h"
 
 using namespace llvm;
 
 /// Removes out-of-chunk arguments from functions, and modifies their calls
 /// accordingly. It also removes allocations of out-of-chunk arguments.
 static void extractInstrFromModule(std::vector<Chunk> ChunksToKeep,
                                    Module *Program) {
   Oracle O(ChunksToKeep);
for (auto &BB : F) {
           InstToKeep.insert(&Inst);
     }
 
   std::vector<Instruction *> InstToDelete;
   for (auto &F : *Program)
     for (auto &BB : F)
       for (auto &Inst : BB)
         if (!InstToKeep.count(&Inst)) {
-          Inst.replaceAllUsesWith(UndefValue::get(Inst.getType()));
+          Inst.replaceAllUsesWith(defaultValueForType(Inst.getType()));
           InstToDelete.push_back(&Inst);
         }
 
   for (auto &I : InstToDelete)
     I->eraseFromParent();
 }
 
 /// Counts the amount of basic blocks and prints their name & respective index

llvm/tools/llvm-reduce/deltas/ReduceOperands.cpp

 //===- ReduceOperands.cpp - Specialized Delta Pass ------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a function to reduce operands to undef.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ReduceOperands.h"
+#include "Delta.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/InstIterator.h"
 
 using namespace llvm;
 
-/// Returns if the given operand is undef.
-static bool operandIsUndefValue(Use &Op) {
-  if (auto *C = dyn_cast<Constant>(Op)) {
-    return isa<UndefValue>(C);
-  }
-  return false;
-}
-
-/// Returns if an operand can be reduced to undef.
-/// TODO: make this logic check what types are reducible rather than
-/// check what types that are not reducible.
-static bool canReduceOperand(Use &Op) {
-  auto *Ty = Op->getType();
-  // Can't reduce labels to undef
-  return !Ty->isLabelTy() && !operandIsUndefValue(Op);
+/// Returns if an operand can be reduced to the given constant.
+static bool canReduceOperand(Use &Op, Constant *Reduced) {
+  return Reduced && dyn_cast<Constant>(&Op) != Reduced;
 }
 
 /// Sets Operands to undef.
 static void extractOperandsFromModule(std::vector<Chunk> ChunksToKeep,
                                       Module *Program) {
   Oracle O(ChunksToKeep);
 
   // Extract Operands from the module.
   for (auto &F : Program->functions()) {
     for (auto &I : instructions(&F)) {
       for (auto &Op : I.operands()) {
         // Filter Operands then set to undef.
-        if (canReduceOperand(Op) && !O.shouldKeep()) {
-          auto *Ty = Op->getType();
-          Op.set(UndefValue::get(Ty));
+        auto *Reduced = defaultValueForType(Op->getType());
+        if (canReduceOperand(Op, Reduced) && !O.shouldKeep()) {
+          Op.set(Reduced);
         }
       }
     }
   }
 }
 
 /// Counts the amount of operands in the module that can be reduced.
 static int countOperands(Module *Program) {
   int Count = 0;
   for (auto &F : Program->functions()) {
     for (auto &I : instructions(&F)) {
       for (auto &Op : I.operands()) {
-        if (canReduceOperand(Op)) {
+        if (canReduceOperand(Op, defaultValueForType(Op->getType()))) {
           Count++;
         }
       }
     }
   }
   return Count;
 }
 
 void llvm::reduceOperandsDeltaPass(TestRunner &Test) {
   errs() << "*** Reducing Operands...\n";
   int Count = countOperands(Test.getProgram());
   runDeltaPass(Test, Count, extractOperandsFromModule);
 }

llvm/tools/llvm-reduce/deltas/ReduceSpecialGlobals.cpp

 /// desired Chunks.
 static void
 extractSpecialGlobalsFromModule(const std::vector<Chunk> &ChunksToKeep,
                                 Module *Program) {
   Oracle O(ChunksToKeep);
 
   for (StringRef Name : SpecialGlobalNames) {
     if (auto *Used = Program->getNamedGlobal(Name)) {
-      Used->replaceAllUsesWith(UndefValue::get(Used->getType()));
+      Used->replaceAllUsesWith(defaultValueForType(Used->getType()));
       Used->eraseFromParent();
     }
   }
 }
 
 /// Counts the amount of special globals and prints their
 /// respective name & index
 static int countSpecialGlobals(Module *Program) {