[llvm-reduce] Skip terminators when reducing instructions.

[fhahn]

Summary

Removing terminators will result in invalid IR, making further
reductions pointless. I do not think there is any valid use case where
we actually want to create invalid IR as part of a reduction.

[arsenm]

Testcase? Does this fix https://bugs.llvm.org/show_bug.cgi?id=43798

[fhahn]

Add test for PR43798, adjust existing tests that checked that the terminator was actually removed.

[fhahn]

In D86210#2226119, @arsenm wrote:

Testcase? Does this fix https://bugs.llvm.org/show_bug.cgi?id=43798

Yes, it should fix the bug.

I missed the tests directory initially, assuming the tests would live under llvm/test/tools/llvm-reduce.. Added tests now.

[lebedev.ri]

Honestly i don't like this, mainly because this could result in valid reduction
deleting *all* instructions, but then yes, it more frequently results in broken IR.
So i think this will do after all. Thanks.

[fhahn]

In D86210#2232204, @lebedev.ri wrote:

Honestly i don't like this, mainly because this could result in valid reduction
deleting *all* instructions, but then yes, it more frequently results in broken IR.
So i think this will do after all. Thanks.

Thanks for taking a look! Happy to adjust things down the road if it turns out we are now missing any useful reductions.

llvm/test/Reduce/do-not-remove-terminator.ll

+; RUN: llvm-reduce --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: cat %t | FileCheck --check-prefixes=CHECK-FINAL %s
+
+; Make sure we do not remove the terminator of the entry block. The interesting
+; check only requires the result to define the function @test.
+
+; Test case for PR43798.
+
+; CHECK-INTERESTINGNESS: define i32 @test
+
+; CHECK-FINAL:      define i32 @test
+; CHECK-FINAL-NEXT: entry:
+; CHECK-FINAL-NEXT:   ret i32
+
+define i32 @test(i32 %x) {
+entry:
+  %add = add i32 %x, %x
+  ret i32 %add
+}

llvm/test/Reduce/remove-funcs.ll

entry:
   ; CHECK-INTERESTINGNESS: call i32 @interesting()
   %call2 = call i32 @interesting()
   %call = call i32 @uninteresting1()
   ret i32 5
 }
 
 ; CHECK-FINAL-NEXT: entry:
 ; CHECK-FINAL-NEXT:   %call2 = call i32 @interesting()
+; CHECK-FINAL-NEXT:   ret i32 5
 ; CHECK-FINAL-NEXT: }
 
 define i32 @uninteresting2() {
 entry:
   ret i32 0
 }
 
 declare void @uninteresting3()

llvm/test/Reduce/remove-instructions.ll

 ; Test that llvm-reduce can remove uninteresting instructions.
 ;
 ; RUN: llvm-reduce --test %python --test-arg %p/Inputs/remove-instructions.py %s -o %t
 ; RUN: cat %t | FileCheck -implicit-check-not=uninteresting %s
 ; REQUIRES: plugins
 
-; We're testing all direct uses of %interesting are conserved
+; We're testing all direct uses of %interesting are conserved. The terminator
+; (ret) must also be preserved.
+
 ; CHECK-COUNT-5: %interesting
+; CHECK: ret
+
 define i32 @main() #0 {
 entry:
   %uninteresting1 = alloca i32, align 4
   %interesting = alloca i32, align 4
   %uninteresting2 = alloca i32, align 4
   store i32 0, i32* %uninteresting1, align 4
   store i32 0, i32* %interesting, align 4
   %0 = load i32, i32* %interesting, align 4
   %uninteresting3 = add nsw i32 %0, 1
   store i32 %uninteresting3, i32* %interesting, align 4
   %1 = load i32, i32* %interesting, align 4
   store i32 %1, i32* %uninteresting2, align 4
-  ; CHECK-NOT: ret
   ret i32 0
 }

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

 /// accordingly. It also removes allocations of out-of-chunk arguments.
 static void extractInstrFromModule(std::vector<Chunk> ChunksToKeep,
                                    Module *Program) {
   Oracle O(ChunksToKeep);
 
   std::set<Instruction *> InstToKeep;
 
   for (auto &F : *Program)
-    for (auto &BB : F)
-      for (auto &Inst : BB)
+    for (auto &BB : F) {
+      // Removing the terminator would make the block invalid. Only iterate over
+      // instructions before the terminator.
+      InstToKeep.insert(BB.getTerminator());
+      for (auto &Inst : make_range(BB.begin(), std::prev(BB.end())))
         if (O.shouldKeep())
           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()));
           InstToDelete.push_back(&Inst);
         }
 
   for (auto &I : InstToDelete)
     I->eraseFromParent();
 }
 
 /// Counts the amount of basic blocks and prints their name & respective index
 static unsigned countInstructions(Module *Program) {
   // TODO: Silence index with --quiet flag
   outs() << "----------------------------\n";
   int InstCount = 0;
   for (auto &F : *Program)
     for (auto &BB : F)
-        InstCount += BB.getInstList().size();
+      // Well-formed blocks have terminators, which we cannot remove.
+      InstCount += BB.getInstList().size() - 1;
   outs() << "Number of instructions: " << InstCount << "\n";
 
   return InstCount;
 }
 
 void llvm::reduceInstructionsDeltaPass(TestRunner &Test) {
   outs() << "*** Reducing Insructions...\n";
   unsigned InstCount = countInstructions(Test.getProgram());
   runDeltaPass(Test, InstCount, extractInstrFromModule);
 }