[llvm-reduce] Try harder to not create invalid aliases

[aeubanks]

Summary

This was done by adding --abort-on-invalid-reduction to remove-function-bodies-used-in-globals.ll and fixing the fallout.

Aliases must have a GlobalValue or ConstantExpr aliasee and the aliasee must be a definition if it's a GlobalValue.
Don't RAUW functions with null if there's an alias pointing to it, and similarly don't delete the body of a function.
Don't delete the entire body of a function when reducing blocks, preserve at least one block.

Also make debugging these sorts of things easier by dumping the module when --abort-on-invalid-reduction triggers.

[regehr]

LGTM

I like the debug output and I also like making more test cases abort on invalid IR, we definitely have some bugs to flush out here.

llvm/test/tools/llvm-reduce/remove-bbs-comdat.ll

-; RUN: llvm-reduce --delta-passes=basic-blocks --abort-on-invalid-reduction --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
-; RUN: cat %t | FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL %s
-
-; CHECK-FINAL-NOT: = comdat
-; CHECK-INTERESTINGNESS: @callee(
-; CHECK-FINAL: declare void @callee()
-
-$foo = comdat any
-
-define void @callee() comdat($foo) {
-  ret void
-}
-
-; CHECK-ALL: define void @caller()
-define void @caller() {
-entry:
-; CHECK-ALL: call void @callee()
-; CHECK-ALL: ret void
-  call void @callee()
-  ret void
-}

llvm/test/tools/llvm-reduce/remove-bbs-entry.ll

-; Test that llvm-reduce correctly removes the entry block of functions for
-; linkages other than external and weak.
+; Test that llvm-reduce does not remove the entry block of functions.
 ;
 ; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=basic-blocks --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
 ; RUN: cat %t | FileCheck %s
 
-; CHECK-INTERESTINGNESS: interesting1:
+; CHECK-INTERESTINGNESS: foo
 
-; CHECK-NOT: uninteresting
-define linkonce_odr i32 @foo() {
+; CHECK: add i32
+define i32 @foo() {
 uninteresting:
+  %a = add i32 0, 0
   ret i32 0
 }
 
-define i32 @main(i1 %c) {
-interesting1:
-  ret i32 0
-}

llvm/test/tools/llvm-reduce/remove-function-bodies-used-in-globals.ll

-; RUN: llvm-reduce --test FileCheck --test-arg --check-prefix=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: llvm-reduce --test FileCheck --test-arg --check-prefix=CHECK-INTERESTINGNESS --abort-on-invalid-reduction --test-arg %s --test-arg --input-file %s -o %t
 ; RUN: FileCheck --check-prefix=CHECK-FINAL %s < %t
 
 ; We cannot change the @alias to undef, because it would result in invalid IR
 ; (Aliasee should be either GlobalValue or ConstantExpr).
 
 ; CHECK-INTERESTINGNESS: @alias =
 ; CHECK-FINAL: @alias = alias void (i32), ptr @func
 
 @alias = alias void (i32), ptr @func
 
 ; CHECK-FINAL: @func()
 
 define void @func(i32 %arg) {
 entry:
   ret void
 }

llvm/test/tools/llvm-reduce/temporary-files-as-bitcode-split.ll

 ; RUN: opt --thinlto-bc --thinlto-split-lto-unit %s -o %t0
-; RUN: llvm-reduce -write-tmp-files-as-bitcode --delta-passes=basic-blocks %t0 -o %t1 \
+; RUN: llvm-reduce -write-tmp-files-as-bitcode --delta-passes=function-bodies,basic-blocks %t0 -o %t1 \
 ; RUN:     --test %python --test-arg %p/Inputs/llvm-dis-and-filecheck.py --test-arg llvm-dis --test-arg FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s
 ; RUN: cat %t1* | FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL %s
 
 @g = internal global i8 42, !type !0
 
 ; CHECK-INTERESTINGNESS: @callee(
 ; CHECK-FINAL: declare void @callee()
 define void @callee() {

llvm/test/tools/llvm-reduce/temporary-files-as-bitcode.ll

-; RUN: llvm-reduce -write-tmp-files-as-bitcode --delta-passes=basic-blocks %s -o %t \
+; RUN: llvm-reduce -write-tmp-files-as-bitcode --delta-passes=function-bodies,basic-blocks %s -o %t \
 ; RUN:     --test %python --test-arg %p/Inputs/llvm-dis-and-filecheck.py --test-arg llvm-dis --test-arg FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s
 ; RUN: cat %t | FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL %s
 
 ; CHECK-INTERESTINGNESS: @callee(
 ; CHECK-FINAL: declare void @callee()
 define void @callee() {
   ret void
 }

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

CheckChunk(Chunk &ChunkToCheckForUninterestingness,
 
   // Generate Module with only Targets inside Current Chunks
   Oracle O(CurrentChunks);
   ExtractChunksFromModule(O, *Clone);
 
   // Some reductions may result in invalid IR. Skip such reductions.
   if (verifyReducerWorkItem(*Clone, &errs())) {
     if (AbortOnInvalidReduction) {
-      errs() << "Invalid reduction\n";
+      errs() << "Invalid reduction, aborting.\n";
+      Clone->print(errs());
       exit(1);
     }
     errs() << " **** WARNING | reduction resulted in invalid module, "
               "skipping\n";
     return nullptr;
   }
 
   errs() << "Ignoring: ";

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

for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
         --I;
         --E;
       }
     }
 }
 
 /// It's OK to add a block to the set of removed blocks if the first
 /// basic block in the function that survives all of the deletions is
-/// a legal entry block
+/// a legal entry block. Keep at least one block in a function.
 static bool okToRemove(BasicBlock &Candidate, Function &F,
                        const DenseSet<BasicBlock *> &BBsToDelete) {
+  size_t NumBlocksDeleted = 0;
+  bool FoundNewEntryBlock = false;
   for (auto &B : F) {
     if (&B == &Candidate)
       continue;
-    if (BBsToDelete.count(&B))
+    if (BBsToDelete.count(&B)) {
+      ++NumBlocksDeleted;
       continue;
+    }
+    if (!FoundNewEntryBlock) {
       /// Ok we've found the first block that's not going to be deleted,
       /// it will be the new entry block -- that's only legal if this
       /// block has no predecessors among blocks that survive the
       /// deletions
       for (BasicBlock *Pred : predecessors(&B)) {
         if (!BBsToDelete.contains(Pred))
           return false;
       }
-    return true;
+      FoundNewEntryBlock = true;
+    }
   }
-  return true;
+  // Don't delete the last block.
+  return NumBlocksDeleted + 1 < F.size();
 }
 
 /// Removes out-of-chunk arguments from functions, and modifies their calls
 /// accordingly. It also removes allocations of out-of-chunk arguments.
 static void extractBasicBlocksFromModule(Oracle &O, Module &Program) {
   DenseSet<BasicBlock *> BBsToKeep, BBsToDelete;
 
   for (auto &F : Program) {
for (auto &BB : F) {
         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(getDefaultValue(I.getType()));
-    if (BB->getParent()->size() == 1) {
-      // this is the last basic block of the function, thus we must also make
-      // sure to remove comdat and set linkage to external
-      auto F = BB->getParent();
-      F->deleteBody();
-      F->setComdat(nullptr);
-    } else {
-      BB->eraseFromParent();
-    }
-  }
-}
+    // Should not be completely removing the body of a function.
+    assert(BB->getParent()->size() > 1);
 
 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
-  outs() << "*** Reducing Basic Blocks...\n";
+  errs() << "*** Reducing Basic Blocks...\n";
   runDeltaPass(Test, extractBasicBlocksFromModule);
 }

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

 //===- ReduceFunctions.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 function bodies in the provided Module.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ReduceFunctionBodies.h"
 #include "Delta.h"
+#include "Utils.h"
 #include "llvm/IR/GlobalValue.h"
 
 using namespace llvm;
 
 /// Removes all the bodies of defined functions that aren't inside any of the
 /// desired Chunks.
 static void extractFunctionBodiesFromModule(Oracle &O, Module &Program) {
   // Delete out-of-chunk function bodies
-  std::vector<Function *> FuncDefsToReduce;
-  for (auto &F : Program)
-    if (!F.isDeclaration() && !O.shouldKeep()) {
+  for (auto &F : Program) {
+    if (!F.isDeclaration() && !hasAliasUse(F) && !O.shouldKeep()) {
       F.deleteBody();
       F.setComdat(nullptr);
     }
   }
+}
 
 void llvm::reduceFunctionBodiesDeltaPass(TestRunner &Test) {
   errs() << "*** Reducing Function Bodies...\n";
   runDeltaPass(Test, extractFunctionBodiesFromModule);
   errs() << "----------------------------\n";
 }

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

 // Module.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ReduceFunctions.h"
 #include "Delta.h"
 #include "Utils.h"
 #include "llvm/ADT/STLExtras.h"
-#include "llvm/IR/Constants.h"
-#include "llvm/IR/Instructions.h"
 #include <iterator>
 #include <vector>
 
 using namespace llvm;
 
 /// Removes all the Defined Functions
 /// that aren't inside any of the desired Chunks.
 static void extractFunctionsFromModule(Oracle &O, Module &Program) {
   // Record all out-of-chunk functions.
   std::vector<std::reference_wrapper<Function>> FuncsToRemove;
   copy_if(Program.functions(), std::back_inserter(FuncsToRemove),
           [&O](Function &F) {
             // Intrinsics don't have function bodies that are useful to
             // reduce. Additionally, intrinsics may have additional operand
             // constraints. But, do drop intrinsics that are not referenced.
-            return (!F.isIntrinsic() || F.use_empty()) && !O.shouldKeep();
+            return (!F.isIntrinsic() || F.use_empty()) && !hasAliasUse(F) &&
+                   !O.shouldKeep();
           });
 
   // 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.

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

 //===- Utils.h - llvm-reduce utility functions ----------------------------===//
 //
 // 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 some utility functions supporting llvm-reduce.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_UTILS_H
 #define LLVM_TOOLS_LLVM_REDUCE_DELTAS_UTILS_H
 
+#include "llvm/IR/Function.h"
 #include "llvm/IR/Value.h"
 
 namespace llvm {
 
 Value *getDefaultValue(Type *T);
+bool hasAliasUse(Function &F);
 
 } // namespace llvm
 
 #endif

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

 //===- Utils.cpp - llvm-reduce utility functions --------------------------===//
 //
 // 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 some utility functions supporting llvm-reduce.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Utils.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/GlobalAlias.h"
 
 using namespace llvm;
 
 Value *llvm::getDefaultValue(Type *T) {
   return T->isVoidTy() ? PoisonValue::get(T) : Constant::getNullValue(T);
 }
+
+bool llvm::hasAliasUse(Function &F) {
+  return any_of(F.users(), [](User *U) { return isa<GlobalAlias>(U); });
+}